#include <ultra_circuit_builder.hpp>

Inheritance diagram for bb::UltraCircuitBuilder_< ExecutionTrace_ >:

Classes
struct	cached_partial_non_native_field_multiplication
	Used to store instructions to create partial_non_native_field_multiplication gates. More...

struct	RangeList

Public Types
enum	MEMORY_SELECTORS { MEM_NONE , RAM_CONSISTENCY_CHECK , ROM_CONSISTENCY_CHECK , RAM_TIMESTAMP_CHECK , ROM_READ , RAM_READ , RAM_WRITE }

enum	NNF_SELECTORS { NNF_NONE , LIMB_ACCUMULATE_1 , LIMB_ACCUMULATE_2 , NON_NATIVE_FIELD_1 , NON_NATIVE_FIELD_2 , NON_NATIVE_FIELD_3 }

using	ExecutionTrace = ExecutionTrace_

using	FF = typename ExecutionTrace::FF

using	RomRamLogic = RomRamLogic_< ExecutionTrace >

using	scaled_witness = std::pair< uint32_t, FF >

using	add_simple = std::tuple< scaled_witness, scaled_witness, FF >

Public Types inherited from bb::CircuitBuilderBase< ExecutionTrace_::FF >
using	FF = ExecutionTrace_::FF

using	EmbeddedCurve = curve::Grumpkin

Public Member Functions
void	populate_public_inputs_block ()
	Copy the public input idx data into the public inputs trace block.

void	process_non_native_field_multiplications ()
	Iterates over the cached_non_native_field_multiplication objects, removes duplicates, and instantiates the corresponding constraints.

	UltraCircuitBuilder_ (bool is_write_vk_mode=false)

	UltraCircuitBuilder_ (const std::vector< FF > &witness_values, const std::vector< uint32_t > &public_inputs, const bool is_write_vk_mode)
	Constructor from data generated from ACIR.

	UltraCircuitBuilder_ (const UltraCircuitBuilder_ &other)=default

	UltraCircuitBuilder_ (UltraCircuitBuilder_ &&other)=default

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

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

	~UltraCircuitBuilder_ () override=default

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

void	finalize_circuit (const bool ensure_nonzero)

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)
	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_mul_add_gate (const mul_quad_< FF > &in, const bool use_next_gate_w_4=false)
	Create a big multiplication-addition gate, where in.a * in.b * in.mul_scaling + 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 this sum also adds the value of the 4-th witness at the next index.

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 the sum also adds the value of the 4-th witness at the next index.

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

void	create_arithmetic_gate (const arithmetic_triple_< FF > &in)
	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 its value.

void	create_small_range_constraint (const uint32_t variable_index, const uint64_t target_range, std::string const msg="create_small_range_constraint")
	Range-constraints for small ranges, where the upper bound (`target_range`) need not be dyadic. Max possible value is 2^16 - 1. Adds variable to a RangeList for batched processing.

void	create_dyadic_range_constraint (const uint32_t variable_index, const size_t num_bits, std::string const &msg)
	Entry point for range constraints where the upper bound is a power of 2 (i.e., dyadic). Dispatches to appropriate implementation based on range size.

uint32_t	put_constant_variable (const FF &variable)

size_t	get_num_constant_gates () const override

size_t	get_num_finalized_gates () const override
	Get the number of gates in a finalized circuit.

size_t	get_num_finalized_gates_inefficient (bool ensure_nonzero=true) const
	Get the number of gates in the finalized version of the circuit.

size_t	get_tables_size () const
	Get combined size of all tables used in circuit.

size_t	get_finalized_total_circuit_size () const
	Get the actual finalized size of a circuit. Assumes the circuit is finalized already.

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

plookup::BasicTable &	get_table (const plookup::BasicTableId id)
	Get the basic table with provided ID from the set of tables for the present circuit; create it if it doesnt yet exist.

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

const std::deque< plookup::BasicTable > &	get_lookup_tables () const

std::deque< plookup::BasicTable > &	get_lookup_tables ()

size_t	get_num_lookup_tables () const

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)
	Create gates from pre-computed accumulator values which simultaneously establish individual basic-table lookups and the reconstruction of the desired result from those components.

std::vector< uint32_t >	create_limbed_range_constraint (const uint32_t variable_index, const uint64_t num_bits, const uint64_t target_range_bitnum=DEFAULT_PLOOKUP_RANGE_BITNUM, std::string const &msg="create_limbed_range_constraint")
	Range-constrain a variable to [0, 2^num_bits - 1] by decomposing into smaller limbs.

void	create_unconstrained_gate (auto &block, const uint32_t &idx_1, const uint32_t &idx_2, const uint32_t &idx_3, const uint32_t &idx_4)
	Create a gate with no constraints but with possibly non-trivial wire values.

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

void	enforce_small_deltas (const std::vector< uint32_t > &variable_indices)
	Check for a sequence of variables that the neighboring differences are in {0, 1, 2, 3} via the delta_range block.

void	create_sort_constraint_with_edges (const std::vector< uint32_t > &variable_indices, const FF &start, const FF &end)
	Constrain consecutive variable differences to be in {0, 1, 2, 3}, with boundary checks.

void	assign_tag (const uint32_t variable_index, const uint32_t tag)

void	set_tau_at_index (const uint32_t tag_index, const uint32_t tau_index)
	Set the tau(tag_index) = tau_index.

void	set_tau_transposition (const uint32_t tag_index_1, const uint32_t tag_index_2)
	Add a transposition to tau.

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_memory_selectors (const MEMORY_SELECTORS type)
	Enable the memory gate of particular type.

void	apply_nnf_selectors (const NNF_SELECTORS type)
	Enable the nnf 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::string const &msg="range_constrain_two_limbs")

std::array< uint32_t, 2 >	evaluate_non_native_field_multiplication (const non_native_multiplication_witnesses< FF > &input)
	Create gates for a full non-native field multiplication identity a * b = q * p + r.

std::array< uint32_t, 2 >	queue_partial_non_native_field_multiplication (const non_native_partial_multiplication_witnesses< FF > &input)
	Queue the addition of gates constraining the limb-multiplication part of a non native field mul.

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)
	Construct gates for non-native field subtraction.

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)
	Construct gates for non-native field addition.

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

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.

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	create_poseidon2_external_gate (const poseidon2_external_gate_< FF > &in)
	Poseidon2 external round gate, activates the q_poseidon2_external selector and relation.

void	create_poseidon2_internal_gate (const poseidon2_internal_gate_< FF > &in)
	Poseidon2 internal round gate, activates the q_poseidon2_internal selector and relation.

const std::vector< uint32_t > &	get_used_witnesses () const

const std::unordered_set< uint32_t > &	get_finalize_witnesses () const

void	update_used_witnesses (uint32_t var_idx)
	Add a witness index to the boomerang exclusion list.

void	update_used_witnesses (const std::vector< uint32_t > &used_indices)
	Add a list of witness indices to the boomerang exclusion list.

void	update_finalize_witnesses (uint32_t var_idx)
	Add a witness index to the finalize exclusion list.

void	update_finalize_witnesses (const std::vector< uint32_t > &finalize_indices)
	Add a list of witness indices to the finalize exclusion list.

msgpack::sbuffer	export_circuit () override

Public Member Functions inherited from bb::CircuitBuilderBase< ExecutionTrace_::FF >
	CircuitBuilderBase (bool is_write_vk_mode=false)

	CircuitBuilderBase (const CircuitBuilderBase &other)=default

	CircuitBuilderBase (CircuitBuilderBase &&other) noexcept=default

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

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

virtual	~CircuitBuilderBase ()=default

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

virtual size_t	get_num_variables () const

size_t	num_gates () const

void	increment_num_gates (size_t count=1)

const std::unordered_map< uint32_t, uint32_t > &	tau () const

uint32_t	zero_idx () const

const std::vector< FF > &	get_variables () const

FF	get_variable (const uint32_t index) const
	Get the value of the variable v_{index}.

void	set_variable (const uint32_t index, const FF &value)
	Set the value of the variable pointed to by a witness index.

const std::vector< uint32_t > &	public_inputs () const

void	finalize_public_inputs ()
	Set the _public_inputs_finalized to true to prevent any new public inputs from being added.

void	initialize_public_inputs (const std::vector< uint32_t > &public_inputs)
	Directly initialize the public inputs vector.

virtual uint32_t	add_variable (const FF &in)
	Add a variable to variables.

uint32_t	add_variable (const OT &in)=delete

virtual uint32_t	add_public_variable (const FF &in)
	Add a public variable to variables.

uint32_t	add_public_variable (const OT &in)=delete

virtual uint32_t	set_public_input (uint32_t witness_index)
	Make a witness variable public.

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

size_t	get_circuit_subgroup_size (size_t num_gates) const

size_t	num_public_inputs () const

virtual void	set_variable_name (uint32_t index, const std::string &name)
	Assign a name to a variable (equivalence class)

bool	failed () const

const std::string &	err () const

void	failure (std::string msg)

bool	is_write_vk_mode () const

Public Attributes
ExecutionTrace	blocks

std::unordered_map< FF, uint32_t >	constant_variable_indices

RomRamLogic	rom_ram_logic

std::vector< uint32_t >	memory_read_records

std::vector< uint32_t >	memory_write_records

std::map< uint64_t, RangeList >	range_lists

std::vector< cached_partial_non_native_field_multiplication >	cached_partial_non_native_field_multiplications

bool	circuit_finalized = false

std::vector< fr >	ipa_proof

Public Attributes inherited from bb::CircuitBuilderBase< ExecutionTrace_::FF >
std::vector< uint32_t >	real_variable_index
	Map from witness index to real variable index.

std::vector< uint32_t >	real_variable_tags
	`real_variable_tags` is the tagging mechanism for the the multiset-equality check.

uint32_t	current_tag

PairingPointsTagging	pairing_points_tagging
	PairingPoints tagging tool, used to ensure that all pairing points created in this circuit are aggregated together. This is not related to circuit logic.

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

static constexpr std::string_view	NAME_STRING = "UltraCircuitBuilder"

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 size_t	MAX_SMALL_RANGE_CONSTRAINT_VAL = (1 << 16) - 1

static constexpr size_t	MAX_NUM_BITS_RANGE_CONSTRAINT

Private Attributes
std::deque< plookup::BasicTable >	lookup_tables

std::vector< uint32_t >	used_witnesses

std::unordered_set< uint32_t >	finalize_witnesses

Additional Inherited Members
Protected Member Functions inherited from bb::CircuitBuilderBase< ExecutionTrace_::FF >
void	set_zero_idx (uint32_t value)

uint32_t	get_first_variable_in_class (uint32_t index) const
	Get the index of the first variable in class.

void	assert_valid_variables (const std::vector< uint32_t > &variable_indices)
	Check whether each variable index points to a witness value in the variables array.

Protected Attributes inherited from bb::CircuitBuilderBase< ExecutionTrace_::FF >
std::unordered_map< uint32_t, uint32_t >	_tau
	The permutation on variable tags, as a constituent of the generalized permutation argument.

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

Detailed Description

template<typename ExecutionTrace_>
class bb::UltraCircuitBuilder_< ExecutionTrace_ >

Definition at line 41 of file ultra_circuit_builder.hpp.

Member Typedef Documentation

◆ add_simple

template<typename ExecutionTrace_ >

using bb::UltraCircuitBuilder_< ExecutionTrace_ >::add_simple = std::tuple<scaled_witness, scaled_witness, FF>

Definition at line 580 of file ultra_circuit_builder.hpp.

◆ ExecutionTrace

template<typename ExecutionTrace_ >

using bb::UltraCircuitBuilder_< ExecutionTrace_ >::ExecutionTrace = ExecutionTrace_

Definition at line 43 of file ultra_circuit_builder.hpp.

◆ FF

template<typename ExecutionTrace_ >

using bb::UltraCircuitBuilder_< ExecutionTrace_ >::FF = typename ExecutionTrace::FF

Definition at line 44 of file ultra_circuit_builder.hpp.

◆ RomRamLogic

template<typename ExecutionTrace_ >

using bb::UltraCircuitBuilder_< ExecutionTrace_ >::RomRamLogic = RomRamLogic_<ExecutionTrace>

Definition at line 45 of file ultra_circuit_builder.hpp.

◆ scaled_witness

template<typename ExecutionTrace_ >

using bb::UltraCircuitBuilder_< ExecutionTrace_ >::scaled_witness = std::pair<uint32_t, FF>

Definition at line 579 of file ultra_circuit_builder.hpp.

Member Enumeration Documentation

◆ MEMORY_SELECTORS

template<typename ExecutionTrace_ >

enum bb::UltraCircuitBuilder_::MEMORY_SELECTORS

Enumerator
MEM_NONE
RAM_CONSISTENCY_CHECK
ROM_CONSISTENCY_CHECK
RAM_TIMESTAMP_CHECK
ROM_READ
RAM_READ
RAM_WRITE

Definition at line 63 of file ultra_circuit_builder.hpp.

◆ NNF_SELECTORS

template<typename ExecutionTrace_ >

enum bb::UltraCircuitBuilder_::NNF_SELECTORS

Enumerator
NNF_NONE
LIMB_ACCUMULATE_1
LIMB_ACCUMULATE_2
NON_NATIVE_FIELD_1
NON_NATIVE_FIELD_2
NON_NATIVE_FIELD_3

Definition at line 73 of file ultra_circuit_builder.hpp.

Constructor & Destructor Documentation

◆ UltraCircuitBuilder_() [1/4]

template<typename ExecutionTrace_ >

bb::UltraCircuitBuilder_< ExecutionTrace_ >::UltraCircuitBuilder_ ( bool is_write_vk_mode = false )

inline

Definition at line 223 of file ultra_circuit_builder.hpp.

◆ UltraCircuitBuilder_() [2/4]

template<typename ExecutionTrace_ >

bb::UltraCircuitBuilder_< ExecutionTrace_ >::UltraCircuitBuilder_	(	const std::vector< FF > &	witness_values,
		const std::vector< uint32_t > &	public_inputs,
		const bool	is_write_vk_mode
	)

inline

Constructor from data generated from ACIR.

Parameters

witness_values	witnesses values known to acir
public_inputs	indices of public inputs in witness array
is_write_vk_mode	true if the builder is use to generate the vk of a circuit

Note: witness_values is the vector of witness values known at the time of acir generation. It is filled with witness values which are interleaved with zeros when witnesses are optimized away.; The length of the witness vector is in general less than total number of variables/witnesses that might be present for a circuit generated from acir, since many gates will depend on the details of the bberg implementation (or more generally on the backend used to process acir).

Definition at line 247 of file ultra_circuit_builder.hpp.

◆ UltraCircuitBuilder_() [3/4]

template<typename ExecutionTrace_ >

bb::UltraCircuitBuilder_< ExecutionTrace_ >::UltraCircuitBuilder_ ( const UltraCircuitBuilder_< ExecutionTrace_ > & other )

default

◆ UltraCircuitBuilder_() [4/4]

template<typename ExecutionTrace_ >

bb::UltraCircuitBuilder_< ExecutionTrace_ >::UltraCircuitBuilder_ ( UltraCircuitBuilder_< ExecutionTrace_ > && other )

default

◆ ~UltraCircuitBuilder_()

template<typename ExecutionTrace_ >

bb::UltraCircuitBuilder_< ExecutionTrace_ >::~UltraCircuitBuilder_ ( )

overridedefault

Member Function Documentation

◆ add_gates_to_ensure_all_polys_are_non_zero()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::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

Definition at line 98 of file ultra_circuit_builder.cpp.

◆ apply_memory_selectors()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::apply_memory_selectors ( const MEMORY_SELECTORS type )

Enable the memory 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_memory for all of them and enabling each in particular, depending on the combination of standard selector values. So you can do: q_memory * (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' memory gates on/off according to the following pattern:

gate type	q_mem	q_1	q_2	q_3	q_4	q_m	q_c
RAM/ROM access gate	1	1	0	0	0	1	—
RAM timestamp check	1	1	0	0	1	0	—
ROM consistency check	1	1	1	0	0	0	—
RAM consistency check	1	0	0	1	0	0	0

Parameters

type

Definition at line 989 of file ultra_circuit_builder.cpp.

◆ apply_nnf_selectors()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::apply_nnf_selectors ( const NNF_SELECTORS type )

Enable the nnf gate of particular type.

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_nnf for all of them and enabling each in particular, depending on the combination of standard selector values. So you can do: q_nnf * (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' nnf gates on/off according to the following pattern:

gate type	q_nnf	q_2	q_3	q_4	q_m
Bigfield Limb Accumulation 1	1	0	1	1	0
Bigfield Limb Accumulation 2	1	0	1	0	1
Bigfield Product 1	1	1	1	0	0
Bigfield Product 2	1	1	0	1	0
Bigfield Product 3	1	1	0	0	1

Parameters

type

Definition at line 1111 of file ultra_circuit_builder.cpp.

◆ assert_equal_constant()

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::assert_equal_constant	(	const uint32_t	a_idx,
		const FF &	b,
		std::string const &	msg = `"assert equal constant"`
	)

inline

Definition at line 416 of file ultra_circuit_builder.hpp.

◆ assign_tag()

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::assign_tag	(	const uint32_t	variable_index,
		const uint32_t	tag
	)

inline

Generalized Permutation Methods

Definition at line 511 of file ultra_circuit_builder.hpp.

◆ check_selector_length_consistency()

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::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.

Definition at line 279 of file ultra_circuit_builder.hpp.

◆ create_add_gate()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::create_add_gate ( const add_triple_< FF > & in )

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. Multiplication selector is set to 0

Parameters

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

Definition at line 241 of file ultra_circuit_builder.cpp.

◆ create_arithmetic_gate()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::create_arithmetic_gate ( const arithmetic_triple_< FF > & in )

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

Definition at line 338 of file ultra_circuit_builder.cpp.

◆ create_big_add_gate()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::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 the 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

Definition at line 293 of file ultra_circuit_builder.cpp.

◆ create_big_mul_add_gate()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::create_big_mul_add_gate	(	const mul_quad_< FF > &	in,
		const bool	include_next_gate_w_4 = `false`
	)

Create a big multiplication-addition gate, where in.a * in.b * in.mul_scaling + 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 this 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

Definition at line 264 of file ultra_circuit_builder.cpp.

◆ create_bool_gate()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::create_bool_gate ( const uint32_t variable_index )

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

Definition at line 315 of file ultra_circuit_builder.cpp.

◆ create_dyadic_range_constraint()

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::create_dyadic_range_constraint	(	const uint32_t	variable_index,
		const size_t	num_bits,
		std::string const &	msg
	)

inline

Entry point for range constraints where the upper bound is a power of 2 (i.e., dyadic). Dispatches to appropriate implementation based on range size.

1 bit: uses a boolean gate (x * (x - 1) = 0)
≤ DEFAULT_PLOOKUP_RANGE_BITNUM bits: uses create_new_range_constraint (batched delta-range)
> DEFAULT_PLOOKUP_RANGE_BITNUM bits: uses create_limbed_range_constraint (first decompose into limbs)
Note
The upper bound of the range is specified via num_bits, i.e., the range-constrained constructed is for 1 << num_bits -1.

Definition at line 343 of file ultra_circuit_builder.hpp.

◆ create_ecc_add_gate()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::create_ecc_add_gate ( const ecc_add_gate_< FF > & in )

Create an elliptic curve addition gate.

Adds either one or two gates. In general, this method creates two gates with the following structure:

 | q_ecc | w1  | w2  | w3  | w4  |
 |-------|-----|-----|-----|-----|
 |    1  |  -  | x1  | y1  |  -  | --> constrained
 |    0  | x2  | x3  | y3  | y2  | --> "unconstrained" (utilized by previous gate via shifts)

However, if the "output" of the previous gate is equal to the "input" of the current gate, i.e. (x3, y3)_{i-1} == (x1, y1)_i, we can fuse them together by simply setting the selector values of the previous gate {i-1} to q_ecc = 1 and q_1 = sign_coefficient (which in the relation translates to q_sign). We take advantage of this frequently when performing chained additions or doubling operations.

Parameters

in	Elliptic curve point addition gate parameters

Definition at line 371 of file ultra_circuit_builder.cpp.

◆ create_ecc_dbl_gate()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::create_ecc_dbl_gate ( const ecc_dbl_gate_< FF > & in )

Create an elliptic curve doubling gate.

Adds either one or two gates. In general, this method creates two gates with the following structure:

 | q_ecc | w1  | w2  | w3  | w4  |
 |-------|-----|-----|-----|-----|
 |    1  |  -  | x1  | y1  |  -  | --> constrained
 |    0  |  -  | x3  | y3  |  -  | --> "unconstrained" (utilized by previous gate via shifts)

However, if the "output" of the previous gate is equal to the "input" of the current gate, i.e. (x3, y3)_{i-1} == (x1, y1)_i, we can fuse them together by simply setting the selector values of the previous gate {i-1} to q_ecc = 1 and q_m = 1 (which in the relation translates to q_is_double = 1). We take advantage of this frequently when performing chained additions or doubling operations.

Parameters

in	Elliptic curve point doubling gate parameters

Definition at line 420 of file ultra_circuit_builder.cpp.

◆ create_gates_from_plookup_accumulators()

template<typename ExecutionTrace >

plookup::ReadData< uint32_t > bb::UltraCircuitBuilder_< ExecutionTrace >::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`
	)

Create gates from pre-computed accumulator values which simultaneously establish individual basic-table lookups and the reconstruction of the desired result from those components.

To perform a lookup, we often need to decompose inputs into smaller "limbs", look up each limb in a BasicTable, then reconstruct the result. E.g., to perform a 32-bit XOR, we decompose into 6-bit limbs, look up each limb's XOR in a 6-bit XOR table, then reconstruct the full 32-bit XOR from those.

This method creates a sequence of lookup gates that simultaneously establish (1) the individual BasicTable lookups, and (2) the reconstruction of the final result from the results of the BasicTable lookups. This is done via an accumulator pattern where the wires in each gate store accumulated sums and we use step size coefficients (stored in q_2, q_m, q_c) to extract actual table entries via an expression of the form derived_entry_i = w_i - step_size_i * w_i_shift where w_i is the wire value at the current row, w_i_shift is the wire value at the next row. For a detailed description of the accumulator pattern, see barretenberg/stdlib_circuit_builders/plookup_tables/README.md.

The last lookup has zero step size coefficients (q_2 = q_m = q_c = 0) because there's no next accumulator to subtract; its wire values already contain the raw slices.

Parameters

id	MultiTable identifier specifying which lookup operation to perform
read_values	Pre-computed accumulator values and lookup entries from plookup::get_lookup_accumulators
key_a_index	Witness index for first input; reused in first lookup gate to avoid creating duplicate variables
key_b_index	Optional witness index for second input (2-to-1 lookups); reused in first lookup if provided

Returns: ReadData<uint32_t> containing witness indices for all created gates. Primary use: [C3][0] contains the result of the lookup operation. All indices are returned (not just the result) because some algorithms like SHA256 need access to the intermediate decomposed limb values.

Definition at line 537 of file ultra_circuit_builder.cpp.

◆ create_limbed_range_constraint()

template<typename ExecutionTrace >

std::vector< uint32_t > bb::UltraCircuitBuilder_< ExecutionTrace >::create_limbed_range_constraint	(	const uint32_t	variable_index,
		const uint64_t	num_bits,
		const uint64_t	target_range_bitnum = `DEFAULT_PLOOKUP_RANGE_BITNUM`,
		std::string const &	msg = `"create_limbed_range_constraint"`
	)

Range-constrain a variable to [0, 2^num_bits - 1] by decomposing into smaller limbs.

For large ranges, direct range-checking is too expensive (scales linearly in the target_range). Instead, we decompose the value into limbs of target_range_bitnum bits, call create_new_range_constraint on each limb, and add arithmetic gates proving the limbs reconstruct the original value.

Returns: The variable indices of the limbs.

Definition at line 624 of file ultra_circuit_builder.cpp.

◆ create_poseidon2_external_gate()

template<typename FF >

void bb::UltraCircuitBuilder_< FF >::create_poseidon2_external_gate ( const poseidon2_external_gate_< FF > & in )

Poseidon2 external round gate, activates the q_poseidon2_external selector and relation.

Definition at line 1905 of file ultra_circuit_builder.cpp.

◆ create_poseidon2_internal_gate()

template<typename FF >

void bb::UltraCircuitBuilder_< FF >::create_poseidon2_internal_gate ( const poseidon2_internal_gate_< FF > & in )

Poseidon2 internal round gate, activates the q_poseidon2_internal selector and relation.

Definition at line 1924 of file ultra_circuit_builder.cpp.

◆ create_RAM_array()

template<typename ExecutionTrace >

size_t bb::UltraCircuitBuilder_< ExecutionTrace >::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 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

Definition at line 1802 of file ultra_circuit_builder.cpp.

◆ create_range_list()

template<typename ExecutionTrace >

UltraCircuitBuilder_< ExecutionTrace >::RangeList bb::UltraCircuitBuilder_< ExecutionTrace >::create_range_list ( const uint64_t target_range )

Range constraint methods

Definition at line 590 of file ultra_circuit_builder.cpp.

◆ create_ROM_array()

template<typename ExecutionTrace >

size_t bb::UltraCircuitBuilder_< ExecutionTrace >::create_ROM_array ( const size_t array_size )

Create a new read-only memory region (a.k.a. ROM table)

Memory

Creates a transcript object, where the inside memory state array is filled with "uninitialized memory" 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

Definition at line 1787 of file ultra_circuit_builder.cpp.

◆ create_small_range_constraint()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::create_small_range_constraint	(	const uint32_t	variable_index,
		const uint64_t	target_range,
		std::string const	msg = `"create_small_range_constraint"`
	)

Range-constraints for small ranges, where the upper bound (target_range) need not be dyadic. Max possible value is 2^16 - 1. Adds variable to a RangeList for batched processing.

Constrains variable to [0, target_range], where target_range < 2^14. The constraint is deferred: variables are collected into RangeLists (grouped by target_range), then processed together in process_range_lists() which creates the actual delta-range gates. This batching is efficient because multiple variables sharing the same range can share the "staircase" of multiples-of-3 values.

Warning: This will yield an UNSATISFIABLE CIRCUIT if variable_index does not appear in any of the wires. If variable_index is not used in any gate, its tag would never appear in the permutation polynomials, yielding an unsatisfiable circuit: the GPA would fail because the range constraint increases the sorted set size by one while the non-sorted set (given by wire indices) would remain unchanged. If variable_index has not been used elsewhere, must add a dummy gate, e.g. create_unconstrained_gate(blocks.arithmetic, variable_index, this->zero_idx(), this->zero_idx(), this->zero_idx());

Note: Only suitable for small ranges (≤ DEFAULT_PLOOKUP_RANGE_SIZE). For larger ranges, use create_limbed_range_constraint which decomposes into smaller limbs.; The tag of variable_index is DEFAULT_TAG if it has never been range-constrained and a non-trivial value else. In other words, the non-trivial tags that occur for witnesses in the first phase of witness-generation precisely correspond to existing ranges (a.k.a. target_ranges) being used in range-constraints.

Definition at line 748 of file ultra_circuit_builder.cpp.

◆ create_sort_constraint_with_edges()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::create_sort_constraint_with_edges	(	const std::vector< uint32_t > &	variable_indices,
		const FF &	start,
		const FF &	end
	)

Constrain consecutive variable differences to be in {0, 1, 2, 3}, with boundary checks.

Enforces that:

variable_indices[0] == start
variable_indices[i+1] - variable_indices[i] ∈ {0, 1, 2, 3} for all adjacent pairs
variable_indices[last] == end

This is the core primitive for batched range checks: given a sorted list with bounded deltas starting at 0 and ending at N, all elements are proven to lie in [0, N].

Parameters

variable_indices	The sequence of variable indices to constrain. Must have size > NUM_WIRES and divisible by NUM_WIRES (pad if necessary).
start	The required value of the first element.
end	The required value of the last element.

Definition at line 925 of file ultra_circuit_builder.cpp.

◆ create_unconstrained_gate()

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::create_unconstrained_gate	(	auto &	block,
		const uint32_t &	idx_1,
		const uint32_t &	idx_2,
		const uint32_t &	idx_3,
		const uint32_t &	idx_4
	)

inline

Create a gate with no constraints but with possibly non-trivial wire values.

A dummy gate can be used to provide wire values to be accessed via shifts by the gate that proceeds it. The dummy gate itself does not have to satisfy any constraints (all selectors are zero).

Template Parameters

ExecutionTrace

Parameters

block Execution trace block into which the dummy gate is to be placed

Definition at line 464 of file ultra_circuit_builder.hpp.

◆ create_unconstrained_gates()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::create_unconstrained_gates ( const std::vector< uint32_t > & variable_index )

Definition at line 907 of file ultra_circuit_builder.cpp.

◆ enforce_small_deltas()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::enforce_small_deltas ( const std::vector< uint32_t > & variable_indices )

Check for a sequence of variables that the neighboring differences are in {0, 1, 2, 3} via the delta_range block.

Parameters

variable_indices

Definition at line 876 of file ultra_circuit_builder.cpp.

◆ evaluate_non_native_field_addition()

template<typename ExecutionTrace >

std::array< uint32_t, 5 > bb::UltraCircuitBuilder_< ExecutionTrace >::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
	)

Construct gates for non-native field addition.

Uses special mode of ArithmeticRelation (q_arith = 2 and q_arith = 3) to add two non-native field elements in 4 gates instead of 5.

We want to impose the following five constraints: Limb constraints: z.i = x.i * x_mulconst.i + y.i * y_mulconst.i + addconst.i, for i in [0, 3] Prime basis limb constraint: z.p = x.p + y.p + addconstp

Wire layout for non-native field addition (z = x + y)

w_1	w_2	w_3	w_4	q_arith
y.p	x.0	y.0	x.p	3
z.p	x.1	y.1	z.0	2
x.2	y.2	z.2	z.1	1
x.3	y.3	z.3	—	1

Row 0:

x.0 * x_mulconst.0 + y.0 * y_mulconst.0 - z.0 + addconst.0 = 0 (q_2*w_2 + q_3*w_3 + q_c + w_4_shift = 0)
x.p + y.p - z.p + addconstp = 0 (w_1 + w_4 - w_1_shift + q_m = 0) Row 1: x.1 * x_mulconst.1 + y.1 * y_mulconst.1 - z.1 + addconst.1 = 0 (q_2*w_2 + q_3*w_3 + q_c + w_4_shift = 0) Row 2: x.2 * x_mulconst.2 + y.2 * y_mulconst.2 - z.2 + addconst.2 = 0 (q_1*w_1 + q_2*w_2 + q_3*w_3 + q_c = 0) Row 3: x.3 * x_mulconst.3 + y.3 * y_mulconst.3 - z.3 + addconst.3 = 0 (q_1*w_1 + q_2*w_2 + q_3*w_3 + q_c = 0)

Definition at line 1536 of file ultra_circuit_builder.cpp.

◆ evaluate_non_native_field_multiplication()

template<typename ExecutionTrace >

std::array< uint32_t, 2 > bb::UltraCircuitBuilder_< ExecutionTrace >::evaluate_non_native_field_multiplication ( const non_native_multiplication_witnesses< FF > & input )

Create gates for a full non-native field multiplication identity a * b = q * p + r.

Creates gates to constrain the 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.

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

This method creates 8 gates total: 4 non-native field gates to check the limb multiplications, plus 4 arithmetic gates (3 big add gates + 1 unconstrained gate) to validate the quotient and remainder terms.

The return values are the witness indices of the two remainder limbs lo_1, hi_3

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

Definition at line 1287 of file ultra_circuit_builder.cpp.

◆ evaluate_non_native_field_subtraction()

template<typename ExecutionTrace >

std::array< uint32_t, 5 > bb::UltraCircuitBuilder_< ExecutionTrace >::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
	)

Construct gates for non-native field subtraction.

Uses special mode of ArithmeticRelation (q_arith = 2 and q_arith = 3) to subtract two non-native field elements in 4 gates instead of 5.

We want to impose the following five constraints: Limb constraints: z.i = x.i * x_mulconst.i - y.i * y_mulconst.i + addconst.i, for i in [0, 3] Prime basis limb constraint: z.p = x.p - y.p + addconstp

Wire layout for non-native field subtraction (z = x - y)

w_1	w_2	w_3	w_4	q_arith
y.p	x.0	y.0	z.p	3
x.p	x.1	y.1	z.0	2
x.2	y.2	z.2	z.1	1
x.3	y.3	z.3	—	1

Note: The positions of z.p and x.p are swapped compared to the corresponding addition method. This is necessary to achieve the desired constraint since the scaler on w_1_shift is fixed to -1 in the relation implementation.

Row 0:

x.0 * x_mulconst.0 - y.0 * y_mulconst.0 - z.0 + addconst.0 = 0 (q_2*w_2 + q_3*w_3 + q_c + w_4_shift = 0)
x.p - y.p - z.p + addconstp = 0 (w_1 + w_4 - w_1_shift + q_m = 0) Row 1: x.1 * x_mulconst.1 - y.1 * y_mulconst.1 - z.1 + addconst.1 = 0 (q_2*w_2 + q_3*w_3 + q_c + w_4_shift = 0) Row 2: x.2 * x_mulconst.2 - y.2 * y_mulconst.2 - z.2 + addconst.2 = 0 (q_1*w_1 + q_2*w_2 + q_3*w_3 + q_c = 0) Row 3: x.3 * x_mulconst.3 - y.3 * y_mulconst.3 - z.3 + addconst.3 = 0 (q_1*w_1 + q_2*w_2 + q_3*w_3 + q_c = 0)

Definition at line 1658 of file ultra_circuit_builder.cpp.

◆ export_circuit()

template<typename ExecutionTrace >

msgpack::sbuffer bb::UltraCircuitBuilder_< ExecutionTrace >::export_circuit ( )

overridevirtual

Export the existing circuit as msgpack compatible buffer. Should be called after finalize_circuit()

Returns: msgpack compatible buffer

Reimplemented from bb::CircuitBuilderBase< ExecutionTrace_::FF >.

Definition at line 1945 of file ultra_circuit_builder.cpp.

◆ finalize_circuit()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::finalize_circuit ( const bool ensure_nonzero )

First of all, add the gates related to ROM arrays and range lists. Note that the total number of rows in an Ultra 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,
prover_instance::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.

Definition at line 27 of file ultra_circuit_builder.cpp.

◆ fix_witness()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::fix_witness	(	const uint32_t	witness_index,
		const FF &	witness_value
	)

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

Parameters

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

Definition at line 459 of file ultra_circuit_builder.cpp.

◆ get_finalize_witnesses()

template<typename ExecutionTrace_ >

const std::unordered_set< uint32_t > & bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_finalize_witnesses ( ) const

inline

Definition at line 630 of file ultra_circuit_builder.hpp.

◆ get_finalized_total_circuit_size()

template<typename ExecutionTrace_ >

size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_finalized_total_circuit_size ( ) const

inline

Get the actual finalized size of a circuit. Assumes the circuit is finalized already.

This method calculates 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 plookup argument size and the general circuit size

Returns: size_t

Definition at line 409 of file ultra_circuit_builder.hpp.

◆ get_lookup_tables() [1/2]

template<typename ExecutionTrace_ >

std::deque< plookup::BasicTable > & bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_lookup_tables ( )

inline

Definition at line 433 of file ultra_circuit_builder.hpp.

◆ get_lookup_tables() [2/2]

template<typename ExecutionTrace_ >

const std::deque< plookup::BasicTable > & bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_lookup_tables ( ) const

inline

Definition at line 432 of file ultra_circuit_builder.hpp.

◆ get_multitable()

template<typename ExecutionTrace_ >

plookup::MultiTable & bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_multitable ( const plookup::MultiTableId id )

◆ get_new_tag()

template<typename ExecutionTrace_ >

uint32_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_new_tag ( )

inline

Definition at line 551 of file ultra_circuit_builder.hpp.

◆ get_num_constant_gates()

template<typename ExecutionTrace_ >

size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_num_constant_gates ( ) const

inlineoverridevirtual

Implements bb::CircuitBuilderBase< ExecutionTrace_::FF >.

Definition at line 360 of file ultra_circuit_builder.hpp.

◆ get_num_finalized_gates()

template<typename ExecutionTrace_ >

size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_num_finalized_gates ( ) const

inlineoverridevirtual

Get the number of gates in a finalized circuit.

Returns: size_t

Reimplemented from bb::CircuitBuilderBase< ExecutionTrace_::FF >.

Definition at line 366 of file ultra_circuit_builder.hpp.

◆ get_num_finalized_gates_inefficient()

template<typename ExecutionTrace_ >

size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_num_finalized_gates_inefficient ( bool ensure_nonzero = true ) const

inline

Get the number of gates in the finalized version of the circuit.

Warning: This method makes a copy then finalizes it and returns the number of gates. It is therefore inefficient and should only be used in testing/debugging scenarios.

Parameters

ensure_nonzero Whether or not to add gates to ensure all polynomials are non-zero during finalization.

Returns: size_t

Definition at line 380 of file ultra_circuit_builder.hpp.

◆ get_num_lookup_tables()

template<typename ExecutionTrace_ >

size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_num_lookup_tables ( ) const

inline

Definition at line 434 of file ultra_circuit_builder.hpp.

◆ get_table()

template<typename ExecutionTrace >

plookup::BasicTable & bb::UltraCircuitBuilder_< ExecutionTrace >::get_table ( const plookup::BasicTableId id )

Get the basic table with provided ID from the set of tables for the present circuit; create it if it doesnt yet exist.

Plookup Methods

Template Parameters

ExecutionTrace

Parameters

id

Returns: plookup::BasicTable&

Definition at line 497 of file ultra_circuit_builder.cpp.

◆ get_tables_size()

template<typename ExecutionTrace_ >

size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_tables_size ( ) const

inline

Get combined size of all tables used in circuit.

Definition at line 391 of file ultra_circuit_builder.hpp.

◆ get_used_witnesses()

template<typename ExecutionTrace_ >

const std::vector< uint32_t > & bb::UltraCircuitBuilder_< ExecutionTrace_ >::get_used_witnesses ( ) const

inline

Definition at line 629 of file ultra_circuit_builder.hpp.

◆ init_RAM_element()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::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 RAM 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

Definition at line 1815 of file ultra_circuit_builder.cpp.

◆ operator=() [1/2]

template<typename ExecutionTrace_ >

UltraCircuitBuilder_ & bb::UltraCircuitBuilder_< ExecutionTrace_ >::operator= ( const UltraCircuitBuilder_< ExecutionTrace_ > & other )

default

◆ operator=() [2/2]

template<typename ExecutionTrace_ >

UltraCircuitBuilder_ & bb::UltraCircuitBuilder_< ExecutionTrace_ >::operator= ( UltraCircuitBuilder_< ExecutionTrace_ > && other )

default

◆ populate_public_inputs_block()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::populate_public_inputs_block ( )

Copy the public input idx data into the public inputs trace block.

Definition at line 75 of file ultra_circuit_builder.cpp.

◆ process_non_native_field_multiplications()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::process_non_native_field_multiplications ( )

Iterates over the cached_non_native_field_multiplication objects, removes duplicates, and instantiates the corresponding constraints.

Intended to be called during circuit finalization.

Definition at line 1453 of file ultra_circuit_builder.cpp.

◆ process_range_list()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::process_range_list ( RangeList & list )

Definition at line 812 of file ultra_circuit_builder.cpp.

◆ process_range_lists()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::process_range_lists ( )

Definition at line 868 of file ultra_circuit_builder.cpp.

◆ put_constant_variable()

template<typename ExecutionTrace >

uint32_t bb::UltraCircuitBuilder_< ExecutionTrace >::put_constant_variable ( const FF & variable )

Definition at line 476 of file ultra_circuit_builder.cpp.

◆ queue_partial_non_native_field_multiplication()

template<typename ExecutionTrace >

std::array< uint32_t, 2 > bb::UltraCircuitBuilder_< ExecutionTrace >::queue_partial_non_native_field_multiplication ( const non_native_partial_multiplication_witnesses< FF > & input )

Queue the addition of gates constraining 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

Definition at line 1492 of file ultra_circuit_builder.cpp.

◆ range_constrain_two_limbs()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::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::string const &	msg = `"range_constrain_two_limbs"`
	)

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 nnf gates

Definition at line 1190 of file ultra_circuit_builder.cpp.

◆ read_RAM_array()

template<typename ExecutionTrace >

uint32_t bb::UltraCircuitBuilder_< ExecutionTrace >::read_RAM_array	(	const size_t	ram_id,
		const uint32_t	index_witness
	)

Definition at line 1823 of file ultra_circuit_builder.cpp.

◆ read_ROM_array()

template<typename ExecutionTrace >

uint32_t bb::UltraCircuitBuilder_< ExecutionTrace >::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

Definition at line 1882 of file ultra_circuit_builder.cpp.

◆ read_ROM_array_pair()

template<typename ExecutionTrace >

std::array< uint32_t, 2 > bb::UltraCircuitBuilder_< ExecutionTrace >::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

Definition at line 1895 of file ultra_circuit_builder.cpp.

◆ set_ROM_element()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::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 in which we are initializing a cell
index_value	The index of the cell within the array/ROM table (an actual index, not a witness index)
value_witness	The index of the witness with the value that should be in the `index_value` place in the ROM table.

Definition at line 1852 of file ultra_circuit_builder.cpp.

◆ set_ROM_element_pair()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::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

Definition at line 1867 of file ultra_circuit_builder.cpp.

◆ set_tau_at_index()

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::set_tau_at_index	(	const uint32_t	tag_index,
		const uint32_t	tau_index
	)

inline

Set the tau(tag_index) = tau_index.

Parameters

tag_index
tau_index

Returns: uint32_t

Definition at line 529 of file ultra_circuit_builder.hpp.

◆ set_tau_transposition()

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::set_tau_transposition	(	const uint32_t	tag_index_1,
		const uint32_t	tag_index_2
	)

inline

Add a transposition to tau.

Adds a simple transposition to the tau permutation, namely, swaps tag_index_1 and tag_index_2.

Parameters

tag_index_1
tag_index_2

Returns: uint32_t

Note: This is the only operation we need in our builders as our tau-permutations are products disjoint transpositions. Indeed, they are only used in memory operations and range constraints, where we simply check that the multisets of unsorted and sorted witnesses (or records) are the same.

Definition at line 545 of file ultra_circuit_builder.hpp.

◆ update_finalize_witnesses() [1/2]

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::update_finalize_witnesses ( const std::vector< uint32_t > & finalize_indices )

inline

Add a list of witness indices to the finalize exclusion list.

Parameters

finalize_indices List of witness indices to add to the finalize exclusion list

Barretenberg has special isolated subcircuit detection logic that ensures that variables in the main circuit are all connected. However, during finalization we intentionally create some subcircuits that are only connected through the set permutation. We want to exclude these variables from this detection.

Definition at line 672 of file ultra_circuit_builder.hpp.

◆ update_finalize_witnesses() [2/2]

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::update_finalize_witnesses ( uint32_t var_idx )

inline

Add a witness index to the finalize exclusion list.

Parameters

var_idx Witness index to add to the finalize exclusion list

Barretenberg has special isolated subcircuit detection logic that ensures that variables in the main circuit are all connected. However, during finalization we intentionally create some subcircuits that are only connected through the set permutation. We want to exclude these variables from this detection.

Definition at line 663 of file ultra_circuit_builder.hpp.

◆ update_used_witnesses() [1/2]

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::update_used_witnesses ( const std::vector< uint32_t > & used_indices )

inline

Add a list of witness indices to the boomerang exclusion list.

Parameters

used_indices List of witness indices to add to the boomerang exclusion list

Barretenberg has special boomerang value detection logic that detects variables that are used in one gate However, there are some cases where we want to exclude certain variables from this detection (for example, when we show that x!=0 -> x*(x^-1) = 1).

Definition at line 648 of file ultra_circuit_builder.hpp.

◆ update_used_witnesses() [2/2]

template<typename ExecutionTrace_ >

void bb::UltraCircuitBuilder_< ExecutionTrace_ >::update_used_witnesses ( uint32_t var_idx )

inline

Add a witness index to the boomerang exclusion list.

Parameters

var_idx Witness index to add to the boomerang exclusion list

Barretenberg has special boomerang value detection logic that detects variables that are used in one gate However, there are some cases where we want to exclude certain variables from this detection (for example, when we show that x!=0 -> x*(x^-1) = 1).

Definition at line 639 of file ultra_circuit_builder.hpp.

◆ write_RAM_array()

template<typename ExecutionTrace >

void bb::UltraCircuitBuilder_< ExecutionTrace >::write_RAM_array	(	const size_t	ram_id,
		const uint32_t	index_witness,
		const uint32_t	value_witness
	)

Definition at line 1829 of file ultra_circuit_builder.cpp.

Member Data Documentation

◆ blocks

template<typename ExecutionTrace_ >

ExecutionTrace bb::UltraCircuitBuilder_< ExecutionTrace_ >::blocks

Definition at line 199 of file ultra_circuit_builder.hpp.

◆ cached_partial_non_native_field_multiplications

template<typename ExecutionTrace_ >

std::vector<cached_partial_non_native_field_multiplication> bb::UltraCircuitBuilder_< ExecutionTrace_ >::cached_partial_non_native_field_multiplications

Definition at line 213 of file ultra_circuit_builder.hpp.

◆ circuit_finalized

template<typename ExecutionTrace_ >

bool bb::UltraCircuitBuilder_< ExecutionTrace_ >::circuit_finalized = false

Definition at line 215 of file ultra_circuit_builder.hpp.

◆ constant_variable_indices

template<typename ExecutionTrace_ >

std::unordered_map<FF, uint32_t> bb::UltraCircuitBuilder_< ExecutionTrace_ >::constant_variable_indices

Definition at line 202 of file ultra_circuit_builder.hpp.

◆ DEFAULT_NON_NATIVE_FIELD_LIMB_BITS

template<typename ExecutionTrace_ >

constexpr size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::DEFAULT_NON_NATIVE_FIELD_LIMB_BITS = 68

staticconstexpr

Definition at line 56 of file ultra_circuit_builder.hpp.

◆ DEFAULT_PLOOKUP_RANGE_BITNUM

template<typename ExecutionTrace_ >

constexpr size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::DEFAULT_PLOOKUP_RANGE_BITNUM = 14

staticconstexpr

Definition at line 53 of file ultra_circuit_builder.hpp.

◆ DEFAULT_PLOOKUP_RANGE_SIZE

template<typename ExecutionTrace_ >

constexpr size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::DEFAULT_PLOOKUP_RANGE_SIZE = (1 << DEFAULT_PLOOKUP_RANGE_BITNUM) - 1

staticconstexpr

Definition at line 55 of file ultra_circuit_builder.hpp.

◆ DEFAULT_PLOOKUP_RANGE_STEP_SIZE

template<typename ExecutionTrace_ >

constexpr size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::DEFAULT_PLOOKUP_RANGE_STEP_SIZE = 3

staticconstexpr

Definition at line 54 of file ultra_circuit_builder.hpp.

◆ finalize_witnesses

template<typename ExecutionTrace_ >

std::unordered_set<uint32_t> bb::UltraCircuitBuilder_< ExecutionTrace_ >::finalize_witnesses

private

Definition at line 626 of file ultra_circuit_builder.hpp.

◆ ipa_proof

template<typename ExecutionTrace_ >

std::vector<fr> bb::UltraCircuitBuilder_< ExecutionTrace_ >::ipa_proof

Definition at line 217 of file ultra_circuit_builder.hpp.

◆ lookup_tables

template<typename ExecutionTrace_ >

std::deque<plookup::BasicTable> bb::UltraCircuitBuilder_< ExecutionTrace_ >::lookup_tables

private

Definition at line 195 of file ultra_circuit_builder.hpp.

◆ MAX_NUM_BITS_RANGE_CONSTRAINT

template<typename ExecutionTrace_ >

constexpr size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::MAX_NUM_BITS_RANGE_CONSTRAINT

staticconstexpr

Initial value:

=

253

Definition at line 60 of file ultra_circuit_builder.hpp.

◆ MAX_SMALL_RANGE_CONSTRAINT_VAL

template<typename ExecutionTrace_ >

constexpr size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::MAX_SMALL_RANGE_CONSTRAINT_VAL = (1 << 16) - 1

staticconstexpr

Definition at line 59 of file ultra_circuit_builder.hpp.

◆ memory_read_records

template<typename ExecutionTrace_ >

std::vector<uint32_t> bb::UltraCircuitBuilder_< ExecutionTrace_ >::memory_read_records

Definition at line 208 of file ultra_circuit_builder.hpp.

◆ memory_write_records

template<typename ExecutionTrace_ >

std::vector<uint32_t> bb::UltraCircuitBuilder_< ExecutionTrace_ >::memory_write_records

Definition at line 210 of file ultra_circuit_builder.hpp.

◆ NAME_STRING

template<typename ExecutionTrace_ >

constexpr std::string_view bb::UltraCircuitBuilder_< ExecutionTrace_ >::NAME_STRING = "UltraCircuitBuilder"

staticconstexpr

Definition at line 49 of file ultra_circuit_builder.hpp.

◆ NUM_WIRES

template<typename ExecutionTrace_ >

constexpr size_t bb::UltraCircuitBuilder_< ExecutionTrace_ >::NUM_WIRES = ExecutionTrace::NUM_WIRES

staticconstexpr

Definition at line 47 of file ultra_circuit_builder.hpp.

◆ range_lists

template<typename ExecutionTrace_ >

std::map<uint64_t, RangeList> bb::UltraCircuitBuilder_< ExecutionTrace_ >::range_lists

Definition at line 211 of file ultra_circuit_builder.hpp.

◆ rom_ram_logic

template<typename ExecutionTrace_ >

RomRamLogic bb::UltraCircuitBuilder_< ExecutionTrace_ >::rom_ram_logic

Definition at line 205 of file ultra_circuit_builder.hpp.

◆ used_witnesses

template<typename ExecutionTrace_ >

std::vector<uint32_t> bb::UltraCircuitBuilder_< ExecutionTrace_ >::used_witnesses

private

Definition at line 623 of file ultra_circuit_builder.hpp.

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

src/barretenberg/stdlib/primitives/circuit_builders/circuit_builders_fwd.hpp
src/barretenberg/stdlib_circuit_builders/ultra_circuit_builder.hpp
src/barretenberg/stdlib_circuit_builders/ultra_circuit_builder.cpp

Classes

Public Types

Public Member Functions

Public Attributes

Static Public Attributes

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ add_simple

◆ ExecutionTrace

◆ FF

◆ RomRamLogic

◆ scaled_witness

Member Enumeration Documentation

◆ MEMORY_SELECTORS

◆ NNF_SELECTORS

Constructor & Destructor Documentation

◆ UltraCircuitBuilder_() [1/4]

◆ UltraCircuitBuilder_() [2/4]

◆ UltraCircuitBuilder_() [3/4]

◆ UltraCircuitBuilder_() [4/4]

◆ ~UltraCircuitBuilder_()

Member Function Documentation

◆ add_gates_to_ensure_all_polys_are_non_zero()

◆ apply_memory_selectors()

◆ apply_nnf_selectors()

◆ assert_equal_constant()

◆ assign_tag()

◆ check_selector_length_consistency()

◆ create_add_gate()

◆ create_arithmetic_gate()

◆ create_big_add_gate()

◆ create_big_mul_add_gate()

◆ create_bool_gate()

◆ create_dyadic_range_constraint()

◆ create_ecc_add_gate()

◆ create_ecc_dbl_gate()

◆ create_gates_from_plookup_accumulators()

◆ create_limbed_range_constraint()

◆ create_poseidon2_external_gate()

◆ create_poseidon2_internal_gate()

◆ create_RAM_array()

◆ create_range_list()

◆ create_ROM_array()

◆ create_small_range_constraint()

◆ create_sort_constraint_with_edges()

◆ create_unconstrained_gate()

◆ create_unconstrained_gates()

◆ enforce_small_deltas()

◆ evaluate_non_native_field_addition()

◆ evaluate_non_native_field_multiplication()

◆ evaluate_non_native_field_subtraction()

◆ export_circuit()

◆ finalize_circuit()

◆ fix_witness()

◆ get_finalize_witnesses()

◆ get_finalized_total_circuit_size()

◆ get_lookup_tables() [1/2]

◆ get_lookup_tables() [2/2]

◆ get_multitable()

◆ get_new_tag()

◆ get_num_constant_gates()

◆ get_num_finalized_gates()

◆ get_num_finalized_gates_inefficient()

◆ get_num_lookup_tables()

◆ get_table()

◆ get_tables_size()

◆ get_used_witnesses()

◆ init_RAM_element()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ populate_public_inputs_block()

◆ process_non_native_field_multiplications()

◆ process_range_list()

◆ process_range_lists()

◆ put_constant_variable()

◆ queue_partial_non_native_field_multiplication()

◆ range_constrain_two_limbs()

◆ read_RAM_array()