Paper 2021/030

Linear-time and post-quantum zero-knowledge SNARKs for R1CS

Jonathan Lee, Srinath Setty, 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 IOPs and 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 to an $N$-sized polynomial is $O(N)$ finite field operations. 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 can be derived from recent work of Bootle, Chiesa, and Liu (ePrint 2020/1527). We implement the aforementioned polynomial commitment scheme with $\epsilon = 1/2$ and combine it with Spartan’s interactive proof system to obtain a SNARK for R1CS. We refer to this combination as Cerberus. It uses Reed-Solomon codes in the polynomial commitment scheme, and hence the prover is not asymptotically linear-time. Nonetheless, Cerberus features the fastest known prover (the only exception is Spartan when proving large instances over 256-bit fields), and is plausibly post-quantum secure.

Note: Include experimental results.