#include <protogalaxy_prover.hpp>

Public Types
using	ProverInstance = ProverInstance_< Flavor >

using	VerifierInstance = VerifierInstance_< Flavor >

using	FF = typename Flavor::FF

using	CombinerQuotient = Univariate< FF, BATCHED_EXTENDED_LENGTH, NUM_INSTANCES >

using	TupleOfTuplesOfUnivariates = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariates< NUM_INSTANCES >

using	UnivariateRelationParameters = bb::RelationParameters< Univariate< FF, EXTENDED_LENGTH, 0, SKIP_COUNT > >

using	UnivariateSubrelationSeparators = std::array< Univariate< FF, BATCHED_EXTENDED_LENGTH >, NUM_SUBRELATIONS - 1 >

using	Transcript = typename Flavor::Transcript

using	CommitmentKey = typename Flavor::CommitmentKey

using	PGInternal = ProtogalaxyProverInternal< ProverInstance >

using	ProverInstances = std::array< std::shared_ptr< ProverInstance >, NUM_INSTANCES >

using	VerifierInstances = std::array< std::shared_ptr< VerifierInstance >, NUM_INSTANCES >

Public Member Functions
	ProtogalaxyProver_ ()=default

	ProtogalaxyProver_ (const ProverInstances &prover_insts, const VerifierInstances &verifier_insts, const std::shared_ptr< Transcript > &transcript, ExecutionTraceUsageTracker trace_usage_tracker=ExecutionTraceUsageTracker{})

void	run_oink_prover_on_one_incomplete_instance (std::shared_ptr< ProverInstance >, std::shared_ptr< VerifierInstance >, const std::string &domain_separator)
	For each Prover instance derived from a circuit, prior to folding, we need to complete the computation of its polynomials (some of which require generating relation parameters first); commit to witnesses and generate the relation parameters; and send the public data ϕ of the instance to the verifier (which will represent the verifier instance).

void	run_oink_prover_on_each_incomplete_instance ()
	Create inputs to folding protocol (an Oink interaction).

std::tuple< std::vector< FF >, Polynomial< FF > >	perturbator_round (const std::shared_ptr< const ProverInstance > &accumulator)
	Steps 2 - 5 of the paper.

std::tuple< std::vector< FF >, UnivariateSubrelationSeparators, UnivariateRelationParameters, FF, CombinerQuotient >	combiner_quotient_round (const std::vector< FF > &gate_challenges, const std::vector< FF > &deltas, const ProverInstances &instances)
	Steps 6 - 11 of the paper.

void	update_target_sum_and_fold (const ProverInstances &instances, const CombinerQuotient &combiner_quotient, const UnivariateSubrelationSeparators &alphas, const UnivariateRelationParameters &univariate_relation_parameters, const FF &perturbator_evaluation)
	Steps 12 - 13 of the paper plus the prover folding work.

BB_PROFILE FoldingResult< Flavor >	prove ()
	Execute the folding prover.

Public Attributes
ProverInstances	prover_insts_to_fold

VerifierInstances	verifier_insts_to_fold

CommitmentKey	commitment_key

std::shared_ptr< Transcript >	transcript = std::make_shared<Transcript>()

std::shared_ptr< ProverInstance >	accumulator

Polynomial< FF >	perturbator

std::vector< FF >	deltas

CombinerQuotient	combiner_quotient

FF	perturbator_evaluation

UnivariateRelationParameters	relation_parameters

UnivariateSubrelationSeparators	alphas

PGInternal	pg_internal

Static Public Attributes
static constexpr size_t	NUM_SUBRELATIONS = Flavor::NUM_SUBRELATIONS

static constexpr size_t	EXTENDED_LENGTH = computed_extended_length<Flavor>()

static constexpr size_t	BATCHED_EXTENDED_LENGTH = computed_batched_extended_length<Flavor>()

Private Member Functions
size_t	get_max_dyadic_size () const
	Get the maximum dyadic circuit size among all prover instances.

Detailed Description

template<IsUltraOrMegaHonk Flavor>
class bb::ProtogalaxyProver_< Flavor >

Definition at line 19 of file protogalaxy_prover.hpp.

Member Typedef Documentation

◆ CombinerQuotient

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::CombinerQuotient = Univariate<FF, BATCHED_EXTENDED_LENGTH, NUM_INSTANCES>

Definition at line 28 of file protogalaxy_prover.hpp.

◆ CommitmentKey

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::CommitmentKey = typename Flavor::CommitmentKey

Definition at line 35 of file protogalaxy_prover.hpp.

◆ FF

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::FF = typename Flavor::FF

Definition at line 27 of file protogalaxy_prover.hpp.

◆ PGInternal

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::PGInternal = ProtogalaxyProverInternal<ProverInstance>

Definition at line 36 of file protogalaxy_prover.hpp.

◆ ProverInstance

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::ProverInstance = ProverInstance_<Flavor>

Definition at line 25 of file protogalaxy_prover.hpp.

◆ ProverInstances

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::ProverInstances = std::array<std::shared_ptr<ProverInstance>, NUM_INSTANCES>

Definition at line 38 of file protogalaxy_prover.hpp.

◆ Transcript

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::Transcript = typename Flavor::Transcript

Definition at line 34 of file protogalaxy_prover.hpp.

◆ TupleOfTuplesOfUnivariates

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::TupleOfTuplesOfUnivariates = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariates<NUM_INSTANCES>

Definition at line 29 of file protogalaxy_prover.hpp.

◆ UnivariateRelationParameters

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::UnivariateRelationParameters = bb::RelationParameters<Univariate<FF, EXTENDED_LENGTH, 0, SKIP_COUNT> >

Definition at line 30 of file protogalaxy_prover.hpp.

◆ UnivariateSubrelationSeparators

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::UnivariateSubrelationSeparators = std::array<Univariate<FF, BATCHED_EXTENDED_LENGTH>, NUM_SUBRELATIONS - 1>

Definition at line 32 of file protogalaxy_prover.hpp.

◆ VerifierInstance

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::VerifierInstance = VerifierInstance_<Flavor>

Definition at line 26 of file protogalaxy_prover.hpp.

◆ VerifierInstances

template<IsUltraOrMegaHonk Flavor>

using bb::ProtogalaxyProver_< Flavor >::VerifierInstances = std::array<std::shared_ptr<VerifierInstance>, NUM_INSTANCES>

Definition at line 39 of file protogalaxy_prover.hpp.

Constructor & Destructor Documentation

◆ ProtogalaxyProver_() [1/2]

template<IsUltraOrMegaHonk Flavor>

bb::ProtogalaxyProver_< Flavor >::ProtogalaxyProver_ ( )

default

◆ ProtogalaxyProver_() [2/2]

template<IsUltraOrMegaHonk Flavor>

bb::ProtogalaxyProver_< Flavor >::ProtogalaxyProver_	(	const ProverInstances &	prover_insts,
		const VerifierInstances &	verifier_insts,
		const std::shared_ptr< Transcript > &	transcript,
		ExecutionTraceUsageTracker	trace_usage_tracker = `ExecutionTraceUsageTracker{}`
	)

inline

Definition at line 58 of file protogalaxy_prover.hpp.

Member Function Documentation

◆ combiner_quotient_round()

template<IsUltraOrMegaHonk Flavor>

std::tuple< std::vector< typename Flavor::FF >, typename ProtogalaxyProver_< Flavor >::UnivariateSubrelationSeparators, typename ProtogalaxyProver_< Flavor >::UnivariateRelationParameters, typename Flavor::FF, typename ProtogalaxyProver_< Flavor >::CombinerQuotient > bb::ProtogalaxyProver_< Flavor >::combiner_quotient_round	(	const std::vector< FF > &	gate_challenges,
		const std::vector< FF > &	deltas,
		const ProverInstances &	instances
	)

Steps 6 - 11 of the paper.

Compute combiner (G polynomial in the paper) and then its quotient (K polynomial), whose coefficients will be sent to the verifier.

Definition at line 74 of file protogalaxy_prover_impl.hpp.

◆ get_max_dyadic_size()

template<IsUltraOrMegaHonk Flavor>

size_t bb::ProtogalaxyProver_< Flavor >::get_max_dyadic_size ( ) const

inlineprivate

Get the maximum dyadic circuit size among all prover instances.

Returns: The maximum dyadic size

Definition at line 134 of file protogalaxy_prover.hpp.

◆ perturbator_round()

template<IsUltraOrMegaHonk Flavor>

std::tuple< std::vector< typename Flavor::FF >, Polynomial< typename Flavor::FF > > bb::ProtogalaxyProver_< Flavor >::perturbator_round ( const std::shared_ptr< const ProverInstance > & accumulator )

Steps 2 - 5 of the paper.

Compute perturbator (F polynomial in paper). Send all but the constant coefficient to verifier.

Parameters

accumulator

Returns: std::tuple<std::vector<FF>, Polynomial<FF>> deltas, perturbator

Definition at line 50 of file protogalaxy_prover_impl.hpp.

◆ prove()

template<IsUltraOrMegaHonk Flavor>

FoldingResult< Flavor > bb::ProtogalaxyProver_< Flavor >::prove ( )

Execute the folding prover.

Returns: FoldingResult is a pair consisting of the new accumulator and a folding proof, which is a proof that the accumulator was computed correctly.

Definition at line 220 of file protogalaxy_prover_impl.hpp.

◆ run_oink_prover_on_each_incomplete_instance()

template<IsUltraOrMegaHonk Flavor>

void bb::ProtogalaxyProver_< Flavor >::run_oink_prover_on_each_incomplete_instance ( )

Create inputs to folding protocol (an Oink interaction).

Complete all Prover instances that will be folded: complete computation of all the witness polynomials and compute commitments. Send commitments to the verifier and retrieve challenges.

Definition at line 29 of file protogalaxy_prover_impl.hpp.

◆ run_oink_prover_on_one_incomplete_instance()

template<IsUltraOrMegaHonk Flavor>

void bb::ProtogalaxyProver_< Flavor >::run_oink_prover_on_one_incomplete_instance	(	std::shared_ptr< ProverInstance >	key,
		std::shared_ptr< VerifierInstance >	vk,
		const std::string &	domain_separator
	)

For each Prover instance derived from a circuit, prior to folding, we need to complete the computation of its polynomials (some of which require generating relation parameters first); commit to witnesses and generate the relation parameters; and send the public data ϕ of the instance to the verifier (which will represent the verifier instance).

Parameters

domain_separator a label used for tracking data in the transcript

Definition at line 19 of file protogalaxy_prover_impl.hpp.

◆ update_target_sum_and_fold()

template<IsUltraOrMegaHonk Flavor>

void bb::ProtogalaxyProver_< Flavor >::update_target_sum_and_fold	(	const ProverInstances &	instances,
		const CombinerQuotient &	combiner_quotient,
		const UnivariateSubrelationSeparators &	alphas,
		const UnivariateRelationParameters &	univariate_relation_parameters,
		const FF &	perturbator_evaluation
	)

Steps 12 - 13 of the paper plus the prover folding work.

Given the challenge \(\gamma\), compute \(Z(\gamma)\) and \(L_0(\gamma),L_1(\gamma)\).

Compute \( e^* \) (the new target sum), then update the prover accumulator by taking a Lagrange-linear combination of the current accumulator and the prover instances to be folded. In our mental model, we are doing a scalar multiplication of matrices whose columns are polynomials, as well as taking similar linear combinations of the relation parameters.

Definition at line 115 of file protogalaxy_prover_impl.hpp.

Member Data Documentation

◆ accumulator

template<IsUltraOrMegaHonk Flavor>

std::shared_ptr<ProverInstance> bb::ProtogalaxyProver_< Flavor >::accumulator

Definition at line 47 of file protogalaxy_prover.hpp.

◆ alphas

template<IsUltraOrMegaHonk Flavor>

UnivariateSubrelationSeparators bb::ProtogalaxyProver_< Flavor >::alphas

Definition at line 53 of file protogalaxy_prover.hpp.

◆ BATCHED_EXTENDED_LENGTH

template<IsUltraOrMegaHonk Flavor>

constexpr size_t bb::ProtogalaxyProver_< Flavor >::BATCHED_EXTENDED_LENGTH = computed_batched_extended_length<Flavor>()

staticconstexpr

Definition at line 23 of file protogalaxy_prover.hpp.

◆ combiner_quotient

template<IsUltraOrMegaHonk Flavor>

CombinerQuotient bb::ProtogalaxyProver_< Flavor >::combiner_quotient

Definition at line 50 of file protogalaxy_prover.hpp.

◆ commitment_key

template<IsUltraOrMegaHonk Flavor>

CommitmentKey bb::ProtogalaxyProver_< Flavor >::commitment_key

Definition at line 43 of file protogalaxy_prover.hpp.

◆ deltas

template<IsUltraOrMegaHonk Flavor>

std::vector<FF> bb::ProtogalaxyProver_< Flavor >::deltas

Definition at line 49 of file protogalaxy_prover.hpp.

◆ EXTENDED_LENGTH

template<IsUltraOrMegaHonk Flavor>

constexpr size_t bb::ProtogalaxyProver_< Flavor >::EXTENDED_LENGTH = computed_extended_length<Flavor>()

staticconstexpr

Definition at line 22 of file protogalaxy_prover.hpp.

◆ NUM_SUBRELATIONS

template<IsUltraOrMegaHonk Flavor>

constexpr size_t bb::ProtogalaxyProver_< Flavor >::NUM_SUBRELATIONS = Flavor::NUM_SUBRELATIONS

staticconstexpr

Definition at line 21 of file protogalaxy_prover.hpp.

◆ perturbator

template<IsUltraOrMegaHonk Flavor>

Polynomial<FF> bb::ProtogalaxyProver_< Flavor >::perturbator

Definition at line 48 of file protogalaxy_prover.hpp.

◆ perturbator_evaluation

template<IsUltraOrMegaHonk Flavor>

FF bb::ProtogalaxyProver_< Flavor >::perturbator_evaluation

Definition at line 51 of file protogalaxy_prover.hpp.

◆ pg_internal

template<IsUltraOrMegaHonk Flavor>

PGInternal bb::ProtogalaxyProver_< Flavor >::pg_internal

Definition at line 55 of file protogalaxy_prover.hpp.

◆ prover_insts_to_fold

template<IsUltraOrMegaHonk Flavor>

ProverInstances bb::ProtogalaxyProver_< Flavor >::prover_insts_to_fold

Definition at line 41 of file protogalaxy_prover.hpp.

◆ relation_parameters

template<IsUltraOrMegaHonk Flavor>

UnivariateRelationParameters bb::ProtogalaxyProver_< Flavor >::relation_parameters

Definition at line 52 of file protogalaxy_prover.hpp.

◆ transcript

template<IsUltraOrMegaHonk Flavor>

std::shared_ptr<Transcript> bb::ProtogalaxyProver_< Flavor >::transcript = std::make_shared<Transcript>()

Definition at line 46 of file protogalaxy_prover.hpp.

◆ verifier_insts_to_fold

template<IsUltraOrMegaHonk Flavor>

VerifierInstances bb::ProtogalaxyProver_< Flavor >::verifier_insts_to_fold

Definition at line 42 of file protogalaxy_prover.hpp.

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

src/barretenberg/protogalaxy/protogalaxy_prover.hpp
src/barretenberg/protogalaxy/protogalaxy_prover_impl.hpp

Public Types

Public Member Functions

Public Attributes

Static Public Attributes

Private Member Functions

Detailed Description

Member Typedef Documentation

◆ CombinerQuotient

◆ CommitmentKey

◆ FF

◆ PGInternal

◆ ProverInstance

◆ ProverInstances

◆ Transcript

◆ TupleOfTuplesOfUnivariates

◆ UnivariateRelationParameters

◆ UnivariateSubrelationSeparators

◆ VerifierInstance

◆ VerifierInstances

Constructor & Destructor Documentation

◆ ProtogalaxyProver_() [1/2]

◆ ProtogalaxyProver_() [2/2]

Member Function Documentation

◆ combiner_quotient_round()

◆ get_max_dyadic_size()

◆ perturbator_round()

◆ prove()

◆ run_oink_prover_on_each_incomplete_instance()

◆ run_oink_prover_on_one_incomplete_instance()

◆ update_target_sum_and_fold()

Member Data Documentation

◆ accumulator

◆ alphas

◆ BATCHED_EXTENDED_LENGTH

◆ combiner_quotient

◆ commitment_key

◆ deltas

◆ EXTENDED_LENGTH

◆ NUM_SUBRELATIONS

◆ perturbator

◆ perturbator_evaluation

◆ pg_internal

◆ prover_insts_to_fold

◆ relation_parameters

◆ transcript

◆ verifier_insts_to_fold