Paper 2022/420

Gemini: Elastic SNARKs for Diverse Environments

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


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.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2022
interactive oracle proofsSNARKsstreaming algorithms
Contact author(s)
michele orru @ berkeley edu
2022-04-06: received
Short URL
Creative Commons Attribution


      author = {Jonathan Bootle and Alessandro Chiesa and Yuncong Hu and Michele Orrù},
      title = {Gemini: Elastic SNARKs for Diverse Environments},
      howpublished = {Cryptology ePrint Archive, Paper 2022/420},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.