Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes | List of all members
bb::ProtogalaxyProverInternal< ProverInstance > Class Template Reference

A purely static class (never add state to this!) consisting of functions used by the Protogalaxy prover. More...

#include <protogalaxy_prover_internal.hpp>

Public Types

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 >, 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

 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 > &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 skip_count = 0>
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.
 
template<size_t skip_count = 0>
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.
 
template<size_t relation_idx = 0>
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.
 
template<typename TupleOfTuplesOfUnivariatePossiblyOptimistic >
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.
 
template<typename ExtendedRelationParameters >
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.
 

Public Attributes

ExecutionTraceUsageTracker trace_usage_tracker
 

Static Public Attributes

static constexpr size_t EXTENDED_LENGTH = computed_extended_length<Flavor>()
 
static constexpr size_t BATCHED_EXTENDED_LENGTH = computed_batched_extended_length<Flavor>()
 
static constexpr size_t NUM_SUBRELATIONS = Flavor::NUM_SUBRELATIONS
 

Detailed Description

template<class ProverInstance>
class bb::ProtogalaxyProverInternal< ProverInstance >

A purely static class (never add state to this!) consisting of functions used by the Protogalaxy prover.

Template Parameters
ProverInstance

Definition at line 26 of file protogalaxy_prover_internal.hpp.

Member Typedef Documentation

◆ AllValues

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::AllValues = typename Flavor::AllValues

Definition at line 33 of file protogalaxy_prover_internal.hpp.

◆ ExtendedUnivariate

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::ExtendedUnivariate = Univariate<FF, EXTENDED_LENGTH>

Definition at line 47 of file protogalaxy_prover_internal.hpp.

◆ ExtendedUnivariates

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::ExtendedUnivariates = typename Flavor::template ProverUnivariatesWithOptimisticSkipping<ExtendedUnivariate::LENGTH, SKIP_COUNT>

Definition at line 72 of file protogalaxy_prover_internal.hpp.

◆ ExtendedUnivariatesType

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::ExtendedUnivariatesType = std::conditional_t<Flavor::USE_SHORT_MONOMIALS, ShortUnivariates, ExtendedUnivariates>

Definition at line 76 of file protogalaxy_prover_internal.hpp.

◆ ExtendedUnivariateWithRandomization

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::ExtendedUnivariateWithRandomization = Univariate<FF, BATCHED_EXTENDED_LENGTH>

Definition at line 49 of file protogalaxy_prover_internal.hpp.

◆ FF

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::FF = typename Flavor::FF

Definition at line 29 of file protogalaxy_prover_internal.hpp.

◆ Flavor

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::Flavor = typename ProverInstance::Flavor

Definition at line 28 of file protogalaxy_prover_internal.hpp.

◆ ProverInstances

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::ProverInstances = std::array<std::shared_ptr<ProverInstance>, NUM_INSTANCES>

Definition at line 35 of file protogalaxy_prover_internal.hpp.

◆ ProverPolynomials

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::ProverPolynomials = typename Flavor::ProverPolynomials

Definition at line 31 of file protogalaxy_prover_internal.hpp.

◆ RelationEvaluations

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::RelationEvaluations = decltype(create_tuple_of_arrays_of_values<typename Flavor::Relations>())

Definition at line 83 of file protogalaxy_prover_internal.hpp.

◆ Relations

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::Relations = typename Flavor::Relations

Definition at line 32 of file protogalaxy_prover_internal.hpp.

◆ RelationUtils

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::RelationUtils = bb::RelationUtils<Flavor>

Definition at line 30 of file protogalaxy_prover_internal.hpp.

◆ ShortUnivariates

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::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.

Each Flavor relation is computed as a degree-Flavor::MAX_TOTAL_RELATION_LENGTH Univariate monomial in the Lagrange basis, however it is more efficient if the input monomials into the relation are not in this form, but are instead left as a degree-1 monomial using the coefficient basis (i.e. P(X) = a0 + a1.X)

When computing relation algebra, it is typically more efficient to use the coefficient basis up to degree-2. If the degree must be extended beyond 2, then the monomials are converted into their higher-degree representation in the Lagrange basis.

Not only is the relation algebra more efficient, but we do not have to perform a basis extension on all the Flavor polynomials each time the Flavor relation algebra is evaluated. Given the sparse representation of our circuits, many relations are skipped each row which means many polynomials can go unused. By skipping the basis extension entirely we avoid this unneccessary work.

Tests indicates that utilizing ShortUnivariates speeds up the benchmark_client_ivc.sh benchmark by 10%

Note
This only works for two instances.

Definition at line 70 of file protogalaxy_prover_internal.hpp.

◆ SubrelationSeparators

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::SubrelationSeparators = typename Flavor::SubrelationSeparators

Definition at line 34 of file protogalaxy_prover_internal.hpp.

◆ TupleOfTuplesOfUnivariates

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::TupleOfTuplesOfUnivariates = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariates<NUM_INSTANCES>

Definition at line 79 of file protogalaxy_prover_internal.hpp.

◆ TupleOfTuplesOfUnivariatesNoOptimisticSkipping

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::TupleOfTuplesOfUnivariatesNoOptimisticSkipping = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariatesNoOptimisticSkipping<NUM_INSTANCES>

Definition at line 80 of file protogalaxy_prover_internal.hpp.

◆ UnivariateRelationParameters

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::UnivariateRelationParameters = bb::RelationParameters<Univariate<FF, EXTENDED_LENGTH, 0, SKIP_COUNT> >

Definition at line 42 of file protogalaxy_prover_internal.hpp.

◆ UnivariateRelationParametersNoOptimisticSkipping

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::UnivariateRelationParametersNoOptimisticSkipping = bb::RelationParameters<Univariate<FF, EXTENDED_LENGTH> >

Definition at line 41 of file protogalaxy_prover_internal.hpp.

◆ UnivariateSubrelationSeparators

template<class ProverInstance >
using bb::ProtogalaxyProverInternal< ProverInstance >::UnivariateSubrelationSeparators = std::array<Univariate<FF, BATCHED_EXTENDED_LENGTH>, NUM_SUBRELATIONS - 1>

Definition at line 44 of file protogalaxy_prover_internal.hpp.

Constructor & Destructor Documentation

◆ ProtogalaxyProverInternal()

template<class ProverInstance >
bb::ProtogalaxyProverInternal< ProverInstance >::ProtogalaxyProverInternal ( ExecutionTraceUsageTracker  trace_usage_tracker = ExecutionTraceUsageTracker{})
inline

Definition at line 87 of file protogalaxy_prover_internal.hpp.

Member Function Documentation

◆ accumulate_relation_univariates()

template<class ProverInstance >
template<size_t relation_idx = 0>
static BB_INLINE void bb::ProtogalaxyProverInternal< ProverInstance >::accumulate_relation_univariates ( TupleOfTuplesOfUnivariates &  univariate_accumulators,
const ExtendedUnivariatesType &  extended_univariates,
const UnivariateRelationParameters &  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
Parametersrelation parameters type
relation_idxThe index of the relation
Parameters
univariate_accumulators
extended_univariates
relation_parameters
scaling_factor

Definition at line 487 of file protogalaxy_prover_internal.hpp.

◆ batch_over_relations()

template<class ProverInstance >
static ExtendedUnivariateWithRandomization bb::ProtogalaxyProverInternal< ProverInstance >::batch_over_relations ( TupleOfTuplesOfUnivariatesNoOptimisticSkipping &  univariate_accumulators,
const UnivariateSubrelationSeparators &  alphas 
)
inlinestatic

Given the univariate accumulators and the batching challenges, compute the combiner by batching the subrelations.

univariate_accumulators contain the contributions from the entire trace for each folded subrelation. To complete the calculation of the combiner, we have to batch these contributions using the folded batching challenges.

Parameters
univariate_accumulators
alphas
Returns
ExtendedUnivariateWithRandomization

Definition at line 640 of file protogalaxy_prover_internal.hpp.

◆ compute_and_extend_alphas()

template<class ProverInstance >
static UnivariateSubrelationSeparators bb::ProtogalaxyProverInternal< ProverInstance >::compute_and_extend_alphas ( const ProverInstances &  instances)
inlinestatic

Combine the relation batching parameters (alphas) from each prover instance into a univariate for the combiner computation.

Note
Univariates are in Lagrange basis. Therefore, this function returns the folded batching challenges.

The ProverInstance is made of prover polynomials, relation parameters, and subrelations batching challenges: the alphas. As the alphas are part of the instance, they must be folded. This function arranges the alphas from the instances in a matrix where column i represents the alphas from the i-th instance to be folded and then defines a univariate for each row of the matrix by using the alphas in that row as coefficients. The univariates are extended up to length BATCHED_EXTENDED_LENGTH, which is the max degree of the \(f_i\)'s in the relation calculation.

Definition at line 748 of file protogalaxy_prover_internal.hpp.

◆ compute_combiner()

template<class ProverInstance >
ExtendedUnivariateWithRandomization bb::ProtogalaxyProverInternal< ProverInstance >::compute_combiner ( const ProverInstances &  instances,
const GateSeparatorPolynomial< FF > &  gate_separators,
const UnivariateRelationParameters &  relation_parameters,
const UnivariateSubrelationSeparators &  alphas,
TupleOfTuplesOfUnivariates &  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
Parameters
instances
gate_separators
relation_parameters
alphas
univariate_accumulators
Returns
ExtendedUnivariateWithRandomization

Definition at line 532 of file protogalaxy_prover_internal.hpp.

◆ compute_combiner_quotient()

template<class ProverInstance >
static Univariate< FF, BATCHED_EXTENDED_LENGTH, NUM_INSTANCES > bb::ProtogalaxyProverInternal< ProverInstance >::compute_combiner_quotient ( FF  perturbator_evaluation,
ExtendedUnivariateWithRandomization  combiner 
)
inlinestatic

Compute the combiner quotient defined as $K$ polynomial in the paper specialised for only folding two instances at once.

The combiner quotient is defined by the formula \(G(X) = F(\alpha) L_0(X) + Z(X) K(X)\). The polynomial \(Z(X)\) is the vanishing polynomial of the set 0, NUM_INSTANCES-1 = 1. Therefore, we cannot compute the value of \(K(X)\) on these values. We evaluate \(K(X)\) on NUM_INSTANCES = 2, ..., BATCHED_EXTENDED_LENGTH (the length of the combiner) and we return the univariate over this domain.

Definition at line 690 of file protogalaxy_prover_internal.hpp.

◆ compute_extended_relation_parameters()

template<class ProverInstance >
template<typename ExtendedRelationParameters >
static ExtendedRelationParameters bb::ProtogalaxyProverInternal< ProverInstance >::compute_extended_relation_parameters ( const ProverInstances &  instances)
inlinestatic

For each parameter, collect the value in each ProverInstance in a univariate and extend for use in the combiner computation.

Note
Univariates are in Lagrange basis. Therefore, this function returns the folded relation parameters.

The ProverInstance is made of prover polynomials, relation parameters, and subrelations batching challenges. As the relation parameters are part of the instance, they must be folded. This function arranges the relation parameters from the instances in a matrix where column i represents the relation parameters from the i-th instance to be folded and then defines a univariate for each row of the matrix by using the relation parameters in that row as coefficients. The univariates are extended up to length EXTENDED_LENGTH, which is the max length of a subrelation when the relation parameters are considered as variables.

Definition at line 720 of file protogalaxy_prover_internal.hpp.

◆ compute_num_threads()

template<class ProverInstance >
static size_t bb::ProtogalaxyProverInternal< ProverInstance >::compute_num_threads ( const size_t  domain_size)
inlinestatic

Determine number of threads for multithreading of perterbator/combiner operations.

Potentially uses fewer threads than are available to avoid distributing very small amounts of work

Parameters
domain_size
Returns
size_t

Definition at line 769 of file protogalaxy_prover_internal.hpp.

◆ compute_perturbator()

template<class ProverInstance >
Polynomial< FF > bb::ProtogalaxyProverInternal< ProverInstance >::compute_perturbator ( const std::shared_ptr< const ProverInstance > &  accumulator,
const std::vector< FF > &  deltas 
)
inline

Construct the perturbator polynomial F(X) in coefficient form from the accumulator resulted from a previous round of Protogalaxy.

Definition at line 421 of file protogalaxy_prover_internal.hpp.

◆ compute_row_evaluations()

template<class ProverInstance >
Polynomial< FF > bb::ProtogalaxyProverInternal< ProverInstance >::compute_row_evaluations ( const ProverPolynomials &  polynomials,
const SubrelationSeparators &  alphas,
const RelationParameters< FF > &  relation_parameters 
)
inline

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).

When folding Mega prover instances, one of the relations is linearly dependent. We define such relations as acting on the entire execution trace and hence requiring to be accumulated separately as we iterate over each row. At the end of the function, the linearly dependent contribution is accumulated at index 0 representing the sum f_0(ω) + α_j*g(ω) where f_0 represents the full honk evaluation at row 0, g(ω) is the linearly dependent subrelation and α_j is its corresponding batching challenge.

Definition at line 183 of file protogalaxy_prover_internal.hpp.

◆ compute_vanishing_polynomial_and_lagranges()

template<class ProverInstance >
static std::pair< typename ProverInstance::FF, std::array< typename ProverInstance::FF, NUM_INSTANCES > > bb::ProtogalaxyProverInternal< ProverInstance >::compute_vanishing_polynomial_and_lagranges ( const FF &  challenge)
inlinestatic

Compute the vanishing polynomial \(Z(X) = X * (X - 1)\) and Lagranges \(L_0(X) = 1 - X, L_1(X) = X\) at the challenge.

Definition at line 670 of file protogalaxy_prover_internal.hpp.

◆ construct_coefficients_tree()

template<class ProverInstance >
static std::vector< FF > bb::ProtogalaxyProverInternal< ProverInstance >::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 
)
inlinestatic

Non-recursively compute the parent nodes of each level in the tree, starting from the leaves.

MATHEMATICAL SPECIFICATION

Inputs:

  • betas: β = (β₀, β₁, ..., βₖ₋₁) - gate challenge vector
  • deltas: δ = (δ₀, δ₁, ..., δₖ₋₁) - delta challenge vector
  • current_level_buffer: Coefficients from previous level (flat buffer)
  • current_width: Number of nodes at current level
  • current_degree: Polynomial degree + 1 (number of coefficients per node)

Output: F(X) = Σᵢ fᵢXⁱ - perturbator polynomial coefficient vector

Algorithm: Binary Tree Construction (Iterative)

Level ℓ (General Case): For parent node p ∈ [0, n/2ℓ) with children at 2p and 2p+1:

Pℓ[p](X) = Pℓ₋₁[2p](X) + Pℓ₋₁[2p+1](X) · (βℓ + δℓX)

In Lagrange basis: Pℓ[p][d] = Pℓ₋₁[2p][d] + Pℓ₋₁[2p+1][d] · βℓ for d ∈ [0, ℓ+1] Pℓ[p][d+1] += Pℓ₋₁[2p+1][d] · δℓ for d ∈ [0, ℓ+1]

Note: Pℓ[p] has degree ℓ+1 (requires ℓ+2 coefficients)

Flat Buffer Layout:

At level ℓ with w nodes and stride s = ℓ+2:

  • Parent p offset: p_offset = p · (ℓ+2)
  • Left child offset: l_offset = (2p) · (ℓ+1)
  • Right child offset: r_offset = (2p+1) · (ℓ+1)

Complexity:

  • Time: O(n) - each leaf combined once per level
  • Space: O(n) - two buffers with alternating roles

  • Parallelism: n/2ℓ independent tasks per level

    This iterative implementation uses flat contiguous buffers that alternate roles as source and destination, enabling efficient parallel initialization and better cache locality.

Definition at line 265 of file protogalaxy_prover_internal.hpp.

◆ construct_perturbator_coefficients()

template<class ProverInstance >
static std::vector< FF > bb::ProtogalaxyProverInternal< ProverInstance >::construct_perturbator_coefficients ( std::span< const FF >  betas,
std::span< const FF >  deltas,
const Polynomial< FF > &  full_honk_evaluations 
)
inlinestatic

Construct the perturbator polynomial F(X) coefficients in O(n) time using binary tree reduction.

MATHEMATICAL SPECIFICATION

Inputs:

  • ℰ = {e₀, e₁, ..., eₙ₋₁}: Full Honk relation evaluations (size n = 2^k)
  • β = (β₀, β₁, ..., βₖ₋₁): Gate challenge vector
  • δ = (δ₀, δ₁, ..., δₖ₋₁): Delta challenge vector

Output: F(X) = Σᵢ fᵢXⁱ - perturbator polynomial of degree k

Algorithm (following Claim 4.4 from Protogalaxy paper):

Level 0 (Leaves): L₀[i] = eᵢ for i ∈ [0, n)

Level 1 (First Combination): For parent p ∈ [0, n/2) with children at 2p and 2p+1: P₁[p](X) = e₂ₚ + e₂ₚ₊₁ · (β₀ + δ₀X)

Expanding to coefficients: P₁[p][0] = e₂ₚ + e₂ₚ₊₁ · β₀ P₁[p][1] = e₂ₚ₊₁ · δ₀

General Level ℓ ∈ [1, k): For parent p with children from previous level: Pℓ[p](X) = Pℓ₋₁[2p](X) + Pℓ₋₁[2p+1](X) · (βℓ + δℓX)

Final Result: F(X) = Pₖ[0](X) (root node after k levels)

Tree Structure Example (n=8): Level 0: e₀ e₁ e₂ e₃ e₄ e₅ e₆ e₇ (degree 0, 8 nodes) └─┬┘ └─┬┘ └─┬┘ └─┬┘ ↓β₀ ↓β₀ ↓β₀ ↓β₀ Level 1: P₁[0] P₁[1] P₁[2] P₁[3] (degree 1, 4 nodes) └────┬────┘ └────┬────┘ ↓β₁ ↓β₁ Level 2: P₂[0] P₂[1] (degree 2, 2 nodes) └──────┬──────┘ ↓β₂ Level 3: P₃[0] (degree 3, 1 node) ↓ F(X)

Properties:

  • Degree growth: At level ℓ, polynomials have degree ℓ
  • Tree reduction: Each level halves the number of nodes

  • Zeroth coefficient: F(0) = f₀ equals the target sum

    This implementation is non-recursive and uses flat contiguous buffers with alternating roles, enabling efficient parallel initialization and minimizing memory allocations.

Definition at line 390 of file protogalaxy_prover_internal.hpp.

◆ deoptimize_univariates()

template<class ProverInstance >
template<typename TupleOfTuplesOfUnivariatePossiblyOptimistic >
static TupleOfTuplesOfUnivariatesNoOptimisticSkipping bb::ProtogalaxyProverInternal< ProverInstance >::deoptimize_univariates ( const TupleOfTuplesOfUnivariatePossiblyOptimistic &  tup)
inlinestatic

Convert univariates from optimized form to regular.

We need to convert before we batch relations, since optimized versions don't have enough information to extend the univariates to maximum length

Definition at line 608 of file protogalaxy_prover_internal.hpp.

◆ extend_univariates()

template<class ProverInstance >
template<size_t skip_count = 0>
static BB_INLINE void bb::ProtogalaxyProverInternal< ProverInstance >::extend_univariates ( ExtendedUnivariatesType &  extended_univariates,
const ProverInstances &  instances,
const size_t  row_idx 
)
inlinestatic

Prepare a univariate polynomial for relation execution in one step of the combiner construction.

For a fixed prover polynomial index, extract that polynomial from each key in ProverInstances. From each polynomial, extract the value at row_idx. Use these values to create a univariate polynomial, and then extend (i.e., compute additional evaluations at adjacent domain values) as needed.

Definition at line 457 of file protogalaxy_prover_internal.hpp.

◆ process_subrelation_evaluations()

template<class ProverInstance >
static FF bb::ProtogalaxyProverInternal< ProverInstance >::process_subrelation_evaluations ( const RelationEvaluations &  evals,
const SubrelationSeparators &  challenges,
FF &  linearly_dependent_contribution 
)
inlinestatic

Scale all linearly independent subrelations evaluations by challenges ('alphas').

Note that this is not done for linearly dependent subrelation, because their evaluation is not computed on a specific row but rather on the entire execution trace.

Parameters
evalsThe evaluations of all subrelations on some row
challengesThe 'alpha' challenges used to batch the subrelations (we use separate challenges rather than a single alpha raised to powers to avoid an unsustainable degree increase in the combiner polynomial)
linearly_dependent_contributionAn accumulator for values of the linearly-dependent (i.e., 'whole-trace') subrelations
Returns
FF The evaluation of the linearly-independent (i.e., 'per-row') subrelations

Definition at line 146 of file protogalaxy_prover_internal.hpp.

◆ row_to_univariates()

template<class ProverInstance >
template<size_t skip_count = 0>
static auto bb::ProtogalaxyProverInternal< ProverInstance >::row_to_univariates ( const ProverInstances &  instances,
size_t  row_idx 
)
inlinestatic

Constructs univariates that interpolate the values of each instance across a given row.

The returned univariates are over the domain 0, .., EXTENDED_LENGTH - 1.

Template Parameters
skip_countThe number of evaluations to skip in the returned univariates. Used only if not using short monomials.
Parameters
row_idxA fixed row position in several execution traces
Returns
The univariates whose extensions will be used to construct the combiner.

Definition at line 101 of file protogalaxy_prover_internal.hpp.

Member Data Documentation

◆ BATCHED_EXTENDED_LENGTH

template<class ProverInstance >
constexpr size_t bb::ProtogalaxyProverInternal< ProverInstance >::BATCHED_EXTENDED_LENGTH = computed_batched_extended_length<Flavor>()
staticconstexpr

Definition at line 38 of file protogalaxy_prover_internal.hpp.

◆ EXTENDED_LENGTH

template<class ProverInstance >
constexpr size_t bb::ProtogalaxyProverInternal< ProverInstance >::EXTENDED_LENGTH = computed_extended_length<Flavor>()
staticconstexpr

Definition at line 37 of file protogalaxy_prover_internal.hpp.

◆ NUM_SUBRELATIONS

template<class ProverInstance >
constexpr size_t bb::ProtogalaxyProverInternal< ProverInstance >::NUM_SUBRELATIONS = Flavor::NUM_SUBRELATIONS
staticconstexpr

Definition at line 39 of file protogalaxy_prover_internal.hpp.

◆ trace_usage_tracker

template<class ProverInstance >
ExecutionTraceUsageTracker bb::ProtogalaxyProverInternal< ProverInstance >::trace_usage_tracker

Definition at line 85 of file protogalaxy_prover_internal.hpp.

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