Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Public Attributes | Static Public Attributes | Private Attributes | List of all members
bb::UltraCircuitBuilder_< ExecutionTrace_ > Class Template Reference

#include <ultra_circuit_builder.hpp>

Inheritance diagram for bb::UltraCircuitBuilder_< ExecutionTrace_ >:
bb::CircuitBuilderBase< ExecutionTrace_::FF >

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_ (const size_t size_hint=0, bool is_write_vk_mode=false)
 
 UltraCircuitBuilder_ (const size_t size_hint, 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_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)
 
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 > 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")
 
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 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)
 
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 (size_t size_hint=0, 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
 

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 527 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 526 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 58 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 68 of file ultra_circuit_builder.hpp.

Constructor & Destructor Documentation

◆ UltraCircuitBuilder_() [1/4]

template<typename ExecutionTrace_ >
bb::UltraCircuitBuilder_< ExecutionTrace_ >::UltraCircuitBuilder_ ( const size_t  size_hint = 0,
bool  is_write_vk_mode = false 
)
inline

Definition at line 214 of file ultra_circuit_builder.hpp.

◆ UltraCircuitBuilder_() [2/4]

template<typename ExecutionTrace_ >
bb::UltraCircuitBuilder_< ExecutionTrace_ >::UltraCircuitBuilder_ ( const size_t  size_hint,
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
size_hint
witness_valueswitnesses values known to acir
public_inputsindices of public inputs in witness array
is_write_vk_modetrue 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 239 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
inStructure 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 992 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_1 q_2 q_3 q_4 q_m
Bigfield Limb Accumulation 1 1 0 0 1 1 0
Bigfield Limb Accumulation 2 1 0 0 1 0 1
Bigfield Product 1 1 0 1 1 0 0
Bigfield Product 2 1 0 1 0 1 0
Bigfield Product 3 1 0 1 0 0 1
Parameters
type

Definition at line 1114 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 397 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 463 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 270 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
inA 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
inStructure 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
inStructure with variable indexes and wire selector values
include_next_gate_w_4Switches 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
inStructure with variable indexes and wire selector values
include_next_gate_w_4Switches 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_indexthe variable which needs to be constrained

Definition at line 315 of file ultra_circuit_builder.cpp.

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

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
idMultiTable identifier specifying which lookup operation to perform
read_valuesPre-computed accumulator values and lookup entries from plookup::get_lookup_accumulators
key_a_indexWitness index for first input; reused in first lookup gate to avoid creating duplicate variables
key_b_indexOptional 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 536 of file ultra_circuit_builder.cpp.

◆ create_new_range_constraint()

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

Definition at line 738 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 1906 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 1925 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_sizeThe size of region in elements
Returns
size_t The index of the element

Definition at line 1803 of file ultra_circuit_builder.cpp.

◆ create_range_constraint()

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

Definition at line 304 of file ultra_circuit_builder.hpp.

◆ create_range_list()

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

Generalized Permutation Methods

Definition at line 589 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_sizeThe size of region in elements
Returns
size_t The index of the element

Definition at line 1788 of file ultra_circuit_builder.cpp.

◆ create_sort_constraint()

template<typename ExecutionTrace >
void bb::UltraCircuitBuilder_< ExecutionTrace >::create_sort_constraint ( const std::vector< uint32_t > &  variable_index)

sort constraints for (batched) range checks.

Definition at line 865 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_index,
const FF &  start,
const FF &  end 
)

Definition at line 915 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
blockExecution trace block into which the dummy gate is to be placed

Definition at line 437 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 896 of file ultra_circuit_builder.cpp.

◆ decompose_into_default_range()

template<typename ExecutionTrace >
std::vector< uint32_t > bb::UltraCircuitBuilder_< ExecutionTrace >::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" 
)

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 }; }

Definition at line 623 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 1537 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 1288 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 1659 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 1946 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:

  1. arithmetic gates: n_computation (includes all computation gates)
  2. rom/memory gates: n_rom
  3. range list gates: n_range
  4. public inputs: n_pub

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

  1. ComposerBase::n => refers to the size of the witness of a given program,
  2. 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_indexThe index of the witness we are fixing
witness_valueThe 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 577 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 390 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 414 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 413 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 498 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 341 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 347 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_nonzeroWhether or not to add gates to ensure all polynomials are non-zero during finalization.
Returns
size_t

Definition at line 361 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 415 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 372 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 576 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_idThe index of the RAM array, which cell we are initializing
index_valueThe index of the cell within the array (an actual index, not a witness index)
value_witnessThe index of the witness with the value that should be in the

Definition at line 1816 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 1454 of file ultra_circuit_builder.cpp.

◆ process_range_list()

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

Definition at line 790 of file ultra_circuit_builder.cpp.

◆ process_range_lists()

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

Definition at line 844 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 1493 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 1193 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 1824 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_idThe index of the array to read from
index_witnessThe witness with the index inside the array
Returns
uint32_t Cell value witness index

Definition at line 1883 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_idThe id of the ROM array
index_witnessThe 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 1896 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_idThe index of the ROM array in which we are initializing a cell
index_valueThe index of the cell within the array/ROM table (an actual index, not a witness index)
value_witnessThe index of the witness with the value that should be in the index_value place in the ROM table.

Definition at line 1853 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_idROM array id
index_valueIndex in the array
value_witnessesThe witnesses to put in the slot

Definition at line 1868 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 481 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.

Parameters
tag_index_1
tag_index_2
Returns
uint32_t

Definition at line 492 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_indicesList 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 619 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_idxWitness 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 610 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_indicesList 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 595 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_idxWitness 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 586 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 1830 of file ultra_circuit_builder.cpp.

Member Data Documentation

◆ blocks

template<typename ExecutionTrace_ >
ExecutionTrace bb::UltraCircuitBuilder_< ExecutionTrace_ >::blocks

Definition at line 190 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 204 of file ultra_circuit_builder.hpp.

◆ circuit_finalized

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

Definition at line 206 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 193 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 573 of file ultra_circuit_builder.hpp.

◆ ipa_proof

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

Definition at line 208 of file ultra_circuit_builder.hpp.

◆ lookup_tables

template<typename ExecutionTrace_ >
std::deque<plookup::BasicTable> bb::UltraCircuitBuilder_< ExecutionTrace_ >::lookup_tables
private

Definition at line 186 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 199 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 201 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 202 of file ultra_circuit_builder.hpp.

◆ rom_ram_logic

template<typename ExecutionTrace_ >
RomRamLogic bb::UltraCircuitBuilder_< ExecutionTrace_ >::rom_ram_logic

Definition at line 196 of file ultra_circuit_builder.hpp.

◆ used_witnesses

template<typename ExecutionTrace_ >
std::vector<uint32_t> bb::UltraCircuitBuilder_< ExecutionTrace_ >::used_witnesses
private

Definition at line 570 of file ultra_circuit_builder.hpp.

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