- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
#include <biggroup.hpp>
Classes | |
| struct | batch_lookup_table_plookup |
| struct | chain_add_accumulator |
| struct | eight_bit_fixed_base_table |
| Eight-bit fixed base table for scalar multiplication. More... | |
| struct | four_bit_table_plookup |
| Four-bit variable-base table for scalar multiplication. More... | |
| struct | lookup_table_plookup |
| Generic lookup table that uses ROM tables internally to access group elements. More... | |
| 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 Fq &x, const Fq &y, const bool_ct &is_infinity) | |
| element (const element &other) | |
| element (element &&other) noexcept | |
| ~element ()=default | |
| uint32_t | set_public () const |
| Set the witness indices for the x and y coordinates to public. | |
| void | validate_on_curve (std::string const &msg="biggroup::validate_on_curve") const |
| Check that the point is on the curve. | |
| void | convert_constant_to_fixed_witness (Builder *builder) |
| Creates fixed witnesses from a constant element. | |
| void | fix_witness () |
| Fix a witness. The value of the witness is constrained with a selector. | |
| element & | operator= (const element &other) |
| element & | operator= (element &&other) noexcept |
| byte_array< Builder > | to_byte_array () const |
| Serialize the element to a byte array in form: (yhi || ylo || xhi || xlo). | |
| 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 &other) const |
| Compute (*this) + other AND (*this) - other as a size-2 array. | |
| element | operator* (const Fr &scalar) const |
| element | conditional_negate (const bool_ct &predicate) const |
| element | conditional_select (const element &other, const bool_ct &predicate) const |
Selects this if predicate is false, other if predicate is true. | |
| void | incomplete_assert_equal (const element &other, const std::string msg="biggroup::incomplete_assert_equal") const |
| Asserts that two group elements are equal (i.e., x, y coordinates and infinity flag are all equal). | |
| 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 &to_add) |
| 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, const bool &add_to_used_witnesses=false) |
| 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 wnaf_size> | |
| std::vector< field_t< C > > | convert_wnaf_values_to_witnesses (C *builder, const uint64_t *wnaf_values, bool is_negative, size_t rounds, const bool range_constrain_wnaf) |
| template<size_t num_bits, size_t wnaf_size, size_t lo_stagger, size_t hi_stagger> | |
| std::pair< Fr, typename element< C, Fq, Fr, G >::secp256k1_wnaf > | compute_secp256k1_single_wnaf (C *builder, const secp256k1::fr &scalar, size_t stagger, bool is_negative, const bool range_constrain_wnaf, bool is_lo) |
| 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 >, Fq::NUM_LIMBS+1 > | create_group_element_rom_tables (const std::array< element, num_elements > &rom_data, std::array< uint256_t, Fq::NUM_LIMBS *2 > &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 >, Fq::NUM_LIMBS+1 > &tables, const field_t< C > &index, const std::array< uint256_t, Fq::NUM_LIMBS *2 > &limb_max) |
Static Public Member Functions | |
| static std::array< fr, PUBLIC_INPUTS_SIZE > | construct_dummy () |
| Construct a dummy element (the group generator) and return its limbs as fr constants. | |
| 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) |
| Create a biggroup witness from a native group element, allocating new witnesses as necessary. | |
| static element | one (Builder *ctx) |
| Creates a constant group generator. | |
| 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, const bool range_constrain_wnaf=true) |
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_bits, size_t wnaf_size, size_t lo_stagger, size_t hi_stagger> | |
| static std::pair< Fr, secp256k1_wnaf > | compute_secp256k1_single_wnaf (Builder *builder, const secp256k1::fr &scalar, size_t stagger, bool is_negative, const bool range_constrain_wnaf=true, bool is_lo=false) |
| Compute the wNAF representation (in circuit) of a scalar for secp256k1. | |
| template<size_t wnaf_size> | |
| static std::pair< uint64_t, bool > | get_staggered_wnaf_fragment_value (const uint64_t fragment_u64, const uint64_t stagger, bool is_negative, bool wnaf_skew) |
| Compute the stagger-related part of wNAF and the final skew. | |
| template<size_t wnaf_size> | |
| static std::vector< field_t< Builder > > | convert_wnaf_values_to_witnesses (Builder *builder, const uint64_t *wnaf_values, bool is_negative, size_t rounds, const bool range_constrain_wnaf=true) |
| Convert wNAF values to witness values. | |
| template<size_t wnaf_size> | |
| static Fr | reconstruct_bigfield_from_wnaf (Builder *builder, const std::vector< field_t< Builder > > &wnaf, const bool_ct &positive_skew, const bool_ct &negative_skew, const field_t< Builder > &stagger_fragment, const size_t stagger, const size_t rounds) |
| Reconstruct a scalar from its wNAF representation in circuit. | |
| template<size_t num_elements> | |
| static std::array< twin_rom_table< Builder >, Fq::NUM_LIMBS+1 > | create_group_element_rom_tables (const std::array< element, num_elements > &rom_data, std::array< uint256_t, Fq::NUM_LIMBS *2 > &limb_max) |
| template<size_t num_elements> | |
| static element | read_group_element_rom_tables (const std::array< twin_rom_table< Builder >, Fq::NUM_LIMBS+1 > &tables, const field_t< Builder > &index, const std::array< uint256_t, Fq::NUM_LIMBS *2 > &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) |
| Create a endo pair four bit table for the given group element. | |
| static std::pair< quad_lookup_table, quad_lookup_table > | create_endo_pair_quad_lookup_table (const std::array< element, 4 > &inputs) |
Private Attributes | |
| bool_ct | _is_infinity |
Friends | |
| class | element_test_accessor |
Definition at line 25 of file biggroup.hpp.
| using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::BaseField = Fq |
Definition at line 30 of file biggroup.hpp.
|
private |
Definition at line 989 of file biggroup.hpp.
| using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::biggroup_tag = element |
Definition at line 29 of file biggroup.hpp.
| using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::bool_ct = stdlib::bool_t<Builder> |
Definition at line 28 of file biggroup.hpp.
| using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::Builder = Builder_ |
Definition at line 27 of file biggroup.hpp.
|
private |
Definition at line 679 of file biggroup.hpp.
|
private |
Definition at line 677 of file biggroup.hpp.
|
private |
Definition at line 675 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 Fq & | x, |
| const Fq & | y, | ||
| const bool_ct & | is_infinity | ||
| ) |
Definition at line 40 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 47 of file biggroup_impl.hpp.
|
noexcept |
Definition at line 54 of file biggroup_impl.hpp.
|
default |
|
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 806 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 327 of file biggroup_impl.hpp.
|
static |
End an addition chain. Produces a full output group element with a y-coordinate
Definition at line 376 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 310 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 213 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 250 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 223 of file biggroup_impl.hpp.
|
static |
Definition at line 520 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 777 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
Definition at line 325 of file biggroup_nafs.hpp.
|
staticprivate |
Compute the wNAF representation (in circuit) of a scalar for secp256k1.
| builder | |
| scalar | The scalar to be represented in wNAF, should be ≤ 129 bits |
| stagger | The stagger value (in terms of number of bits) |
| is_negative | Whether the scalar is negative |
| is_lo | Whether this is the low part of a split scalar |
For a scalar k > (r / 2), we compute the wNAF representation of k' = r - k. We then have k = -k' mod r, and we can perform scalar multiplication using -k'. This case is handled by setting is_negative = true.
| std::pair< Fr, typename element< C, Fq, Fr, G >::secp256k1_wnaf > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::compute_secp256k1_single_wnaf | ( | C * | builder, |
| const secp256k1::fr & | scalar, | ||
| size_t | stagger, | ||
| bool | is_negative, | ||
| const bool | range_constrain_wnaf, | ||
| bool | is_lo | ||
| ) |
Definition at line 164 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 405 of file biggroup_nafs.hpp.
|
inline |
Definition at line 250 of file biggroup.hpp.
|
inline |
Selects this if predicate is false, other if predicate is true.
| other | |
| predicate |
Definition at line 264 of file biggroup.hpp.
|
inlinestatic |
Construct a dummy element (the group generator) and return its limbs as fr constants.
Definition at line 61 of file biggroup.hpp.
|
inline |
Creates fixed witnesses from a constant element.
Definition at line 165 of file biggroup.hpp.
|
staticprivate |
Convert wNAF values to witness values.
| builder | |
| wnaf_values | |
| is_negative | |
| rounds |
For 4-bit window, each wNAF value is in the range [-15, 15]. We convert these to the range [0, 30] by adding 15 if is_negative = false and by subtracting from 15 if is_negative = true. This ensures that all values are non-negative, which is required for the ROM table lookup.
| std::vector< field_t< C > > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::convert_wnaf_values_to_witnesses | ( | C * | builder, |
| const uint64_t * | wnaf_values, | ||
| bool | is_negative, | ||
| size_t | rounds, | ||
| const bool | range_constrain_wnaf | ||
| ) |
Definition at line 71 of file biggroup_nafs.hpp.
|
staticprivate |
Create a endo pair four bit table for the given group element.
| C | |
| Fq | |
| Fr | |
| G |
| input |
| Index | P = (x, y) | Q = (β.x, y) |
|---|---|---|
| 0 | -15.P | Q_0 |
| 1 | -13.P | Q_1 |
| 2 | -11.P | Q_2 |
| 3 | -9.P | Q_3 |
| 4 | -7.P | Q_4 |
| 5 | -5.P | Q_5 |
| 6 | -3.P | Q_6 |
| 7 | -1.P | Q_7 |
| 8 | 1.P | Q_8 |
| 9 | 3.P | Q_9 |
| 10 | 5.P | Q_10 |
| 11 | 7.P | Q_11 |
| 12 | 9.P | Q_12 |
| 13 | 11.P | Q_13 |
| 14 | 13.P | Q_14 |
| 15 | 15.P | Q_15 |
Definition at line 376 of file biggroup_tables.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 685 of file biggroup.hpp.
|
staticprivate |
| std::array< twin_rom_table< C >, Fq::NUM_LIMBS+1 > 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, Fq::NUM_LIMBS *2 > & | 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 270 of file biggroup_impl.hpp.
|
inline |
Fix a witness. The value of the witness is constrained with a selector.
Definition at line 176 of file biggroup.hpp.
|
inlinestatic |
Create a biggroup witness from a native group element, allocating new witnesses as necessary.
| ctx | |
| input |
Definition at line 113 of file biggroup.hpp.
|
inline |
Definition at line 427 of file biggroup.hpp.
|
inline |
Definition at line 438 of file biggroup.hpp.
|
inline |
Definition at line 472 of file biggroup.hpp.
|
staticprivate |
Compute the stagger-related part of wNAF and the final skew.
| fragment_u64 | Stagger-masked lower bits of the scalar |
| 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 scalar |
Definition at line 16 of file biggroup_nafs.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 148 of file biggroup_impl.hpp.
|
inline |
Definition at line 359 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 |
Asserts that two group elements are equal (i.e., x, y coordinates and infinity flag are all equal).
| other | |
| msg |
Note that checking the coordinates as well as the infinity flag opens up the possibility of honest prover unable to satisfy constraints if both points are at infinity but have different x, y. This is not a problem in practice as we should never have multiple representations of the point at infinity in a circuit.
Definition at line 296 of file biggroup.hpp.
|
inline |
Definition at line 455 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 465 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 429 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 623 of file biggroup_impl.hpp.
|
inline |
Definition at line 304 of file biggroup.hpp.
|
inlinestatic |
Creates a constant group generator.
Definition at line 189 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 880 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 85 of file biggroup_impl.hpp.
|
inline |
Definition at line 236 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 >::operator- | ( | const element< Builder_, Fq, Fr, NativeGroup > & | other | ) | const |
Definition at line 160 of file biggroup_impl.hpp.
|
inline |
Definition at line 241 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 61 of file biggroup_impl.hpp.
|
noexcept |
Definition at line 73 of file biggroup_impl.hpp.
|
inlinestatic |
Definition at line 198 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 511 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 >, Fq::NUM_LIMBS+1 > & | tables, |
| const field_t< C > & | index, | ||
| const std::array< uint256_t, Fq::NUM_LIMBS *2 > & | limb_max | ||
| ) |
Definition at line 74 of file biggroup_tables.hpp.
|
staticprivate |
Reconstruct a scalar from its wNAF representation in circuit.
| builder | |
| wnaf | The wNAF representation of the scalar |
| positive_skew | The skew to be applied if the scalar is non-negative |
| stagger_fragment | The stagger-related fragment of the scalar |
| stagger | The number of staggering bits |
| rounds | The number of rounds in the wNAF representation |
Definition at line 105 of file biggroup_nafs.hpp.
|
inlinestatic |
Reconstruct a biggroup element from limbs of its coordinates (generally stored in the public inputs)
| limbs |
Definition at line 96 of file biggroup.hpp.
|
inline |
Definition at line 313 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 895 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
We do NOT range constrain the wNAF entries, because we will use them to lookup in a ROM/regular table. The ROM/regular table lookup implicitly enforces the range constraint
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 490 of file biggroup.hpp.
|
inline |
Definition at line 465 of file biggroup.hpp.
|
inline |
Definition at line 456 of file biggroup.hpp.
|
inline |
Set the witness indices for the x and y coordinates to public.
Definition at line 82 of file biggroup.hpp.
|
inline |
Serialize the element to a byte array in form: (yhi || ylo || xhi || xlo).
Definition at line 217 of file biggroup.hpp.
|
inline |
Unset the free witness flag for the element's tags.
Definition at line 480 of file biggroup.hpp.
|
inline |
Check that the point is on the curve.
Definition at line 138 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 |
|
friend |
Definition at line 501 of file biggroup.hpp.
|
private |
Definition at line 504 of file biggroup.hpp.
|
staticconstexpr |
Definition at line 33 of file biggroup.hpp.
| Fq bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::x |
Definition at line 497 of file biggroup.hpp.
| Fq bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::y |
Definition at line 498 of file biggroup.hpp.
1.9.8