sumcheck_round.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/thread.hpp"
#include "barretenberg/flavor/flavor.hpp"
#include "barretenberg/polynomials/gate_separator.hpp"
#include "barretenberg/polynomials/row_disabling_polynomial.hpp"
#include "barretenberg/relations/relation_parameters.hpp"
#include "barretenberg/relations/relation_types.hpp"
#include "barretenberg/relations/utils.hpp"
#include "barretenberg/stdlib/primitives/bool/bool.hpp"
#include "zk_sumcheck_data.hpp"
 
namespace bb {
 
// To know if a flavor is AVM, without including the flavor.
template <typename Flavor>
concept isAvmFlavor = std::convertible_to<decltype(Flavor::IS_AVM), bool>;
 
template <typename Flavor> class SumcheckProverRound {
    using Utils = bb::RelationUtils<Flavor>;
 
  public:
    using FF = typename Flavor::FF;
    using Relations = typename Flavor::Relations;
    using SumcheckTupleOfTuplesOfUnivariates = decltype(create_sumcheck_tuple_of_tuples_of_univariates<Relations>());
    using SubrelationSeparators = std::array<FF, Flavor::NUM_SUBRELATIONS - 1>;
    using ExtendedEdges = std::conditional_t<Flavor::USE_SHORT_MONOMIALS,
                                             typename Flavor::template ProverUnivariates<2>,
                                             typename Flavor::ExtendedEdges>;
    using ZKData = ZKSumcheckData<Flavor>;
    size_t round_size;
    static constexpr size_t NUM_RELATIONS = Flavor::NUM_RELATIONS;
    static constexpr size_t MAX_PARTIAL_RELATION_LENGTH = Flavor::MAX_PARTIAL_RELATION_LENGTH;
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH;
    using SumcheckRoundUnivariate = bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>;
    // Note: since this is not initialized with {}, the univariates contain garbage.
    SumcheckTupleOfTuplesOfUnivariates univariate_accumulators;
 
    // The length of the polynomials used to mask the Sumcheck Round Univariates.
    static constexpr size_t LIBRA_UNIVARIATES_LENGTH = Flavor::Curve::LIBRA_UNIVARIATES_LENGTH;
 
    // Prover constructor
    SumcheckProverRound(size_t initial_round_size)
        : round_size(initial_round_size)
    {
        BB_BENCH_NAME("SumcheckProverRound constructor");
 
        // Initialize univariate accumulators to 0
        Utils::zero_univariates(univariate_accumulators);
    }
 
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates>
    size_t compute_effective_round_size(const ProverPolynomialsOrPartiallyEvaluatedMultivariates& multivariates) const
    {
        if constexpr (Flavor::HasZK) {
            // When ZK is enabled, we must iterate over the full round_size
            return round_size;
        } else {
            // When ZK is disabled, find the maximum end_index() across witness polynomials only
            // (precomputed polynomials like selectors are always full size)
            // We need to round up to the next even number since we process edges in pairs
            size_t max_end_index = 0;
 
            // Check if the flavor has a get_witness() method to iterate over all witness polynomials
            if constexpr (requires { multivariates.get_witness(); }) {
                for (auto& witness_poly : multivariates.get_witness()) {
                    max_end_index = std::max(max_end_index, witness_poly.end_index());
                }
            } else {
                // Fallback: use full round_size if no get_witness() method available
                return round_size;
            }
 
            // Round up to next even number and ensure we don't exceed round_size
            return std::min(round_size, max_end_index + (max_end_index % 2));
        }
    }
 
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates>
    void extend_edges(ExtendedEdges& extended_edges,
                      const ProverPolynomialsOrPartiallyEvaluatedMultivariates& multivariates,
                      const size_t edge_idx)
    {
        for (auto [extended_edge, multivariate] : zip_view(extended_edges.get_all(), multivariates.get_all())) {
            if constexpr (Flavor::USE_SHORT_MONOMIALS) {
                extended_edge = bb::Univariate<FF, 2>({ multivariate[edge_idx], multivariate[edge_idx + 1] });
            } else {
                if (multivariate.end_index() < edge_idx) {
                    static const auto zero_univariate = bb::Univariate<FF, MAX_PARTIAL_RELATION_LENGTH>::zero();
                    extended_edge = zero_univariate;
                } else {
                    extended_edge = bb::Univariate<FF, 2>({ multivariate[edge_idx], multivariate[edge_idx + 1] })
                                        .template extend_to<MAX_PARTIAL_RELATION_LENGTH>();
                }
            }
        }
    }
 
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates>
    SumcheckRoundUnivariate compute_univariate(ProverPolynomialsOrPartiallyEvaluatedMultivariates& polynomials,
                                               const bb::RelationParameters<FF>& relation_parameters,
                                               const bb::GateSeparatorPolynomial<FF>& gate_separators,
                                               const SubrelationSeparators& alphas)
    {
        if constexpr (isAvmFlavor<Flavor>) {
            return compute_univariate_avm(polynomials, relation_parameters, gate_separators, alphas);
        } else {
            return compute_univariate_with_row_skipping(polynomials, relation_parameters, gate_separators, alphas);
        }
    }
 
    // TODO(https://github.com/AztecProtocol/barretenberg/issues/1484): should we more intelligently incorporate the two
    // `compute_univariate` types of functions?
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates>
    SumcheckRoundUnivariate compute_univariate_avm(ProverPolynomialsOrPartiallyEvaluatedMultivariates& polynomials,
                                                   const bb::RelationParameters<FF>& relation_parameters,
                                                   const bb::GateSeparatorPolynomial<FF>& gate_separators,
                                                   const SubrelationSeparators& alphas)
    {
        BB_BENCH_NAME("compute_univariate_avm");
 
        // Compute the effective round size. If the trace is short, we don't need to iterate over the full round_size.
        const size_t effective_round_size = compute_effective_round_size(polynomials);
        // Note: effective_round_size is expected to be even.
        BB_ASSERT(effective_round_size % 2 == 0, "effective_round_size must be even");
 
        // Determine number of threads for multithreading.
        // Note: Multithreading is "on" for every round but we reduce the number of threads from the max available based
        // on a specified minimum number of iterations per thread. This eventually leads to the use of a single thread.
        size_t min_iterations_per_thread = 1 << 6; // min number of iterations for which we'll spin up a unique thread
        size_t num_threads = bb::calculate_num_threads(effective_round_size, min_iterations_per_thread);
 
        // In the AVM, the trace is more dense at the top and therefore it is worth to split the work per thread
        // in a more distributed way over the edges. To achieve this, we split the trace into chunks and each chunk is
        // evenly divided among the threads.
 
        // Pattern over edges is now (note that horizontal direction here is edge direction, i.e., vertical direction in
        // the trace):
        //
        //          chunk_0             |           chunk_1             |         chunk_2 ....
        //  thread_0 | thread_1 ...     | thread_0 | thread_1 ...       | thread_0 | thread_1 ...
        //
        // Any thread now processes edges which are distributed at different locations in the trace contrary
        // to the "standard" method where thread_0 processes all the low indices and the last thread processes
        // all the high indices.
 
        constexpr size_t rows_per_thread = 2; // Measured in rows, not edges.
        static_assert((rows_per_thread >= 2) && (rows_per_thread % 2 == 0),
                      "rows_per_thread must be at least 2 and even, because edges are processed in pairs");
        size_t chunk_size = rows_per_thread * num_threads;
        size_t num_chunks = (effective_round_size / chunk_size) +            // This rounds down.
                            (effective_round_size % chunk_size > 0 ? 1 : 0); // If there's a remainder, add 1.
 
        // Construct univariate accumulator containers; one per thread
        // Note: std::vector will trigger {}-initialization of the contents. Therefore no need to zero the univariates.
        std::vector<SumcheckTupleOfTuplesOfUnivariates> thread_univariate_accumulators(num_threads);
 
        // Accumulate the contribution from each sub-relation across each edge of the hyper-cube
        parallel_for(num_threads, [&](size_t thread_idx) {
            ExtendedEdges lazy_extended_edges(polynomials);
 
            for (size_t chunk_idx = 0; chunk_idx < num_chunks; chunk_idx++) {
                size_t start = (chunk_idx * chunk_size) + (thread_idx * rows_per_thread);
                size_t end = std::min(start + rows_per_thread, effective_round_size);
                for (size_t edge_idx = start; edge_idx < end; edge_idx += 2) {
                    lazy_extended_edges.set_current_edge(edge_idx);
                    // Compute the \f$ \ell \f$-th edge's univariate contribution,
                    // scale it by the corresponding \f$ pow_{\beta} \f$ contribution and add it to the accumulators for
                    // \f$ \tilde{S}^i(X_i) \f$. If \f$ \ell \f$'s binary representation is given by \f$
                    // (\ell_{i+1},\ldots, \ell_{d-1})\f$, the \f$ pow_{\beta}\f$-contribution is
                    // \f$\beta_{i+1}^{\ell_{i+1}} \cdot \ldots \cdot \beta_{d-1}^{\ell_{d-1}}\f$.
                    accumulate_relation_univariates(thread_univariate_accumulators[thread_idx],
                                                    lazy_extended_edges,
                                                    relation_parameters,
                                                    gate_separators[edge_idx]);
                }
            }
        });
 
        // Accumulate the per-thread univariate accumulators into a single set of accumulators
        for (auto& accumulators : thread_univariate_accumulators) {
            Utils::add_nested_tuples(univariate_accumulators, accumulators);
        }
 
        // Batch the univariate contributions from each sub-relation to obtain the round univariate
        return batch_over_relations<SumcheckRoundUnivariate>(univariate_accumulators, alphas, gate_separators);
    }
 
    struct BlockOfContiguousRows {
        size_t starting_edge_idx;
        size_t size;
    };
 
    struct RowIterator {
        const std::vector<BlockOfContiguousRows>* blocks;
        size_t current_block_index = 0;
        size_t current_block_count = 0;
        RowIterator(const std::vector<BlockOfContiguousRows>& _blocks, size_t starting_index = 0)
            : blocks(&_blocks)
        {
            size_t count = 0;
            for (size_t i = 0; i < blocks->size(); ++i) {
                const BlockOfContiguousRows block = blocks->at(i);
                if (count + (block.size / 2) > starting_index) {
                    current_block_index = i;
                    current_block_count = (starting_index - count) * 2;
                    break;
                }
                count += (block.size / 2);
            }
        }
 
        size_t get_next_edge()
        {
            const BlockOfContiguousRows& block = blocks->at(current_block_index);
            size_t edge = block.starting_edge_idx + current_block_count;
            if (current_block_count + 2 >= block.size) {
                current_block_index += 1;
                current_block_count = 0;
            } else {
                current_block_count += 2;
            }
            return edge;
        }
    };
 
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates>
    std::vector<BlockOfContiguousRows> compute_contiguous_round_size(
        ProverPolynomialsOrPartiallyEvaluatedMultivariates& polynomials)
    {
        // When !HasZK, compute the effective round size to avoid iterating over zero regions
        const size_t effective_round_size = compute_effective_round_size(polynomials);
 
        std::vector<BlockOfContiguousRows> result;
        constexpr bool can_skip_rows = (isRowSkippable<Flavor, decltype(polynomials), size_t>);
 
        if constexpr (can_skip_rows) {
            // Iterate over edge-pairs (stride-2) so each thread gets an even-aligned range
            const size_t num_edge_pairs = effective_round_size / 2;
            // Cost per iteration: skip_entire_row reads across polynomial columns.
            // Overestimates by using total entity count (skip_entire_row only checks a subset).
            constexpr size_t heuristic_cost = bb::thread_heuristics::FF_COPY_COST * 2 * Flavor::NUM_ALL_ENTITIES;
            std::vector<std::vector<BlockOfContiguousRows>> all_thread_blocks(bb::get_num_cpus());
            bb::parallel_for_heuristic(
                num_edge_pairs,
                [&](ThreadChunk chunk) {
                    auto range = chunk.range(num_edge_pairs);
                    if (range.empty()) {
                        return;
                    }
                    // Scan edge pairs to find contiguous runs of non-skippable rows.
                    // We track the start and size of the current run, emitting a block
                    // whenever we hit a skippable row or reach the end of the range.
                    size_t current_block_start = 0;
                    size_t current_block_size = 0;
                    std::vector<BlockOfContiguousRows> thread_blocks;
                    for (size_t pair_idx : range) {
                        size_t edge_idx = pair_idx * 2;
                        if (!Flavor::skip_entire_row(polynomials, edge_idx)) {
                            // Non-skippable row: begin a new block or extend the current one
                            if (current_block_size == 0) {
                                current_block_start = edge_idx;
                            }
                            current_block_size += 2; // each pair covers 2 edges
                        } else {
                            // Skippable row: flush the current block if one is open
                            if (current_block_size > 0) {
                                thread_blocks.push_back(BlockOfContiguousRows{ .starting_edge_idx = current_block_start,
                                                                               .size = current_block_size });
                                current_block_size = 0;
                            }
                        }
                    }
                    // Flush any remaining block at the end of the range
                    if (current_block_size > 0) {
                        thread_blocks.push_back(BlockOfContiguousRows{ .starting_edge_idx = current_block_start,
                                                                       .size = current_block_size });
                    }
                    all_thread_blocks[chunk.thread_index] = std::move(thread_blocks);
                },
                heuristic_cost);
 
            for (const auto& thread_blocks : all_thread_blocks) {
                for (const auto block : thread_blocks) {
                    result.push_back(block);
                }
            }
        } else {
            result.push_back(BlockOfContiguousRows{ .starting_edge_idx = 0, .size = effective_round_size });
        }
        return result;
    }
 
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates>
    SumcheckRoundUnivariate compute_univariate_with_row_skipping(
        ProverPolynomialsOrPartiallyEvaluatedMultivariates& polynomials,
        const bb::RelationParameters<FF>& relation_parameters,
        const bb::GateSeparatorPolynomial<FF>& gate_separators,
        const SubrelationSeparators alphas)
    {
        BB_BENCH_NAME("compute_univariate_with_row_skipping");
 
        std::vector<BlockOfContiguousRows> round_manifest = compute_contiguous_round_size(polynomials);
 
        // Construct univariate accumulator containers; one per thread
        // Note: std::vector will trigger {}-initialization of the contents. Therefore no need to zero the univariates.
        std::vector<SumcheckTupleOfTuplesOfUnivariates> thread_univariate_accumulators(get_num_cpus());
 
        parallel_for([&](ThreadChunk chunk) {
            // Construct extended univariates containers; one per thread
            ExtendedEdges extended_edges;
 
            // Process each block, dividing work within each block
            for (const BlockOfContiguousRows& block : round_manifest) {
                size_t block_iterations = block.size / 2;
 
                // Get the range of iterations this thread should process for this block
                auto iteration_range = chunk.range(block_iterations);
 
                for (size_t i : iteration_range) {
                    size_t edge_idx = block.starting_edge_idx + (i * 2);
                    extend_edges(extended_edges, polynomials, edge_idx);
                    // Compute the \f$ \ell \f$-th edge's univariate contribution,
                    // scale it by the corresponding \f$ pow_{\beta} \f$ contribution and add it to the accumulators for
                    // \f$
                    // \tilde{S}^i(X_i) \f$. If \f$ \ell \f$'s binary representation is given by \f$ (\ell_{i+1},\ldots,
                    // \ell_{d-1})\f$, the \f$ pow_{\beta}\f$-contribution is \f$\beta_{i+1}^{\ell_{i+1}} \cdot \ldots
                    // \cdot
                    // \beta_{d-1}^{\ell_{d-1}}\f$.
 
                    FF scaling_factor;
                    // All subrelation in MultilinearBatchingFlavor are linearly dependent, i.e. they are not scaled by
                    // `pow`-polynomial, hence we don't need to initialize `scaling_factor`.
                    if constexpr (!isMultilinearBatchingFlavor<Flavor>) {
                        scaling_factor = gate_separators[edge_idx];
                    }
                    accumulate_relation_univariates(thread_univariate_accumulators[chunk.thread_index],
                                                    extended_edges,
                                                    relation_parameters,
                                                    scaling_factor);
                }
            }
        });
 
        // Accumulate the per-thread univariate accumulators into a single set of accumulators
        for (auto& accumulators : thread_univariate_accumulators) {
            Utils::add_nested_tuples(univariate_accumulators, accumulators);
        }
        // Batch the univariate contributions from each sub-relation to obtain the round univariate
        // these are unmasked; we will mask in sumcheck.
        const auto round_univariate =
            batch_over_relations<SumcheckRoundUnivariate>(univariate_accumulators, alphas, gate_separators);
        // define eval at 0 from target sum/or previous round univariate
 
        return round_univariate;
    };
 
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates>
    SumcheckRoundUnivariate compute_disabled_contribution(
        ProverPolynomialsOrPartiallyEvaluatedMultivariates& polynomials,
        const bb::RelationParameters<FF>& relation_parameters,
        const bb::GateSeparatorPolynomial<FF>& gate_separators,
        const SubrelationSeparators& alphas,
        const size_t round_idx,
        const RowDisablingPolynomial<FF> row_disabling_polynomial)
        requires UseRowDisablingPolynomial<Flavor>
    {
        // Note: {} is required to initialize the tuple contents. Otherwise the univariates contain garbage.
        SumcheckTupleOfTuplesOfUnivariates univariate_accumulator{};
        ExtendedEdges extended_edges;
        SumcheckRoundUnivariate result;
 
        // In Round 0, we have to compute the contribution from 2 edges: (1, 1,..., 1) and (0, 1, ..., 1) (as points on
        // (d-1) - dimensional Boolean hypercube).
        size_t start_edge_idx = (round_idx == 0) ? round_size - 4 : round_size - 2;
 
        for (size_t edge_idx = start_edge_idx; edge_idx < round_size; edge_idx += 2) {
            extend_edges(extended_edges, polynomials, edge_idx);
            accumulate_relation_univariates(
                univariate_accumulator, extended_edges, relation_parameters, gate_separators[edge_idx]);
        }
        result = batch_over_relations<SumcheckRoundUnivariate>(univariate_accumulator, alphas, gate_separators);
        bb::Univariate<FF, 2> row_disabling_factor =
            bb::Univariate<FF, 2>({ row_disabling_polynomial.eval_at_0, row_disabling_polynomial.eval_at_1 });
        SumcheckRoundUnivariate row_disabling_factor_extended =
            row_disabling_factor.template extend_to<SumcheckRoundUnivariate::LENGTH>();
        result *= row_disabling_factor_extended;
 
        return result;
    }
 
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates>
    SumcheckRoundUnivariate compute_virtual_contribution(
        ProverPolynomialsOrPartiallyEvaluatedMultivariates& polynomials,
        const bb::RelationParameters<FF>& relation_parameters,
        const GateSeparatorPolynomial<FF>& gate_separator,
        const SubrelationSeparators& alphas)
    {
        // Note: {} is required to initialize the tuple contents. Otherwise the univariates contain garbage.
        SumcheckTupleOfTuplesOfUnivariates univariate_accumulator{};
 
        // For a given prover polynomial P_i(X_0, ..., X_{d-1}) extended by zero, i.e. multiplied by
        //      \tau(X_d, ..., X_{virtual_log_n - 1}) =  \prod (1 - X_k)
        // for k = d, ..., virtual_log_n - 1, the computation of the virtual sumcheck round univariate reduces to the
        // edge (0, ...,0).
        const size_t virtual_contribution_edge_idx = 0;
 
        // Perform the usual sumcheck accumulation, but for a single edge.
        // Note: we use a combination of `auto`, constexpr and a lambda to construct different types.
        auto extended_edges = [&]() {
            if constexpr (isAvmFlavor<Flavor>) {
                auto lazy_extended_edges = ExtendedEdges(polynomials);
                lazy_extended_edges.set_current_edge(virtual_contribution_edge_idx);
                return lazy_extended_edges;
            } else {
                ExtendedEdges extended_edges;
                extend_edges(extended_edges, polynomials, virtual_contribution_edge_idx);
                return extended_edges;
            }
        }();
 
        // The tail of G(X) = \prod_{k} (1 + X_k(\beta_k - 1) ) evaluated at the edge (0, ..., 0).
        const FF gate_separator_tail{ 1 };
        accumulate_relation_univariates(
            univariate_accumulator, extended_edges, relation_parameters, gate_separator_tail);
 
        return batch_over_relations<SumcheckRoundUnivariate>(univariate_accumulator, alphas, gate_separator);
    };
    template <typename ExtendedUnivariate, typename ContainerOverSubrelations>
    static ExtendedUnivariate batch_over_relations(ContainerOverSubrelations& univariate_accumulators,
                                                   const SubrelationSeparators& challenge,
                                                   const bb::GateSeparatorPolynomial<FF>& gate_separators)
    {
        Utils::scale_univariates(univariate_accumulators, challenge);
 
        auto result = ExtendedUnivariate(0);
        extend_and_batch_univariates(univariate_accumulators, result, gate_separators);
 
        // Reset all univariate accumulators to 0 before beginning accumulation in the next round
        Utils::zero_univariates(univariate_accumulators);
        return result;
    }
 
    template <typename ExtendedUnivariate, typename TupleOfTuplesOfUnivariates>
    static void extend_and_batch_univariates(const TupleOfTuplesOfUnivariates& tuple,
                                             ExtendedUnivariate& result,
                                             const bb::GateSeparatorPolynomial<FF>& gate_separators)
    {
        // Pow-Factor  \f$ (1-X) + X\beta_i \f$
        auto random_polynomial = bb::Univariate<FF, 2>({ 1, gate_separators.current_element() });
        ExtendedUnivariate extended_random_polynomial =
            random_polynomial.template extend_to<ExtendedUnivariate::LENGTH>();
 
        constexpr_for<0, std::tuple_size_v<TupleOfTuplesOfUnivariates>, 1>([&]<size_t relation_idx>() {
            const auto& outer_element = std::get<relation_idx>(tuple);
            constexpr_for<0, std::tuple_size_v<std::decay_t<decltype(outer_element)>>, 1>(
                [&]<size_t subrelation_idx>() {
                    const auto& element = std::get<subrelation_idx>(outer_element);
                    auto extended = element.template extend_to<ExtendedUnivariate::LENGTH>();
 
                    using Relation = typename std::tuple_element_t<relation_idx, Relations>;
                    constexpr bool is_subrelation_linearly_independent =
                        bb::subrelation_is_linearly_independent<Relation, subrelation_idx>();
                    // Except from the log derivative subrelation, each other subrelation in part is required to be 0
                    // hence we multiply by the power polynomial. As the sumcheck prover is required to send a
                    // univariate to the verifier, we additionally need a univariate contribution from the pow
                    // polynomial which is the extended_random_polynomial which is the
                    if constexpr (!is_subrelation_linearly_independent) {
                        result += extended;
                    } else {
                        // Multiply by the pow polynomial univariate contribution and the partial
                        // evaluation result c_i (i.e. \f$ pow(u_0,...,u_{l-1})) \f$ where \f$(u_0,...,u_{i-1})\f$ are
                        // the verifier challenges from previous rounds.
                        result += extended * extended_random_polynomial * gate_separators.partial_evaluation_result;
                    }
                });
        });
    }
 
    static SumcheckRoundUnivariate compute_libra_univariate(const ZKData& zk_sumcheck_data, size_t round_idx)
    {
        bb::Univariate<FF, LIBRA_UNIVARIATES_LENGTH> libra_round_univariate;
        // select the i'th column of Libra book-keeping table
        const auto& current_column = zk_sumcheck_data.libra_univariates[round_idx];
        // the evaluation of Libra round univariate at k=0...D are equal to \f$\texttt{libra_univariates}_{i}(k)\f$
        // corrected by the Libra running sum
        for (size_t idx = 0; idx < LIBRA_UNIVARIATES_LENGTH; ++idx) {
            libra_round_univariate.value_at(idx) =
                current_column.evaluate(FF(idx)) + zk_sumcheck_data.libra_running_sum;
        };
        if constexpr (BATCHED_RELATION_PARTIAL_LENGTH == LIBRA_UNIVARIATES_LENGTH) {
            return libra_round_univariate;
        } else {
            return libra_round_univariate.template extend_to<SumcheckRoundUnivariate::LENGTH>();
        }
    }
 
    // Methods made accessible for testing
    void accumulate_relation_univariates_public(SumcheckTupleOfTuplesOfUnivariates& univariate_accumulators,
                                                const auto& extended_edges,
                                                const bb::RelationParameters<FF>& relation_parameters,
                                                const FF& scaling_factor)
    {
        accumulate_relation_univariates(univariate_accumulators, extended_edges, relation_parameters, scaling_factor);
    }
 
  private:
    void accumulate_relation_univariates(SumcheckTupleOfTuplesOfUnivariates& univariate_accumulators,
                                         const auto& extended_edges,
                                         const bb::RelationParameters<FF>& relation_parameters,
                                         const FF& scaling_factor)
    {
        constexpr_for<0, NUM_RELATIONS, 1>([&]<size_t relation_idx>() {
            using Relation = std::tuple_element_t<relation_idx, Relations>;
            // Check if the relation is skippable to speed up accumulation
            if constexpr (!isSkippable<Relation, decltype(extended_edges)>) {
                // If not, accumulate normally
                Relation::accumulate(std::get<relation_idx>(univariate_accumulators),
                                     extended_edges,
                                     relation_parameters,
                                     scaling_factor);
            } else {
                // If so, only compute the contribution if the relation is active
                if (!Relation::skip(extended_edges)) {
                    Relation::accumulate(std::get<relation_idx>(univariate_accumulators),
                                         extended_edges,
                                         relation_parameters,
                                         scaling_factor);
                }
            }
        });
    }
};
 
template <typename Flavor, bool IsGrumpkin = IsGrumpkinFlavor<Flavor>> class SumcheckVerifierRound {
    using FF = typename Flavor::FF;
    using Utils = bb::RelationUtils<Flavor>;
    using Relations = typename Flavor::Relations;
    using TupleOfArraysOfValues = decltype(create_tuple_of_arrays_of_values<typename Flavor::Relations>());
    using SubrelationSeparators = std::array<FF, Flavor::NUM_SUBRELATIONS - 1>;
 
  public:
    using ClaimedEvaluations = typename Flavor::AllValues;
    using ClaimedLibraEvaluations = typename std::vector<FF>;
    using Transcript = typename Flavor::Transcript;
    using Commitment = typename Flavor::Commitment;
 
    bool round_failed = false;
    static constexpr size_t NUM_RELATIONS = Flavor::NUM_RELATIONS;
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH;
    using SumcheckRoundUnivariate = bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>;
 
    FF target_total_sum = 0;
    TupleOfArraysOfValues relation_evaluations;
 
    explicit SumcheckVerifierRound(FF target_total_sum = 0)
        : target_total_sum(target_total_sum)
    {
        Utils::zero_elements(relation_evaluations);
    };
 
    void check_sum(bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>& univariate, const FF& indicator)
    {
        // OriginTag false positive: The univariate is constrained by the sumcheck relation S^i(0) + S^i(1) =
        // S^{i-1}(u_{i-1}).
        if constexpr (IsRecursiveFlavor<Flavor>) {
            const auto bound_tag = target_total_sum.get_origin_tag();
            for (auto& eval : univariate.evaluations) {
                eval.set_origin_tag(bound_tag);
            }
        }
 
        FF total_sum =
            (FF(1) - indicator) * target_total_sum + indicator * (univariate.value_at(0) + univariate.value_at(1));
        bool sumcheck_round_failed(false);
        if constexpr (IsRecursiveFlavor<Flavor>) {
            if (indicator.get_value() == FF{ 1 }.get_value()) {
                sumcheck_round_failed = (target_total_sum.get_value() != total_sum.get_value());
            }
            target_total_sum.assert_equal(total_sum);
        } else {
            sumcheck_round_failed = (target_total_sum != total_sum);
        }
        round_failed = round_failed || sumcheck_round_failed;
    };
 
    void compute_next_target_sum(bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>& univariate,
                                 FF& round_challenge,
                                 const FF& indicator)
    {
        target_total_sum = (FF(1) - indicator) * target_total_sum + indicator * univariate.evaluate(round_challenge);
    }
 
    FF compute_full_relation_purported_value(const ClaimedEvaluations& purported_evaluations,
                                             const bb::RelationParameters<FF>& relation_parameters,
                                             const bb::GateSeparatorPolynomial<FF>& gate_separators,
                                             const SubrelationSeparators& alphas)
    {
        Utils::template accumulate_relation_evaluations_without_skipping<>(purported_evaluations,
                                                                           relation_evaluations,
                                                                           relation_parameters,
                                                                           gate_separators.partial_evaluation_result);
        return Utils::scale_and_batch_elements(relation_evaluations, alphas);
    }
 
    void process_round(const std::shared_ptr<Transcript>& transcript,
                       std::vector<FF>& multivariate_challenge,
                       bb::GateSeparatorPolynomial<FF>& gate_separators,
                       const FF& padding_indicator,
                       size_t round_idx)
    {
        // Obtain the round univariate from the transcript
        std::string round_univariate_label = "Sumcheck:univariate_" + std::to_string(round_idx);
        auto 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);
        // Check that $\tilde{S}^{i-1}(u_{i-1}) == \tilde{S}^{i}(0) + \tilde{S}^{i}(1)$
        // For i = 0, check that $\tilde{S}^0(u_0) == target_total_sum$
        check_sum(round_univariate, padding_indicator);
        // Evaluate $\tilde{S}^{i}(u_i)$
        compute_next_target_sum(round_univariate, round_challenge, padding_indicator);
        gate_separators.partially_evaluate(round_challenge, padding_indicator);
    }
 
    bool perform_final_verification(const FF& full_honk_purported_value)
    {
        bool verified = false;
        if constexpr (IsRecursiveFlavor<Flavor>) {
            verified = (full_honk_purported_value.get_value() == target_total_sum.get_value());
            full_honk_purported_value.assert_equal(target_total_sum);
        } else {
            verified = (full_honk_purported_value == target_total_sum);
        }
        return verified;
    }
 
    std::vector<Commitment> get_round_univariate_commitments() { return {}; }
 
    std::vector<std::array<FF, 3>> get_round_univariate_evaluations() { return {}; }
};
 
template <typename Flavor> class SumcheckVerifierRound<Flavor, true> {
    using FF = typename Flavor::FF;
    using Utils = bb::RelationUtils<Flavor>;
    using Relations = typename Flavor::Relations;
    using TupleOfArraysOfValues = decltype(create_tuple_of_arrays_of_values<typename Flavor::Relations>());
    using SubrelationSeparators = std::array<FF, Flavor::NUM_SUBRELATIONS - 1>;
 
  public:
    using ClaimedEvaluations = typename Flavor::AllValues;
    using ClaimedLibraEvaluations = typename std::vector<FF>;
    using Transcript = typename Flavor::Transcript;
    using Commitment = typename Flavor::Commitment;
 
    bool round_failed = false;
    static constexpr size_t NUM_RELATIONS = Flavor::NUM_RELATIONS;
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH;
    using SumcheckRoundUnivariate = bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>;
 
    FF target_total_sum = 0;
    TupleOfArraysOfValues relation_evaluations;
 
    // Grumpkin-specific state for Shplemini
    std::vector<Commitment> round_univariate_commitments;
    std::vector<std::array<FF, 3>> round_univariate_evaluations;
 
    explicit SumcheckVerifierRound(FF target_total_sum = 0)
        : target_total_sum(target_total_sum)
    {
        Utils::zero_elements(relation_evaluations);
    };
 
    FF compute_full_relation_purported_value(const ClaimedEvaluations& purported_evaluations,
                                             const bb::RelationParameters<FF>& relation_parameters,
                                             const bb::GateSeparatorPolynomial<FF>& gate_separators,
                                             const SubrelationSeparators& alphas)
    {
        Utils::template accumulate_relation_evaluations_without_skipping<>(purported_evaluations,
                                                                           relation_evaluations,
                                                                           relation_parameters,
                                                                           gate_separators.partial_evaluation_result);
        return Utils::scale_and_batch_elements(relation_evaluations, alphas);
    }
 
    void process_round(const std::shared_ptr<Transcript>& transcript,
                       std::vector<FF>& multivariate_challenge,
                       bb::GateSeparatorPolynomial<FF>& gate_separators,
                       const FF& /*padding_indicator*/,
                       size_t round_idx)
    {
        // For Grumpkin, we don't use padding_indicator
        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),
              FF(0) }); // Third element will be populated in perform_final_verification
 
        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);
 
        // For Grumpkin, we don't perform per-round verification here
        // It will be deferred to the final check
    }
 
    bool perform_final_verification(const FF& full_honk_purported_value)
    {
        // Compute the sum of evaluations at 0 and 1 for the first round
        FF first_sumcheck_round_evaluations_sum =
            round_univariate_evaluations[0][0] + round_univariate_evaluations[0][1];
 
        bool verified = false;
        if constexpr (IsRecursiveFlavor<Flavor>) {
            first_sumcheck_round_evaluations_sum.self_reduce();
            target_total_sum.self_reduce();
            // This bool is only needed for debugging
            verified = (first_sumcheck_round_evaluations_sum.get_value() == 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(target_total_sum);
 
            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 == target_total_sum);
        }
 
        // Populate claimed evaluations of Sumcheck Round Univariates at the round challenges.
        // These will be checked as a part of Shplemini.
        for (size_t round_idx = 1; round_idx < round_univariate_evaluations.size(); round_idx++) {
            round_univariate_evaluations[round_idx - 1][2] =
                round_univariate_evaluations[round_idx][0] + round_univariate_evaluations[round_idx][1];
        }
 
        // Store the final evaluation for Shplemini
        round_univariate_evaluations[round_univariate_evaluations.size() - 1][2] = full_honk_purported_value;
        return verified;
    }
 
    std::vector<Commitment> get_round_univariate_commitments() { return round_univariate_commitments; }
 
    std::vector<std::array<FF, 3>> get_round_univariate_evaluations() { return round_univariate_evaluations; }
};
} // namespace bb