A ProverInstance is normally constructed from a finalized circuit and it contains all the information required by a Mega Honk prover to create a proof. A ProverInstance is also the result of running the Protogalaxy prover, in which case it becomes a relaxed counterpart with the folding parameters (target sum and gate challenges set to non-zero values). More...

#include <prover_instance.hpp>

Public Types
using	Flavor = Flavor_

using	FF = typename Flavor::FF

using	Trace = TraceToPolynomials< Flavor >

Public Member Functions
void	set_dyadic_size (size_t size)

void	set_overflow_size (size_t size)

void	set_final_active_wire_idx (size_t idx)

size_t	dyadic_size () const

size_t	log_dyadic_size () const

size_t	pub_inputs_offset () const

size_t	num_public_inputs () const

MetaData	get_metadata () const

size_t	get_overflow_size () const

size_t	get_final_active_wire_idx () const

Flavor::PrecomputedData	get_precomputed ()

	ProverInstance_ (Circuit &circuit, TraceSettings trace_settings={}, const CommitmentKey &commitment_key=CommitmentKey())

	ProverInstance_ ()=default

	ProverInstance_ (const ProverInstance_ &)=delete

	ProverInstance_ (ProverInstance_ &&)=delete

ProverInstance_ &	operator= (const ProverInstance_ &)=delete

ProverInstance_ &	operator= (ProverInstance_ &&)=delete

	~ProverInstance_ ()=default

bool	get_is_structured ()

Public Attributes
std::vector< FF >	public_inputs

ProverPolynomials	polynomials

WitnessCommitments	commitments

SubrelationSeparators	alphas

bb::RelationParameters< FF >	relation_parameters

std::vector< FF >	gate_challenges

FF	target_sum { 0 }

HonkProof	ipa_proof

bool	is_relaxed_instance = false

bool	is_complete = false

std::vector< uint32_t >	memory_read_records

std::vector< uint32_t >	memory_write_records

CommitmentKey	commitment_key

ActiveRegionData	active_region_data

Private Types
using	Circuit = typename Flavor::CircuitBuilder

using	CommitmentKey = typename Flavor::CommitmentKey

using	ProverPolynomials = typename Flavor::ProverPolynomials

using	WitnessCommitments = typename Flavor::WitnessCommitments

using	Polynomial = typename Flavor::Polynomial

using	SubrelationSeparators = typename Flavor::SubrelationSeparators

Private Member Functions
size_t	compute_dyadic_size (Circuit &)
	Helper method to compute quantities like total number of gates and dyadic circuit size.

void	allocate_wires ()

void	allocate_permutation_argument_polynomials ()

void	allocate_lagrange_polynomials ()

void	allocate_selectors (const Circuit &)

void	allocate_table_lookup_polynomials (const Circuit &)

void	allocate_ecc_op_polynomials (const Circuit &)

void	allocate_databus_polynomials (const Circuit &)

size_t	compute_structured_dyadic_size (Circuit &circuit)
	Compute dyadic size based on a structured trace with fixed block size.

void	construct_databus_polynomials (Circuit &)

void	populate_memory_records (const Circuit &circuit)
	Copy RAM/ROM record of reads and writes from the circuit to the instance.

Static Private Member Functions
static void	move_structured_trace_overflow_to_overflow_block (Circuit &circuit)
	Check that the number of gates in each block does not exceed its fixed capacity. Move any overflow to the overflow block.

Private Attributes
bool	is_structured

MetaData	metadata

size_t	overflow_size { 0 }

size_t	final_active_wire_idx { 0 }

Static Private Attributes
static constexpr size_t	num_zero_rows = Flavor::has_zero_row ? 1 : 0

static constexpr size_t	NUM_WIRES = Circuit::NUM_WIRES

Detailed Description

template<IsUltraOrMegaHonk Flavor_>
class bb::ProverInstance_< Flavor_ >

A ProverInstance is normally constructed from a finalized circuit and it contains all the information required by a Mega Honk prover to create a proof. A ProverInstance is also the result of running the Protogalaxy prover, in which case it becomes a relaxed counterpart with the folding parameters (target sum and gate challenges set to non-zero values).

A ProverInstance is the equivalent of \(\omega\) in the Protogalaxy paper.

Our arithmetization works as follows. The Flavor defines \(fM\) (Flavor::NUM_ALL_ENTITIES) and a series of relations \(R_1, \dots, R_n\) (Flavor::Relations_). Each relation is made up by a series of subrelations: \(R_i = (R_{i,1}, \dots, R_{i,r_i})\).

Write \(p_1, \dots, p_M\) for the prover polynomials and \(p_{i,k}\) for the \(k\)-th coefficient of \(p_i\). Write \(\theta_1, \dots, \theta_6\) for the relation parameters. Let \(n\) be the max degree of the prover polynomials. A pure ProverInstance is valid if for all \(i, j, k\) we have \(R_{i,j}(p_{1,k}, \dots, p_{M,k}, \theta_1, \dots, \theta_6) = 0\).

Instead of checking each equality separately, we batch them using challenges that we call alphas. Thus, a ProverInstance is valid if for each \(k = 0, \dots, n\).

\[ f_k(\omega) := \sum_{i, j} \alpha_{i,j} R_{i,j}(p_{1,k}, \dots, p_{M,k}, \theta_1, \dots, \theta_6) = 0 \]

Instead of checking each equality separately, we once again batch them using challenges. These challenges are the \(pow_i(\beta)\) in the Protogalaxy paper, and are derived using the vector gate_challenges as the vector \(\beta\). Write \(gc\) for the vector gate_challenges. Then, a ProverInstance is valid if

\[ \sum_{k} pow_k(gc) f_k(\omega) = 0 \]

The equation is modified for a relaxed ProverInstance to

\[ \sum_{k} pow_k(gc) f_k(\omega) = ts \]

where we write \(ts\) for the vector target_sum.

Hence, the correspondence between the class below and the Protogalaxy paper is \(\omega = (p_1, \dots, p_M, , \theta_1, \dots, \theta_6, \alpha_{1,1}, \dots, \alpha_{n,r_n})\), \(\beta\) are the gate_challenges, and \(e\) is target_sum.

Definition at line 69 of file prover_instance.hpp.

Member Typedef Documentation

◆ Circuit

template<IsUltraOrMegaHonk Flavor_>

using bb::ProverInstance_< Flavor_ >::Circuit = typename Flavor::CircuitBuilder

private

Definition at line 75 of file prover_instance.hpp.

◆ CommitmentKey

template<IsUltraOrMegaHonk Flavor_>

using bb::ProverInstance_< Flavor_ >::CommitmentKey = typename Flavor::CommitmentKey

private

Definition at line 76 of file prover_instance.hpp.

◆ FF

template<IsUltraOrMegaHonk Flavor_>

using bb::ProverInstance_< Flavor_ >::FF = typename Flavor::FF

Definition at line 72 of file prover_instance.hpp.

◆ Flavor

template<IsUltraOrMegaHonk Flavor_>

using bb::ProverInstance_< Flavor_ >::Flavor = Flavor_

Definition at line 71 of file prover_instance.hpp.

◆ Polynomial

template<IsUltraOrMegaHonk Flavor_>

using bb::ProverInstance_< Flavor_ >::Polynomial = typename Flavor::Polynomial

private

Definition at line 79 of file prover_instance.hpp.

◆ ProverPolynomials

template<IsUltraOrMegaHonk Flavor_>

using bb::ProverInstance_< Flavor_ >::ProverPolynomials = typename Flavor::ProverPolynomials

private

Definition at line 77 of file prover_instance.hpp.

◆ SubrelationSeparators

template<IsUltraOrMegaHonk Flavor_>

using bb::ProverInstance_< Flavor_ >::SubrelationSeparators = typename Flavor::SubrelationSeparators

private

Definition at line 80 of file prover_instance.hpp.

◆ Trace

template<IsUltraOrMegaHonk Flavor_>

using bb::ProverInstance_< Flavor_ >::Trace = TraceToPolynomials<Flavor>

Definition at line 90 of file prover_instance.hpp.

◆ WitnessCommitments

template<IsUltraOrMegaHonk Flavor_>

using bb::ProverInstance_< Flavor_ >::WitnessCommitments = typename Flavor::WitnessCommitments

private

Definition at line 78 of file prover_instance.hpp.

Constructor & Destructor Documentation

◆ ProverInstance_() [1/4]

template<IsUltraOrMegaHonk Flavor_>

bb::ProverInstance_< Flavor_ >::ProverInstance_	(	Circuit &	circuit,
		TraceSettings	trace_settings = `{}`,
		const CommitmentKey &	commitment_key = `CommitmentKey()`
	)

inline

Definition at line 131 of file prover_instance.hpp.

◆ ProverInstance_() [2/4]

template<IsUltraOrMegaHonk Flavor_>

bb::ProverInstance_< Flavor_ >::ProverInstance_ ( )

default

◆ ProverInstance_() [3/4]

template<IsUltraOrMegaHonk Flavor_>

bb::ProverInstance_< Flavor_ >::ProverInstance_ ( const ProverInstance_< Flavor_ > & )

delete

◆ ProverInstance_() [4/4]

template<IsUltraOrMegaHonk Flavor_>

bb::ProverInstance_< Flavor_ >::ProverInstance_ ( ProverInstance_< Flavor_ > && )

delete

◆ ~ProverInstance_()

template<IsUltraOrMegaHonk Flavor_>

bb::ProverInstance_< Flavor_ >::~ProverInstance_ ( )

default

Member Function Documentation

◆ allocate_databus_polynomials()

template<IsUltraOrMegaHonk Flavor>
requires HasDataBus<Flavor>

void bb::ProverInstance_< Flavor >::allocate_databus_polynomials ( const Circuit & circuit )

private

Definition at line 149 of file prover_instance.cpp.

◆ allocate_ecc_op_polynomials()

template<IsUltraOrMegaHonk Flavor>
requires IsMegaFlavor<Flavor>

void bb::ProverInstance_< Flavor >::allocate_ecc_op_polynomials ( const Circuit & circuit )

private

Definition at line 135 of file prover_instance.cpp.

◆ allocate_lagrange_polynomials()

template<IsUltraOrMegaHonk Flavor>

void bb::ProverInstance_< Flavor >::allocate_lagrange_polynomials ( )

private

Definition at line 61 of file prover_instance.cpp.

◆ allocate_permutation_argument_polynomials()

template<IsUltraOrMegaHonk Flavor>

void bb::ProverInstance_< Flavor >::allocate_permutation_argument_polynomials ( )

private

Definition at line 48 of file prover_instance.cpp.

◆ allocate_selectors()

template<IsUltraOrMegaHonk Flavor>

void bb::ProverInstance_< Flavor >::allocate_selectors ( const Circuit & circuit )

private

Definition at line 76 of file prover_instance.cpp.

◆ allocate_table_lookup_polynomials()

template<IsUltraOrMegaHonk Flavor>

void bb::ProverInstance_< Flavor >::allocate_table_lookup_polynomials ( const Circuit & circuit )

private

Definition at line 101 of file prover_instance.cpp.

◆ allocate_wires()

template<IsUltraOrMegaHonk Flavor>

void bb::ProverInstance_< Flavor >::allocate_wires ( )

private

Definition at line 39 of file prover_instance.cpp.

◆ compute_dyadic_size()

template<IsUltraOrMegaHonk Flavor>

size_t bb::ProverInstance_< Flavor >::compute_dyadic_size ( Circuit & circuit )

private

Helper method to compute quantities like total number of gates and dyadic circuit size.

Template Parameters

Flavor

Parameters

circuit

Definition at line 22 of file prover_instance.cpp.

◆ compute_structured_dyadic_size()

template<IsUltraOrMegaHonk Flavor_>

size_t bb::ProverInstance_< Flavor_ >::compute_structured_dyadic_size ( Circuit & circuit )

inlineprivate

Compute dyadic size based on a structured trace with fixed block size.

Definition at line 290 of file prover_instance.hpp.

◆ construct_databus_polynomials()

template<IsUltraOrMegaHonk Flavor>
requires HasDataBus<Flavor>

void bb::ProverInstance_< Flavor >::construct_databus_polynomials ( Circuit & circuit )

private

Template Parameters

Flavor

Parameters

circuit

Definition at line 187 of file prover_instance.cpp.

◆ dyadic_size()

template<IsUltraOrMegaHonk Flavor_>

size_t bb::ProverInstance_< Flavor_ >::dyadic_size ( ) const

inline

Definition at line 114 of file prover_instance.hpp.

◆ get_final_active_wire_idx()

template<IsUltraOrMegaHonk Flavor_>

size_t bb::ProverInstance_< Flavor_ >::get_final_active_wire_idx ( ) const

inline

Definition at line 124 of file prover_instance.hpp.

◆ get_is_structured()

template<IsUltraOrMegaHonk Flavor_>

bool bb::ProverInstance_< Flavor_ >::get_is_structured ( )

inline

Definition at line 262 of file prover_instance.hpp.

◆ get_metadata()

template<IsUltraOrMegaHonk Flavor_>

MetaData bb::ProverInstance_< Flavor_ >::get_metadata ( ) const

inline

Definition at line 122 of file prover_instance.hpp.

◆ get_overflow_size()

template<IsUltraOrMegaHonk Flavor_>

size_t bb::ProverInstance_< Flavor_ >::get_overflow_size ( ) const

inline

Definition at line 123 of file prover_instance.hpp.

◆ get_precomputed()

template<IsUltraOrMegaHonk Flavor_>

Flavor::PrecomputedData bb::ProverInstance_< Flavor_ >::get_precomputed ( )

inline

Definition at line 126 of file prover_instance.hpp.

◆ log_dyadic_size()

template<IsUltraOrMegaHonk Flavor_>

size_t bb::ProverInstance_< Flavor_ >::log_dyadic_size ( ) const

inline

Definition at line 115 of file prover_instance.hpp.

◆ move_structured_trace_overflow_to_overflow_block()

template<IsUltraOrMegaHonk Flavor>
requires IsMegaFlavor<Flavor>

void bb::ProverInstance_< Flavor >::move_structured_trace_overflow_to_overflow_block ( Circuit & circuit )

staticprivate

Check that the number of gates in each block does not exceed its fixed capacity. Move any overflow to the overflow block.

Using a structured trace (fixed capcity for each gate type) optimizes the efficiency of folding. However, to accommodate circuits which cannot fit into a prescribed trace, gates which overflow their corresponding block are placed into an overflow block which can contain arbitrary gate types.

Note: One sublety is that gates at row i may in general utilize the values at row i+1 via shifts. If the last row in a full-capacity block is such a gate, then moving the overflow out of sequence will cause that gate not to be satisfied. To avoid this, when a block overflows, the final gate in the block is duplicated, once in the main block with the selectors turned off but the wires values maintained (so that the prior gate can read into it but it does not itself try to read into the next row) and again as a normal gate in the overflow block. Therefore, the total number of gates in the circuit increases by one for each block that overflows.

Template Parameters

Flavor

Parameters

circuit

Definition at line 247 of file prover_instance.cpp.

◆ num_public_inputs()

template<IsUltraOrMegaHonk Flavor_>

size_t bb::ProverInstance_< Flavor_ >::num_public_inputs ( ) const

inline

Definition at line 117 of file prover_instance.hpp.

◆ operator=() [1/2]

template<IsUltraOrMegaHonk Flavor_>

ProverInstance_ & bb::ProverInstance_< Flavor_ >::operator= ( const ProverInstance_< Flavor_ > & )

delete

◆ operator=() [2/2]

template<IsUltraOrMegaHonk Flavor_>

ProverInstance_ & bb::ProverInstance_< Flavor_ >::operator= ( ProverInstance_< Flavor_ > && )

delete

◆ populate_memory_records()

template<IsUltraOrMegaHonk Flavor>

void bb::ProverInstance_< Flavor >::populate_memory_records ( const Circuit & circuit )

private

Copy RAM/ROM record of reads and writes from the circuit to the instance.

The memory records in the circuit store indices within the memory block where a read/write is performed. They are stored in the DPK as indices into the full trace by accounting for the offset of the memory block.

Definition at line 348 of file prover_instance.cpp.

◆ pub_inputs_offset()

template<IsUltraOrMegaHonk Flavor_>

size_t bb::ProverInstance_< Flavor_ >::pub_inputs_offset ( ) const

inline

Definition at line 116 of file prover_instance.hpp.

◆ set_dyadic_size()

template<IsUltraOrMegaHonk Flavor_>

void bb::ProverInstance_< Flavor_ >::set_dyadic_size ( size_t size )

inline

Definition at line 111 of file prover_instance.hpp.

◆ set_final_active_wire_idx()

template<IsUltraOrMegaHonk Flavor_>

void bb::ProverInstance_< Flavor_ >::set_final_active_wire_idx ( size_t idx )

inline

Definition at line 113 of file prover_instance.hpp.

◆ set_overflow_size()

template<IsUltraOrMegaHonk Flavor_>

void bb::ProverInstance_< Flavor_ >::set_overflow_size ( size_t size )

inline

Definition at line 112 of file prover_instance.hpp.

Member Data Documentation

◆ active_region_data

template<IsUltraOrMegaHonk Flavor_>

ActiveRegionData bb::ProverInstance_< Flavor_ >::active_region_data

Definition at line 109 of file prover_instance.hpp.

◆ alphas

template<IsUltraOrMegaHonk Flavor_>

SubrelationSeparators bb::ProverInstance_< Flavor_ >::alphas

Definition at line 95 of file prover_instance.hpp.

◆ commitment_key

template<IsUltraOrMegaHonk Flavor_>

CommitmentKey bb::ProverInstance_< Flavor_ >::commitment_key

Definition at line 107 of file prover_instance.hpp.

◆ commitments

template<IsUltraOrMegaHonk Flavor_>

WitnessCommitments bb::ProverInstance_< Flavor_ >::commitments

Definition at line 94 of file prover_instance.hpp.

◆ final_active_wire_idx

template<IsUltraOrMegaHonk Flavor_>

size_t bb::ProverInstance_< Flavor_ >::final_active_wire_idx { 0 }

private

Definition at line 87 of file prover_instance.hpp.

◆ gate_challenges

template<IsUltraOrMegaHonk Flavor_>

std::vector<FF> bb::ProverInstance_< Flavor_ >::gate_challenges

Definition at line 97 of file prover_instance.hpp.

◆ ipa_proof

template<IsUltraOrMegaHonk Flavor_>

HonkProof bb::ProverInstance_< Flavor_ >::ipa_proof

Definition at line 100 of file prover_instance.hpp.

◆ is_complete

template<IsUltraOrMegaHonk Flavor_>

bool bb::ProverInstance_< Flavor_ >::is_complete = false

Definition at line 103 of file prover_instance.hpp.

◆ is_relaxed_instance

template<IsUltraOrMegaHonk Flavor_>

bool bb::ProverInstance_< Flavor_ >::is_relaxed_instance = false

Definition at line 102 of file prover_instance.hpp.

◆ is_structured

template<IsUltraOrMegaHonk Flavor_>

bool bb::ProverInstance_< Flavor_ >::is_structured

private

Definition at line 83 of file prover_instance.hpp.

◆ memory_read_records

template<IsUltraOrMegaHonk Flavor_>

std::vector<uint32_t> bb::ProverInstance_< Flavor_ >::memory_read_records

Definition at line 104 of file prover_instance.hpp.

◆ memory_write_records

template<IsUltraOrMegaHonk Flavor_>

std::vector<uint32_t> bb::ProverInstance_< Flavor_ >::memory_write_records

Definition at line 105 of file prover_instance.hpp.

◆ metadata

template<IsUltraOrMegaHonk Flavor_>

MetaData bb::ProverInstance_< Flavor_ >::metadata

private

Definition at line 85 of file prover_instance.hpp.

◆ NUM_WIRES

template<IsUltraOrMegaHonk Flavor_>

constexpr size_t bb::ProverInstance_< Flavor_ >::NUM_WIRES = Circuit::NUM_WIRES

staticconstexprprivate

Definition at line 266 of file prover_instance.hpp.

◆ num_zero_rows

template<IsUltraOrMegaHonk Flavor_>

constexpr size_t bb::ProverInstance_< Flavor_ >::num_zero_rows = Flavor::has_zero_row ? 1 : 0

staticconstexprprivate

Definition at line 265 of file prover_instance.hpp.

◆ overflow_size

template<IsUltraOrMegaHonk Flavor_>

size_t bb::ProverInstance_< Flavor_ >::overflow_size { 0 }

private

Definition at line 86 of file prover_instance.hpp.

◆ polynomials

template<IsUltraOrMegaHonk Flavor_>

ProverPolynomials bb::ProverInstance_< Flavor_ >::polynomials

Definition at line 93 of file prover_instance.hpp.

◆ public_inputs

template<IsUltraOrMegaHonk Flavor_>

std::vector<FF> bb::ProverInstance_< Flavor_ >::public_inputs

Definition at line 92 of file prover_instance.hpp.

◆ relation_parameters

template<IsUltraOrMegaHonk Flavor_>

bb::RelationParameters<FF> bb::ProverInstance_< Flavor_ >::relation_parameters

Definition at line 96 of file prover_instance.hpp.

◆ target_sum

template<IsUltraOrMegaHonk Flavor_>

FF bb::ProverInstance_< Flavor_ >::target_sum { 0 }

Definition at line 98 of file prover_instance.hpp.

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

src/barretenberg/ultra_honk/prover_instance.hpp
src/barretenberg/ultra_honk/prover_instance.cpp

Public Types

Public Member Functions

Public Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Circuit

◆ CommitmentKey

◆ FF

◆ Flavor

◆ Polynomial

◆ ProverPolynomials

◆ SubrelationSeparators

◆ Trace

◆ WitnessCommitments

Constructor & Destructor Documentation

◆ ProverInstance_() [1/4]

◆ ProverInstance_() [2/4]

◆ ProverInstance_() [3/4]

◆ ProverInstance_() [4/4]

◆ ~ProverInstance_()

Member Function Documentation

◆ allocate_databus_polynomials()

◆ allocate_ecc_op_polynomials()

◆ allocate_lagrange_polynomials()

◆ allocate_permutation_argument_polynomials()

◆ allocate_selectors()

◆ allocate_table_lookup_polynomials()

◆ allocate_wires()

◆ compute_dyadic_size()

◆ compute_structured_dyadic_size()

◆ construct_databus_polynomials()

◆ dyadic_size()

◆ get_final_active_wire_idx()

◆ get_is_structured()

◆ get_metadata()

◆ get_overflow_size()

◆ get_precomputed()

◆ log_dyadic_size()

◆ move_structured_trace_overflow_to_overflow_block()

◆ num_public_inputs()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ populate_memory_records()

◆ pub_inputs_offset()

◆ set_dyadic_size()

◆ set_final_active_wire_idx()

◆ set_overflow_size()

Member Data Documentation

◆ active_region_data

◆ alphas

◆ commitment_key

◆ commitments

◆ final_active_wire_idx

◆ gate_challenges

◆ ipa_proof

◆ is_complete

◆ is_relaxed_instance

◆ is_structured

◆ memory_read_records

◆ memory_write_records

◆ metadata

◆ NUM_WIRES

◆ num_zero_rows

◆ overflow_size

◆ polynomials

◆ public_inputs

◆ relation_parameters

◆ target_sum