#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	field_ct = stdlib::field_t< Builder >

using	witness_ct = stdlib::witness_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, const bool assert_on_curve=true)

	element (const Fq &x, const Fq &y, const bool_ct &is_infinity, bool assert_on_curve=true)

	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.

bool	is_constant () const

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

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)

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

void	assert_coordinates_in_field (const std::string &msg="biggroup::assert_coordinates_in_field") const

element	dbl () const

element	multiple_montgomery_ladder (const std::vector< chain_add_accumulator > &to_add) const
	Perform repeated iterations of the montgomery ladder algorithm.

NativeGroup::affine_element	get_value () const

Builder *	get_context () const

Builder *	get_context (const element &other) const

const Fq &	x () const

const Fq &	y () 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

void	clear_round_provenance () 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 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 wnaf_size>
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)

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<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_ct &index, const std::array< uint256_t, Fq::NUM_LIMBS *2 > &limb_max)

Static Public Member Functions
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)
	Begin a chain of additions.

static chain_add_accumulator	chain_add (const element &p1, const chain_add_accumulator &accumulator)
	Evaluate a chain addition using incomplete addition formulae.

static element	chain_add_end (const chain_add_accumulator &accumulator)
	End an addition chain and compute the final y-coordinate.

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, const Fr &masking_scalar=Fr(1))
	Generic batch multiplication that works for all elliptic curve types.

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)
	Compute Non-Adjacent Form (NAF) representation of a 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)
	Compute endomorphism for a secp256k1 scalar, and then compute the wNAF representation of both halves.

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

Private Member Functions
std::array< element, 2 >	checked_unconditional_add_sub (const element &other) const
	Compute both add and subtract (a + b, a - b) results simultaneously.

Static Private Member Functions
static std::pair< std::vector< element >, std::vector< Fr > >	mask_points (const std::vector< element > &_points, const std::vector< Fr > &_scalars, const Fr &masking_scalar)
	Mask points for batch multiplication to handle edge cases.

static std::pair< std::vector< element >, std::vector< Fr > >	handle_points_at_infinity (const std::vector< element > &_points, const std::vector< Fr > &_scalars)
	Handle points at infinity in batch operations, replaces (∞, scalar) pairs by (G, 0)

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_ct >	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_ct > &wnaf, const bool_ct &positive_skew, const bool_ct &negative_skew, const field_ct &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_ct &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)

static element	process_strauss_msm_rounds (const std::vector< element > &points, const std::vector< Fr > &scalars, const size_t max_num_bits)

Private Attributes
Fq	_x

Fq	_y

bool_ct	_is_infinity

Friends
class	element_test_accessor

Detailed Description

template<class Builder_, class Fq, class Fr, class NativeGroup>
class bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >

Definition at line 26 of file biggroup.hpp.

Member Typedef Documentation

◆ BaseField

template<class Builder_ , class Fq , class Fr , class NativeGroup >

using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::BaseField = Fq

Definition at line 33 of file biggroup.hpp.

◆ batch_lookup_table

template<class Builder_ , class Fq , class Fr , class NativeGroup >

using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::batch_lookup_table = batch_lookup_table_plookup

private

Definition at line 936 of file biggroup.hpp.

◆ biggroup_tag

template<class Builder_ , class Fq , class Fr , class NativeGroup >

using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::biggroup_tag = element

Definition at line 32 of file biggroup.hpp.

◆ bool_ct

template<class Builder_ , class Fq , class Fr , class NativeGroup >

using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::bool_ct = stdlib::bool_t<Builder>

Definition at line 29 of file biggroup.hpp.

◆ Builder

template<class Builder_ , class Fq , class Fr , class NativeGroup >

using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::Builder = Builder_

Definition at line 28 of file biggroup.hpp.

◆ field_ct

template<class Builder_ , class Fq , class Fr , class NativeGroup >

using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::field_ct = stdlib::field_t<Builder>

Definition at line 30 of file biggroup.hpp.

◆ quad_lookup_table

template<class Builder_ , class Fq , class Fr , class NativeGroup >

using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::quad_lookup_table = lookup_table_plookup<4>

private

Definition at line 655 of file biggroup.hpp.

◆ triple_lookup_table

template<class Builder_ , class Fq , class Fr , class NativeGroup >

using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::triple_lookup_table = lookup_table_plookup<3>

private

Definition at line 653 of file biggroup.hpp.

◆ twin_lookup_table

template<class Builder_ , class Fq , class Fr , class NativeGroup >

using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::twin_lookup_table = lookup_table_plookup<2>

private

Definition at line 651 of file biggroup.hpp.

◆ witness_ct

template<class Builder_ , class Fq , class Fr , class NativeGroup >

using bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::witness_ct = stdlib::witness_t<Builder>

Definition at line 31 of file biggroup.hpp.

Constructor & Destructor Documentation

◆ element() [1/6]

template<typename C , class Fq , class Fr , class G >

bb::stdlib::element_default::element< C, Fq, Fr, G >::element ( )

Definition at line 20 of file biggroup_impl.hpp.

◆ element() [2/6]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::element ( const typename NativeGroup::affine_element< Builder_, Fq, Fr, NativeGroup > & input )

◆ element() [3/6]

template<typename C , class Fq , class Fr , class G >

bb::stdlib::element_default::element< C, Fq, Fr, G >::element	(	const Fq &	x,
		const Fq &	y,
		const bool	assert_on_curve = `true`
	)

Definition at line 34 of file biggroup_impl.hpp.

◆ element() [4/6]

template<typename C , class Fq , class Fr , class G >

bb::stdlib::element_default::element< C, Fq, Fr, G >::element	(	const Fq &	x,
		const Fq &	y,
		const bool_ct &	is_infinity,
		bool	assert_on_curve = `true`
	)

Definition at line 45 of file biggroup_impl.hpp.

◆ element() [5/6]

template<typename C , class Fq , class Fr , class G >

bb::stdlib::element_default::element< C, Fq, Fr, G >::element ( const element< Builder_, Fq, Fr, NativeGroup > & other )

Definition at line 56 of file biggroup_impl.hpp.

◆ element() [6/6]

template<typename C , class Fq , class Fr , class G >

bb::stdlib::element_default::element< C, Fq, Fr, G >::element ( element< Builder_, Fq, Fr, NativeGroup > && other )

noexcept

Definition at line 63 of file biggroup_impl.hpp.

◆ ~element()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::~element ( )

default

Member Function Documentation

◆ assert_coordinates_in_field()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

void bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::assert_coordinates_in_field ( const std::string & msg = "biggroup::assert_coordinates_in_field" ) const

inline

Definition at line 294 of file biggroup.hpp.

◆ batch_mul()

template<typename C , class Fq , class Fr , class G >

element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::batch_mul	(	const std::vector< element< Builder_, Fq, Fr, NativeGroup > > &	_points,
		const std::vector< Fr > &	_scalars,
		const size_t	max_num_bits = `0`,
		const bool	with_edgecases = `false`,
		const Fr &	masking_scalar = `Fr(1)`
	)

static

Generic batch multiplication that works for all elliptic curve types.

Template Parameters

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`.

Parameters

_points
_scalars
max_num_bits	The max of the bit lengths of the scalars.
with_edgecases	Use when points are linearly dependent. Randomises them.

Returns: element<C, Fq, Fr, G>

This is an implementation of the Strauss algorithm for multi-scalar-multiplication (MSM). It uses the Non-Adjacent Form (NAF) representation of scalars and ROM lookups to efficiently compute the MSM. The algorithm processes 4 bits of each scalar per iteration,

accumulating the results in an accumulator point. The first NAF entry (I, see below) is used to

Point NAF(scalar) G1 [+1, -1, -1, -1, +1, ...] G2 [+1, +1, -1, -1, +1, ...] G3 [-1, +1, +1, -1, +1, ...] ↑ ↑____________↑

I Iteration 1

select the initial point to add to the offset generator. Thereafter, we process 4 NAF entries per iteration. For one NAF entry, we lookup the corresponding points to add, and accumulate them using chain_add_accumulator. After processing 4 NAF entries, we perform a single multiple_montgomery_ladder call to update the accumulator. For example, in iteration 1 above, for the second NAF entry, the lookup output is: table(-1, +1, +1) = (-G1 + G2 + G3) This lookup output is accumulated with the lookup outputs from the other 3 NAF entries.

Definition at line 819 of file biggroup_impl.hpp.

◆ chain_add()

template<typename C , class Fq , class Fr , class G >

element< C, Fq, Fr, G >::chain_add_accumulator bb::stdlib::element_default::element< C, Fq, Fr, G >::chain_add	(	const element< Builder_, Fq, Fr, NativeGroup > &	p1,
		const chain_add_accumulator &	acc
	)

static

Evaluate a chain addition using incomplete addition formulae.

Parameters

p1	Point to add (x₁, y₁)
acc	Accumulator from previous addition

Returns: Updated accumulator with new x3_prev, and previous x1_prev, y1_prev, lambda_prev

When adding a set of points P₁ + ... + Pₙ, we can optimize by not computing the y-coordinate of intermediate addition terms. Instead, we substitute: acc.y = acc.lambda_prev * (acc.x1_prev - acc.x) - acc.y1_prev

The accumulator stores (lambda_prev, x1_prev, y1_prev, x3_prev) from the previous addition operation, allowing us to defer y-coordinate computation until the end.

chain_add requires 1 less non-native field reduction than a regular add operation.

Warning: : These functions use INCOMPLETE addition formulae and require x₁ ≠ x₂ for all inputs.

Definition at line 393 of file biggroup_impl.hpp.

◆ chain_add_end()

template<typename C , class Fq , class Fr , class G >

element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::chain_add_end ( const chain_add_accumulator & acc )

static

End an addition chain and compute the final y-coordinate.

Parameters

acc	The chain accumulator from the last addition

Returns: Complete point (x₃, y₃) with both coordinates

Definition at line 439 of file biggroup_impl.hpp.

◆ chain_add_start()

template<typename C , class Fq , class Fr , class G >

element< C, Fq, Fr, G >::chain_add_accumulator bb::stdlib::element_default::element< C, Fq, Fr, G >::chain_add_start	(	const element< Builder_, Fq, Fr, NativeGroup > &	p1,
		const element< Builder_, Fq, Fr, NativeGroup > &	p2
	)

static

Begin a chain of additions.

We can chain repeated point additions together, where we only require 2 non-native field multiplications per point addition, instead of 3 NOTE: These must remain public as they are used by nested structs like batch_lookup_table_plookup

Parameters

p1	First point (x₁, y₁)
p2	Second point (x₂, y₂)

Returns: Accumulator containing: x3_prev = λ² - x₁ - x₂, x1_prev = x₁, y1_prev = y₁, lambda_prev = (y₂ - y₁)/(x₂ - x₁)

Definition at line 355 of file biggroup_impl.hpp.

◆ checked_unconditional_add()

template<typename C , class Fq , class Fr , class G >

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 244 of file biggroup_impl.hpp.

◆ checked_unconditional_add_sub()

template<typename C , class Fq , class Fr , class G >

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

private

Compute both add and subtract (a + b, a - b) results simultaneously.

Compute (*this) + other AND (*this) - other as a size-2 array.

Only used internally for lookup table generation

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)

Template Parameters

C
Fq
Fr
G

Parameters

other

Returns: std::array<element<C, Fq, Fr, G>, 2>

Definition at line 280 of file biggroup_impl.hpp.

◆ checked_unconditional_subtract()

template<typename C , class Fq , class Fr , class G >

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 254 of file biggroup_impl.hpp.

◆ clear_round_provenance()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

void bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::clear_round_provenance ( ) const

inline

Definition at line 412 of file biggroup.hpp.

◆ compute_naf()

template<typename C , class Fq , class Fr , class G >

std::vector< bool_t< C > > bb::stdlib::element_default::element< C, Fq, Fr, G >::compute_naf	(	const Fr &	scalar,
		const size_t	max_num_bits = `0`
	)

static

Compute Non-Adjacent Form (NAF) representation of a scalar.

Only used internally in biggroup_nafs.hpp

Definition at line 412 of file biggroup_nafs.hpp.

◆ compute_offset_generators()

template<typename C , class Fq , class Fr , class G >

std::pair< element< C, Fq, Fr, G >, element< C, Fq, Fr, G > > bb::stdlib::element_default::element< C, Fq, Fr, G >::compute_offset_generators ( const size_t num_rounds )

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 689 of file biggroup_impl.hpp.

◆ compute_secp256k1_endo_wnaf()

template<typename C , class Fq , class Fr , class G >

template<size_t wnaf_size, size_t lo_stagger, size_t hi_stagger>

element< C, Fq, Fr, G >::secp256k1_wnaf_pair bb::stdlib::element_default::element< C, Fq, Fr, G >::compute_secp256k1_endo_wnaf	(	const Fr &	scalar,
		const bool	range_constrain_wnaf = `true`
	)

static

Compute endomorphism for a secp256k1 scalar, and then compute the wNAF representation of both halves.

Only used internally in biggroup_nafs.hpp and biggroup_secp256k1.hpp

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.dbl() + A ACC = ACC.dbl() + B

This is more efficient than the non-staggered approach as we save 1 non-native field multiplication when we combine the DBL and ADD operations

Definition at line 325 of file biggroup_nafs.hpp.

◆ compute_secp256k1_single_wnaf() [1/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<size_t num_bits, size_t wnaf_size, size_t lo_stagger, size_t hi_stagger>

static std::pair< Fr, secp256k1_wnaf > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::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`
	)

staticprivate

Compute the wNAF representation (in circuit) of a scalar for secp256k1.

Parameters

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

Returns: std::pair<Fr, secp256k1_wnaf>

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.

◆ compute_secp256k1_single_wnaf() [2/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

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 > 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.

◆ compute_table_offset_generator()

template<typename C , class Fq , class Fr , class G >

G::affine_element bb::stdlib::element_default::element< C, Fq, Fr, G >::compute_table_offset_generator ( )

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.

Parameters

num_rounds

Definition at line 26 of file biggroup_edgecase_handling.hpp.

◆ conditional_negate()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::conditional_negate ( const bool_ct & predicate ) const

inline

Definition at line 223 of file biggroup.hpp.

◆ conditional_select()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::conditional_select	(	const element< Builder_, Fq, Fr, NativeGroup > &	other,
		const bool_ct &	predicate
	)		const

inline

Selects this if predicate is false, other if predicate is true.

Parameters

other
predicate

Returns: element

Definition at line 237 of file biggroup.hpp.

◆ convert_constant_to_fixed_witness()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

void bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::convert_constant_to_fixed_witness ( Builder * builder )

inline

Creates fixed witnesses from a constant element.

Definition at line 152 of file biggroup.hpp.

◆ convert_wnaf_values_to_witnesses() [1/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<size_t wnaf_size>

static std::vector< field_ct > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::convert_wnaf_values_to_witnesses	(	Builder *	builder,
		const uint64_t *	wnaf_values,
		bool	is_negative,
		size_t	rounds,
		const bool	range_constrain_wnaf = `true`
	)

staticprivate

Convert wNAF values to witness values.

Parameters

builder
wnaf_values
is_negative
rounds

Returns: std::vector<field_ct>

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.

◆ convert_wnaf_values_to_witnesses() [2/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<size_t wnaf_size>

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.

◆ create_endo_pair_four_bit_table_plookup()

template<typename C , class Fq , class Fr , class G >

std::pair< typename element< C, Fq, Fr, G >::four_bit_table_plookup, typename element< C, Fq, Fr, G >::four_bit_table_plookup > bb::stdlib::element_default::element< C, Fq, Fr, G >::create_endo_pair_four_bit_table_plookup ( const element< Builder_, Fq, Fr, NativeGroup > & input )

staticprivate

Create a endo pair four bit table for the given group element.

Template Parameters

C
Fq
Fr
G

Parameters

input

Returns: std::pair<four_bit_table_plookup, four_bit_table_plookup>

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 363 of file biggroup_tables.hpp.

◆ create_endo_pair_quad_lookup_table()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

static std::pair< quad_lookup_table, quad_lookup_table > bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::create_endo_pair_quad_lookup_table ( const std::array< element< Builder_, Fq, Fr, NativeGroup >, 4 > & inputs )

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 661 of file biggroup.hpp.

◆ create_group_element_rom_tables() [1/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<size_t num_elements>

static std::array< twin_rom_table< Builder >, 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
	)

staticprivate

◆ create_group_element_rom_tables() [2/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<size_t num_elements>

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.

Template Parameters

C
Fq
Fr
G
num_elements
typename

Parameters

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!

Returns: std::array<twin_rom_table<C>, Fq::NUM_LIMBS + 1>

Definition at line 33 of file biggroup_tables.hpp.

◆ dbl()

template<typename C , class Fq , class Fr , class G >

element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::dbl ( ) const

Definition at line 298 of file biggroup_impl.hpp.

◆ fix_witness()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

void bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::fix_witness ( )

inline

Fix a witness. The value of the witness is constrained with a selector.

Definition at line 163 of file biggroup.hpp.

◆ from_witness()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

static element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::from_witness	(	Builder *	ctx,
		const typename NativeGroup::affine_element< Builder_, Fq, Fr, NativeGroup > &	input
	)

inlinestatic

Create a biggroup witness from a native group element, allocating new witnesses as necessary.

Parameters

ctx
input

Returns: element

Warning: Use this carefully, as its creating free witnesses.

Definition at line 89 of file biggroup.hpp.

◆ get_context() [1/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

Builder * bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::get_context ( ) const

inline

Definition at line 384 of file biggroup.hpp.

◆ get_context() [2/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

Builder * bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::get_context ( const element< Builder_, Fq, Fr, NativeGroup > & other ) const

inline

Definition at line 386 of file biggroup.hpp.

◆ get_origin_tag()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

OriginTag bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::get_origin_tag ( ) const

inline

Definition at line 419 of file biggroup.hpp.

◆ get_staggered_wnaf_fragment_value()

template<typename C , class Fq , class Fr , class G >

template<size_t wnaf_size>

std::pair< uint64_t, bool > bb::stdlib::element_default::element< C, Fq, Fr, G >::get_staggered_wnaf_fragment_value	(	const uint64_t	fragment_u64,
		const uint64_t	stagger,
		bool	is_negative,
		bool	wnaf_skew
	)

staticprivate

Compute the stagger-related part of wNAF and the final skew.

Parameters

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.

◆ get_standard_form()

template<typename C , class Fq , class Fr , class G >

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 170 of file biggroup_impl.hpp.

◆ get_value()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

NativeGroup::affine_element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::get_value ( ) const

inline

Definition at line 336 of file biggroup.hpp.

◆ handle_points_at_infinity()

template<typename C , class Fq , class Fr , class G >

std::pair< std::vector< element< C, Fq, Fr, G > >, std::vector< Fr > > bb::stdlib::element_default::element< C, Fq, Fr, G >::handle_points_at_infinity	(	const std::vector< element< Builder_, Fq, Fr, NativeGroup > > &	_points,
		const std::vector< Fr > &	_scalars
	)

staticprivate

Handle points at infinity in batch operations, replaces (∞, scalar) pairs by (G, 0)

Replace all pairs (∞, scalar) by the pair (one, 0) where one is a fixed generator of the curve.

Parameters

_points	The input points
_scalars	The corresponding scalars

Returns: A pair of vectors containing the processed points and scalars

Only used internally in biggroup_edgecase_handling.hpp

This is a step in enabling our our multiscalar multiplication algorithms to hande points at infinity.

Definition at line 104 of file biggroup_edgecase_handling.hpp.

◆ incomplete_assert_equal()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

void bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::incomplete_assert_equal	(	const element< Builder_, Fq, Fr, NativeGroup > &	other,
		const std::string	msg = `"biggroup::incomplete_assert_equal"`
	)		const

inline

Asserts that two group elements are equal (i.e., x, y coordinates and infinity flag are all equal).

Parameters

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 269 of file biggroup.hpp.

◆ is_constant()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

bool bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::is_constant ( ) const

inline

Definition at line 141 of file biggroup.hpp.

◆ is_point_at_infinity()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

bool_ct bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::is_point_at_infinity ( ) const

inline

Definition at line 395 of file biggroup.hpp.

◆ mask_points()

template<typename C , class Fq , class Fr , class G >

std::pair< std::vector< element< C, Fq, Fr, G > >, std::vector< Fr > > bb::stdlib::element_default::element< C, Fq, Fr, G >::mask_points	(	const std::vector< element< Builder_, Fq, Fr, NativeGroup > > &	_points,
		const std::vector< Fr > &	_scalars,
		const Fr &	masking_scalar
	)

staticprivate

Mask points for batch multiplication to handle edge cases.

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.

Parameters

_points	The points to be masked
_scalars	The corresponding scalars
masking_scalar	The masking scalar used to randomise the points

Returns: A pair of vectors containing the masked points and scalars

Only used internally in biggroup_edgecase_handling.hpp

Add (δ)G, (2δ)G, (4δ)G 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. Since the challenge δ not known to the prover ahead of time, it is not possible to create points that cancel out the offset generators.

Definition at line 44 of file biggroup_edgecase_handling.hpp.

◆ multiple_montgomery_ladder()

template<typename C , class Fq , class Fr , class G >

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.

Template Parameters

C
Fq
Fr
G

Parameters

add

Returns: element<C, Fq, Fr, G>

Definition at line 475 of file biggroup_impl.hpp.

◆ normalize()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::normalize ( ) const

inline

Definition at line 277 of file biggroup.hpp.

◆ one()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

static element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::one ( Builder * ctx )

inlinestatic

Creates a constant group generator.

Definition at line 176 of file biggroup.hpp.

◆ operator*()

template<typename C , class Fq , class Fr , class G >

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 961 of file biggroup_impl.hpp.

◆ operator+()

template<typename C , class Fq , class Fr , class G >

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 94 of file biggroup_impl.hpp.

◆ operator+=()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::operator+= ( const element< Builder_, Fq, Fr, NativeGroup > & other )

inline

Definition at line 210 of file biggroup.hpp.

◆ operator-() [1/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::operator- ( ) const

inline

Definition at line 204 of file biggroup.hpp.

◆ operator-() [2/2]

template<typename C , class Fq , class Fr , class G >

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 182 of file biggroup_impl.hpp.

◆ operator-=()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::operator-= ( const element< Builder_, Fq, Fr, NativeGroup > & other )

inline

Definition at line 215 of file biggroup.hpp.

◆ operator=() [1/2]

template<typename C , class Fq , class Fr , class G >

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 70 of file biggroup_impl.hpp.

◆ operator=() [2/2]

template<typename C , class Fq , class Fr , class G >

element< C, Fq, Fr, G > & bb::stdlib::element_default::element< C, Fq, Fr, G >::operator= ( element< Builder_, Fq, Fr, NativeGroup > && other )

noexcept

Definition at line 82 of file biggroup_impl.hpp.

◆ point_at_infinity()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

static element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::point_at_infinity ( Builder * ctx )

inlinestatic

Definition at line 185 of file biggroup.hpp.

◆ process_strauss_msm_rounds()

template<typename C , class Fq , class Fr , class G >

element< C, Fq, Fr, G > bb::stdlib::element_default::element< C, Fq, Fr, G >::process_strauss_msm_rounds	(	const std::vector< element< Builder_, Fq, Fr, NativeGroup > > &	points,
		const std::vector< Fr > &	scalars,
		const size_t	max_num_bits
	)

staticprivate

Definition at line 702 of file biggroup_impl.hpp.

◆ read_group_element_rom_tables() [1/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<size_t num_elements>

static element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::read_group_element_rom_tables	(	const std::array< twin_rom_table< Builder >, Fq::NUM_LIMBS+1 > &	tables,
		const field_ct &	index,
		const std::array< uint256_t, Fq::NUM_LIMBS *2 > &	limb_max
	)

staticprivate

◆ read_group_element_rom_tables() [2/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<size_t >

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_ct &	index,
		const std::array< uint256_t, Fq::NUM_LIMBS *2 > &	limb_max
	)

Definition at line 74 of file biggroup_tables.hpp.

◆ reconstruct_bigfield_from_wnaf() [1/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<size_t wnaf_size>

static Fr bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::reconstruct_bigfield_from_wnaf	(	Builder *	builder,
		const std::vector< field_ct > &	wnaf,
		const bool_ct &	positive_skew,
		const bool_ct &	negative_skew,
		const field_ct &	stagger_fragment,
		const size_t	stagger,
		const size_t	rounds
	)

staticprivate

Reconstruct a scalar from its wNAF representation in circuit.

Parameters

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

Returns: Fr The reconstructed scalar

◆ reconstruct_bigfield_from_wnaf() [2/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<size_t wnaf_size>

Fr bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::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
	)

Definition at line 105 of file biggroup_nafs.hpp.

◆ reconstruct_from_public()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

static element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::reconstruct_from_public ( const std::span< const Fr, PUBLIC_INPUTS_SIZE > & limbs )

inlinestatic

Reconstruct a biggroup element from limbs of its coordinates (generally stored in the public inputs)

Parameters

limbs

Returns: element

Definition at line 70 of file biggroup.hpp.

◆ reduce()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

element bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::reduce ( ) const

inline

Definition at line 286 of file biggroup.hpp.

◆ scalar_mul()

template<typename C , class Fq , class Fr , class G >

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.

Parameters

scalar	A field element. If `max_num_bits`>0, the length of the scalar must not exceed `max_num_bits`.
max_num_bits	Positive integer < 254. Default value 0 corresponds to scalar multiplication by scalars of unspecified length.

Returns: element<C, Fq, Fr, G>

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 976 of file biggroup_impl.hpp.

◆ secp256k1_ecdsa_mul() [1/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<typename X = NativeGroup, typename = typename std::enable_if_t<std::is_same<X, secp256k1::g1>::value>>

static element 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
	)

static

◆ secp256k1_ecdsa_mul() [2/2]

template<class Builder_ , class Fq , class Fr , class NativeGroup >

template<typename , typename >

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.

◆ set_free_witness_tag()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

void bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::set_free_witness_tag ( )

inline

Set the free witness flag for the element's tags.

Definition at line 437 of file biggroup.hpp.

◆ set_origin_tag()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

void bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::set_origin_tag ( OriginTag tag ) const

inline

Definition at line 405 of file biggroup.hpp.

◆ set_point_at_infinity()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

void bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::set_point_at_infinity	(	const bool_ct &	is_infinity,
		const bool &	add_to_used_witnesses = `false`
	)

inline

Definition at line 396 of file biggroup.hpp.

◆ set_public()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

uint32_t bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::set_public ( ) const

inline

Set the witness indices for the x and y coordinates to public.

Returns: uint32_t Index at which the representation is stored in the public inputs

Definition at line 56 of file biggroup.hpp.

◆ unset_free_witness_tag()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

void bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::unset_free_witness_tag ( )

inline

Unset the free witness flag for the element's tags.

Definition at line 427 of file biggroup.hpp.

◆ validate_on_curve()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

void bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::validate_on_curve ( std::string const & msg = "biggroup::validate_on_curve" ) const

inline

Check that the point is on the curve.

Definition at line 114 of file biggroup.hpp.

◆ x()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

const Fq & bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::x ( ) const

inline

Definition at line 392 of file biggroup.hpp.

◆ y()

template<class Builder_ , class Fq , class Fr , class NativeGroup >

const Fq & bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::y ( ) const

inline

Definition at line 393 of file biggroup.hpp.

Friends And Related Symbol Documentation

◆ element_test_accessor

template<class Builder_ , class Fq , class Fr , class NativeGroup >

friend class element_test_accessor

friend

Definition at line 445 of file biggroup.hpp.

Member Data Documentation

◆ _is_infinity

template<class Builder_ , class Fq , class Fr , class NativeGroup >

bool_ct bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::_is_infinity

private

Definition at line 450 of file biggroup.hpp.

◆ _x

template<class Builder_ , class Fq , class Fr , class NativeGroup >

Fq bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::_x

private

Definition at line 448 of file biggroup.hpp.

◆ _y

template<class Builder_ , class Fq , class Fr , class NativeGroup >

Fq bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::_y

private

Definition at line 449 of file biggroup.hpp.

◆ PUBLIC_INPUTS_SIZE

template<class Builder_ , class Fq , class Fr , class NativeGroup >

constexpr size_t bb::stdlib::element_default::element< Builder_, Fq, Fr, NativeGroup >::PUBLIC_INPUTS_SIZE = BIGGROUP_PUBLIC_INPUTS_SIZE

staticconstexpr

Definition at line 36 of file biggroup.hpp.

The documentation for this class was generated from the following files:

src/barretenberg/stdlib/primitives/biggroup/biggroup.hpp
src/barretenberg/stdlib/primitives/biggroup/biggroup_edgecase_handling.hpp
src/barretenberg/stdlib/primitives/biggroup/biggroup_impl.hpp
src/barretenberg/stdlib/primitives/biggroup/biggroup_nafs.hpp
src/barretenberg/stdlib/primitives/biggroup/biggroup_secp256k1.hpp
src/barretenberg/stdlib/primitives/biggroup/biggroup_tables.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ BaseField

◆ batch_lookup_table

◆ biggroup_tag

◆ bool_ct

◆ Builder

◆ field_ct

◆ quad_lookup_table

◆ triple_lookup_table

◆ twin_lookup_table

◆ witness_ct

Constructor & Destructor Documentation

◆ element() [1/6]

◆ element() [2/6]

◆ element() [3/6]

◆ element() [4/6]

◆ element() [5/6]

◆ element() [6/6]

◆ ~element()

Member Function Documentation

◆ assert_coordinates_in_field()

◆ batch_mul()

accumulating the results in an accumulator point. The first NAF entry (I, see below) is used to

I Iteration 1

◆ chain_add()

◆ chain_add_end()

◆ chain_add_start()

◆ checked_unconditional_add()

◆ checked_unconditional_add_sub()

◆ checked_unconditional_subtract()

◆ clear_round_provenance()

◆ compute_naf()

◆ compute_offset_generators()

◆ compute_secp256k1_endo_wnaf()

◆ compute_secp256k1_single_wnaf() [1/2]

◆ compute_secp256k1_single_wnaf() [2/2]

◆ compute_table_offset_generator()

◆ conditional_negate()

◆ conditional_select()

◆ convert_constant_to_fixed_witness()

◆ convert_wnaf_values_to_witnesses() [1/2]

◆ convert_wnaf_values_to_witnesses() [2/2]

◆ create_endo_pair_four_bit_table_plookup()

◆ create_endo_pair_quad_lookup_table()

◆ create_group_element_rom_tables() [1/2]

◆ create_group_element_rom_tables() [2/2]

◆ dbl()

◆ fix_witness()

◆ from_witness()

◆ get_context() [1/2]

◆ get_context() [2/2]

◆ get_origin_tag()

◆ get_staggered_wnaf_fragment_value()

◆ get_standard_form()

◆ get_value()

◆ handle_points_at_infinity()

◆ incomplete_assert_equal()

◆ is_constant()

◆ is_point_at_infinity()

◆ mask_points()

◆ multiple_montgomery_ladder()

◆ normalize()

◆ one()

◆ operator*()

◆ operator+()

◆ operator+=()

◆ operator-() [1/2]

◆ operator-() [2/2]

◆ operator-=()