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/flavor/multilinear_batching_flavor.hpp"
#include "barretenberg/honk/library/grand_product_delta.hpp"
#include "barretenberg/polynomials/eq_polynomial.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"
 
namespace bb {
 
template <typename Flavor, bool IsGrumpkin = IsGrumpkinFlavor<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))
    {}
 
    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 {}; }
};
 
template <typename Flavor> struct RoundUnivariateHandler<Flavor, true> {
    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;
    CommitmentKey ck;
    std::vector<FF> eval_domain;
    std::vector<std::array<FF, 3>> round_evaluations;
    std::vector<Polynomial<FF>> round_univariates;
 
    RoundUnivariateHandler(std::shared_ptr<Transcript> transcript)
        : transcript(std::move(transcript))
        , ck(BATCHED_RELATION_PARTIAL_LENGTH)
    {
        // Compute the vector {0, 1, \ldots, BATCHED_RELATION_PARTIAL_LENGTH-1} needed to transform
        // the round univariates from Lagrange to monomial basis
        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);
        transcript->send_to_verifier("Sumcheck:univariate_comm_" + idx, ck.commit(round_poly_monomial));
 
        // 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);
    }
 
    std::vector<std::array<FF, 3>> get_evaluations() { return round_evaluations; }
    std::vector<Polynomial<FF>> get_univariates() { return round_univariates; }
};
 
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*/,
                              const std::vector<FF>& /*padding_indicator_array*/)
    {}
 
    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 };
 
    // If running zero-knowledge sumcheck the target total sum is corrected by the claimed sum of libra masking
    // multivariate over the hypercube
    VerifierZKCorrectionHandler(std::shared_ptr<Transcript> transcript)
        : transcript(std::move(transcript))
        , libra_total_sum(this->transcript->template receive_from_prover<FF>("Libra:Sum"))
        , libra_challenge(this->transcript->template get_challenge<FF>("Libra:Challenge"))
    {}
 
    void initialize_target_sum(SumcheckRound& round) { round.target_total_sum = libra_total_sum * libra_challenge; }
 
    void apply_zk_corrections(FF& full_honk_purported_value,
                              std::vector<FF>& multivariate_challenge,
                              const std::vector<FF>& padding_indicator_array)
    {
        if constexpr (UseRowDisablingPolynomial<Flavor>) {
            // Compute the evaluations of the polynomial (1 - \sum L_i) where the sum is for i corresponding to the
            // rows where all sumcheck relations are disabled
            // i.e. compute the term $1 - \prod_{i=2}^{d-1} u_i$
            full_honk_purported_value *=
                RowDisablingPolynomial<FF>::evaluate_at_challenge(multivariate_challenge, padding_indicator_array);
        }
 
        // Get the claimed evaluation of the Libra multivariate evaluated at the sumcheck challenge
        libra_evaluation = transcript->template receive_from_prover<FF>("Libra:claimed_evaluation");
        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 = IsAnyOf<Flavor, MultilinearBatchingFlavor>;
    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;
 
    // For computing eq polymomials in Multilinear Batching Flavor
    std::vector<FF> accumulator_challenge = {};
    std::vector<FF> instance_challenge = {};
    FF libra_evaluation = FF{ 0 };
 
    RowDisablingPolynomial<FF> row_disabling_polynomial;
 
    // SumcheckProver constructor for MultilinearBatchingFlavor.
    SumcheckProver(size_t multivariate_n,
                   ProverPolynomials& prover_polynomials,
                   std::shared_ptr<Transcript> transcript,
                   const FF& relation_separator,
                   const size_t virtual_log_n,
                   const std::vector<FF>& accumulator_challenge,
                   const std::vector<FF>& instance_challenge)
        : 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>(relation_separator))
        , gate_challenges({})
        , virtual_log_n(virtual_log_n)
        , accumulator_challenge(accumulator_challenge)
        , instance_challenge(instance_challenge) {};
 
    // 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) {};
    SumcheckOutput<Flavor> prove()
    {
        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.
        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
        PartiallyEvaluatedMultivariates partially_evaluated_polynomials =
            partially_evaluate_first_round(full_polynomials, round_challenge);
 
        gate_separators.partially_evaluate(round_challenge);
        round.round_size = round.round_size >> 1;
        for (size_t round_idx = 1; round_idx < multivariate_d; round_idx++) {
            BB_BENCH_NAME("sumcheck loop");
 
            // Write the round univariate to the transcript
            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.round_size = round.round_size >> 1;
        }
        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
                std::vector<FF> index_1_challenge(virtual_log_n);
                for (size_t i = 0; i < k; i++) {
                    index_1_challenge[i] = multivariate_challenge[i];
                }
                index_1_challenge[k] = FF(1);
                if (partially_evaluated_polynomials.eq_accumulator.size() == 1) {
 
                    // We need to reallocate the polynomials
                    auto new_polynomial =
                        Polynomial<FF>(2, partially_evaluated_polynomials.eq_accumulator.virtual_size());
                    new_polynomial.at(0) = partially_evaluated_polynomials.eq_accumulator.at(0);
                    partially_evaluated_polynomials.eq_accumulator = new_polynomial;
                }
                if (partially_evaluated_polynomials.eq_instance.size() == 1) {
                    // We need to reallocate the polynomials
                    auto new_polynomial = Polynomial<FF>(2, partially_evaluated_polynomials.eq_instance.virtual_size());
                    new_polynomial.at(0) = partially_evaluated_polynomials.eq_instance.at(0);
                    partially_evaluated_polynomials.eq_instance = new_polynomial;
                }
                partially_evaluated_polynomials.eq_accumulator.at(1) =
                    VerifierEqPolynomial<FF>::eval(accumulator_challenge, index_1_challenge);
                partially_evaluated_polynomials.eq_instance.at(1) =
                    VerifierEqPolynomial<FF>::eval(instance_challenge, index_1_challenge);
                index_1_challenge[k] = FF(0);
            }
            // 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());
        // For ZK Flavors: the evaluations of Libra univariates are included in the Sumcheck Output
 
        return SumcheckOutput<Flavor>{ .challenge = multivariate_challenge,
                                       .claimed_evaluations = multivariate_evaluations };
        vinfo("finished sumcheck");
    };
 
    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
        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;
 
        // Subtract the contribution from the disabled rows
        if constexpr (UseRowDisablingPolynomial<Flavor>) {
            round_univariate -= round.compute_disabled_contribution(
                full_polynomials, relation_parameters, gate_separators, alphas, round_idx, 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.round_size = round.round_size >> 1;
        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;
            // Subtract the contribution from the disabled rows
            if constexpr (UseRowDisablingPolynomial<Flavor>) {
                round_univariate -= round.compute_disabled_contribution(partially_evaluated_polynomials,
                                                                        relation_parameters,
                                                                        gate_separators,
                                                                        alphas,
                                                                        round_idx,
                                                                        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);
            // 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.round_size = round.round_size >> 1;
        }
 
        handler.finalize_last_round(multivariate_d, round_univariate, multivariate_challenge[multivariate_d - 1]);
 
        vinfo("completed ", multivariate_d, " rounds of sumcheck");
 
        // Zero univariates are used to pad the proof to the fixed size virtual_log_n.
        auto zero_univariate = bb::Univariate<FF, Flavor::BATCHED_RELATION_PARTIAL_LENGTH>::zero();
        for (size_t idx = multivariate_d; idx < virtual_log_n; idx++) {
            transcript->send_to_verifier("Sumcheck:univariate_" + std::to_string(idx), zero_univariate);
 
            FF round_challenge = transcript->template get_challenge<FF>("Sumcheck:u_" + std::to_string(idx));
            multivariate_challenge.emplace_back(round_challenge);
        }
 
        // Claimed evaluations of Prover polynomials are extracted and added to the transcript. When Flavor has ZK, the
        // evaluations of all witnesses are masked.
        ClaimedEvaluations multivariate_evaluations = extract_claimed_evaluations(partially_evaluated_polynomials);
        transcript->send_to_verifier("Sumcheck:evaluations", multivariate_evaluations.get_all());
 
        // The evaluations of Libra uninvariates at \f$ g_0(u_0), \ldots, g_{d-1} (u_{d-1}) \f$ are added to the
        // transcript.
        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
        return SumcheckOutput<Flavor>{ .challenge = multivariate_challenge,
                                       .claimed_evaluations = multivariate_evaluations,
                                       .claimed_libra_evaluation = libra_evaluation,
                                       .round_univariates = handler.get_univariates(),
                                       .round_univariate_evaluations = handler.get_evaluations() };
        vinfo("finished sumcheck");
    };
 
    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) {
            const auto& poly = source_view[j];
            size_t limit = poly.end_index();
            for (size_t i = 0; i < limit; i += 2) {
                dest_view[j].at(i >> 1) = poly[i] + round_challenge * (poly[i + 1] - poly[i]);
            }
            dest_view[j].shrink_end_index((limit / 2) + (limit % 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;
    }
 
    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 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 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,
                                  const std::vector<FF>& padding_indicator_array)
    {
        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;
        for (size_t round_idx = 0; round_idx < virtual_log_n; round_idx++) {
            round.process_round(
                transcript, multivariate_challenge, gate_separators, padding_indicator_array[round_idx], round_idx);
            verified = verified && !round.round_failed;
        }
 
        // Populate claimed evaluations at the challenge
        ClaimedEvaluations purported_evaluations;
        auto transcript_evaluations =
            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;
        }
 
        // Evaluate the Honk relation at the point (u_0, ..., u_{d-1}) using claimed evaluations of prover polynomials.
        // In ZK Flavors, the evaluation is corrected by full_libra_purported_value
        FF full_honk_purported_value = round.compute_full_relation_purported_value(
            purported_evaluations, relation_parameters, gate_separators, alphas);
 
        // For ZK Flavors: compute the evaluation of the Row Disabling Polynomial at the sumcheck challenge and of the
        // libra univariate used to hide the contribution from the actual Honk relation
        zk_correction_handler.apply_zk_corrections(
            full_honk_purported_value, multivariate_challenge, padding_indicator_array);
 
        verified = round.perform_final_verification(full_honk_purported_value) && verified;
 
        // For ZK Flavors: the evaluations of Libra univariates are included in the Sumcheck Output
        return SumcheckOutput<Flavor>{ .challenge = multivariate_challenge,
                                       .claimed_evaluations = 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