Struct SelectStatement 

pub struct SelectStatement<F, EF> { /* private fields */ }

A batched system of select-based evaluation constraints for multilinear polynomials.

This struct represents a collection of evaluation constraints of the form p(z_i) = s_i for a multilinear polynomial p over the Boolean hypercube {0,1}^k.

The Select Function

For vectors X, Y ∈ F^k, the select function is defined as:

select(X, Y) = ∏_i (X_i · Y_i + (1 - Y_i))

Key Property: When Y ∈ {0,1}^k is a Boolean vector and X = pow(z):

select(pow(z), b) = z^{int(b)}

where pow(z) = (z, z^2, z^4, ..., z^{2^{k-1}}) and int(b) interprets the Boolean vector b as an integer in binary.

Derivation:

select(pow(z), b) = ∏_i (z^{2^i} · b_i + (1 - b_i))
                  = ∏_{i: b_i=1} (z^{2^i})     [since b_i ∈ {0,1}]
                  = z^{Σ_{i: b_i=1} 2^i}
                  = z^{int(b)}

Verification Claims

Each constraint (z_i, s_i) in this statement asserts:

Σ_{b ∈ {0,1}^k} P(b) · select(pow(z_i), b) = s_i

where P(b) are the evaluations of the polynomial over the Boolean hypercube.

Batching

Multiple constraints are batched using random challenge γ to produce:

• Weight polynomial: W(b) = Σ_i γ^i · select(pow(z_i), b)
• Target sum: S = Σ_i γ^i · s_i

This reduces n separate verification claims to a single sumcheck:

Σ_{b ∈ {0,1}^k} P(b) · W(b) = S

Implementations

impl<F: Field, EF: ExtensionField<F>> SelectStatement<F, EF>

pub const fn initialize(num_variables: usize) -> Self

Creates an empty select statement for polynomials over {0,1}^k.

Parameters

• num_variables: The dimension k of the Boolean hypercube

Returns

An initialized statement with no constraints, ready to accept constraints.

pub const fn new( num_variables: usize, vars: Vec<F>, evaluations: Vec<EF>, ) -> Self

Creates a select statement pre-populated with constraints.

Parameters

• num_variables: The dimension k of the Boolean hypercube
• vars: Evaluation points [z_1, ..., z_n]
• evaluations: Expected values [s_1, ..., s_n]

Panics

Panics if the nu

pub const fn num_variables(&self) -> usize

Returns the number of variables k defining the polynomial space dimension.

This is the dimension of the Boolean hypercube {0,1}^k over which polynomials are defined, containing 2^k evaluation points.

pub const fn is_empty(&self) -> bool

Returns true if no constraints have been added to this statement.

pub fn iter(&self) -> impl Iterator<Item = (&F, &EF)>

Returns an iterator over constraint pairs (z_i, s_i).

Each pair represents one evaluation constraint: p(z_i) = s_i.

pub const fn len(&self) -> usize

Returns the number of evaluation constraints n in this statement.

pub fn verify(&self, poly: &Poly<EF>) -> bool

Verifies that a given polynomial satisfies all constraints in the statement.

For each constraint (z_i, s_i), this method interprets the evaluation table as coefficients of a univariate polynomial, evaluates it at z_i using Horner’s method, and checks if the result equals the expected value s_i.

For a polynomial represented by evaluations [c_0, c_1, ..., c_{2^k-1}]:

p(z) = c_0 + z(c_1 + z(c_2 + z(...)))

This is computed right-to-left as:

acc = 0
for i = 2^k-1 down to 0:
    acc = acc * z + c_i

Parameters

• poly: Evaluation table treated as univariate polynomial coefficients

Returns

true if all constraints are satisfied, false otherwise.

pub fn add_constraint(&mut self, var: F, eval: EF)

Adds a single evaluation constraint p(z) = s to the statement.

Parameters

• var: Evaluation point z ∈ F
• eval: Expected evaluation value s ∈ EF

pub fn combine( &self, acc_weights: &mut Poly<EF>, acc_sum: &mut EF, challenge: EF, shift: usize, )

Batches all constraints into a single weighted polynomial and target sum for sumcheck.

Given constraints p(z_1) = s_1, ..., p(z_n) = s_n, this method transforms them into a single sumcheck claim using random challenge γ:

Σ_{b ∈ {0,1}^k} P(b) · W(b) = S

where:

• Weight polynomial: W(b) = Σ_i γ^{i+shift} · select(pow(z_i), b)
• Target sum: S = Σ_i γ^{i+shift} · s_i

The method computes W(b) for all b ∈ {0,1}^k and S, adding them to the provided accumulators.

Parameters

• acc_weights: Accumulator for the weight polynomial W(b). Must have 2^k entries. This method adds the batched weights to existing values.

• acc_sum: Accumulator for the target sum S. This method adds the batched evaluations to the existing value.

• challenge: Random challenge γ ∈ EF used for batching.

• shift: Power offset for challenge. Constraint i uses weight γ^{i+shift}. Allows multiple statement types to use non-overlapping challenge powers. Batches all constraints into a single weighted polynomial and target sum for sumcheck.

Algorithm

Three stages:

1. Power map: Build a k × n matrix where row i, column j holds z_j^{2^i}. Stored as a flat row-major buffer so each butterfly step reads a contiguous row (cache-friendly).

2. Butterfly expansion: Expand the power map into the full 2^k × n select matrix using the same binary-tree doubling as the scalar power table. Entry [b, j] = z_j^b.

3. Challenge combination: Dot each row of the select matrix with the challenge power vector to produce the weight polynomial.

pub fn combine_packed( &self, weights: &mut Poly<EF::ExtensionPacking>, sum: &mut EF, challenge: EF, shift: usize, )

SIMD-packed variant of constraint batching.

Overview

Produces the same result as the scalar version, but stores the weight polynomial in packed form (one SIMD element per Packing::WIDTH consecutive hypercube entries).

Algorithm

For small k (where 2 * k_pack > k), falls back to a naive per-constraint loop using shifted powers.

For larger k, uses the split-and-dot approach:

1. Expand each evaluation point into its power-map representation.
2. Transpose into a k × n matrix and split at k / 2.
3. Build the packed left-half power table and the scalar right-half power table.
4. For each pair of rows (left packed, right scalar), compute the weighted dot product with the challenge powers.

pub fn combine_evals(&self, claimed_eval: &mut EF, challenge: EF, shift: usize)

Batches expected evaluation values into a single target sum using challenge powers.

Computes and adds to claimed_eval:

S = Σ_i γ^{i+shift} · s_i

where s_i are the expected evaluation values in self.evaluations.

Parameters

• claimed_eval: Accumulator for the target sum. This method adds the batched evaluations to the existing value.

• challenge: Random challenge γ ∈ EF used for batching.

• shift: Power offset. Constraint i uses weight γ^{i+shift}.

Trait Implementations

impl<F: Clone, EF: Clone> Clone for SelectStatement<F, EF>

fn clone(&self) -> SelectStatement<F, EF>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F: Debug, EF: Debug> Debug for SelectStatement<F, EF>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.