Extend the ProtogalaxyProverInternal class to compute the combiner without optimistically skipping. More...

Inheritance diagram for PGInternalTest:

Public Types
using	ExtendedUnivariatesNoOptimisticSkipping = typename Flavor::template ProverUnivariates< ExtendedUnivariate::LENGTH >

using	UnivariateRelationParametersNoOptimisticSkipping = bb::RelationParameters< Univariate< FF, EXTENDED_LENGTH > >

using	ExtendedUnivariatesTypeNoOptimisticSkipping = std::conditional_t< Flavor::USE_SHORT_MONOMIALS, ShortUnivariates, ExtendedUnivariatesNoOptimisticSkipping >

Public Types inherited from bb::ProtogalaxyProverInternal< ProverInstance_< Flavor > >
using	Flavor = typename ProverInstance::Flavor

using	FF = typename Flavor::FF

using	RelationUtils = bb::RelationUtils< Flavor >

using	ProverPolynomials = typename Flavor::ProverPolynomials

using	Relations = typename Flavor::Relations

using	AllValues = typename Flavor::AllValues

using	SubrelationSeparators = typename Flavor::SubrelationSeparators

using	ProverInstances = std::array< std::shared_ptr< ProverInstance_< Flavor > >, NUM_INSTANCES >

using	UnivariateRelationParametersNoOptimisticSkipping = bb::RelationParameters< Univariate< FF, EXTENDED_LENGTH > >

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

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

using	ExtendedUnivariate = Univariate< FF, EXTENDED_LENGTH >

using	ExtendedUnivariateWithRandomization = Univariate< FF, BATCHED_EXTENDED_LENGTH >

using	ShortUnivariates = typename Flavor::template ProverUnivariates< NUM_INSTANCES >
	ShortUnivariates is an optimisation to improve the evaluation of Flavor relations when the output is a low-degree monomial.

using	ExtendedUnivariates = typename Flavor::template ProverUnivariatesWithOptimisticSkipping< ExtendedUnivariate::LENGTH, SKIP_COUNT >

using	ExtendedUnivariatesType = std::conditional_t< Flavor::USE_SHORT_MONOMIALS, ShortUnivariates, ExtendedUnivariates >

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

using	TupleOfTuplesOfUnivariatesNoOptimisticSkipping = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariatesNoOptimisticSkipping< NUM_INSTANCES >

using	RelationEvaluations = decltype(create_tuple_of_arrays_of_values< typename Flavor::Relations >())

Public Member Functions
ExtendedUnivariateWithRandomization	compute_combiner_no_optimistic_skipping (const ProverInstances &keys, const GateSeparatorPolynomial< FF > &gate_separators, const UnivariateRelationParametersNoOptimisticSkipping &relation_parameters, const UnivariateSubrelationSeparators &alphas)
	Compute combiner using univariates that do not avoid zero computation in case of valid incoming indices.

ExtendedUnivariateWithRandomization	compute_combiner_no_optimistic_skipping (const ProverInstances &keys, const GateSeparatorPolynomial< FF > &gate_separators, const UnivariateRelationParametersNoOptimisticSkipping &relation_parameters, const UnivariateSubrelationSeparators &alphas, TupleOfTuplesOfUnivariatesNoOptimisticSkipping &univariate_accumulators)
	Compute the combiner polynomial $G$ in the Protogalaxy paper.

Public Member Functions inherited from bb::ProtogalaxyProverInternal< ProverInstance_< Flavor > >
	ProtogalaxyProverInternal (ExecutionTraceUsageTracker trace_usage_tracker=ExecutionTraceUsageTracker{})

Polynomial< FF >	compute_row_evaluations (const ProverPolynomials &polynomials, const SubrelationSeparators &alphas, const RelationParameters< FF > &relation_parameters)
	Compute the values of the aggregated relation evaluations at each row in the execution trace, representing f_i(ω) in the Protogalaxy paper, given the evaluations of all the prover polynomials and \vec{α} (the batching challenges that help establishing each subrelation is independently valid in Mega Honk relation - this α is same as in the Plonk paper, DO NOT confuse with α in Protogalaxy).

Polynomial< FF >	compute_perturbator (const std::shared_ptr< const ProverInstance_< Flavor > > &accumulator, const std::vector< FF > &deltas)
	Construct the perturbator polynomial F(X) in coefficient form from the accumulator resulted from a previous round of Protogalaxy.

ExtendedUnivariateWithRandomization	compute_combiner (const ProverInstances &instances, const GateSeparatorPolynomial< FF > &gate_separators, const UnivariateRelationParameters &relation_parameters, const UnivariateSubrelationSeparators &alphas, TupleOfTuplesOfUnivariates &univariate_accumulators)
	Compute the combiner polynomial $G$ in the Protogalaxy paper.

Static Public Member Functions
template<size_t relation_idx = 0>
static BB_INLINE void	accumulate_relation_univariates_no_optimistic_skipping (TupleOfTuplesOfUnivariatesNoOptimisticSkipping &univariate_accumulators, const ExtendedUnivariatesTypeNoOptimisticSkipping &extended_univariates, const UnivariateRelationParametersNoOptimisticSkipping &relation_parameters, const FF &scaling_factor)
	Add the value of each relation over univariates to an appropriate accumulator.

Static Public Member Functions inherited from bb::ProtogalaxyProverInternal< ProverInstance_< Flavor > >
static auto	row_to_univariates (const ProverInstances &instances, size_t row_idx)
	Constructs univariates that interpolate the values of each instance across a given row.

static FF	process_subrelation_evaluations (const RelationEvaluations &evals, const SubrelationSeparators &challenges, FF &linearly_dependent_contribution)
	Scale all linearly independent subrelations evaluations by challenges ('alphas').

static std::vector< FF >	construct_coefficients_tree (std::span< const FF > betas, std::span< const FF > deltas, std::vector< FF > &current_level_buffer, size_t current_width, size_t current_degree)
	Non-recursively compute the parent nodes of each level in the tree, starting from the leaves.

static std::vector< FF >	construct_perturbator_coefficients (std::span< const FF > betas, std::span< const FF > deltas, const Polynomial< FF > &full_honk_evaluations)
	Construct the perturbator polynomial F(X) coefficients in O(n) time using binary tree reduction.

static BB_INLINE void	extend_univariates (ExtendedUnivariatesType &extended_univariates, const ProverInstances &instances, const size_t row_idx)
	Prepare a univariate polynomial for relation execution in one step of the combiner construction.

static BB_INLINE void	accumulate_relation_univariates (TupleOfTuplesOfUnivariates &univariate_accumulators, const ExtendedUnivariatesType &extended_univariates, const UnivariateRelationParameters &relation_parameters, const FF &scaling_factor)
	Add the value of each relation over univariates to an appropriate accumulator.

static TupleOfTuplesOfUnivariatesNoOptimisticSkipping	deoptimize_univariates (const TupleOfTuplesOfUnivariatePossiblyOptimistic &tup)
	Convert univariates from optimized form to regular.

static ExtendedUnivariateWithRandomization	batch_over_relations (TupleOfTuplesOfUnivariatesNoOptimisticSkipping &univariate_accumulators, const UnivariateSubrelationSeparators &alphas)
	Given the univariate accumulators and the batching challenges, compute the combiner by batching the subrelations.

static std::pair< typename ProverInstance::FF, std::array< typename ProverInstance::FF, NUM_INSTANCES > >	compute_vanishing_polynomial_and_lagranges (const FF &challenge)
	Compute the vanishing polynomial $Z(X) = X * (X - 1)$ and Lagranges $L_0(X) = 1 - X, L_1(X) = X$ at the challenge.

static Univariate< FF, BATCHED_EXTENDED_LENGTH, NUM_INSTANCES >	compute_combiner_quotient (FF perturbator_evaluation, ExtendedUnivariateWithRandomization combiner)
	Compute the combiner quotient defined as $K$ polynomial in the paper specialised for only folding two instances at once.

static ExtendedRelationParameters	compute_extended_relation_parameters (const ProverInstances &instances)
	For each parameter, collect the value in each ProverInstance in a univariate and extend for use in the combiner computation.

static UnivariateSubrelationSeparators	compute_and_extend_alphas (const ProverInstances &instances)
	Combine the relation batching parameters (alphas) from each prover instance into a univariate for the combiner computation.

static size_t	compute_num_threads (const size_t domain_size)
	Determine number of threads for multithreading of perterbator/combiner operations.

Additional Inherited Members
Public Attributes inherited from bb::ProtogalaxyProverInternal< ProverInstance_< Flavor > >
ExecutionTraceUsageTracker	trace_usage_tracker

Static Public Attributes inherited from bb::ProtogalaxyProverInternal< ProverInstance_< Flavor > >
static constexpr size_t	EXTENDED_LENGTH

static constexpr size_t	BATCHED_EXTENDED_LENGTH

static constexpr size_t	NUM_SUBRELATIONS

Detailed Description

Extend the ProtogalaxyProverInternal class to compute the combiner without optimistically skipping.

"optimistic skipping" is the act of not computing the flavor's relation monomials at evaluation points where an honest Prover would produce an evaluation result of 0 For example, when folding 1 instance w0 with 1 accumulator w, ProtoGalaxy uses a witness polynomial w(X) = w.L0(X) + w0.L1(X), where L0, L1 are Lagrange polynomials. At X=1, w(X) = w0 . The full Protogalaxy relation in this case should evaluate to 0. so we can skip its computation at X=1. The PGInternalTest class adds methods where we do not perform this optimistic skipping, so we can test whether the optimistic skipping algorithm produces the correct result

Definition at line 24 of file combiner.test.cpp.

Member Typedef Documentation

◆ ExtendedUnivariatesNoOptimisticSkipping

using PGInternalTest::ExtendedUnivariatesNoOptimisticSkipping = typename Flavor::template ProverUnivariates<ExtendedUnivariate::LENGTH>

Definition at line 26 of file combiner.test.cpp.

◆ ExtendedUnivariatesTypeNoOptimisticSkipping

using PGInternalTest::ExtendedUnivariatesTypeNoOptimisticSkipping = std::conditional_t<Flavor::USE_SHORT_MONOMIALS, ShortUnivariates, ExtendedUnivariatesNoOptimisticSkipping>

Definition at line 30 of file combiner.test.cpp.

◆ UnivariateRelationParametersNoOptimisticSkipping

using PGInternalTest::UnivariateRelationParametersNoOptimisticSkipping = bb::RelationParameters<Univariate<FF, EXTENDED_LENGTH> >

Definition at line 29 of file combiner.test.cpp.

Member Function Documentation

◆ accumulate_relation_univariates_no_optimistic_skipping()

template<size_t relation_idx = 0>

static BB_INLINE void PGInternalTest::accumulate_relation_univariates_no_optimistic_skipping	(	TupleOfTuplesOfUnivariatesNoOptimisticSkipping &	univariate_accumulators,
		const ExtendedUnivariatesTypeNoOptimisticSkipping &	extended_univariates,
		const UnivariateRelationParametersNoOptimisticSkipping &	relation_parameters,
		const FF &	scaling_factor
	)

inlinestatic

Add the value of each relation over univariates to an appropriate accumulator.

Template Parameters

TupleOfTuplesOfUnivariates_	A tuple of univariate accumulators, where the univariates may be optimized to avoid computation on some indices.
ExtendedUnivariates_	T
Parameters	relation parameters type
relation_idx	The index of the relation

Parameters

univariate_accumulators
extended_univariates
relation_parameters
scaling_factor

Definition at line 137 of file combiner.test.cpp.

◆ compute_combiner_no_optimistic_skipping() [1/2]

ExtendedUnivariateWithRandomization PGInternalTest::compute_combiner_no_optimistic_skipping	(	const ProverInstances &	keys,
		const GateSeparatorPolynomial< FF > &	gate_separators,
		const UnivariateRelationParametersNoOptimisticSkipping &	relation_parameters,
		const UnivariateSubrelationSeparators &	alphas
	)

inline

Compute combiner using univariates that do not avoid zero computation in case of valid incoming indices.

This is only used for testing the combiner calculation.

Definition at line 37 of file combiner.test.cpp.

◆ compute_combiner_no_optimistic_skipping() [2/2]

ExtendedUnivariateWithRandomization PGInternalTest::compute_combiner_no_optimistic_skipping	(	const ProverInstances &	keys,
		const GateSeparatorPolynomial< FF > &	gate_separators,
		const UnivariateRelationParametersNoOptimisticSkipping &	relation_parameters,
		const UnivariateSubrelationSeparators &	alphas,
		TupleOfTuplesOfUnivariatesNoOptimisticSkipping &	univariate_accumulators
	)

inline

Compute the combiner polynomial $G$ in the Protogalaxy paper.

We have implemented an optimization that (eg in the case where we fold one instance-witness pair at a time) assumes the value G(1) is 0, which is true in the case where the witness to be folded is valid.

Todo:: (https://github.com/AztecProtocol/barretenberg/issues/968) Make combiner tests better

Template Parameters

skip_zero_computations whether to use the optimization that skips computing zero.

Parameters

param gate_separators

Returns: ExtendedUnivariateWithRandomization

Definition at line 59 of file combiner.test.cpp.

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

src/barretenberg/protogalaxy/combiner.test.cpp

Public Types

Public Member Functions

Static Public Member Functions

Additional Inherited Members