Imlementation of the Sumcheck prover round. More...

#include <sumcheck_round.hpp>

Classes
struct	ContiguousEdgeChunks

struct	EdgeRange

class	LazyExtendedEdges
	Lazy edge container for USE_SHORT_MONOMIALS flavors, generic over the lane element type. More...

struct	ListedEdgeChunks

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 >

template<typename Element >
using	RelationTupleFor = typename Flavor::template Relations_< Element >

template<typename Element >
using	AccumulatorsFor = decltype(create_sumcheck_tuple_of_tuples_of_univariates< RelationTupleFor< Element > >())

Public Member Functions
	SumcheckProverRound (size_t initial_round_size)

void	advance_round ()
	Advance to the next regular sumcheck round: halve the active hypercube size and increment the round index.

bool	is_virtual_round () const
	A virtual (zero-extension) round is any round at or beyond the multivariate_d regular rounds. Used to enforce that compute_virtual_contribution only runs after all regular rounds have completed.

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 Element = void, 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 round univariate \( \tilde{S}_{i}(X_{i}) \) at \( X_i = 0,\ldots,D \).

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
auto	make_edge_chunks (ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials)

template<typename Accumulators , typename Edges , typename Multivariates , typename Element >
void	accumulate_edge (Accumulators &accumulator, Edges &edge_container, const Multivariates &polynomials, const bb::RelationParameters< Element > &params, const bb::GateSeparatorPolynomial< FF > &gate_separators, const size_t edge_idx)

template<typename Element , typename EdgeChunks , typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
void	accumulate_edge_chunks (EdgeChunks &chunks, ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials, const bb::RelationParameters< FF > &relation_parameters, const bb::GateSeparatorPolynomial< FF > &gate_separators)

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
std::vector< EdgeRange >	compute_row_skip_edge_ranges (ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials, const size_t effective_round_size) const

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
std::vector< EdgeRange >	compute_edge_ranges (ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials)
	Compute the edge ranges the main sumcheck loop must visit.

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates > requires UseRowDisablingPolynomial<Flavor>
SumcheckRoundUnivariate	compute_offset_area_contribution (ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials, const bb::RelationParameters< FF > &relation_parameters, const bb::GateSeparatorPolynomial< FF > &gate_separators, const SubrelationSeparators &alphas, const RowDisablingPolynomial< FF > row_disabling_polynomial)
	Contribution to the round univariate from the offset-area head rows (rows 0 .. `TRACE_OFFSET - 1`), which are excluded from the main sumcheck loop.

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
SumcheckRoundUnivariate	compute_virtual_contribution (ProverPolynomialsOrPartiallyEvaluatedMultivariates &polynomials, const bb::RelationParameters< FF > &relation_parameters, const GateSeparatorPolynomial< FF > &gate_separator, const SubrelationSeparators &alphas, const RowDisablingPolynomial< FF > *row_disabling_polynomial=nullptr)
	Virtual (zero-extension) round univariate contribution.

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 ProverPolynomialsOrPartiallyEvaluatedMultivariates >
static 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 Element = FF, typename Multivariates >
static auto	make_extended_edges (const Multivariates &multivariates)

template<typename Edges , typename Multivariates >
static void	load_edge (Edges &edges, const Multivariates &multivariates, const size_t edge_idx)

template<typename Element >
static Element	element_scaling (const bb::GateSeparatorPolynomial< FF > &gate_separators, const size_t edge_idx)

template<typename Element >
static void	reduce_accumulator (SumcheckTupleOfTuplesOfUnivariates &destination, const AccumulatorsFor< Element > &source)

static size_t	chunk_count (const size_t span, const size_t rows_per_chunk)

template<typename GroupFn , typename PairFn >
static void	for_each_edge_group (const size_t begin, const size_t end, const size_t group_stride, GroupFn on_full_group, PairFn on_leftover_pair)

static size_t	round_up_to_even (const size_t value)

static void	append_edge_range (std::vector< EdgeRange > &ranges, const size_t start, const size_t end)

static void	merge_edge_ranges (std::vector< EdgeRange > &ranges)

template<typename ExtendedUnivariate , typename ContainerOverSubrelations >
static ExtendedUnivariate	batch_over_relations (ContainerOverSubrelations &univariate_accumulators, const SubrelationSeparators &challenge, const bb::GateSeparatorPolynomial< FF > &gate_separators, const RowDisablingPolynomial< FF > *row_disabling_polynomial=nullptr)
	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, const RowDisablingPolynomial< FF > *row_disabling_polynomial=nullptr)
	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	excluded_head_size = Flavor::HasZK ? Flavor::TRACE_OFFSET : 0

SumcheckTupleOfTuplesOfUnivariates	univariate_accumulators

Static Public Attributes
static constexpr bool	USE_LAZY_SHORT_EDGES = HasLazyShortEdges<Flavor>

static constexpr bool	USE_LAZY_EDGES = isAvmFlavor<Flavor> \|\| USE_LAZY_SHORT_EDGES

static constexpr size_t	ROWS_PER_CHUNK

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

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
static constexpr bool	HAS_STATIC_ROW_SKIP_MANIFEST

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
static constexpr bool	CAN_SKIP_ROWS

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
static constexpr bool	USES_ROW_MANIFEST

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

Private Member Functions
template<typename RelationTuple = Relations, typename Accumulators , typename Edges , typename Element >
void	accumulate_relation_univariates (Accumulators &univariate_accumulators, const Edges &extended_edges, const bb::RelationParameters< Element > &relation_parameters, const Element &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) \).

Private Attributes
size_t	round_size
	In regular round i = 0,...,multivariate_d-1, equals 2^{multivariate_d - i}; halved once per regular round via advance_round().

size_t	multivariate_d

size_t	round_index = 0

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 69 of file sumcheck_round.hpp.

Member Typedef Documentation

◆ AccumulatorsFor

template<typename Flavor >

template<typename Element >

using bb::SumcheckProverRound< Flavor >::AccumulatorsFor = decltype(create_sumcheck_tuple_of_tuples_of_univariates<RelationTupleFor<Element> >())

Definition at line 353 of file sumcheck_round.hpp.

◆ 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 77 of file sumcheck_round.hpp.

◆ FF

template<typename Flavor >

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

Definition at line 73 of file sumcheck_round.hpp.

◆ Relations

template<typename Flavor >

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

Definition at line 74 of file sumcheck_round.hpp.

◆ RelationTupleFor

template<typename Flavor >

template<typename Element >

using bb::SumcheckProverRound< Flavor >::RelationTupleFor = typename Flavor::template Relations_<Element>

Definition at line 347 of file sumcheck_round.hpp.

◆ SubrelationSeparators

template<typename Flavor >

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

Definition at line 76 of file sumcheck_round.hpp.

◆ SumcheckRoundUnivariate

template<typename Flavor >

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

Definition at line 119 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 75 of file sumcheck_round.hpp.

◆ Utils

template<typename Flavor >

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

private

Definition at line 70 of file sumcheck_round.hpp.

◆ ZKData

template<typename Flavor >

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

Definition at line 95 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 127 of file sumcheck_round.hpp.

Member Function Documentation

◆ accumulate_edge()

template<typename Flavor >

template<typename Accumulators , typename Edges , typename Multivariates , typename Element >

void bb::SumcheckProverRound< Flavor >::accumulate_edge	(	Accumulators &	accumulator,
		Edges &	edge_container,
		const Multivariates &	polynomials,
		const bb::RelationParameters< Element > &	params,
		const bb::GateSeparatorPolynomial< FF > &	gate_separators,
		const size_t	edge_idx
	)

inline

Definition at line 553 of file sumcheck_round.hpp.

◆ accumulate_edge_chunks()

template<typename Flavor >

template<typename Element , typename EdgeChunks , typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

void bb::SumcheckProverRound< Flavor >::accumulate_edge_chunks	(	EdgeChunks &	chunks,
		ProverPolynomialsOrPartiallyEvaluatedMultivariates &	polynomials,
		const bb::RelationParameters< FF > &	relation_parameters,
		const bb::GateSeparatorPolynomial< FF > &	gate_separators
	)

inline

Definition at line 571 of file sumcheck_round.hpp.

◆ accumulate_relation_univariates()

template<typename Flavor >

template<typename RelationTuple = Relations, typename Accumulators , typename Edges , typename Element >

void bb::SumcheckProverRound< Flavor >::accumulate_relation_univariates	(	Accumulators &	univariate_accumulators,
		const Edges &	extended_edges,
		const bb::RelationParameters< Element > &	relation_parameters,
		const Element &	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#647. Each relation Flavor is endowed with \p accumulate method that computes its contribution to\iline 1064 \_form#648@_fakenl \ref extend_and_batch_univariates "Adding these univariates together", with appropriate scaling factors, produces required evaluations of \_form#649. @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 1070 \_form#650@_fakenl, for \_form#651, \_form#652 and fixed \_form#653. @param scaling_factor In Round \_form#174, for \_form#654 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 1079 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 1042 of file sumcheck_round.hpp.

◆ advance_round()

template<typename Flavor >

void bb::SumcheckProverRound< Flavor >::advance_round ( )

inline

Advance to the next regular sumcheck round: halve the active hypercube size and increment the round index.

Called exactly once per regular round. After the multivariate_d regular rounds, round_index equals multivariate_d, so the remaining zero-extension (virtual) rounds satisfy is_virtual_round().

Definition at line 143 of file sumcheck_round.hpp.

◆ append_edge_range()

template<typename Flavor >

static void bb::SumcheckProverRound< Flavor >::append_edge_range	(	std::vector< EdgeRange > &	ranges,
		const size_t	start,
		const size_t	end
	)

inlinestatic

Definition at line 639 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,
		const RowDisablingPolynomial< FF > *	row_disabling_polynomial = `nullptr`
	)

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#202 and summed with appropriate \_form#318-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 887 of file sumcheck_round.hpp.

◆ chunk_count()

template<typename Flavor >

static size_t bb::SumcheckProverRound< Flavor >::chunk_count	(	const size_t	span,
		const size_t	rows_per_chunk
	)

inlinestatic

Definition at line 429 of file sumcheck_round.hpp.

◆ compute_edge_ranges()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

std::vector< EdgeRange > bb::SumcheckProverRound< Flavor >::compute_edge_ranges ( ProverPolynomialsOrPartiallyEvaluatedMultivariates & polynomials )

inline

Compute the edge ranges the main sumcheck loop must visit.

Some circuits have a circuit size much larger than the number of used rows (ECCVM, Translator). Static row-manifest flavors provide the relation-active edge ranges directly; row-skippable flavors expose a skip_entire_row predicate and this method scans the trace to compute contiguous live edge ranges.

Template Parameters

ProverPolynomialsOrPartiallyEvaluatedMultivariates

Parameters

polynomials

Returns: std::vector<EdgeRange>

Definition at line 722 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(), so we cap per-round iteration there and skip the trailing zero region. The disabled head rows are handled separately by compute_offset_area_contribution, so they are not included here.

INVARIANT: capping at the maximum witness end_index (rather than the full round_size) is only sound while the following hold:

Every subrelation term carries at least one witness factor, so on any row where all witnesses are zero (i.e. beyond the witness support) every relation contribution is zero.
The support of the precomputed/selector polynomials is contained in the witness support, so no relation becomes active on a row past the max witness end_index.
end_index() upper-bounds a polynomial's non-zero support A relation term with no witness factor, or a precomputed column whose support exceeds the witnesses, would make this cap drop non-zero rows.

Definition at line 172 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 1021 of file sumcheck_round.hpp.

◆ compute_offset_area_contribution()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >
requires UseRowDisablingPolynomial<Flavor>

SumcheckRoundUnivariate bb::SumcheckProverRound< Flavor >::compute_offset_area_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

Contribution to the round univariate from the offset-area head rows (rows 0 .. TRACE_OFFSET - 1), which are excluded from the main sumcheck loop.

Let L = L_0 + L_1 + L_2 + L_3 be the indicator of the offset area. The full Honk relation on the hypercube is

\[ H(x) = (1 - L)(x) \cdot \sum_{R \in \text{main}} H_R(x) + L(x) \cdot \sum_{R \in \text{offset-only}} H_R(x), \]

so each relation's head-row contribution carries its own row-disabling factor:

main-domain relations (default): factor (1 - L),
offset-only relations (IsOffsetOnlyRelation): factor L.

At round 0 the head-row values of (1 - L) vanish while those of L equal 1, so the round univariate receives offset-only contributions there and no main-domain contribution. At later rounds both factors are nontrivial linear univariates tracked by RowDisablingPolynomial.

When the flavor lists no offset-only relation, the per-relation dispatch reduces to multiplying the whole head-edge accumulation by (1 - L).

Definition at line 811 of file sumcheck_round.hpp.

◆ compute_row_skip_edge_ranges()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

std::vector< EdgeRange > bb::SumcheckProverRound< Flavor >::compute_row_skip_edge_ranges	(	ProverPolynomialsOrPartiallyEvaluatedMultivariates &	polynomials,
		const size_t	effective_round_size
	)		const

inline

Definition at line 680 of file sumcheck_round.hpp.

◆ compute_univariate()

template<typename Flavor >

template<typename Element = void, 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 round univariate \( \tilde{S}_{i}(X_{i}) \) at \( X_i = 0,\ldots,D \).

Work is split into fixed-size chunks handed to threads by a work-stealing scheduler, which balances the per-row cost variance that selector-gated relation skipping introduces. make_edge_chunks selects, at compile time, which edges the round visits and the scheduler that covers them – the canonical taxonomy for the rest of this file:

Row-skipping flavors (ECCVM/Translator): only the live edge ranges from compute_edge_ranges, scheduled by a ListedEdgeChunks manifest.
Dense flavors (AVM/Ultra/Mega/MultilinearBatching): the single contiguous active range, scheduled by ContiguousEdgeChunks. Per-relation accumulators are then batched into the round univariate (unmasked; masking happens later in sumcheck). See accumulate_edge_chunks for the per-edge accumulation and batch_over_relations for the batching.

Definition at line 393 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,
		const RowDisablingPolynomial< FF > *	row_disabling_polynomial = `nullptr`
	)

inline

Virtual (zero-extension) round univariate contribution.

Definition at line 836 of file sumcheck_round.hpp.

◆ element_scaling()

template<typename Flavor >

template<typename Element >

static Element bb::SumcheckProverRound< Flavor >::element_scaling	(	const bb::GateSeparatorPolynomial< FF > &	gate_separators,
		const size_t	edge_idx
	)

inlinestatic

Definition at line 337 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,
		const RowDisablingPolynomial< FF > *	row_disabling_polynomial = `nullptr`
	)

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\).

Each relation's per-relation sum is then scaled by a row-disabling factor Λ_R: (1 - L^{(i)})(X) for main-domain relations and L^{(i)}(X) for offset-only relations. When row_disabling_polynomial == nullptr the factors default to the constants (1, 0), so main relations pass through unscaled and offset-only relations collapse to zero.

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 )\).
row_disabling_polynomial	Optional; when non-null, its `eval_at_0/1` supply `L^{(i)}` for per-relation `L` / `(1 - L)` scaling.

Definition at line 924 of file sumcheck_round.hpp.

◆ extend_edges()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

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

inlinestatic

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. 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 219 of file sumcheck_round.hpp.

◆ for_each_edge_group()

template<typename Flavor >

template<typename GroupFn , typename PairFn >

static void bb::SumcheckProverRound< Flavor >::for_each_edge_group	(	const size_t	begin,
		const size_t	end,
		const size_t	group_stride,
		GroupFn	on_full_group,
		PairFn	on_leftover_pair
	)

inlinestatic

Definition at line 535 of file sumcheck_round.hpp.

◆ is_virtual_round()

template<typename Flavor >

bool bb::SumcheckProverRound< Flavor >::is_virtual_round ( ) const

inline

A virtual (zero-extension) round is any round at or beyond the multivariate_d regular rounds. Used to enforce that compute_virtual_contribution only runs after all regular rounds have completed.

Definition at line 153 of file sumcheck_round.hpp.

◆ load_edge()

template<typename Flavor >

template<typename Edges , typename Multivariates >

static void bb::SumcheckProverRound< Flavor >::load_edge	(	Edges &	edges,
		const Multivariates &	multivariates,
		const size_t	edge_idx
	)

inlinestatic

Definition at line 322 of file sumcheck_round.hpp.

◆ make_edge_chunks()

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

auto bb::SumcheckProverRound< Flavor >::make_edge_chunks ( ProverPolynomialsOrPartiallyEvaluatedMultivariates & polynomials )

inline

Definition at line 512 of file sumcheck_round.hpp.

◆ make_extended_edges()

template<typename Flavor >

template<typename Element = FF, typename Multivariates >

static auto bb::SumcheckProverRound< Flavor >::make_extended_edges ( const Multivariates & multivariates )

inlinestatic

Definition at line 307 of file sumcheck_round.hpp.

◆ merge_edge_ranges()

template<typename Flavor >

static void bb::SumcheckProverRound< Flavor >::merge_edge_ranges ( std::vector< EdgeRange > & ranges )

inlinestatic

Definition at line 655 of file sumcheck_round.hpp.

◆ reduce_accumulator()

template<typename Flavor >

template<typename Element >

static void bb::SumcheckProverRound< Flavor >::reduce_accumulator	(	SumcheckTupleOfTuplesOfUnivariates &	destination,
		const AccumulatorsFor< Element > &	source
	)

inlinestatic

Definition at line 360 of file sumcheck_round.hpp.

◆ round_up_to_even()

template<typename Flavor >

static size_t bb::SumcheckProverRound< Flavor >::round_up_to_even ( const size_t value )

inlinestatic

Definition at line 637 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 118 of file sumcheck_round.hpp.

◆ CAN_SKIP_ROWS

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

constexpr bool bb::SumcheckProverRound< Flavor >::CAN_SKIP_ROWS

staticconstexpr

Initial value:

=

isRowSkippable<Flavor, ProverPolynomialsOrPartiallyEvaluatedMultivariates&, size_t>

bb::isRowSkippable

Check if the flavor has a static skip method to determine if accumulation of all relations can be ski...

Definition relation_types.hpp:98

Definition at line 627 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 101 of file sumcheck_round.hpp.

◆ HAS_STATIC_ROW_SKIP_MANIFEST

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

constexpr bool bb::SumcheckProverRound< Flavor >::HAS_STATIC_ROW_SKIP_MANIFEST

staticconstexpr

Initial value:

=
        IsAnyOf<Flavor, ECCVMFlavor, ECCVMShortMonomialFlavor, ECCVMRecursiveFlavor> &&
        requires(const ProverPolynomialsOrPartiallyEvaluatedMultivariates& polynomials) {
            Flavor::row_skip_active_prefix_end(polynomials);
        }

Definition at line 618 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 124 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 112 of file sumcheck_round.hpp.

◆ multivariate_d

template<typename Flavor >

size_t bb::SumcheckProverRound< Flavor >::multivariate_d

private

Definition at line 1114 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 107 of file sumcheck_round.hpp.

◆ round_index

template<typename Flavor >

size_t bb::SumcheckProverRound< Flavor >::round_index = 0

private

Definition at line 1116 of file sumcheck_round.hpp.

◆ round_size

template<typename Flavor >

size_t bb::SumcheckProverRound< Flavor >::round_size

private

In regular round i = 0,...,multivariate_d-1, equals 2^{multivariate_d - i}; halved once per regular round via advance_round().

Definition at line 1112 of file sumcheck_round.hpp.

◆ ROWS_PER_CHUNK

template<typename Flavor >

constexpr size_t bb::SumcheckProverRound< Flavor >::ROWS_PER_CHUNK

staticconstexpr

Initial value:

= isAvmFlavor<Flavor> ? 16
                                             : (SupportsSimdSumcheck<Flavor> && simd_available_v<typename FF::Params>)
                                                 ? 50
                                                 : 64

Definition at line 91 of file sumcheck_round.hpp.

◆ univariate_accumulators

template<typename Flavor >

SumcheckTupleOfTuplesOfUnivariates bb::SumcheckProverRound< Flavor >::univariate_accumulators

Definition at line 121 of file sumcheck_round.hpp.

◆ USE_LAZY_EDGES

template<typename Flavor >

constexpr bool bb::SumcheckProverRound< Flavor >::USE_LAZY_EDGES = isAvmFlavor<Flavor> || USE_LAZY_SHORT_EDGES

staticconstexpr

Definition at line 84 of file sumcheck_round.hpp.

◆ USE_LAZY_SHORT_EDGES

template<typename Flavor >

constexpr bool bb::SumcheckProverRound< Flavor >::USE_LAZY_SHORT_EDGES = HasLazyShortEdges<Flavor>

staticconstexpr

Definition at line 81 of file sumcheck_round.hpp.

◆ USES_ROW_MANIFEST

template<typename Flavor >

template<typename ProverPolynomialsOrPartiallyEvaluatedMultivariates >

constexpr bool bb::SumcheckProverRound< Flavor >::USES_ROW_MANIFEST

staticconstexpr

Initial value:

=
        HAS_STATIC_ROW_SKIP_MANIFEST<ProverPolynomialsOrPartiallyEvaluatedMultivariates> ||
        CAN_SKIP_ROWS<ProverPolynomialsOrPartiallyEvaluatedMultivariates>

Definition at line 633 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

Private Attributes

Detailed Description

Member Typedef Documentation

◆ AccumulatorsFor

◆ ExtendedEdges

◆ FF

◆ Relations

◆ RelationTupleFor

◆ SubrelationSeparators

◆ SumcheckRoundUnivariate

◆ SumcheckTupleOfTuplesOfUnivariates

◆ Utils

◆ ZKData

Constructor & Destructor Documentation

◆ SumcheckProverRound()

Member Function Documentation

◆ accumulate_edge()

◆ accumulate_edge_chunks()

◆ accumulate_relation_univariates()

◆ accumulate_relation_univariates_public()

◆ advance_round()

◆ append_edge_range()

◆ batch_over_relations()

◆ chunk_count()

◆ compute_edge_ranges()

◆ compute_effective_round_size()

◆ compute_libra_univariate()

◆ compute_offset_area_contribution()

◆ compute_row_skip_edge_ranges()

◆ compute_univariate()

◆ compute_virtual_contribution()

◆ element_scaling()

◆ extend_and_batch_univariates()

◆ extend_edges()

◆ for_each_edge_group()

◆ is_virtual_round()

◆ load_edge()

◆ make_edge_chunks()

◆ make_extended_edges()

◆ merge_edge_ranges()

◆ reduce_accumulator()

◆ round_up_to_even()

Member Data Documentation

◆ BATCHED_RELATION_PARTIAL_LENGTH

◆ CAN_SKIP_ROWS

◆ excluded_head_size

◆ HAS_STATIC_ROW_SKIP_MANIFEST

◆ LIBRA_UNIVARIATES_LENGTH

◆ MAX_PARTIAL_RELATION_LENGTH

◆ multivariate_d

◆ NUM_RELATIONS

◆ round_index

◆ round_size

◆ ROWS_PER_CHUNK

◆ univariate_accumulators

◆ USE_LAZY_EDGES

◆ USE_LAZY_SHORT_EDGES

◆ USES_ROW_MANIFEST