translator_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 "translator_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/sparse_masking_poly.hpp"
#include "barretenberg/commitment_schemes/small_subgroup_ipa/small_subgroup_ipa.hpp"
#include "barretenberg/honk/library/grand_product_library.hpp"
#include "barretenberg/numeric/bitop/get_msb.hpp"
#include "barretenberg/relations/translator_vm/translator_decomposition_short_relation_impl.hpp"
#include "barretenberg/relations/translator_vm/translator_delta_range_constraint_short_relation_impl.hpp"
#include "barretenberg/relations/translator_vm/translator_extra_short_relations_impl.hpp"
#include "barretenberg/relations/translator_vm/translator_non_native_field_short_relation_impl.hpp"
#include "barretenberg/relations/translator_vm/translator_permutation_short_relation_impl.hpp"
#include "barretenberg/relations/translator_vm/translator_shiftable_first_coeff_zero_short_relation_impl.hpp"
#include "barretenberg/sumcheck/sumcheck.hpp"
 
namespace bb {
 
TranslatorProver::TranslatorProver(const std::shared_ptr<TranslatorProvingKey>& key,
                                   const std::shared_ptr<Transcript>& transcript)
    : transcript(transcript)
    , key(key)
{
    BB_BENCH();
    key->proving_key->commitment_key = CommitmentKey(key->proving_key->circuit_size);
}
 
void TranslatorProver::execute_preamble_round()
{
    // Fiat-Shamir the vk hash
    typename Flavor::VerificationKey vk;
    typename Flavor::FF vk_hash = vk.get_hash();
    transcript->add_to_hash_buffer("vk_hash", vk_hash);
    vinfo("Translator vk hash in prover: ", vk_hash);
 
    const size_t RESULT_ROW = Flavor::RESULT_ROW;
 
    // Set accumulated_result in relation parameters from the witness polynomials
    // The verifier will receive this value from the ECCVM verifier instead of the transcript
    relation_parameters.accumulated_result = { key->proving_key->polynomials.accumulators_binary_limbs_0[RESULT_ROW],
                                               key->proving_key->polynomials.accumulators_binary_limbs_1[RESULT_ROW],
                                               key->proving_key->polynomials.accumulators_binary_limbs_2[RESULT_ROW],
                                               key->proving_key->polynomials.accumulators_binary_limbs_3[RESULT_ROW] };
}
 
void TranslatorProver::commit_to_witness_polynomial(Polynomial& polynomial,
                                                    const std::string& label,
                                                    bool has_duplicates_hint)
{
    transcript->send_to_verifier(label, key->proving_key->commitment_key.commit(polynomial, has_duplicates_hint));
}
 
void TranslatorProver::execute_wire_and_sorted_constraints_commitments_round()
{
    BB_BENCH_NAME("TranslatorProver::execute_wire_and_sorted_constraints_commitments_round");
 
    // Sparse 2d-coefficient Gemini masking polynomial on the tail-halving support.
    // See SHPLEMINI_ZK_MASKING.md for the rank / ZK argument.
    const size_t circuit_size = key->proving_key->circuit_size;
    const size_t d = numeric::get_msb(circuit_size);
    key->proving_key->polynomials.gemini_masking_poly = build_gemini_masking_poly<FF>(d, circuit_size, circuit_size);
    Flavor::Commitment masking_commitment;
    {
        BB_BENCH_NAME("Translator::commit_masking_poly_msm");
        masking_commitment = key->proving_key->commitment_key.commit(key->proving_key->polynomials.gemini_masking_poly);
    }
    transcript->send_to_verifier("Gemini:masking_poly_comm", masking_commitment);
 
    // Commit to non-op-queue wires and ordered range constraints
    // Note: Op queue wires (op, x_lo_y_hi, x_hi_z_1, y_lo_z_2) are NOT committed to here
    // They are provided by the merge protocol and passed to the verifier
    auto batch = key->proving_key->commitment_key.start_batch();
    for (const auto& [wire, label] :
         zip_view(key->proving_key->polynomials.get_non_opqueue_wires_and_ordered_range_constraints(),
                  commitment_labels.get_non_opqueue_wires_and_ordered_range_constraints())) {
        batch.add_to_batch(wire, label);
    }
    batch.commit_and_send_to_verifier(transcript);
}
 
void TranslatorProver::execute_grand_product_computation_round()
{
    // Compute and store parameters required by relations in Sumcheck
    FF beta = transcript->template get_challenge<FF>("beta");
    FF gamma = transcript->template get_challenge<FF>("gamma");
    const size_t NUM_LIMB_BITS = Flavor::NUM_LIMB_BITS;
    relation_parameters.beta = beta;
    relation_parameters.gamma = gamma;
    auto uint_evaluation_input = uint256_t(key->evaluation_input_x);
    relation_parameters.evaluation_input_x = { uint_evaluation_input.slice(0, NUM_LIMB_BITS),
                                               uint_evaluation_input.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2),
                                               uint_evaluation_input.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3),
                                               uint_evaluation_input.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4),
                                               uint_evaluation_input };
 
    std::vector<uint256_t> uint_batching_challenge_powers;
    auto batching_challenge_v = key->batching_challenge_v;
    uint_batching_challenge_powers.emplace_back(batching_challenge_v);
    auto running_power = batching_challenge_v * batching_challenge_v;
    uint_batching_challenge_powers.emplace_back(running_power);
    running_power *= batching_challenge_v;
    uint_batching_challenge_powers.emplace_back(running_power);
    running_power *= batching_challenge_v;
    uint_batching_challenge_powers.emplace_back(running_power);
 
    for (size_t i = 0; i < 4; i++) {
        relation_parameters.batching_challenge_v[i] = {
            uint_batching_challenge_powers[i].slice(0, NUM_LIMB_BITS),
            uint_batching_challenge_powers[i].slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2),
            uint_batching_challenge_powers[i].slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3),
            uint_batching_challenge_powers[i].slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4),
            uint_batching_challenge_powers[i]
        };
    }
    // Compute constraint permutation grand product
    compute_grand_products<Flavor>(key->proving_key->polynomials, relation_parameters);
 
    // set has_duplicates_hint for Z_PERM (empty row = duplicate Z value)
    commit_to_witness_polynomial(key->proving_key->polynomials.z_perm, commitment_labels.z_perm, true);
}
 
void TranslatorProver::execute_relation_check_rounds()
{
    using Sumcheck = SumcheckProver<Flavor>;
 
    // Each linearly independent subrelation contribution is multiplied by `alpha^i`, where
    //  i = 0, ..., NUM_SUBRELATIONS- 1.
    const 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", Flavor::CONST_TRANSLATOR_LOG_N);
 
    const size_t circuit_size = key->proving_key->circuit_size;
 
    Sumcheck sumcheck(circuit_size,
                      key->proving_key->polynomials,
                      transcript,
                      alpha,
                      gate_challenges,
                      relation_parameters,
                      Flavor::CONST_TRANSLATOR_LOG_N);
 
    const size_t log_subgroup_size = static_cast<size_t>(numeric::get_msb(Flavor::Curve::SUBGROUP_SIZE));
    // Create a temporary commitment key that is only used to initialize the ZKSumcheckData
    // If proving in WASM, the commitment key that is part of the Translator proving key remains deallocated
    // until we enter the PCS round
    CommitmentKey ck(1 << (log_subgroup_size + 1));
 
    zk_sumcheck_data = ZKData(key->proving_key->log_circuit_size, transcript, ck);
 
    sumcheck_output = sumcheck.prove(zk_sumcheck_data);
}
 
void TranslatorProver::execute_pcs_rounds()
{
    using Curve = typename Flavor::Curve;
    using OpeningClaim = ProverOpeningClaim<Curve>;
    using SmallSubgroupIPA = SmallSubgroupIPAProver<Flavor>;
    using PolynomialBatcher = GeminiProver_<Curve>::PolynomialBatcher;
 
    auto& ck = key->proving_key->commitment_key;
 
    SmallSubgroupIPA small_subgroup_ipa_prover(
        zk_sumcheck_data, sumcheck_output.challenge, sumcheck_output.claimed_libra_evaluation, transcript, ck);
    small_subgroup_ipa_prover.prove();
 
    PolynomialBatcher polynomial_batcher(key->proving_key->circuit_size);
 
    // Unshifted for PCS (excludes computable precomputed — verifier computes them locally)
    polynomial_batcher.set_unshifted(key->proving_key->polynomials.get_pcs_unshifted());
    // Shifted for PCS (base to-be-shifted + concatenated)
    polynomial_batcher.set_to_be_shifted_by_one(key->proving_key->polynomials.get_pcs_to_be_shifted());
 
    const OpeningClaim prover_opening_claim =
        ShpleminiProver_<Curve>::prove(key->proving_key->circuit_size,
                                       polynomial_batcher,
                                       sumcheck_output.challenge,
                                       ck,
                                       transcript,
                                       small_subgroup_ipa_prover.get_witness_polynomials());
 
    PCS::compute_opening_proof(ck, prover_opening_claim, transcript);
}
 
HonkProof TranslatorProver::export_proof()
{
    return transcript->export_proof();
}
 
HonkProof TranslatorProver::construct_proof()
{
    BB_BENCH_NAME("TranslatorProver::construct_proof");
 
    // Add circuit size public input size and public inputs to transcript.
    execute_preamble_round();
 
    // Compute first three wire commitments
    execute_wire_and_sorted_constraints_commitments_round();
 
    // Fiat-Shamir: gamma
    // Compute grand product(s) and commitments.
    execute_grand_product_computation_round();
 
    // Fiat-Shamir: alpha
    // Run sumcheck subprotocol.
    execute_relation_check_rounds();
 
    // Fiat-Shamir: rho, y, x, z
    // Execute Shplemini PCS
    execute_pcs_rounds();
    vinfo("computed opening proof");
    return export_proof();
}
 
uint256_t TranslatorProver::get_accumulated_result() const
{
    const size_t RESULT_ROW = Flavor::RESULT_ROW;
    return uint256_t(key->proving_key->polynomials.accumulators_binary_limbs_0[RESULT_ROW]) +
           (uint256_t(key->proving_key->polynomials.accumulators_binary_limbs_1[RESULT_ROW]) << 68) +
           (uint256_t(key->proving_key->polynomials.accumulators_binary_limbs_2[RESULT_ROW]) << 136) +
           (uint256_t(key->proving_key->polynomials.accumulators_binary_limbs_3[RESULT_ROW]) << 204);
}
 
} // namespace bb