eccvm_prover.cpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Planned, auditors: [], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#include "eccvm_prover.hpp"
#include "barretenberg/commitment_schemes/claim.hpp"
#include "barretenberg/commitment_schemes/commitment_key.hpp"
#include "barretenberg/commitment_schemes/shplonk/shplemini.hpp"
#include "barretenberg/commitment_schemes/shplonk/shplonk.hpp"
#include "barretenberg/commitment_schemes/small_subgroup_ipa/small_subgroup_ipa.hpp"
#include "barretenberg/common/bb_bench.hpp"
#include "barretenberg/common/ref_array.hpp"
#include "barretenberg/honk/library/grand_product_library.hpp"
#include "barretenberg/honk/proof_system/logderivative_library.hpp"
#include "barretenberg/relations/permutation_relation.hpp"
#include "barretenberg/sumcheck/sumcheck.hpp"
 
namespace bb {
 
ECCVMProver::ECCVMProver(CircuitBuilder& builder, const std::shared_ptr<Transcript>& transcript)
    : transcript(transcript)
{
    BB_BENCH_NAME("ECCVMProver(CircuitBuilder&)");
 
    // TODO(https://github.com/AztecProtocol/barretenberg/issues/939): Remove redundancy between
    // ProvingKey/ProverPolynomials and update the model to reflect what's done in all other proving systems.
 
    // Construct the proving key; populates all polynomials except for witness polys
    key = std::make_shared<ProvingKey>(builder);
 
    key->commitment_key = CommitmentKey(key->circuit_size);
}
 
void ECCVMProver::execute_preamble_round()
{
    using VerificationKey = Flavor::VerificationKey;
 
    // Fiat-Shamir the vk hash
    VerificationKey vk;
    typename Flavor::BF vk_hash = vk.get_hash();
    transcript->add_to_hash_buffer("vk_hash", vk_hash);
    vinfo("ECCVM vk hash in prover: ", vk_hash);
}
 
void ECCVMProver::execute_wire_commitments_round()
{
    BB_BENCH_NAME("ECCVMProver::execute_wire_commitments_round");
 
    const size_t circuit_size = key->circuit_size;
 
    // Create and commit to Gemini masking polynomial (for ZK-PCS)
    key->polynomials.gemini_masking_poly = Polynomial::random(circuit_size);
    auto masking_commitment = key->commitment_key.commit(key->polynomials.gemini_masking_poly);
    transcript->send_to_verifier("Gemini:masking_poly_comm", masking_commitment);
 
    auto batch = key->commitment_key.start_batch();
    for (const auto& [wire, label] : zip_view(key->polynomials.get_wires(), commitment_labels.get_wires())) {
        batch.add_to_batch(wire, label, Flavor::CommitmentLabels::wire_has_high_duplicate_density(label));
    }
    batch.commit_and_send_to_verifier(transcript);
}
 
void ECCVMProver::execute_log_derivative_commitments_round()
{
    BB_BENCH_NAME("ECCVMProver::execute_log_derivative_commitments_round");
 
    // Compute and add beta to relation parameters
    auto [beta, gamma] = transcript->template get_challenges<FF>(std::array<std::string, 2>{ "beta", "gamma" });
 
    // TODO(#583)(@zac-williamson): fix Transcript to be able to generate more than 2 challenges per round! oof.
    auto beta_sqr = beta * beta;
    auto beta_quartic = beta_sqr * beta_sqr;
    relation_parameters.gamma = gamma;
    relation_parameters.beta = beta;
    relation_parameters.beta_sqr = beta_sqr;
    relation_parameters.beta_cube = beta_sqr * beta;
    relation_parameters.beta_quartic = beta_quartic;
    // `eccvm_set_permutation_delta` is used in the set membership gadget in eccvm/ecc_set_relation.hpp, specifically to
    // constrain (pc, round, wnaf_slice) to match between the MSM table and the Precomputed table. The number of rows we
    // add per short scalar `mul` is slightly less in the Precomputed table as in the MSM table, so to get the
    // permutation argument to work out, when `precompute_select == 0`, we must implicitly _remove_ (0, 0, 0) as a tuple
    // on the wNAF side. This corresponds to dividing by
    // (γ+t·β⁴)·(γ+β²+t·β⁴)·(γ+2β²+t·β⁴)·(γ+3β²+t·β⁴), where t = FIRST_TERM_TAG.
    auto first_term_tag = beta_quartic; // FIRST_TERM_TAG (= 1) * beta_quartic
    relation_parameters.eccvm_set_permutation_delta = (gamma + first_term_tag) * (gamma + beta_sqr + first_term_tag) *
                                                      (gamma + beta_sqr + beta_sqr + first_term_tag) *
                                                      (gamma + beta_sqr + beta_sqr + beta_sqr + first_term_tag);
    relation_parameters.eccvm_set_permutation_delta = relation_parameters.eccvm_set_permutation_delta.invert();
    // Compute inverse polynomial for our logarithmic-derivative lookup method
    // Skip the disabled head region to preserve masking values
    compute_logderivative_inverse<typename Flavor::FF,
                                  typename Flavor::LookupRelation,
                                  typename Flavor::ProverPolynomials,
                                  true>(key->polynomials, relation_parameters, Flavor::TRACE_OFFSET);
    auto& li = key->polynomials.lookup_inverses;
    transcript->send_to_verifier(commitment_labels.lookup_inverses, key->commitment_key.commit(li));
}
 
void ECCVMProver::execute_grand_product_computation_round()
{
    BB_BENCH_NAME("ECCVMProver::execute_grand_product_computation_round");
    // Compute permutation grand product (starts after disabled head region via gp_start)
    compute_grand_products<Flavor>(key->polynomials, relation_parameters);
    auto& zp = key->polynomials.z_perm;
    // set has_duplicates_hint for Z_PERM (empty row = duplicate Z value)
    transcript->send_to_verifier(commitment_labels.z_perm,
                                 key->commitment_key.commit(zp, /*has_duplicates_hint=*/true));
}
 
void ECCVMProver::execute_relation_check_rounds()
{
    BB_BENCH_NAME("ECCVMProver::execute_relation_check_rounds");
    using Sumcheck = SumcheckProver<Flavor>;
 
    // Each linearly independent subrelation contribution is multiplied by `alpha^i`, where
    //  i = 0, ..., NUM_SUBRELATIONS- 1.
    FF alpha = transcript->template get_challenge<FF>("Sumcheck:alpha");
 
    std::vector<FF> gate_challenges =
        transcript->template get_dyadic_powers_of_challenge<FF>("Sumcheck:gate_challenge", CONST_ECCVM_LOG_N);
 
    Sumcheck sumcheck(key->circuit_size,
                      key->polynomials,
                      transcript,
                      alpha,
                      gate_challenges,
                      relation_parameters,
                      CONST_ECCVM_LOG_N);
 
    zk_sumcheck_data = ZKData(key->log_circuit_size, transcript, key->commitment_key);
 
    sumcheck_output = sumcheck.prove(zk_sumcheck_data);
}
 
void ECCVMProver::execute_pcs_rounds()
{
    BB_BENCH_NAME("ECCVMProver::execute_pcs_rounds");
    using Curve = typename Flavor::Curve;
    using Shplemini = ShpleminiProver_<Curve>;
    using Shplonk = ShplonkProver_<Curve>;
    using OpeningClaim = ProverOpeningClaim<Curve>;
    using PolynomialBatcher = GeminiProver_<Curve>::PolynomialBatcher;
 
    SmallSubgroupIPA small_subgroup_ipa_prover(zk_sumcheck_data,
                                               sumcheck_output.challenge,
                                               sumcheck_output.claimed_libra_evaluation,
                                               transcript,
                                               key->commitment_key);
    small_subgroup_ipa_prover.prove();
 
    // Execute the Shplemini (Gemini + Shplonk) protocol to produce a univariate opening claim for the multilinear
    // evaluations produced by Sumcheck
    PolynomialBatcher polynomial_batcher(key->circuit_size);
    polynomial_batcher.set_unshifted(key->polynomials.get_unshifted());
    polynomial_batcher.set_to_be_shifted_by_one(key->polynomials.get_to_be_shifted());
 
    OpeningClaim multivariate_to_univariate_opening_claim =
        Shplemini::prove(key->circuit_size,
                         polynomial_batcher,
                         sumcheck_output.challenge,
                         key->commitment_key,
                         transcript,
                         small_subgroup_ipa_prover.get_witness_polynomials(),
                         sumcheck_output.round_univariates,
                         sumcheck_output.round_univariate_evaluations);
 
    ECCVMProver::compute_translation_opening_claims();
 
    opening_claims.back() = std::move(multivariate_to_univariate_opening_claim);
 
    // Reduce the opening claims to a single opening claim via Shplonk
    // IPA proving is performed externally
    batch_opening_claim = Shplonk::prove(key->commitment_key, opening_claims, transcript);
}
 
ECCVMProver::Proof ECCVMProver::export_proof()
{
    return { transcript->export_proof() };
}
 
std::pair<ECCVMProver::Proof, ECCVMProver::OpeningClaim> ECCVMProver::construct_proof()
{
    BB_BENCH_NAME("ECCVMProver::construct_proof");
 
    execute_preamble_round();
    execute_wire_commitments_round();
    execute_log_derivative_commitments_round();
    execute_grand_product_computation_round();
    execute_relation_check_rounds();
    execute_pcs_rounds();
 
    return { export_proof(), batch_opening_claim };
}
 
void ECCVMProver::compute_translation_opening_claims()
{
    // Used to capture the batched evaluation of unmasked `translation_polynomials` while preserving ZK
    using SmallIPA = SmallSubgroupIPAProver<Flavor>;
 
    // Initialize SmallSubgroupIPA structures
    std::array<std::string, NUM_SMALL_IPA_EVALUATIONS> evaluation_labels;
    std::array<FF, NUM_SMALL_IPA_EVALUATIONS> evaluation_points;
 
    RefArray translation_polynomials{ key->polynomials.transcript_op,
                                      key->polynomials.transcript_Px,
                                      key->polynomials.transcript_Py,
                                      key->polynomials.transcript_z1,
                                      key->polynomials.transcript_z2 };
 
    // Extract the masking terms of `translation_polynomials`, concatenate them in the Lagrange basis over SmallSubgroup
    // H, mask the resulting polynomial, and commit to it
    TranslationData<Transcript> translation_data(translation_polynomials, transcript, key->commitment_key);
 
    // Get a challenge to evaluate the `translation_polynomials` as univariates
    evaluation_challenge_x = transcript->template get_challenge<FF>("Translation:evaluation_challenge_x");
 
    // Evaluate `translation_polynomial` as univariates and add their evaluations at x to the transcript
    for (auto [eval, poly, label] :
         zip_view(translation_evaluations.get_all(), translation_polynomials, translation_evaluations.labels)) {
        eval = poly.evaluate(evaluation_challenge_x);
        transcript->send_to_verifier(label, eval);
    }
 
    // Get another challenge to batch the evaluations of the transcript polynomials
    batching_challenge_v = transcript->template get_challenge<FF>("Translation:batching_challenge_v");
 
    SmallIPA translation_masking_term_prover(
        translation_data, evaluation_challenge_x, batching_challenge_v, transcript, key->commitment_key);
    translation_masking_term_prover.prove();
 
    // Get the challenge to check evaluations of the SmallSubgroupIPA witness polynomials
    FF small_ipa_evaluation_challenge =
        transcript->template get_challenge<FF>("Translation:small_ipa_evaluation_challenge");
 
    // Populate SmallSubgroupIPA opening claims:
    // 1. Get the evaluation points and labels
    evaluation_points = translation_masking_term_prover.evaluation_points(small_ipa_evaluation_challenge);
    evaluation_labels = translation_masking_term_prover.evaluation_labels();
    // 2. Compute the evaluations of witness polynomials at corresponding points, send them to the verifier, and create
    // the opening claims
    for (size_t idx = 0; idx < NUM_SMALL_IPA_EVALUATIONS; idx++) {
        auto witness_poly = translation_masking_term_prover.get_witness_polynomials()[idx];
        const FF evaluation = witness_poly.evaluate(evaluation_points[idx]);
        transcript->send_to_verifier(evaluation_labels[idx], evaluation);
        opening_claims[idx] = { .polynomial = witness_poly, .opening_pair = { evaluation_points[idx], evaluation } };
    }
 
    // Compute the opening claim for the masked evaluations of `op`, `Px`, `Py`, `z1`, and `z2` at
    // `evaluation_challenge_x` batched by the powers of `batching_challenge_v`.
    Polynomial batched_translation_univariate{ key->circuit_size };
    FF batched_translation_evaluation{ 0 };
    FF batching_scalar = FF(1);
    for (auto [polynomial, eval] : zip_view(translation_polynomials, translation_evaluations.get_all())) {
        batched_translation_univariate.add_scaled(polynomial, batching_scalar);
        batched_translation_evaluation += eval * batching_scalar;
        batching_scalar *= batching_challenge_v;
    }
 
    // Add the batched claim to the array of SmallSubgroupIPA opening claims.
    opening_claims[NUM_SMALL_IPA_EVALUATIONS] = { batched_translation_univariate,
                                                  { evaluation_challenge_x, batched_translation_evaluation } };
}
 
} // namespace bb