Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
Public Types | Static Public Member Functions | Static Public Attributes | List of all members
bb::ECCVMMSMRelationImpl< FF_ > Class Template Reference

MSM relations that evaluate the Strauss multiscalar multiplication algorithm. More...

#include <ecc_msm_relation.hpp>

Public Types

using FF = FF_
 

Static Public Member Functions

template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
static void accumulate (ContainerOverSubrelations &accumulator, const AllEntities &in, const Parameters &, const FF &scaling_factor)
 MSM relations that evaluate the Strauss multiscalar multiplication algorithm.
 

Static Public Attributes

static constexpr std::array< size_t, 36 > SUBRELATION_PARTIAL_LENGTHS
 

Detailed Description

template<typename FF_>
class bb::ECCVMMSMRelationImpl< FF_ >

MSM relations that evaluate the Strauss multiscalar multiplication algorithm.

The Strauss algorithm for a size-k MSM takes scalars/points (a_i, [P_i]) for i = 0 to k-1. The specific algoritm we use is the following:

PHASE 1: Precomputation (performed in ecc_wnaf_relation.hpp, ecc_point_table_relation.hpp) Each scalar a_i is split into 4-bit WNAF slices s_{j, i} for j = 0 to 31, and a skew bool skew_i For each point [P_i] a size-16 lookup table of points, T_i, is computed { [-15 P_i], [-13 P_i], ..., [15 P_i] }

PHASE 2: MSM evaluation MSM evaluation is split into 32 rounds that operate on an accumulator point [Acc] The first 31 rounds are composed of an ADDITION round and a DOUBLE round. The final 32nd round is composed of an ADDITION round and a SKEW round.

ADDITION round (round = j): [Acc] = [Acc] + T_i[a_{i, j}] for all i in [0, ... k-1]

DOUBLE round: [Acc] = 16 * [Acc] (four point doublings)

SKEW round: If skew_i == 1, [Acc] = [Acc] - [P_i] for all i in [0, ..., k - 1]

The relations in ECCVMMSMRelationImpl constrain the ADDITION, DOUBLE and SKEW rounds

Parameters
evalstransformed to evals + C(in(X)...)*scaling_factor
inan std::array containing the fully extended Accumulator edges.
parameterscontains beta, gamma, and public_input_delta, ....
scaling_factoroptional term to scale the evaluation before adding to evals.

Definition at line 43 of file ecc_msm_relation.hpp.

Member Typedef Documentation

◆ FF

template<typename FF_ >
using bb::ECCVMMSMRelationImpl< FF_ >::FF = FF_

Definition at line 45 of file ecc_msm_relation.hpp.

Member Function Documentation

◆ accumulate()

template<typename FF >
template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
void bb::ECCVMMSMRelationImpl< FF >::accumulate ( ContainerOverSubrelations &  accumulator,
const AllEntities &  in,
const Parameters &  ,
const FF &  scaling_factor 
)
static

MSM relations that evaluate the Strauss multiscalar multiplication algorithm.

The Strauss algorithm for a size-k MSM takes scalars/points (a_i, [P_i]) for i = 0 to k-1. The specific algoritm we use is the following:

PHASE 1: Precomputation (performed in ecc_wnaf_relation.hpp, ecc_point_table_relation.hpp) Each scalar a_i is split into 4-bit WNAF slices s_{j, i} for j = 0 to 31, and a skew bool skew_i For each point [P_i] a size-16 lookup table of points, T_i, is computed { [-15 P_i], [-13 P_i], ..., [15 P_i] }

PHASE 2: MSM evaluation MSM evaluation is split into 32 rounds that operate on an accumulator point [Acc] The first 31 rounds are composed of an ADDITION round and a DOUBLE round. The final 32nd round is composed of an ADDITION round and a SKEW round.

ADDITION round (round = j): [Acc] = [Acc] + T_i[a_{i, j}] for all i in [0, ... k-1]

DOUBLE round: [Acc] = 16 * [Acc] (four point doublings)

SKEW round: If skew_i == 1, [Acc] = [Acc] - [P_i] for all i in [0, ..., k - 1]

The relations in ECCVMMSMRelationImpl constrain the ADDITION, DOUBLE and SKEW rounds

Parameters
evalstransformed to evals + C(in(X)...)*scaling_factor
inan std::array containing the fully extended Accumulator edges.
parameterscontains beta, gamma, and public_input_delta, ....
scaling_factoroptional term to scale the evaluation before adding to evals.

Evaluating ADDITION rounds

This comment describes the algorithm we want the Prover to perform. The relations we constrain are supposed to make an honest Prover compute witnesses consistent with the following:

For an MSM of size-k...

Algorithm to determine if round at shifted row is an ADDITION round:

  1. count_shift < msm_size
  2. round != 32

Algorithm to process MSM ADDITION round:

  1. If round == 0 set count = 0
  2. For j = pc + count, perform the following: 2a. If j + 3 < k: [P_{j + 3}] = T_{j+ 3}[slice_{j + 3}] 2b. If j + 2 < k: [P_{j + 2}] = T_{j+ 2}[slice_{j + 2}] 2c. If j + 1 < k: [P_{j + 1}] = T_{j+ 1}[slice_{j + 1}] 2d. [P_{j}] = T_{j}[slice_{j}] 2e. If j + 3 < k: [Acc_shift] = [Acc] + [P_j] + [P_{j+1}] + [P_{j+2}] + [P_{j+3}] 2f. Else If j + 2 < k: [Acc_shift] = [Acc] + [P_j] + [P_{j+1}] + [P_{j+2}] 2g. Else IF j + 1 < k: [Acc_shift] = [Acc] + [P_j] + [P_{j+1}] 2h. Else : [Acc_shift] = [Acc] + [P_j]
  3. count_shift = count + 1 + (j + 1 < k) + (j + 2 < k) + (j + 3 < k)

Constraining addition rounds

The boolean column q_add describes whether a round is an ADDITION round. The values of q_add are Prover-defined. We need to ensure they set q_add correctly. We rely on the following statements that we assume are constrained to be true (from other relations):

  1. The set of reads into (pc, round, wnaf_slice) is constructed when q_add = 1
  2. The set of reads into (pc, round, wnaf_slice) must match the set of writes from the point_table columns
  3. The set of writes into (pc, round, wnaf_slice) from the point table columns is correct
  4. round only updates when q_add = 1 at current row and q_add = 0 at next row If a Prover sets q_add = 0 when an honest Prover would set q_add = 1, this will produce an inequality in the set of reads / writes into the (pc, round, wnaf_slice) table.

The addition algorithm has several IF/ELSE statements based on comparing count with msm_size. Instead of directly constraining these, we define 4 boolean columns q_add1, q_add2, q_add3, q_add4. Like q_add, their values are Prover-defined. We need to ensure they are set correctly. We update the above conditions on reads into (pc, round, wnaf_slice) to the following:

  1. The set of reads into (pc_{count}, round, wnaf_slice_{count}) is constructed when q_add = 1 AND q_add1 = 1
  2. The set of reads into (pc_{count + 1}, round, wnaf_slice_{count + 1}) is constructed when q_add = 1 AND q_add2 = 1
  3. The set of reads into (pc_{count + 2}, round, wnaf_slice_{count + 2}) is constructed when q_add = 1 AND q_add3 = 1
  4. The set of reads into (pc_{count + 3}, round, wnaf_slice_{count + 3}) is constructed when q_add = 1 AND q_add4 = 1

To ensure that all q_addi values are correctly set we apply consistency checks to q_add1/q_add2/q_add3/q_add4:

  1. If q_add2 = 1, require q_add1 = 1
  2. If q_add3 = 1, require q_add2 = 1
  3. If q_add4 = 1, require q_add3 = 1
  4. If q_add1_shift = 1 AND round does not update between rows, require q_add4 = 1

We want to use all of the above to reason about the set of reads into (pc, round, wnaf_slice). The goal is to conclude that any case where the Prover incorrectly sets q_add/q_add1/q_add2/q_add3/q_add4 will produce a set inequality between the reads/writes into (pc, round, wnaf_slice)

Addition relation

All addition operations in ECCVMMSMRelationImpl are conditional additions! This method returns two Accumulators that represent x/y coord of output. Output is either an addition of inputs, or xa/ya dpeending on value of selector. Additionally, we require lambda = 0 if selector = 0. The collision_relation accumulator tracks a subrelation that validates xb != xa. Repeated calls to this method will increase the max degree of the Accumulator output Degree of x_out, y_out = max degree of x_a/x_b + 1 4 Iterations will produce an output degree of 6

First Addition relation

The first add operation per row is treated differently. Normally we add the point xa/ya with an accumulator xb/yb, BUT, if this row STARTS a multiscalar multiplication, We need to add the point xa/ya with the "offset generator point" xo/yo The offset generator point's purpose is to ensure that no intermediate computations in the MSM will produce points at infinity, for an honest Prover. (we ensure soundness by validating the x-coordinates of xa/xb are not the same i.e. incomplete addition formula edge cases have not been hit) Note: this technique is only statistically complete, as there is a chance of an honest Prover creating a collision, but this probability is equivalent to solving the discrete logarithm problem

doubles a point.

Degree of x_out = 2 Degree of y_out = 3 Degree of relation = 4

Algorithm to determine if round is a DOUBLE round:

  1. count_shift >= msm_size
  2. round != 32

Algorithm to process MSM DOUBLE round: [Acc_shift] = (([Acc].double()).double()).double()

As with additions, the column q_double describes whether row is a double round. It is Prover-defined. The value of msm_round can only update when q_double = 1 and we use this to ensure Prover correctly sets q_double. (see round transition relations further down)

SKEW operations When computing x * [P], if x is even we must subtract [P] from accumulator (this is because our windowed non-adjacent-form can only represent odd numbers) Round 32 represents "skew" round. If scalar slice == 7, we add into accumulator (point_table[7] maps to -[P]) If scalar slice == 0, we do not add into accumulator i.e. for the skew round we can use the slice values as our "selector" when doing conditional point adds

Definition at line 47 of file ecc_msm_relation_impl.hpp.

Member Data Documentation

◆ SUBRELATION_PARTIAL_LENGTHS

template<typename FF_ >
constexpr std::array<size_t, 36> bb::ECCVMMSMRelationImpl< FF_ >::SUBRELATION_PARTIAL_LENGTHS
staticconstexpr
Initial value:
{ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 }

Definition at line 46 of file ecc_msm_relation.hpp.

The documentation for this class was generated from the following files: