sumcheck_round.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/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");
 
        // 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.
        // For now we use a power of 2 number of threads simply to ensure the round size is evenly divided.
        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_pow2(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. Below we name a portion in the chunk being processed by any given thread
        // a "chunk thread portion".
        // We have: round_size = num_of_chunks * chunk_size and chunk_size = num_threads * chunk_thread_portion_size
        // Important invariant: round_size = num_of_chunks * num_threads * chunk_thread_portion_size
        // All the involved values are power of 2. We also require chunk_thread_portion_size >= 2
        // because a "work unit" cannot be smaller than 2 as extended_edges() process 2 edges at a time.
        //
        // Example: round_size = 4096, num_threads = 16, chunk_thread_portion_size = 8
        // - chunk_size = 16 * 8 = 128
        // - num_of_chunks = 4096/128 = 32
        //
        // For each chunk with index chunk_idx, the thread with index thread_idx will process the edges
        // in range starting at index: chunk_idx * chunk_size + thread_idx * chunk_thread_portion_size
        // up to index (not included): chunk_idx * chunk_size + (thread_idx + 1) * chunk_thread_portion_size
        //
        // Pattern over edges is now:
        //
        //          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.
        //
        // MAX_CHUNK_THREAD_PORTION_SIZE is defined in the flavor.
        // The MAX_CHUNK_THREAD_PORTION_SIZE defines the maximum value for chunk_thread_portion_size. Whenever the
        // round_size is large enough, we set chunk_thread_portion_size = MAX_CHUNK_THREAD_PORTION_SIZE. When it is not
        // possible we use a smaller value but must be at least 2 as mentioned above. If chunk_thread_portion_size is
        // not at least 2, we fallback to using a single chunk. Note that chunk_size and num_of_chunks are not constant
        // but are derived by round_size, num_threads and the chunk_thread_portion_size which needs to satisfy: 1) 2 <=
        // chunk_thread_portion_size <= MAX_CHUNK_THREAD_PORTION_SIZE 2) chunk_thread_portion_size * num_threads <=
        // round_size For the non-AVM flavors, we use a single chunk.
 
        // Non AVM flavors
        size_t num_of_chunks = 1;
        size_t chunk_thread_portion_size = round_size / num_threads;
 
        // This constant is assumed to be a power of 2 greater or equal to 2.
        static_assert(Flavor::MAX_CHUNK_THREAD_PORTION_SIZE >= 2);
        static_assert((Flavor::MAX_CHUNK_THREAD_PORTION_SIZE & (Flavor::MAX_CHUNK_THREAD_PORTION_SIZE - 1)) == 0);
 
        // When the number of edges is so small that the chunk portion size per thread is lower than 2,
        // we fall back to a single chunk, i.e., we keep the "non-AVM" values.
        if (round_size / num_threads >= 2) {
            chunk_thread_portion_size = std::min(round_size / num_threads, Flavor::MAX_CHUNK_THREAD_PORTION_SIZE);
            num_of_chunks = round_size / (chunk_thread_portion_size * num_threads);
            // We show that chunk_thread_portion_size satisfies 1) and 2) defined above.
            // From "std::min()": chunk_thread_portion_size <= round_size/num_threads implying 2)
            // From static_assert above, and "if condition", we know that both values in "std::min()"
            // are >= 2 and therefore: chunk_thread_portion_size >= 2
            // Finally, "std::min()" guarantees that: chunk_thread_portion_size <= MAX_CHUNK_THREAD_PORTION_SIZE
            // which completes 1).
        }
 
        size_t chunk_size = round_size / num_of_chunks;
        // 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 accross each edge of the hyper-cube
        parallel_for(num_threads, [&](size_t thread_idx) {
            // Construct extended univariates containers; one per thread
            ExtendedEdges lazy_extended_edges(polynomials);
 
            for (size_t chunk_idx = 0; chunk_idx < num_of_chunks; chunk_idx++) {
                size_t start = (chunk_idx * chunk_size) + (thread_idx * chunk_thread_portion_size);
                size_t end = (chunk_idx * chunk_size) + ((thread_idx + 1) * chunk_thread_portion_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);
 
        const size_t min_iterations_per_thread = 1 << 10; // min number of iterations for which we'll spin up a unique
        const size_t num_threads = bb::calculate_num_threads_pow2(effective_round_size, min_iterations_per_thread);
 
        std::vector<BlockOfContiguousRows> result;
        constexpr bool can_skip_rows = (isRowSkippable<Flavor, decltype(polynomials), size_t>);
 
        if constexpr (can_skip_rows) {
            std::vector<std::vector<BlockOfContiguousRows>> all_thread_blocks(num_threads);
            parallel_for(num_threads, [&](size_t thread_idx) {
                ThreadChunk chunk{ .thread_index = thread_idx, .total_threads = num_threads };
                auto range = chunk.range(effective_round_size);
                if (range.empty()) {
                    return;
                }
                size_t current_block_size = 0;
                size_t start = *range.begin();
                size_t end = start + range.size();
                std::vector<BlockOfContiguousRows> thread_blocks;
                for (size_t edge_idx = start; edge_idx < end; edge_idx += 2) {
                    if (!Flavor::skip_entire_row(polynomials, edge_idx)) {
                        current_block_size += 2;
                    } else {
                        if (current_block_size > 0) {
                            thread_blocks.push_back(BlockOfContiguousRows{
                                .starting_edge_idx = edge_idx - current_block_size, .size = current_block_size });
                            current_block_size = 0;
                        }
                    }
                }
                if (current_block_size > 0) {
                    thread_blocks.push_back(BlockOfContiguousRows{ .starting_edge_idx = end - current_block_size,
                                                                   .size = current_block_size });
                }
                all_thread_blocks[thread_idx] = thread_blocks;
            });
 
            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)
    {
        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