Cryptology ePrint Archive: Report 2021/030

Linear-time zero-knowledge SNARKs for R1CS

Jonathan Lee and Srinath Setty and Justin Thaler and Riad Wahby

Abstract: This paper studies zero-knowledge SNARKs for NP, where the prover incurs $O(N)$ finite field operations to prove the satisfiability of an $N$-sized R1CS instance. We observe that recent work of Bootle, Chiesa, and Groth (BCG, TCC 20) provides a polynomial commitment scheme that, when combined with the linear-time interactive proof system of Spartan (CRYPTO 20), yields linear-time SNARKs for R1CS. Specifically, for security parameter $\lambda$, and for an $N$-sized R1CS instance over a field of size $\exp(\lambda)$ and fixed $\epsilon > 0$, the prover incurs $O(N)$ finite field operations to produce a proof of size $O_\lambda(N^\epsilon)$ that can be verified in $O_\lambda(N^\epsilon)$---after a one-time preprocessing step, which requires $O(N)$ finite field operations. This reestablishes the main result of BCG. Arguably, our approach is conceptually simpler and more direct. Additionally, the polynomial commitment scheme that we distill from BCG is of independent interest; it improves over the prior state of the art by offering the first scheme where the time to commit and to prove an evaluation of a committed polynomial are both $O(N)$ finite field operations for an $N$-sized polynomial.

We further observe that one can render the aforementioned SNARK zero knowledge and reduce the proof size and verifier time to polylogarithmic---while maintaining a linear-time prover---by outsourcing the verifier's work via one layer of proof composition with an existing zkSNARK as the ``outer'' proof system. A similar result was recently obtained by Bootle, Chiesa, and Liu (ePrint 2020/1527).

Category / Keywords: cryptographic protocols / linear-time zkSNARKs, succinct arguments, zero-knowledge proofs

Date: received 7 Jan 2021

Contact author: srinath at microsoft com,Justin Thaler@georgetown edu

Available format(s): PDF | BibTeX Citation

Version: 20210112:075318 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]