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 $O(\log n)$ proof size, with the smallest concrete proof size being $\approx 7$ KB for circuits of size $2^{25}$. Our improved multivariate sum-check protocol improves the proof size of all of the above SNARKs while retaining the $O(n)$ prover cost. In particular, plugging our sum-check protocol into the HyperPlonk multilinear PIOP yields $\mathsf{HybridPlonk}$ -- the first SNARK that simultaneously achieves $O(n)$ prover, sublogarithmic proof size of $O(\log\log n)$, and $O(\log n)$ verifier. Concretely, the proof size of $\mathsf{HybridPlonk}$ is about 2 KB for circuit sizes up to $2^{30}$. We note that SNARKs with smaller proof size than $\mathsf{HybridPlonk}$ are based on univariate polynomials, and are not prover-efficient as they inherently incur $O(n\log n)$ prover cost due to polynomial multiplications. Moreover, $\mathsf{HybridPlonk}$ 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.