Talk by Michele Orrù

Abstract: We introduce and study elastic SNARKs, a class of proofs where the prover can select different time and memory tradeoffs, 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 streaming algorithms and a quasilinear number of cryptographic operations with 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.

Bio: Michele Orrù is a CNRS research scientist at Sorbonne Université. Previously, he was at UC Berkeley as a research scholar. He obtained his PhD from École Normale Supérieure, and his MSc in mathematics from the University of Trento. His research focuses on building authentication mechanisms that preserve user anonymity. He works on improving the efficiency and security of zero-knowledge proofs, lightweight anonymous credential systems, and confidential transactions. In the past, Michele has contributed to Python, Debian, and Tor. He co-designed GlobaLeaks, an open-source whistleblowing platform now translated into more than 90 languages and used by more than 300 organizations. Additionally, he co-authored the cryptography behind Google’s Trust Tokens. Currently, he is actively involved in maintaining the arkworks.rs algebra crate.