Implementation of the sumcheck Verifier for statements of the form \(\sum_{\vec \ell \in \{0,1\}^d} pow_{\beta}(\vec \ell) \cdot F \left(P_1(\vec \ell),\ldots, P_N(\vec \ell) \right) = 0 \) for multilinear polynomials \(P_1, \ldots, P_N \). More...

#include <sumcheck.hpp>

Public Types
using	Utils = bb::RelationUtils< Flavor >

using	FF = typename Flavor::FF

using	ClaimedEvaluations = typename Flavor::AllValues
	Container type for the evaluations of Prover Polynomials \(P_1,\ldots,P_N\) at the challenge point \((u_0,\ldots, u_{d-1}) \).

using	ClaimedLibraEvaluations = typename std::vector< FF >

using	Transcript = typename Flavor::Transcript

using	SubrelationSeparators = typename Flavor::SubrelationSeparators

using	Commitment = typename Flavor::Commitment

Public Member Functions
	SumcheckVerifier (std::shared_ptr< Transcript > transcript, SubrelationSeparators &relation_separator, size_t virtual_log_n, FF target_sum=0)

	SumcheckVerifier (std::shared_ptr< Transcript > transcript, const FF &alpha, size_t virtual_log_n, FF target_sum=0)

SumcheckOutput< Flavor >	verify (const bb::RelationParameters< FF > &relation_parameters, std::vector< FF > &gate_challenges, const std::vector< FF > &padding_indicator_array)
	Extract round univariate, check sum, generate challenge, compute next target sum..., repeat until final round, then use purported evaluations to generate purported full Honk relation value and check against final target sum.

SumcheckOutput< Flavor >	verify (const bb::RelationParameters< FF > &relation_parameters, const std::vector< FF > &gate_challenges)
	Sumcheck Verifier for ECCVM and ECCVMRecursive.

Public Attributes
std::shared_ptr< Transcript >	transcript

SumcheckVerifierRound< Flavor >	round

size_t	virtual_log_n

SubrelationSeparators	alphas

FF	libra_evaluation { 0 }

FF	libra_challenge

FF	libra_total_sum

FF	correcting_factor

std::vector< Commitment >	round_univariate_commitments = {}

std::vector< std::array< FF, 3 > >	round_univariate_evaluations = {}

Static Public Attributes
static constexpr size_t	BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH
	Maximum partial algebraic degree of the relation \(\tilde F = pow_{\beta} \cdot F \), i.e. MAX_PARTIAL_RELATION_LENGTH + 1.

static constexpr size_t	NUM_POLYNOMIALS = Flavor::NUM_ALL_ENTITIES
	The number of Prover Polynomials \( P_1, \ldots, P_N \) specified by the Flavor.

Detailed Description

template<typename Flavor>
class bb::SumcheckVerifier< Flavor >

Implementation of the sumcheck Verifier for statements of the form \(\sum_{\vec \ell \in \{0,1\}^d} pow_{\beta}(\vec \ell) \cdot F \left(P_1(\vec \ell),\ldots, P_N(\vec \ell) \right) = 0 \) for multilinear polynomials \(P_1, \ldots, P_N \).

Init:

Claimed Sumcheck sum: \(\quad \sigma_{ 0 } \gets 0 \)

For \( i = 0,\ldots, d-1\):

Extract Round Univariate's \(\tilde{F}\) evaluations at \(0,\ldots, D \) from the transcript using receive_from_prover method from Base Transcript Class.
Check target sum: \(\quad \sigma_{ i } \stackrel{?}{=} \tilde{S}^i(0) + \tilde{S}^i(1) \)

Compute the challenge \(u_i\) from the transcript using get_challenge method.

Compute next target sum : \( \quad \sigma_{i+1} \gets \tilde{S}^i(u_i) \)

Verifier's Data before Final Step

Entering the final round, the Verifier has already checked that \(\quad \sigma_{ d-1 } = \tilde{S}^{d-2}(u_{d-2}) \stackrel{?}{=} \tilde{S}^{d-1}(0) + \tilde{S}^{d-1}(1) \) and computed \(\sigma_d = \tilde{S}^{d-1}(u_{d-1})\).

Final Verification Step

Extract Add Claimed Evaluations to Transcript of prover polynomials \(P_1,\ldots, P_N\) at the challenge point \( (u_0,\ldots,u_{d-1}) \) from the transcript and bb::SumcheckVerifierRound< Flavor >::compute_full_relation_purported_value "compute evaluation:"
\begin{align}\tilde{F}\left( P_1(u_0,\ldots, u_{d-1}), \ldots, P_N(u_0,\ldots, u_{d-1}) \right)\end{align}
and store it at \( \texttt{full_honk_relation_purported_value} \).

Compare \( \sigma_d \) against the evaluation of \( \tilde{F} \) at \(P_1(u_0,\ldots, u_{d-1}), \ldots, P_N(u_0,\ldots, u_{d-1})\):

\begin{align}\quad \sigma_{ d } \stackrel{?}{=} \tilde{F}\left(P_1(u_{0}, \ldots, u_{d-1}),\ldots, P_N(u_0,\ldots, u_{d-1})\right)\end{align}

        bool final_check(false);
        if constexpr (IsRecursiveFlavor<Flavor>) {
            // These booleans are only needed for debugging
            final_check = (full_honk_purported_value.get_value() == round.target_total_sum.get_value());
            verified = verified && final_check;
 
            full_honk_purported_value.assert_equal(round.target_total_sum);
        } else {
            final_check = (full_honk_purported_value == round.target_total_sum);
            verified = verified && final_check;
        }
 
        return SumcheckOutput<Flavor>{ .challenge = multivariate_challenge,
                                       .claimed_evaluations = purported_evaluations,
                                       .verified = verified,
                                       .claimed_libra_evaluation = libra_evaluation };
    };
 
    SumcheckOutput<Flavor> verify(const bb::RelationParameters<FF>& relation_parameters,
                                  const std::vector<FF>& gate_challenges)
        requires IsGrumpkinFlavor<Flavor>
    {
        bool verified(false);
 
        bb::GateSeparatorPolynomial<FF> gate_separators(gate_challenges);
 
        // get the claimed sum of libra masking multivariate over the hypercube
        libra_total_sum = transcript->template receive_from_prover<FF>("Libra:Sum");
        // get the challenge for the ZK Sumcheck claim
        const FF libra_challenge = transcript->template get_challenge<FF>("Libra:Challenge");
 
        std::vector<FF> multivariate_challenge;
        multivariate_challenge.reserve(virtual_log_n);
        // if Flavor has ZK, the target total sum is corrected by Libra total sum multiplied by the Libra
        // challenge
        round.target_total_sum = libra_total_sum * libra_challenge;
 
        for (size_t round_idx = 0; round_idx < virtual_log_n; round_idx++) {
            // Obtain the round univariate from the transcript
            const std::string round_univariate_comm_label = "Sumcheck:univariate_comm_" + std::to_string(round_idx);
            const std::string univariate_eval_label_0 = "Sumcheck:univariate_" + std::to_string(round_idx) + "_eval_0";
            const std::string univariate_eval_label_1 = "Sumcheck:univariate_" + std::to_string(round_idx) + "_eval_1";
 
            // Receive the commitment to the round univariate
            round_univariate_commitments.push_back(
                transcript->template receive_from_prover<Commitment>(round_univariate_comm_label));
            // Receive evals at 0 and 1
            round_univariate_evaluations.push_back(
                { transcript->template receive_from_prover<FF>(univariate_eval_label_0),
                  transcript->template receive_from_prover<FF>(univariate_eval_label_1) });
 
            const FF round_challenge =
                transcript->template get_challenge<FF>("Sumcheck:u_" + std::to_string(round_idx));
            multivariate_challenge.emplace_back(round_challenge);
 
            gate_separators.partially_evaluate(round_challenge);
        }
 
        FF first_sumcheck_round_evaluations_sum =
            round_univariate_evaluations[0][0] + round_univariate_evaluations[0][1];
 
        // Populate claimed evaluations at the challenge
        ClaimedEvaluations purported_evaluations;
        auto transcript_evaluations =
            transcript->template receive_from_prover<std::array<FF, NUM_POLYNOMIALS>>("Sumcheck:evaluations");
        for (auto [eval, transcript_eval] : zip_view(purported_evaluations.get_all(), transcript_evaluations)) {
            eval = transcript_eval;
        }
        // For ZK Flavors: the evaluation of the Row Disabling Polynomial at the sumcheck challenge
        // Evaluate the Honk relation at the point (u_0, ..., u_{d-1}) using claimed evaluations of prover polynomials.
        // In ZK Flavors, the evaluation is corrected by full_libra_purported_value
        FF full_honk_purported_value = round.compute_full_relation_purported_value(
            purported_evaluations, relation_parameters, gate_separators, alphas);
 
        // Compute the evaluations of the polynomial (1 - \sum L_i) where the sum is for i corresponding to the rows
        // where all sumcheck relations are disabled
        full_honk_purported_value *=
            RowDisablingPolynomial<FF>::evaluate_at_challenge(multivariate_challenge, virtual_log_n);
 
        // Extract claimed evaluations of Libra univariates and compute their sum multiplied by the Libra challenge
        const FF libra_evaluation = transcript->template receive_from_prover<FF>("Libra:claimed_evaluation");
        // Verifier computes full ZK Honk value, taking into account the contribution from the disabled row and the
        // Libra polynomials
        full_honk_purported_value += libra_evaluation * libra_challenge;
 
        // Populate claimed evaluations of Sumcheck Round Unviariates at the round challenges. These will be checked as
        // a part of Shplemini.
        for (size_t round_idx = 1; round_idx < virtual_log_n; round_idx++) {
            round_univariate_evaluations[round_idx - 1][2] =
                round_univariate_evaluations[round_idx][0] + round_univariate_evaluations[round_idx][1];
        };
 
        if constexpr (IsRecursiveFlavor<Flavor>) {
 
            first_sumcheck_round_evaluations_sum.self_reduce();
            round.target_total_sum.self_reduce();
 
            // This bool is only needed for debugging
            verified = (first_sumcheck_round_evaluations_sum.get_value() == round.target_total_sum.get_value());
            // Ensure that the sum of the evaluations of the first Sumcheck Round Univariate is equal to the claimed
            // target total sum
            first_sumcheck_round_evaluations_sum.assert_equal(round.target_total_sum);
 
            // TODO(https://github.com/AztecProtocol/barretenberg/issues/1197)
            full_honk_purported_value.self_reduce();
 
        } else {
            // Ensure that the sum of the evaluations of the first Sumcheck Round Univariate is equal to the claimed
            // target total sum
            verified = (first_sumcheck_round_evaluations_sum == round.target_total_sum);
        }
 
        round_univariate_evaluations[virtual_log_n - 1][2] = full_honk_purported_value;
 

Definition at line 698 of file sumcheck.hpp.

Member Typedef Documentation

◆ ClaimedEvaluations

template<typename Flavor >

using bb::SumcheckVerifier< Flavor >::ClaimedEvaluations = typename Flavor::AllValues

Container type for the evaluations of Prover Polynomials \(P_1,\ldots,P_N\) at the challenge point \((u_0,\ldots, u_{d-1}) \).

Definition at line 708 of file sumcheck.hpp.

◆ ClaimedLibraEvaluations

template<typename Flavor >

using bb::SumcheckVerifier< Flavor >::ClaimedLibraEvaluations = typename std::vector<FF>

Definition at line 711 of file sumcheck.hpp.

◆ Commitment

template<typename Flavor >

using bb::SumcheckVerifier< Flavor >::Commitment = typename Flavor::Commitment

Definition at line 714 of file sumcheck.hpp.

◆ FF

template<typename Flavor >

using bb::SumcheckVerifier< Flavor >::FF = typename Flavor::FF

Definition at line 702 of file sumcheck.hpp.

◆ SubrelationSeparators

template<typename Flavor >

using bb::SumcheckVerifier< Flavor >::SubrelationSeparators = typename Flavor::SubrelationSeparators

Definition at line 713 of file sumcheck.hpp.

◆ Transcript

template<typename Flavor >

using bb::SumcheckVerifier< Flavor >::Transcript = typename Flavor::Transcript

Definition at line 712 of file sumcheck.hpp.

◆ Utils

template<typename Flavor >

using bb::SumcheckVerifier< Flavor >::Utils = bb::RelationUtils<Flavor>

Definition at line 701 of file sumcheck.hpp.

Constructor & Destructor Documentation

◆ SumcheckVerifier() [1/2]

template<typename Flavor >

bb::SumcheckVerifier< Flavor >::SumcheckVerifier	(	std::shared_ptr< Transcript >	transcript,
		SubrelationSeparators &	relation_separator,
		size_t	virtual_log_n,
		FF	target_sum = `0`
	)

inlineexplicit

Definition at line 745 of file sumcheck.hpp.

◆ SumcheckVerifier() [2/2]

template<typename Flavor >

bb::SumcheckVerifier< Flavor >::SumcheckVerifier	(	std::shared_ptr< Transcript >	transcript,
		const FF &	alpha,
		size_t	virtual_log_n,
		FF	target_sum = `0`
	)

inlineexplicit

Definition at line 754 of file sumcheck.hpp.

Member Function Documentation

◆ verify() [1/2]

template<typename Flavor >

SumcheckOutput< Flavor > bb::SumcheckVerifier< Flavor >::verify	(	const bb::RelationParameters< FF > &	relation_parameters,
		const std::vector< FF > &	gate_challenges
	)

inline

Sumcheck Verifier for ECCVM and ECCVMRecursive.

The verifier receives commitments to RoundUnivariates, along with their evaluations at 0 and 1. These evaluations will be proved as a part of Shplemini. The only check that the Verifier performs in this version is the comparison of the target sumcheck sum with the claimed evaluations of the first sumcheck round univariate at 0 and 1.

Note that the SumcheckOutput in this case contains a vector of commitments and a vector of arrays (of size 3) of evaluations at 0, 1, and a round challenge.

Parameters

relation_parameters
alpha
gate_challenges

Returns: SumcheckOutput<Flavor>

[Final Verification Step]

Definition at line 871 of file sumcheck.hpp.

◆ verify() [2/2]

template<typename Flavor >

SumcheckOutput< Flavor > bb::SumcheckVerifier< Flavor >::verify	(	const bb::RelationParameters< FF > &	relation_parameters,
		std::vector< FF > &	gate_challenges,
		const std::vector< FF > &	padding_indicator_array
	)

inline

Extract round univariate, check sum, generate challenge, compute next target sum..., repeat until final round, then use purported evaluations to generate purported full Honk relation value and check against final target sum.

If verification fails, returns std::nullopt, otherwise returns SumcheckOutput

Parameters

relation_parameters
transcript

[Final Verification Step]

Definition at line 771 of file sumcheck.hpp.

Member Data Documentation

◆ alphas

template<typename Flavor >

SubrelationSeparators bb::SumcheckVerifier< Flavor >::alphas

Definition at line 735 of file sumcheck.hpp.

◆ BATCHED_RELATION_PARTIAL_LENGTH

template<typename Flavor >

constexpr size_t bb::SumcheckVerifier< Flavor >::BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH

staticconstexpr

Maximum partial algebraic degree of the relation \(\tilde F = pow_{\beta} \cdot F \), i.e. MAX_PARTIAL_RELATION_LENGTH + 1.

Definition at line 720 of file sumcheck.hpp.

◆ correcting_factor

template<typename Flavor >

FF bb::SumcheckVerifier< Flavor >::correcting_factor

Definition at line 740 of file sumcheck.hpp.

◆ libra_challenge

template<typename Flavor >

FF bb::SumcheckVerifier< Flavor >::libra_challenge

Definition at line 737 of file sumcheck.hpp.

◆ libra_evaluation

template<typename Flavor >

FF bb::SumcheckVerifier< Flavor >::libra_evaluation { 0 }

Definition at line 736 of file sumcheck.hpp.

◆ libra_total_sum

template<typename Flavor >

FF bb::SumcheckVerifier< Flavor >::libra_total_sum

Definition at line 738 of file sumcheck.hpp.

◆ NUM_POLYNOMIALS

template<typename Flavor >

constexpr size_t bb::SumcheckVerifier< Flavor >::NUM_POLYNOMIALS = Flavor::NUM_ALL_ENTITIES

staticconstexpr

The number of Prover Polynomials \( P_1, \ldots, P_N \) specified by the Flavor.

Definition at line 725 of file sumcheck.hpp.

◆ round

template<typename Flavor >

SumcheckVerifierRound<Flavor> bb::SumcheckVerifier< Flavor >::round

Definition at line 728 of file sumcheck.hpp.

◆ round_univariate_commitments

template<typename Flavor >

std::vector<Commitment> bb::SumcheckVerifier< Flavor >::round_univariate_commitments = {}

Definition at line 742 of file sumcheck.hpp.

◆ round_univariate_evaluations

template<typename Flavor >

std::vector<std::array<FF, 3> > bb::SumcheckVerifier< Flavor >::round_univariate_evaluations = {}

Definition at line 743 of file sumcheck.hpp.

◆ transcript

template<typename Flavor >

std::shared_ptr<Transcript> bb::SumcheckVerifier< Flavor >::transcript

Definition at line 727 of file sumcheck.hpp.

◆ virtual_log_n

template<typename Flavor >

size_t bb::SumcheckVerifier< Flavor >::virtual_log_n

Definition at line 731 of file sumcheck.hpp.

The documentation for this class was generated from the following file:

src/barretenberg/sumcheck/sumcheck.hpp

Public Types

Public Member Functions

Public Attributes

Static Public Attributes

Detailed Description

Verifier's Data before Final Step

Final Verification Step

Member Typedef Documentation

◆ ClaimedEvaluations

◆ ClaimedLibraEvaluations

◆ Commitment

◆ FF

◆ SubrelationSeparators

◆ Transcript

◆ Utils

Constructor & Destructor Documentation

◆ SumcheckVerifier() [1/2]

◆ SumcheckVerifier() [2/2]

Member Function Documentation

◆ verify() [1/2]

◆ verify() [2/2]

Member Data Documentation

◆ alphas

◆ BATCHED_RELATION_PARTIAL_LENGTH

◆ correcting_factor

◆ libra_challenge

◆ libra_evaluation

◆ libra_total_sum

◆ NUM_POLYNOMIALS

◆ round

◆ round_univariate_commitments

◆ round_univariate_evaluations

◆ transcript

◆ virtual_log_n