We construct an elastic SNARK for rank-1 constraint satisfiability (R1CS). In a time-efficient configuration, the prover uses a linear number of cryptographic operations and a linear amount of memory. In a space-efficient configuration, the prover uses a quasilinear number of cryptographic operations and a logarithmic amount of memory. A key component of our construction is an elastic probabilistic proof. Along the way, we also formulate a streaming framework for R1CS that we deem of independent interest.
We additionally contribute Gemini, a Rust implementation of our protocol. Our benchmarks show that Gemini, on a single machine, supports R1CS instances with tens of billions of constraints.
Category / Keywords: public-key cryptography / interactive oracle proofs, SNARKs, streaming algorithms Original Publication (with major differences): IACR-EUROCRYPT-2022 Date: received 1 Apr 2022 Contact author: michele orru at berkeley edu Available format(s): PDF | BibTeX Citation Version: 20220406:125953 (All versions of this report) Short URL: ia.cr/2022/420