- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
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 |
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
| evals | transformed to evals + C(in(X)...)*scaling_factor |
| in | an std::array containing the fully extended Accumulator edges. |
| parameters | contains beta, gamma, and public_input_delta, .... |
| scaling_factor | optional term to scale the evaluation before adding to evals. |
Definition at line 43 of file ecc_msm_relation.hpp.
| using bb::ECCVMMSMRelationImpl< FF_ >::FF = FF_ |
Definition at line 45 of file ecc_msm_relation.hpp.
|
static |
MSM relations that evaluate the Strauss multiscalar multiplication algorithm.
The Straus algorithm for a size-k MSM takes scalars/points (a_i, [P_i]) for i = 0 to k-1. The specific algorithm we use may be found here. We briefly reprise the algorithm nonetheless.
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
| evals | transformed to evals + C(in(X)...)*scaling_factor |
| in | an std::array containing the fully extended Accumulator edges. |
| parameters | contains beta, gamma, and public_input_delta, .... |
| scaling_factor | optional 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:
Algorithm to process MSM ADDITION round:
round == 0 set count = 0count_shift = count + 1 + (j + 1 < k) + (j + 2 < k) + (j + 3 < k)Constraining addition rounds via a multiset-equality check
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 will do this via a multiset-equality check (formerly called a "strict lookup"), which allows the various tables to "communicate". On a high level, this table "reads" (pc, round, wnaf_slice), another table (Precomputed) "writes" a potentially different set of (pc, round, wnaf_slice), and we demand that the reads match the writes. Alternatively said, the MSM columns spawn a multiset of tuples of the form (pc, round, wnaf_slice), the Precomputed Table columns spawn a potentially different multiset of tuples of the form (pc, round, wnaf_slice), and we check that these two multisets match.
The above description does not reference how we will prove that the two multisets are equal. As usual, we use a grand product argument. A happy byproduct of this is that we can use the grand product technique, which is powerful enough to allow our multiset equality testing to support conditional adds; this means that we only add a tuple if some particular condition occurs.
This (pc, round, wnaf_slice) multiset equality testing is made more difficult by the fact that the values of precomputed_pc are not the same as the values of msm_pc. The former indexes over every (non-trivial, 128 bit) scalar multiplication, while the latter jumps values and is constant on MSM rows corresponding to a fixed MSM. However, the transition values should match.
Given a row of the MSM table, we have four selectors q_add1, q_add2, q_add3, q_add4, as well as a q_skew selector. For the MSM side of the multiset corresponding to (pc, round, wnaf_slice), we add:
1. (msm_pc - msm_count, round, wnaf_slice_{count}) when q_add1 = 1
2. (msm_pc - msm_count - 1, round, wnaf_slice_{count + 1}) when q_add2 = 1
3. (msm_pc - msm_count - 2, round, wnaf_slice_{count + 2}) when q_add3 = 1
4. (msm_pc - msm_count - 3, round, wnaf_slice_{count + 3}) when q_add4 = 1
That this is "what we want" comes from the following facts: msm_pc is the number of (non-trivial, 128-bit) Point multiplications we have done until the start of the current MSM, and msm_count is the number of Point * wNAF slice multiplications/lookups we have done in this round. (Recall that a round corresponds to a wNAF digit.) In particular, msm_count updates by the appropriate amount (usually 4, more accurately q_add1 + q_add2 + q_add3 + q_add4) per row of the MSM table.
On the other side, given a row of the Precomputed columns, if precompute_select == 1, we add
ELSE precompute_select == 0 and we add:
Here, w_K is the compressed wNAF slices corresponding to precompute_sKhi and precompute_sKlo, for K ∈ {1, 2, 3, 4} and precompute_skew ∈ {0, 7}.
SKETCH OF PROOF: We now argue that, under the following assumptions, if the multiset equality holds, then the q_addK and also q_add are all correctly constrained for K ∈ {1, 2, 3, 4}.
precompute_pc, precompute_round, precompute_skew, precompute_select, and wK are all correctly constrained.round monotonically increases from 0 to 32 before reseting back to 0. round_shift - round == 1 precisely when q_double == 1.pc is monotonic and only updates when there is an msm_transition. Here, it updates by msm_size, which must be constrained somewhere else by a multiset argument. We detail this below.q_add, q_skew, and q_double are pairwise mutually exclusive.q_add1 == 1 iff either q_add == 1 OR q_skew == 1.First of all, note the asymmetry: we do not explicitly add tuples corresponding to skew on the MSM side of the table. Indeeed, this is implicit with msm_round == 32. Now, the point is that the pair (pc, round) uniquely specifies the point + wNAF digit that we are processing (and adding to the accumulator) and both pc and round are directly constrained to be monotonic.
Suppose the Prover sets q_addK = 0 when an honest Prover would set q_addK == 1. Then there would be some (pc, round, wnaf_slice) that the Precomputed table added to its multiset that the prover did not add. The Prover can never "compensate" for this, as pc is locally constrained to be monotonic and round is constrained to be periodic; this means that the Prover has "lost their chance" to add this element to the multiset and hence the multiset equality check will fail.
Conversely, if the Prover sets q_addK = 1 when it should be set to 0, there are several options: either we are at the end of a round (so e.g. q_add4 should be 0), or we are at a double row, or we are at a row that should be all 0s. In the first two cases, as long as the Precomputed table is correctly constrained, again we would be adding a tuple to the multiset that can never be hit by the Precomputed table due to precompute_pc monotonicty and precompute_round periodicity (enforced in the precomputed columns.). In the final case, the only way we don't break the multiset check is if wnaf_slice == 0 for the corresponding q_addK that is on. But then the lookup argument will fail, as there is no corresponding point when pc = 0. (Here it is helpful to remember that pc stands for point-counter.) Note that this requires that precompute_pc is well-formed.
We apply consistency/continuity checks to q_add1/q_add2/q_add3/q_add4:
Constrain msm_size and output of MSM computation via multiset equality
As explained in the section on constraining the addition wire values, to make everything work we also need to constrain msm_size, something directly computed in the Transcript columns. We also need to "send" the final output value of an MSM from the MSM table to the transcript table so it can continue its processing. (Send here is a euphemism for constrain.) We do this via a multiset equality check of the form: (pc, P.x, P.y, msm-size) From the perspective of the MSM table, we add such a tuple only at an msm_transition. The terms P.x and P.y refer to the output values of the MSM just computed by the MSM table. msm_size is the size of the just completed MSM.
Looking up the slice-point products {-15[P], -13[P], ..., 13[P], 15[P]}
In the Point Table, for every point [P] that occurs in the MSM table, we compute the list of points: {-15[P], -13[P], ..., 13[P], 15[P]}. (Note that these never vanish, as we only send a point to each table if they are non-zero.) We then constrain the "slice products" that occur here via a lookup argument. For completeness, we briefly sketch this.
The PointTable will "write" the following row to the lookup table: (pc, slice, x, y), where if pc corresponds to an elliptic curve point [P] (pc is a decreasing counter of the non-zero points that occur in our computation), slice ∈ {0, ..., 15}, and (x, y) are the affine coordinates of (2 * slice - 15)[P].
The MSM table will then read a row of the same form. This constrains the MSM table to have correctly used the wNAF * point in the Straus algorithm.
Addition relation
All addition operations in ECCVMMSMRelationImpl are conditional additions, as we sometimes want to add values and other times simply want to propagate values. (consider, e.g., when q_add2 == 0.) This method returns two Accumulators that represent x/y coord of output. Output is either an addition of inputs (if selector == 1), or xa/ya (if selector == 0). 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: deg(x_out) = 1 + max(deg(xa, xb)), deg(y_out) = max(1 + deg(x_out), 1 + deg(ya)) in our application, we chain together 4 of these with the pattern in such a way that the final x_out will have degree 5 and the final y_out will have degree 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:
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. The reason for this is that msm_round witnesses the wNAF digit we are processing, and we only perform the four doublings when we are done processing a wNAF digit. 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
As with addition and doubling, the column q_skew is prover-defined. It is precisely turned on when the round is 32. We implement this constraint slightly differently. For more details, see the round transition relations below.
Definition at line 48 of file ecc_msm_relation_impl.hpp.
|
staticconstexpr |
Definition at line 46 of file ecc_msm_relation.hpp.
1.9.8