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, DeciderPKs::EXTENDED_LENGTH > >

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

Public Types inherited from bb::ProtogalaxyProverInternal< DeciderProvingKeys_< Flavor, NUM_KEYS > >
using	DeciderPKs = DeciderProvingKeys_< Flavor, NUM_KEYS >

using	Flavor = typename DeciderPKs::Flavor

using	FF = typename Flavor::FF

using	DeciderPK = typename DeciderPKs::DeciderPK

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	UnivariateRelationParametersNoOptimisticSkipping = bb::RelationParameters< Univariate< FF, DeciderProvingKeys_::EXTENDED_LENGTH > >

using	UnivariateRelationParameters = bb::RelationParameters< Univariate< FF, DeciderProvingKeys_::EXTENDED_LENGTH, 0, NUM_KEYS - 1 > >

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

using	ExtendedUnivariate = Univariate< FF,(Flavor::MAX_TOTAL_RELATION_LENGTH - 1) *(DeciderPKs::NUM - 1)+1 >

using	ExtendedUnivariateWithRandomization = Univariate< FF,(Flavor::MAX_TOTAL_RELATION_LENGTH - 1+DeciderPKs::NUM - 1) *(DeciderPKs::NUM - 1)+1 >

using	ShortUnivariates = typename Flavor::template ProverUnivariates< DeciderPKs::NUM >
	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, DeciderPKs::NUM - 1 >

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

using	TupleOfTuplesOfUnivariates = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariates< DeciderPKs::NUM >

using	TupleOfTuplesOfUnivariatesNoOptimisticSkipping = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariatesNoOptimisticSkipping< DeciderPKs::NUM >

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

Public Member Functions
ExtendedUnivariateWithRandomization	compute_combiner_no_optimistic_skipping (const DeciderPKs &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 DeciderPKs &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< DeciderProvingKeys_< Flavor, NUM_KEYS > >
	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 Honk - from the Plonk paper, DO NOT confuse with α in Protogalaxy).

Polynomial< FF >	compute_perturbator (const std::shared_ptr< const DeciderPK > &accumulator, const std::vector< FF > &deltas)
	Construct the power perturbator polynomial F(X) in coefficient form from the accumulator.

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

ExtendedUnivariateWithRandomization	compute_combiner (const DeciderPKs &keys, const GateSeparatorPolynomial< FF > &gate_separators, const UnivariateRelationParameters &relation_parameters, const UnivariateSubrelationSeparators &alphas)

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< DeciderProvingKeys_< Flavor, NUM_KEYS > >
static FF	process_subrelation_evaluations (const RelationEvaluations &evals, const SubrelationSeparators &challenges, FF &linearly_dependent_contribution)
	A scale subrelations evaluations by challenges ('alphas') and part of the linearly dependent relation evaluation(s).

static std::vector< FF >	construct_coefficients_tree (std::span< const FF > betas, std::span< const FF > deltas, const std::vector< std::vector< FF > > &prev_level_coeffs, size_t level=1)
	Recursively compute the parent nodes of each level in the tree, starting from the leaves. Note that at each level, the resulting parent nodes will be polynomials of degree (level+1) because we multiply by an additional factor of X.

static std::vector< FF >	construct_perturbator_coefficients (std::span< const FF > betas, std::span< const FF > deltas, const Polynomial< FF > &full_honk_evaluations)
	We construct the coefficients of the perturbator polynomial in O(n) time following the technique in Claim 4.4. Consider a binary tree whose leaves are the evaluations of the full Honk relation at each row in the execution trace. The subsequent levels in the tree are constructed using the following technique: At level i in the tree, label the branch connecting the left node n_l to its parent by 1 and for the right node n_r by β_i + δ_i X. The value of the parent node n will be constructed as n = n_l + n_r * (β_i + δ_i X). Recurse over each layer until the root is reached which will correspond to the perturbator polynomial F(X). TODO(https://github.com/AztecProtocol/barretenberg/issues/745): make computation of perturbator more memory efficient, operate in-place and use std::resize; add multithreading.

static BB_INLINE void	extend_univariates (ExtendedUnivariatesType &extended_univariates, const DeciderPKs &keys, 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)

static std::pair< typename DeciderPKs::FF, std::array< typename DeciderPKs::FF, DeciderPKs::NUM > >	compute_vanishing_polynomial_and_lagranges (const FF &challenge)

static Univariate< FF, DeciderPKs::BATCHED_EXTENDED_LENGTH, DeciderPKs::NUM >	compute_combiner_quotient (FF perturbator_evaluation, ExtendedUnivariateWithRandomization combiner)
	Compute the combiner quotient defined as $K$ polynomial in the paper.

static ExtendedRelationParameters	compute_extended_relation_parameters (const DeciderPKs &keys)
	For each parameter, collect the value in each decider pvogin key in a univariate and extend for use in the combiner compute.

static UnivariateSubrelationSeparators	compute_and_extend_alphas (const DeciderPKs &keys)
	Combine the relation batching parameters (alphas) from each decider proving key into a univariate for using in 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< DeciderProvingKeys_< Flavor, NUM_KEYS > >
ExecutionTraceUsageTracker	trace_usage_tracker

Static Public Attributes inherited from bb::ProtogalaxyProverInternal< DeciderProvingKeys_< Flavor, NUM_KEYS > >
static constexpr size_t	NUM_KEYS

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 25 of file combiner.test.cpp.

Member Typedef Documentation

◆ ExtendedUnivariatesNoOptimisticSkipping

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

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

◆ ExtendedUnivariatesTypeNoOptimisticSkipping

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

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

◆ UnivariateRelationParametersNoOptimisticSkipping

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

Definition at line 30 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 139 of file combiner.test.cpp.

◆ compute_combiner_no_optimistic_skipping() [1/2]

ExtendedUnivariateWithRandomization PGInternalTest::compute_combiner_no_optimistic_skipping	(	const DeciderPKs &	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 39 of file combiner.test.cpp.

◆ compute_combiner_no_optimistic_skipping() [2/2]

ExtendedUnivariateWithRandomization PGInternalTest::compute_combiner_no_optimistic_skipping	(	const DeciderPKs &	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 61 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