1970-01-01

(2026-04) The Sum-Check Protocol over the Monomial Basis, and Other Optimizations

• [[Quang Dao]]
• [[Ari Biswas]]
• [[Liam Eagen]]
• [[Andrew Milson]]
• [[Shahar Papini]]
• [[Justin Thaler]]

2026-04-17

• #cryptography
• #paper

Abstract

The sum-check protocol underpins SNARKs with the fastest known provers. For an $n$-variate polynomial $g$ defined over a finite field $\mathbb{F}$, the protocol enables an untrusted prover to convince a verifier of the sum of all evaluations of $g$ over a product set $H^n$ with $H \subset \mathbb{F}$. The standard choice for $H^n$ is the Boolean hypercube $\{0,1\}^n$, which serves as a natural interpolating set for multilinear polynomials.

We propose a projective variant of the sum-check protocol, obtained by changing the interpolating set from $\{0,1\}^n$ to the infinity hypercube $\{0,\infty\}^n$. Under a suitable notion of evaluation at $\infty$, evaluating a multilinear polynomial at a point in $\{0,\infty\}^n$ directly extracts its corresponding monomial coefficient.

This projective viewpoint is a near-drop-in replacement for applications of sum-check, requiring only local changes to polynomial representations, round identities, and evaluation formulas. It yields a ${\approx}\,10\%$ end-to-end speedup for the sum-check prover on BN254 and on a pseudo-Mersenne 128-bit prime field, against a fair baseline. It eliminates all field subtractions when binding a multilinear polynomial, and for structured polynomials such as equality and less-than, the projective interpolants admit evaluation procedures with fewer field operations. Moreover, the monomial-coefficient form aligns naturally with polynomial commitment schemes like WHIR, removing a basis mismatch that these schemes otherwise need to work around.

Finally, we describe an optimization for sum-check over $\approx 256$-bit prime fields. When targeting $\approx 128$ bits of security, it suffices to sample challenges from a subset of size $\approx 2^{128}$. We show that a suitable choice of this subset, interpreted as upper-limb values in Montgomery form, yields a $1.92\times$ speedup for field multiplication. Combined with the projective binding formula, this gives a $1.82\times$ speedup for sum-check binding (a key component of fast sum-check proving).