International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Gemini: elastic SNARKs for diverse environments

Authors:
Jonathan Bootle , IBM Research – Zurich
Alessandro Chiesa , EPFL
Yuncong Hu , UC Berkeley
Michele Orrù , UC Berkeley
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: We introduce a new class of succinct arguments, that we call elastic. Elastic SNARKs allow the prover to allocate different resources (such as memory and time) depending on the execution environment and the statement to prove. The resulting output is independent of the prover’s configuration. To study elastic SNARKs, we extend the streaming paradigm of [Block et al., TCC’20]. We provide a definitional framework for elastic polynomial interactive oracle proofs for R1CS instances and design a compiler which transforms an elastic PIOP into a preprocessing argument system that supports streaming or random access to its inputs. Depending on the configuration, the prover will choose different trade-offs for time (either linear, or quasilinear) and memory (either linear, or logarithmic). We prove the existence of elastic SNARKS by presenting Gemini, a novel FFT-free preprocessing argument. We prove its security and develop a proof-of-concept implementation in Rust based on the arkworks framework. We provide benchmarks for large R1CS instances of tens of billions of gates on a single machine.
Video from EUROCRYPT 2022
BibTeX
@inproceedings{eurocrypt-2022-31934,
  title={Gemini: elastic SNARKs for diverse environments},
  publisher={Springer-Verlag},
  author={Jonathan Bootle and Alessandro Chiesa and Yuncong Hu and Michele Orrù},
  year=2022
}