bb::TranslatorProvingKey Class Reference

#include <translator_proving_key.hpp>

Public Types
using	Flavor = TranslatorFlavor
using	Circuit = typename Flavor::CircuitBuilder
using	FF = typename Flavor::FF
using	BF = typename Flavor::BF
using	ProvingKey = typename Flavor::ProvingKey
using	Polynomial = typename Flavor::Polynomial
using	ProverPolynomials = typename Flavor::ProverPolynomials
using	CommitmentKey = typename Flavor::CommitmentKey

Public Member Functions
	TranslatorProvingKey ()=default
	TranslatorProvingKey (const Circuit &circuit, const CommitmentKey &commitment_key=CommitmentKey())
void	compute_lagrange_polynomials ()
	Set all the precomputed lagrange polynomials used in Translator relations.
void	compute_extra_range_constraint_numerator ()
	Compute the extra numerator for the grand product polynomial.
void	compute_translator_range_constraint_ordered_polynomials ()
	Compute denominator polynomials for Translator's range constraint permutation.
void	compute_interleaved_polynomials ()
	Construct a set of polynomials that are the result of interleaving a group of polynomials into one. Used in translator to reduce the degree of the permutation relation.
void	split_interleaved_random_coefficients_to_ordered ()
	Distribute the randomness from the 4 interleaved polynomials to the 5 ordered range constraints such that commitments and evaluations of ordered polynomials and their shifts are hidden.

Static Public Member Functions
static std::array< size_t, Flavor::SORTED_STEPS_COUNT >	get_sorted_steps ()
	Create the array of steps inserted in each ordered range constraint to ensure they respect the appropriate structure for applying the DeltaRangeConstraint relation.

Public Attributes
std::shared_ptr< ProvingKey >	proving_key
BF	batching_challenge_v = { 0 }
BF	evaluation_input_x = { 0 }

Static Public Attributes
static constexpr size_t	mini_circuit_dyadic_size = Flavor::MINI_CIRCUIT_SIZE
static constexpr size_t	dyadic_circuit_size = mini_circuit_dyadic_size * Flavor::INTERLEAVING_GROUP_SIZE
static constexpr size_t	dyadic_mini_circuit_size_without_masking
static constexpr size_t	dyadic_circuit_size_without_masking

Detailed Description

Definition at line 14 of file translator_proving_key.hpp.

Member Typedef Documentation

BF

using bb::TranslatorProvingKey::BF = typename Flavor::BF

Definition at line 19 of file translator_proving_key.hpp.

Circuit

using bb::TranslatorProvingKey::Circuit = typename Flavor::CircuitBuilder

Definition at line 17 of file translator_proving_key.hpp.

CommitmentKey

using bb::TranslatorProvingKey::CommitmentKey = typename Flavor::CommitmentKey

Definition at line 23 of file translator_proving_key.hpp.

FF

using bb::TranslatorProvingKey::FF = typename Flavor::FF

Definition at line 18 of file translator_proving_key.hpp.

Flavor

using bb::TranslatorProvingKey::Flavor = TranslatorFlavor

Definition at line 16 of file translator_proving_key.hpp.

Polynomial

using bb::TranslatorProvingKey::Polynomial = typename Flavor::Polynomial

Definition at line 21 of file translator_proving_key.hpp.

ProverPolynomials

using bb::TranslatorProvingKey::ProverPolynomials = typename Flavor::ProverPolynomials

Definition at line 22 of file translator_proving_key.hpp.

ProvingKey

using bb::TranslatorProvingKey::ProvingKey = typename Flavor::ProvingKey

Definition at line 20 of file translator_proving_key.hpp.

Constructor & Destructor Documentation

TranslatorProvingKey() [1/2]

bb::TranslatorProvingKey::TranslatorProvingKey ( )

default

TranslatorProvingKey() [2/2]

bb::TranslatorProvingKey::TranslatorProvingKey ( const Circuit &  circuit, const CommitmentKey &  commitment_key = CommitmentKey()  )

inline

Definition at line 45 of file translator_proving_key.hpp.

Member Function Documentation

compute_extra_range_constraint_numerator()

void bb::TranslatorProvingKey::compute_extra_range_constraint_numerator

(

)

Compute the extra numerator for the grand product polynomial.

Goblin proves that several polynomials contain only values in a certain range through 2 relations: 1) A grand product which ignores positions of elements (TranslatorPermutationRelation) 2) A relation enforcing a certain ordering on the elements of given polynomials (TranslatorDeltaRangeConstraintRelation)

We take the values from 4 polynomials (interleaved_range_constraint_), and spread them into 5 polynomials to be sorted (ordered_range_constraint_), adding all the steps from MAX_VALUE to 0 in each ordered range constraint to complete them. The latter polynomials will be in the numerator of the grand product, the former in the numerator. To make up for the added steps in the numerator, an additional polynomial needs to be generated which contains 5 MAX_VALUE, 5 (MAX_VALUE-STEP),... values.

Definition at line 282 of file translator_proving_key.cpp.

compute_interleaved_polynomials()

void bb::TranslatorProvingKey::compute_interleaved_polynomials

(

)

Construct a set of polynomials that are the result of interleaving a group of polynomials into one. Used in translator to reduce the degree of the permutation relation.

Multilinear PCS allow to provide openings for the resulting interleaved polynomials without having to commit to them, using the commitments of polynomials in groups.

If we have: f(x₁, x₂) = {a₁, a₂, a₃, a₄} g(x₁, x₂) = {b₁, b₂, b₃, b₄} then: h(x₁, x₂, x₃) = interleave(f(x₁, x₂), g(x₁, x₂)) = {a₁, b₁, a₂, b₂, a₃, b₃, a₄, b₄}

Since we commit to multilinear polynomials with KZG, which treats evaluations as monomial coefficients, in univariate form h(x)=f(x) + x⋅g(x⁴)

Definition at line 27 of file translator_proving_key.cpp.

compute_lagrange_polynomials()

void bb::TranslatorProvingKey::compute_lagrange_polynomials

(

)

Set all the precomputed lagrange polynomials used in Translator relations.

Definition at line 237 of file translator_proving_key.cpp.

compute_translator_range_constraint_ordered_polynomials()

void bb::TranslatorProvingKey::compute_translator_range_constraint_ordered_polynomials

(

)

Compute denominator polynomials for Translator's range constraint permutation.

We need to prove that all the range constraint wires in the groups indeed have values within the given range [0 , 2¹⁴ -1]. To do this, we use several virtual interleaved wires, each of which represents a subset of the original wires (the virtual wires are interleaved_range_constraints_). We also generate several new polynomials of the same length as the interleaved ones (ordered_range_constraints_ which, as the name suggests, are sorted in non-descending order). To show the interleaved range constraints have values within the appropriate range, we in fact use the ordered range constraints, on which TranslatorFlavor's DeltaRangeConstraint relation operates. The relation ensures that sequential values differ by no more than 3, the last value is the maximum and the first value is zero (zero at the start allows us not to dance around shifts). Then, we run the TranslatorPermutationRelation on interleaved_range_constraint_ and ordered_range_constraint_ to show that they contain the same values which implies that the small wires in the groups are indeed within the correct range.

Ideally, we could simply rearrange the values in interleaved_.._0 ,..., interleaved_.._3 and get 4 denominator polynomials (ordered_constraints), but we could get the worst case scenario: each value in the polynomials is the maximum value. What can we do in that case? We still have to add (max_range/3)+1 values to each of the ordered wires for the sort constraint to hold. So we also need an extra denominator to store k ⋅ ( max_range / 3 + 1 ) values that couldn't go in + ( max_range / 3 + 1 ) connecting values. To counteract the extra ( k + 1 ) ⋅ ⋅ (max_range / 3 + 1 ) values needed for denominator sort constraints we need a polynomial in the numerator. So we can construct a proof when ( k + 1 ) ⋅ ( max_range/ 3 + 1 ) < interleaved size

Definition at line 81 of file translator_proving_key.cpp.

get_sorted_steps()

static std::array< size_t, Flavor::SORTED_STEPS_COUNT > bb::TranslatorProvingKey::get_sorted_steps ( )

inlinestatic

Create the array of steps inserted in each ordered range constraint to ensure they respect the appropriate structure for applying the DeltaRangeConstraint relation.

The delta range relation enforces values of a polynomial are within a certain range ([0, 2¹⁴ - 1] for translator). It achieves this efficiently by sorting the polynomial and checking that the difference between two adjacent values is no more than 3. In the event that the distribution of a polynomial is not uniform across the range (e.g. p_1(x) = {0, 2^14 - 1, 2^14 - 1, 2^14 - 1}), to ensure the relation is still satisfied, we concatenate the set of coefficients to a set of steps that span across the desired range.

Definition at line 109 of file translator_proving_key.hpp.

split_interleaved_random_coefficients_to_ordered()

void bb::TranslatorProvingKey::split_interleaved_random_coefficients_to_ordered

(

)

Distribute the randomness from the 4 interleaved polynomials to the 5 ordered range constraints such that commitments and evaluations of ordered polynomials and their shifts are hidden.

While we don't commit to the interleaved polynomials, ths PCS round connecting the opening of these to the commitments of group polynomials, we have to commit to the ordered polynomials. Since the permutation relation enforces that the values of ordered_* and interleaved_* are the same, we must use the same blinding as for hiding commitments and evaluations of the groups *_range_constraint_* wire polynomials. This methods hence splits the randomness from interleaved to ordered polynomials.

As a result, the ordered_* polynomials withing the range pointed to by lagrange_masking will have some random values and some zeroes. This still maintains the correctness of the permutation relation as we "make up" for the zeroes from the precomputed extra_range_constraint_numerator.

Definition at line 184 of file translator_proving_key.cpp.

Member Data Documentation

batching_challenge_v

BF bb::TranslatorProvingKey::batching_challenge_v = { 0 }

Definition at line 40 of file translator_proving_key.hpp.

dyadic_circuit_size

constexpr size_t bb::TranslatorProvingKey::dyadic_circuit_size = mini_circuit_dyadic_size * Flavor::INTERLEAVING_GROUP_SIZE

staticconstexpr

Definition at line 28 of file translator_proving_key.hpp.

dyadic_circuit_size_without_masking

constexpr size_t bb::TranslatorProvingKey::dyadic_circuit_size_without_masking

staticconstexpr

Initial value:

=
        dyadic_circuit_size - NUM_DISABLED_ROWS_IN_SUMCHECK * Flavor::INTERLEAVING_GROUP_SIZE

Definition at line 35 of file translator_proving_key.hpp.

dyadic_mini_circuit_size_without_masking

constexpr size_t bb::TranslatorProvingKey::dyadic_mini_circuit_size_without_masking

staticconstexpr

Initial value:

=
        mini_circuit_dyadic_size - NUM_DISABLED_ROWS_IN_SUMCHECK

Definition at line 33 of file translator_proving_key.hpp.

evaluation_input_x

BF bb::TranslatorProvingKey::evaluation_input_x = { 0 }

Definition at line 41 of file translator_proving_key.hpp.

mini_circuit_dyadic_size

constexpr size_t bb::TranslatorProvingKey::mini_circuit_dyadic_size = Flavor::MINI_CIRCUIT_SIZE

staticconstexpr

Definition at line 25 of file translator_proving_key.hpp.

proving_key

std::shared_ptr<ProvingKey> bb::TranslatorProvingKey::proving_key

Definition at line 38 of file translator_proving_key.hpp.

---

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

• src/barretenberg/translator_vm/translator_proving_key.hpp
• src/barretenberg/translator_vm/translator_proving_key.cpp