Struct SparseDenseProductSumcheckProver 

pub struct SparseDenseProductSumcheckProver<P: PackedField, Data: BufferData<P> = Vec<P>> { /* private fields */ }

Proves the hypercube sum of the product of a sparse and a dense multilinear.

The sparse multilinear $A$ is given as a list of (index, value) entries, defined as

$$ A(v) = \sum_{(i, c) \in \text{entries}, i = v} c $$

so entries at a repeated index add up and need not be deduplicated. The dense multilinear $B$ is a full buffer over the same $n$ variables. The prover argues the claim

$$ s = \sum_{v \in B_n} A(v) B(v) $$

which is the plain, non-eq-weighted sumcheck of a degree-2 composition. Its rounds cost one pass over the entry list plus two dense lookups per entry, so the work per round is set by the number of entries rather than by the size of the hypercube.

Variables bind from the highest index down, as in the dense provers of this module. Round $j$ therefore splits the index space at half, the bit the round binds: an entry below it lies in the half where the bound variable is 0, one at or above it in the half where it is 1.

Round polynomial

With $A_0, A_1$ the two halves of $A$ on the bound variable (likewise $B$), the round polynomial is sampled at 1 and at infinity, and its value at 0 recovered from the round claim:

$$ R(1) = \sum_v A_1(v) B_1(v) \qquad R(\infty) = \sum_v (A_0 + A_1)(v) (B_0 + B_1)(v) $$

Both are linear in $A$, so each entry contributes to them on its own: pairing an entry with the one facing it across the split is never needed. An entry $(i, c)$ with $v = i \bmod \text{half}$ adds $c B(i)$ to $R(1)$ when it lies in the upper half, and $c (B_0 + B_1)(v)$ to $R(\infty)$ wherever it lies.

Folding

Folding is linear in $A$ for the same reason: an entry keeps its identity across the fold, scaled by the challenge weight of the half it sits in and moved down into the lower half. Entries thus stay a flat list of the same length for the whole protocol, and collapse to the evaluation of $A$ at the challenge point only in SumcheckProver::finish, which emits the sparse multilinear’s evaluation before the dense one’s.

Implementations

impl<P: PackedField, Data: BufferData<P>> SparseDenseProductSumcheckProver<P, Data>

pub fn new( sparse: Vec<SparseEntry<P::Scalar>>, dense: FactoredMultilinear<P, Data>, sum: P::Scalar, ) -> Self

Creates a prover for the claim that the sparse-dense product sums to sum.

Arguments

• sparse - the entries of the sparse multilinear, in any order, indices repeatable
• dense - the dense multilinear, whose length fixes the number of variables
• sum - the claimed sum of the product over the hypercube

Panics

Panics if any entry index is out of range for dense.

Trait Implementations

impl<F: Field, P: PackedField<Scalar = F>, Data: BufferData<P> + Sync> SumcheckProver<F> for SparseDenseProductSumcheckProver<P, Data>

fn n_vars(&self) -> usize

The number of variables in the remaining multivariate polynomial.

fn execute(&mut self) -> Vec<RoundCoeffs<F>>

Computes the prover messages for this round as a univariate polynomial.

fn fold(&mut self, challenge: F)

Folds the sumcheck multilinears with a new verifier challenge.

fn finish(self) -> Vec<F>

Finishes the sumcheck proving protocol and returns the evaluations of all multilinears at the challenge point.