Function zerocheck_univariate_evals

pub fn zerocheck_univariate_evals<F, FDomain, PBase, P, Composition, M, Backend>(
    multilinears: &[M],
    compositions: &[Composition],
    zerocheck_challenges: &[F],
    skip_rounds: usize,
    max_domain_size: usize,
    backend: &Backend,
) -> Result<ZerocheckUnivariateEvalsOutput<F, P, Backend>, Error>
where
    FDomain: TowerField,
    F: TowerField + ExtensionField<PBase::Scalar> + ExtensionField<FDomain>,
    PBase: PackedFieldIndexable<Scalar: ExtensionField<FDomain>> + PackedExtension<FDomain, PackedSubfield: PackedFieldIndexable>,
    P: PackedFieldIndexable<Scalar = F> + RepackedExtension<PBase>,
    Composition: CompositionPolyOS<PBase>,
    M: MultilinearPoly<P> + Send + Sync,
    Backend: ComputationBackend,

Compute univariate skip round evaluations for zerocheck.

When all witness multilinear hypercube evaluations can be embedded into a small field PBase::Scalar that is significantly smaller than F, we naturally want to refrain from folding for skip_rounds (denoted below as $k$) to reap the benefits of faster small field multiplications. Naive extensions to sumcheck protocol which compute multivariate round polynomials do not work though, given that for a composition of degree $d$ one would need $(d+1)^k-2^k$ evaluations (assuming Gruen24 section 3.2 optimizations), which usually grows faster than $2^k$ and thus will typically require more work than large field sumcheck. We adopt a univariatizing approach instead, where we define “oblong” multivariates: $$\hat{M}(\hat{u}_1,x_1,\ldots,x_n) = \sum M(u_1,\ldots, u_k, x_1, \ldots, x_n) \cdot L_u(\hat{u}_1)$$ with $\mathbb{M}: \hat{u}_1 \rightarrow (u_1, \ldots, u_k)$ being some map from the univariate domain to the $\mathcal{B}_k$ hypercube and $L_u(\hat{u})$ being Lagrange polynomials.

The main idea of the univariatizing approach is that $\hat{M}$ are of degree $2^k-1$ in $\hat{u}_1$ and multilinear in other variables, thus evaluating a composition of degree $d$ over $\hat{M}$ yields a total degree of $d(2^k-1)$ in the first round (again, assuming Gruen24 section 3.2 trick to avoid multiplication by the equality indicator), which is comparable to what a regular non-skipping zerocheck prover would do. The only issue is that we normally don’t have an oracle for $\hat{M}$, which necessitates an extra sumcheck reduction to multilinear claims (see univariatizing_reduction_claim).

One special trick of the univariate round is that round polynomial is represented in Lagrange form:

1. Honest prover evaluates to zero on $2^k$ domain points mapping to $\mathcal{B}_k$, reducing proof size
2. Avoiding monomial conversion saves prover time by skipping $O(N^3)$ inverse Vandermonde precomp
3. Evaluation in the verifier can be made linear time when barycentric weights are precomputed

This implementation defines $\mathbb{M}$ to be the basis-induced mapping of the binary field FDomain; the main reason for that is to be able to use additive NTT from LCH14 for extrapolation. The choice of domain field impacts performance, thus generally the smallest field with cardinality not less than the degree of the round polynomial should be used.