batched_honk_translator_prover.cpp

Go to the documentation of this file.

#include "batched_honk_translator_prover.hpp"
 
#include "barretenberg/commitment_schemes/gemini/gemini.hpp"
#include "barretenberg/commitment_schemes/shplonk/shplemini.hpp"
#include "barretenberg/commitment_schemes/small_subgroup_ipa/small_subgroup_ipa.hpp"
#include "barretenberg/polynomials/gate_separator.hpp"
#include "barretenberg/polynomials/row_disabling_polynomial.hpp"
#include "barretenberg/translator_vm/translator_prover.hpp"
 
namespace bb {
 
BatchedHonkTranslatorProver::BatchedHonkTranslatorProver(std::shared_ptr<MegaZKProverInstance> mega_zk_instance,
                                                         std::shared_ptr<MegaZKVK> mega_zk_vk,
                                                         std::shared_ptr<Transcript> transcript)
    : mega_zk_inst(std::move(mega_zk_instance))
    , mega_zk_vk(std::move(mega_zk_vk))
    , transcript(std::move(transcript))
{}
 
void BatchedHonkTranslatorProver::execute_mega_zk_oink()
{
    OinkProver<MegaZKFlavor> oink_prover(mega_zk_inst, mega_zk_vk, transcript);
    oink_prover.prove(/*emit_alpha=*/false);
}
 
void BatchedHonkTranslatorProver::execute_translator_oink()
{
    TranslatorProver trans_prover(translator_key, transcript);
    trans_prover.execute_preamble_round();
    trans_prover.execute_wire_and_sorted_constraints_commitments_round();
    trans_prover.execute_grand_product_computation_round();
    translator_relation_parameters = trans_prover.relation_parameters;
}
 
void BatchedHonkTranslatorProver::execute_joint_sumcheck_rounds()
{
    // Draw joint alpha after all pre-sumcheck commitments from both circuits.
    const FF alpha = transcript->template get_challenge<FF>("Sumcheck:alpha");
 
    // Draw joint gate challenges (17 total).
    std::vector<FF> gate_challenges(JOINT_LOG_N);
    for (size_t i = 0; i < JOINT_LOG_N; i++) {
        gate_challenges[i] = transcript->template get_challenge<FF>("Sumcheck:gate_challenge_" + std::to_string(i));
    }
 
    // Compute α^{K_H}: offset for translator subrelation separators.
    FF alpha_power_KH = FF(1);
    for (size_t i = 0; i < MegaZKFlavor::NUM_SUBRELATIONS; i++) {
        alpha_power_KH *= alpha;
    }
 
    // Subrelation separator arrays (powers of alpha starting at alpha^1).
    const MegaZKSubrelationSeparators mega_zk_alphas =
        initialize_relation_separator<FF, MegaZKFlavor::NUM_SUBRELATIONS - 1>(alpha);
    const TransSubrelationSeparators translator_alphas =
        initialize_relation_separator<FF, TranslatorFlavor::NUM_SUBRELATIONS - 1>(alpha);
 
    // Derive MegaZK circuit log_circuit_size from the proving instance.
    const size_t mega_zk_log_n = mega_zk_inst->log_dyadic_size();
    BB_ASSERT(mega_zk_log_n <= JOINT_LOG_N);
 
    // Joint ZK data: single Libra masking for all 17 rounds.
    constexpr size_t log_subgroup_size = static_cast<size_t>(numeric::get_msb(Curve::SUBGROUP_SIZE));
    MegaZKCommitmentKey small_ck(1 << (log_subgroup_size + 1));
    zk_sumcheck_data = ZKData(JOINT_LOG_N, transcript, small_ck);
 
    // Gate separator polynomials:
    //   MegaZK circuit uses gate_challenges[0..mega_zk_log_n-1] for beta_products (real rounds only).
    //   During virtual rounds, only betas[] and partial_evaluation_result are accessed.
    //   Translator uses all JOINT_LOG_N challenges.
    GateSeparatorPolynomial<FF> mega_zk_gate_sep(gate_challenges, mega_zk_log_n);
    GateSeparatorPolynomial<FF> translator_gate_sep(gate_challenges, JOINT_LOG_N);
 
    // Round helper objects.
    MegaZKProverRound mega_zk_round(static_cast<size_t>(1) << mega_zk_log_n);
    TransProverRound translator_round(static_cast<size_t>(1) << JOINT_LOG_N);
 
    // Row disabling polynomial for the MegaZK circuit.
    // (TranslatorFlavor does not use UseRowDisablingPolynomial.)
    RowDisablingPolynomial<FF> rdp;
 
    auto& mega_zk_polys = mega_zk_inst->polynomials;
    auto& mega_zk_params = mega_zk_inst->relation_parameters;
    auto& translator_polys = translator_key->proving_key->polynomials;
 
    // Allocate partially evaluated polynomial tables (populated by the first partially_evaluate call).
    MegaZKPartialEvals mega_zk_partial(mega_zk_polys, static_cast<size_t>(1) << mega_zk_log_n);
    TransPartialEvals translator_partial(translator_polys, static_cast<size_t>(1) << JOINT_LOG_N);
 
    // Type aliases for static partial-evaluation helpers from SumcheckProver.
    using MegaZKSumcheck = SumcheckProver<MegaZKFlavor>;
    using TransSumcheck = SumcheckProver<TranslatorFlavor>;
 
    joint_challenge.reserve(JOINT_LOG_N);
 
    SumcheckRoundUnivariate U_joint;
 
    // Per-round helper: add Libra masking, send the joint univariate, receive the round challenge.
    auto send_round = [&](size_t round_idx) -> FF {
        U_joint += MegaZKProverRound::compute_libra_univariate(zk_sumcheck_data, round_idx);
        transcript->send_to_verifier("Sumcheck:univariate_" + std::to_string(round_idx), U_joint);
        FF u = transcript->template get_challenge<FF>("Sumcheck:u_" + std::to_string(round_idx));
        joint_challenge.emplace_back(u);
        return u;
    };
 
    // Per-round helper: update ZK data, gate separators, translator round size, and optionally send
    // translator minicircuit evaluations.
    auto update_round_state = [&](size_t round_idx, const FF& u) {
        if (round_idx == TranslatorFlavor::LOG_MINI_CIRCUIT_SIZE - 1) {
            transcript->send_to_verifier("Sumcheck:minicircuit_evaluations",
                                         TranslatorFlavor::get_minicircuit_evaluations(translator_partial));
        }
        zk_sumcheck_data.update_zk_sumcheck_data(u, round_idx);
        mega_zk_gate_sep.partially_evaluate(u);
        translator_gate_sep.partially_evaluate(u);
        translator_round.round_size >>= 1;
    };
 
    // Per-round helper: compute U_joint = U_MZK + α^{K_H}·U_translator from given polynomial
    // sources, add Libra masking, send to verifier, and return the round challenge.
    // hpolys/tpolys are the full tables on round 0, the partial-eval tables on subsequent rounds.
    auto do_round = [&](auto& hpolys, auto& tpolys, size_t round_idx) -> FF {
        U_joint = SumcheckRoundUnivariate::zero();
 
        auto U_H = mega_zk_round.compute_univariate(hpolys, mega_zk_params, mega_zk_gate_sep, mega_zk_alphas);
        U_H -= mega_zk_round.compute_disabled_contribution(
            hpolys, mega_zk_params, mega_zk_gate_sep, mega_zk_alphas, round_idx, rdp);
        U_joint += U_H;
 
        auto U_T = translator_round.compute_univariate(
            tpolys, translator_relation_parameters, translator_gate_sep, translator_alphas);
        for (auto& eval : U_T.evaluations) {
            eval *= alpha_power_KH;
        }
        U_joint += U_T;
 
        return send_round(round_idx);
    };
 
    // ==================== Round 0: bootstraps mega_zk_partial and translator_partial ====================
    // PartiallyEvaluatedMultivariates only allocates output buffers; values are populated here.
    {
        const FF u = do_round(mega_zk_polys, translator_polys, 0);
        MegaZKSumcheck::partially_evaluate(mega_zk_polys, mega_zk_partial, u);
        TransSumcheck::partially_evaluate(translator_polys, translator_partial, u);
        rdp.update_evaluations(u, 0);
        mega_zk_round.round_size >>= 1;
        update_round_state(0, u);
    }
 
    // ==================== Real rounds 1..mega_zk_log_n-1 ====================
    for (size_t round_idx = 1; round_idx < mega_zk_log_n; round_idx++) {
        const FF u = do_round(mega_zk_partial, translator_partial, round_idx);
        MegaZKSumcheck::partially_evaluate_in_place(mega_zk_partial, u);
        TransSumcheck::partially_evaluate_in_place(translator_partial, u);
        rdp.update_evaluations(u, round_idx);
        mega_zk_round.round_size >>= 1;
        update_round_state(round_idx, u);
    }
 
    // Capture RDP scalar after all real rounds for use in virtual rounds.
    // rdp_scalar = RDP(u_0,...,u_{d-1}) = 1 - u_2*...*u_{d-1}.
    const FF rdp_scalar = FF(1) - rdp.eval_at_1;
 
    // Send MegaZK circuit evaluations immediately after the real rounds.
    // These are P_j(u_0,...,u_{d-1}) — the natural d-variable evaluations without the tau factor.
    // The verifier will extend them by zero (multiply by τ = ∏(1-u_k)) after drawing virtual-round challenges.
    // This eliminates any prover freedom in the zero-padded region: the extension is verifier-determined.
    for (auto [eval, poly] : zip_view(mega_zk_claimed_evals.get_all(), mega_zk_partial.get_all())) {
        eval = poly[0];
    }
    transcript->send_to_verifier("Sumcheck:evaluations", mega_zk_claimed_evals.get_all());
 
    // ==================== Virtual rounds mega_zk_log_n..JOINT_LOG_N-1 ====================
    // The MegaZK polynomials are zero-padded beyond 2^mega_zk_log_n. The virtual contribution
    // is compute_virtual_contribution * rdp_scalar. The polynomial values are updated by
    // (1-u_k) after each round for the virtual contribution computation.
    for (size_t round_idx = mega_zk_log_n; round_idx < JOINT_LOG_N; round_idx++) {
        U_joint = SumcheckRoundUnivariate::zero();
 
        auto U_H = mega_zk_round.compute_virtual_contribution(
            mega_zk_partial, mega_zk_params, mega_zk_gate_sep, mega_zk_alphas);
        U_H *= rdp_scalar;
        U_joint += U_H;
 
        auto U_T = translator_round.compute_univariate(
            translator_partial, translator_relation_parameters, translator_gate_sep, translator_alphas);
        for (auto& eval : U_T.evaluations) {
            eval *= alpha_power_KH;
        }
        U_joint += U_T;
 
        const FF u = send_round(round_idx);
 
        // Virtual: poly values *= (1 - u_k) for the next virtual contribution computation.
        for (auto& poly : mega_zk_partial.get_all()) {
            if (poly.end_index() > 0) {
                poly.at(0) *= (FF(1) - u);
            }
        }
        TransSumcheck::partially_evaluate_in_place(translator_partial, u);
        update_round_state(round_idx, u);
    }
 
    // Extract and send translator evaluations after all rounds.
    for (auto [eval, poly] : zip_view(trans_claimed_evals.get_all(), translator_partial.get_all())) {
        eval = poly[0];
    }
    transcript->send_to_verifier("Sumcheck:evaluations_translator",
                                 TranslatorFlavor::get_full_circuit_evaluations(trans_claimed_evals));
 
    // Compute and send the claimed Libra evaluation.
    claimed_libra_evaluation = zk_sumcheck_data.constant_term;
    for (const auto& libra_eval : zk_sumcheck_data.libra_evaluations) {
        claimed_libra_evaluation += libra_eval;
    }
    transcript->send_to_verifier("Libra:claimed_evaluation", claimed_libra_evaluation);
}
 
void BatchedHonkTranslatorProver::execute_joint_pcs()
{
    using OpeningClaim = ProverOpeningClaim<Curve>;
    using PolynomialBatcher = GeminiProver_<Curve>::PolynomialBatcher;
    using SmallSubgroupIPA = SmallSubgroupIPAProver<MegaZKFlavor>;
 
    // Use the translator's commitment key (sized to 2^17 = joint_circuit_size) for all PCS work.
    // The translator key is initialised by TranslatorProver in execute_translator_oink().
    auto& ck = translator_key->proving_key->commitment_key;
 
    // Prove the small-subgroup IPA opening for the joint Libra polynomial.
    SmallSubgroupIPA small_subgroup_ipa(zk_sumcheck_data, joint_challenge, claimed_libra_evaluation, transcript, ck);
    small_subgroup_ipa.prove();
 
    // Build joint PolynomialBatcher at joint_circuit_size = 2^17.
    // max_end_index covers hiding (2^16) and translator (2^17) polynomials; use the larger.
    const size_t joint_circuit_size = static_cast<size_t>(1) << JOINT_LOG_N;
    const size_t mega_zk_max_end = mega_zk_inst->polynomials.max_end_index();
    const size_t trans_max_end = translator_key->proving_key->circuit_size; // translator polys fill 2^17
    const size_t max_end_index = std::max(mega_zk_max_end, trans_max_end);
 
    PolynomialBatcher polynomial_batcher(joint_circuit_size, max_end_index);
 
    // Combine unshifted polynomials from both circuits.
    auto mega_zk_unshifted = mega_zk_inst->polynomials.get_unshifted();
    auto trans_unshifted = translator_key->proving_key->polynomials.get_pcs_unshifted();
    auto joint_unshifted = concatenate(mega_zk_unshifted, trans_unshifted);
    polynomial_batcher.set_unshifted(joint_unshifted);
 
    // Combine shifted polynomials from both circuits.
    auto mega_zk_shifted = mega_zk_inst->polynomials.get_to_be_shifted();
    auto trans_shifted = translator_key->proving_key->polynomials.get_pcs_to_be_shifted();
    auto joint_shifted = concatenate(mega_zk_shifted, trans_shifted);
    polynomial_batcher.set_to_be_shifted_by_one(joint_shifted);
 
    const OpeningClaim prover_opening_claim =
        ShpleminiProver_<Curve>::prove(joint_circuit_size,
                                       polynomial_batcher,
                                       joint_challenge,
                                       ck,
                                       transcript,
                                       small_subgroup_ipa.get_witness_polynomials());
 
    MegaZKFlavor::PCS::compute_opening_proof(ck, prover_opening_claim, transcript);
}
 
HonkProof BatchedHonkTranslatorProver::prove_mega_zk_oink()
{
    execute_mega_zk_oink();
    return transcript->export_proof();
}
 
HonkProof BatchedHonkTranslatorProver::prove(std::shared_ptr<TranslatorProvingKey> translator_proving_key)
{
    translator_key = std::move(translator_proving_key);
    execute_translator_oink();
    execute_joint_sumcheck_rounds();
    execute_joint_pcs();
    return transcript->export_proof();
}
 
} // namespace bb