sumcheck.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Khashayar], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "barretenberg/common/bb_bench.hpp"
#include "barretenberg/flavor/flavor_concepts.hpp"
#include "barretenberg/honk/library/grand_product_delta.hpp"
#include "barretenberg/polynomials/eq_polynomial.hpp"
#include "barretenberg/polynomials/fold_stride2.hpp"
#include "barretenberg/polynomials/polynomial.hpp"
#include "barretenberg/polynomials/polynomial_arithmetic.hpp"
#include "barretenberg/sumcheck/sumcheck_output.hpp"
#include "barretenberg/transcript/transcript.hpp"
#include "barretenberg/ultra_honk/prover_instance.hpp"
#include "sumcheck_round.hpp"
#include <memory>
 
namespace bb {
 
template <typename Flavor, bool CommittedSumcheck = UsesCommittedSumcheck<Flavor>> struct RoundUnivariateHandler {
    using FF = typename Flavor::FF;
    using Transcript = typename Flavor::Transcript;
    using CommitmentKey = typename Flavor::CommitmentKey;
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH;
 
    std::shared_ptr<Transcript> transcript;
 
    RoundUnivariateHandler(std::shared_ptr<Transcript> transcript)
        : transcript(std::move(transcript))
    {
        BB_ASSERT(this->transcript != nullptr, "RoundUnivariateHandler: transcript must not be null");
    }
 
    void process_round_univariate(size_t round_idx,
                                  bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>& round_univariate)
    {
        transcript->send_to_verifier("Sumcheck:univariate_" + std::to_string(round_idx), round_univariate);
    }
 
    void finalize_last_round(size_t /*multivariate_d*/,
                             const bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>& /*round_univariate*/,
                             const FF& /*last_challenge*/)
    {}
 
    std::vector<std::array<FF, 3>> get_evaluations() { return {}; }
    std::vector<Polynomial<FF>> get_univariates() { return {}; }
    std::vector<typename Flavor::Commitment> get_commitments() { return {}; }
};
 
template <typename Flavor> struct RoundUnivariateHandler<Flavor, true> {
    using FF = typename Flavor::FF;
    using Transcript = typename Flavor::Transcript;
    using CommitmentKey = typename Flavor::CommitmentKey;
    using Commitment = typename Flavor::Commitment;
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH;
 
    std::shared_ptr<Transcript> transcript;
    CommitmentKey ck;
    std::vector<FF> eval_domain;
    std::vector<std::array<FF, 3>> round_evaluations;
    std::vector<Polynomial<FF>> round_univariates;
    std::vector<Commitment> round_commitments;
 
    RoundUnivariateHandler(std::shared_ptr<Transcript> transcript)
        : transcript(std::move(transcript))
        , ck(BATCHED_RELATION_PARTIAL_LENGTH)
    {
        BB_ASSERT(this->transcript != nullptr, "RoundUnivariateHandler: transcript must not be null");
        // Compute the vector {0, 1, \ldots, BATCHED_RELATION_PARTIAL_LENGTH-1} needed to transform
        // the round univariates from Lagrange to monomial basis
        eval_domain.reserve(BATCHED_RELATION_PARTIAL_LENGTH);
        for (size_t idx = 0; idx < BATCHED_RELATION_PARTIAL_LENGTH; idx++) {
            eval_domain.push_back(FF(idx));
        }
    }
 
    void process_round_univariate(size_t round_idx,
                                  bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>& round_univariate)
    {
        const std::string idx = std::to_string(round_idx);
 
        // Transform to monomial form and commit to it
        Polynomial<FF> round_poly_monomial(
            eval_domain, std::span<FF>(round_univariate.evaluations), BATCHED_RELATION_PARTIAL_LENGTH);
        auto round_commitment = ck.commit(round_poly_monomial);
        transcript->send_to_verifier("Sumcheck:univariate_comm_" + idx, round_commitment);
        round_commitments.push_back(round_commitment);
 
        // Store round univariate in monomial, as it is required by Shplemini
        round_univariates.push_back(std::move(round_poly_monomial));
 
        // Send the evaluations of the round univariate at 0 and 1
        transcript->send_to_verifier("Sumcheck:univariate_" + idx + "_eval_0", round_univariate.value_at(0));
        transcript->send_to_verifier("Sumcheck:univariate_" + idx + "_eval_1", round_univariate.value_at(1));
 
        // Store the evaluations to be used by ShpleminiProver.
        round_evaluations.push_back({ round_univariate.value_at(0), round_univariate.value_at(1), FF(0) });
        if (round_idx > 0) {
            round_evaluations[round_idx - 1][2] = round_univariate.value_at(0) + round_univariate.value_at(1);
        }
    }
 
    void finalize_last_round(size_t multivariate_d,
                             const bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>& round_univariate,
                             const FF& last_challenge)
    {
        round_evaluations[multivariate_d - 1][2] = round_univariate.evaluate(last_challenge);
    }
 
    // The members are moved out: each getter is called once at the end of `prove`, after which the handler is dead.
    std::vector<std::array<FF, 3>> get_evaluations() { return std::move(round_evaluations); }
    std::vector<Polynomial<FF>> get_univariates() { return std::move(round_univariates); }
    std::vector<Commitment> get_commitments() { return std::move(round_commitments); }
};
 
template <typename Flavor, bool HasZK = Flavor::HasZK> struct VerifierZKCorrectionHandler {
    using FF = typename Flavor::FF;
    using Transcript = typename Flavor::Transcript;
    using SumcheckRound = SumcheckVerifierRound<Flavor>;
 
    std::shared_ptr<Transcript> transcript;
    FF libra_challenge = FF{ 0 };
    FF libra_evaluation = FF{ 0 };
 
    // Construct a handler which will handle all the evaluations/
    VerifierZKCorrectionHandler(std::shared_ptr<Transcript> transcript)
        : transcript(std::move(transcript))
    {}
 
    void initialize_target_sum(SumcheckRound& /*round*/) {}
 
    void apply_zk_corrections(FF& /*full_honk_purported_value*/, const std::vector<FF>& /*multivariate_challenge*/) {}
 
    FF get_libra_evaluation() const { return libra_evaluation; }
};
 
template <typename Flavor> struct VerifierZKCorrectionHandler<Flavor, true> {
    using FF = typename Flavor::FF;
    using Transcript = typename Flavor::Transcript;
    using SumcheckRound = SumcheckVerifierRound<Flavor>;
 
    std::shared_ptr<Transcript> transcript;
    FF libra_total_sum = FF{ 0 };
    FF libra_challenge = FF{ 0 };
    FF libra_evaluation = FF{ 0 };
 
    VerifierZKCorrectionHandler(std::shared_ptr<Transcript> transcript)
        : transcript(std::move(transcript))
    {}
 
    // If running zero-knowledge sumcheck the target total sum is corrected by the claimed sum of libra masking
    // multivariate over the hypercube.
    void initialize_target_sum(SumcheckRound& round)
    {
        libra_total_sum = transcript->template receive_from_prover<FF>("Libra:Sum");
        libra_challenge = transcript->template get_challenge<FF>("Libra:Challenge");
        round.target_total_sum = libra_total_sum * libra_challenge;
    }
 
    void apply_zk_corrections(FF& full_honk_purported_value, std::vector<FF>& multivariate_challenge)
    {
 
        // Get the claimed evaluation of the Libra multivariate evaluated at the sumcheck challenge
        libra_evaluation = transcript->template receive_from_prover<FF>("Libra:claimed_evaluation");
 
        // OriginTag false positive: libra_evaluation is PCS-bound (verified by Shplemini opening).
        // Once commitments are fixed and sumcheck challenges derived, the correct evaluation is determined.
        if constexpr (IsRecursiveFlavor<Flavor>) {
            const auto challenge_tag = multivariate_challenge.back().get_origin_tag();
            libra_evaluation.set_origin_tag(challenge_tag);
        }
 
        full_honk_purported_value += libra_evaluation * libra_challenge;
    }
 
    FF get_libra_evaluation() const { return libra_evaluation; }
};
 
template <typename Flavor> class SumcheckProver {
  public:
    using FF = typename Flavor::FF;
    // PartiallyEvaluatedMultivariates OR ProverPolynomials
    // both inherit from AllEntities
    using ProverPolynomials = typename Flavor::ProverPolynomials;
    using PartiallyEvaluatedMultivariates = typename Flavor::PartiallyEvaluatedMultivariates;
    using ClaimedEvaluations = typename Flavor::AllValues;
    using ZKData = ZKSumcheckData<Flavor>;
    using Transcript = typename Flavor::Transcript;
    using SubrelationSeparators = std::array<FF, Flavor::NUM_SUBRELATIONS - 1>;
    using CommitmentKey = typename Flavor::CommitmentKey;
 
    static constexpr bool isMultilinearBatchingFlavor = bb::isMultilinearBatchingFlavor<Flavor>;
    static constexpr size_t MAX_PARTIAL_RELATION_LENGTH = Flavor::MAX_PARTIAL_RELATION_LENGTH;
 
    // this constant specifies the number of coefficients of libra polynomials, and evaluations of round univariate
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH;
 
    using SumcheckRoundUnivariate = typename bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>;
 
    // The size of the hypercube, i.e. \f$ 2^d\f$.
    const size_t multivariate_n;
    // The number of variables
    const size_t multivariate_d;
    // A reference to all prover multilinear polynomials.
    ProverPolynomials& full_polynomials;
 
    std::shared_ptr<Transcript> transcript;
    // Contains the core sumcheck methods such as `compute_univariate`.
    SumcheckProverRound<Flavor> round;
    // An array of size NUM_SUBRELATIONS-1 containing challenges or consecutive powers of a single challenge that
    // separate linearly independent subrelation.
    SubrelationSeparators alphas;
    // pow_β(X₀, ..., X_{d−1}) = ∏ₖ₌₀^{d−1} (1 − Xₖ + Xₖ ⋅ βₖ)
    std::vector<FF> gate_challenges;
    // Contains various challenges, such as `beta` and `gamma` used in the Grand Product argument.
    bb::RelationParameters<FF> relation_parameters;
 
    // Determines the number of rounds in the sumcheck (may include padding rounds, i.e. >= multivariate_d).
    size_t virtual_log_n;
 
    std::vector<FF> multivariate_challenge;
 
    FF libra_evaluation = FF{ 0 };
 
    RowDisablingPolynomial<FF> row_disabling_polynomial;
 
    // SumcheckProver constructor for the Flavors that generate a single challenge `alpha` and use its powers as
    // subrelation seperator challenges.
    SumcheckProver(size_t multivariate_n,
                   ProverPolynomials& prover_polynomials,
                   std::shared_ptr<Transcript> transcript,
                   const FF& alpha,
                   const std::vector<FF>& gate_challenges,
                   const RelationParameters<FF>& relation_parameters,
                   const size_t virtual_log_n)
        : multivariate_n(multivariate_n)
        , multivariate_d(numeric::get_msb(multivariate_n))
        , full_polynomials(prover_polynomials)
        , transcript(std::move(transcript))
        , round(multivariate_n)
        , alphas(initialize_relation_separator<FF, Flavor::NUM_SUBRELATIONS - 1>(alpha))
        , gate_challenges(gate_challenges)
        , relation_parameters(relation_parameters)
        , virtual_log_n(virtual_log_n)
    {
        // multivariate_d = get_msb(multivariate_n) only gives the correct round count for a power-of-two size.
        BB_ASSERT(multivariate_n != 0 && (multivariate_n & (multivariate_n - 1)) == 0,
                  "SumcheckProver: multivariate_n must be a power of two");
        if constexpr (isMultilinearBatchingFlavor) {
            BB_ASSERT_EQ(relation_parameters.num_multilinear_batching_challenges,
                         Flavor::NUM_CLAIMS,
                         "Incorrect number of computed multilinear batching challenges.");
            BB_ASSERT_EQ(gate_challenges.size(),
                         0U,
                         "Sumcheck Prover: Multilinear batching flavor has only dependent relations, no gate "
                         "challenges should be provided.");
        } else {
            // The rounds index gate_challenges through GateSeparatorPolynomial assuming at least multivariate_d
            // entries.
            BB_ASSERT_GTE(gate_challenges.size(), multivariate_d, "SumcheckProver: fewer gate challenges than rounds");
        }
    };
    SumcheckOutput<Flavor> prove()
        requires(!Flavor::HasZK)
    {
        vinfo("starting sumcheck rounds...");
 
        // Given gate challenges β = (β₀, ..., β_{d−1}) and d = `multivariate_d`, compute the evaluations of
        // GateSeparator_β (X₀, ..., X_{d−1}) = ∏ₖ₌₀^{d−1} (1 − Xₖ + Xₖ · βₖ)
        // on the boolean hypercube.
        GateSeparatorPolynomial<FF> gate_separators(gate_challenges, multivariate_d);
 
        multivariate_challenge.reserve(virtual_log_n);
        // In the first round, we compute the first univariate polynomial and populate the book-keeping table of
        // #partially_evaluated_polynomials, which has \f$ n/2 \f$ rows and \f$ N \f$ columns.
        PartiallyEvaluatedMultivariates partially_evaluated_polynomials = [&] {
            BB_BENCH_NAME("sumcheck loop 0");
            auto round_univariate =
                round.compute_univariate(full_polynomials, relation_parameters, gate_separators, alphas);
 
            // Place the evaluations of the round univariate into transcript.
            transcript->send_to_verifier("Sumcheck:univariate_0", round_univariate);
            FF round_challenge = transcript->template get_challenge<FF>("Sumcheck:u_0");
            multivariate_challenge.emplace_back(round_challenge);
 
            // Populate the book-keeping table
            auto result = partially_evaluate_first_round(full_polynomials, round_challenge);
            gate_separators.partially_evaluate(round_challenge);
            round.advance_round();
            return result;
        }();
        for (size_t round_idx = 1; round_idx < multivariate_d; round_idx++) {
            BB_BENCH_NAME("sumcheck loop");
 
            // Write the round univariate to the transcript
            auto round_univariate =
                round.compute_univariate(partially_evaluated_polynomials, relation_parameters, gate_separators, alphas);
            // Place evaluations of Sumcheck Round Univariate in the transcript
            transcript->send_to_verifier("Sumcheck:univariate_" + std::to_string(round_idx), round_univariate);
            FF round_challenge = transcript->template get_challenge<FF>("Sumcheck:u_" + std::to_string(round_idx));
            multivariate_challenge.emplace_back(round_challenge);
            // Prepare sumcheck book-keeping table for the next round.
            partially_evaluate_in_place(partially_evaluated_polynomials, round_challenge);
            gate_separators.partially_evaluate(round_challenge);
            round.advance_round();
        }
        vinfo("completed ", multivariate_d, " rounds of sumcheck");
 
        GateSeparatorPolynomial<FF> virtual_gate_separator(gate_challenges, multivariate_challenge);
        // If required, extend prover's multilinear polynomials in `multivariate_d` variables by zero to get multilinear
        // polynomials in `virtual_log_n` variables.
        for (size_t k = multivariate_d; k < virtual_log_n; ++k) {
            if constexpr (isMultilinearBatchingFlavor) {
                // We need to specify the evaluation at index 1 for eq polynomials
                Flavor::extend_eq_polynomials_for_virtual_round(
                    partially_evaluated_polynomials, multivariate_challenge, k);
            }
            // Compute the contribution from the extensions by zero. It is sufficient to evaluate the main constraint at
            // `MAX_PARTIAL_RELATION_LENGTH` points.
            const auto virtual_round_univariate = round.compute_virtual_contribution(
                partially_evaluated_polynomials, relation_parameters, virtual_gate_separator, alphas);
 
            transcript->send_to_verifier("Sumcheck:univariate_" + std::to_string(k), virtual_round_univariate);
 
            const FF round_challenge = transcript->template get_challenge<FF>("Sumcheck:u_" + std::to_string(k));
            multivariate_challenge.emplace_back(round_challenge);
 
            // Update the book-keeping table of partial evaluations of the prover polynomials extended by zero.
            for (auto& poly : partially_evaluated_polynomials.get_all()) {
                // Avoid bad access if polynomials are set to be of size 0, which can happen in AVM.
                if (poly.size() > 0) {
                    if (poly.size() == 1) {
                        poly.at(0) *= (FF(1) - round_challenge);
                    } else if (poly.size() == 2) {
                        // Here we handle the eq polynomial case
                        poly.at(0) = poly.at(0) * (FF(1) - round_challenge) + poly.at(1) * round_challenge;
                        poly.at(1) = 0;
                    } else {
                        BB_ASSERT_EQ(true, false, "Polynomial size is not 1 or 2");
                    }
                }
            }
            virtual_gate_separator.partially_evaluate(round_challenge);
        }
 
        ClaimedEvaluations multivariate_evaluations = extract_claimed_evaluations(partially_evaluated_polynomials);
        transcript->send_to_verifier("Sumcheck:evaluations", multivariate_evaluations.get_all());
 
        vinfo("finished sumcheck");
        return SumcheckOutput<Flavor>{ .challenge = multivariate_challenge,
                                       .claimed_evaluations = multivariate_evaluations };
    };
 
    SumcheckOutput<Flavor> prove(ZKData& zk_sumcheck_data)
        requires Flavor::HasZK
    {
        RoundUnivariateHandler<Flavor> handler(transcript);
        vinfo("starting sumcheck rounds...");
        // Given gate challenges β = (β₀, ..., β_{d−1}) and d = `multivariate_d`, compute the evaluations of
        // GateSeparator_β (X₀, ..., X_{d−1}) = ∏ₖ₌₀^{d−1} (1 − Xₖ + Xₖ · βₖ)
        // on the boolean hypercube.
        GateSeparatorPolynomial<FF> gate_separators(gate_challenges, multivariate_d);
 
        multivariate_challenge.reserve(multivariate_d);
        size_t round_idx = 0;
 
        // In the first round, we compute the first univariate polynomial and populate the book-keeping table of
        // #partially_evaluated_polynomials, which has \f$ n/2 \f$ rows and \f$ N \f$ columns.
 
        // Compute the round univariate (excludes disabled rows; handled separately below)
        auto round_univariate =
            round.compute_univariate(full_polynomials, relation_parameters, gate_separators, alphas);
 
        // Add the contribution from the Libra univariates
        auto hiding_univariate = round.compute_libra_univariate(zk_sumcheck_data, round_idx);
        round_univariate += hiding_univariate;
 
        // Handle disabled rows contribution
        if constexpr (UseRowDisablingPolynomial<Flavor>) {
            round_univariate += round.compute_offset_area_contribution(
                full_polynomials, relation_parameters, gate_separators, alphas, row_disabling_polynomial);
        }
 
        handler.process_round_univariate(round_idx, round_univariate);
 
        const FF round_challenge = transcript->template get_challenge<FF>("Sumcheck:u_0");
        multivariate_challenge.emplace_back(round_challenge);
 
        // Populate the book-keeping table
        PartiallyEvaluatedMultivariates partially_evaluated_polynomials =
            partially_evaluate_first_round(full_polynomials, round_challenge);
 
        // Prepare ZK Sumcheck data for the next round
        zk_sumcheck_data.update_zk_sumcheck_data(round_challenge, round_idx);
        row_disabling_polynomial.update_evaluations(round_challenge, round_idx);
        gate_separators.partially_evaluate(round_challenge);
        round.advance_round();
        if constexpr (UseRowDisablingPolynomial<Flavor>) {
            round.excluded_head_size = 2; // After round 0, disabled zone collapses to 1 edge pair
        }
        for (size_t round_idx = 1; round_idx < multivariate_d; round_idx++) {
            BB_BENCH_NAME("sumcheck loop");
 
            // Computes the round univariate in two parts: first the contribution necessary to hide the polynomial and
            // account for having randomness at the end of the trace and then the contribution from the full
            // relation. Note: we compute the hiding univariate first as the `compute_univariate` method prepares
            // relevant data structures for the next round
            round_univariate =
                round.compute_univariate(partially_evaluated_polynomials, relation_parameters, gate_separators, alphas);
            hiding_univariate = round.compute_libra_univariate(zk_sumcheck_data, round_idx);
            // Add the contribution from the Libra univariates
            round_univariate += hiding_univariate;
            // Handle disabled rows contribution
            if constexpr (UseRowDisablingPolynomial<Flavor>) {
                round_univariate += round.compute_offset_area_contribution(partially_evaluated_polynomials,
                                                                           relation_parameters,
                                                                           gate_separators,
                                                                           alphas,
                                                                           row_disabling_polynomial);
            }
 
            handler.process_round_univariate(round_idx, round_univariate);
 
            const FF round_challenge =
                transcript->template get_challenge<FF>("Sumcheck:u_" + std::to_string(round_idx));
            multivariate_challenge.emplace_back(round_challenge);
 
            // Prepare sumcheck book-keeping table for the next round.
            partially_evaluate_in_place(partially_evaluated_polynomials, round_challenge);
 
            if constexpr (IsTranslatorFlavor<Flavor>) {
                if (round_idx == Flavor::LOG_MINI_CIRCUIT_SIZE - 1) {
                    // Send mini-circuit evaluations mid-sumcheck so that they get hashed into the transcript,
                    // ensuring the remaining LOG_N - LOG_MINI_CIRCUIT_SIZE round challenges depend on them.
                    transcript->send_to_verifier("Sumcheck:minicircuit_evaluations",
                                                 Flavor::get_minicircuit_evaluations(partially_evaluated_polynomials));
                }
            }
 
            // Prepare evaluation masking and libra structures for the next round (for ZK Flavors)
            zk_sumcheck_data.update_zk_sumcheck_data(round_challenge, round_idx);
            row_disabling_polynomial.update_evaluations(round_challenge, round_idx);
 
            gate_separators.partially_evaluate(round_challenge);
            round.advance_round();
        }
 
        handler.finalize_last_round(multivariate_d, round_univariate, multivariate_challenge[multivariate_d - 1]);
 
        vinfo("completed ", multivariate_d, " rounds of sumcheck");
 
        // Virtual rounds: unified path for ZK and non-ZK.
        // The row-disabling polynomial 1-L is circuit-size independent,
        // so we continue updating it through virtual rounds. The verifier evaluates
        // 1 - ∏_{i≥2}(1-u_i) over ALL D challenges — no log_n needed.
        // Libra univariates are generated for ALL D rounds, so compute_libra_univariate works here too.
        GateSeparatorPolynomial<FF> virtual_gate_separator(gate_challenges, multivariate_challenge);
        for (size_t idx = multivariate_d; idx < virtual_log_n; idx++) {
            round_univariate = compute_virtual_round_univariate(round,
                                                                partially_evaluated_polynomials,
                                                                relation_parameters,
                                                                virtual_gate_separator,
                                                                alphas,
                                                                row_disabling_polynomial);
 
            hiding_univariate = round.compute_libra_univariate(zk_sumcheck_data, idx);
            round_univariate += hiding_univariate;
 
            handler.process_round_univariate(idx, round_univariate);
            const FF round_challenge = transcript->template get_challenge<FF>("Sumcheck:u_" + std::to_string(idx));
            multivariate_challenge.emplace_back(round_challenge);
 
            fold_for_zero_extension(partially_evaluated_polynomials, round_challenge);
            zk_sumcheck_data.update_zk_sumcheck_data(round_challenge, idx);
            row_disabling_polynomial.update_evaluations(round_challenge, idx);
            virtual_gate_separator.partially_evaluate(round_challenge);
        }
 
        // Claimed evaluations of Prover polynomials are extracted and added to the transcript.
        ClaimedEvaluations multivariate_evaluations = extract_claimed_evaluations(partially_evaluated_polynomials);
 
        // For Translator: send only the full-circuit evaluations
        if constexpr (IsTranslatorFlavor<Flavor>) {
            transcript->send_to_verifier("Sumcheck:evaluations",
                                         Flavor::get_full_circuit_evaluations(multivariate_evaluations));
        } else {
            transcript->send_to_verifier("Sumcheck:evaluations", multivariate_evaluations.get_all());
        }
 
        // Libra evaluation covers all D rounds now (real + virtual).
        FF libra_evaluation = zk_sumcheck_data.constant_term;
        for (const auto& libra_eval : zk_sumcheck_data.libra_evaluations) {
            libra_evaluation += libra_eval;
        }
        transcript->send_to_verifier("Libra:claimed_evaluation", libra_evaluation);
 
        // The sum of the Libra constant term and the evaluations of Libra univariates at corresponding sumcheck
        // challenges is included in the Sumcheck Output
        vinfo("finished sumcheck");
        return SumcheckOutput<Flavor>{ .challenge = multivariate_challenge,
                                       .claimed_evaluations = multivariate_evaluations,
                                       .claimed_libra_evaluation = libra_evaluation,
                                       .round_univariate_commitments = handler.get_commitments(),
                                       .round_univariates = handler.get_univariates(),
                                       .round_univariate_evaluations = handler.get_evaluations() };
    };
 
    static void partially_evaluate(auto& source_polynomials,
                                   PartiallyEvaluatedMultivariates& dest_polynomials,
                                   const FF& round_challenge)
    {
        auto source_view = source_polynomials.get_all();
        auto dest_view = dest_polynomials.get_all();
        parallel_for(source_view.size(), [&](size_t j) {
            BB_BENCH_TRACY_NAME("Sumcheck::partially_evaluate");
            const auto& poly = source_view[j];
            auto& dest = dest_view[j];
            const size_t limit = poly.end_index();
            // One output per source pair (2k, 2k+1); when limit is odd the last source slot is unpaired
            // and folds against an implicit zero, so we round up: ceil(limit / 2).
            const size_t num_outputs = (limit / 2) + (limit % 2);
            fold_stride2(poly, dest, /*begin=*/0, /*end=*/num_outputs, round_challenge);
            dest.shrink_end_index(num_outputs);
        });
        // Halve the active-row prefix to track the folded trace; the loop above leaves the member untouched, so this
        // reads the pre-round value even when source and dest alias (see partially_evaluate_in_place).
        if constexpr (requires {
                          source_polynomials.row_skip_active_prefix_end;
                          dest_polynomials.row_skip_active_prefix_end;
                      }) {
            dest_polynomials.row_skip_active_prefix_end = (source_polynomials.row_skip_active_prefix_end / 2) +
                                                          (source_polynomials.row_skip_active_prefix_end % 2);
        }
    };
 
    PartiallyEvaluatedMultivariates partially_evaluate_first_round(ProverPolynomials& full_polynomials,
                                                                   const FF& round_challenge)
    {
        PartiallyEvaluatedMultivariates partially_evaluated_polynomials(full_polynomials, multivariate_n);
        partially_evaluate(full_polynomials, partially_evaluated_polynomials, round_challenge);
        return partially_evaluated_polynomials;
    }
 
    static void partially_evaluate_in_place(PartiallyEvaluatedMultivariates& polynomials, const FF& round_challenge)
    {
        partially_evaluate(polynomials, polynomials, round_challenge);
    };
 
    ClaimedEvaluations extract_claimed_evaluations(PartiallyEvaluatedMultivariates& partially_evaluated_polynomials)
    {
        ClaimedEvaluations multivariate_evaluations;
        for (auto [eval, poly] :
             zip_view(multivariate_evaluations.get_all(), partially_evaluated_polynomials.get_all())) {
            eval = poly[0];
        };
        return multivariate_evaluations;
    };
 
    template <typename PartialEvals, typename Alphas>
    static bb::Univariate<FF, Flavor::BATCHED_RELATION_PARTIAL_LENGTH> compute_virtual_round_univariate(
        SumcheckProverRound<Flavor>& round,
        PartialEvals& partially_evaluated_polynomials,
        const RelationParameters<FF>& relation_parameters,
        GateSeparatorPolynomial<FF>& gate_separator,
        const Alphas& alphas,
        RowDisablingPolynomial<FF>& row_disabling_polynomial)
    {
        // Row-disabling flavors batch with per-relation L / (1 - L). Non-row-disabling flavors
        // pass nullptr so the callee's factor defaults collapse to plain α-batching.
        const RowDisablingPolynomial<FF>* rd = UseRowDisablingPolynomial<Flavor> ? &row_disabling_polynomial : nullptr;
        return round.compute_virtual_contribution(
            partially_evaluated_polynomials, relation_parameters, gate_separator, alphas, rd);
    }
 
    static void fold_for_zero_extension(PartiallyEvaluatedMultivariates& pe, const FF& round_challenge)
    {
        for (auto& poly : pe.get_all()) {
            if (poly.end_index() > 0) {
                poly.at(0) *= (FF(1) - round_challenge);
            }
        }
    }
};
 
template <typename Flavor> class SumcheckVerifier {
 
  public:
    using Utils = bb::RelationUtils<Flavor>;
    using FF = typename Flavor::FF;
    using ClaimedEvaluations = typename Flavor::AllValues;
    // For ZK Flavors: the verifier obtains a vector of evaluations of \f$ d \f$ univariate polynomials and uses them to
    // compute full_honk_relation_purported_value
    using ClaimedLibraEvaluations = typename std::vector<FF>;
    using Transcript = typename Flavor::Transcript;
    using SubrelationSeparators = std::array<FF, Flavor::NUM_SUBRELATIONS - 1>;
    using Commitment = typename Flavor::Commitment;
 
    static constexpr bool isMultilinearBatchingFlavor = bb::isMultilinearBatchingFlavor<Flavor>;
 
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH;
    static constexpr size_t NUM_POLYNOMIALS = Flavor::NUM_ALL_ENTITIES;
 
    std::shared_ptr<Transcript> transcript;
    SumcheckVerifierRound<Flavor> round;
 
    // Determines number of rounds in the sumcheck (may include padding rounds)
    size_t virtual_log_n;
 
    // An array of size NUM_SUBRELATIONS-1 containing challenges or consecutive powers of a single challenge that
    // separate linearly independent subrelation.
    SubrelationSeparators alphas;
 
    explicit SumcheckVerifier(std::shared_ptr<Transcript> transcript,
                              const FF& alpha,
                              size_t virtual_log_n,
                              FF target_sum = 0)
        : transcript(std::move(transcript))
        , round(target_sum)
        , virtual_log_n(virtual_log_n)
        , alphas(initialize_relation_separator<FF, Flavor::NUM_SUBRELATIONS - 1>(alpha)) {};
    SumcheckOutput<Flavor> verify(const bb::RelationParameters<FF>& relation_parameters,
                                  const std::vector<FF>& gate_challenges)
    {
        if constexpr (isMultilinearBatchingFlavor) {
            BB_ASSERT_EQ(relation_parameters.num_multilinear_batching_challenges,
                         Flavor::NUM_CLAIMS,
                         "Incorrect number of computed multilinear batching challenges.");
        }
 
        bb::GateSeparatorPolynomial<FF> gate_separators(gate_challenges);
        // Construct a ZKHandler to handle all the libra related information in the transcript
        VerifierZKCorrectionHandler<Flavor> zk_correction_handler(transcript);
 
        // Correct the target sum in the round in the ZK case
        zk_correction_handler.initialize_target_sum(round);
 
        std::vector<FF> multivariate_challenge;
        multivariate_challenge.reserve(virtual_log_n);
 
        // Process univariate consistancy check rounds
        // For ECCVM we ensure the consistencies by populating an vector of claimed evaluations that will be checked in
        // the PCS rounds
        // For other flavors, we perform the sumcheck univariate consistency check
 
        bool verified = true;
        // Heap-allocate ClaimedEvaluations (AllValues) to keep the sumcheck-verify stack frame small.
        // For recursive flavors with many columns (e.g. AVM), holding this inline on the stack can exceed the 8 MB
        // stack limit once nested inside the inner-Mega AVM recursive verifier chain
        auto purported_evaluations_storage = std::make_unique<ClaimedEvaluations>();
        ClaimedEvaluations& purported_evaluations = *purported_evaluations_storage;
        for (size_t round_idx = 0; round_idx < virtual_log_n; round_idx++) {
            round.process_round(transcript, multivariate_challenge, gate_separators, round_idx);
            verified = verified && !round.round_failed;
 
            if constexpr (IsTranslatorFlavor<Flavor>) {
                if (round_idx == Flavor::LOG_MINI_CIRCUIT_SIZE - 1) {
                    // Receive mini-circuit evaluations mid-sumcheck so that they get hashed into the transcript,
                    // ensuring the remaining LOG_N - LOG_MINI_CIRCUIT_SIZE round challenges depend on them.
                    Flavor::set_minicircuit_evaluations(
                        purported_evaluations,
                        transcript->template receive_from_prover<std::array<FF, Flavor::NUM_MINICIRCUIT_EVALUATIONS>>(
                            "Sumcheck:minicircuit_evaluations"));
                }
            }
        }
 
        // Populate claimed evaluations at the challenge
        if constexpr (IsTranslatorFlavor<Flavor>) {
            // Translator path: receive full-circuit evaluations, set them, and complete
            // (computable precomputed selectors + L_0 scaling of minicircuit wires already placed above)
            auto get_full_circuit_evaluations = std::make_unique<std::array<FF, Flavor::NUM_FULL_CIRCUIT_EVALUATIONS>>(
                transcript->template receive_from_prover<std::array<FF, Flavor::NUM_FULL_CIRCUIT_EVALUATIONS>>(
                    "Sumcheck:evaluations"));
            Flavor::complete_full_circuit_evaluations(
                purported_evaluations, *get_full_circuit_evaluations, std::span<const FF>(multivariate_challenge));
        } else {
            // Heap-allocate transcript_evaluations for the same reason as purported_evaluations above.
            auto transcript_evaluations = std::make_unique<std::array<FF, NUM_POLYNOMIALS>>(
                transcript->template receive_from_prover<std::array<FF, NUM_POLYNOMIALS>>("Sumcheck:evaluations"));
            for (auto [eval, transcript_eval] : zip_view(purported_evaluations.get_all(), *transcript_evaluations)) {
                eval = transcript_eval;
            }
        }
 
        // OriginTag false positive: The evaluations are PCS-bound - the prover committed to the
        // polynomials before challenges were known, and the PCS opening verifies consistency.
        if constexpr (IsRecursiveFlavor<Flavor>) {
            const auto challenge_tag = multivariate_challenge.back().get_origin_tag();
            for (auto& eval : purported_evaluations.get_all()) {
                eval.set_origin_tag(challenge_tag);
            }
        }
 
        // Evaluate the Honk relation at the sumcheck challenge; row-disabling factors are applied
        // internally for flavors that use them.
        FF full_honk_purported_value = round.compute_full_relation_purported_value(
            purported_evaluations, relation_parameters, gate_separators, alphas, multivariate_challenge);
 
        // Libra correction (ZK only).
        zk_correction_handler.apply_zk_corrections(full_honk_purported_value, multivariate_challenge);
 
        bool final_check = round.perform_final_verification(full_honk_purported_value);
        verified = final_check && verified;
 
        // For ZK Flavors: the evaluations of Libra univariates are included in the Sumcheck Output
        return SumcheckOutput<Flavor>{ .challenge = multivariate_challenge,
                                       .claimed_evaluations = std::move(purported_evaluations),
                                       .verified = verified,
                                       .claimed_libra_evaluation = zk_correction_handler.get_libra_evaluation(),
                                       .round_univariate_commitments = round.get_round_univariate_commitments(),
                                       .round_univariate_evaluations = round.get_round_univariate_evaluations() };
    };
};
 
template <typename FF, size_t N> std::array<FF, N> initialize_relation_separator(const FF& alpha)
{
    std::array<FF, N> alphas;
    alphas[0] = alpha;
    for (size_t i = 1; i < N; ++i) {
        alphas[i] = alphas[i - 1] * alpha;
    }
    return alphas;
}
} // namespace bb