International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS

Authors:
Alessandro Chiesa , UC Berkeley
Yuncong Hu , UC Berkeley
Mary Maller , Ethereum Foundation
Pratyush Mishra , UC Berkeley
Noah Vesely , UC Berkeley
Nicholas P. Ward , UC Berkeley
Download:
DOI: 10.1007/978-3-030-45721-1_26 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: We present a general methodology to construct preprocessing zkSNARKs where the structured reference string (SRS) is universal and updatable. This exploits a novel application of *holographic* IOPs, a natural generalization of holographic PCPs [Babai et al., STOC 1991]. We use our methodology to obtain a preprocessing zkSNARK where the SRS has linear size and arguments have constant size. Our construction improves on Sonic [Maller et al., CCS 2019], the prior state of the art in this setting, in all efficiency parameters: proving is an order of magnitude faster and verification is twice as fast, even with smaller SRS size and argument size. Our construction is most efficient when instantiated in the algebraic group model (also used by Sonic), but we also demonstrate how to realize it under concrete knowledge assumptions. The core of our zkSNARK is a new holographic IOP for rank-1 constraint satisfiability (R1CS), which is the first to achieve linear proof length and constant query complexity (among other efficiency features).
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30190,
  title={Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={succinct arguments;universal SRS;algebraic holographic proofs;polynomial commitments},
  volume={12105},
  doi={10.1007/978-3-030-45721-1_26},
  author={Alessandro Chiesa and Yuncong Hu and Mary Maller and Pratyush Mishra and Noah Vesely and Nicholas P. Ward},
  year=2020
}