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 = std::array< FF, Flavor::NUM_SUBRELATIONS - 1 >

using	Commitment = typename Flavor::Commitment

Public Member Functions
	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, const std::vector< FF > &gate_challenges, const std::vector< FF > &padding_indicator_array)
	The Sumcheck verification method. First it extracts round univariate, checks sum (the sumcheck univariate consistency check), 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.

Public Attributes
std::shared_ptr< Transcript >	transcript

SumcheckVerifierRound< Flavor >	round

size_t	virtual_log_n

SubrelationSeparators	alphas

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 ClaimedEvaluations 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}

Definition at line 719 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 729 of file sumcheck.hpp.

◆ ClaimedLibraEvaluations

template<typename Flavor >

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

Definition at line 732 of file sumcheck.hpp.

◆ Commitment

template<typename Flavor >

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

Definition at line 735 of file sumcheck.hpp.

◆ FF

template<typename Flavor >

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

Definition at line 723 of file sumcheck.hpp.

◆ SubrelationSeparators

template<typename Flavor >

using bb::SumcheckVerifier< Flavor >::SubrelationSeparators = std::array<FF, Flavor::NUM_SUBRELATIONS - 1>

Definition at line 734 of file sumcheck.hpp.

◆ Transcript

template<typename Flavor >

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

Definition at line 733 of file sumcheck.hpp.

◆ Utils

template<typename Flavor >

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

Definition at line 722 of file sumcheck.hpp.

Constructor & Destructor Documentation

◆ SumcheckVerifier()

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 758 of file sumcheck.hpp.

Member Function Documentation

◆ verify()

template<typename Flavor >

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

inline

The Sumcheck verification method. First it extracts round univariate, checks sum (the sumcheck univariate consistency check), 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
gate_challenges
padding_indicator	Optional padding indicator (only used for non-Grumpkin flavors)

Returns: SumcheckOutput

[Final Verification Step]

Definition at line 777 of file sumcheck.hpp.

Member Data Documentation

◆ alphas

template<typename Flavor >

SubrelationSeparators bb::SumcheckVerifier< Flavor >::alphas

Definition at line 756 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 741 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 746 of file sumcheck.hpp.

◆ round

template<typename Flavor >

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

Definition at line 749 of file sumcheck.hpp.

◆ transcript

template<typename Flavor >

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

Definition at line 748 of file sumcheck.hpp.

◆ virtual_log_n

template<typename Flavor >

size_t bb::SumcheckVerifier< Flavor >::virtual_log_n

Definition at line 752 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()

Member Function Documentation

◆ verify()

Member Data Documentation

◆ alphas

◆ BATCHED_RELATION_PARTIAL_LENGTH

◆ NUM_POLYNOMIALS

◆ round

◆ transcript

◆ virtual_log_n