Imlementation of the Sumcheck prover round. More...

#include <sumcheck_round.hpp>

Classes
struct	BlockOfContiguousRows
	Helper struct that describes a block of non-zero unskippable rows. More...

struct	ChunkStealer
	Shared chunk scheduler for dynamic work-stealing in the sumcheck prover's main loop. More...

Public Types
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 >

using	SumcheckRoundUnivariate = bb::Univariate< FF, BATCHED_RELATION_PARTIAL_LENGTH >

Public Member Functions
	SumcheckProverRound (size_t initial_round_size)

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
size_t	compute_effective_round_size (const ProverPolynomialsOrPartiallyEvaluatedMultivariates &multivariates) const
	Compute the effective round size by finding the maximum end_index() across witness polynomials.

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
void	extend_edges (ExtendedEdges &extended_edges, const ProverPolynomialsOrPartiallyEvaluatedMultivariates &multivariates, const size_t edge_idx)
	To compute the round univariate in Round \(i\), the prover first computes the values of Honk polynomials \( P_1,\ldots, P_N \) at the points of the form \( (u_0,\ldots, u_{i-1}, k, \vec \ell)\) for \( k=0,\ldots, D \), where \( D \) is defined as partial algebraic degree of the relation multiplied by pow-polynomial.

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
SumcheckRoundUnivariate	compute_univariate (ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials, const bb::RelationParameters< FF > &relation_parameters, const bb::GateSeparatorPolynomial< FF > &gate_separators, const SubrelationSeparators &alphas)
	Return the evaluations of the univariate round polynomials. Toggles between chunked computation (designed with the AVM in mind) and a version which intelligently allows from row-skipped functionality.

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
SumcheckRoundUnivariate	compute_univariate_avm (ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials, const bb::RelationParameters< FF > &relation_parameters, const bb::GateSeparatorPolynomial< FF > &gate_separators, const SubrelationSeparators &alphas)
	A version of `compute_univariate` that is better optimized for the AVM.

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
std::vector< BlockOfContiguousRows >	compute_contiguous_round_size (ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials)
	Compute the number of unskippable rows we must iterate over.

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)
	Return the evaluations of the univariate round polynomials \( \tilde{S}_{i} (X_{i}) \) at \( X_{i } = 0,\ldots, D \). Most likely, \( D \) is around \( 12 \). At the end, reset all univariate accumulators to be zero.

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates > requires UseRowDisablingPolynomial<Flavor>
SumcheckRoundUnivariate	compute_disabled_contribution (ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials, const bb::RelationParameters< FF > &relation_parameters, const bb::GateSeparatorPolynomial< FF > &gate_separators, const SubrelationSeparators &alphas, const RowDisablingPolynomial< FF > row_disabling_polynomial)
	Compute the disabled rows' contribution to the round univariate.

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
SumcheckRoundUnivariate	compute_virtual_contribution (ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials, const bb::RelationParameters< FF > &relation_parameters, const GateSeparatorPolynomial< FF > &gate_separator, const SubrelationSeparators &alphas)

void	accumulate_relation_univariates_public (SumcheckTupleOfTuplesOfUnivariates &univariate_accumulators, const auto &extended_edges, const bb::RelationParameters< FF > &relation_parameters, const FF &scaling_factor)

Static Public Member Functions
template<typename ExtendedUnivariate , typename ContainerOverSubrelations >
static ExtendedUnivariate	batch_over_relations (ContainerOverSubrelations &univariate_accumulators, const SubrelationSeparators &challenge, const bb::GateSeparatorPolynomial< FF > &gate_separators)
	Given a tuple of tuples of extended per-relation contributions, \( (t_0, t_1, \ldots, t_{\text{NUM_SUBRELATIONS}-1}) \) and a challenge \( \alpha \), scale them by the relation separator \(\alpha\), extend to the correct degree, and take the sum multiplying by \(pow_{\beta}\)-contributions.

template<typename ExtendedUnivariate , typename TupleOfTuplesOfUnivariates >
static void	extend_and_batch_univariates (const TupleOfTuplesOfUnivariates &tuple, ExtendedUnivariate &result, const bb::GateSeparatorPolynomial< FF > &gate_separators)
	Extend Univariates then sum them multiplying by the current \( pow_{\beta} \)-contributions.

static SumcheckRoundUnivariate	compute_libra_univariate (const ZKData &zk_sumcheck_data, size_t round_idx)
	Compute Libra round univariate expressed given by the formula.

Public Attributes
size_t	round_size
	In Round \(i = 0,\ldots, d-1\), equals \(2^{d-i}\).

size_t	excluded_head_size = Flavor::HasZK ? Flavor::TRACE_OFFSET : 0

SumcheckTupleOfTuplesOfUnivariates	univariate_accumulators

Static Public Attributes
static constexpr size_t	NUM_RELATIONS = Flavor::NUM_RELATIONS
	Number of batched sub-relations in \(F\) specified by Flavor.

static constexpr size_t	MAX_PARTIAL_RELATION_LENGTH = Flavor::MAX_PARTIAL_RELATION_LENGTH
	The total algebraic degree of the Sumcheck relation \( F \) as a polynomial in Prover Polynomials \(P_1,\ldots, P_N\).

static constexpr size_t	BATCHED_RELATION_PARTIAL_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH
	The total algebraic degree of the Sumcheck relation \( F \) as a polynomial in Prover Polynomials \(P_1,\ldots, P_N\) incremented by 1, i.e. it is equal MAX_PARTIAL_RELATION_LENGTH + 1.

static constexpr size_t	LIBRA_UNIVARIATES_LENGTH = Flavor::Curve::LIBRA_UNIVARIATES_LENGTH

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

Private Member Functions
void	accumulate_relation_univariates (SumcheckTupleOfTuplesOfUnivariates &univariate_accumulators, const auto &extended_edges, const bb::RelationParameters< FF > &relation_parameters, const FF &scaling_factor)
	In Round \( i \), for a given point \( \vec \ell \in \{0,1\}^{d-1 - i}\), calculate the contribution of each sub-relation to \( T^i(X_i) \).

Detailed Description

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

Imlementation of the Sumcheck prover round.

The evaluations of the round univariate \( \tilde{S}^i \) over the domain \(0,\ldots, D \) are obtained by the method compute univariate. The implementation consists of the following sub-methods:

Extend evaluations of linear univariate polynomials \( P_j(u_0,\ldots, u_{i-1}, X_i, \vec \ell) \) to the domain \(0,\ldots, D\).
Accumulate per-relation contributions of the extended polynomials to \( T^i(X_i)\)
Extend and batch the subrelation contibutions multiplying by the constants \(c_i\) and the evaluations of \( ( (1−X_i) + X_i\cdot \beta_i ) \).

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.

Definition at line 45 of file sumcheck_round.hpp.

Member Typedef Documentation

◆ ExtendedEdges

template<typename Flavor >

using bb::SumcheckProverRound< Flavor >::ExtendedEdges = std::conditional_t<Flavor::USE_SHORT_MONOMIALS, typename Flavor::template ProverUnivariates<2>, typename Flavor::ExtendedEdges>

Definition at line 53 of file sumcheck_round.hpp.

◆ FF

template<typename Flavor >

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

Definition at line 49 of file sumcheck_round.hpp.

◆ Relations

template<typename Flavor >

using bb::SumcheckProverRound< Flavor >::Relations = typename Flavor::Relations

Definition at line 50 of file sumcheck_round.hpp.

◆ SubrelationSeparators

template<typename Flavor >

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

Definition at line 52 of file sumcheck_round.hpp.

◆ SumcheckRoundUnivariate

template<typename Flavor >

using bb::SumcheckProverRound< Flavor >::SumcheckRoundUnivariate = bb::Univariate<FF, BATCHED_RELATION_PARTIAL_LENGTH>

Definition at line 84 of file sumcheck_round.hpp.

◆ SumcheckTupleOfTuplesOfUnivariates

template<typename Flavor >

using bb::SumcheckProverRound< Flavor >::SumcheckTupleOfTuplesOfUnivariates = decltype(create_sumcheck_tuple_of_tuples_of_univariates<Relations>())

Definition at line 51 of file sumcheck_round.hpp.

◆ Utils

template<typename Flavor >

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

private

Definition at line 46 of file sumcheck_round.hpp.

◆ ZKData

template<typename Flavor >

using bb::SumcheckProverRound< Flavor >::ZKData = ZKSumcheckData<Flavor>

Definition at line 56 of file sumcheck_round.hpp.

Constructor & Destructor Documentation

◆ SumcheckProverRound()

template<typename Flavor >

bb::SumcheckProverRound< Flavor >::SumcheckProverRound ( size_t initial_round_size )

inline

Definition at line 92 of file sumcheck_round.hpp.

Member Function Documentation

◆ accumulate_relation_univariates()

template<typename Flavor >

void bb::SumcheckProverRound< Flavor >::accumulate_relation_univariates	(	SumcheckTupleOfTuplesOfUnivariates &	univariate_accumulators,
		const auto &	extended_edges,
		const bb::RelationParameters< FF > &	relation_parameters,
		const FF &	scaling_factor
	)

inlineprivate

In Round \( i \), for a given point \( \vec \ell \in \{0,1\}^{d-1 - i}\), calculate the contribution of each sub-relation to \( T^i(X_i) \).

In Round \( i \), this method computes the univariate \( T^i(X_i) \) defined in this section. It is done as follows:

Outer loop: iterate through the "edge" points \( (0,\vec \ell) \) on the boolean hypercube \(\{0,1\}\times \{0,1\}^{d-1 - i}\), i.e. skipping every other point. On each iteration, apply extend edges". - Inner loop: iterate through the sub-relations, feeding each relation the "the group of edges", i.e. the evaluations \_form#1021. Each relation Flavor is endowed with \p accumulate method that computes its contribution to\iline 718 \_form#1022@_fakenl \ref extend_and_batch_univariates "Adding these univariates together", with appropriate scaling factors, produces required evaluations of \_form#1023. @param univariate_accumulators The container for per-thread-per-relation univariate contributions output by \ref accumulate_relation_univariates "accumulate relation univariates" for the previous "groups of edges". @param extended_edges Contains tuples of evaluations of\iline 724 \_form#1024@_fakenl, for \_form#1025, \_form#1026 and fixed \_form#1027. @param scaling_factor In Round \_form#656, for \_form#660 takes an element of \ref bb::GateSeparatorPolynomial< FF >::beta_products "vector of powers of challenges" at index \( 2^{i+1} *(\ell_{i+1} 2^{i+1} +\ldots + \ell_{d-1} 2^{d-1})\).
Returns
univariate_accumulators are updated with the contribution from the current group of edges. For each relation, a univariate of some degree is computed by accumulating the contributions of each group of edges.

Definition at line 732 of file sumcheck_round.hpp.

◆ accumulate_relation_univariates_public()

template<typename Flavor >

void bb::SumcheckProverRound< Flavor >::accumulate_relation_univariates_public	(	SumcheckTupleOfTuplesOfUnivariates &	univariate_accumulators,
		const auto &	extended_edges,
		const bb::RelationParameters< FF > &	relation_parameters,
		const FF &	scaling_factor
	)

inline

Definition at line 696 of file sumcheck_round.hpp.

◆ batch_over_relations()

template<typename Flavor >

template<typename ExtendedUnivariate , typename ContainerOverSubrelations >

static ExtendedUnivariate bb::SumcheckProverRound< Flavor >::batch_over_relations	(	ContainerOverSubrelations &	univariate_accumulators,
		const SubrelationSeparators &	challenge,
		const bb::GateSeparatorPolynomial< FF > &	gate_separators
	)

inlinestatic

Given a tuple of tuples of extended per-relation contributions, \( (t_0, t_1, \ldots, t_{\text{NUM_SUBRELATIONS}-1}) \) and a challenge \( \alpha \), scale them by the relation separator \(\alpha\), extend to the correct degree, and take the sum multiplying by \(pow_{\beta}\)-contributions.

This method receives as input the univariate accumulators computed by accumulate relation univariates after passing through the entire hypercube and applying add_nested_tuples method to join the threads. The accumulators are scaled using the method scaleunivariates", extended to the degree \_form#193 and summed with appropriate \_form#643-factors using \ref extend_and_batch_univariates "extend and batch univariates method" to return a vector \((\tilde{S}^i(0), \ldots, \tilde{S}^i(D))\).

Parameters

challenge	Challenge \(\alpha\).
gate_separators	Round \(pow_{\beta}\)-factor given by \( ( (1−u_i) + u_i\cdot \beta_i )\).

Definition at line 602 of file sumcheck_round.hpp.

◆ compute_contiguous_round_size()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

std::vector< BlockOfContiguousRows > bb::SumcheckProverRound< Flavor >::compute_contiguous_round_size ( ProverPolynomialsOrPartiallyEvaluatedMultivariates & polynomials )

inline

Compute the number of unskippable rows we must iterate over.

Some circuits have a circuit size much larger than the number of used rows (ECCVM, Translator). For relevant flavors, we have a skip_entire_row method that can be used to check whether to skip. This method iterates over the execution trace & computes blocks of contiguous unskippable rows.

Note: We assume that the number of blocks returned by this fn is small. i.e. the circuit does not have a large number of interleaved empty rows. If the circuit does have a lot of interleaved empty/non-empty rows, this function will be quite slow as the returned vector will be large.

Template Parameters

ProverPolynomialsOrPartiallyEvaluatedMultivariates

Parameters

polynomials

Returns: std::vector<BlockOfContiguousRows>

Definition at line 309 of file sumcheck_round.hpp.

◆ compute_disabled_contribution()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
requires UseRowDisablingPolynomial<Flavor>

SumcheckRoundUnivariate bb::SumcheckProverRound< Flavor >::compute_disabled_contribution	(	ProverPolynomialsOrPartiallyEvaluatedMultivariates &	polynomials,
		const bb::RelationParameters< FF > &	relation_parameters,
		const bb::GateSeparatorPolynomial< FF > &	gate_separators,
		const SubrelationSeparators &	alphas,
		const RowDisablingPolynomial< FF >	row_disabling_polynomial
	)

inline

Compute the disabled rows' contribution to the round univariate.

The main sumcheck loop excludes disabled head edge pairs. This method computes the relation evaluation at those positions directly from the (partially evaluated) polynomials, multiplied by the (1-L) row-disabling factor. Masking values are already in the polynomials.

Result is H_disabled * (1-L), to be ADDED to S_active. In round 0, (1-L) = 0, so this returns zero.

Definition at line 518 of file sumcheck_round.hpp.

◆ compute_effective_round_size()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

size_t bb::SumcheckProverRound< Flavor >::compute_effective_round_size ( const ProverPolynomialsOrPartiallyEvaluatedMultivariates & multivariates ) const

inline

Compute the effective round size by finding the maximum end_index() across witness polynomials.

Witness polynomials only contain meaningful data up to their end_index(), and we can avoid iterating over the zero region beyond that point. The disabled head rows are handled separately by compute_disabled_contribution, so we don't include them here.

Definition at line 108 of file sumcheck_round.hpp.

◆ compute_libra_univariate()

template<typename Flavor >

static SumcheckRoundUnivariate bb::SumcheckProverRound< Flavor >::compute_libra_univariate	(	const ZKData &	zk_sumcheck_data,
		size_t	round_idx
	)

inlinestatic

Compute Libra round univariate expressed given by the formula.

\begin{align} \texttt{libra_round_univariate}_i(k) = \rho \cdot 2^{d-1-i} \left(\sum_{j = 0}^{i-1} g_j(u_{j}) + g_{i,k}+ \sum_{j=i+1}^{d-1}\left(g_{j,0}+g_{j,1}\right)\right) = \texttt{libra_univariates}_{i}(k) + \texttt{libra_running_sum} \end{align}

.

Parameters

zk_sumcheck_data
round_idx

Definition at line 677 of file sumcheck_round.hpp.

◆ compute_univariate()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

SumcheckRoundUnivariate bb::SumcheckProverRound< Flavor >::compute_univariate	(	ProverPolynomialsOrPartiallyEvaluatedMultivariates &	polynomials,
		const bb::RelationParameters< FF > &	relation_parameters,
		const bb::GateSeparatorPolynomial< FF > &	gate_separators,
		const SubrelationSeparators &	alphas
	)

inline

Return the evaluations of the univariate round polynomials. Toggles between chunked computation (designed with the AVM in mind) and a version which intelligently allows from row-skipped functionality.

Definition at line 182 of file sumcheck_round.hpp.

◆ compute_univariate_avm()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

SumcheckRoundUnivariate bb::SumcheckProverRound< Flavor >::compute_univariate_avm	(	ProverPolynomialsOrPartiallyEvaluatedMultivariates &	polynomials,
		const bb::RelationParameters< FF > &	relation_parameters,
		const bb::GateSeparatorPolynomial< FF > &	gate_separators,
		const SubrelationSeparators &	alphas
	)

inline

A version of compute_univariate that is better optimized for the AVM.

Main changes are:

Use a different threading strategy ("chunking").
Use lazy extension of edges.

Definition at line 241 of file sumcheck_round.hpp.

◆ compute_univariate_with_row_skipping()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

SumcheckRoundUnivariate bb::SumcheckProverRound< Flavor >::compute_univariate_with_row_skipping	(	ProverPolynomialsOrPartiallyEvaluatedMultivariates &	polynomials,
		const bb::RelationParameters< FF > &	relation_parameters,
		const bb::GateSeparatorPolynomial< FF > &	gate_separators,
		const SubrelationSeparators	alphas
	)

inline

Return the evaluations of the univariate round polynomials \( \tilde{S}_{i} (X_{i}) \) at \( X_{i } = 0,\ldots, D \). Most likely, \( D \) is around \( 12 \). At the end, reset all univariate accumulators to be zero.

First, the vector of pow challenges is computed. Then, multi-threading is being set up. Compute the evaluations of partially evaluated Honk polynomials \( P_j\left(u_0,\ldots, u_{i-1}, X_{i} , \vec \ell \right) \) for \( X_{i} = 2, \ldots, D \) using extend edges method. This method invokes more general extend_to method that in this case reduces to a very simple expression

\begin{align} P_j\left( u_0,\ldots, u_{i-1}, k, \vec \ell \right) = P_j\left( u_0,\ldots, u_{i-1}, k-1, \vec \ell \right) + P_j\left( u_0,\ldots, u_{i-1}, 1, \vec \ell \right) - P_j\left( u_0,\ldots, u_{i-1}, 0, \vec \ell \right) \end{align}

, where \( k=2,\ldots, D \). For a given \( \vec \ell \in \{0,1\}^{d -1 -i} \), we invoke accumulate relation univariates to compute the contributions of \( P_1\left(u_0,\ldots, u_{i-1}, k, \vec \ell \right) \), ..., \( P_N\left(u_0,\ldots, u_{i-1}, k, \vec \ell \right) \) to every sub-relation. Finally, the accumulators for individual relations' contributions are summed with appropriate factors using method extend and batch univariates.

Definition at line 401 of file sumcheck_round.hpp.

◆ compute_virtual_contribution()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

SumcheckRoundUnivariate bb::SumcheckProverRound< Flavor >::compute_virtual_contribution	(	ProverPolynomialsOrPartiallyEvaluatedMultivariates &	polynomials,
		const bb::RelationParameters< FF > &	relation_parameters,
		const GateSeparatorPolynomial< FF > &	gate_separator,
		const SubrelationSeparators &	alphas
	)

inline

Definition at line 549 of file sumcheck_round.hpp.

◆ extend_and_batch_univariates()

template<typename Flavor >

template<typename ExtendedUnivariate , typename TupleOfTuplesOfUnivariates >

static void bb::SumcheckProverRound< Flavor >::extend_and_batch_univariates	(	const TupleOfTuplesOfUnivariates &	tuple,
		ExtendedUnivariate &	result,
		const bb::GateSeparatorPolynomial< FF > &	gate_separators
	)

inlinestatic

Extend Univariates then sum them multiplying by the current \( pow_{\beta} \)-contributions.

Since the sub-relations comprising full Honk relation are of different degrees, the computation of the evaluations of round univariate \( \tilde{S}_{i}(X_{i}) \) at points \( X_{i} = 0,\ldots, D \) requires to extend evaluations of individual relations to the domain \( 0,\ldots, D\). Moreover, linearly independent sub-relations, i.e. whose validity is being checked at every point of the hypercube, are multiplied by the constant \( c_i = pow_\beta(u_0,\ldots, u_{i-1}) \) and the current \(pow_{\beta}\)-factor \( ( (1−X_i) + X_i\cdot \beta_i ) \vert_{X_i = k} \) for \( k = 0,\ldots, D\).

Template Parameters

extended_size Size after extension

Parameters

tuple	A tuple of tuples of Univariates
result	Round univariate \( \tilde{S}^i\) represented by its evaluations over \( \{0,\ldots, D\} \).
gate_separators	Round \(pow_{\beta}\)-factor \( ( (1−X_i) + X_i\cdot \beta_i )\).

Definition at line 630 of file sumcheck_round.hpp.

◆ extend_edges()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

void bb::SumcheckProverRound< Flavor >::extend_edges	(	ExtendedEdges &	extended_edges,
		const ProverPolynomialsOrPartiallyEvaluatedMultivariates &	multivariates,
		const size_t	edge_idx
	)

inline

To compute the round univariate in Round \(i\), the prover first computes the values of Honk polynomials \( P_1,\ldots, P_N \) at the points of the form \( (u_0,\ldots, u_{i-1}, k, \vec \ell)\) for \( k=0,\ldots, D \), where \( D \) is defined as partial algebraic degree of the relation multiplied by pow-polynomial.

In the first round, extend edges method receives required evaluations from the prover polynomials. In the subsequent rounds, the method receives partially evaluated polynomials.

In both cases, in Round \( i \), the method receives \((0, \vec \ell) \in \{0,1\}\times\{0,1\}^{d-1 - i} \), accesses the evaluations \( P_j\left(u_0,\ldots, u_{i-1}, 0, \vec \ell\right) \) and \( P_j\left(u_0,\ldots, u_{i-1}, 1, \vec \ell\right) \) of \( N \) linear polynomials \( P_j\left(u_0,\ldots, u_{i-1}, X_{i}, \vec \ell \right) \) that are already available either from the prover's input in the first round, or from the multivariates table. Using general method extend_to, the evaluations of these polynomials are extended from the domain \( \{0,1\} \) to the domain \( \{0,\ldots, D\} \) required for the computation of the round univariate. In the case when witness polynomials are masked (ZK Flavors), this method has to distinguish between witness and non-witness polynomials. The witness univariates obtained from witness multilinears are corrected by a masking quadratic term extended to the same length MAX_PARTIAL_RELATION_LENGTH. Should only be called externally with relation_idx equal to 0. In practice, #multivariates is either ProverPolynomials or PartiallyEvaluatedMultivariates.

Parameters

edge_idx	A point \((0, \vec \ell) \in \{0,1\}^{d-i} \), where \( i\in \{0,\ldots, d-1\}\) is Round number.
extended_edges	Container for the evaluations of \(P_j(u_0,\ldots, u_{i-1}, k, \vec \ell) \) for \(k=0,\ldots, D\) and \(j=1,\ldots,N\).

Definition at line 158 of file sumcheck_round.hpp.

Member Data Documentation

◆ BATCHED_RELATION_PARTIAL_LENGTH

template<typename Flavor >

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

staticconstexpr

The total algebraic degree of the Sumcheck relation \( F \) as a polynomial in Prover Polynomials \(P_1,\ldots, P_N\) incremented by 1, i.e. it is equal MAX_PARTIAL_RELATION_LENGTH + 1.

Definition at line 83 of file sumcheck_round.hpp.

◆ excluded_head_size

template<typename Flavor >

size_t bb::SumcheckProverRound< Flavor >::excluded_head_size = Flavor::HasZK ? Flavor::TRACE_OFFSET : 0

Definition at line 66 of file sumcheck_round.hpp.

◆ LIBRA_UNIVARIATES_LENGTH

template<typename Flavor >

constexpr size_t bb::SumcheckProverRound< Flavor >::LIBRA_UNIVARIATES_LENGTH = Flavor::Curve::LIBRA_UNIVARIATES_LENGTH

staticconstexpr

Definition at line 89 of file sumcheck_round.hpp.

◆ MAX_PARTIAL_RELATION_LENGTH

template<typename Flavor >

constexpr size_t bb::SumcheckProverRound< Flavor >::MAX_PARTIAL_RELATION_LENGTH = Flavor::MAX_PARTIAL_RELATION_LENGTH

staticconstexpr

The total algebraic degree of the Sumcheck relation \( F \) as a polynomial in Prover Polynomials \(P_1,\ldots, P_N\).

Definition at line 77 of file sumcheck_round.hpp.

◆ NUM_RELATIONS

template<typename Flavor >

constexpr size_t bb::SumcheckProverRound< Flavor >::NUM_RELATIONS = Flavor::NUM_RELATIONS

staticconstexpr

Number of batched sub-relations in \(F\) specified by Flavor.

Definition at line 72 of file sumcheck_round.hpp.

◆ round_size

template<typename Flavor >

size_t bb::SumcheckProverRound< Flavor >::round_size

In Round \(i = 0,\ldots, d-1\), equals \(2^{d-i}\).

Definition at line 60 of file sumcheck_round.hpp.

◆ univariate_accumulators

template<typename Flavor >

SumcheckTupleOfTuplesOfUnivariates bb::SumcheckProverRound< Flavor >::univariate_accumulators

Definition at line 86 of file sumcheck_round.hpp.

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

src/barretenberg/sumcheck/sumcheck_round.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Private Types

Private Member Functions

Detailed Description

Member Typedef Documentation

◆ ExtendedEdges

◆ FF

◆ Relations

◆ SubrelationSeparators

◆ SumcheckRoundUnivariate

◆ SumcheckTupleOfTuplesOfUnivariates

◆ Utils

◆ ZKData

Constructor & Destructor Documentation

◆ SumcheckProverRound()

Member Function Documentation

◆ accumulate_relation_univariates()

◆ accumulate_relation_univariates_public()

◆ batch_over_relations()

◆ compute_contiguous_round_size()

◆ compute_disabled_contribution()

◆ compute_effective_round_size()

◆ compute_libra_univariate()

◆ compute_univariate()

◆ compute_univariate_avm()

◆ compute_univariate_with_row_skipping()

◆ compute_virtual_contribution()

◆ extend_and_batch_univariates()

◆ extend_edges()

Member Data Documentation

◆ BATCHED_RELATION_PARTIAL_LENGTH

◆ excluded_head_size

◆ LIBRA_UNIVARIATES_LENGTH

◆ MAX_PARTIAL_RELATION_LENGTH

◆ NUM_RELATIONS

◆ round_size

◆ univariate_accumulators