Paper 2025/908

SubLogarithmic Linear Time SNARKs from Compressed Sum-Check

Abstract

We leverage recently proposed multilinear polynomial commitment schemes, with linear time prover and constant proof size to reduce the communication complexity of the classical sum-check protocol for multivariate polynomials. Specifically, we consider degree $d$ multivariate polynomials in $\mu$ variables which can be decomposed into $\ell$ multilinear polynomials. We exhibit a new multivariate sum-check protocol with $O(\ell +d\log \log n)$ communication for $n=2^{\mu }$. Our protocol retains the $O(n)$ prover cost~(where the precise constant depends on $\ell$, $d$ and the multivariate form). Thus we improve on the $O(\log n)$ communication inherent in all applications of existing multivariate sum-check protocol. Multivariate sum-check is a key ingredient in the design of several prover-efficient SNARKs, such as HyperPlonk (EUROCRYPT 2023), Spartan (CRYPTO 2020), Hyrax (IEEE S&P 2018), Libra (CRYPTO 2019), Gemini (EUROCRYPT 2022), Virgo (S&P 2020) etc. All of these SNARKS incur at least $$ proof size, with the smallest concrete proof size being $$ KB for circuits of size $$. Our improved multivariate sum-check protocol improves the proof size of all of the above SNARKs while retaining the $$ prover cost. In particular, plugging our sum-check protocol into the HyperPlonk multilinear PIOP yields $$ -- the first SNARK that simultaneously achieves $$ prover, sublogarithmic proof size of $$, and $$ verifier. Concretely, the proof size of $$ is about 2 KB for circuit sizes up to $$. We note that SNARKs with smaller proof size than $$ are based on univariate polynomials, and are not prover-efficient as they inherently incur $$ prover cost due to polynomial multiplications. Moreover, $$ avoids proof recursion techniques and non-black-box usage of cryptographic primitives. We believe that our improved multivariate sum-check protocol is of independent interest, and could have applications beyond SNARKs.

Note: Expanded construction of Hyperplonk PIOP based on compressed sum-check. Incorporating comments on first version.