Paper 2025/908

SubLogarithmic Linear Time SNARKs from Improved Sum-Check

Abstract

We present HybridSpartan and HybridPlonk -- the first SNARKs that simultaneously achieve linear-time prover, sublogarithmic proof size, logarithmic verifier, and also feature updatable setups. Our constructions are provably secure in the random oracle model. As a core technical contribution~(possibly of independent interest), we reduce the communication complexity of the classical sumcheck protocol for multivariate polynomials from logarithmic to sublogarithmic, while retaining linear prover complexity. For degree $d$ multivariate polynomials in $\mu$ variables which can be decomposed into $\ell$ multilinear polynomials, our protocol achieves $O(\ell + d\log\log n)$ communication and $O(n)$ prover cost for $n = 2^\mu$. Our protocol leverages recently proposed multilinear polynomial commitment schemes (PCS) with linear-time prover and constant proof size. Multivariate sumcheck is a key ingredient in the design of several prover-efficient SNARKs, such as Spartan (Crypto '20), HyperPlonk (Eurocrypt '23), MicroSpartan (S&P '25), Hyrax (S&P '18), Libra (Crypto '19), Gemini (Eurocrypt '22), Virgo (S&P '20) etc. All of these SNARKs incur $\Omega(\log n)$ proof size, with the smallest concrete proof sizes ranging from $5$KB-$10$KB for circuit sizes in the range of $2^{20}$-$2^{30}$. We compile variants of the Spartan and HyperPlonk multilinear PIOPs with our improved sumcheck to realize HybridSpartan and HyperPlonk that support R1CS and Plonkish constraints, respectively. Both of them achieve $O(n)$ prover, $O(\log\log n)$ proof size, and $O(\log n)$ verifier, while avoiding proof recursion and non-black-box use of cryptographic primitives. We implement HybridSpartan and HyperPlonk, and compare their performances with several state-of-the-art prover-efficient SNARKs. For circuits of size $2^{30}$, HybridSpartan and HybridSpartan achieve proof sizes of $1.8$ KB and $2.3$ KB, respectively, which are $2.5-3.8\times$ smaller than the most compact prover-efficient SNARKs, while achieving comparable prover costs.

Note: In addition to HyperPlonk, we present a new application of our improved sumcheck argument to a variant of the Spartan multilinear PIOP to achieve HybridSpartan - a new linear-prover SNARK with sublogarithmic proof size and logarithmic verification that supports R1CS constraints.