Inheritance diagram for proof_system::UltraCircuitBuilder_< Arithmetization >:

Classes
struct	cached_partial_non_native_field_multiplication
	Used to store instructions to create partial_non_native_field_multiplication gates. We want to cache these (and remove duplicates) as the stdlib code can end up multiplying the same inputs repeatedly. More...

struct	CircuitDataBackup
	CircuitDataBackup is a structure we use to store all the information about the circuit that is needed to restore it back to a pre-finalized state. More...

struct	non_native_field_multiplication_cross_terms

struct	RamRecord
	A RAM memory record that can be ordered. More...

struct	RamTranscript
	Each ram array is an instance of memory transcript. It saves values and indexes for a particular memory array. More...

struct	RangeList

struct	RomRecord
	A ROM memory record that can be ordered. More...

struct	RomTranscript
	Each rom array is an instance of memory transcript. It saves values and indexes for a particular memory array. More...

Public Types
enum	AUX_SELECTORS { NONE , LIMB_ACCUMULATE_1 , LIMB_ACCUMULATE_2 , NON_NATIVE_FIELD_1 , NON_NATIVE_FIELD_2 , NON_NATIVE_FIELD_3 , RAM_CONSISTENCY_CHECK , ROM_CONSISTENCY_CHECK , RAM_TIMESTAMP_CHECK , ROM_READ , RAM_READ , RAM_WRITE }

using	FF = typename Arithmetization::FF

using	WireVector = std::vector< uint32_t, ContainerSlabAllocator< uint32_t > >

using	SelectorVector = std::vector< FF, ContainerSlabAllocator< FF > >

typedef std::pair< uint32_t, FF >	scaled_witness

typedef std::tuple< scaled_witness, scaled_witness, FF >	add_simple

Public Types inherited from proof_system::CircuitBuilderBase< Arithmetization::FF >
using	FF = Arithmetization::FF

using	EmbeddedCurve = std::conditional_t< std::same_as< FF, barretenberg::g1::coordinate_field >, curve::BN254, curve::Grumpkin >

Public Member Functions
WireVector &	w_l ()

WireVector &	w_r ()

WireVector &	w_o ()

WireVector &	w_4 ()

const WireVector &	w_l () const

const WireVector &	w_r () const

const WireVector &	w_o () const

const WireVector &	w_4 () const

SelectorVector &	q_m ()

SelectorVector &	q_c ()

SelectorVector &	q_1 ()

SelectorVector &	q_2 ()

SelectorVector &	q_3 ()

SelectorVector &	q_4 ()

SelectorVector &	q_arith ()

SelectorVector &	q_sort ()

SelectorVector &	q_elliptic ()

SelectorVector &	q_aux ()

SelectorVector &	q_lookup_type ()

const SelectorVector &	q_c () const

const SelectorVector &	q_1 () const

const SelectorVector &	q_2 () const

const SelectorVector &	q_3 () const

const SelectorVector &	q_4 () const

const SelectorVector &	q_arith () const

const SelectorVector &	q_sort () const

const SelectorVector &	q_elliptic () const

const SelectorVector &	q_aux () const

const SelectorVector &	q_lookup_type () const

const SelectorVector &	q_m () const

void	process_non_native_field_multiplications ()
	Called in `compute_proving_key` when finalizing circuit. Iterates over the cached_non_native_field_multiplication objects, removes duplicates, and instantiates the remainder as constraints`.

	UltraCircuitBuilder_ (const size_t size_hint=0)

	UltraCircuitBuilder_ (const UltraCircuitBuilder_ &other)=default

	UltraCircuitBuilder_ (UltraCircuitBuilder_ &&other)

UltraCircuitBuilder_ &	operator= (const UltraCircuitBuilder_ &other)=default

UltraCircuitBuilder_ &	operator= (UltraCircuitBuilder_ &&other)

void	check_selector_length_consistency ()
	Debug helper method for ensuring all selectors have the same size.

void	finalize_circuit ()

void	add_gates_to_ensure_all_polys_are_non_zero ()
	Ensure all polynomials have at least one non-zero coefficient to avoid commiting to the zero-polynomial.

void	create_add_gate (const add_triple_< FF > &in) override
	Create an addition gate, where in.a * in.a_scaling + in.b * in.b_scaling + in.c * in.c_scaling + in.const_scaling = 0.

void	create_big_add_gate (const add_quad_< FF > &in, const bool use_next_gate_w_4=false)
	Create a big addition gate, where in.a * in.a_scaling + in.b * in.b_scaling + in.c * in.c_scaling + in.d * in.d_scaling + in.const_scaling = 0. If include_next_gate_w_4 is enabled, then thes sum also adds the value of the 4-th witness at the next index.

void	create_big_add_gate_with_bit_extraction (const add_quad_< FF > &in)
	A legacy method that was used to extract a bit from c-4d by using gate selectors in the Turboplonk, but is simulated here for ultraplonk.

void	create_big_mul_gate (const mul_quad_< FF > &in)
	Create a basic multiplication gate q_m * a * b + q_1 * a + q_2 * b + q_3 * c + q_4 * d + q_c = 0 (q_arith = 1)

void	create_balanced_add_gate (const add_quad_< FF > &in)

void	create_mul_gate (const mul_triple_< FF > &in) override
	Create a multiplication gate with q_m * a * b + q_3 * c + q_const = 0.

void	create_bool_gate (const uint32_t a) override
	Generate an arithmetic gate equivalent to x^2 - x = 0, which forces x to be 0 or 1.

void	create_poly_gate (const poly_triple_< FF > &in) override
	A plonk gate with disabled (set to zero) fourth wire. q_m * a * b + q_1 * a + q_2 * b + q_3.

void	create_ecc_add_gate (const ecc_add_gate_< FF > &in)
	Create an elliptic curve addition gate.

void	create_ecc_dbl_gate (const ecc_dbl_gate_< FF > &in)
	Create an elliptic curve doubling gate.

void	fix_witness (const uint32_t witness_index, const FF &witness_value)
	Add a gate equating a particular witness to a constant, fixing it the value.

void	create_new_range_constraint (const uint32_t variable_index, const uint64_t target_range, std::string const msg="create_new_range_constraint")
	Constrain a variable to a range.

void	create_range_constraint (const uint32_t variable_index, const size_t num_bits, std::string const &msg)

accumulator_triple_< FF >	create_logic_constraint (const uint32_t a, const uint32_t b, const size_t num_bits, bool is_xor_gate)

accumulator_triple_< FF >	create_and_constraint (const uint32_t a, const uint32_t b, const size_t num_bits)

accumulator_triple_< FF >	create_xor_constraint (const uint32_t a, const uint32_t b, const size_t num_bits)

uint32_t	put_constant_variable (const FF &variable)

size_t	get_num_constant_gates () const override

void	get_num_gates_split_into_components (size_t &count, size_t &rangecount, size_t &romcount, size_t &ramcount, size_t &nnfcount) const
	Get the final number of gates in a circuit, which consists of the sum of: 1) Current number number of actual gates 2) Number of public inputs, as we'll need to add a gate for each of them 3) Number of Rom array-associated gates 4) Number of range-list associated gates 5) Number of non-native field multiplication gates.

size_t	get_num_gates () const override
	Get the final number of gates in a circuit, which consists of the sum of: 1) Current number number of actual gates 2) Number of public inputs, as we'll need to add a gate for each of them 3) Number of Rom array-associated gates 4) Number of range-list associated gates 5) Number of non-native field multiplication gates.

size_t	get_total_circuit_size () const
	Get the size of the circuit if it was finalized now.

virtual void	print_num_gates () const override
	Print the number and composition of gates in the circuit.

void	assert_equal_constant (const uint32_t a_idx, const FF &b, std::string const &msg="assert equal constant")

void	add_table_column_selector_poly_to_proving_key (barretenberg::polynomial &small, const std::string &tag)

void	initialize_precomputed_table (const plookup::BasicTableId id, bool(generator)(std::vector< FF > &, std::vector< FF > &, std::vector< FF > &), std::array< FF, 2 >(get_values_from_key)(const std::array< uint64_t, 2 >))

plookup::BasicTable &	get_table (const plookup::BasicTableId id)

plookup::MultiTable &	create_table (const plookup::MultiTableId id)

plookup::ReadData< uint32_t >	create_gates_from_plookup_accumulators (const plookup::MultiTableId &id, const plookup::ReadData< FF > &read_values, const uint32_t key_a_index, std::optional< uint32_t > key_b_index=std::nullopt)
	Perform a series of lookups, one for each 'row' in read_values.

std::vector< uint32_t >	decompose_into_default_range (const uint32_t variable_index, const uint64_t num_bits, const uint64_t target_range_bitnum=DEFAULT_PLOOKUP_RANGE_BITNUM, std::string const &msg="decompose_into_default_range")

std::vector< uint32_t >	decompose_into_default_range_better_for_oddlimbnum (const uint32_t variable_index, const size_t num_bits, std::string const &msg="decompose_into_default_range_better_for_oddlimbnum")

void	create_dummy_constraints (const std::vector< uint32_t > &variable_index)

void	create_sort_constraint (const std::vector< uint32_t > &variable_index)

void	create_sort_constraint_with_edges (const std::vector< uint32_t > &variable_index, const FF &, const FF &)

void	assign_tag (const uint32_t variable_index, const uint32_t tag)

uint32_t	create_tag (const uint32_t tag_index, const uint32_t tau_index)

uint32_t	get_new_tag ()

RangeList	create_range_list (const uint64_t target_range)

void	process_range_list (RangeList &list)

void	process_range_lists ()

void	apply_aux_selectors (const AUX_SELECTORS type)
	Enable the auxilary gate of particular type.

void	range_constrain_two_limbs (const uint32_t lo_idx, const uint32_t hi_idx, const size_t lo_limb_bits=DEFAULT_NON_NATIVE_FIELD_LIMB_BITS, const size_t hi_limb_bits=DEFAULT_NON_NATIVE_FIELD_LIMB_BITS)

std::array< uint32_t, 2 >	decompose_non_native_field_double_width_limb (const uint32_t limb_idx, const size_t num_limb_bits=(2 *DEFAULT_NON_NATIVE_FIELD_LIMB_BITS))
	Decompose a single witness into two, where the lowest is DEFAULT_NON_NATIVE_FIELD_LIMB_BITS (68) range constrained and the lowst is num_limb_bits - DEFAULT.. range constrained.

std::array< uint32_t, 2 >	evaluate_non_native_field_multiplication (const non_native_field_witnesses< FF > &input, const bool range_constrain_quotient_and_remainder=true)
	Queue up non-native field multiplication data.

std::array< uint32_t, 2 >	queue_partial_non_native_field_multiplication (const non_native_field_witnesses< FF > &input)

std::array< uint32_t, 5 >	evaluate_non_native_field_subtraction (add_simple limb0, add_simple limb1, add_simple limb2, add_simple limb3, std::tuple< uint32_t, uint32_t, FF > limbp)

std::array< uint32_t, 5 >	evaluate_non_native_field_addition (add_simple limb0, add_simple limb1, add_simple limb2, add_simple limb3, std::tuple< uint32_t, uint32_t, FF > limbp)

size_t	create_ROM_array (const size_t array_size)
	Create a new read-only memory region.

void	set_ROM_element (const size_t rom_id, const size_t index_value, const uint32_t value_witness)
	Initialize a rom cell to equal `value_witness`

void	set_ROM_element_pair (const size_t rom_id, const size_t index_value, const std::array< uint32_t, 2 > &value_witnesses)
	Initialize a ROM array element with a pair of witness values.

uint32_t	read_ROM_array (const size_t rom_id, const uint32_t index_witness)
	Read a single element from ROM.

std::array< uint32_t, 2 >	read_ROM_array_pair (const size_t rom_id, const uint32_t index_witness)
	Read a pair of elements from ROM.

void	create_ROM_gate (RomRecord &record)
	Gate that'reads' from a ROM table. i.e. table index is a witness not precomputed.

void	create_sorted_ROM_gate (RomRecord &record)
	Gate that performs consistency checks to validate that a claimed ROM read value is correct.

void	process_ROM_array (const size_t rom_id)
	Compute additional gates required to validate ROM reads. Called when generating the proving key.

void	process_ROM_arrays ()

void	create_RAM_gate (RamRecord &record)
	Gate that performs a read/write operation into a RAM table. i.e. table index is a witness not precomputed.

void	create_sorted_RAM_gate (RamRecord &record)
	Gate that performs consistency checks to validate that a claimed RAM read/write value is correct.

void	create_final_sorted_RAM_gate (RamRecord &record, const size_t ram_array_size)
	Performs consistency checks to validate that a claimed RAM read/write value is correct. Used for the final gate in a list of sorted RAM records.

size_t	create_RAM_array (const size_t array_size)
	Create a new updatable memory region.

void	init_RAM_element (const size_t ram_id, const size_t index_value, const uint32_t value_witness)
	Initialize a RAM cell to equal `value_witness`

uint32_t	read_RAM_array (const size_t ram_id, const uint32_t index_witness)

void	write_RAM_array (const size_t ram_id, const uint32_t index_witness, const uint32_t value_witness)

void	process_RAM_array (const size_t ram_id)
	Compute additional gates required to validate RAM read/writes. Called when generating the proving key.

void	process_RAM_arrays ()

FF	compute_arithmetic_identity (FF q_arith_value, FF q_1_value, FF q_2_value, FF q_3_value, FF q_4_value, FF q_m_value, FF q_c_value, FF w_1_value, FF w_2_value, FF w_3_value, FF w_4_value, FF w_1_shifted_value, FF w_4_shifted_value, const FF alpha_base, const FF alpha) const
	Arithmetic gate-related methods.

FF	compute_auxilary_identity (FF q_aux_value, FF q_arith_value, FF q_1_value, FF q_2_value, FF q_3_value, FF q_4_value, FF q_m_value, FF q_c_value, FF w_1_value, FF w_2_value, FF w_3_value, FF w_4_value, FF w_1_shifted_value, FF w_2_shifted_value, FF w_3_shifted_value, FF w_4_shifted_value, FF alpha_base, FF alpha, FF eta) const
	Plookup Auxiliary Gate Identity.

FF	compute_elliptic_identity (FF q_elliptic_value, FF q_1_value, FF q_m_value, FF w_2_value, FF w_3_value, FF w_1_shifted_value, FF w_2_shifted_value, FF w_3_shifted_value, FF w_4_shifted_value, FF alpha_base, FF alpha) const
	Elliptic curve identity gate methods implement elliptic curve point addition.

FF	compute_genperm_sort_identity (FF q_sort_value, FF w_1_value, FF w_2_value, FF w_3_value, FF w_4_value, FF w_1_shifted_value, FF alpha_base, FF alpha) const
	General permutation sorting identity.

bool	check_circuit ()
	Check that the circuit is correct in its current state.

Public Member Functions inherited from proof_system::CircuitBuilderBase< Arithmetization::FF >
	CircuitBuilderBase (size_t size_hint=0)

	CircuitBuilderBase (const CircuitBuilderBase &other)=default

	CircuitBuilderBase (CircuitBuilderBase &&other) noexcept=default

CircuitBuilderBase &	operator= (const CircuitBuilderBase &other)=default

CircuitBuilderBase &	operator= (CircuitBuilderBase &&other) noexcept=default

virtual size_t	get_num_gates () const

virtual void	print_num_gates () const

virtual size_t	get_num_variables () const

virtual void	create_add_gate (const add_triple_< FF > &in)=0

virtual void	create_mul_gate (const mul_triple_< FF > &in)=0

virtual void	create_bool_gate (const uint32_t a)=0

virtual void	create_poly_gate (const poly_triple_< FF > &in)=0

virtual size_t	get_num_constant_gates () const=0

uint32_t	get_first_variable_in_class (uint32_t index) const

void	update_real_variable_indices (uint32_t index, uint32_t new_real_index)

FF	get_variable (const uint32_t index) const

const FF &	get_variable_reference (const uint32_t index) const

uint32_t	get_public_input_index (const uint32_t witness_index) const

FF	get_public_input (const uint32_t index) const

std::vector< FF >	get_public_inputs () const

virtual uint32_t	add_variable (const FF &in)

virtual void	set_variable_name (uint32_t index, const std::string &name)

virtual void	update_variable_names (uint32_t index)

virtual void	finalize_variable_names ()

virtual msgpack::sbuffer	export_circuit ()

virtual uint32_t	add_public_variable (const FF &in)

virtual void	set_public_input (const uint32_t witness_index)

virtual void	assert_equal (const uint32_t a_idx, const uint32_t b_idx, std::string const &msg="assert_equal")

size_t	get_circuit_subgroup_size (const size_t num_gates) const

size_t	get_num_public_inputs () const

void	assert_valid_variables (const std::vector< uint32_t > &variable_indices)

bool	is_valid_variable (uint32_t variable_index)

void	add_recursive_proof (const std::vector< uint32_t > &proof_output_witness_indices)
	Add information about which witnesses contain the recursive proof computation information.

void	set_recursive_proof (const std::vector< uint32_t > &proof_output_witness_indices)
	Update recursive_proof_public_input_indices with existing public inputs that represent a recursive proof.

bool	failed () const

const std::string &	err () const

void	set_err (std::string msg)

void	failure (std::string msg)

Public Attributes
std::vector< std::string >	selector_names = Arithmetization::selector_names

size_t	num_vars_added_in_constructor = 0

std::array< std::vector< uint32_t, barretenberg::ContainerSlabAllocator< uint32_t > >, NUM_WIRES >	wires

Arithmetization	selectors

std::map< FF, uint32_t >	constant_variable_indices

std::vector< plookup::BasicTable >	lookup_tables

std::vector< plookup::MultiTable >	lookup_multi_tables

std::map< uint64_t, RangeList >	range_lists

std::vector< RamTranscript >	ram_arrays
	Each entry in ram_arrays represents an independent RAM table. RamTranscript tracks the current table state, as well as the 'records' produced by each read and write operation. Used in `compute_proving_key` to generate consistency check gates required to validate the RAM read/write history.

std::vector< RomTranscript >	rom_arrays
	Each entry in ram_arrays represents an independent ROM table. RomTranscript tracks the current table state, as well as the 'records' produced by each read operation. Used in `compute_proving_key` to generate consistency check gates required to validate the ROM read history.

std::vector< uint32_t >	memory_read_records

std::vector< uint32_t >	memory_write_records

std::vector< cached_partial_non_native_field_multiplication >	cached_partial_non_native_field_multiplications

bool	circuit_finalized = false

Public Attributes inherited from proof_system::CircuitBuilderBase< Arithmetization::FF >
size_t	num_gates

std::vector< uint32_t >	public_inputs

std::vector< FF >	variables

std::unordered_map< uint32_t, std::string >	variable_names

std::vector< uint32_t >	next_var_index

std::vector< uint32_t >	prev_var_index

std::vector< uint32_t >	real_variable_index

std::vector< uint32_t >	real_variable_tags

uint32_t	current_tag

std::map< uint32_t, uint32_t >	tau

std::vector< uint32_t >	recursive_proof_public_input_indices

bool	contains_recursive_proof

bool	_failed

std::string	_err

uint32_t	zero_idx

uint32_t	one_idx

Static Public Attributes
static constexpr size_t	NUM_WIRES = Arithmetization::NUM_WIRES

static constexpr size_t	program_width = Arithmetization::NUM_WIRES

static constexpr size_t	num_selectors = Arithmetization::NUM_SELECTORS

static constexpr std::string_view	NAME_STRING = "UltraArithmetization"

static constexpr CircuitType	CIRCUIT_TYPE = CircuitType::ULTRA

static constexpr merkle::HashType	merkle_hash_type = merkle::HashType::LOOKUP_PEDERSEN

static constexpr pedersen::CommitmentType	commitment_type = pedersen::CommitmentType::FIXED_BASE_PEDERSEN

static constexpr size_t	UINT_LOG2_BASE = 6

static constexpr size_t	DEFAULT_PLOOKUP_RANGE_BITNUM = 14

static constexpr size_t	DEFAULT_PLOOKUP_RANGE_STEP_SIZE = 3

static constexpr size_t	DEFAULT_PLOOKUP_RANGE_SIZE = (1 << DEFAULT_PLOOKUP_RANGE_BITNUM) - 1

static constexpr size_t	DEFAULT_NON_NATIVE_FIELD_LIMB_BITS = 68

static constexpr uint32_t	UNINITIALIZED_MEMORY_RECORD = UINT32_MAX

static constexpr size_t	NUMBER_OF_GATES_PER_RAM_ACCESS = 2

static constexpr size_t	NUMBER_OF_ARITHMETIC_GATES_PER_RAM_ARRAY = 1

static constexpr size_t	NUM_RESERVED_GATES = 4

static constexpr size_t	GATES_PER_NON_NATIVE_FIELD_MULTIPLICATION_ARITHMETIC = 7

Static Public Attributes inherited from proof_system::CircuitBuilderBase< Arithmetization::FF >
static constexpr uint32_t	REAL_VARIABLE

static constexpr uint32_t	FIRST_VARIABLE_IN_CLASS

Member Function Documentation

◆ add_gates_to_ensure_all_polys_are_non_zero()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::add_gates_to_ensure_all_polys_are_non_zero

Ensure all polynomials have at least one non-zero coefficient to avoid commiting to the zero-polynomial.

Parameters

in	Structure containing variables and witness selectors

◆ add_table_column_selector_poly_to_proving_key()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::add_table_column_selector_poly_to_proving_key	(	barretenberg::polynomial &	small,
		const std::string &	tag
	)

Plookup Methods

◆ apply_aux_selectors()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::apply_aux_selectors ( const AUX_SELECTORS type )

Enable the auxilary gate of particular type.

Custom Gate Selectors

If we have several operations being performed do not require parametrization (if we put each of them into a separate widget they would not require any selectors other than the ones enabling the operation itself, for example q_special*(w_l-2*w_r)), we can group them all into one widget, by using a special selector q_aux for all of them and enabling each in particular, depending on the combination of standard selector values. So you can do: q_aux * (q_1 * q_2 * statement_1 + q_3 * q_4 * statement_2). q_1=q_2=1 would activate statement_1, while q_3=q_4=1 would activate statement_2

Multiple selectors are used to 'switch' aux gates on/off according to the following pattern:

gate type	q_aux	q_1	q_2	q_3	q_4	q_m	q_c	q_arith
Bigfield Limb Accumulation 1	1	0	0	1	1	0	—	0
Bigfield Limb Accumulation 2	1	0	0	1	0	1	—	0
Bigfield Product 1	1	0	1	1	0	0	—	0
Bigfield Product 2	1	0	1	0	1	0	—	0
Bigfield Product 3	1	0	1	0	0	1	—	0
RAM/ROM access gate	1	1	0	0	0	1	—	0
RAM timestamp check	1	1	0	0	1	0	—	0
ROM consistency check	1	1	1	0	0	0	—	0
RAM consistency check	1	0	0	0	0	0	0	1

Parameters

type

◆ check_circuit()

template<typename Arithmetization >

bool proof_system::UltraCircuitBuilder_< Arithmetization >::check_circuit

Check that the circuit is correct in its current state.

The method switches the circuit to the "in-the-head" version, finalizes it, checks gates, lookups and permutations and then switches it back from the in-the-head version, discarding the updates

Returns: true; false

◆ check_selector_length_consistency()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::check_selector_length_consistency ( )

inline

Debug helper method for ensuring all selectors have the same size.

Each gate construction method manually appends values to the selectors. Failing to update one of the selectors will lead to an unsatisfiable circuit. This method provides a mechanism for ensuring that each selector has been updated as expected. Its logic is only active in debug mode.

◆ compute_arithmetic_identity()

template<typename Arithmetization >

Arithmetization::FF proof_system::UltraCircuitBuilder_< Arithmetization >::compute_arithmetic_identity	(	FF	q_arith_value,
		FF	q_1_value,
		FF	q_2_value,
		FF	q_3_value,
		FF	q_4_value,
		FF	q_m_value,
		FF	q_c_value,
		FF	w_1_value,
		FF	w_2_value,
		FF	w_3_value,
		FF	w_4_value,
		FF	w_1_shifted_value,
		FF	w_4_shifted_value,
		const FF	alpha_base,
		const FF	alpha
	)		const

inline

Arithmetic gate-related methods.

The whole formula without alpha scaling is:

q_arith * ( ( (-1/2) * (q_arith - 3) * q_m * w_1 * w_2 + q_1 * w_1 + q_2 * w_2 + q_3 * w_3 + q_4 * w_4 + q_c ) + (q_arith - 1)*( α * (q_arith - 2) * (w_1 + w_4 - w_1_omega + q_m) + w_4_omega) ) = 0

This formula results in several cases depending on q_arith:

q_arith == 0: Arithmetic gate is completely disabled
q_arith == 1: Everything in the minigate on the right is disabled. The equation is just a standard plonk equation with extra wires: q_m * w_1 * w_2 + q_1 * w_1 + q_2 * w_2 + q_3 * w_3 + q_4 * w_4 + q_c = 0
q_arith == 2: The (w_1 + w_4 - ...) term is disabled. THe equation is: (1/2) * q_m * w_1 * w_2 + q_1 * w_1 + q_2 * w_2 + q_3 * w_3 + q_4 * w_4 + q_c + w_4_omega = 0 It allows defining w_4 at next index (w_4_omega) in terms of current wire values
q_arith == 3: The product of w_1 and w_2 is disabled, but a mini addition gate is enabled. α² allows us to split the equation into two:

q_1 * w_1 + q_2 * w_2 + q_3 * w_3 + q_4 * w_4 + q_c + 2 * w_4_omega = 0

w_1 + w_4 - w_1_omega + q_m = 0 (we are reusing q_m here)

q_arith > 3: The product of w_1 and w_2 is scaled by (q_arith - 3), while the w_4_omega term is scaled by (q_arith

1). The equation can be split into two:

(q_arith - 3)* q_m * w_1 * w_ 2 + q_1 * w_1 + q_2 * w_2 + q_3 * w_3 + q_4 * w_4 + q_c + (q_arith - 1) * w_4_omega = 0

w_1 + w_4 - w_1_omega + q_m = 0

The problem that q_m is used both in both equations can be dealt with by appropriately changing selector values at the next gate. Then we can treat (q_arith - 1) as a simulated q_6 selector and scale q_m to handle (q_arith - 3) at product.

Uses only the alpha challenge

Compute the arithmetic relation/gate evaluation base on given selector and witness evaluations

We need this function because in ultra we have committed and non-committed gates (for example RAM and ROM). However, we'd still like to evaluate all of them, so we can't access selectors and witness values directly.

You can scroll up to look at the description of the general logic of this gate

Parameters

q_arith_value
q_1_value
q_2_value
q_3_value
q_4_value
q_m_value
q_c_value
w_1_value
w_2_value
w_3_value
w_4_value
w_1_shifted_value
w_4_shifted_value
alpha_base
alpha

Returns: fr

◆ compute_auxilary_identity()

template<typename Arithmetization >

Arithmetization::FF proof_system::UltraCircuitBuilder_< Arithmetization >::compute_auxilary_identity	(	FF	q_aux_value,
		FF	q_arith_value,
		FF	q_1_value,
		FF	q_2_value,
		FF	q_3_value,
		FF	q_4_value,
		FF	q_m_value,
		FF	q_c_value,
		FF	w_1_value,
		FF	w_2_value,
		FF	w_3_value,
		FF	w_4_value,
		FF	w_1_shifted_value,
		FF	w_2_shifted_value,
		FF	w_3_shifted_value,
		FF	w_4_shifted_value,
		FF	alpha_base,
		FF	alpha,
		FF	eta
	)		const

inline

Plookup Auxiliary Gate Identity.

Evaluates polynomial identities associated with the following Ultra custom gates:

RAM/ROM read-write consistency check
RAM timestamp difference consistency check
RAM/ROM index difference consistency check
Bigfield product evaluation (3 in total)
Bigfield limb accumulation (2 in total)

Multiple selectors are used to 'switch' aux gates on/off according to the following pattern:

gate type	q_aux	q_1	q_2	q_3	q_4	q_m	q_c	q_arith
Bigfield Limb Accumulation 1	1	0	0	1	1	0	—	0
Bigfield Limb Accumulation 2	1	0	0	1	0	1	—	0
Bigfield Product 1	1	0	1	1	0	0	—	0
Bigfield Product 2	1	0	1	0	1	0	—	0
Bigfield Product 3	1	0	1	0	0	1	—	0
RAM/ROM access gate	1	1	0	0	0	1	—	0
RAM timestamp check	1	1	0	0	1	0	—	0
ROM consistency check	1	1	1	0	0	0	—	0
RAM consistency check	1	0	0	0	0	0	0	1

N.B. The RAM consistency check identity is degree 3. To keep the overall quotient degree at <=5, only 2 selectors can be used to select it.

N.B.2 The q_c selector is used to store circuit-specific values in the RAM/ROM access gate

MEMORY

A RAM memory record contains a tuple of the following fields:

i: index of memory cell being accessed
t: timestamp of memory cell being accessed (used for RAM, set to 0 for ROM)
v: value of memory cell being accessed
a: access type of record. read: 0 = read, 1 = write
r: record of memory cell. record = access + index * eta + timestamp * eta^2 + value * eta^3

A ROM memory record contains a tuple of the following fields:

i: index of memory cell being accessed
v: value1 of memory cell being accessed (ROM tables can store up to 2 values per index)
v2:value2 of memory cell being accessed (ROM tables can store up to 2 values per index)
r: record of memory cell. record = index * eta + value2 * eta^2 + value1 * eta^3

When performing a read/write access, the values of i, t, v, v2, a, r are stored in the following wires + selectors, depending on whether the gate is a RAM read/write or a ROM read

gate type	i	v2/t	v	a	r
ROM	w1	w2	w3	–	w4
RAM	w1	w2	w3	qc	w4

(for accesses where index is a circuit constant, it is assumed the circuit will apply a copy constraint on w2 to fix its value)

Memory Record Check

Memory record check is needed to generate a 4 ~ 1 correspondence between the record of the memory cell and all the other values. It allows us to use set equivalence for whole cells, since we only need to take care of 1 witness per cell

A ROM/ROM access gate can be evaluated with the identity:

qc + w1 \eta + w2 \eta^2 + w3 \eta^3 - w4 = 0

For ROM gates, qc = 0

ROM Consistency Check

For every ROM read, a set equivalence check is applied between the record witnesses, and a second set of records that are sorted.

We apply the following checks for the sorted records:

w1, w2, w3 correctly map to 'index', 'v1, 'v2' for a given record value at w4
index values for adjacent records are monotonically increasing
if, at gate i, index_i == index_{i + 1}, then value1_i == value1_{i + 1} and value2_i == value2_{i + 1}

RAM Consistency Check

The 'access' type of the record is extracted with the expression w_4 - partial_record_check (i.e. for an honest Prover w1 * eta + w2 * eta^2 + w3 * eta^3 - w4 = access. This is validated by requiring access to be boolean

For two adjacent entries in the sorted list if both A) index values match B) adjacent access value is 0 (i.e. next gate is a READ) then C) both values must match. The gate boolean check is (A && B) => C === !(A && B) || C === !A || !B || C

N.B. it is the responsibility of the circuit writer to ensure that every RAM cell is initialized with a WRITE operation.

RAM Timestamp Consistency Check

| w1 | w2 | w3 | w4 | | index | timestamp | timestamp_check | – |

Let delta_index = index_{i + 1} - index_{i}

Iff delta_index == 0, timestamp_check = timestamp_{i + 1} - timestamp_i Else timestamp_check = 0

The complete RAM/ROM memory identity

◆ compute_elliptic_identity()

template<typename Arithmetization >

Arithmetization::FF proof_system::UltraCircuitBuilder_< Arithmetization >::compute_elliptic_identity	(	FF	q_elliptic_value,
		FF	q_1_value,
		FF	q_m_value,
		FF	w_2_value,
		FF	w_3_value,
		FF	w_1_shifted_value,
		FF	w_2_shifted_value,
		FF	w_3_shifted_value,
		FF	w_4_shifted_value,
		FF	alpha_base,
		FF	alpha
	)		const

inline

Elliptic curve identity gate methods implement elliptic curve point addition.

The basic equation for the elliptic curve in short weierstrass form is y^2 == x^3 + a * x + b.

The addition formulas are: λ = (y_2 - y_1) / (x_2 - x_1) x_3 = λ^2 - x_2 - x_1 = (y_2 - y_1)^2 / (x_2 - x_1)^2 - x_2 - x_1 = ((y_2 - y_1)^2 - (x_2 - x_1) * (x_2^2 - x_1^2)) / (x_2 - x_1)^2

If we assume that the points being added are distinct and not invereses of each other (so their x coordinates differ), then we can rephrase this equality: x_3 * (x_2 - x_1)^2 = ((y_2 - y_1)^2 - (x_2 - x_1) * (x_2^2 - x_1^2))

Compute the identity of the arithmetic gate given all coefficients

Parameters

q_1_value	1 or -1 (the sign). Controls whether we are subtracting or adding the second point
w_2_value	x₁
w_3_value	y₁
w_1_shifted_value	x₂
w_2_shifted_value	y₂
w_3_shifted_value	x₃
w_4_shifted_value	y₃

Returns: fr

◆ compute_genperm_sort_identity()

template<typename Arithmetization >

Arithmetization::FF proof_system::UltraCircuitBuilder_< Arithmetization >::compute_genperm_sort_identity	(	FF	q_sort_value,
		FF	w_1_value,
		FF	w_2_value,
		FF	w_3_value,
		FF	w_4_value,
		FF	w_1_shifted_value,
		FF	alpha_base,
		FF	alpha
	)		const

inline

General permutation sorting identity.

This identity binds together the values of witnesses on the same row (w_1, w_2, w_3, w_4) and the w_1 witness on the next row (w_1_shifted) so that the difference between 2 consecutive elements is in the set {0,1,2,3}

Compute a single general permutation sorting identity

Parameters

w_1_value
w_2_value
w_3_value
w_4_value
w_1_shifted_value
alpha_base
alpha

Returns: fr

◆ create_add_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_add_gate ( const add_triple_< FF > & in )

overridevirtual

Create an addition gate, where in.a * in.a_scaling + in.b * in.b_scaling + in.c * in.c_scaling + in.const_scaling = 0.

Arithmetic selector is set to 1, all other gate selectors are 0. Mutliplication selector is set to 0

Parameters

in	A structure with variable indexes and selector values for the gate.

Implements proof_system::CircuitBuilderBase< Arithmetization::FF >.

◆ create_big_add_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_big_add_gate	(	const add_quad_< FF > &	in,
		const bool	include_next_gate_w_4 = `false`
	)

Create a big addition gate, where in.a * in.a_scaling + in.b * in.b_scaling + in.c * in.c_scaling + in.d * in.d_scaling + in.const_scaling = 0. If include_next_gate_w_4 is enabled, then thes sum also adds the value of the 4-th witness at the next index.

Parameters

in	Structure with variable indexes and wire selector values
include_next_gate_w_4	Switches on/off the addition of w_4 at the next index

◆ create_big_add_gate_with_bit_extraction()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_big_add_gate_with_bit_extraction ( const add_quad_< FF > & in )

A legacy method that was used to extract a bit from c-4d by using gate selectors in the Turboplonk, but is simulated here for ultraplonk.

Parameters

in	Structure with variables and witness selector values

◆ create_big_mul_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_big_mul_gate ( const mul_quad_< FF > & in )

Create a basic multiplication gate q_m * a * b + q_1 * a + q_2 * b + q_3 * c + q_4 * d + q_c = 0 (q_arith = 1)

Parameters

in	Structure containing variables and witness selectors

◆ create_bool_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_bool_gate ( const uint32_t variable_index )

overridevirtual

Generate an arithmetic gate equivalent to x^2 - x = 0, which forces x to be 0 or 1.

Parameters

variable_index the variable which needs to be constrained

Implements proof_system::CircuitBuilderBase< Arithmetization::FF >.

◆ create_ecc_add_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_ecc_add_gate ( const ecc_add_gate_< FF > & in )

Create an elliptic curve addition gate.

x and y are defined over scalar field.

Parameters

in	Elliptic curve point addition gate parameters, including the the affine coordinates of the two points being added, the resulting point coordinates and the selector values that describe whether the second point is negated.

gate structure: | 1 | 2 | 3 | 4 | | – | x1 | y1 | – | | x2 | x3 | y3 | y2 | we can chain successive ecc_add_gates if x3 y3 of previous gate equals x1 y1 of current gate

◆ create_ecc_dbl_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_ecc_dbl_gate ( const ecc_dbl_gate_< FF > & in )

Create an elliptic curve doubling gate.

Parameters

in	Elliptic curve point doubling gate parameters

gate structure: | 1 | 2 | 3 | 4 | | - | x1 | y1 | - | | - | x3 | y3 | - | we can chain an ecc_add_gate + an ecc_dbl_gate if x3 y3 of previous add_gate equals x1 y1 of current gate can also chain double gates together

◆ create_final_sorted_RAM_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_final_sorted_RAM_gate	(	RamRecord &	record,
		const size_t	ram_array_size
	)

Performs consistency checks to validate that a claimed RAM read/write value is correct. Used for the final gate in a list of sorted RAM records.

Parameters

record Stores details of this read operation. Mutated by this fn!

◆ create_mul_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_mul_gate ( const mul_triple_< FF > & in )

overridevirtual

Create a multiplication gate with q_m * a * b + q_3 * c + q_const = 0.

q_arith == 1

Parameters

in	Structure containing variables and witness selectors

Implements proof_system::CircuitBuilderBase< Arithmetization::FF >.

◆ create_new_range_constraint()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_new_range_constraint	(	const uint32_t	variable_index,
		const uint64_t	target_range,
		std::string const	msg = `"create_new_range_constraint"`
	)

Constrain a variable to a range.

Checks if the range [0, target_range] already exists. If it doesn't, then creates a new range. Then tags variable as belonging to this set.

Parameters

variable_index
target_range

◆ create_poly_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_poly_gate ( const poly_triple_< FF > & in )

overridevirtual

A plonk gate with disabled (set to zero) fourth wire. q_m * a * b + q_1 * a + q_2 * b + q_3.

c + q_const = 0

Parameters

in	Structure containing variables and witness selectors

Implements proof_system::CircuitBuilderBase< Arithmetization::FF >.

◆ create_RAM_array()

template<typename Arithmetization >

size_t proof_system::UltraCircuitBuilder_< Arithmetization >::create_RAM_array ( const size_t array_size )

Create a new updatable memory region.

Creates a transcript object, where the inside memory state array is filled with "uninitialized memory" and and empty memory record array. Puts this object into the vector of ROM arrays.

Parameters

array_size The size of region in elements

Returns: size_t The index of the element

◆ create_RAM_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_RAM_gate ( RamRecord & record )

Gate that performs a read/write operation into a RAM table. i.e. table index is a witness not precomputed.

Parameters

record Stores details of this read operation. Mutated by this fn!

◆ create_range_constraint()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_range_constraint	(	const uint32_t	variable_index,
		const size_t	num_bits,
		std::string const &	msg
	)

inline

N.B. if variable_index is not used in any arithmetic constraints, this will create an unsatisfiable circuit! this range constraint will increase the size of the 'sorted set' of range-constrained integers by 1. The 'non-sorted set' of range-constrained integers is a subset of the wire indices of all arithmetic gates. No arithmetic gate => size imbalance between sorted and non-sorted sets. Checking for this and throwing an error would require a refactor of the Composer to catelog all 'orphan' variables not assigned to gates.

TODO(Suyash): The following is a temporary fix to make sure the range constraints on numbers with num_bits <= DEFAULT_PLOOKUP_RANGE_BITNUM is correctly enforced in the circuit. Longer term, as Zac says, we would need to refactor the composer to fix this.

◆ create_range_list()

template<typename Arithmetization >

UltraCircuitBuilder_< Arithmetization >::RangeList proof_system::UltraCircuitBuilder_< Arithmetization >::create_range_list ( const uint64_t target_range )

Generalized Permutation Methods

◆ create_ROM_array()

template<typename Arithmetization >

size_t proof_system::UltraCircuitBuilder_< Arithmetization >::create_ROM_array ( const size_t array_size )

Create a new read-only memory region.

Memory

Creates a transcript object, where the inside memory state array is filled with "uninitialized memory" and and empty memory record array. Puts this object into the vector of ROM arrays.

Parameters

array_size The size of region in elements

Returns: size_t The index of the element

◆ create_ROM_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_ROM_gate ( RomRecord & record )

Gate that'reads' from a ROM table. i.e. table index is a witness not precomputed.

Parameters

record Stores details of this read operation. Mutated by this fn!

◆ create_sorted_RAM_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_sorted_RAM_gate ( RamRecord & record )

Gate that performs consistency checks to validate that a claimed RAM read/write value is correct.

sorted RAM gates are generated sequentially, each RAM record is sorted first by index then by timestamp

Parameters

record Stores details of this read operation. Mutated by this fn!

◆ create_sorted_ROM_gate()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::create_sorted_ROM_gate ( RomRecord & record )

Gate that performs consistency checks to validate that a claimed ROM read value is correct.

sorted ROM gates are generated sequentially, each ROM record is sorted by index

Parameters

record Stores details of this read operation. Mutated by this fn!

◆ decompose_into_default_range()

template<typename Arithmetization >

std::vector< uint32_t > proof_system::UltraCircuitBuilder_< Arithmetization >::decompose_into_default_range	(	const uint32_t	variable_index,
		const uint64_t	num_bits,
		const uint64_t	target_range_bitnum = `DEFAULT_PLOOKUP_RANGE_BITNUM`,
		std::string const &	msg = `"decompose_into_default_range"`
	)

Generalized Permutation Methods

TODO: Support this commented-out code! At the moment, decompose_into_default_range generates a minimum of 1 arithmetic gate. This is not strictly required iff num_bits <= target_range_bitnum. However, this produces an edge-case where a variable is range-constrained but NOT present in an arithmetic gate. This in turn produces an unsatisfiable circuit (see create_new_range_constraint). We would need to check for and accommodate/reject this edge case to support not adding addition gates here if not reqiured if (num_bits <= target_range_bitnum) { const uint64_t expected_range = (1ULL << num_bits) - 1ULL; create_new_range_constraint(variable_index, expected_range); return { variable_index }; }

◆ decompose_non_native_field_double_width_limb()

template<typename Arithmetization >

std::array< uint32_t, 2 > proof_system::UltraCircuitBuilder_< Arithmetization >::decompose_non_native_field_double_width_limb	(	const uint32_t	limb_idx,
		const size_t	num_limb_bits = `(2 * DEFAULT_NON_NATIVE_FIELD_LIMB_BITS)`
	)

Decompose a single witness into two, where the lowest is DEFAULT_NON_NATIVE_FIELD_LIMB_BITS (68) range constrained and the lowst is num_limb_bits - DEFAULT.. range constrained.

Doesn't create gates constraining the limbs to each other.

Parameters

limb_idx	The index of the limb that will be decomposed
num_limb_bits	The range we want to constrain the original limb to

Returns: std::array<uint32_t, 2> The indices of new limbs.

◆ evaluate_non_native_field_addition()

template<typename Arithmetization >

std::array< uint32_t, 5 > proof_system::UltraCircuitBuilder_< Arithmetization >::evaluate_non_native_field_addition	(	add_simple	limb0,
		add_simple	limb1,
		add_simple	limb2,
		add_simple	limb3,
		std::tuple< uint32_t, uint32_t, FF >	limbp
	)

Uses a sneaky extra mini-addition gate in plookup_arithmetic_widget.hpp to add two non-native field elements in 4 gates (would normally take 5)

we want the following layout in program memory (x - y = z)

| 1 | 2 | 3 | 4 | |--—|--—|--—|--—| | y.p | x.0 | y.0 | x.p | (b.p + c.p - a.p = 0) AND (a.0 - b.0 - c.0 = 0) | z.p | x.1 | y.1 | z.0 | (a.1 - b.1 - c.1 = 0) | x.2 | y.2 | z.2 | z.1 | (a.2 - b.2 - c.2 = 0) | x.3 | y.3 | z.3 | — | (a.3 - b.3 - c.3 = 0)

By setting q_arith to 3, we can validate x_p + y_p + q_m = z_p

◆ evaluate_non_native_field_multiplication()

template<typename Arithmetization >

std::array< uint32_t, 2 > proof_system::UltraCircuitBuilder_< Arithmetization >::evaluate_non_native_field_multiplication	(	const non_native_field_witnesses< FF > &	input,
		const bool	range_constrain_quotient_and_remainder = `true`
	)

Queue up non-native field multiplication data.

The data queued represents a non-native field multiplication identity a * b = q * p + r, where a, b, q, r are all emulated non-native field elements that are each split across 4 distinct witness variables.

Without this queue some functions, such as proof_system::plonk::stdlib::element::multiple_montgomery_ladder, would duplicate non-native field operations, which can be quite expensive. We queue up these operations, and remove duplicates in the circuit finishing stage of the proving key computation.

The non-native field modulus, p, is a circuit constant

The return value are the witness indices of the two remainder limbs lo_1, hi_2

N.B.: This method does NOT evaluate the prime field component of non-native field multiplications.

product gate 6

hi_2 - hi_1 - lo_1 - q2 - q3 = 0

product gate 7

hi_3 - (hi_2 - q0 - q1).2^-2b

◆ evaluate_non_native_field_subtraction()

template<typename Arithmetization >

std::array< uint32_t, 5 > proof_system::UltraCircuitBuilder_< Arithmetization >::evaluate_non_native_field_subtraction	(	add_simple	limb0,
		add_simple	limb1,
		add_simple	limb2,
		add_simple	limb3,
		std::tuple< uint32_t, uint32_t, FF >	limbp
	)

we want the following layout in program memory (x - y = z)

| 1 | 2 | 3 | 4 | |--—|--—|--—|--—| | y.p | x.0 | y.0 | z.p | (b.p + c.p - a.p = 0) AND (a.0 - b.0 - c.0 = 0) | x.p | x.1 | y.1 | z.0 | (a.1 - b.1 - c.1 = 0) | x.2 | y.2 | z.2 | z.1 | (a.2 - b.2 - c.2 = 0) | x.3 | y.3 | z.3 | — | (a.3 - b.3 - c.3 = 0)

◆ finalize_circuit()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::finalize_circuit

First of all, add the gates related to ROM arrays and range lists. Note that the total number of rows in an UltraPlonk program can be divided as following:

arithmetic gates: n_computation (includes all computation gates)
rom/memory gates: n_rom
range list gates: n_range
public inputs: n_pub

Now we have two variables referred to as n in the code:

ComposerBase::n => refers to the size of the witness of a given program,
proving_key::n => the next power of two ≥ total witness size.

In this case, we have composer.num_gates = n_computation before we execute the following two functions. After these functions are executed, the composer's n is incremented to include the ROM and range list gates. Therefore we have: composer.num_gates = n_computation + n_rom + n_range.

Its necessary to include the (n_rom + n_range) gates at this point because if we already have a proving key, and we just return it without including these ROM and range list gates, the overall circuit size would not be correct (resulting in the code crashing while performing FFT operations).

Therefore, we introduce a boolean flag circuit_finalized here. Once we add the rom and range gates, our circuit is finalized, and we must not to execute these functions again.

◆ fix_witness()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::fix_witness	(	const uint32_t	witness_index,
		const FF &	witness_value
	)

Add a gate equating a particular witness to a constant, fixing it the value.

Parameters

witness_index	The index of the witness we are fixing
witness_value	The value we are fixing it to

◆ get_num_constant_gates()

template<typename Arithmetization >

size_t proof_system::UltraCircuitBuilder_< Arithmetization >::get_num_constant_gates ( ) const

inlineoverridevirtual

Implements proof_system::CircuitBuilderBase< Arithmetization::FF >.

◆ get_num_gates()

template<typename Arithmetization >

size_t proof_system::UltraCircuitBuilder_< Arithmetization >::get_num_gates ( ) const

inlineoverridevirtual

Get the final number of gates in a circuit, which consists of the sum of: 1) Current number number of actual gates 2) Number of public inputs, as we'll need to add a gate for each of them 3) Number of Rom array-associated gates 4) Number of range-list associated gates 5) Number of non-native field multiplication gates.

Returns: size_t

Reimplemented from proof_system::CircuitBuilderBase< Arithmetization::FF >.

◆ get_num_gates_split_into_components()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::get_num_gates_split_into_components	(	size_t &	count,
		size_t &	rangecount,
		size_t &	romcount,
		size_t &	ramcount,
		size_t &	nnfcount
	)		const

inline

Get the final number of gates in a circuit, which consists of the sum of: 1) Current number number of actual gates 2) Number of public inputs, as we'll need to add a gate for each of them 3) Number of Rom array-associated gates 4) Number of range-list associated gates 5) Number of non-native field multiplication gates.

Parameters

count	return arument, number of existing gates
rangecount	return argument, extra gates due to range checks
romcount	return argument, extra gates due to rom reads
ramcount	return argument, extra gates due to ram read/writes
nnfcount	return argument, extra gates due to queued non native field gates

◆ get_total_circuit_size()

template<typename Arithmetization >

size_t proof_system::UltraCircuitBuilder_< Arithmetization >::get_total_circuit_size ( ) const

inline

Get the size of the circuit if it was finalized now.

This method estimates the size of the circuit without rounding up to the next power of 2. It takes into account the possibility that the tables will dominate the size and checks both the estimated plookup argument size and the general circuit size

Returns: size_t

◆ init_RAM_element()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::init_RAM_element	(	const size_t	ram_id,
		const size_t	index_value,
		const uint32_t	value_witness
	)

Initialize a RAM cell to equal value_witness

Parameters

ram_id	The index of the ROM array, which cell we are initializing
index_value	The index of the cell within the array (an actual index, not a witness index)
value_witness	The index of the witness with the value that should be in the

◆ print_num_gates()

template<typename Arithmetization >

virtual void proof_system::UltraCircuitBuilder_< Arithmetization >::print_num_gates ( ) const

inlineoverridevirtual

Print the number and composition of gates in the circuit.

x

Reimplemented from proof_system::CircuitBuilderBase< Arithmetization::FF >.

Reimplemented in proof_system::GoblinUltraCircuitBuilder_< FF >.

◆ process_RAM_array()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::process_RAM_array ( const size_t ram_id )

Compute additional gates required to validate RAM read/writes. Called when generating the proving key.

Parameters

ram_id	The id of the RAM table
gate_offset_from_public_inputs	Required to track the gate position of where we're adding extra gates

◆ process_ROM_array()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::process_ROM_array ( const size_t rom_id )

Compute additional gates required to validate ROM reads. Called when generating the proving key.

Parameters

rom_id	The id of the ROM table
gate_offset_from_public_inputs	Required to track the gate position of where we're adding extra gates

◆ queue_partial_non_native_field_multiplication()

template<typename Arithmetization >

std::array< uint32_t, 2 > proof_system::UltraCircuitBuilder_< Arithmetization >::queue_partial_non_native_field_multiplication ( const non_native_field_witnesses< FF > & input )

Compute the limb-multiplication part of a non native field mul

i.e. compute the low 204 and high 204 bit components of a * b where a, b are nnf elements composed of 4 limbs with size DEFAULT_NON_NATIVE_FIELD_LIMB_BITS

◆ range_constrain_two_limbs()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::range_constrain_two_limbs	(	const uint32_t	lo_idx,
		const uint32_t	hi_idx,
		const size_t	lo_limb_bits = `DEFAULT_NON_NATIVE_FIELD_LIMB_BITS`,
		const size_t	hi_limb_bits = `DEFAULT_NON_NATIVE_FIELD_LIMB_BITS`
	)

Non Native Field Arithmetic

NON NATIVE FIELD METHODS

Methods to efficiently apply constraints that evaluate non-native field multiplications Applies range constraints to two 70-bit limbs, splititng each into 5 14-bit sublimbs. We can efficiently chain together two 70-bit limb checks in 3 gates, using auxiliary gates

◆ read_ROM_array()

template<typename Arithmetization >

uint32_t proof_system::UltraCircuitBuilder_< Arithmetization >::read_ROM_array	(	const size_t	rom_id,
		const uint32_t	index_witness
	)

Read a single element from ROM.

Parameters

rom_id	The index of the array to read from
index_witness	The witness with the index inside the array

Returns: uint32_t Cell value witness index

◆ read_ROM_array_pair()

template<typename Arithmetization >

std::array< uint32_t, 2 > proof_system::UltraCircuitBuilder_< Arithmetization >::read_ROM_array_pair	(	const size_t	rom_id,
		const uint32_t	index_witness
	)

Read a pair of elements from ROM.

Parameters

rom_id	The id of the ROM array
index_witness	The witness containing the index in the array

Returns: std::array<uint32_t, 2> A pair of indexes of witness variables of cell values

◆ set_ROM_element()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::set_ROM_element	(	const size_t	rom_id,
		const size_t	index_value,
		const uint32_t	value_witness
	)

Initialize a rom cell to equal value_witness

Initialize a ROM cell to equal value_witness index_value is a RAW VALUE that describes the cell index. It is NOT a witness When intializing ROM arrays, it is important that the index of the cell is known when compiling the circuit. This ensures that, for a given circuit, we know with 100% certainty that EVERY rom cell is initialized

Parameters

rom_id	The index of the ROM array, which cell we are initializing
index_value	The index of the cell within the array (an actual index, not a witness index)
value_witness	The index of the witness with the value that should be in the

The structure MemoryRecord contains the following members in this order: uint32_t index_witness; uint32_t timestamp_witness; uint32_t value_witness; uint32_t index; uint32_t timestamp; uint32_t record_witness; size_t gate_index; The second initialization value here is the witness, because in ROM it doesn't matter. We will decouple this logic later.

◆ set_ROM_element_pair()

template<typename Arithmetization >

void proof_system::UltraCircuitBuilder_< Arithmetization >::set_ROM_element_pair	(	const size_t	rom_id,
		const size_t	index_value,
		const std::array< uint32_t, 2 > &	value_witnesses
	)

Initialize a ROM array element with a pair of witness values.

Parameters

rom_id	ROM array id
index_value	Index in the array
value_witnesses	The witnesses to put in the slot

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

src/barretenberg/proof_system/circuit_builder/ultra_circuit_builder.hpp
src/barretenberg/proof_system/circuit_builder/ultra_circuit_builder.cpp

Classes

Public Types

Public Member Functions

Public Attributes

Static Public Attributes

Member Function Documentation

◆ add_gates_to_ensure_all_polys_are_non_zero()

◆ add_table_column_selector_poly_to_proving_key()

◆ apply_aux_selectors()

◆ check_circuit()

◆ check_selector_length_consistency()

◆ compute_arithmetic_identity()

◆ compute_auxilary_identity()

◆ compute_elliptic_identity()

◆ compute_genperm_sort_identity()

◆ create_add_gate()

◆ create_big_add_gate()

◆ create_big_add_gate_with_bit_extraction()

◆ create_big_mul_gate()

◆ create_bool_gate()

◆ create_ecc_add_gate()

◆ create_ecc_dbl_gate()

◆ create_final_sorted_RAM_gate()

◆ create_mul_gate()

◆ create_new_range_constraint()

◆ create_poly_gate()

◆ create_RAM_array()

◆ create_RAM_gate()

◆ create_range_constraint()

◆ create_range_list()

◆ create_ROM_array()

◆ create_ROM_gate()

◆ create_sorted_RAM_gate()

◆ create_sorted_ROM_gate()

◆ decompose_into_default_range()

◆ decompose_non_native_field_double_width_limb()

◆ evaluate_non_native_field_addition()

◆ evaluate_non_native_field_multiplication()

◆ evaluate_non_native_field_subtraction()

◆ finalize_circuit()

◆ fix_witness()

◆ get_num_constant_gates()

◆ get_num_gates()

◆ get_num_gates_split_into_components()

◆ get_total_circuit_size()

◆ init_RAM_element()

◆ print_num_gates()

◆ process_RAM_array()

◆ process_ROM_array()

◆ queue_partial_non_native_field_multiplication()

◆ range_constrain_two_limbs()

◆ read_ROM_array()

◆ read_ROM_array_pair()

◆ set_ROM_element()

◆ set_ROM_element_pair()