Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS

Alessandro Chiesa; Yuncong Hu; Mary Maller; Pratyush Mishra; Psi Vesely; Nicholas Ward

Paper 2019/1047

Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS

Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas Ward

Abstract

We present a methodology to construct preprocessing zkSNARKs where the structured reference string (SRS) is universal and updatable. This exploits a novel use of *holography* [Babai et al., STOC 1991], where fast verification is achieved provided the statement being checked is given in encoded form. 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 thrice 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. We implement and evaluate our construction. The core of our preprocessing zkSNARK is an efficient *algebraic holographic proof* (AHP) for rank-1 constraint satisfiability (R1CS) that achieves linear proof length and constant query complexity.

Note: The updated version includes further optimizations to both the AHP and the compiler.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in EUROCRYPT 2020
Keywords: succinct arguments universal SRS algebraic holographic proofs polynomial commitments
Contact author(s): alexch @ berkeley edu
pratyush @ berkeley edu
History: 2021-10-04: last of 4 revisions; 2019-09-18: received; See all versions
Short URL: https://ia.cr/2019/1047
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1047,
      author = {Alessandro Chiesa and Yuncong Hu and Mary Maller and Pratyush Mishra and Psi Vesely and Nicholas Ward},
      title = {Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1047},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1047}},
      url = {https://eprint.iacr.org/2019/1047}
}