bb::stdlib Namespace Reference

Namespaces
namespace	aes128
namespace	blake_util
namespace	element_default
namespace	element_goblin
namespace	field_conversion_tests
namespace	hash_utils
namespace	recursion
namespace	test_utils

Classes
class	bigfield
class	bigfield_test_access
class	Blake2s
class	Blake3s
struct	bn254
class	bool_t
	Implements boolean logic in-circuit. More...
class	byte_array
	Represents a dynamic array of bytes in-circuit. More...
class	cycle_group
	cycle_group represents a group Element of the proving system's embedded curve, i.e. a curve with a cofactor 1 defined over a field equal to the circuit's native field Builder::FF More...
class	cycle_scalar
	Represents a member of the Grumpkin curve scalar field (i.e. BN254 base field). More...
class	databus
class	DataBusDepot
	Class for managing propagation of databus return data commitments used in consistency checks. More...
struct	ecdsa_signature
class	field_t
class	FieldSponge
	Implements the circuit form of a cryptographic sponge over prime fields. More...
class	goblin_field
	goblin_field wraps x/y coordinates of bn254 group elements when using goblin More...
struct	grumpkin
	Curve grumpkin in circuit setting. More...
class	keccak
	KECCAK. More...
class	logic
class	plookup_read
class	poseidon2
	stdlib class that evaluates in-circuit poseidon2 hashes, consistent with behavior in crypto::poseidon2 More...
class	Poseidon2Permutation
	Circuit form of Poseidon2 permutation from https://eprint.iacr.org/2023/323. More...
class	Proof
	A simple wrapper around a vector of stdlib field elements representing a proof. More...
class	public_witness_t
class	PublicInputComponent
	A wrapper class for serializing objects to and from the public inputs of a circuit. More...
class	ram_table
class	rom_table
struct	secp256k1
struct	secp256r1
class	SHA256
class	StdlibCodec
class	straus_lookup_table
	straus_lookup_table computes a lookup table of size 1 << table_bits More...
class	straus_scalar_slices
	straus_scalar_slices decomposes an input scalar into bit-slices of size table_bits. Used in batch_mul, which implements the Straus multiscalar multiplication algorithm. More...
class	twin_rom_table
class	witness_t
struct	WycherproofTest

Concepts
concept	IsBigGroup
concept	IsGoblinBigGroup
concept	IsSerializableToPublicInputs
	A concept for types that can be serialized to public inputs.
concept	HasReconstructFromPublic
	Check if a type has reconstruct_from_public method.

Typedefs
using	WycherproofSecp256k1 = WycherproofTest< bb::curve::SECP256K1 >
using	WycherproofSecp256r1 = WycherproofTest< bb::curve::SECP256R1 >
template<typename C , typename Fq , typename Fr , typename G >
using	element = std::conditional_t< IsGoblinBigGroup< C, Fq, Fr, G >, element_goblin::goblin_element< C, goblin_field< C >, Fr, G >, element_default::element< C, Fq, Fr, G > >
	element wraps either element_default::element or element_goblin::goblin_element depending on parametrisation

Functions
template<typename Builder , typename Curve , typename Fq , typename Fr , typename G1 >
bool_t< Builder >	ecdsa_verify_signature (const stdlib::byte_array< Builder > &hashed_message, const G1 &public_key, const ecdsa_signature< Builder > &sig)
	Verify ECDSA signature. Returns bool_t(true/false) depending on whether the signature is valid or not.
template<typename Builder >
void	generate_ecdsa_verification_test_circuit (Builder &builder, size_t num_iterations)
	Generate a simple ecdsa verification circuit for testing purposes.
template<typename C , typename T >
std::ostream &	operator<< (std::ostream &os, bigfield< T, C > const &v)
template<typename C >
std::ostream &	operator<< (std::ostream &os, goblin_field< C > const &v)
template<typename T >
std::ostream &	operator<< (std::ostream &os, bool_t< T > const &v)
template<typename Builder >
std::ostream &	operator<< (std::ostream &os, byte_array< Builder > const &arr)
template<typename T >
T *	validate_context (T *ptr)
template<typename T , typename... Ts>
T *	validate_context (T *first, Ts *... rest)
template<typename T , typename Container >
T *	validate_context (const Container &elements)
template<typename Builder >
std::ostream &	operator<< (std::ostream &os, field_t< Builder > const &v)
template<typename Builder >
void	validate_split_in_field_unsafe (const field_t< Builder > &lo, const field_t< Builder > &hi, const size_t lo_bits, const uint256_t &field_modulus)
	Validates that lo + hi * 2^lo_bits < field_modulus (assuming range constraints on lo and hi)
template<typename Builder >
std::pair< field_t< Builder >, field_t< Builder > >	split_unique (const field_t< Builder > &field, const size_t lo_bits, const bool skip_range_constraints=false)
	Split a bn254 scalar field element into unique lo and hi limbs.
template<typename Builder >
void	mark_witness_as_used (const field_t< Builder > &field)
	Mark a field_t witness as used (for UltraBuilder only).
template std::pair< field_t< bb::UltraCircuitBuilder >, field_t< bb::UltraCircuitBuilder > >	split_unique (const field_t< bb::UltraCircuitBuilder > &field, const size_t lo_bits, const bool skip_range_constraints)
template std::pair< field_t< bb::MegaCircuitBuilder >, field_t< bb::MegaCircuitBuilder > >	split_unique (const field_t< bb::MegaCircuitBuilder > &field, const size_t lo_bits, const bool skip_range_constraints)
template void	validate_split_in_field_unsafe (const field_t< bb::UltraCircuitBuilder > &lo, const field_t< bb::UltraCircuitBuilder > &hi, const size_t lo_bits, const uint256_t &field_modulus)
template void	validate_split_in_field_unsafe (const field_t< bb::MegaCircuitBuilder > &lo, const field_t< bb::MegaCircuitBuilder > &hi, const size_t lo_bits, const uint256_t &field_modulus)
template void	mark_witness_as_used (const field_t< bb::UltraCircuitBuilder > &field)
template void	mark_witness_as_used (const field_t< bb::MegaCircuitBuilder > &field)
template<typename Builder >
std::ostream &	operator<< (std::ostream &os, cycle_group< Builder > const &v)

Variables
const std::vector< WycherproofSecp256k1 >	secp256k1_tests
	Test for Secp256k1 ECDSA signatures taken from the Wycherproof project.
const std::vector< WycherproofSecp256r1 >	secp256r1_tests
	Test for Secp256r1 ECDSA signatures taken from the Wycherproof project.

Detailed Description

Optimizations:

1. use lookup tables for basic XOR operations
2. replace use of uint32 with basic field_t type

Typedef Documentation

element

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

using bb::stdlib::element = typedef std::conditional_t<IsGoblinBigGroup<C, Fq, Fr, G>, element_goblin::goblin_element<C, goblin_field<C>, Fr, G>, element_default::element<C, Fq, Fr, G> >

element wraps either element_default::element or element_goblin::goblin_element depending on parametrisation

if C = MegaBuilder, G = bn254, Fq = bigfield<C, bb::Bn254FqParams>, Fr = field_t then we're cooking

Definition at line 1021 of file biggroup.hpp.

WycherproofSecp256k1

using bb::stdlib::WycherproofSecp256k1 = typedef WycherproofTest<bb::curve::SECP256K1>

Definition at line 33 of file ecdsa_tests_data.hpp.

WycherproofSecp256r1

using bb::stdlib::WycherproofSecp256r1 = typedef WycherproofTest<bb::curve::SECP256R1>

Definition at line 34 of file ecdsa_tests_data.hpp.

Function Documentation

ecdsa_verify_signature()

template<typename Builder , typename Curve , typename Fq , typename Fr , typename G1 >

bool_t< Builder > bb::stdlib::ecdsa_verify_signature	(	const stdlib::byte_array< Builder > &	hashed_message,
		const G1 &	public_key,
		const ecdsa_signature< Builder > &	sig
	)

Verify ECDSA signature. Returns bool_t(true/false) depending on whether the signature is valid or not.

Fix the following notation:

1. \(E\) is an elliptic curve over the base field \(\mathbb{F}_q\).
2. \(G\) is a generator of the group of points of \(E\), the order of \(G\) is \(n\) and prime.
3. \(a \in \mathbb{F}_n^{\ast}\) is a private key, and \(P := aG\) is the associated public key
4. \(\mathbf{H}\) is a hash function

Given a message \(m\), a couple \((r,s)\) is a valid signature for the message \(m\) with respect to the public key \(P\) if (following https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf):

1. \(P\) is a point on \(E\)
2. \(P = (x,y)\), then x < q, y < q
3. \(P\) is not the point at infinity
4. \(0 < r < n\)
5. \(0 < s < (n+1) / 2\)
6. Define \(e := \mathbf{H}(m) \mod n\) and \(Q := e s^{-1} G + r s^{-1} P \)
7. \(Q\) is not the point at infinity
8. \(Q_x = r \mod n\) (note that \(Q_x \in \mathbb{F}_q\))

Note

The requirement of step 4. is to avoid signature malleability: if \((r,s)\) is a valid signature for message \(m\) and public key \(P\), so is \((r,n-s)\). We protect against malleability by enforcing that \(s\) is always the lowest of the two possible values.

In Ethereum signatures contain also a recovery byte \(v\) which is used to recover the public key for which the signature is to be validated. As we receive the public key as part of the inputs to the verification function, we do not handle the recovery byte. The signature which is the input to the verification function is given by \((r,s)\). The users of the verification function should handle the recovery byte if that is in their interest.

This function verifies that sig is a valid signature for the public key public_key. The function returns an in-circuit boolean value which bears witness to whether the signature verification was successfull or not. The boolean is NOT constrained to be equal to bool_t(true).

There is one case in which the circuit will be unsatisfiable even if the witness values are correct: for the curve Secp256R1 when the public key is plus or minus the generator point. This is due to our usage of lookup tables.

Template Parameters

Builder
Curve
Fq
Fr
G1

Parameters

hashed_message
public_key
sig

Returns

bool_t<Builder>

Definition at line 67 of file ecdsa_impl.hpp.

generate_ecdsa_verification_test_circuit()

template<typename Builder >

void bb::stdlib::generate_ecdsa_verification_test_circuit	(	Builder &	builder,
		size_t	num_iterations
	)

Generate a simple ecdsa verification circuit for testing purposes.

Template Parameters

Builder

Parameters

builder
num_iterations	number of signature verifications to perform

Definition at line 179 of file ecdsa_impl.hpp.

mark_witness_as_used() [1/3]

template void bb::stdlib::mark_witness_as_used

(

const field_t< bb::MegaCircuitBuilder > &

field

)

mark_witness_as_used() [2/3]

template void bb::stdlib::mark_witness_as_used

(

const field_t< bb::UltraCircuitBuilder > &

field

)

mark_witness_as_used() [3/3]

template<typename Builder >

void bb::stdlib::mark_witness_as_used

(

const field_t< Builder > &

field

)

Mark a field_t witness as used (for UltraBuilder only).

For certain operations like assert_is_not_zero, we create intermediate witnesses that are not part of the circuit's primary logic but are needed for constraints. This function marks such witnesses as "used" to prevent them from being incorrectly identified as unused. Uses raw witness_index to avoid normalization overhead.

This is a no-op for non-Ultra builders.

Parameters

field

The field element whose witness should be marked as used

Definition at line 107 of file field_utils.cpp.

operator<<() [1/6]

template<typename C , typename T >

std::ostream & bb::stdlib::operator<< ( std::ostream &  os, bigfield< T, C > const &  v  )

inline

Definition at line 1188 of file bigfield.hpp.

operator<<() [2/6]

template<typename T >

std::ostream & bb::stdlib::operator<< ( std::ostream &  os, bool_t< T > const &  v  )

inline

Definition at line 185 of file bool.hpp.

operator<<() [3/6]

template<typename Builder >

std::ostream & bb::stdlib::operator<< ( std::ostream &  os, byte_array< Builder > const &  arr  )

inline

Definition at line 131 of file byte_array.hpp.

operator<<() [4/6]

template<typename Builder >

std::ostream & bb::stdlib::operator<< ( std::ostream &  os, cycle_group< Builder > const &  v  )

inline

Definition at line 234 of file cycle_group.hpp.

operator<<() [5/6]

template<typename Builder >

std::ostream & bb::stdlib::operator<< ( std::ostream &  os, field_t< Builder > const &  v  )

inline

Definition at line 580 of file field.hpp.

operator<<() [6/6]

template<typename C >

std::ostream & bb::stdlib::operator<< ( std::ostream &  os, goblin_field< C > const &  v  )

inline

Definition at line 192 of file goblin_field.hpp.

split_unique() [1/3]

template std::pair< field_t< bb::MegaCircuitBuilder >, field_t< bb::MegaCircuitBuilder > > bb::stdlib::split_unique	(	const field_t< bb::MegaCircuitBuilder > &	field,
		const size_t	lo_bits,
		const bool	skip_range_constraints
	)

split_unique() [2/3]

template std::pair< field_t< bb::UltraCircuitBuilder >, field_t< bb::UltraCircuitBuilder > > bb::stdlib::split_unique	(	const field_t< bb::UltraCircuitBuilder > &	field,
		const size_t	lo_bits,
		const bool	skip_range_constraints
	)

split_unique() [3/3]

template<typename Builder >

std::pair< field_t< Builder >, field_t< Builder > > bb::stdlib::split_unique	(	const field_t< Builder > &	field,
		const size_t	lo_bits,
		const bool	skip_range_constraints = false
	)

Split a bn254 scalar field element into unique lo and hi limbs.

Splits field into a low and high limb at the given bit index with:

1. Reconstruction constraint: lo + hi * 2^lo_bits = field
2. Modulus check: lo + hi * 2^lo_bits < bn254::ScalarField::modulus
3. Range constraints: lo in [0, 2^lo_bits), hi in [0, 2^(254-lo_bits)) (unless skip_range_constraints = true)

Note

The combination of (2) and (3) establishes the uniqueness of the decomposition.

Parameters

field	The bn254 scalar field element to split
lo_bits	Number of bits for the low limb
skip_range_constraints	If true, skip range constraints (use when they're implicit, e.g., in lookups)

Returns

std::pair<field_t<Builder>, field_t<Builder>> The (lo, hi) pair

Definition at line 60 of file field_utils.cpp.

validate_context() [1/3]

template<typename T , typename Container >

T * bb::stdlib::validate_context

(

const Container &

elements

)

Definition at line 36 of file field.hpp.

validate_context() [2/3]

template<typename T , typename... Ts>

T * bb::stdlib::validate_context	(	T *	first,
		Ts *...	rest
	)

Definition at line 23 of file field.hpp.

validate_context() [3/3]

template<typename T >

T * bb::stdlib::validate_context

(

T *

ptr

)

Definition at line 17 of file field.hpp.

validate_split_in_field_unsafe() [1/3]

template void bb::stdlib::validate_split_in_field_unsafe	(	const field_t< bb::MegaCircuitBuilder > &	lo,
		const field_t< bb::MegaCircuitBuilder > &	hi,
		const size_t	lo_bits,
		const uint256_t &	field_modulus
	)

validate_split_in_field_unsafe() [2/3]

template void bb::stdlib::validate_split_in_field_unsafe	(	const field_t< bb::UltraCircuitBuilder > &	lo,
		const field_t< bb::UltraCircuitBuilder > &	hi,
		const size_t	lo_bits,
		const uint256_t &	field_modulus
	)

validate_split_in_field_unsafe() [3/3]

template<typename Builder >

void bb::stdlib::validate_split_in_field_unsafe	(	const field_t< Builder > &	lo,
		const field_t< Builder > &	hi,
		const size_t	lo_bits,
		const uint256_t &	field_modulus
	)

Validates that lo + hi * 2^lo_bits < field_modulus (assuming range constraints on lo and hi)

Uses a borrow-subtraction algorithm to check the inequality. Can be used in conjunction with range constraints on lo and hi to establish a unique decomposition of a field element.

Warning

: This function only checks the borrow arithmetic; it does NOT apply the following range constraints which are necessary to establish the above inequality in the integer sense:

• lo < 2^lo_bits
• hi < 2^hi_bits (where hi_bits = field_modulus.get_msb() + 1 - lo_bits)

Parameters

lo	The low limb
hi	The high limb
lo_bits	The bit position at which the split occurred
field_modulus	The field modulus to validate against

Definition at line 14 of file field_utils.cpp.

Variable Documentation

secp256k1_tests

const std::vector<WycherproofSecp256k1> bb::stdlib::secp256k1_tests

Test for Secp256k1 ECDSA signatures taken from the Wycherproof project.

Definition at line 40 of file ecdsa_tests_data.hpp.

secp256r1_tests

const std::vector<WycherproofSecp256r1> bb::stdlib::secp256r1_tests

Test for Secp256r1 ECDSA signatures taken from the Wycherproof project.

Definition at line 101 of file ecdsa_tests_data.hpp.