- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
A purely static class (never add state to this!) consisting of functions used by the Protogalaxy prover. More...
#include <protogalaxy_prover_internal.hpp>
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 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 | |
| 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. | |
| template<size_t skip_count = 0> | |
| 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. | |
| 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) |
| 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. | |
| template<typename ExtendedRelationParameters > | |
| 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. | |
Public Attributes | |
| ExecutionTraceUsageTracker | trace_usage_tracker |
Static Public Attributes | |
| static constexpr size_t | NUM_KEYS = DeciderProvingKeys_::NUM |
| static constexpr size_t | NUM_SUBRELATIONS = DeciderPKs::NUM_SUBRELATIONS |
A purely static class (never add state to this!) consisting of functions used by the Protogalaxy prover.
| DeciderProvingKeys_ |
Definition at line 25 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::AllValues = typename Flavor::AllValues |
Definition at line 34 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::DeciderPK = typename DeciderPKs::DeciderPK |
Definition at line 30 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::DeciderPKs = DeciderProvingKeys_ |
Definition at line 27 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::ExtendedUnivariate = Univariate<FF, (Flavor::MAX_TOTAL_RELATION_LENGTH - 1) * (DeciderPKs::NUM - 1) + 1> |
Definition at line 47 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::ExtendedUnivariates = typename Flavor::template ProverUnivariatesWithOptimisticSkipping<ExtendedUnivariate::LENGTH, DeciderPKs::NUM - 1> |
Definition at line 75 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::ExtendedUnivariatesType = std::conditional_t<Flavor::USE_SHORT_MONOMIALS, ShortUnivariates, ExtendedUnivariates> |
Definition at line 79 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::ExtendedUnivariateWithRandomization = Univariate<FF, (Flavor::MAX_TOTAL_RELATION_LENGTH - 1 + DeciderPKs::NUM - 1) * (DeciderPKs::NUM - 1) + 1> |
Definition at line 50 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::FF = typename Flavor::FF |
Definition at line 29 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::Flavor = typename DeciderPKs::Flavor |
Definition at line 28 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::ProverPolynomials = typename Flavor::ProverPolynomials |
Definition at line 32 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::RelationEvaluations = decltype(create_tuple_of_arrays_of_values<typename Flavor::Relations>()) |
Definition at line 86 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::Relations = typename Flavor::Relations |
Definition at line 33 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::RelationUtils = bb::RelationUtils<Flavor> |
Definition at line 31 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::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.
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%
Definition at line 73 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::SubrelationSeparators = typename Flavor::SubrelationSeparators |
Definition at line 35 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::TupleOfTuplesOfUnivariates = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariates<DeciderPKs::NUM> |
Definition at line 82 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::TupleOfTuplesOfUnivariatesNoOptimisticSkipping = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariatesNoOptimisticSkipping<DeciderPKs::NUM> |
Definition at line 83 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::UnivariateRelationParameters = bb::RelationParameters<Univariate<FF, DeciderProvingKeys_::EXTENDED_LENGTH, 0, NUM_KEYS - 1> > |
Definition at line 39 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::UnivariateRelationParametersNoOptimisticSkipping = bb::RelationParameters<Univariate<FF, DeciderProvingKeys_::EXTENDED_LENGTH> > |
Definition at line 37 of file protogalaxy_prover_internal.hpp.
| using bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::UnivariateSubrelationSeparators = std::array<Univariate<FF, DeciderPKs::BATCHED_EXTENDED_LENGTH>, Flavor::NUM_SUBRELATIONS - 1> |
Definition at line 41 of file protogalaxy_prover_internal.hpp.
|
inline |
Definition at line 92 of file protogalaxy_prover_internal.hpp.
|
inlinestatic |
Add the value of each relation over univariates to an appropriate accumulator.
| 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 |
| univariate_accumulators | |
| extended_univariates | |
| relation_parameters | |
| scaling_factor |
Definition at line 309 of file protogalaxy_prover_internal.hpp.
|
inlinestatic |
Definition at line 450 of file protogalaxy_prover_internal.hpp.
|
inlinestatic |
Combine the relation batching parameters (alphas) from each decider proving key into a univariate for using in the combiner computation.
Definition at line 564 of file protogalaxy_prover_internal.hpp.
|
inline |
Definition at line 414 of file protogalaxy_prover_internal.hpp.
|
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.
| skip_zero_computations | whether to use the optimization that skips computing zero. |
param gate_separators
Definition at line 351 of file protogalaxy_prover_internal.hpp.
|
inlinestatic |
Compute the combiner quotient defined as $K$ polynomial in the paper.
Definition at line 507 of file protogalaxy_prover_internal.hpp.
|
inlinestatic |
For each parameter, collect the value in each decider pvogin key in a univariate and extend for use in the combiner compute.
Definition at line 542 of file protogalaxy_prover_internal.hpp.
|
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
| domain_size |
Definition at line 588 of file protogalaxy_prover_internal.hpp.
|
inline |
Construct the power perturbator polynomial F(X) in coefficient form from the accumulator.
Definition at line 247 of file protogalaxy_prover_internal.hpp.
|
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 Honk - from the Plonk paper, DO NOT confuse with α in Protogalaxy).
When folding Mega decider proving keys, 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 146 of file protogalaxy_prover_internal.hpp.
|
inlinestatic |
Definition at line 476 of file protogalaxy_prover_internal.hpp.
|
inlinestatic |
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.
Definition at line 190 of file protogalaxy_prover_internal.hpp.
|
inlinestatic |
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.
Definition at line 226 of file protogalaxy_prover_internal.hpp.
|
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 430 of file protogalaxy_prover_internal.hpp.
|
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 DeciderProvingKeys. 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 278 of file protogalaxy_prover_internal.hpp.
|
inlinestatic |
A scale subrelations evaluations by challenges ('alphas') and part of the linearly dependent relation evaluation(s).
Note that a linearly dependent subrelation is not computed on a specific row but rather on the entire execution trace.
| evals | The evaluations of all subrelations on some row |
| challenges | The 'alpha' challenges used to batch the subrelations |
| linearly_dependent_contribution | An accumulator for values of the linearly-dependent (i.e., 'whole-trace') subrelations |
Definition at line 109 of file protogalaxy_prover_internal.hpp.
|
staticconstexpr |
Definition at line 36 of file protogalaxy_prover_internal.hpp.
|
staticconstexpr |
Definition at line 88 of file protogalaxy_prover_internal.hpp.
| ExecutionTraceUsageTracker bb::ProtogalaxyProverInternal< DeciderProvingKeys_ >::trace_usage_tracker |
Definition at line 90 of file protogalaxy_prover_internal.hpp.
1.9.8