sumcheck.hpp

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 }
// =====================
 
#pragma once
#include "barretenberg/honk/library/grand_product_delta.hpp"
#include "barretenberg/polynomials/polynomial_arithmetic.hpp"
#include "barretenberg/sumcheck/sumcheck_output.hpp"
#include "barretenberg/transcript/transcript.hpp"
#include "barretenberg/ultra_honk/decider_proving_key.hpp"
#include "sumcheck_round.hpp"
 
namespace bb {
 
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 = typename Flavor::SubrelationSeparators;
    using CommitmentKey = typename Flavor::CommitmentKey;
 
    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;
 
    std::vector<typename Flavor::Commitment> round_univariate_commitments = {};
    std::vector<std::array<FF, 3>> round_evaluations = {};
    std::vector<Polynomial<FF>> round_univariates = {};
    std::vector<FF> eval_domain = {};
    FF libra_evaluation = FF{ 0 };
 
    RowDisablingPolynomial<FF> row_disabling_polynomial;
 
    PartiallyEvaluatedMultivariates partially_evaluated_polynomials;
 
    // SumcheckProver constructor for the Flavors that generate NUM_SUBRELATIONS - 1 subrelation separator challenges.
    SumcheckProver(size_t multivariate_n,
                   ProverPolynomials& prover_polynomials,
                   std::shared_ptr<Transcript> transcript,
                   const SubrelationSeparators& relation_separator,
                   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(relation_separator)
        , gate_challenges(gate_challenges)
        , relation_parameters(relation_parameters)
        , virtual_log_n(virtual_log_n) {};
 
    // SumcheckProver constructor for the Flavors that generate a single challeng `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()
    {
        // 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);
        // Initialize the partially evaluated polynomials which will be used in the following rounds.
        // This will use the information in the structured full polynomials to save memory if possible.
        partially_evaluated_polynomials = PartiallyEvaluatedMultivariates(full_polynomials, multivariate_n);
 
        vinfo("starting sumcheck rounds...");
        {
            PROFILE_THIS_NAME("rest of sumcheck round 1");
 
            // 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);
            // Prepare sumcheck book-keeping table for the next round
            partially_evaluate(full_polynomials, round_challenge);
            gate_separators.partially_evaluate(round_challenge);
            round.round_size = round.round_size >> 1; // TODO(#224)(Cody): Maybe partially_evaluate should do this and
            // release memory?        // All but final round
            // We operate on partially_evaluated_polynomials in place.
        }
        for (size_t round_idx = 1; round_idx < multivariate_d; round_idx++) {
            PROFILE_THIS_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(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) {
            // 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) {
                    poly.at(0) *= (FF(1) - round_challenge);
                }
            }
            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
    {
        CommitmentKey ck;
 
        if constexpr (IsGrumpkinFlavor<Flavor>) {
            ck = CommitmentKey(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));
            }
        }
 
        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.
        auto hiding_univariate = round.compute_hiding_univariate(round_idx,
                                                                 full_polynomials,
                                                                 relation_parameters,
                                                                 gate_separators,
                                                                 alphas,
                                                                 zk_sumcheck_data,
                                                                 row_disabling_polynomial);
        auto round_univariate =
            round.compute_univariate(full_polynomials, relation_parameters, gate_separators, alphas);
        round_univariate += hiding_univariate;
 
        // Initialize the partially evaluated polynomials which will be used in the following rounds.
        // This will use the information in the structured full polynomials to save memory if possible.
        partially_evaluated_polynomials = PartiallyEvaluatedMultivariates(full_polynomials, multivariate_n);
 
        {
            PROFILE_THIS_NAME("rest of sumcheck round 1");
 
            if constexpr (!IsGrumpkinFlavor<Flavor>) {
                // Place the evaluations of the round univariate into transcript.
                transcript->send_to_verifier("Sumcheck:univariate_0", round_univariate);
            } else {
 
                // Compute monomial coefficients of the round univariate, commit to it, populate an auxiliary structure
                // needed in the PCS round
                commit_to_round_univariate(round_idx, round_univariate, ck);
            }
 
            const FF round_challenge = transcript->template get_challenge<FF>("Sumcheck:u_0");
 
            multivariate_challenge.emplace_back(round_challenge);
            // Prepare sumcheck book-keeping table for the next round
            partially_evaluate(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; // TODO(#224)(Cody): Maybe partially_evaluate should do this and
                                                      // release memory?        // All but final round
                                                      // We operate on partially_evaluated_polynomials in place.
        }
        for (size_t round_idx = 1; round_idx < multivariate_d; round_idx++) {
            PROFILE_THIS_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
            hiding_univariate = round.compute_hiding_univariate(round_idx,
                                                                partially_evaluated_polynomials,
                                                                relation_parameters,
                                                                gate_separators,
                                                                alphas,
                                                                zk_sumcheck_data,
                                                                row_disabling_polynomial);
            round_univariate =
                round.compute_univariate(partially_evaluated_polynomials, relation_parameters, gate_separators, alphas);
            round_univariate += hiding_univariate;
 
            if constexpr (!IsGrumpkinFlavor<Flavor>) {
                // Place evaluations of Sumcheck Round Univariate in the transcript
                transcript->send_to_verifier("Sumcheck:univariate_" + std::to_string(round_idx), round_univariate);
            } else {
 
                // Compute monomial coefficients of the round univariate, commit to it, populate an auxiliary structure
                // needed in the PCS round
                commit_to_round_univariate(round_idx, round_univariate, ck);
            }
            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(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;
        }
 
        if constexpr (IsGrumpkinFlavor<Flavor>) {
            round_evaluations[multivariate_d - 1][2] =
                round_univariate.evaluate(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
        if constexpr (!IsGrumpkinFlavor<Flavor>) {
            return SumcheckOutput<Flavor>{ .challenge = multivariate_challenge,
                                           .claimed_evaluations = multivariate_evaluations,
                                           .claimed_libra_evaluation = libra_evaluation };
        } else {
            return SumcheckOutput<Flavor>{ .challenge = multivariate_challenge,
                                           .claimed_evaluations = multivariate_evaluations,
                                           .claimed_libra_evaluation = libra_evaluation,
                                           .round_univariates = round_univariates,
                                           .round_univariate_evaluations = round_evaluations };
        }
        vinfo("finished sumcheck");
    };
 
    void partially_evaluate(auto& polynomials, const FF& round_challenge)
    {
        auto pep_view = partially_evaluated_polynomials.get_all();
        auto poly_view = polynomials.get_all();
        // after the first round, operate in place on partially_evaluated_polynomials
        parallel_for(poly_view.size(), [&](size_t j) {
            const auto& poly = poly_view[j];
            // The polynomial is shorter than the round size.
            size_t limit = poly.end_index();
            for (size_t i = 0; i < limit; i += 2) {
                pep_view[j].at(i >> 1) = poly[i] + round_challenge * (poly[i + 1] - poly[i]);
            }
 
            // We resize pep_view[j] to have the exact size required for the next round which is
            // CEIL(limit/2). This has the effect to reduce the limit in next round and also to
            // virtually zeroize any leftover values beyond the limit (in-place computation).
            // This is important to zeroize leftover values to not mess up with compute_univariate().
            // Note that the virtual size of pep_view[j] remains unchanged.
            pep_view[j].shrink_end_index(limit / 2 + limit % 2);
        });
    };
    template <typename PolynomialT, std::size_t N>
    void partially_evaluate(std::array<PolynomialT, N>& polynomials, const FF& round_challenge)
    {
        auto pep_view = partially_evaluated_polynomials.get_all();
        // after the first round, operate in place on partially_evaluated_polynomials
        parallel_for(polynomials.size(), [&](size_t j) {
            const auto& poly = polynomials[j];
            // The polynomial is shorter than the round size.
            size_t limit = poly.end_index();
            for (size_t i = 0; i < limit; i += 2) {
                pep_view[j].at(i >> 1) = poly[i] + round_challenge * (poly[i + 1] - poly[i]);
            }
 
            // We resize pep_view[j] to have the exact size required for the next round which is
            // CEIL(limit/2). This has the effect to reduce the limit in next round and also to
            // virtually zeroize any leftover values beyond the limit (in-place computation).
            // This is important to zeroize leftover values to not mess up with compute_univariate().
            // Note that the virtual size of pep_view[j] remains unchanged.
            pep_view[j].shrink_end_index(limit / 2 + limit % 2);
        });
    };
 
    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;
    };
 
    void commit_to_round_univariate(const size_t round_idx,
                                    bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>& round_univariate,
                                    const CommitmentKey& ck)
 
    {
        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);
        };
    }
};
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 = typename Flavor::SubrelationSeparators;
    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;
    FF libra_evaluation{ 0 };
    FF libra_challenge;
    FF libra_total_sum;
 
    FF correcting_factor;
 
    std::vector<Commitment> round_univariate_commitments = {};
    std::vector<std::array<FF, 3>> round_univariate_evaluations = {};
 
    explicit SumcheckVerifier(std::shared_ptr<Transcript> transcript,
                              SubrelationSeparators& relation_separator,
                              size_t virtual_log_n,
                              FF target_sum = 0)
        : transcript(std::move(transcript))
        , round(target_sum)
        , virtual_log_n(virtual_log_n)
        , alphas(relation_separator) {};
 
    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,
                                  std::vector<FF>& gate_challenges,
                                  const std::vector<FF>& padding_indicator_array)
        requires(!IsGrumpkinFlavor<Flavor>)
    {
        bool verified(true);
 
        bb::GateSeparatorPolynomial<FF> gate_separators(gate_challenges);
        // All but final round.
        // target_total_sum is initialized to zero then mutated in place.
 
        bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH> round_univariate;
 
        if constexpr (Flavor::HasZK) {
            // If running zero-knowledge sumcheck the target total sum is corrected by the claimed sum of libra masking
            // multivariate over the hypercube
            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;
        }
 
        std::vector<FF> multivariate_challenge;
        multivariate_challenge.reserve(virtual_log_n);
        for (size_t round_idx = 0; round_idx < virtual_log_n; round_idx++) {
            // Obtain the round univariate from the transcript
            std::string round_univariate_label = "Sumcheck:univariate_" + std::to_string(round_idx);
            round_univariate =
                transcript->template receive_from_prover<bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>>(
                    round_univariate_label);
            FF round_challenge = transcript->template get_challenge<FF>("Sumcheck:u_" + std::to_string(round_idx));
            multivariate_challenge.emplace_back(round_challenge);
 
            const bool checked = round.check_sum(round_univariate, padding_indicator_array[round_idx]);
            round.compute_next_target_sum(round_univariate, round_challenge, padding_indicator_array[round_idx]);
            gate_separators.partially_evaluate(round_challenge, padding_indicator_array[round_idx]);
 
            verified = verified && checked;
        }
        // Extract claimed evaluations of Libra univariates and compute their sum multiplied by the Libra challenge
        // Final round
        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
        if constexpr (Flavor::HasZK) {
            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
                full_honk_purported_value *=
                    RowDisablingPolynomial<FF>::evaluate_at_challenge(multivariate_challenge, padding_indicator_array);
            }
 
            libra_evaluation = transcript->template receive_from_prover<FF>("Libra:claimed_evaluation");
            full_honk_purported_value += libra_evaluation * libra_challenge;
        }
 
        bool final_check(false);
        if constexpr (IsRecursiveFlavor<Flavor>) {
            // These booleans are only needed for debugging
            final_check = (full_honk_purported_value.get_value() == round.target_total_sum.get_value());
            verified = verified && final_check;
 
            full_honk_purported_value.assert_equal(round.target_total_sum);
        } else {
            final_check = (full_honk_purported_value == round.target_total_sum);
            verified = verified && final_check;
        }
 
        return SumcheckOutput<Flavor>{ .challenge = multivariate_challenge,
                                       .claimed_evaluations = purported_evaluations,
                                       .verified = verified,
                                       .claimed_libra_evaluation = libra_evaluation };
    };
 
    SumcheckOutput<Flavor> verify(const bb::RelationParameters<FF>& relation_parameters,
                                  const std::vector<FF>& gate_challenges)
        requires IsGrumpkinFlavor<Flavor>
    {
        bool verified(false);
 
        bb::GateSeparatorPolynomial<FF> gate_separators(gate_challenges);
 
        // get the claimed sum of libra masking multivariate over the hypercube
        libra_total_sum = transcript->template receive_from_prover<FF>("Libra:Sum");
        // get the challenge for the ZK Sumcheck claim
        const FF libra_challenge = transcript->template get_challenge<FF>("Libra:Challenge");
 
        std::vector<FF> multivariate_challenge;
        multivariate_challenge.reserve(virtual_log_n);
        // if Flavor has ZK, the target total sum is corrected by Libra total sum multiplied by the Libra
        // challenge
        round.target_total_sum = libra_total_sum * libra_challenge;
 
        for (size_t round_idx = 0; round_idx < virtual_log_n; round_idx++) {
            // Obtain the round univariate from the transcript
            const std::string round_univariate_comm_label = "Sumcheck:univariate_comm_" + std::to_string(round_idx);
            const std::string univariate_eval_label_0 = "Sumcheck:univariate_" + std::to_string(round_idx) + "_eval_0";
            const std::string univariate_eval_label_1 = "Sumcheck:univariate_" + std::to_string(round_idx) + "_eval_1";
 
            // Receive the commitment to the round univariate
            round_univariate_commitments.push_back(
                transcript->template receive_from_prover<Commitment>(round_univariate_comm_label));
            // Receive evals at 0 and 1
            round_univariate_evaluations.push_back(
                { transcript->template receive_from_prover<FF>(univariate_eval_label_0),
                  transcript->template receive_from_prover<FF>(univariate_eval_label_1) });
 
            const FF round_challenge =
                transcript->template get_challenge<FF>("Sumcheck:u_" + std::to_string(round_idx));
            multivariate_challenge.emplace_back(round_challenge);
 
            gate_separators.partially_evaluate(round_challenge);
        }
 
        FF first_sumcheck_round_evaluations_sum =
            round_univariate_evaluations[0][0] + round_univariate_evaluations[0][1];
 
        // 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;
        }
        // For ZK Flavors: the evaluation of the Row Disabling Polynomial at the sumcheck challenge
        // 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);
 
        // 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
        full_honk_purported_value *=
            RowDisablingPolynomial<FF>::evaluate_at_challenge(multivariate_challenge, virtual_log_n);
 
        // Extract claimed evaluations of Libra univariates and compute their sum multiplied by the Libra challenge
        const FF libra_evaluation = transcript->template receive_from_prover<FF>("Libra:claimed_evaluation");
        // Verifier computes full ZK Honk value, taking into account the contribution from the disabled row and the
        // Libra polynomials
        full_honk_purported_value += libra_evaluation * libra_challenge;
 
        // Populate claimed evaluations of Sumcheck Round Unviariates at the round challenges. These will be checked as
        // a part of Shplemini.
        for (size_t round_idx = 1; round_idx < virtual_log_n; round_idx++) {
            round_univariate_evaluations[round_idx - 1][2] =
                round_univariate_evaluations[round_idx][0] + round_univariate_evaluations[round_idx][1];
        };
 
        if constexpr (IsRecursiveFlavor<Flavor>) {
 
            first_sumcheck_round_evaluations_sum.self_reduce();
            round.target_total_sum.self_reduce();
 
            // This bool is only needed for debugging
            verified = (first_sumcheck_round_evaluations_sum.get_value() == round.target_total_sum.get_value());
            // Ensure that the sum of the evaluations of the first Sumcheck Round Univariate is equal to the claimed
            // target total sum
            first_sumcheck_round_evaluations_sum.assert_equal(round.target_total_sum);
 
            // TODO(https://github.com/AztecProtocol/barretenberg/issues/1197)
            full_honk_purported_value.self_reduce();
 
        } else {
            // Ensure that the sum of the evaluations of the first Sumcheck Round Univariate is equal to the claimed
            // target total sum
            verified = (first_sumcheck_round_evaluations_sum == round.target_total_sum);
        }
 
        round_univariate_evaluations[virtual_log_n - 1][2] = full_honk_purported_value;
 
        // 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 = libra_evaluation,
                                       .round_univariate_commitments = round_univariate_commitments,
                                       .round_univariate_evaluations = 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