sumcheck_round.hpp

#pragma once
#include "barretenberg/common/thread.hpp"
#include "barretenberg/common/thread_utils.hpp"
#include "barretenberg/flavor/flavor.hpp"
#include "barretenberg/polynomials/pow.hpp"
#include "barretenberg/relations/relation_parameters.hpp"
#include "barretenberg/relations/relation_types.hpp"
#include "barretenberg/relations/utils.hpp"
 
namespace proof_system::honk::sumcheck {
 
/*
 Notation: The polynomial P(X0, X1) that is the low-degree extension of its values vij = P(i,j)
 for i,j ∈ H = {0,1} is conveniently recorded as follows:
     (0,1)-----(1,1)   v01 ------ v11
       |          |     |          |  P(X0,X1) =   (v00 * (1-X0) + v10 * X0) * (1-X1)
   X1  |   H^2    |     | P(X0,X1) |             + (v01 * (1-X0) + v11 * X0) *   X1
       |          |     |          |
     (0,0) ---- (1,0)  v00 -------v10
            X0
*/
 
/*
 Example: There are two low-degree extensions Y1, Y2 over the square H^2 in the Cartesian plane.
 
    3 -------- 7   4 -------- 8
    |          |   |          | Let F(X0, X1) = G(Y1, Y2) =     G0(Y1(X0, X1), Y2(X0, X1))
    |    Y1    |   |    Y2    |                             + α G1(Y1(X0, X1), Y2(X0, X1)),
    |          |   |          |  where the relations are G0(Y1, Y2) = Y1 * Y2
    1 -------- 5   2 -------- 6                      and G1(Y1, Y2) = Y1 + Y2.
 
 G1, G2 together comprise the Relations.
 
 In the first round, the computations will relate elements along horizontal lines. As a mnemonic, we
 use the term "edge" for the linear, univariate polynomials corresponding to the four lines
  1 - 5
  2 - 6
  3 - 7
  4 - 8
 
 The polynomials Y1, Y2 are stored in an array in Multivariates. In the first round, these are arrays
 of spans living outside of the Multivariates object, and in sebsequent rounds these are arrays of field
 elements that are stored in the Multivariates. The rationale for adopting this model is to
 avoid copying the full-length polynomials; this way, the largest polynomial array stores in a
 Multivariates class is multivariates_n/2.
 
 Note: This class uses recursive function calls with template parameters. This is a common trick that is used to force
 the compiler to unroll loops. The idea is that a function that is only called once will always be inlined, and since
 template functions always create different functions, this is guaranteed.
 
 */
 
template <typename Flavor> class SumcheckProverRound {
 
    using Utils = barretenberg::RelationUtils<Flavor>;
    using Relations = typename Flavor::Relations;
    using SumcheckTupleOfTuplesOfUnivariates = typename Flavor::SumcheckTupleOfTuplesOfUnivariates;
 
  public:
    using FF = typename Flavor::FF;
    using ExtendedEdges = typename Flavor::ExtendedEdges;
 
    size_t round_size; // a power of 2
 
    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;
 
    SumcheckTupleOfTuplesOfUnivariates univariate_accumulators;
 
    // Prover constructor
    SumcheckProverRound(size_t initial_round_size)
        : round_size(initial_round_size)
    {
        // Initialize univariate accumulators to 0
        Utils::zero_univariates(univariate_accumulators);
    }
 
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates>
    void extend_edges(ExtendedEdges& extended_edges,
                      const ProverPolynomialsOrPartiallyEvaluatedMultivariates& multivariates,
                      size_t edge_idx)
    {
        for (auto [extended_edge, multivariate] : zip_view(extended_edges.get_all(), multivariates.get_all())) {
            barretenberg::Univariate<FF, 2> edge({ multivariate[edge_idx], multivariate[edge_idx + 1] });
            extended_edge = edge.template extend_to<MAX_PARTIAL_RELATION_LENGTH>();
        }
    }
 
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates>
    barretenberg::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH> compute_univariate(
        ProverPolynomialsOrPartiallyEvaluatedMultivariates& polynomials,
        const proof_system::RelationParameters<FF>& relation_parameters,
        const barretenberg::PowUnivariate<FF>& pow_univariate,
        const FF alpha)
    {
        // Precompute the vector of required powers of zeta
        // TODO(luke): Parallelize this
        std::vector<FF> pow_challenges(round_size >> 1);
        pow_challenges[0] = pow_univariate.partial_evaluation_constant;
        for (size_t i = 1; i < (round_size >> 1); ++i) {
            pow_challenges[i] = pow_challenges[i - 1] * pow_univariate.zeta_pow_sqr;
        }
 
        // 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 =
            barretenberg::thread_utils::calculate_num_threads_pow2(round_size, min_iterations_per_thread);
        size_t iterations_per_thread = round_size / num_threads; // actual iterations per thread
 
        // Construct univariate accumulator containers; one per thread
        std::vector<SumcheckTupleOfTuplesOfUnivariates> thread_univariate_accumulators(num_threads);
        for (auto& accum : thread_univariate_accumulators) {
            Utils::zero_univariates(accum);
        }
 
        // Construct extended edge containers; one per thread
        std::vector<ExtendedEdges> extended_edges;
        extended_edges.resize(num_threads);
 
        // Accumulate the contribution from each sub-relation accross each edge of the hyper-cube
        parallel_for(num_threads, [&](size_t thread_idx) {
            size_t start = thread_idx * iterations_per_thread;
            size_t end = (thread_idx + 1) * iterations_per_thread;
 
            // For each edge_idx = 2i, we need to multiply the whole contribution by zeta^{2^{2i}}
            // This means that each univariate for each relation needs an extra multiplication.
            for (size_t edge_idx = start; edge_idx < end; edge_idx += 2) {
                extend_edges(extended_edges[thread_idx], polynomials, edge_idx);
 
                // Update the pow polynomial's contribution c_l ⋅ ζ_{l+1}ⁱ for the next edge.
                FF pow_challenge = pow_challenges[edge_idx >> 1];
 
                // Compute the i-th edge's univariate contribution,
                // scale it by the pow polynomial's constant and zeta power "c_l ⋅ ζ_{l+1}ⁱ"
                // and add it to the accumulators for Sˡ(Xₗ)
                accumulate_relation_univariates(thread_univariate_accumulators[thread_idx],
                                                extended_edges[thread_idx],
                                                relation_parameters,
                                                pow_challenge);
            }
        });
 
        // 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<barretenberg::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>>(
            univariate_accumulators, alpha, pow_univariate);
    }
 
    template <typename ExtendedUnivariate, typename ContainerOverSubrelations>
    static ExtendedUnivariate batch_over_relations(ContainerOverSubrelations& univariate_accumulators,
                                                   const FF& challenge,
                                                   const barretenberg::PowUnivariate<FF>& pow_univariate)
    {
        auto running_challenge = FF(1);
        Utils::scale_univariates(univariate_accumulators, challenge, running_challenge);
 
        auto result = ExtendedUnivariate(0);
        extend_and_batch_univariates(univariate_accumulators, result, pow_univariate);
 
        // 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 barretenberg::PowUnivariate<FF>& pow_univariate)
    {
        ExtendedUnivariate extended_random_polynomial;
        // Random poly R(X) = (1-X) + X.zeta_pow
        auto random_polynomial = barretenberg::Univariate<FF, 2>({ 1, pow_univariate.zeta_pow });
        extended_random_polynomial = random_polynomial.template extend_to<ExtendedUnivariate::LENGTH>();
 
        auto extend_and_sum = [&]<size_t relation_idx, size_t subrelation_idx, typename Element>(Element& element) {
            auto extended = element.template extend_to<ExtendedUnivariate::LENGTH>();
 
            using Relation = typename std::tuple_element_t<relation_idx, Relations>;
            const bool is_subrelation_linearly_independent =
                proof_system::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.
            if (!is_subrelation_linearly_independent) {
                result += extended;
            } else {
                result += extended * extended_random_polynomial;
            }
        };
        Utils::apply_to_tuple_of_tuples(tuple, extend_and_sum);
    }
 
  private:
    template <size_t relation_idx = 0>
    void accumulate_relation_univariates(SumcheckTupleOfTuplesOfUnivariates& univariate_accumulators,
                                         const auto& extended_edges,
                                         const proof_system::RelationParameters<FF>& relation_parameters,
                                         const FF& scaling_factor)
    {
        using Relation = std::tuple_element_t<relation_idx, Relations>;
        Relation::accumulate(
            std::get<relation_idx>(univariate_accumulators), extended_edges, relation_parameters, scaling_factor);
 
        // Repeat for the next relation.
        if constexpr (relation_idx + 1 < NUM_RELATIONS) {
            accumulate_relation_univariates<relation_idx + 1>(
                univariate_accumulators, extended_edges, relation_parameters, scaling_factor);
        }
    }
};
 
template <typename Flavor> class SumcheckVerifierRound {
    using Utils = barretenberg::RelationUtils<Flavor>;
    using Relations = typename Flavor::Relations;
    using TupleOfArraysOfValues = typename Flavor::TupleOfArraysOfValues;
 
  public:
    using FF = typename Flavor::FF;
    using ClaimedEvaluations = typename Flavor::AllValues;
 
    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;
 
    FF target_total_sum = 0;
 
    TupleOfArraysOfValues relation_evaluations;
 
    // Verifier constructor
    explicit SumcheckVerifierRound() { Utils::zero_elements(relation_evaluations); };
 
    bool check_sum(barretenberg::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>& univariate)
    {
        // S^{l}(0) = ( (1−0) + 0⋅ζ^{ 2^l } ) ⋅ T^{l}(0) = T^{l}(0)
        // S^{l}(1) = ( (1−1) + 1⋅ζ^{ 2^l } ) ⋅ T^{l}(1) = ζ^{ 2^l } ⋅ T^{l}(1)
        FF total_sum = univariate.value_at(0) + univariate.value_at(1);
        // target_total_sum = sigma_{l} =
        // TODO(#673): Conditionals like this can go away once native verification is is just recursive verification
        // with a simulated builder.
        bool sumcheck_round_failed(false);
        if constexpr (IsRecursiveFlavor<Flavor>) {
            target_total_sum.assert_equal(total_sum);
            sumcheck_round_failed = (target_total_sum != total_sum).get_value();
        } else {
            sumcheck_round_failed = (target_total_sum != total_sum);
        }
 
        round_failed = round_failed || sumcheck_round_failed;
        return !sumcheck_round_failed;
    };
 
    FF compute_next_target_sum(barretenberg::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>& univariate,
                               FF& round_challenge)
    {
        // Evaluate T^{l}(u_{l})
        target_total_sum = univariate.evaluate(round_challenge);
        return target_total_sum;
    }
 
    // also copy paste in PG
    // so instead of having claimed evaluations of each relation in part  you have the actual evaluations
    // kill the pow_univariat
    FF compute_full_honk_relation_purported_value(ClaimedEvaluations purported_evaluations,
                                                  const proof_system::RelationParameters<FF>& relation_parameters,
                                                  const barretenberg::PowUnivariate<FF>& pow_univariate,
                                                  const FF alpha)
    {
        Utils::template accumulate_relation_evaluations<>(purported_evaluations,
                                                          relation_evaluations,
                                                          relation_parameters,
                                                          pow_univariate.partial_evaluation_constant);
 
        auto running_challenge = FF(1);
        auto output = FF(0);
        Utils::scale_and_batch_elements(relation_evaluations, alpha, running_challenge, output);
        return output;
    }
};
} // namespace proof_system::honk::sumcheck