sumcheck.hpp

#pragma once
#include "barretenberg/proof_system/library/grand_product_delta.hpp"
#include "barretenberg/sumcheck/instance/prover_instance.hpp"
#include "barretenberg/sumcheck/sumcheck_output.hpp"
#include "barretenberg/transcript/transcript.hpp"
#include "sumcheck_round.hpp"
 
namespace proof_system::honk::sumcheck {
 
template <typename Flavor> class SumcheckProver {
 
  public:
    using FF = typename Flavor::FF;
    using ProverPolynomials = typename Flavor::ProverPolynomials;
    using PartiallyEvaluatedMultivariates = typename Flavor::PartiallyEvaluatedMultivariates;
    using ClaimedEvaluations = typename Flavor::AllValues;
    using Transcript = typename Flavor::Transcript;
    using Instance = ProverInstance_<Flavor>;
 
    std::shared_ptr<Transcript> transcript;
 
    const size_t multivariate_n;
    const size_t multivariate_d;
    SumcheckProverRound<Flavor> round;
 
    PartiallyEvaluatedMultivariates partially_evaluated_polynomials;
 
    // prover instantiates sumcheck with circuit size and a prover transcript
    SumcheckProver(size_t multivariate_n, const std::shared_ptr<Transcript>& transcript)
        : transcript(transcript)
        , multivariate_n(multivariate_n)
        , multivariate_d(numeric::get_msb(multivariate_n))
        , round(multivariate_n)
        , partially_evaluated_polynomials(multivariate_n){};
 
    SumcheckOutput<Flavor> prove(ProverPolynomials& full_polynomials,
                                 const proof_system::RelationParameters<FF>& relation_parameters,
                                 FF alpha) // pass by value, not by reference
    {
        FF zeta = transcript->get_challenge("Sumcheck:zeta");
 
        barretenberg::PowUnivariate<FF> pow_univariate(zeta);
 
        std::vector<FF> multivariate_challenge;
        multivariate_challenge.reserve(multivariate_d);
 
        // First round
        // This populates partially_evaluated_polynomials.
        auto round_univariate = round.compute_univariate(full_polynomials, relation_parameters, pow_univariate, alpha);
        transcript->send_to_verifier("Sumcheck:univariate_0", round_univariate);
        FF round_challenge = transcript->get_challenge("Sumcheck:u_0");
        multivariate_challenge.emplace_back(round_challenge);
        partially_evaluate(full_polynomials, multivariate_n, round_challenge);
        pow_univariate.partially_evaluate(round_challenge);
        round.round_size =
            round.round_size >> 1; // TODO(#224)(Cody): Maybe partially_evaluate should do this and release memory?
 
        // All but final round
        // We operate on partially_evaluated_polynomials in place.
        for (size_t round_idx = 1; round_idx < multivariate_d; round_idx++) {
            // Write the round univariate to the transcript
            round_univariate =
                round.compute_univariate(partially_evaluated_polynomials, relation_parameters, pow_univariate, alpha);
            transcript->send_to_verifier("Sumcheck:univariate_" + std::to_string(round_idx), round_univariate);
            FF round_challenge = transcript->get_challenge("Sumcheck:u_" + std::to_string(round_idx));
            multivariate_challenge.emplace_back(round_challenge);
            partially_evaluate(partially_evaluated_polynomials, round.round_size, round_challenge);
            pow_univariate.partially_evaluate(round_challenge);
            round.round_size = round.round_size >> 1;
        }
 
        // Final round: Extract multivariate evaluations from partially_evaluated_polynomials and add to transcript
        ClaimedEvaluations multivariate_evaluations;
        for (auto [eval, poly] :
             zip_view(multivariate_evaluations.get_all(), partially_evaluated_polynomials.get_all())) {
            eval = (poly)[0];
        }
        transcript->send_to_verifier("Sumcheck:evaluations", multivariate_evaluations);
 
        return { multivariate_challenge, multivariate_evaluations };
    };
 
    SumcheckOutput<Flavor> prove(std::shared_ptr<Instance> instance)
    {
        return prove(instance->prover_polynomials, instance->relation_parameters, instance->alpha);
    };
 
    void partially_evaluate(auto& polynomials, size_t round_size, FF round_challenge)
    {
        auto pep_view = partially_evaluated_polynomials.get_all();
        auto poly_view = polynomials.get_all();
        // after the first round, operate in place on partially_evaluated_polynomials
        parallel_for(poly_view.size(), [&](size_t j) {
            for (size_t i = 0; i < round_size; i += 2) {
                pep_view[j][i >> 1] = poly_view[j][i] + round_challenge * (poly_view[j][i + 1] - poly_view[j][i]);
            }
        });
    };
    template <typename PolynomialT, std::size_t N>
    void partially_evaluate(std::array<PolynomialT, N>& polynomials, size_t round_size, FF round_challenge)
    {
        auto pep_view = partially_evaluated_polynomials.get_all();
        // after the first round, operate in place on partially_evaluated_polynomials
        parallel_for(polynomials.size(), [&](size_t j) {
            for (size_t i = 0; i < round_size; i += 2) {
                pep_view[j][i >> 1] = polynomials[j][i] + round_challenge * (polynomials[j][i + 1] - polynomials[j][i]);
            }
        });
    };
};
 
template <typename Flavor> class SumcheckVerifier {
 
  public:
    using Utils = barretenberg::RelationUtils<Flavor>;
    using FF = typename Flavor::FF;
    using ClaimedEvaluations = typename Flavor::AllValues;
    using Transcript = typename Flavor::Transcript;
 
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH;
    static constexpr size_t NUM_POLYNOMIALS = Flavor::NUM_ALL_ENTITIES;
 
    const size_t multivariate_d;
    SumcheckVerifierRound<Flavor> round;
 
    // verifier instantiates sumcheck with circuit size
    explicit SumcheckVerifier(size_t multivariate_n)
        : multivariate_d(numeric::get_msb(multivariate_n))
        , round(){};
 
    SumcheckOutput<Flavor> verify(const proof_system::RelationParameters<FF>& relation_parameters,
                                  FF alpha,
                                  const std::shared_ptr<Transcript>& transcript)
    {
        bool verified(true);
 
        FF zeta = transcript->get_challenge("Sumcheck:zeta");
 
        barretenberg::PowUnivariate<FF> pow_univariate(zeta);
        // All but final round.
        // target_total_sum is initialized to zero then mutated in place.
 
        if (multivariate_d == 0) {
            throw_or_abort("Number of variables in multivariate is 0.");
        }
 
        std::vector<FF> multivariate_challenge;
        multivariate_challenge.reserve(multivariate_d);
 
        for (size_t round_idx = 0; round_idx < multivariate_d; 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<barretenberg::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>>(
                    round_univariate_label);
 
            bool checked = round.check_sum(round_univariate);
            verified = verified && checked;
            FF round_challenge = transcript->get_challenge("Sumcheck:u_" + std::to_string(round_idx));
            multivariate_challenge.emplace_back(round_challenge);
 
            round.compute_next_target_sum(round_univariate, round_challenge);
            pow_univariate.partially_evaluate(round_challenge);
        }
 
        // Final round
        ClaimedEvaluations purported_evaluations;
        auto transcript_evaluations =
            transcript->template receive_from_prover<std::array<FF, NUM_POLYNOMIALS>>("Sumcheck:evaluations");
        for (auto [eval, transcript_eval] : zip_view(purported_evaluations.get_all(), transcript_evaluations)) {
            eval = transcript_eval;
        }
 
        FF full_honk_relation_purported_value = round.compute_full_honk_relation_purported_value(
            purported_evaluations, relation_parameters, pow_univariate, alpha);
 
        bool checked = false;
        if constexpr (IsRecursiveFlavor<Flavor>) {
            checked = (full_honk_relation_purported_value == round.target_total_sum).get_value();
        } else {
            checked = (full_honk_relation_purported_value == round.target_total_sum);
        }
        verified = verified && checked;
 
        return SumcheckOutput<Flavor>{ multivariate_challenge, purported_evaluations, verified };
    };
};
} // namespace proof_system::honk::sumcheck