Paper 2022/420
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2022-04-06: received
- Short URL
- https://ia.cr/2022/420
- License
-
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}
}
