- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
#include <biggroup.hpp>
Classes | |
| struct | batch_lookup_table_base |
| struct | batch_lookup_table_plookup |
| struct | chain_add_accumulator |
| struct | eight_bit_fixed_base_table |
| struct | four_bit_table_plookup |
| struct | lookup_table_base |
| struct | lookup_table_plookup |
| struct | secp256k1_wnaf |
| struct | secp256k1_wnaf_pair |
Public Types | |
| using | Builder = Builder_ |
| using | bool_ct = stdlib::bool_t< Builder > |
| using | biggroup_tag = element |
| using | BaseField = Fq |
Public Member Functions | |
| element () | |
| element (const typename NativeGroup::affine_element &input) | |
| element (const Fq &x, const Fq &y) | |
| element (const element &other) | |
| element (element &&other) noexcept | |
| uint32_t | set_public () const |
| Set the witness indices for the x and y coordinates to public. | |
| void | validate_on_curve () const |
| void | convert_constant_to_fixed_witness (Builder *builder) |
| Creates fixed witnesses from a constant element. | |
| void | fix_witness () |
| element & | operator= (const element &other) |
| element & | operator= (element &&other) noexcept |
| byte_array< Builder > | to_byte_array () const |
| element | checked_unconditional_add (const element &other) const |
| element | checked_unconditional_subtract (const element &other) const |
| element | operator+ (const element &other) const |
| element | operator- (const element &other) const |
| element | operator- () const |
| element | operator+= (const element &other) |
| element | operator-= (const element &other) |
| std::array< element, 2 > | checked_unconditional_add_sub (const element &) const |
| Compute (*this) + other AND (*this) - other as a size-2 array. | |
| element | operator* (const Fr &other) const |
| element | conditional_negate (const bool_ct &predicate) const |
| element | normalize () const |
| element | scalar_mul (const Fr &scalar, const size_t max_num_bits=0) const |
Implements scalar multiplication that supports short scalars. For multiple scalar multiplication use one of the batch_mul methods to save gates. | |
| element | reduce () const |
| element | dbl () const |
| element | montgomery_ladder (const element &other) const |
| element | montgomery_ladder (const chain_add_accumulator &accumulator) |
| element | multiple_montgomery_ladder (const std::vector< chain_add_accumulator > &to_add) const |
| Perform repeated iterations of the montgomery ladder algorithm. | |
| element | quadruple_and_add (const std::vector< element > &to_add) const |
| Compute 4.P + to_add[0] + ... + to_add[to_add.size() - 1]. | |
| NativeGroup::affine_element | get_value () const |
| Builder * | get_context () const |
| Builder * | get_context (const element &other) const |
| bool_ct | is_point_at_infinity () const |
| void | set_point_at_infinity (const bool_ct &is_infinity) |
| element | get_standard_form () const |
| Enforce x and y coordinates of a point to be (0,0) in the case of point at infinity. | |
| void | set_origin_tag (OriginTag tag) const |
| OriginTag | get_origin_tag () const |
| void | unset_free_witness_tag () |
| Unset the free witness flag for the element's tags. | |
| void | set_free_witness_tag () |
| Set the free witness flag for the element's tags. | |
| template<size_t max_num_bits> | |
| element< C, Fq, Fr, G > | wnaf_batch_mul (const std::vector< element > &_points, const std::vector< Fr > &_scalars) |
| Multiscalar multiplication that utilizes 4-bit wNAF lookup tables. | |
| template<typename , typename > requires (IsNotMegaBuilder<C>) | |
| element< C, Fq, Fr, G > | bn254_endo_batch_mul_with_generator (const std::vector< element > &big_points, const std::vector< Fr > &big_scalars, const std::vector< element > &small_points, const std::vector< Fr > &small_scalars, const Fr &generator_scalar, const size_t max_num_small_bits) |
| template<typename , typename > requires (IsNotMegaBuilder<C>) | |
| element< C, Fq, Fr, G > | bn254_endo_batch_mul (const std::vector< element > &big_points, const std::vector< Fr > &big_scalars, const std::vector< element > &small_points, const std::vector< Fr > &small_scalars, const size_t max_num_small_bits) |
| template<size_t max_num_bits, size_t WNAF_SIZE> | |
| std::vector< field_t< C > > | compute_wnaf (const Fr &scalar) |
| template<typename , typename > | |
| element< C, Fq, Fr, G > | secp256k1_ecdsa_mul (const element &pubkey, const Fr &u1, const Fr &u2) |
| template<size_t num_elements> | |
| std::array< twin_rom_table< C >, 5 > | create_group_element_rom_tables (const std::array< element, num_elements > &rom_data, std::array< uint256_t, 8 > &limb_max) |
| Constructs a ROM table to look up linear combinations of group elements. | |
| template<size_t > | |
| element< C, Fq, Fr, G > | read_group_element_rom_tables (const std::array< twin_rom_table< C >, 5 > &tables, const field_t< C > &index, const std::array< uint256_t, 8 > &limb_max) |
Static Public Member Functions | |
| static std::array< fr, PUBLIC_INPUTS_SIZE > | construct_dummy () |
| static element | reconstruct_from_public (const std::span< const Fr, PUBLIC_INPUTS_SIZE > &limbs) |
| Reconstruct a biggroup element from limbs of its coordinates (generally stored in the public inputs) | |
| static element | from_witness (Builder *ctx, const typename NativeGroup::affine_element &input) |
| static element | one (Builder *ctx) |
| static element | point_at_infinity (Builder *ctx) |
| static chain_add_accumulator | chain_add_start (const element &p1, const element &p2) |
| static chain_add_accumulator | chain_add (const element &p1, const chain_add_accumulator &accumulator) |
| static element | chain_add_end (const chain_add_accumulator &accumulator) |
| static std::pair< std::vector< element >, std::vector< Fr > > | mask_points (const std::vector< element > &_points, const std::vector< Fr > &_scalars) |
| Given two lists of points that need to be multiplied by scalars, create a new list of length +1 with original points masked, but the same scalar product sum. | |
| static std::pair< std::vector< element >, std::vector< Fr > > | handle_points_at_infinity (const std::vector< element > &_points, const std::vector< Fr > &_scalars) |
| Replace all pairs (∞, scalar) by the pair (one, 0) where one is a fixed generator of the curve. | |
| template<size_t max_num_bits = 0> | |
| static element | wnaf_batch_mul (const std::vector< element > &points, const std::vector< Fr > &scalars) |
| static element | batch_mul (const std::vector< element > &points, const std::vector< Fr > &scalars, const size_t max_num_bits=0, const bool with_edgecases=false) |
| Generic batch multiplication that works for all elliptic curve types. | |
| template<typename X = NativeGroup, typename = typename std::enable_if_t<std::is_same<X, bb::g1>::value>> requires (IsNotMegaBuilder<Builder>) | |
| static element | bn254_endo_batch_mul (const std::vector< element > &big_points, const std::vector< Fr > &big_scalars, const std::vector< element > &small_points, const std::vector< Fr > &small_scalars, const size_t max_num_small_bits) |
| template<typename X = NativeGroup, typename = typename std::enable_if_t<std::is_same<X, bb::g1>::value>> requires (IsNotMegaBuilder<Builder>) | |
| static element | bn254_endo_batch_mul_with_generator (const std::vector< element > &big_points, const std::vector< Fr > &big_scalars, const std::vector< element > &small_points, const std::vector< Fr > &small_scalars, const Fr &generator_scalar, const size_t max_num_small_bits) |
| template<typename X = NativeGroup, typename = typename std::enable_if_t<std::is_same<X, secp256k1::g1>::value>> | |
| static element | secp256k1_ecdsa_mul (const element &pubkey, const Fr &u1, const Fr &u2) |
| static std::vector< bool_ct > | compute_naf (const Fr &scalar, const size_t max_num_bits=0) |
| template<size_t max_num_bits = 0, size_t WNAF_SIZE = 4> | |
| static std::vector< field_t< Builder > > | compute_wnaf (const Fr &scalar) |
| template<size_t wnaf_size, size_t staggered_lo_offset = 0, size_t staggered_hi_offset = 0> | |
| static secp256k1_wnaf_pair | compute_secp256k1_endo_wnaf (const Fr &scalar) |
Public Attributes | |
| Fq | x |
| Fq | y |
Static Public Attributes | |
| static constexpr size_t | PUBLIC_INPUTS_SIZE = BIGGROUP_PUBLIC_INPUTS_SIZE |
Private Types | |
| using | twin_lookup_table = lookup_table_plookup< 2 > |
| using | triple_lookup_table = lookup_table_plookup< 3 > |
| using | quad_lookup_table = lookup_table_plookup< 4 > |
| using | batch_lookup_table = batch_lookup_table_plookup |
Static Private Member Functions | |
| template<size_t num_elements> | |
| static std::array< twin_rom_table< Builder >, 5 > | create_group_element_rom_tables (const std::array< element, num_elements > &elements, std::array< uint256_t, 8 > &limb_max) |
| template<size_t num_elements> | |
| static element | read_group_element_rom_tables (const std::array< twin_rom_table< Builder >, 5 > &tables, const field_t< Builder > &index, const std::array< uint256_t, 8 > &limb_max) |
| static std::pair< element, element > | compute_offset_generators (const size_t num_rounds) |
| static NativeGroup::affine_element | compute_table_offset_generator () |
| Compute an offset generator for use in biggroup tables. | |
| static std::pair< four_bit_table_plookup, four_bit_table_plookup > | create_endo_pair_four_bit_table_plookup (const element &input) |
| static std::pair< quad_lookup_table, quad_lookup_table > | create_endo_pair_quad_lookup_table (const std::array< element, 4 > &inputs) |
| static std::pair< lookup_table_plookup< 5 >, lookup_table_plookup< 5 > > | create_endo_pair_five_lookup_table (const std::array< element, 5 > &inputs) |
Private Attributes | |
| bool_ct | _is_infinity |
Definition at line 24 of file biggroup.hpp.
| using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::BaseField = Fq |
Definition at line 29 of file biggroup.hpp.
|
private |
Definition at line 1029 of file biggroup.hpp.
| using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::biggroup_tag = element |
Definition at line 28 of file biggroup.hpp.
| using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::bool_ct = stdlib::bool_t<Builder> |
Definition at line 27 of file biggroup.hpp.
| using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::Builder = Builder_ |
Definition at line 26 of file biggroup.hpp.
|
private |
Definition at line 554 of file biggroup.hpp.
|
private |
Definition at line 552 of file biggroup.hpp.
|
private |
Definition at line 550 of file biggroup.hpp.
| bb::stdlib::element_default::element< C, Fq, Fr, G >::element | ( | ) |
Definition at line 19 of file biggroup_impl.hpp.
| bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::element | ( | const typename NativeGroup::affine_element< Builder_, Fq, Fr, NativeGroup > & | input | ) |
Definition at line 33 of file biggroup_impl.hpp.
| bb::stdlib::element_default::element< C, Fq, Fr, G >::element | ( | const element< Builder_, Fq, Fr, NativeGroup > & | other | ) |
Definition at line 40 of file biggroup_impl.hpp.
|
noexcept |
Definition at line 47 of file biggroup_impl.hpp.
|
static |
Generic batch multiplication that works for all elliptic curve types.
Implementation is identical to bn254_endo_batch_mul but WITHOUT the endomorphism transforms OR support for short scalars See bn254_endo_batch_mul for description of algorithm.
| C | The circuit builder type. |
| Fq | The field of definition of the points in _points. |
| Fr | The field of scalars acting on _points. |
| G | The group whose arithmetic is emulated by element. |
| _points | |
| _scalars | |
| max_num_bits | The max of the bit lengths of the scalars. |
| with_edgecases | Use when points are linearly dependent. Randomises them. |
Definition at line 771 of file biggroup_impl.hpp.
|
static |
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::bn254_endo_batch_mul | ( | const std::vector< element< Builder_, Fq, Fr, NativeGroup > > & | big_points, |
| const std::vector< Fr > & | big_scalars, | ||
| const std::vector< element< Builder_, Fq, Fr, NativeGroup > > & | small_points, | ||
| const std::vector< Fr > & | small_scalars, | ||
| const size_t | max_num_small_bits | ||
| ) |
A batch multiplication method for the BN254 curve. This method is only available if Fr == field_t<bb::fr>
big_points : group elements we will multiply by full 254-bit scalar multipliers big_scalars : 254-bit scalar multipliers. We want to compute (\sum big_scalars[i] * big_points[i]) small_points : group elements we will multiply by short scalar mutipliers whose max value will be (1 << max_num_small_bits) small_scalars : short scalar mutipliers whose max value will be (1 << max_num_small_bits) max_num_small_bits : MINIMUM value must be 128 bits (we will be splitting big_scalars into two 128-bit scalars, we assume all scalars after this transformation are 128 bits)
Split big scalars into short 128-bit scalars.
For big_scalars we use the BN254 curve endomorphism to split the scalar into two short 128-bit scalars. i.e. for scalar multiplier k we derive 128-bit values k1, k2 where: k = k1 - k2 * \lambda (\lambda is the cube root of unity modulo the group order of the BN254 curve)
This ensures ALL our scalar multipliers can now be treated as 128-bit scalars, which halves the number of iterations of our main "double and add" loop!
Compute batch_lookup_table
batch_lookup_table implements a lookup table for a vector of points.
We subdivide batch_lookup_table into a set of 3-bit lookup tables, (using 2-bit and 1-bit tables if points.size() is not a multiple of 8)
We index the lookup table using a vector of NAF values for each point
e.g. for points P_1, .., P_N and naf values s_1, ..., s_n (where S_i = +1 or -1), the lookup table will compute:
\sum_{i=0}^n (s_i ? -P_i : P_i)
Compute scalar multiplier NAFs
A Non Adjacent Form is a representation of an integer where each 'bit' is either +1 OR -1, i.e. each bit entry is non-zero. This is VERY useful for biggroup operations, as this removes the need to conditionally add points depending on whether the scalar mul bit is +1 or 0 (instead we multiply the y-coordinate by the NAF value, which is cheaper)
The vector naf_entries tracks the naf set for each point, where each naf set is a vector of bools if naf[i][j] = 0 this represents a NAF value of -1 if naf[i][j] = 1 this represents a NAF value of +1
Initialize accumulator point with an offset generator. See compute_offset_generators for detailed explanation
Get the initial entry of our point table. This is the same as point_table.get_accumulator for the most significant NAF entry. HOWEVER, we know the most significant NAF value is +1 because our scalar muls are positive. get_initial_entry handles this special case as it's cheaper than point_table.get_accumulator
Main "double and add" loop
Each loop iteration traverses TWO bits of our scalar multiplier. Algorithm performs following:
2*i - 1 for each scalar multiplier and store in nafs vector.nafs vector to derive the point that we need (add_1) to add into our accumulator.2 * i (add_2)accumulator = 4 * accumulator + 2 * add_1 + add_2 using multiple_montgomery_ladder methodThe purpose of the above is to minimize the number of required range checks (vs a simple double and add algo).
When computing repeated iterations of the montgomery ladder algorithm, we can neglect computing the y-coordinate of each ladder output. See multiple_montgomery_ladder for more details.
Recovering a point from our point table requires group additions iff the table is >3 bits. We can chain repeated add operations together without computing the y-coordinate of intermediate addition outputs.
This is represented using the chain_add_accumulator type. See the type declaration for more details
(this is cheaper than regular additions iff point_table.get_accumulator require 2 or more point additions. Cost is the same as point_table.get_accumulator if 1 or 0 point additions are required)
Handle skew factors.
We represent scalar multipliers via Non Adjacent Form values (NAF). In a NAF, each bit value is either -1 or +1. We use this representation to avoid having to conditionally add points (i.e. every bit we iterate over will result in either a point addition or subtraction, instead of conditionally adding a point into an accumulator, we conditionally negate the point's y-coordinate and always add it into the accumulator)
However! The problem here is that we can only represent odd integers with a NAF. For even integers we add +1 to the integer and set that multiplier's skew value to true.
We record a scalar multiplier's skew value at the end of their NAF values (naf_entries[point_index][num_rounds])
If the skew is true, we must subtract the original point from the accumulator.
Definition at line 218 of file biggroup_bn254.hpp.
|
static |
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::bn254_endo_batch_mul_with_generator | ( | const std::vector< element< Builder_, Fq, Fr, NativeGroup > > & | big_points, |
| const std::vector< Fr > & | big_scalars, | ||
| const std::vector< element< Builder_, Fq, Fr, NativeGroup > > & | small_points, | ||
| const std::vector< Fr > & | small_scalars, | ||
| const Fr & | generator_scalar, | ||
| const size_t | max_num_small_bits | ||
| ) |
Perform a multi-scalar multiplication over the BN254 curve
The inputs are:
big_scalars/big_points : 254-bit scalar multipliers (hardcoded to be 4 at the moment) small_scalars/small_points : 128-bit scalar multipliers generator_scalar : a 254-bit scalar multiplier over the bn254 generator point
Definition at line 36 of file biggroup_bn254.hpp.
|
static |
We compute the following terms:
lambda = acc.lambda_prev * (acc.x1_prev - acc.x) - acc.y1_prev - p1.y / acc.x - p1.x x3 = lambda * lambda - acc.x - p1.x
Requires only 2 non-native field reductions
Definition at line 329 of file biggroup_impl.hpp.
|
static |
End an addition chain. Produces a full output group element with a y-coordinate
Definition at line 373 of file biggroup_impl.hpp.
|
static |
We can chain repeated point additions together, where we only require 2 non-native field multiplications per point addition, instead of 3
Evaluate a chain addition!
When adding a set of points P_1 + ... + P_N, we do not need to compute the y-coordinate of intermediate addition terms.
i.e. we substitute acc.y with acc.y = acc.lambda_prev * (acc.x1_prev - acc.x) - acc.y1_prev
lambda_prev, x1_prev, y1_prev are the lambda, x1, y1 terms from the previous addition operation.
chain_add requires 1 less non-native field reduction than a regular add operation. begin a chain of additions input points p1 p2 output accumulator = x3_prev (output x coordinate), x1_prev, y1_prev (p1), lambda_prev (y2 - y1) / (x2 - x1)
Definition at line 312 of file biggroup_impl.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::checked_unconditional_add | ( | const element< Builder_, Fq, Fr, NativeGroup > & | other | ) | const |
Definition at line 217 of file biggroup_impl.hpp.
| std::array< element< C, Fq, Fr, G >, 2 > bb::stdlib::element_default::element< C, Fq, Fr, G >::checked_unconditional_add_sub | ( | const element< Builder_, Fq, Fr, NativeGroup > & | other | ) | const |
Compute (*this) + other AND (*this) - other as a size-2 array.
We require this operation when computing biggroup lookup tables for multi-scalar-multiplication. This combined method reduces the number of field additions, field subtractions required (as well as 1 less assert_is_not_equal check)
| C | |
| Fq | |
| Fr | |
| G |
| other |
Definition at line 254 of file biggroup_impl.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::checked_unconditional_subtract | ( | const element< Builder_, Fq, Fr, NativeGroup > & | other | ) | const |
Definition at line 227 of file biggroup_impl.hpp.
|
static |
Definition at line 479 of file biggroup_nafs.hpp.
|
staticprivate |
compute_offset_generators! Let's explain what an offset generator is...
We evaluate biggroup group operations using INCOMPLETE addition formulae for short weierstrass curves:
L = y - y / x - x 2 1 2 1
2 x = L - x - x 3 2 1
y = L (x - x ) - y 3 1 3 1
These formuale do not work for the edge case where x2 == x1
Instead of handling the edge case (which is expensive!) we instead FORBID it from happening by requiring x2 != x1 (other.x.assert_is_not_equal(x) will be present in all group operation methods)
This means it is essential we ensure an honest prover will NEVER run into this edge case, or our circuit will lack completeness!
To ensure an honest prover will not fall foul of this edge case when performing a SCALAR MULTIPLICATION, we init the accumulator with an offset_generator point. This point is a generator point that is not equal to the regular generator point for this curve.
When adding points into the accumulator, the probability that an honest prover will find a collision is now ~ 1 in 2^128
We init accumulator = generator and then perform an n-bit scalar mul. The output accumulator will contain a term 2^{n-1} * generator that we need to subtract off.
offset_generators.first = generator (the initial generator point) offset_generators.second = 2^{n-1} * generator (the final generator point we need to subtract off from our accumulator)
Definition at line 742 of file biggroup_impl.hpp.
|
static |
Split a secp256k1 Fr element into two 129 bit scalars klo, khi, where scalar = klo + \lambda * khi mod n where \lambda is the cube root of unity mod n, and n is the secp256k1 Fr modulus
We return the wnaf representation of the two 129-bit scalars
The wnaf representation includes positive_skew and negative_skew components, because for both klo, khi EITHER k < 2^{129} OR -k mod n < 2^{129}. If we have to negate the short scalar, the wnaf skew component flips sign.
Outline of algorithm:
We will use our wnaf elements to index a ROM table. ROM index values act like regular array indices, i.e. start at 0, increase by 1 per index. We need the wnaf format to follow the same structure.
The mapping from wnaf value to lookup table point is as follows (example is 4-bit WNAF):
| wnaf witness value | wnaf real value | point representation |
|---|---|---|
| 0 | -15 | -15.[P] |
| 1 | -13 | -13.[P] |
| 2 | -11 | -11.[P] |
| 3 | -9 | -9.[P] |
| 4 | -7 | -7.[P] |
| 5 | -5 | -5.[P] |
| 6 | -3 | -3.[P] |
| 7 | -1 | -1.[P] |
| 8 | 1 | 1.[P] |
| 9 | 3 | 3.[P] |
| 10 | 5 | 5.[P] |
| 11 | 7 | 7.[P] |
| 12 | 9 | 9.[P] |
| 13 | 11 | 11.[P] |
| 14 | 13 | 13.[P] |
| 15 | 15 | 15.[P] |
| -----------------— | --------------— | -------------------— |
The transformation between the wnaf witness value w and the wnaf real value v is, for an s-bit window:
s
v = 2.w - (2 - 1)
To reconstruct the 129-bit scalar multiplier x from wnaf values w (starting with most significant slice):
m
___
\ / s \ s.(m - i - 1)
x = positive_skew - negative_skew + | | 2.w - (2 - 1) | . 2
/___ \ i /
i=0
N.B. m = number of rounds = (129 + s - 1) / s
We can split the RHS into positive and negative components that are strictly positive:
m
___
\ / \ s.(m - i - 1)
x_pos = positive_skew + | |2.w | . 2
/___ \ i/
i=0
m
___
\ / s \ s.(m - i - 1)
x_neg = negative_skew + | |(2 - 1)| . 2
/___ \ /
i=0
By independently constructing x_pos, x_neg, we ensure we never underflow the native circuit modulus
To reconstruct our wnaf components into a scalar, we perform the following (for each 129-bit slice klo, khi):
1. Compute the wnaf entries and range constrain each entry to be < 2^s 2. Construct `x_pos` 3. Construct `x_neg` 4. Cast `x_pos, x_neg` into two Fr elements and compute `Fr reconstructed = Fr(x_pos) - Fr(x_neg)`
This ensures that the only negation in performed in the Fr representation, removing the risk of underflow errors
Once klo, khi have been reconstructed as Fr elements, we validate the following:
1. `scalar == Fr(klo) - Fr(khi) * Fr(\lambda)
Finally, we return the wnaf representations of klo, khi including the skew
The staggered offset describes the number of bits we want to remove from the input scalar before computing our wnaf slices. This is to enable us to make repeated calls to the montgomery ladder algo when computing a multi-scalar multiplication e.g. Consider an example with 2 points (A, B), using a 2-bit WNAF The typical approach would be to perfomr a double-and-add algorithm, adding points into an accumulator ACC:
ACC = ACC.dbl() ACC = ACC.dbl() ACC = ACC.add(A) ACC = ACC.add(B)
However, if the A and B WNAFs are offset by 1 bit each, we can perform the following:
ACC = ACC.dbl() ACC = ACC.add(A) ACC = ACC.dbl() ACC = ACC.add(B)
which we can reduce to:
ACC = ACC.montgomery_ladder(A) ACC = ACC.montgomery_ladder(B)
This is more efficient than the non-staggered approach as we save 1 non-native field multiplication when we replace a DBL, ADD subroutine with a call to the montgomery ladder
Compute WNAF of a single 129-bit scalar
| k | Scalar |
| stagger | The number of bits that are used in "staggering" |
| is_negative | If it should be subtracted |
| is_lo | True if it's the low scalar |
Compute the stagger-related part of WNAF and the final skew
| fragment_u64 | Stagger-masked lower bits of the skalar |
| stagger | The number of staggering bits |
| is_negative | If the initial scalar is supposed to be subtracted |
| wnaf_skew | The skew of the stagger-right-shifted part of the skalar |
Compute wnaf values, convert them into witness field elements and range constrain them
Definition at line 103 of file biggroup_nafs.hpp.
|
staticprivate |
Compute an offset generator for use in biggroup tables.
Sometimes the points from which we construct the tables are going to be dependent in such a way that combining them for constructing the table is not possible without handling the edgecases such as the point at infinity and doubling. To avoid handling those we add multiples of this offset generator to the points.
| num_rounds |
Definition at line 25 of file biggroup_edgecase_handling.hpp.
|
static |
| std::vector< field_t< C > > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::compute_wnaf | ( | const Fr & | scalar | ) |
Definition at line 364 of file biggroup_nafs.hpp.
|
inline |
Definition at line 214 of file biggroup.hpp.
|
inlinestatic |
Definition at line 52 of file biggroup.hpp.
|
inline |
Creates fixed witnesses from a constant element.
Definition at line 137 of file biggroup.hpp.
|
inlinestaticprivate |
Creates a pair of 5-bit lookup tables, the former corresponding to 5 input points, the latter corresponding to the endomorphism equivalent of the 5 input points (e.g. x -> \beta * x, y -> -y)
Definition at line 583 of file biggroup.hpp.
|
inlinestaticprivate |
Definition at line 457 of file biggroup.hpp.
|
inlinestaticprivate |
Creates a pair of 4-bit lookup tables, the former corresponding to 4 input points, the latter corresponding to the endomorphism equivalent of the 4 input points (e.g. x -> \beta * x, y -> -y)
Definition at line 560 of file biggroup.hpp.
|
staticprivate |
| std::array< twin_rom_table< C >, 5 > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::create_group_element_rom_tables | ( | const std::array< element< Builder_, Fq, Fr, NativeGroup >, num_elements > & | rom_data, |
| std::array< uint256_t, 8 > & | limb_max | ||
| ) |
Constructs a ROM table to look up linear combinations of group elements.
| C | |
| Fq | |
| Fr | |
| G | |
| num_elements | |
| typename |
| rom_data | the ROM table we are writing into |
| limb_max | the maximum size of each limb in the ROM table. |
When reading a group element out of the ROM table, we must know the maximum value of each coordinate's limbs. We take this value to be the maximum of the maximum values of the input limbs into the table!
Definition at line 33 of file biggroup_tables.hpp.
Definition at line 274 of file biggroup_impl.hpp.
|
inline |
Fix a witness. The value of the witness is constrained with a selector
Definition at line 148 of file biggroup.hpp.
|
inlinestatic |
Definition at line 95 of file biggroup.hpp.
|
inline |
Definition at line 344 of file biggroup.hpp.
|
inline |
Definition at line 355 of file biggroup.hpp.
|
inline |
Definition at line 383 of file biggroup.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::get_standard_form | ( | ) | const |
Enforce x and y coordinates of a point to be (0,0) in the case of point at infinity.
We need to have a standard witness in Noir and the point at infinity can have non-zero random coefficients when we get it as output from our optimized algorithms. This function returns a (0,0) point, if it is a point at infinity
Definition at line 147 of file biggroup_impl.hpp.
|
inline |
Definition at line 276 of file biggroup.hpp.
|
static |
Replace all pairs (∞, scalar) by the pair (one, 0) where one is a fixed generator of the curve.
This is a step in enabling our our multiscalar multiplication algorithms to hande points at infinity.
Definition at line 81 of file biggroup_edgecase_handling.hpp.
|
inline |
Definition at line 372 of file biggroup.hpp.
|
static |
Given two lists of points that need to be multiplied by scalars, create a new list of length +1 with original points masked, but the same scalar product sum.
Add +1G, +2G, +4G etc to the original points and adds a new point 2ⁿ⋅G and scalar x to the lists. By doubling the point every time, we ensure that no +-1 combination of 6 sequential elements run into edgecases, unless the points are deliberately constructed to trigger it.
Definition at line 41 of file biggroup_edgecase_handling.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::montgomery_ladder | ( | const chain_add_accumulator & | to_add | ) |
Implementation of montgomery_ladder using chain_add_accumulator.
If the input to montgomery_ladder is the output of a chain of additions, we can avoid computing the y-coordinate of the input to_add, which saves us a non-native field reduction.
We substitute to_add.y with lambda_prev * (to_add.x1_prev - to_add.x) - to_add.y1_prev
Here, x1_prev, y1_prev, lambda_prev are the values of x1, y1, lambda for the addition operation that PRODUCED to_add
The reason why this saves us gates, is because the montgomery ladder does not multiply to_add.y by any values i.e. to_add.y is only used in addition operations
This allows us to substitute to_add.y with the above relation without requiring additional field reductions
e.g. the term (lambda * (x3 - x1) + to_add.y) remains "quadratic" if we replace to_add.y with the above quadratic relation
Definition at line 462 of file biggroup_impl.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::montgomery_ladder | ( | const element< Builder_, Fq, Fr, NativeGroup > & | other | ) | const |
Compute one round of a Montgomery ladder: i.e. compute 2 * (*this) + other Compute D = A + B + A, where A = this and B = other
We can skip computing the y-coordinate of C = A + B:
To compute D = A + C, A=(x_1,y_1), we need the gradient of our two coordinates, specifically:
y_3 - y_1 lambda_1 * (x_1 - x_3) - 2 * y_1 2 * y_1
lambda_2 = __________ = ________________________________ = -\lambda_1 - _________ x_3 - x_1 x_3 - x_1 x_3 - x_1
We don't need y_3 to compute this. We can then compute D.x and D.y as usual:
D.x = lambda_2 * lambda_2 - (C.x + A.x) D.y = lambda_2 * (A.x - D.x) - A.y
Requires 5 non-native field reductions. Doubling and adding would require 6 Compute D = A + B + A, where A = this and B = other
We can skip computing the y-coordinate of C = A + B:
To compute D = A + C, A=(x_1,y_1), we need the gradient of our two coordinates, specifically:
y_3 - y_1 lambda_1 * (x_1 - x_3) - 2 * y_1 2 * y_1
lambda_2 = __________ = ________________________________ = -\lambda_1 - _________ x_3 - x_1 x_3 - x_1 x_3 - x_1
We don't need y_3 to compute this. We can then compute D.x and D.y as usual:
D.x = lambda_2 * lambda_2 - (C.x + A.x) D.y = lambda_2 * (A.x - D.x) - A.y
Definition at line 426 of file biggroup_impl.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::multiple_montgomery_ladder | ( | const std::vector< chain_add_accumulator > & | add | ) | const |
Perform repeated iterations of the montgomery ladder algorithm.
For points P, Q, montgomery ladder computes R = (P + Q) + P i.e. it's "double-and-add" without explicit doublings.
This method can apply repeated iterations of the montgomery ladder. Each iteration reduces the number of field multiplications by 1, at the cost of more additions. (i.e. we don't compute intermediate y-coordinates).
The number of additions scales with the size of the input vector. The optimal input size appears to be 4.
| C | |
| Fq | |
| Fr | |
| G |
| add |
Definition at line 599 of file biggroup_impl.hpp.
|
inline |
Definition at line 221 of file biggroup.hpp.
|
inlinestatic |
Definition at line 158 of file biggroup.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::operator* | ( | const Fr & | scalar | ) | const |
Implements scalar multiplication operator.
Definition at line 846 of file biggroup_impl.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::operator+ | ( | const element< Builder_, Fq, Fr, NativeGroup > & | other | ) | const |
Definition at line 78 of file biggroup_impl.hpp.
|
inline |
Definition at line 200 of file biggroup.hpp.
|
inline |
Definition at line 194 of file biggroup.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::operator- | ( | const element< Builder_, Fq, Fr, NativeGroup > & | other | ) | const |
Definition at line 159 of file biggroup_impl.hpp.
|
inline |
Definition at line 205 of file biggroup.hpp.
| element< C, Fq, Fr, G > & bb::stdlib::element_default::element< C, Fq, Fr, G >::operator= | ( | const element< Builder_, Fq, Fr, NativeGroup > & | other | ) |
Definition at line 54 of file biggroup_impl.hpp.
|
noexcept |
Definition at line 66 of file biggroup_impl.hpp.
|
inlinestatic |
Definition at line 167 of file biggroup.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::quadruple_and_add | ( | const std::vector< element< Builder_, Fq, Fr, NativeGroup > > & | to_add | ) | const |
Compute 4.P + to_add[0] + ... + to_add[to_add.size() - 1].
Used in wnaf_batch_mul method. Combining operations requires fewer bigfield reductions.
Method computes R[i] = (2P + A[0]) + (2P + A[1]) + A[2] + ... + A[n-1]
| C | |
| Fq | |
| Fr | |
| G |
| to_add |
Definition at line 505 of file biggroup_impl.hpp.
|
staticprivate |
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::read_group_element_rom_tables | ( | const std::array< twin_rom_table< C >, 5 > & | tables, |
| const field_t< C > & | index, | ||
| const std::array< uint256_t, 8 > & | limb_max | ||
| ) |
Definition at line 74 of file biggroup_tables.hpp.
|
inlinestatic |
Reconstruct a biggroup element from limbs of its coordinates (generally stored in the public inputs)
| limbs |
Definition at line 86 of file biggroup.hpp.
|
inline |
Definition at line 230 of file biggroup.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::scalar_mul | ( | const Fr & | scalar, |
| const size_t | max_num_bits = 0 |
||
| ) | const |
Implements scalar multiplication that supports short scalars. For multiple scalar multiplication use one of the batch_mul methods to save gates.
| scalar | A field element. If max_num_bits>0, the length of the scalar must not exceed max_num_bits. |
| max_num_bits | Even integer < 254. Default value 0 corresponds to scalar multiplication by scalars of unspecified length. |
Let's say we have some curve E defined over a field Fq. The order of E is p, which is prime.
Now lets say we are constructing a SNARK circuit over another curve E2, whose order is r.
All of our addition / multiplication / custom gates are going to be evaluating low degree multivariate polynomials modulo r.
E.g. our addition/mul gate (for wires a, b, c and selectors q_m, q_l, q_r, q_o, q_c) is:
q_m * a * b + q_l * a + q_r * b + q_o * c + q_c = 0 mod r
We want to construct a circuit that evaluates scalar multiplications of curve E. Where q > r and p > r.
i.e. we need to perform arithmetic in one prime field, using prime field arithmetic in a completely different prime field.
To do this, we need to emulate a binary (or in our case quaternary) number system in Fr, so that we can use the binary/quaternary basis to emulate arithmetic in Fq. Which is very messy. See bigfield.hpp for the specifics.
Definition at line 861 of file biggroup_impl.hpp.
|
static |
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::secp256k1_ecdsa_mul | ( | const element< Builder_, Fq, Fr, NativeGroup > & | pubkey, |
| const Fr & | u1, | ||
| const Fr & | u2 | ||
| ) |
Compute `out = u1.[1] + u2.[pubkey]
Split scalar u1 into 129-bit short scalars u1_lo, u1_hi, where u1 = u1_lo * \lambda u1_hi (\lambda is the cube root of unity modulo the secp256k1 group order)
Covert u1_lo and u1_hi into an 8-bit sliding window NAF. Our base point is the G1 generator. We have a precomputed size-256 plookup table of the generator point, multiplied by all possible wNAF values
We also split scalar u2 using the secp256k1 endomorphism. Convert short scalars into 4-bit sliding window NAFs. We will store the lookup table of all possible base-point wNAF states in a ROM table (it's variable-base scalar multiplication in a SNARK with a lookup table! ho ho ho)
The wNAFs u1_lo_wnaf, u1_hi_wnaf, u2_lo_wnaf, u2_hi_wnaf are each offset by 1 bit relative to each other. i.e. we right-shift u2_hi by 1 bit before computing its wNAF we right-shift u1_lo by 2 bits we right-shift u1_hi by 3 bits we do not shift u2_lo
We do this to ensure that we are never adding more than 1 point into our accumulator when performing our double-and-add scalar multiplication. It is more efficient to use the montgomery ladder algorithm, compared against doubling an accumulator and adding points into it.
The bits removed by the right-shifts are stored in the wnaf's respective least_significant_wnaf_fragment member variable
Construct our 4-bit variable-base and 8-bit fixed base lookup tables
main double-and-add loop
Acc = Acc + Acc Acc = Acc + Acc Acc = Acc + u2_hi_wnaf.[endoP2] + Acc Acc = Acc + u2_lo_wnaf.[P2] + Acc Acc = Acc + u1_hi_wnaf.[endoP1] + Acc Acc = Acc + u1_lo_wnaf.[P1] + Acc Acc = Acc + u2_hi_wnaf.[endoP2] + Acc Acc = Acc + u2_lo_wnaf.[P2] + Acc
We add u2 points into the accumulator twice per 'round' as we only have a 4-bit lookup table (vs the 8-bit table for u1)
At the conclusion of this loop, we will need to add a final contribution from u2_hi, u1_lo, u1_hi. This is because we offset our wNAFs to take advantage of the montgomery ladder, but this means we have doubled our accumulator AFTER adding our final wnaf contributions from u2_hi, u1_lo and u1_hi
Add the final contributions from u2_hi, u1_lo, u1_hi
Handle wNAF skew.
scalars represented via the non-adjacent form can only be odd. If our scalars are even, we must either add or subtract the relevant base point into the accumulator
Definition at line 19 of file biggroup_secp256k1.hpp.
|
inline |
Set the free witness flag for the element's tags.
Definition at line 401 of file biggroup.hpp.
|
inline |
Definition at line 376 of file biggroup.hpp.
|
inline |
Definition at line 373 of file biggroup.hpp.
|
inline |
Set the witness indices for the x and y coordinates to public.
Definition at line 72 of file biggroup.hpp.
|
inline |
Definition at line 181 of file biggroup.hpp.
|
inline |
Unset the free witness flag for the element's tags.
Definition at line 391 of file biggroup.hpp.
|
inline |
Definition at line 117 of file biggroup.hpp.
| element< C, Fq, Fr, G > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::wnaf_batch_mul | ( | const std::vector< element< Builder_, Fq, Fr, NativeGroup > > & | _points, |
| const std::vector< Fr > & | _scalars | ||
| ) |
Multiscalar multiplication that utilizes 4-bit wNAF lookup tables.
This is more efficient than points-as-linear-combinations lookup tables, if the number of points is 3 or fewer.
Definition at line 21 of file biggroup_batch_mul.hpp.
|
static |
|
private |
Definition at line 412 of file biggroup.hpp.
|
staticconstexpr |
Definition at line 32 of file biggroup.hpp.
| Fq bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::x |
Definition at line 408 of file biggroup.hpp.
| Fq bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::y |
Definition at line 409 of file biggroup.hpp.
1.9.8