|
|
using | ProverInstances = ProverInstances_ |
| |
|
using | Flavor = typename ProverInstances::Flavor |
| |
|
using | Transcript = typename Flavor::Transcript |
| |
|
using | FF = typename Flavor::FF |
| |
|
using | Instance = typename ProverInstances::Instance |
| |
|
using | Utils = barretenberg::RelationUtils< Flavor > |
| |
|
using | RowEvaluations = typename Flavor::AllValues |
| |
|
using | ProverPolynomials = typename Flavor::ProverPolynomials |
| |
|
using | Relations = typename Flavor::Relations |
| |
|
using | AlphaType = typename ProverInstances::AlphaType |
| |
|
using | VerificationKey = typename Flavor::VerificationKey |
| |
|
using | CommitmentKey = typename Flavor::CommitmentKey |
| |
|
using | WitnessCommitments = typename Flavor::WitnessCommitments |
| |
|
using | Commitment = typename Flavor::Commitment |
| |
|
using | BaseUnivariate = Univariate< FF, ProverInstances::NUM > |
| |
|
using | ExtendedUnivariate = Univariate< FF,(Flavor::MAX_TOTAL_RELATION_LENGTH - 1) *(ProverInstances::NUM - 1)+1 > |
| |
|
using | ExtendedUnivariateWithRandomization = Univariate< FF,(Flavor::MAX_TOTAL_RELATION_LENGTH - 1+ProverInstances::NUM - 1) *(ProverInstances::NUM - 1)+1 > |
| |
|
using | ExtendedUnivariates = typename Flavor::template ProverUnivariates< ExtendedUnivariate::LENGTH > |
| |
|
using | TupleOfTuplesOfUnivariates = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariates< ProverInstances::NUM > |
| |
|
using | RelationEvaluations = typename Flavor::TupleOfArraysOfValues |
| |
|
|
| ProtoGalaxyProver_ (const std::vector< std::shared_ptr< Instance > > &insts, const std::shared_ptr< CommitmentKey > &commitment_key) |
| |
|
void | prepare_for_folding () |
| | Prior to folding, we need to finalize the given instances and add all their public data ϕ to the transcript, labelled by their corresponding instance index for domain separation. TODO(https://github.com/AztecProtocol/barretenberg/issues/795):The rounds prior to actual proving/folding are common between decider and folding verifier and could be somehow shared so we do not duplicate code so much.
|
| |
| void | send_accumulator (std::shared_ptr< Instance >, const std::string &domain_separator) |
| | Send the public data of an accumulator, i.e. a relaxed instance, to the verifier (ϕ in the paper).
|
| |
| void | finalise_and_send_instance (std::shared_ptr< Instance >, const std::string &domain_separator) |
| | For each instance produced by a circuit, prior to folding, we need to complete the computation of its prover polynomials, commit to witnesses and generate the relation parameters as well as send the public data ϕ of an instance to the verifier.
|
| |
| FoldingResult< Flavor > | fold_instances () |
| | Run the folding prover protocol to produce a new accumulator and a folding proof to be verified by the folding verifier.
|
| |
|
std::shared_ptr< Instance > | get_accumulator () |
| |
| void | extend_univariates (ExtendedUnivariates &extended_univariates, const ProverInstances &instances, const size_t row_idx) |
| | Prepare a univariate polynomial for relation execution in one step of the main loop in folded instance construction.
|
| |
|
template<typename Parameters , size_t relation_idx = 0> |
| void | accumulate_relation_univariates (TupleOfTuplesOfUnivariates &univariate_accumulators, const ExtendedUnivariates &extended_univariates, const Parameters &relation_parameters, const FF &scaling_factor) |
| |
| ExtendedUnivariateWithRandomization | compute_combiner (const ProverInstances &instances, const std::vector< FF > &pow_betas_star) |
| | Compute the combiner polynomial $G$ in the Protogalaxy paper.
|
| |
| std::shared_ptr< Instance > | compute_next_accumulator (ProverInstances &instances, Univariate< FF, ProverInstances::BATCHED_EXTENDED_LENGTH, ProverInstances::NUM > &combiner_quotient, const FF &challenge, const FF &compressed_perturbator) |
| | Compute the next accumulator (ϕ*, ω*\vec{\beta*}, e*), send the public data ϕ* and the folding parameters (\vec{\beta*}, e*) to the verifier and return the complete accumulator.
|
| |
|
|
static std::vector< FF > | compute_pow_polynomial_at_values (const std::vector< FF > &betas, const size_t instance_size) |
| | Given a vector \vec{\beta} of values, compute the pow polynomial on these values as defined in the paper.
|
| |
|
static std::vector< FF > | compute_round_challenge_pows (const size_t log_instance_size, const FF &round_challenge) |
| | For a new round challenge δ at each iteration of the ProtoGalaxy protocol, compute the vector [δ, δ^2,..., δ^t] where t = logn and n is the size of the instance.
|
| |
|
static std::vector< FF > | update_gate_challenges (const FF perturbator_challenge, const std::vector< FF > &gate_challenges, const std::vector< FF > &round_challenges) |
| |
|
static std::vector< FF > | compute_full_honk_evaluations (const ProverPolynomials &instance_polynomials, const FF &alpha, const RelationParameters< FF > &relation_parameters) |
| | Compute the values of the full Honk relation at each row in the execution trace, f_i(ω) in the ProtoGalaxy paper, given the evaluations of all the prover polynomials and α (the parameter that helps establish each subrelation is independently valid in Honk - from the Plonk paper, DO NOT confuse with α in ProtoGalaxy),.
|
| |
|
static std::vector< FF > | construct_coefficients_tree (const std::vector< FF > &betas, const std::vector< FF > &deltas, const std::vector< std::vector< FF > > &prev_level_coeffs, size_t level=1) |
| | Recursively compute the parent nodes of each level in there, 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 (const std::vector< FF > &betas, const std::vector< FF > &deltas, const std::vector< 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 Polynomial< FF > | compute_perturbator (const std::shared_ptr< Instance > accumulator, const std::vector< FF > &deltas) |
| | Construct the power perturbator polynomial F(X) in coefficient form from the accumulator, representing the relaxed instance.
|
| |
|
static ExtendedUnivariateWithRandomization | batch_over_relations (TupleOfTuplesOfUnivariates univariate_accumulators, AlphaType alpha) |
| |
| static Univariate< FF, ProverInstances::BATCHED_EXTENDED_LENGTH, ProverInstances::NUM > | compute_combiner_quotient (FF compressed_perturbator, ExtendedUnivariateWithRandomization combiner) |
| | Compute the combiner quotient defined as $K$ polynomial in the paper.
|
| |
| static void | combine_relation_parameters (ProverInstances &instances) |
| | Combine each relation parameter, in part, from all the instances into univariates, used in the computation of combiner.
|
| |
| static void | combine_alpha (ProverInstances &instances) |
| | Combine the relation batching parameter (named alpha) from each instance into a univariate, used in the computation of combiner.
|
| |
