GoblinTranslatorCircuitBuilder creates a circuit that evaluates the correctness of the evaluation of EccOpQueue in Fq while operating in the Fr scalar field (r is the modulus of Fr and p is the modulus of Fp) More...

#include <goblin_translator_circuit_builder.hpp>

Inheritance diagram for proof_system::GoblinTranslatorCircuitBuilder:

Classes
struct	AccumulationInput
	The accumulation input structure contains all the necessary values to initalize an accumulation gate as well as additional values for checking its correctness. More...

struct	RelationInputs

Public Types
enum	WireIds : size_t { OP , X_LOW_Y_HI , X_HIGH_Z_1 , Y_LOW_Z_2 , P_X_LOW_LIMBS , P_X_LOW_LIMBS_RANGE_CONSTRAINT_0 , P_X_LOW_LIMBS_RANGE_CONSTRAINT_1 , P_X_LOW_LIMBS_RANGE_CONSTRAINT_2 , P_X_LOW_LIMBS_RANGE_CONSTRAINT_3 , P_X_LOW_LIMBS_RANGE_CONSTRAINT_4 , P_X_LOW_LIMBS_RANGE_CONSTRAINT_TAIL , P_X_HIGH_LIMBS , P_X_HIGH_LIMBS_RANGE_CONSTRAINT_0 , P_X_HIGH_LIMBS_RANGE_CONSTRAINT_1 , P_X_HIGH_LIMBS_RANGE_CONSTRAINT_2 , P_X_HIGH_LIMBS_RANGE_CONSTRAINT_3 , P_X_HIGH_LIMBS_RANGE_CONSTRAINT_4 , P_X_HIGH_LIMBS_RANGE_CONSTRAINT_TAIL , P_Y_LOW_LIMBS , P_Y_LOW_LIMBS_RANGE_CONSTRAINT_0 , P_Y_LOW_LIMBS_RANGE_CONSTRAINT_1 , P_Y_LOW_LIMBS_RANGE_CONSTRAINT_2 , P_Y_LOW_LIMBS_RANGE_CONSTRAINT_3 , P_Y_LOW_LIMBS_RANGE_CONSTRAINT_4 , P_Y_LOW_LIMBS_RANGE_CONSTRAINT_TAIL , P_Y_HIGH_LIMBS , P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_0 , P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_1 , P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_2 , P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_3 , P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_4 , P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_TAIL , Z_LOW_LIMBS , Z_LOW_LIMBS_RANGE_CONSTRAINT_0 , Z_LOW_LIMBS_RANGE_CONSTRAINT_1 , Z_LOW_LIMBS_RANGE_CONSTRAINT_2 , Z_LOW_LIMBS_RANGE_CONSTRAINT_3 , Z_LOW_LIMBS_RANGE_CONSTRAINT_4 , Z_LOW_LIMBS_RANGE_CONSTRAINT_TAIL , Z_HIGH_LIMBS , Z_HIGH_LIMBS_RANGE_CONSTRAINT_0 , Z_HIGH_LIMBS_RANGE_CONSTRAINT_1 , Z_HIGH_LIMBS_RANGE_CONSTRAINT_2 , Z_HIGH_LIMBS_RANGE_CONSTRAINT_3 , Z_HIGH_LIMBS_RANGE_CONSTRAINT_4 , Z_HIGH_LIMBS_RANGE_CONSTRAINT_TAIL , ACCUMULATORS_BINARY_LIMBS_0 , ACCUMULATORS_BINARY_LIMBS_1 , ACCUMULATORS_BINARY_LIMBS_2 , ACCUMULATORS_BINARY_LIMBS_3 , ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_0 , ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_1 , ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_2 , ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_3 , ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_4 , ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_TAIL , ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_0 , ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_1 , ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_2 , ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_3 , ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_4 , ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_TAIL , QUOTIENT_LOW_BINARY_LIMBS , QUOTIENT_HIGH_BINARY_LIMBS , QUOTIENT_LOW_LIMBS_RANGE_CONSTRAIN_0 , QUOTIENT_LOW_LIMBS_RANGE_CONSTRAIN_1 , QUOTIENT_LOW_LIMBS_RANGE_CONSTRAIN_2 , QUOTIENT_LOW_LIMBS_RANGE_CONSTRAIN_3 , QUOTIENT_LOW_LIMBS_RANGE_CONSTRAIN_4 , QUOTIENT_LOW_LIMBS_RANGE_CONSTRAIN_TAIL , QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAIN_0 , QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAIN_1 , QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAIN_2 , QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAIN_3 , QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAIN_4 , QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAIN_TAIL , RELATION_WIDE_LIMBS , RELATION_WIDE_LIMBS_RANGE_CONSTRAINT_0 , RELATION_WIDE_LIMBS_RANGE_CONSTRAINT_1 , RELATION_WIDE_LIMBS_RANGE_CONSTRAINT_2 , RELATION_WIDE_LIMBS_RANGE_CONSTRAINT_3 , TOTAL_COUNT }
	There are so many wires that naming them has no sense, it is easier to access them with enums.

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

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

Public Member Functions
void	create_add_gate (const add_triple_< Fr > &) override

void	create_mul_gate (const mul_triple_< Fr > &) override

void	create_bool_gate (const uint32_t) override

void	create_poly_gate (const poly_triple_< Fr > &) override

size_t	get_num_constant_gates () const override

	GoblinTranslatorCircuitBuilder (Fq batching_challenge_v_, Fq evaluation_input_x_)
	Construct a new Goblin Translator Circuit Builder object.

	GoblinTranslatorCircuitBuilder (Fq batching_challenge_v_, Fq evaluation_input_x_, std::shared_ptr< ECCOpQueue > op_queue)
	Construct a new Goblin Translator Circuit Builder object and feed op_queue inside.

	GoblinTranslatorCircuitBuilder (const GoblinTranslatorCircuitBuilder &other)=delete

	GoblinTranslatorCircuitBuilder (GoblinTranslatorCircuitBuilder &&other) noexcept

GoblinTranslatorCircuitBuilder &	operator= (const GoblinTranslatorCircuitBuilder &other)=delete

GoblinTranslatorCircuitBuilder &	operator= (GoblinTranslatorCircuitBuilder &&other) noexcept

void	create_accumulation_gate (AccumulationInput acc_step)
	Create a single accumulation gate.

barretenberg::fq	get_computation_result ()
	Get the result of accumulation.

void	feed_ecc_op_queue_into_circuit (std::shared_ptr< ECCOpQueue > ecc_op_queue)
	Generate all the gates required to prove the correctness of batched evalution of polynomials representing commitments to ECCOpQueue.

bool	check_circuit ()
	Check the witness satisifies the circuit.

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

	CircuitBuilderBase (const CircuitBuilderBase &other)=default

	CircuitBuilderBase (CircuitBuilderBase &&other) noexcept=default

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

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

virtual size_t	get_num_gates () const

virtual void	print_num_gates () const

virtual size_t	get_num_variables () const

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

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

virtual void	create_bool_gate (const uint32_t a)=0

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

virtual size_t	get_num_constant_gates () const=0

uint32_t	get_first_variable_in_class (uint32_t index) const

void	update_real_variable_indices (uint32_t index, uint32_t new_real_index)

FF	get_variable (const uint32_t index) const

const FF &	get_variable_reference (const uint32_t index) const

uint32_t	get_public_input_index (const uint32_t witness_index) const

FF	get_public_input (const uint32_t index) const

std::vector< FF >	get_public_inputs () const

virtual uint32_t	add_variable (const FF &in)

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

virtual void	update_variable_names (uint32_t index)

virtual void	finalize_variable_names ()

virtual msgpack::sbuffer	export_circuit ()

virtual uint32_t	add_public_variable (const FF &in)

virtual void	set_public_input (const uint32_t witness_index)

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

size_t	get_circuit_subgroup_size (const size_t num_gates) const

size_t	get_num_public_inputs () const

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

bool	is_valid_variable (uint32_t variable_index)

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

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

bool	failed () const

const std::string &	err () const

void	set_err (std::string msg)

void	failure (std::string msg)

Static Public Member Functions
static RelationInputs	compute_relation_inputs_limbs (Fq batching_challenge_v, Fq evaluation_input_x)
	Create limb representations of x and powers of v that are needed to compute the witness or check circuit correctness.

Public Attributes
Fq	batching_challenge_v

Fq	evaluation_input_x

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

Public Attributes inherited from proof_system::CircuitBuilderBase< barretenberg::fr >
size_t	num_gates

std::vector< uint32_t >	public_inputs

std::vector< FF >	variables

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

std::vector< uint32_t >	next_var_index

std::vector< uint32_t >	prev_var_index

std::vector< uint32_t >	real_variable_index

std::vector< uint32_t >	real_variable_tags

uint32_t	current_tag

std::map< uint32_t, uint32_t >	tau

std::vector< uint32_t >	recursive_proof_public_input_indices

bool	contains_recursive_proof

bool	_failed

std::string	_err

uint32_t	zero_idx

uint32_t	one_idx

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

static constexpr size_t	DEFAULT_TRANSLATOR_VM_LENGTH = 2048

static constexpr size_t	NUM_LIMB_BITS = 68

static constexpr size_t	NUM_LAST_LIMB_BITS = Fq::modulus.get_msb() + 1 - 3 * NUM_LIMB_BITS

static constexpr size_t	NUM_Z_LIMBS = 2

static constexpr size_t	NUM_QUOTIENT_BITS = 256

static constexpr size_t	NUM_LAST_QUOTIENT_LIMB_BITS = 256 - 3 * NUM_LIMB_BITS

static constexpr size_t	NUM_Z_BITS = 128

static constexpr size_t	MICRO_LIMB_BITS = 14

static constexpr auto	MAX_MICRO_LIMB_SIZE = (uint256_t(1) << MICRO_LIMB_BITS) - 1

static constexpr size_t	NUM_MICRO_LIMBS = 6

static constexpr size_t	NUM_BINARY_LIMBS = 4

static constexpr size_t	NUM_RELATION_WIDE_LIMBS = 2

static constexpr size_t	RELATION_WIDE_LIMB_BITS = 84

static constexpr uint256_t	MAX_RELATION_WIDE_LIMB_SIZE = uint256_t(1) << RELATION_WIDE_LIMB_BITS

static constexpr auto	MICRO_SHIFT = uint256_t(1) << MICRO_LIMB_BITS

static constexpr auto	MAX_LOW_WIDE_LIMB_SIZE = (uint256_t(1) << (NUM_LIMB_BITS * 2)) - 1

static constexpr auto	MAX_HIGH_WIDE_LIMB_SIZE = (uint256_t(1) << (NUM_LIMB_BITS + NUM_LAST_LIMB_BITS)) - 1

static constexpr auto	SHIFT_1 = uint256_t(1) << NUM_LIMB_BITS

static constexpr auto	SHIFT_2 = uint256_t(1) << (NUM_LIMB_BITS << 1)

static constexpr auto	SHIFT_2_INVERSE = Fr(SHIFT_2).invert()

static constexpr auto	SHIFT_3 = uint256_t(1) << (NUM_LIMB_BITS * 3)

static constexpr uint512_t	MODULUS_U512 = uint512_t(Fq::modulus)

static constexpr uint512_t	BINARY_BASIS_MODULUS = uint512_t(1) << (NUM_LIMB_BITS << 2)

static constexpr uint512_t	NEGATIVE_PRIME_MODULUS = BINARY_BASIS_MODULUS - MODULUS_U512

static constexpr std::array< Fr, 5 >	NEGATIVE_MODULUS_LIMBS

static constexpr std::string_view	NAME_STRING = "GoblinTranslatorArithmetization"

Static Public Attributes inherited from proof_system::CircuitBuilderBase< barretenberg::fr >
static constexpr uint32_t	REAL_VARIABLE

static constexpr uint32_t	FIRST_VARIABLE_IN_CLASS

Detailed Description

GoblinTranslatorCircuitBuilder creates a circuit that evaluates the correctness of the evaluation of EccOpQueue in Fq while operating in the Fr scalar field (r is the modulus of Fr and p is the modulus of Fp)

Goblin Translator Circuit Builder builds a circuit the purpose of which is to calculate the batched evaluation of 5 polynomials in non-native field represented through coefficients in 4 native polynomials (op, x_lo_y_hi, x_hi_z_1, y_lo_z_2):

OP | X_LO | X_HI | Y_LO 0 | Y_HI | Z1 | Z2

OP is supposed to be { 0, 1, 2, 3, 4, 8 }. X_LO and Y_LO need to be < 2¹³⁶, X_HI and Y_LO < 2¹¹⁸, Z1 and Z2 < 2¹²⁸. X_* and Y_* are supposed to be the decompositions of bn254 base fields elements P.x and P.y and are split into two chunks each because the scalar field we are operating on can't fit them

Goblin Translator calculates the result of evaluation of a polynomial op + P.x⋅v +P.y⋅v² + z1 ⋅ v³ + z2⋅v⁴ at the given challenge x (evaluation_input_x). For this it uses logic similar to the stdlib bigfield class. We operate in Fr while trying to calculate values in Fq. To show that a⋅b=c mod p, we: 1) Compute a⋅b in integers 2) Compute quotient=a⋅b/p 3) Show that a⋅b - quotient⋅p - c = 0 mod 2²⁷² 4) Show that a⋅b - quotient⋅p - c = 0 mod r (scalar field modulus) This ensures that the logic is sound modulo 2²⁷²⋅r, which means it's correct in integers, if all the values are sufficiently constrained (there is no way to undeflow or overflow)

Concretely, Goblin Translator computes one accumulation every two gates: previous_accumulator⋅x + op + P.x⋅v +P.y⋅v² + z1⋅v³ + z2⋅v⁴ = current_accumulator mod p. Because of the nature of polynomial commitment, previous_accumulator is located at higher index than the current_accumulator. Values of x (evaluation_input_x) and v (batching_challenge_v) are precomputed and considered inputs to the relations.

P.x and P.y are deconstructed into 4 limbs (3 68-bit and 1 50-bit) for non-native arithmetic z1 and z2 are deconstructed into 2 limbs each (68 and 60 bits) op is small and doesn't have to be deconstructed

To show the accumulation is correct we also need to provide the quotient and accumulators as witnesses. Accumulator is split the same way as P.x and P.y, but quotient is 256 bits,so the top limb is 52 bits.

Ensuring that the relation mod 2²⁷² is correct is done through splitting this check into two checks modulo 2¹³⁶. First, we check that a proper combination of the values in the lower limbs gives the correct result modulo 2¹³⁶ (by dividing the result by 2¹³⁶ and range constraining it). Then we use the overlow and higher limbs to prove the same modulo 2¹³⁶ again and as a result we get correctness modulo 2²⁷².

One big issue are range constraints. In Goblin Translator we check ranges by decomposing LIMBS into special other range constrained MICROLIMBS (have "_CONSTRAINT_" in the name of their wires). These wires always have the range of 14 bits, so when we need to constrain something further we use two wires at once and scale the values (for example, 68 bits are decomposed into 5 14-bit limbs + 1 shifted limb, which is equal to the highest microlimb multiplied by 4). The shifted wires usually have "_TAIL" in the name, but that is not a strict rule. To save space and because of the proving system requirements we put some of the decomposed values from relation limbs (limbs which compute the result of computation modulo 2²⁷² divided by shifts) into constraint wires named after P.x, P.y, accumulator and quotient. This is due to the fact that the highest limb in these four is less than 56 bits, which frees up an extra microlimb.

Constructor & Destructor Documentation

◆ GoblinTranslatorCircuitBuilder() [1/2]

proof_system::GoblinTranslatorCircuitBuilder::GoblinTranslatorCircuitBuilder	(	Fq	batching_challenge_v_,
		Fq	evaluation_input_x_
	)

inline

Construct a new Goblin Translator Circuit Builder object.

Goblin Translator Circuit builder has to be initializaed with evaluation input and batching challenge (they are used to compute witness and to store the value for the prover)

Parameters

batching_challenge_v_
evaluation_input_x_

◆ GoblinTranslatorCircuitBuilder() [2/2]

proof_system::GoblinTranslatorCircuitBuilder::GoblinTranslatorCircuitBuilder	(	Fq	batching_challenge_v_,
		Fq	evaluation_input_x_,
		std::shared_ptr< ECCOpQueue >	op_queue
	)

inline

Construct a new Goblin Translator Circuit Builder object and feed op_queue inside.

Goblin Translator Circuit builder has to be initialized with evaluation input and batching challenge (they are used to compute witness and to store the value for the prover)

Parameters

batching_challenge_v_
evaluation_input_x_
op_queue

Member Function Documentation

◆ check_circuit()

bool proof_system::GoblinTranslatorCircuitBuilder::check_circuit ( )

Check the witness satisifies the circuit.

Goes through each gate and checks the correctness of accumulation

Returns: true; false

Get elements at the same index from several sequential wires and put them into a vector

Reconstruct the value of one regular limb used in relation computation from micro chunks used to create range constraints

We might ant to skip several items at the end, since those will be shifted or used for another decomposition

Go through each gate

◆ compute_relation_inputs_limbs()

static RelationInputs proof_system::GoblinTranslatorCircuitBuilder::compute_relation_inputs_limbs	(	Fq	batching_challenge_v,
		Fq	evaluation_input_x
	)

inlinestatic

Create limb representations of x and powers of v that are needed to compute the witness or check circuit correctness.

Parameters

evaluation_input_x	The point at which the polynomials are being evaluated
batching_challenge_v	The batching challenge

Returns: RelationInputs

A small function to transform a native element Fq into its bigfield representation in Fr scalars

◆ create_accumulation_gate()

void proof_system::GoblinTranslatorCircuitBuilder::create_accumulation_gate ( AccumulationInput acc_step )

Create a single accumulation gate.

An accumulation gate adds 2 rows from the op queue computing the accumulation of a single EccOpQueue step

Parameters

acc_step

Parameters

acc_step

Insert two values into the same wire sequentially

Check correctness of limbs values

Check correctness of values for range constraint limbs

Put several values in sequential wires

◆ create_add_gate()

void proof_system::GoblinTranslatorCircuitBuilder::create_add_gate ( const add_triple_< Fr > & )

inlineoverridevirtual

We won't need these standard gates that are defined as virtual in circuit builder base

Implements proof_system::CircuitBuilderBase< barretenberg::fr >.

◆ create_bool_gate()

void proof_system::GoblinTranslatorCircuitBuilder::create_bool_gate ( const uint32_t )

inlineoverridevirtual

Implements proof_system::CircuitBuilderBase< barretenberg::fr >.

◆ create_mul_gate()

void proof_system::GoblinTranslatorCircuitBuilder::create_mul_gate ( const mul_triple_< Fr > & )

inlineoverridevirtual

Implements proof_system::CircuitBuilderBase< barretenberg::fr >.

◆ create_poly_gate()

void proof_system::GoblinTranslatorCircuitBuilder::create_poly_gate ( const poly_triple_< Fr > & )

inlineoverridevirtual

Implements proof_system::CircuitBuilderBase< barretenberg::fr >.

◆ feed_ecc_op_queue_into_circuit()

void proof_system::GoblinTranslatorCircuitBuilder::feed_ecc_op_queue_into_circuit ( std::shared_ptr< ECCOpQueue > ecc_op_queue )

Generate all the gates required to prove the correctness of batched evalution of polynomials representing commitments to ECCOpQueue.

Parameters

ecc_op_queue The queue

◆ get_computation_result()

barretenberg::fq proof_system::GoblinTranslatorCircuitBuilder::get_computation_result ( )

inline

Get the result of accumulation.

Returns: barretenberg::fq

◆ get_num_constant_gates()

size_t proof_system::GoblinTranslatorCircuitBuilder::get_num_constant_gates ( ) const

inlineoverridevirtual

Implements proof_system::CircuitBuilderBase< barretenberg::fr >.

Member Data Documentation

◆ NEGATIVE_MODULUS_LIMBS

constexpr std::array<Fr, 5> proof_system::GoblinTranslatorCircuitBuilder::NEGATIVE_MODULUS_LIMBS

staticconstexpr

Initial value:

= {
        Fr(NEGATIVE_PRIME_MODULUS.slice(0, NUM_LIMB_BITS).lo),
        Fr(NEGATIVE_PRIME_MODULUS.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2).lo),
        Fr(NEGATIVE_PRIME_MODULUS.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3).lo),
        Fr(NEGATIVE_PRIME_MODULUS.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4).lo),
        -Fr(Fq::modulus)
    }

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

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ GoblinTranslatorCircuitBuilder() [1/2]

◆ GoblinTranslatorCircuitBuilder() [2/2]

Member Function Documentation

◆ check_circuit()

◆ compute_relation_inputs_limbs()

◆ create_accumulation_gate()

◆ create_add_gate()

◆ create_bool_gate()

◆ create_mul_gate()

◆ create_poly_gate()

◆ feed_ecc_op_queue_into_circuit()

◆ get_computation_result()

◆ get_num_constant_gates()

Member Data Documentation

◆ NEGATIVE_MODULUS_LIMBS