- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
ECCVMWnafRelationImpl evaluates relations that convert scalar multipliers into 4-bit WNAF slices. More...
#include <ecc_wnaf_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) |
| ECCVMWnafRelationImpl evaluates relations that convert scalar multipliers into 4-bit WNAF slices. | |
Static Public Attributes | |
| static constexpr std::array< size_t, 21 > | SUBRELATION_PARTIAL_LENGTHS |
ECCVMWnafRelationImpl evaluates relations that convert scalar multipliers into 4-bit WNAF slices.
Each WNAF slice is a 4-bit slice representing one of 16 integers { -15, -13, ..., 15 } Each WNAF slice is represented via two 2-bit columns (precompute_s1hi, ..., precompute_s4lo) One 128-bit scalar multiplier is processed across 8 rows, indexed by a round variable. The following table describes the structure for one scalar.
| point_transition | round | slices | skew | scalar_sum |
|---|---|---|---|---|
| 0 | 0 | s0,s1,s2,s3 | 0 | 0 |
| 0 | 1 | s4,s5,s6,s7 | 0 | \sum_{i=0}^4 16^i * s_{3 - i} |
| 0 | 2 | s8,s9,s10,s11 | 0 | \sum_{i=0}^8 16^i * s_{7 - i} |
| 0 | 3 | s12,s13,s14,s14 | 0 | \sum_{i=0}^12 16^i * s_{11 - i} |
| 0 | 4 | s16,s17,s18,s19 | 0 | \sum_{i=0}^16 16^i * s_{15 - i} |
| 0 | 5 | s20,s21,s22,s23 | 0 | \sum_{i=0}^20 16^i * s_{19 - i} |
| 0 | 6 | s24,s25,s26,s27 | 0 | \sum_{i=0}^24 16^i * s_{23 - i} |
| 1 | 7 | s28,s29,s30,s31 | s_skew | \sum_{i=0}^28 16^i * s_{27 - i} |
The value of the input scalar is equal to the following:
scalar = 2^16 * scalar_sum + 2^12 * s28 + 2^8 * s29 + 2^4 * s30 + s31 - s_skew
We use a multiset equality check in ecc_set_relation.hpp to validate the above value maps to the correct input scalar for a given value of pc (i.e., for a given non-trivial EC point). In other words, this constrains that the wNAF expansion is correct. Note that, from the perpsective of the Precomputed table, we only add the tuple (pc, round, slice) to the multiset when point_transition == 1.
The column point_transition is committed to by the Prover, we must constrain it is correctly computed (see ecc_point_table_relation.cpp for details)
| FF |
Definition at line 43 of file ecc_wnaf_relation.hpp.
| using bb::ECCVMWnafRelationImpl< FF_ >::FF = FF_ |
Definition at line 45 of file ecc_wnaf_relation.hpp.
|
static |
ECCVMWnafRelationImpl evaluates relations that convert scalar multipliers into 4-bit WNAF slices.
Each WNAF slice is a 4-bit slice representing one of 16 integers { -15, -13, ..., 15 } Each WNAF slice is represented via two 2-bit columns (precompute_s1hi, ..., precompute_s4lo) One 128-bit scalar multiplier is processed across 8 rows, indexed by a round variable. The following table describes the structure for one scalar.
| point_transition | round | slices | skew | scalar_sum |
|---|---|---|---|---|
| 0 | 0 | s0,s1,s2,s3 | 0 | 0 |
| 0 | 1 | s4,s5,s6,s7 | 0 | \sum_{i=0}^4 16^i * s_{3 - i} |
| 0 | 2 | s8,s9,s10,s11 | 0 | \sum_{i=0}^8 16^i * s_{7 - i} |
| 0 | 3 | s12,s13,s14,s14 | 0 | \sum_{i=0}^12 16^i * s_{11 - i} |
| 0 | 4 | s16,s17,s18,s19 | 0 | \sum_{i=0}^16 16^i * s_{15 - i} |
| 0 | 5 | s20,s21,s22,s23 | 0 | \sum_{i=0}^20 16^i * s_{19 - i} |
| 0 | 6 | s24,s25,s26,s27 | 0 | \sum_{i=0}^24 16^i * s_{23 - i} |
| 1 | 7 | s28,s29,s30,s31 | s_skew | \sum_{i=0}^28 16^i * s_{27 - i} |
The value of the input scalar is equal to the following:
scalar = 2^16 * scalar_sum + 2^12 * s28 + 2^8 * s29 + 2^4 * s30 + s31 - s_skew
We use a multiset equality check in ecc_set_relation.hpp to validate the above value maps to the correct input scalar for a given value of pc (i.e., for a given non-trivial EC point). In other words, this constrains that the wNAF expansion is correct. Note that, from the perpsective of the Precomputed table, we only add the tuple (pc, round, slice) to the multiset when point_transition == 1.
Furthermore, as the column point_transition is committed to by the Prover, we must constrain it is correctly computed (see also ecc_point_table_relation.cpp for a description of what the table looks like.)
| FF | |
| AccumulatorTypes |
Constrain each of our scalar slice chunks (s1, ..., s8) to be 2 bits. Doing range checks this way vs permutation-based range check removes need to create sorted list + grand product polynomial. Probably cheaper even if we have to split each 4-bit WNAF slice into 2-bit chunks.
If we are processing a new scalar (q_transition = 1), validate that the first slice is positive. This requires us to validate slice1 is in the range [8, ... 15]. (when converted into wnaf form this maps to the range [1, 3, ..., 15]). We do this to ensure the final scalar sum is positive. We already know slice1 is in the range [0, ..., 15] To check the range [8, ..., 15] we validate the most significant 2 bits (s1) are >=2
Convert each pair of 2-bit scalar slices into a 4-bit windowed-non-adjacent-form slice. Conversion from binary -> wnaf = 2 * binary - 15. Converts a value in [0, ..., 15] into [-15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11 , 13, 15]. We use WNAF representation to avoid case where we are conditionally adding a point in our MSM algo.
Slice consistency check. We require that scalar_sum on the next row correctly accumulates the 4 WNAF slices present on the current row (i.e. 16 WNAF bits). i.e. next_scalar_sum - 2^{16} * current_scalar_sum - 2^12 * w_0 - 2^8 * w_1 - 2^4 * w_2 - w_3 = 0
Transition logic with round and q_transition. Goal: round is an integer in [0, ... 7] that tracks how many slices we have processed for a given scalar. i.e., the number of 4-bit WNAF slices processed = round * 4. We must ensure that q_transition is well-formed and that round is correctly constrained. Recall that pc stands for point-counter.
For the former, we force the following:
q_transition == 1, then scalar_sum_shift == 0, round_shift == 0, round == 7, and pc_shift == pc - 1.q_transition == 0, then round_shift - round == 1 and pc_shift == pcFor the latter: note that we don't actually range-constrain round (expensive if we don't need to!). We nonetheless can correctly constrain round, because of the multiset checks. There are two multiset equality checks that we perform that implicate the wNAF relation:
q_transition == 1. (It is helpful to recall that pc is monotonic: one per each point involved in a non-trivial scalar multiplication.)Here is the logic. We must ensure that round can never be set to a value > 7. If this were possible at row i, then q_transition == 0 for all subsequent rows by the incrementing logic. There are (at least) two problems.
4 * round and 4 * round + 3 (in fact 4 * round + 4 iff we are at a skew). As the round must increment, this means that the msm_round will be larger than 32, which can't happen due to the internal constraints in the MSM table. In particular, the multiset equality check will fail, as the MSM tables can never send an entry with a round larger than 32.precompute_pc to be constant from here on out. This will violate the multiset equalities both of terms (1) and (2). For the former, we will write too many entries with the given pc. (However, we've already shown how this multset equality fails due to round.) More importantly, for the latter, we will never "send" the tuple (pc, P.x, P.x, scalar-multiplier) to the multiset, for this value of pc and all potentially subsequent values. We explicate this latter failure. The transcript table will certainly fill some values in for (pc, P.x, P.y, scalar-multipler) (at least with correct pc and scalar-multiplier values), which will cause the multiset equality check to fail.As always, we are relying on the monotonicity of the pc in these arguments.
Scalar transition/PC checks. 1: if q_transition = 1, scalar_sum_new = 0 2: if q_transition = 0, pc at next row = pc at current row 3: if q_transition = 1, pc at next row = pc at current row - 1 (decrements by 1) (we combine 2 and 3 into a single relation)
Validate skew is 0 or 7 7 is the wnaf representation of -1. We have one skew variable per scalar multiplier. We can only represent odd integers in WNAF form. If input scalar is even, we must subtract 1 from WNAF scalar sum to get actual value (i.e. where skew = 7) We use skew in two places. 1: when validating sum of wnaf slices matches input scalar (we add skew to scalar_sum in ecc_set_relation) 2: in ecc_msm_relation. Final MSM round uses skew to conditionally subtract a point from the accumulator
Definition at line 46 of file ecc_wnaf_relation_impl.hpp.
|
staticconstexpr |
Definition at line 47 of file ecc_wnaf_relation.hpp.
1.9.8