SubLogarithmic Linear Time SNARKs from Compressed Sum-Check
Nitin Singh, IBM Research India
Sikhar Patranabis, IBM Research India
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 multivariate polynomials in variables which can be decomposed into multilinear polynomials. We exhibit a new multivariate sum-check protocol with communication for . Our protocol retains the prover cost~(where the precise constant depends on , and the multivariate form). Thus we improve on the 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.
@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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.