Paper 2025/908

SubLogarithmic Linear Time SNARKs from Improved Sum-Check

Abstract

We present $\mathsf{HybridSpartan}$ and $\mathsf{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 (ROM) and the Algebraic Group Model (AGM). 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 5KB-10KB 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 two new SNARKs, namely $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$, 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 $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$, and compare their performances with several state-of-the-art prover-efficient SNARKs. For circuits of size $2^{30}$, $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$ achieve proof sizes of 1.9 KB and 2.4 KB, respectively, which are 2.4-3.6x smaller than the most compact prover-efficient SNARKs, while achieving comparable prover costs.

Note: We have substantially expanded the security and efficiency analysis, while also correcting some unaccounted proof size costs from the previous version. We thank the anonymous reviewers of ACM CCS 2026 for their constructive feedback and suggestions.