|
barretenberg
|
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_{31 - i} |
| 0 | 2 | s8,s9,s10,s11 | 0 | \sum_{i=0}^8 16^i * s_{31 - i} |
| 0 | 3 | s12,s13,s14,s14 | 0 | \sum_{i=0}^12 16^i * s_{31 - i} |
| 0 | 4 | s16,s17,s18,s19 | 0 | \sum_{i=0}^16 16^i * s_{31 - i} |
| 0 | 5 | s20,s21,s22,s23 | 0 | \sum_{i=0}^20 16^i * s_{31 - i} |
| 0 | 6 | s24,s25,s26,s27 | 0 | \sum_{i=0}^24 16^i * s_{31 - i} |
| 1 | 7 | s28,s29,s30,s31 | s_skew | \sum_{i=0}^28 16^i * s_{31 - i} |
The value of the input scalar is equal to the following:
scalar = 2^16 * scalar_sum + 2^12 * s31 + 2^8 * s30 + 2^4 * s29 + s28 - s_skew We use a set equality check in ecc_set_relation.hpp to validate the above value maps to the correct input scalar for a given value of pc.
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 |
|
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_{31 - i} |
| 0 | 2 | s8,s9,s10,s11 | 0 | \sum_{i=0}^8 16^i * s_{31 - i} |
| 0 | 3 | s12,s13,s14,s14 | 0 | \sum_{i=0}^12 16^i * s_{31 - i} |
| 0 | 4 | s16,s17,s18,s19 | 0 | \sum_{i=0}^16 16^i * s_{31 - i} |
| 0 | 5 | s20,s21,s22,s23 | 0 | \sum_{i=0}^20 16^i * s_{31 - i} |
| 0 | 6 | s24,s25,s26,s27 | 0 | \sum_{i=0}^24 16^i * s_{31 - i} |
| 1 | 7 | s28,s29,s30,s31 | s_skew | \sum_{i=0}^28 16^i * s_{31 - i} |
The value of the input scalar is equal to the following:
scalar = 2^16 * scalar_sum + 2^12 * s31 + 2^8 * s30 + 2^4 * s29 + s28 - s_skew We use a set equality check in ecc_set_relation.hpp to validate the above value maps to the correct input scalar for a given value of pc.
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 | |
| 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
Round transition logic. Goal: round is an integer in [0, ... 7] that tracks how many slices we have processed for a given scalar. i.e. number of 4-bit WNAF slices processed = round * 4. We apply the following constraints: If q_transition = 0, round increments by 1 between rows. If q_transition = 1, round value at current row = 7 If q_transition = 1, round value at next row = 0 Question: is this sufficient? We don't actually range constrain round (expensive if we don't need to!). Let us analyze...
q_transition = 1, we use a set membership check to map the tuple of (pc, scalar_sum) into a set. We compare this set with an equivalent set generated from the transcript columns. The sets must match.i, a Prover can set round to value > 7 is if q_transition = 0 for all j > i. precompute_pc decrements by 1 when q_transition = 1 We can infer from 1, 2, that if round > 7, the resulting wnafs will map into a set at a value of pc that is greater than all valid msm pc values (assuming the set equivalence check on the scalar sums is satisfied). The resulting msm output of such a computation cannot be mapped into the set of msm outputs in the transcript columns (see relations in ecc_msm_relation.cpp). Conclusion: not applying a strict range-check on round does not affect soundness (TODO(@zac-williamson) validate this! #2225)Scalar transition 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
|
staticconstexpr |
1.9.6