### Gemini: Elastic SNARKs for Diverse Environments

Jonathan Bootle, Alessandro Chiesa, 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.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2022
Keywords
interactive oracle proofsSNARKsstreaming algorithms
Contact author(s)
michele orru @ berkeley edu
History
Short URL
https://ia.cr/2022/420

CC BY

BibTeX

@misc{cryptoeprint:2022/420,
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{https://eprint.iacr.org/2022/420}},
url = {https://eprint.iacr.org/2022/420}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.