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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- SNARKZero Knowledge ProofsPolynomial CommitmentMultilinear SNARKsSum Check
- Contact author(s)
-
nitisin1 @ in ibm com
Sikhar Patranabis @ ibm com - History
- 2025-06-26: last of 3 revisions
- 2025-05-21: received
- See all versions
- Short URL
- https://ia.cr/2025/908
- License
-
CC0
BibTeX
@misc{cryptoeprint:2025/908, author = {Nitin Singh and Sikhar Patranabis}, title = {{SubLogarithmic} Linear Time {SNARKs} from Compressed Sum-Check}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/908}, year = {2025}, url = {https://eprint.iacr.org/2025/908} }