sumcheck_client_ivc.cpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: not started, auditors: [], date: YYYY-MM-DD }
// external_1:  { status: not started, auditors: [], date: YYYY-MM-DD }
// external_2:  { status: not started, auditors: [], date: YYYY-MM-DD }
// =====================
 
#include "barretenberg/client_ivc/sumcheck_client_ivc.hpp"
#include "barretenberg/common/bb_bench.hpp"
#include "barretenberg/common/streams.hpp"
#include "barretenberg/honk/prover_instance_inspector.hpp"
#include "barretenberg/multilinear_batching/multilinear_batching_prover.hpp"
#include "barretenberg/serialize/msgpack_impl.hpp"
#include "barretenberg/special_public_inputs/special_public_inputs.hpp"
#include "barretenberg/ultra_honk/oink_prover.hpp"
#include "barretenberg/ultra_honk/oink_verifier.hpp"
 
namespace bb {
 
// Constructor
SumcheckClientIVC::SumcheckClientIVC(size_t num_circuits)
    : num_circuits(num_circuits)
    , goblin(bn254_commitment_key)
{
    BB_ASSERT_GT(num_circuits, 0UL, "Number of circuits must be specified and greater than 0.");
    // Allocate BN254 commitment key based on translator circuit size.
    // https://github.com/AztecProtocol/barretenberg/issues/1319): Account for Translator only when it's necessary
    size_t commitment_key_size = 1UL << TranslatorFlavor::CONST_TRANSLATOR_LOG_N;
    info("BN254 commitment key size: ", commitment_key_size);
    bn254_commitment_key = CommitmentKey<curve::BN254>(commitment_key_size);
}
 
void SumcheckClientIVC::instantiate_stdlib_verification_queue(
    ClientCircuit& circuit, const std::vector<std::shared_ptr<RecursiveVKAndHash>>& input_keys)
{
    bool vkeys_provided = !input_keys.empty();
    if (vkeys_provided) {
        BB_ASSERT_EQ(verification_queue.size(),
                     input_keys.size(),
                     "Incorrect number of verification keys provided in "
                     "stdlib verification queue instantiation.");
    }
 
    size_t key_idx = 0;
    while (!verification_queue.empty()) {
        const VerifierInputs& entry = verification_queue.front();
 
        // Construct stdlib proof directly from the internal native queue data
        StdlibProof stdlib_proof(circuit, entry.proof);
 
        // Use the provided stdlib vkey if present, otherwise construct one from the internal native queue
        std::shared_ptr<RecursiveVKAndHash> stdlib_vk_and_hash;
        if (vkeys_provided) {
            stdlib_vk_and_hash = input_keys[key_idx++];
        } else {
            stdlib_vk_and_hash = std::make_shared<RecursiveVKAndHash>(circuit, entry.honk_vk);
        }
 
        stdlib_verification_queue.emplace_back(stdlib_proof, stdlib_vk_and_hash, entry.type, entry.is_kernel);
 
        verification_queue.pop_front(); // the native data is not needed beyond this point
    }
}
 
SumcheckClientIVC::RecursiveVerifierAccumulator SumcheckClientIVC::execute_first_sumcheck_recursive_verification(
    ClientCircuit& circuit,
    const std::shared_ptr<RecursiveVerifierInstance>& verifier_instance,
    const std::shared_ptr<RecursiveTranscript>& transcript,
    const StdlibProof& proof)
{
    using VerifierCommitments = typename RecursiveFlavor::VerifierCommitments;
    using Sumcheck = ::bb::SumcheckVerifier<RecursiveFlavor>;
 
    transcript->load_proof(proof);
    OinkRecursiveVerifier verifier{ verifier_instance, transcript };
    verifier.verify();
 
    verifier_instance->target_sum = StdlibFF::from_witness_index(&circuit, circuit.zero_idx());
    // Get the gate challenges for sumcheck/combiner computation
    verifier_instance->gate_challenges =
        transcript->template get_powers_of_challenge<StdlibFF>("gate_challenge", Flavor::VIRTUAL_LOG_N);
 
    VerifierCommitments commitments{ verifier_instance->vk_and_hash->vk, verifier_instance->witness_commitments };
    // DeciderRecursiveVerifier's log circuit size is fixed, hence we are using a trivial `padding_indicator_array`.
    std::vector<StdlibFF> padding_indicator_array(Flavor::VIRTUAL_LOG_N, 1);
 
    Sumcheck sumcheck(transcript, verifier_instance->alphas, Flavor::VIRTUAL_LOG_N, verifier_instance->target_sum);
    SumcheckOutput<RecursiveFlavor> sumcheck_output = sumcheck.verify(
        verifier_instance->relation_parameters, verifier_instance->gate_challenges, padding_indicator_array);
 
    BB_ASSERT_EQ(sumcheck_output.verified || circuit.has_dummy_witnesses(),
                 true,
                 "Sumcheck: Failed to recursively verify first sumcheck.");
 
    RecursiveFirstSumcheckOutput output{ .challenge = sumcheck_output.challenge,
                                         .claimed_evaluations = sumcheck_output.claimed_evaluations };
    auto recursive_accumulator = output.batch(verifier_instance, transcript);
 
    return recursive_accumulator;
}
 
SumcheckClientIVC::RecursiveVerifierAccumulator SumcheckClientIVC::perform_folding_recursive_verification(
    ClientCircuit& circuit,
    const std::optional<RecursiveVerifierAccumulator>& verifier_accumulator,
    const std::shared_ptr<RecursiveVerifierInstance>& verifier_instance,
    const std::shared_ptr<RecursiveTranscript>& transcript,
    const StdlibProof& proof,
    std::optional<StdlibFF>& prev_accum_hash,
    bool is_kernel)
{
    BB_ASSERT_NEQ(verifier_accumulator.has_value(),
                  false,
                  "verifier_accumulator cannot be null in folding recursive verification");
 
    auto incoming_verifier_accumulator =
        execute_first_sumcheck_recursive_verification(circuit, verifier_instance, transcript, proof);
 
    // Update previous accumulator hash so that we can set it as a public input
    if (is_kernel) {
        prev_accum_hash = verifier_accumulator->hash_through_transcript("", *transcript);
    }
 
    MultilinearBatchingVerifier<MultilinearBatchingRecursiveFlavor> batching_verifier(transcript);
    auto [verified, new_accumulator] = batching_verifier.verify_proof();
    BB_ASSERT_EQ(verified || circuit.has_dummy_witnesses(),
                 true,
                 "Batching Sumcheck: Failed to recursively verify sumcheck batching.");
 
    return RecursiveVerifierAccumulator(new_accumulator.challenge,
                                        { new_accumulator.non_shifted_evaluation, new_accumulator.shifted_evaluation },
                                        { new_accumulator.non_shifted_commitment, new_accumulator.shifted_commitment });
}
 
std::tuple<std::optional<SumcheckClientIVC::RecursiveVerifierAccumulator>,
           SumcheckClientIVC::PairingPoints,
           SumcheckClientIVC::TableCommitments>
SumcheckClientIVC::perform_recursive_verification_and_databus_consistency_checks(
    ClientCircuit& circuit,
    const StdlibVerifierInputs& verifier_inputs,
    const std::optional<RecursiveVerifierAccumulator>& input_verifier_accumulator,
    const TableCommitments& T_prev_commitments,
    const std::shared_ptr<RecursiveTranscript>& accumulation_recursive_transcript)
{
    auto num_rows = circuit.op_queue->get_num_rows();
    auto num_ops = circuit.op_queue->get_current_subtable_size();
    info("NUM ROWS WHEN ENTERING: ", num_rows);
    info("NUM OPS WHEN ENTERING: ", num_ops);
 
    using MergeCommitments = Goblin::MergeRecursiveVerifier::InputCommitments;
 
    // The pairing points produced by the verification of the decider proof
    PairingPoints decider_pairing_points;
 
    // Input commitments to be passed to the merge recursive verification
    MergeCommitments merge_commitments{ .T_prev_commitments = T_prev_commitments };
 
    auto verifier_instance = std::make_shared<RecursiveVerifierInstance>(&circuit, verifier_inputs.honk_vk_and_hash);
 
    std::optional<RecursiveVerifierAccumulator> output_verifier_accumulator;
    std::optional<StdlibFF> prev_accum_hash = std::nullopt;
    // The decider proof exists if the tail kernel has been accumulated
    bool is_hiding_kernel = !pcs_proof.empty();
 
    switch (verifier_inputs.type) {
    case QUEUE_TYPE::OINK: {
        BB_ASSERT_EQ(input_verifier_accumulator.has_value(), false);
 
        output_verifier_accumulator = execute_first_sumcheck_recursive_verification(
            circuit, verifier_instance, accumulation_recursive_transcript, verifier_inputs.proof);
 
        // T_prev = 0 in the first recursive verification
        merge_commitments.T_prev_commitments = stdlib::recursion::honk::empty_ecc_op_tables(circuit);
        break;
    }
    case QUEUE_TYPE::PG:
    case QUEUE_TYPE::PG_TAIL: {
        output_verifier_accumulator = perform_folding_recursive_verification(circuit,
                                                                             input_verifier_accumulator,
                                                                             verifier_instance,
                                                                             accumulation_recursive_transcript,
                                                                             verifier_inputs.proof,
                                                                             prev_accum_hash,
                                                                             verifier_inputs.is_kernel);
        break;
    }
    case QUEUE_TYPE::PG_FINAL: {
        using ClaimBatcher = ClaimBatcher_<stdlib::bn254<ClientCircuit>>;
        using ClaimBatch = ClaimBatcher::Batch;
        using Shplemini = ::bb::ShpleminiVerifier_<stdlib::bn254<ClientCircuit>>;
        using PCS = typename RecursiveFlavor::PCS;
 
        BB_ASSERT_EQ(stdlib_verification_queue.size(), size_t(1));
 
        hide_op_queue_accumulation_result(circuit);
 
        auto final_verifier_accumulator = perform_folding_recursive_verification(circuit,
                                                                                 input_verifier_accumulator,
                                                                                 verifier_instance,
                                                                                 accumulation_recursive_transcript,
                                                                                 verifier_inputs.proof,
                                                                                 prev_accum_hash,
                                                                                 verifier_inputs.is_kernel);
 
        StdlibProof stdlib_pcs_proof(circuit, pcs_proof);
        accumulation_recursive_transcript->load_proof(stdlib_pcs_proof);
 
        // DeciderRecursiveVerifier's log circuit size is fixed, hence we are using a trivial `padding_indicator_array`.
        std::vector<StdlibFF> padding_indicator_array(RecursiveFlavor::VIRTUAL_LOG_N, 1);
 
        // Execute Shplemini rounds.
        ClaimBatcher claim_batcher{ .unshifted = ClaimBatch{ final_verifier_accumulator.batched_commitments[0],
                                                             final_verifier_accumulator.batched_evaluations[0] },
                                    .shifted = ClaimBatch{ final_verifier_accumulator.batched_commitments[1],
                                                           final_verifier_accumulator.batched_evaluations[1] } };
        const auto opening_claim = Shplemini::compute_batch_opening_claim(padding_indicator_array,
                                                                          claim_batcher,
                                                                          final_verifier_accumulator.challenge,
                                                                          RecursiveCommitment::one(&circuit),
                                                                          accumulation_recursive_transcript);
        decider_pairing_points =
            PCS::reduce_verify_batch_opening_claim(opening_claim, accumulation_recursive_transcript);
 
        BB_ASSERT_EQ(output_verifier_accumulator.has_value(), false);
        break;
    }
    default: {
        throw_or_abort("Invalid queue type! Only OINK, PG, PG_TAIL and PG_FINAL are supported");
    }
    }
 
    // Extract the witness commitments and public inputs from the incoming verifier instance
    WitnessCommitments witness_commitments = std::move(verifier_instance->witness_commitments);
    std::vector<StdlibFF> public_inputs = std::move(verifier_instance->public_inputs);
 
    PairingPoints nested_pairing_points; // to be extracted from public inputs of app or kernel proof just verified
 
    if (verifier_inputs.is_kernel) {
        // Reconstruct the input from the previous kernel from its public inputs
        KernelIO kernel_input; // pairing points, databus return data commitments
        kernel_input.reconstruct_from_public(public_inputs);
        nested_pairing_points = kernel_input.pairing_inputs;
        // Perform databus consistency checks
        kernel_input.kernel_return_data.incomplete_assert_equal(witness_commitments.calldata);
        kernel_input.app_return_data.incomplete_assert_equal(witness_commitments.secondary_calldata);
 
        // T_prev is read by the public input of the previous kernel K_{i-1} at the beginning of the recursive
        // verification of of the folding of K_{i-1} (kernel), A_{i,1} (app), .., A_{i, n} (app). This verification
        // happens in K_{i}
        merge_commitments.T_prev_commitments = std::move(kernel_input.ecc_op_tables);
 
        BB_ASSERT_EQ(verifier_inputs.type == QUEUE_TYPE::PG || verifier_inputs.type == QUEUE_TYPE::PG_TAIL ||
                         verifier_inputs.type == QUEUE_TYPE::PG_FINAL,
                     true,
                     "Kernel circuits should be folded.");
        // Get the previous accum hash
        info("PG accum hash from IO: ", kernel_input.output_pg_accum_hash);
        ASSERT(prev_accum_hash.has_value());
        kernel_input.output_pg_accum_hash.assert_equal(*prev_accum_hash);
 
        if (!is_hiding_kernel) {
            // The hiding kernel has no return data; it uses the traditional public-inputs mechanism
            bus_depot.set_kernel_return_data_commitment(witness_commitments.return_data);
        }
    } else {
        // Reconstruct the input from the previous app from its public inputs
        AppIO app_input; // pairing points
        app_input.reconstruct_from_public(public_inputs);
        nested_pairing_points = app_input.pairing_inputs;
 
        // Set the app return data commitment to be propagated via the public inputs
        bus_depot.set_app_return_data_commitment(witness_commitments.return_data);
    }
 
    info("NUM ROWS DIFF: ", circuit.op_queue->get_num_rows() - num_rows);
    info("NUM OPS DIFF: ", circuit.op_queue->get_current_subtable_size() - num_ops);
 
    // Extract the commitments to the subtable corresponding to the incoming circuit
    merge_commitments.t_commitments = witness_commitments.get_ecc_op_wires().get_copy();
 
    // Recursively verify the corresponding merge proof
    auto [pairing_points, merged_table_commitments] =
        goblin.recursively_verify_merge(circuit, merge_commitments, accumulation_recursive_transcript);
 
    pairing_points.aggregate(nested_pairing_points);
    if (is_hiding_kernel) {
        pairing_points.aggregate(decider_pairing_points);
        // Add randomness at the end of the hiding kernel (whose ecc ops fall right at the end of the op queue table) to
        // ensure the CIVC proof doesn't leak information about the actual content of the op queue
        hide_op_queue_content_in_hiding(circuit);
    }
 
    info("NUM ROWS DIFF AT THE END: ", circuit.op_queue->get_num_rows() - num_rows);
    info("NUM OPS DIFF AT THE END: ", circuit.op_queue->get_current_subtable_size() - num_ops);
 
    return { output_verifier_accumulator, pairing_points, merged_table_commitments };
}
 
void SumcheckClientIVC::complete_kernel_circuit_logic(ClientCircuit& circuit)
{
 
    // Transcript to be shared shared across recursive verification of the folding of K_{i-1} (kernel), A_{i,1} (app),
    // .., A_{i, n} (app) (all circuits accumulated between the previous kernel and current one)
    auto accumulation_recursive_transcript = std::make_shared<RecursiveTranscript>();
 
    // Commitment to the previous state of the op_queue in the recursive verification
    TableCommitments T_prev_commitments;
 
    // Instantiate stdlib verifier inputs from their native counterparts
    if (stdlib_verification_queue.empty()) {
        instantiate_stdlib_verification_queue(circuit);
    }
 
    bool is_init_kernel =
        stdlib_verification_queue.size() == 1 && (stdlib_verification_queue.front().type == QUEUE_TYPE::OINK);
 
    bool is_tail_kernel =
        stdlib_verification_queue.size() == 1 && (stdlib_verification_queue.front().type == QUEUE_TYPE::PG_TAIL);
 
    bool is_hiding_kernel =
        stdlib_verification_queue.size() == 1 && (stdlib_verification_queue.front().type == QUEUE_TYPE::PG_FINAL);
 
    // The ECC-op subtable for a kernel begins with an eq-and-reset to ensure that the preceeding circuit's subtable
    // cannot affect the ECC-op accumulator for the kernel. For the tail kernel, we additionally add a preceeding no-op
    // to ensure the op queue wires in translator are shiftable, i.e. their 0th coefficient is 0. (The tail kernel
    // subtable is at the top of the final aggregate table since it is the last to be prepended).
    if (is_tail_kernel) {
        BB_ASSERT_EQ(circuit.op_queue->get_current_subtable_size(),
                     0U,
                     "tail kernel ecc ops table should be empty at this point");
        circuit.queue_ecc_no_op();
        // Add randomness at the begining of the tail kernel (whose ecc ops fall at the beginning of the op queue table)
        // to ensure the CIVC proof doesn't leak information about the actual content of the op queue
        hide_op_queue_content_in_tail(circuit);
    }
    circuit.queue_ecc_eq();
 
    // Perform Oink/PG and Merge recursive verification + databus consistency checks for each entry in the queue
    PairingPoints points_accumulator;
    std::optional<RecursiveVerifierAccumulator> current_stdlib_verifier_accumulator;
    if (!is_init_kernel) {
        current_stdlib_verifier_accumulator = RecursiveVerifierAccumulator(&circuit, recursive_verifier_native_accum);
    }
    while (!stdlib_verification_queue.empty()) {
        const StdlibVerifierInputs& verifier_input = stdlib_verification_queue.front();
 
        auto [output_stdlib_verifier_accumulator, pairing_points, merged_table_commitments] =
            perform_recursive_verification_and_databus_consistency_checks(circuit,
                                                                          verifier_input,
                                                                          current_stdlib_verifier_accumulator,
                                                                          T_prev_commitments,
                                                                          accumulation_recursive_transcript);
        points_accumulator.aggregate(pairing_points);
        // Update commitment to the status of the op_queue
        T_prev_commitments = merged_table_commitments;
        // Update the output verifier accumulator
        current_stdlib_verifier_accumulator = output_stdlib_verifier_accumulator;
 
        stdlib_verification_queue.pop_front();
    }
    // Set the kernel output data to be propagated via the public inputs
    if (is_hiding_kernel) {
        BB_ASSERT_EQ(current_stdlib_verifier_accumulator.has_value(), false);
        HidingKernelIO hiding_output{ points_accumulator, T_prev_commitments };
        hiding_output.set_public();
    } else {
        BB_ASSERT_NEQ(current_stdlib_verifier_accumulator.has_value(), false);
        // Extract native verifier accumulator from the stdlib accum for use on the next round
        recursive_verifier_native_accum = current_stdlib_verifier_accumulator->get_value();
 
        KernelIO kernel_output;
        kernel_output.pairing_inputs = points_accumulator;
        kernel_output.kernel_return_data = bus_depot.get_kernel_return_data_commitment(circuit);
        kernel_output.app_return_data = bus_depot.get_app_return_data_commitment(circuit);
        kernel_output.ecc_op_tables = T_prev_commitments;
        RecursiveTranscript hash_transcript;
        kernel_output.output_pg_accum_hash =
            current_stdlib_verifier_accumulator->hash_through_transcript("", hash_transcript);
        info("kernel output pg hash: ", kernel_output.output_pg_accum_hash);
        kernel_output.set_public();
    }
}
 
SumcheckClientIVC::ProverAccumulator SumcheckClientIVC::execute_first_sumcheck(
    const std::shared_ptr<ProverInstance>& prover_instance,
    const std::shared_ptr<MegaVerificationKey>& honk_vk,
    const std::shared_ptr<Transcript>& transcript)
{
    vinfo("computing sumcheck proof...");
    MegaOinkProver oink_prover{ prover_instance, honk_vk, transcript };
    oink_prover.prove();
 
    // Determine the number of rounds in the sumcheck based on whether or not padding is employed
    const size_t virtual_log_n = Flavor::VIRTUAL_LOG_N;
 
    prover_instance->gate_challenges =
        transcript->template get_powers_of_challenge<FF>("Sumcheck:gate_challenge", virtual_log_n);
 
    // Run sumcheck
    DeciderProver decider_prover(prover_instance, transcript);
    decider_prover.execute_relation_check_rounds();
 
    // First sumcheck output
    info("Dyadic size: ", prover_instance->dyadic_size());
    FirstSumcheckOutput sumcheck_output{ .challenge = decider_prover.sumcheck_output.challenge,
                                         .claimed_evaluations = decider_prover.sumcheck_output.claimed_evaluations,
                                         .full_batched_size = prover_instance->dyadic_size() };
 
    // Commitments
    Flavor::VerifierCommitments verifier_commitments(honk_vk, prover_instance->commitments);
 
    // Batching
    ProverAccumulator result = sumcheck_output.batch(prover_instance->polynomials, verifier_commitments, transcript);
 
    return result;
}
 
SumcheckClientIVC::VerifierAccumulator SumcheckClientIVC::execute_first_sumcheck_native_verification(
    const std::shared_ptr<VerifierInstance>& verifier_instance,
    const std::shared_ptr<Transcript>& transcript,
    const HonkProof& proof)
{
    using VerifierCommitments = typename Flavor::VerifierCommitments;
    using Sumcheck = ::bb::SumcheckVerifier<Flavor>;
 
    transcript->load_proof(proof);
    OinkVerifier<Flavor> verifier{ verifier_instance, transcript };
    verifier.verify();
 
    verifier_instance->target_sum = 0;
    // Get the gate challenges for sumcheck/combiner computation
    verifier_instance->gate_challenges =
        transcript->template get_powers_of_challenge<FF>("gate_challenge", Flavor::VIRTUAL_LOG_N);
 
    VerifierCommitments commitments{ verifier_instance->vk, verifier_instance->witness_commitments };
    // DeciderVerifier's log circuit size is fixed, hence we are using a trivial `padding_indicator_array`.
    std::vector<FF> padding_indicator_array(Flavor::VIRTUAL_LOG_N, 1);
 
    Sumcheck sumcheck(transcript, verifier_instance->alphas, Flavor::VIRTUAL_LOG_N, verifier_instance->target_sum);
    SumcheckOutput<Flavor> sumcheck_output = sumcheck.verify(
        verifier_instance->relation_parameters, verifier_instance->gate_challenges, padding_indicator_array);
 
    BB_ASSERT_EQ(sumcheck_output.verified, true, "Sumcheck: Failed native first sumcheck verification.");
 
    FirstSumcheckOutput output{ .challenge = sumcheck_output.challenge,
                                .claimed_evaluations = sumcheck_output.claimed_evaluations };
    auto accumulator = output.batch(verifier_instance, transcript);
 
    return accumulator;
}
 
HonkProof SumcheckClientIVC::construct_sumcheck_proof(const std::shared_ptr<ProverInstance>& prover_instance,
                                                      const std::shared_ptr<MegaVerificationKey>& honk_vk,
                                                      const std::shared_ptr<Transcript>& transcript)
{
    prover_accumulator = SumcheckClientIVC::execute_first_sumcheck(prover_instance, honk_vk, transcript);
    return transcript->export_proof();
}
 
HonkProof SumcheckClientIVC::construct_folding_proof(const std::shared_ptr<ProverInstance>& prover_instance,
                                                     const std::shared_ptr<MegaVerificationKey>& honk_vk,
                                                     const std::shared_ptr<Transcript>& transcript)
{
    vinfo("computing folding proof...");
 
    auto verifier_instance = std::make_shared<VerifierInstance_<Flavor>>(honk_vk);
 
    ProverAccumulator incoming_accumulator =
        SumcheckClientIVC::execute_first_sumcheck(prover_instance, honk_vk, transcript);
 
    MultilinearBatchingProverClaim accumulator_claim{
        .challenge = prover_accumulator.challenge,
        .shifted_evaluation = prover_accumulator.batched_evaluations[1],
        .non_shifted_evaluation = prover_accumulator.batched_evaluations[0],
        .non_shifted_polynomial = prover_accumulator.batched_polynomials[0],
        .shifted_polynomial = prover_accumulator.batched_polynomials[1],
        .non_shifted_commitment = prover_accumulator.batched_commitments[0],
        .shifted_commitment = prover_accumulator.batched_commitments[1],
        .dyadic_size = prover_accumulator.dyadic_size
    };
 
    MultilinearBatchingProverClaim incoming_claim{
        .challenge = incoming_accumulator.challenge,
        .shifted_evaluation = incoming_accumulator.batched_evaluations[1],
        .non_shifted_evaluation = incoming_accumulator.batched_evaluations[0],
        .non_shifted_polynomial = incoming_accumulator.batched_polynomials[0],
        .shifted_polynomial = incoming_accumulator.batched_polynomials[1],
        .non_shifted_commitment = incoming_accumulator.batched_commitments[0],
        .shifted_commitment = incoming_accumulator.batched_commitments[1],
        .dyadic_size = incoming_accumulator.dyadic_size
    };
 
    MultilinearBatchingProver batching_prover(std::make_shared<MultilinearBatchingProverClaim>(accumulator_claim),
                                              std::make_shared<MultilinearBatchingProverClaim>(incoming_claim),
                                              transcript);
 
    HonkProof proof = batching_prover.construct_proof();
    batching_prover.compute_new_claim();
    auto new_accumulator = batching_prover.get_new_claim();
 
    prover_accumulator = ProverAccumulator{
        .challenge = new_accumulator.challenge,
        .batched_evaluations = { new_accumulator.non_shifted_evaluation, new_accumulator.shifted_evaluation },
        .batched_polynomials = { new_accumulator.non_shifted_polynomial, new_accumulator.shifted_polynomial },
        .batched_commitments = { new_accumulator.non_shifted_commitment, new_accumulator.shifted_commitment },
        .dyadic_size = new_accumulator.dyadic_size,
    };
 
    return proof;
}
 
SumcheckClientIVC::QUEUE_TYPE SumcheckClientIVC::get_queue_type() const
{
    // first app
    if (num_circuits_accumulated == 0) {
        return QUEUE_TYPE::OINK;
    }
    // app (excluding first) or kernel (inner or reset)
    if ((num_circuits_accumulated > 0 && num_circuits_accumulated < num_circuits - 3)) {
        return QUEUE_TYPE::PG;
    }
    // last kernel prior to tail kernel
    if ((num_circuits_accumulated == num_circuits - 3)) {
        return QUEUE_TYPE::PG_TAIL;
    }
    // tail kernel
    if ((num_circuits_accumulated == num_circuits - 2)) {
        return QUEUE_TYPE::PG_FINAL;
    }
    // hiding kernel
    if ((num_circuits_accumulated == num_circuits - 1)) {
        return QUEUE_TYPE::MEGA;
    }
    return QUEUE_TYPE{};
}
 
void SumcheckClientIVC::accumulate(ClientCircuit& circuit, const std::shared_ptr<MegaVerificationKey>& precomputed_vk)
{
    BB_ASSERT_LT(num_circuits_accumulated,
                 num_circuits,
                 "SumcheckClientIVC: Attempting to accumulate more circuits than expected.");
 
    ASSERT(precomputed_vk != nullptr, "SumcheckClientIVC::accumulate - VK expected for the provided circuit");
 
    // Construct the prover instance for circuit
    std::shared_ptr<ProverInstance> prover_instance = std::make_shared<ProverInstance>(circuit);
 
    // If the current circuit overflows past the current size of the commitment key, reinitialize accordingly.
    // TODO(https://github.com/AztecProtocol/barretenberg/issues/1319)
    if (prover_instance->dyadic_size() > bn254_commitment_key.dyadic_size) {
        bn254_commitment_key = CommitmentKey<curve::BN254>(prover_instance->dyadic_size());
        goblin.commitment_key = bn254_commitment_key;
    }
    prover_instance->commitment_key = bn254_commitment_key;
 
    // We're accumulating a kernel if the verification queue is empty (because the kernel circuit contains recursive
    // verifiers for all the entries previously present in the verification queue) and if it's not the first accumulate
    // call (which will always be for an app circuit).
    bool is_kernel = verification_queue.empty() && num_circuits_accumulated > 0;
 
    // Transcript to be shared across folding of K_{i} (kernel) (the current kernel), A_{i+1,1} (app), .., A_{i+1,
    // n} (app)
    if (is_kernel) {
        prover_accumulation_transcript = std::make_shared<Transcript>();
    }
 
    // make a copy of the prover_accumulation_transcript for the verifier to use
    auto verifier_transcript =
        Transcript::convert_prover_transcript_to_verifier_transcript(prover_accumulation_transcript);
 
    QUEUE_TYPE queue_type = get_queue_type();
    HonkProof proof;
    switch (queue_type) {
    case QUEUE_TYPE::OINK:
        vinfo("Accumulating first app circuit with OINK");
        BB_ASSERT_EQ(is_kernel, false, "First circuit accumulated must always be an app");
        proof = construct_sumcheck_proof(prover_instance, precomputed_vk, prover_accumulation_transcript);
        break;
    case QUEUE_TYPE::PG:
    case QUEUE_TYPE::PG_TAIL:
        proof = construct_folding_proof(prover_instance, precomputed_vk, prover_accumulation_transcript);
        break;
    case QUEUE_TYPE::PG_FINAL:
        proof = construct_folding_proof(prover_instance, precomputed_vk, prover_accumulation_transcript);
        pcs_proof = construct_pcs_proof(prover_accumulation_transcript);
        break;
    case QUEUE_TYPE::MEGA:
        proof = construct_honk_proof_for_hiding_kernel(circuit, precomputed_vk);
        break;
    }
 
    VerifierInputs queue_entry{ std::move(proof), precomputed_vk, queue_type, is_kernel };
    verification_queue.push_back(queue_entry);
 
    // Update native verifier accumulator and construct merge proof (excluded for hiding kernel since PG terminates with
    // tail kernel and hiding merge proof is constructed as part of goblin proving)
    if (queue_entry.type != QUEUE_TYPE::MEGA) {
        update_native_verifier_accumulator(queue_entry, verifier_transcript);
        goblin.prove_merge(prover_accumulation_transcript);
    }
 
    num_circuits_accumulated++;
}
 
void SumcheckClientIVC::hide_op_queue_accumulation_result(ClientCircuit& circuit)
{
    Point random_point = Point::random_element();
    FF random_scalar = FF::random_element();
    circuit.queue_ecc_mul_accum(random_point, random_scalar);
    circuit.queue_ecc_eq();
}
 
void SumcheckClientIVC::hide_op_queue_content_in_tail(ClientCircuit& circuit)
{
    circuit.queue_ecc_random_op();
    circuit.queue_ecc_random_op();
    circuit.queue_ecc_random_op();
}
 
void SumcheckClientIVC::hide_op_queue_content_in_hiding(ClientCircuit& circuit)
{
    circuit.queue_ecc_random_op();
    circuit.queue_ecc_random_op();
}
 
HonkProof SumcheckClientIVC::construct_honk_proof_for_hiding_kernel(
    ClientCircuit& circuit, const std::shared_ptr<MegaVerificationKey>& verification_key)
{
    // Note: a structured trace is not used for the hiding kernel
    auto hiding_prover_inst = std::make_shared<DeciderZKProvingKey>(circuit, TraceSettings(), bn254_commitment_key);
 
    // Hiding circuit is proven by a MegaZKProver
    MegaZKProver prover(hiding_prover_inst, verification_key, transcript);
    HonkProof proof = prover.construct_proof();
 
    return proof;
}
 
SumcheckClientIVC::Proof SumcheckClientIVC::prove()
{
    // deallocate the protogalaxy accumulator
    prover_accumulator = ProverAccumulator();
    auto mega_proof = verification_queue.front().proof;
 
    // A transcript is shared between the Hiding circuit prover and the Goblin prover
    goblin.transcript = transcript;
 
    // Returns a proof for the hiding circuit and the Goblin proof. The latter consists of Translator and ECCVM proof
    // for the whole ecc op table and the merge proof for appending the subtable coming from the hiding circuit. The
    // final merging is done via appending to facilitate creating a zero-knowledge merge proof. This enables us to add
    // randomness to the beginning of the tail kernel and the end of the hiding kernel, hiding the commitments and
    // evaluations of both the previous table and the incoming subtable.
    // https://github.com/AztecProtocol/barretenberg/issues/1360
    return { mega_proof, goblin.prove(MergeSettings::APPEND) };
};
 
bool SumcheckClientIVC::verify(const Proof& proof, const VerificationKey& vk)
{
    using TableCommitments = Goblin::TableCommitments;
    // Create a transcript to be shared by MegaZK-, Merge-, ECCVM-, and Translator- Verifiers.
    std::shared_ptr<Goblin::Transcript> civc_verifier_transcript = std::make_shared<Goblin::Transcript>();
    // Verify the hiding circuit proof
    MegaZKVerifier verifier{ vk.mega, /*ipa_verification_key=*/{}, civc_verifier_transcript };
    auto [mega_verified, T_prev_commitments] = verifier.template verify_proof<bb::HidingKernelIO>(proof.mega_proof);
    vinfo("Mega verified: ", mega_verified);
    // Extract the commitments to the subtable corresponding to the incoming circuit
    TableCommitments t_commitments = verifier.verifier_instance->witness_commitments.get_ecc_op_wires().get_copy();
 
    // Goblin verification (final merge, eccvm, translator)
    bool goblin_verified = Goblin::verify(
        proof.goblin_proof, { t_commitments, T_prev_commitments }, civc_verifier_transcript, MergeSettings::APPEND);
    vinfo("Goblin verified: ", goblin_verified);
 
    // TODO(https://github.com/AztecProtocol/barretenberg/issues/1396): State tracking in CIVC verifiers.
    return goblin_verified && mega_verified;
}
 
HonkProof SumcheckClientIVC::construct_pcs_proof(const std::shared_ptr<Transcript>& transcript)
{
    vinfo("prove PCS...");
 
    using OpeningClaim = ProverOpeningClaim<Curve>;
    using PolynomialBatcher = GeminiProver_<Curve>::PolynomialBatcher;
 
    auto ck = bn254_commitment_key;
    size_t actual_size = prover_accumulator.batched_polynomials[0].virtual_size();
 
    PolynomialBatcher polynomial_batcher(actual_size);
    polynomial_batcher.set_unshifted(prover_accumulator.batched_polynomials[0]);
    polynomial_batcher.set_to_be_shifted_by_one(prover_accumulator.batched_polynomials[1]);
 
    OpeningClaim prover_opening_claim;
    prover_opening_claim =
        ShpleminiProver_<Curve>::prove(actual_size, polynomial_batcher, prover_accumulator.challenge, ck, transcript);
 
    vinfo("executed multivariate-to-univariate reduction");
    Flavor::PCS::compute_opening_proof(ck, prover_opening_claim, transcript);
    vinfo("computed opening proof");
 
    return transcript->export_proof();
}
 
// Proof methods
size_t SumcheckClientIVC::Proof::size() const
{
    return mega_proof.size() + goblin_proof.size();
}
 
std::vector<SumcheckClientIVC::FF> SumcheckClientIVC::Proof::to_field_elements() const
{
    HonkProof proof;
 
    proof.insert(proof.end(), mega_proof.begin(), mega_proof.end());
    proof.insert(proof.end(), goblin_proof.merge_proof.begin(), goblin_proof.merge_proof.end());
    proof.insert(
        proof.end(), goblin_proof.eccvm_proof.pre_ipa_proof.begin(), goblin_proof.eccvm_proof.pre_ipa_proof.end());
    proof.insert(proof.end(), goblin_proof.eccvm_proof.ipa_proof.begin(), goblin_proof.eccvm_proof.ipa_proof.end());
    proof.insert(proof.end(), goblin_proof.translator_proof.begin(), goblin_proof.translator_proof.end());
    return proof;
};
 
SumcheckClientIVC::Proof SumcheckClientIVC::Proof::from_field_elements(const std::vector<SumcheckClientIVC::FF>& fields)
{
    HonkProof mega_proof;
    GoblinProof goblin_proof;
 
    size_t custom_public_inputs_size = fields.size() - SumcheckClientIVC::Proof::PROOF_LENGTH();
 
    // Mega proof
    auto start_idx = fields.begin();
    auto end_idx = start_idx + static_cast<std::ptrdiff_t>(
                                   MegaZKFlavor::PROOF_LENGTH_WITHOUT_PUB_INPUTS(MegaZKFlavor::VIRTUAL_LOG_N) +
                                   bb::HidingKernelIO::PUBLIC_INPUTS_SIZE + custom_public_inputs_size);
    mega_proof.insert(mega_proof.end(), start_idx, end_idx);
 
    // Merge proof
    start_idx = end_idx;
    end_idx += static_cast<std::ptrdiff_t>(MERGE_PROOF_SIZE);
    goblin_proof.merge_proof.insert(goblin_proof.merge_proof.end(), start_idx, end_idx);
 
    // ECCVM pre-ipa proof
    start_idx = end_idx;
    end_idx += static_cast<std::ptrdiff_t>(ECCVMFlavor::PROOF_LENGTH_WITHOUT_PUB_INPUTS - IPA_PROOF_LENGTH);
    goblin_proof.eccvm_proof.pre_ipa_proof.insert(goblin_proof.eccvm_proof.pre_ipa_proof.end(), start_idx, end_idx);
 
    // ECCVM ipa proof
    start_idx = end_idx;
    end_idx += static_cast<std::ptrdiff_t>(IPA_PROOF_LENGTH);
    goblin_proof.eccvm_proof.ipa_proof.insert(goblin_proof.eccvm_proof.ipa_proof.end(), start_idx, end_idx);
 
    // Translator proof
    start_idx = end_idx;
    end_idx += static_cast<std::ptrdiff_t>(TranslatorFlavor::PROOF_LENGTH_WITHOUT_PUB_INPUTS);
    goblin_proof.translator_proof.insert(goblin_proof.translator_proof.end(), start_idx, end_idx);
 
    return { mega_proof, goblin_proof };
};
 
msgpack::sbuffer SumcheckClientIVC::Proof::to_msgpack_buffer() const
{
    msgpack::sbuffer buffer;
    msgpack::pack(buffer, *this);
    return buffer;
}
 
uint8_t* SumcheckClientIVC::Proof::to_msgpack_heap_buffer() const
{
    msgpack::sbuffer buffer = to_msgpack_buffer();
 
    std::vector<uint8_t> buf(buffer.data(), buffer.data() + buffer.size());
    return to_heap_buffer(buf);
}
 
SumcheckClientIVC::Proof SumcheckClientIVC::Proof::from_msgpack_buffer(uint8_t const*& buffer)
{
    auto uint8_buffer = from_buffer<std::vector<uint8_t>>(buffer);
 
    msgpack::sbuffer sbuf;
    sbuf.write(reinterpret_cast<char*>(uint8_buffer.data()), uint8_buffer.size());
 
    return from_msgpack_buffer(sbuf);
}
 
SumcheckClientIVC::Proof SumcheckClientIVC::Proof::from_msgpack_buffer(const msgpack::sbuffer& buffer)
{
    msgpack::object_handle oh = msgpack::unpack(buffer.data(), buffer.size());
    msgpack::object obj = oh.get();
    Proof proof;
    obj.convert(proof);
    return proof;
}
 
void SumcheckClientIVC::Proof::to_file_msgpack(const std::string& filename) const
{
    msgpack::sbuffer buffer = to_msgpack_buffer();
    std::ofstream ofs(filename, std::ios::binary);
    if (!ofs.is_open()) {
        throw_or_abort("Failed to open file for writing.");
    }
    ofs.write(buffer.data(), static_cast<std::streamsize>(buffer.size()));
    ofs.close();
}
 
SumcheckClientIVC::Proof SumcheckClientIVC::Proof::from_file_msgpack(const std::string& filename)
{
    std::ifstream ifs(filename, std::ios::binary);
    if (!ifs.is_open()) {
        throw_or_abort("Failed to open file for reading.");
    }
 
    ifs.seekg(0, std::ios::end);
    size_t file_size = static_cast<size_t>(ifs.tellg());
    ifs.seekg(0, std::ios::beg);
 
    std::vector<char> buffer(file_size);
    ifs.read(buffer.data(), static_cast<std::streamsize>(file_size));
    ifs.close();
    msgpack::sbuffer msgpack_buffer;
    msgpack_buffer.write(buffer.data(), file_size);
 
    return Proof::from_msgpack_buffer(msgpack_buffer);
}
 
// VerificationKey construction
SumcheckClientIVC::VerificationKey SumcheckClientIVC::get_vk() const
{
    BB_ASSERT_EQ(verification_queue.size(), 1UL);
    BB_ASSERT_EQ(verification_queue.front().type == QUEUE_TYPE::MEGA, true);
    auto verification_key = verification_queue.front().honk_vk;
    return { verification_key,
             std::make_shared<ECCVMVerificationKey>(),
             std::make_shared<TranslatorVerificationKey>() };
}
 
void SumcheckClientIVC::update_native_verifier_accumulator(const VerifierInputs& queue_entry,
                                                           const std::shared_ptr<Transcript>& verifier_transcript)
{
    auto verifier_inst = std::make_shared<VerifierInstance>(queue_entry.honk_vk);
 
    auto incoming_accumulator =
        execute_first_sumcheck_native_verification(verifier_inst, verifier_transcript, queue_entry.proof);
 
    if (queue_entry.type != QUEUE_TYPE::OINK) {
        MultilinearBatchingVerifier<MultilinearBatchingFlavor> batching_verifier(verifier_transcript);
        auto [verified, new_accumulator] = batching_verifier.verify_proof();
        BB_ASSERT_EQ(verified, true, "Batching Sumcheck: Failed native sumcheck batching verification");
 
        native_verifier_accum = VerifierAccumulator{
            .challenge = new_accumulator.challenge,
            .batched_evaluations = { new_accumulator.non_shifted_evaluation, new_accumulator.shifted_evaluation },
            .batched_commitments = { new_accumulator.non_shifted_commitment, new_accumulator.shifted_commitment },
        };
    } else {
        native_verifier_accum = incoming_accumulator;
    }
}
 
} // namespace bb