The Sum-Check Protocol over the Monomial Basis, and Other Optimizations

The sum-check protocol underpins SNARKs with the fastest known provers. For an n -variate polynomial g over a finite field 𝔽 , it enables an untrusted prover to convince a verifier of the sum of all evaluations of g over a product set H n with H ⊂ 𝔽 . The standard choice for H n is the Boolean hypercube { 0 , 1 } n , whose points double as the natural interpolation points for multilinear polynomials. We propose a projective variant of the sum-check protocol, obtained by changing this interpolating set from { 0 , 1 } n to the infinity hypercube { 0 , ∞ } n . Under a suitable notion of evaluation at ∞ , evaluating a multilinear polynomial at a point of { 0 , ∞ } n directly reads off one of its monomial coefficients. The values a prover stores are therefore already monomial coefficients, and no change of basis is needed. This makes the variant a near-drop-in replacement, requiring only local changes to how polynomials are stored and how each round's consistency check is written, and leaving the number of rounds, the proof size, and the verifier's work unchanged. It removes every field subtraction from the prover's per-round update, gives structured polynomials such as equality and less-than shorter formulas that evaluate in fewer field operations, and matches the coefficient representation used by commitment schemes such as WHIR, removing a basis mismatch those schemes otherwise work around. Against a baseline carrying all known optimizations, it yields a 6–12% speedup of the sum-check prover on BN254 and on a pseudo-Mersenne 128-bit prime field. Finally, we describe an optimization specific to approximately 256-bit prime fields, and hence to provers built on elliptic-curve commitments. When targeting approximately 128 bits of security, it suffices to draw challenges from a subset of size close to 2 128 . We choose that subset to be the values whose Montgomery representation occupies only the upper machine words, which makes field multiplication 1.94 × faster and the prover's per-round update 1.82 × faster in combination with the projective formula.