Cryptology ePrint Archive: Report 2022/420

Gemini: Elastic SNARKs for Diverse Environments

Jonathan Bootle and Alessandro Chiesa and Yuncong Hu and Michele Orrù

Abstract: We introduce and study elastic SNARKs, a class of succinct arguments where the prover has multiple configurations with different time and memory tradeoffs, which can be selected depending on the execution environment and the proved statement. The output proof is independent of the chosen configuration.

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