Classes
struct	BasicPlonkKeyAndTranscript

struct	commitment_open_proof

class	CommitmentScheme

class	KateCommitmentScheme

struct	permutation_subgroup_element

struct	PolynomialDescriptor

class	PolynomialManifest

class	PrecomputedPolyList

struct	proof

class	ProverBase

class	ProverPermutationWidget

class	ProverPlookupWidget

class	ProverRandomWidget

struct	proving_key

struct	proving_key_data

struct	SelectorProperties

class	settings_base

class	standard_settings

class	standard_verifier_settings

class	StandardComposer

class	ultra_settings

class	ultra_to_standard_settings

class	ultra_to_standard_verifier_settings

class	ultra_verifier_settings

class	ultra_with_keccak_settings

class	ultra_with_keccak_verifier_settings

class	UltraComposer

struct	verification_key

struct	verification_key_data

class	VerifierBase

class	VerifierPermutationWidget

class	VerifierPlookupWidget

class	work_queue

Typedefs
typedef ProverBase< standard_settings >	Prover

typedef ProverBase< ultra_settings >	UltraProver

typedef ProverBase< ultra_to_standard_settings >	UltraToStandardProver

typedef ProverBase< ultra_with_keccak_settings >	UltraWithKeccakProver

typedef VerifierBase< standard_verifier_settings >	Verifier

typedef VerifierBase< ultra_verifier_settings >	UltraVerifier

typedef VerifierBase< ultra_to_standard_verifier_settings >	UltraToStandardVerifier

typedef VerifierBase< ultra_with_keccak_verifier_settings >	UltraWithKeccakVerifier

template<typename Settings >
using	ProverArithmeticWidget = widget::TransitionWidget< barretenberg::fr, Settings, widget::ArithmeticKernel >
	Standard plonk arithmetic widget for the prover. Provides standard plonk gate transition.

template<typename Field , typename Group , typename Transcript , typename Settings >
using	VerifierArithmeticWidget = widget::GenericVerifierWidget< Field, Transcript, Settings, widget::ArithmeticKernel >
	Standard plonk arithmetic widget for the verifier. Provides standard plonk gate transition.

template<typename Settings >
using	ProverEllipticWidget = widget::TransitionWidget< barretenberg::fr, Settings, widget::EllipticKernel >

template<typename Field , typename Group , typename Transcript , typename Settings >
using	VerifierEllipticWidget = widget::GenericVerifierWidget< Field, Transcript, Settings, widget::EllipticKernel >

template<typename Settings >
using	ProverGenPermSortWidget = widget::TransitionWidget< barretenberg::fr, Settings, widget::GenPermSortKernel >

template<typename Field , typename Group , typename Transcript , typename Settings >
using	VerifierGenPermSortWidget = widget::GenericVerifierWidget< Field, Transcript, Settings, widget::GenPermSortKernel >

template<typename Settings >
using	ProverPlookupArithmeticWidget = widget::TransitionWidget< barretenberg::fr, Settings, widget::PlookupArithmeticKernel >
	Ultra plonk arithmetic widget for the prover. It's quite complex, so for details better look at the kernel class description.

template<typename Field , typename Group , typename Transcript , typename Settings >
using	VerifierPlookupArithmeticWidget = widget::GenericVerifierWidget< Field, Transcript, Settings, widget::PlookupArithmeticKernel >
	Ultra plonk arithmetic widget for the verifier. It's quite complex, so for details better look at the kernel class description.

template<typename Settings >
using	ProverPlookupAuxiliaryWidget = widget::TransitionWidget< barretenberg::fr, Settings, widget::PlookupAuxiliaryKernel >

template<typename Field , typename Group , typename Transcript , typename Settings >
using	VerifierPlookupAuxiliaryWidget = widget::GenericVerifierWidget< Field, Transcript, Settings, widget::PlookupAuxiliaryKernel >

Enumerations
enum	PolynomialSource { WITNESS , SELECTOR , PERMUTATION , OTHER }

enum	EvaluationType { NON_SHIFTED , SHIFTED }

enum	PolynomialIndex { Q_1 , Q_2 , Q_3 , Q_4 , Q_5 , Q_M , Q_C , Q_ARITHMETIC , Q_FIXED_BASE , Q_RANGE , Q_SORT , TABLE_1 , TABLE_2 , TABLE_3 , TABLE_4 , TABLE_INDEX , TABLE_TYPE , Q_ELLIPTIC , Q_AUX , SIGMA_1 , SIGMA_2 , SIGMA_3 , SIGMA_4 , ID_1 , ID_2 , ID_3 , ID_4 , W_1 , W_2 , W_3 , W_4 , S , Z , Z_LOOKUP , LAGRANGE_FIRST , LAGRANGE_LAST , MAX_NUM_POLYNOMIALS }

Functions
BasicPlonkKeyAndTranscript	get_plonk_key_and_transcript ()

template<typename Flavor , typename Widget >
void	execute_widget (::benchmark::State &state)

void	plookup_auxiliary_kernel (::benchmark::State &state) noexcept

	BENCHMARK (plookup_auxiliary_kernel)

void	plookup_auxiliary_widget (::benchmark::State &state) noexcept

	BENCHMARK (plookup_auxiliary_widget)

void	compute_monomial_and_coset_selector_forms (plonk::proving_key *circuit_proving_key, std::vector< SelectorProperties > selector_properties)
	Retrieve lagrange forms of selector polynomials and compute monomial and coset-monomial forms and put into cache.

std::shared_ptr< plonk::verification_key >	compute_verification_key_common (std::shared_ptr< plonk::proving_key > const &proving_key, std::shared_ptr< barretenberg::srs::factories::VerifierCrs< curve::BN254 > > const &vrs)
	Computes the verification key by computing the: (1) commitments to the selector, permutation, and lagrange (first/last) polynomials, (2) sets the polynomial manifest using the data from proving key.

std::shared_ptr< plonk::proving_key >	initialize_proving_key (const auto &circuit_constructor, barretenberg::srs::factories::CrsFactory< curve::BN254 > *crs_factory, const size_t minimum_circuit_size, const size_t num_randomized_gates, CircuitType circuit_type)
	Initilalize proving key and load the crs.

void	enforce_nonzero_selector_polynomials (const auto &circuit_constructor, auto *proving_key)
	Fill the last index of each selector polynomial in lagrange form with a non-zero value.

template<typename B >
void	read (B &any, proving_key_data &key)

template<typename B >
void	write (B &buf, proving_key const &key)

template<typename B >
void	read_from_file (B &is, std::string const &path, proving_key_data &key)

template<typename B >
void	write_to_file (B &os, std::string const &path, proving_key &key)

template<typename Field >
Field	compute_public_input_delta (const std::vector< Field > &inputs, const Field &beta, const Field &gamma, const Field &subgroup_generator)

void	read (uint8_t const *&it, proof &data)

template<typename B >
void	write (B &buf, proof const &data)

std::ostream &	operator<< (std::ostream &os, proof const &data)

template<typename program_settings >
void	compute_gen_permutation_lagrange_base_single (barretenberg::polynomial &output, const std::vector< uint32_t > &permutation, const barretenberg::evaluation_domain &small_domain)

template<typename Field , typename Transcript , typename program_settings >
Field	compute_kate_batch_evaluation (typename Transcript::Key *key, const Transcript &transcript)

template<typename Field , typename Group , typename Transcript , typename program_settings >
void	populate_kate_element_map (verification_key *key, const Transcript &transcript, std::map< std::string, Group > &kate_g1_elements, std::map< std::string, Field > &kate_fr_elements)

template<typename program_settings >
void	compute_permutation_lagrange_base_single (barretenberg::polynomial &output, const std::vector< uint32_t > &permutation, const barretenberg::evaluation_domain &small_domain)

template<typename program_settings >
void	compute_permutation_lagrange_base_single (barretenberg::polynomial &output, const std::vector< permutation_subgroup_element > &permutation, const barretenberg::evaluation_domain &small_domain)

barretenberg::fr	hash_native_evaluation_domain (barretenberg::evaluation_domain const &domain)
	Hashes the evaluation domain to match the 'circuit' approach taken in stdlib/recursion/verification_key/verification_key.hpp.

std::ostream &	operator<< (std::ostream &os, verification_key_data const &key)

bool	operator== (verification_key_data const &lhs, verification_key_data const &rhs)

template<typename B >
void	read (B &buf, verification_key &key)

template<typename B >
void	read (B &buf, std::shared_ptr< verification_key > &key)

template<typename B >
void	write (B &buf, verification_key const &key)

std::ostream &	operator<< (std::ostream &os, verification_key const &key)

Detailed Description

Optimizations:

use lookup tables for basic XOR operations
replace use of uint32 with basic field_t type

Special case function for performing BN254 group operations

TODO: we should try to genericize this, but this method is super fiddly and we need it to be efficient!

We use a special case algorithm to split bn254 scalar multipliers into endomorphism scalars

Special case function for performing secp256k1 ecdsa signature verification group operations

TODO: we should try to genericize this, but this method is super fiddly and we need it to be efficient!

Typedef Documentation

◆ ProverArithmeticWidget

template<typename Settings >

using proof_system::plonk::ProverArithmeticWidget = typedef widget::TransitionWidget<barretenberg::fr, Settings, widget::ArithmeticKernel>

Standard plonk arithmetic widget for the prover. Provides standard plonk gate transition.

ArithmethicKernel provides the logic that implements the standard arithmetic transition q_m * w_1 * w_2 + q_1 * w_1 + q_2 * w_2 + q_3 * w_3 + q_c=0

Template Parameters

Settings

◆ ProverPlookupArithmeticWidget

template<typename Settings >

using proof_system::plonk::ProverPlookupArithmeticWidget = typedef widget::TransitionWidget<barretenberg::fr, Settings, widget::PlookupArithmeticKernel>

Ultra plonk arithmetic widget for the prover. It's quite complex, so for details better look at the kernel class description.

Template Parameters

Settings

◆ VerifierArithmeticWidget

template<typename Field , typename Group , typename Transcript , typename Settings >

using proof_system::plonk::VerifierArithmeticWidget = typedef widget::GenericVerifierWidget<Field, Transcript, Settings, widget::ArithmeticKernel>

Standard plonk arithmetic widget for the verifier. Provides standard plonk gate transition.

ArithmethicKernel provides the logic that implements the standard arithmetic transition q_m * w_1 * w_2 + q_1 * w_1 + q_2 * w_2 + q_3 * w_3 + q_c=0

Template Parameters

Settings

◆ VerifierPlookupArithmeticWidget

template<typename Field , typename Group , typename Transcript , typename Settings >

using proof_system::plonk::VerifierPlookupArithmeticWidget = typedef widget::GenericVerifierWidget<Field, Transcript, Settings, widget::PlookupArithmeticKernel>

Ultra plonk arithmetic widget for the verifier. It's quite complex, so for details better look at the kernel class description.

Template Parameters

Settings

Function Documentation

◆ compute_monomial_and_coset_selector_forms()

void proof_system::plonk::compute_monomial_and_coset_selector_forms	(	plonk::proving_key *	circuit_proving_key,
		std::vector< SelectorProperties >	selector_properties
	)

Retrieve lagrange forms of selector polynomials and compute monomial and coset-monomial forms and put into cache.

Parameters

key	Pointer to the proving key
selector_properties	Names of selectors

Parameters

key	Pointer to the proving key TODO(#293)
selector_properties	Names of selectors

◆ compute_permutation_lagrange_base_single() [1/2]

template<typename program_settings >

void proof_system::plonk::compute_permutation_lagrange_base_single	(	barretenberg::polynomial &	output,
		const std::vector< permutation_subgroup_element > &	permutation,
		const barretenberg::evaluation_domain &	small_domain
	)

inline

Compute sigma permutation polynomial in lagrange base

Parameters

output	Output polynomial.
permuataion	Input permutation.
small_domain	The domain we base our polynomial in.

Template Parameters

program_settings Program settings.

◆ compute_permutation_lagrange_base_single() [2/2]

template<typename program_settings >

void proof_system::plonk::compute_permutation_lagrange_base_single	(	barretenberg::polynomial &	output,
		const std::vector< uint32_t > &	permutation,
		const barretenberg::evaluation_domain &	small_domain
	)

inline

TODO: Remove need for this. We have a lot of old tests that use a vector of uint32s instead of permutation_subgroup_element

◆ compute_public_input_delta()

template<typename Field >

Field proof_system::plonk::compute_public_input_delta	(	const std::vector< Field > &	public_inputs,
		const Field &	beta,
		const Field &	gamma,
		const Field &	subgroup_generator
	)

Public inputs!

This is a linear-time method of evaluating public inputs, that doesn't require modifications to any pre-processed selector polynomials.

We validate public inputs by using a transition constraint to force every public input's copy permutation to be unbalanced. We then directly compute the 'delta' factor required to re-balance the permutation, and add it back into the grand product.

Ok, let's wind back to the start. Let's say we have 'm' public inputs.

We reserve the first 'm' rows of program memory for public input validation. For each of these constraints, we force the first column's cell to be zero, using a standard arithmetic gate (i.e. w_l[i] = 0 for the first i rows).

We then apply a copy constraint between the first two columns in program memory. I.e. for each row, the second cell is a copy of the first, as in w_l[i] = w_r[i].

We then apply a copy constraint that maps the second cell to whererever the public input in question is required.

This creates an unbalanced permutation:

For the arithmetic constraint to be valid, the first cell must be 0.
But for the copy permutation to be valid, the first cell must be our public input!

We make a further modification to the copy permutation argument. For the forced-zero cells, the correct permutation term for sigma_1(g_i) would be k.g_i , where k is a coset generator that maps to the second column.

However the actual permutation term for sigma_1(g_i) is just g_i.

This makes the permutation product, for the targeted zero-value public input cells, equal to 1

We use the following notation:

(*) n is the size of a multiplicative subgroup H

(*) g are the elements of multiplicative subgroup H i (*) w is the i'th witness in column j i, j (*) β, γ are random challenges generated by the verifier

(*) σ are the values of the j'th copy permutation selector polynomial i, j

(*) k are coset generators, such that g . k is not an element of H, or the coset j i j produced by any other k value, for all l != j l

THIS is our normal permutation grand product:

   n
 ━┳━━┳━ /                       \   /                        \   /                       \
  ┃  ┃  | w     +  β . g    + γ |   | w     + β . k . g  + γ |   | w    + β . k . g  + γ |
  ┃  ┃  |  i, 1         i       |   |  i, 2        1   i     |   |  i,3        2   i     |
  ┃  ┃  | ━━━━━━━━━━━━━━━━━━━━━ | . | ━━━━━━━━━━━━━━━━━━━━━━ | . |━━━━━━━━━━━━━━━━━━━━━━ | = z
  ┃  ┃  | w     + β . σ     + γ |   | w     + β . σ     + γ  |   | w    + β . σ     + γ  |
 i = 1  \  i, 1        i, 1     /   \  i, 2        i, 2      /   \  i,3        i, 3      /

Now let's say that we have m public inputs. We transform the first m products involving column 1, into the following:

m m ━┳━━┳━ / \ ━┳━━┳━ / \ ┃ ┃ | w + β . g + γ | ┃ ┃ | 0 + β . g + γ | ┃ ┃ | i, 1 i | =====> ┃ ┃ | i | = 1 ┃ ┃ | ━━━━━━━━━━━━━━━━━━━━━ | ┃ ┃ | ━━━━━━━━━━━━━ | ┃ ┃ | w + β . σ + γ | ┃ ┃ | 0 + β . g + γ | i = 1 \ i, 1 i, 1 / i = 1 \ i /

We now define a 'delta' term that can be publicly computed, which is the inverse of the following product:

m ━┳━━┳━ / \ ┃ ┃ | w + β . g + γ | ┃ ┃ | i, 1 i | 1 ┃ ┃ | ━━━━━━━━━━━━━━━━━━━━━━ | = ━ ┃ ┃ | w + β . k . g + γ | Δ i = 1 \ i, 1 i /

i.e. we apply an explicit copy constraint that maps w to w for the first m witnesses i, 1 i, 2

After applying these transformations, we have

z = Δ n

This can be validated by verifying that

(z(X.g) - Δ).L (X) = 0 mod Z'(X) n-1 H

We check the n-1'th evaluation of z(X.g), as opposed to the n'th evaluation of z(X), because we need to cut the n'th subgroup element out of our vanishing polynomial Z'(X), as H the grand product polynomial identity does not hold at this subgroup element.

This validates the correctness of the public inputs. Specifically, that for the first m rows of program memory, the memory cells on the second column map to our public inputs. We can then use traditional copy constraints to map these cells to other locations in program memory.

◆ enforce_nonzero_selector_polynomials()

void proof_system::plonk::enforce_nonzero_selector_polynomials	(	const auto &	circuit_constructor,
		auto *	proving_key
	)

Fill the last index of each selector polynomial in lagrange form with a non-zero value.

Template Parameters

Flavor

Parameters

circuit_constructor	The object holding the circuit
key	Pointer to the proving key

◆ hash_native_evaluation_domain()

barretenberg::fr proof_system::plonk::hash_native_evaluation_domain ( barretenberg::evaluation_domain const & domain )

Hashes the evaluation domain to match the 'circuit' approach taken in stdlib/recursion/verification_key/verification_key.hpp.

Note: : in that reference file, the circuit-equivalent of this function is a method of the ‘evaluation_domain’ struct. But we cannot do that with the native barretenberg::evaluation_domain type unfortunately, because it's defined in polynomials/evaluation_domain.hpp, and polynomial is a bberg library which does not depend on crypto in its CMakeLists.txt file. (We'd need crypto to be able to call native pedersen functions).

Parameters

domain to hash

Returns: barretenberg::fr hash of the evaluation domain as a field

◆ initialize_proving_key()

std::shared_ptr< plonk::proving_key > proof_system::plonk::initialize_proving_key	(	const auto &	circuit_constructor,
		barretenberg::srs::factories::CrsFactory< curve::BN254 > *	crs_factory,
		const size_t	minimum_circuit_size,
		const size_t	num_randomized_gates,
		CircuitType	circuit_type
	)

Initilalize proving key and load the crs.

Parameters

circuit_constructor	Object containing the circuit
crs_factory	Produces the prover's reference string
minimum_circuit_size	The minimum size of polynomials without randomized elements
num_randomized_gates	Number of gates with randomized witnesses
circuit_type	This is passed in the case of Plonk since we use flavor-independent proving and verification keys in that case.

Returns: std::shared_ptr<typename Flavor::ProvingKey>

Classes

Typedefs

Enumerations

Functions

Detailed Description

Typedef Documentation

◆ ProverArithmeticWidget

◆ ProverPlookupArithmeticWidget

◆ VerifierArithmeticWidget

◆ VerifierPlookupArithmeticWidget

Function Documentation

◆ compute_monomial_and_coset_selector_forms()

◆ compute_permutation_lagrange_base_single() [1/2]

◆ compute_permutation_lagrange_base_single() [2/2]

◆ compute_public_input_delta()

◆ enforce_nonzero_selector_polynomials()

◆ hash_native_evaluation_domain()

◆ initialize_proving_key()