Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings

Mary Maller; Sean Bowe; Markulf Kohlweiss; Sarah Meiklejohn

Paper 2019/099

Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings

Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn

Abstract

Zero-knowledge proofs have become an important tool for addressing privacy and scalability concerns in cryptocurrencies and other applications. In many systems each client downloads and verifies every new proof, and so proofs must be small and cheap to verify. The most practical schemes require either a trusted setup, as in (pre-processing) zk-SNARKs, or verification complexity that scales linearly with the complexity of the relation, as in Bulletproofs. The structured reference strings required by most zk-SNARK schemes can be constructed with multi-party computation protocols, but the resulting parameters are specific to an individual relation. Groth et al. discovered a zk-SNARK protocol with a universal and updateable structured reference string, however the string scales quadratically in the size of the supported relations. Here we describe a zero-knowledge SNARK, Sonic, which supports a universal and continually updateable structured reference string that scales linearly in size. Sonic proofs are constant size, and in the batch verification context the marginal cost of verification is comparable with the most efficient SNARKs in the literature. We also describe a generally useful technique in which untrusted ``helpers'' can compute advice which allows batches of proofs to be verified more efficiently.

Note: Batching arguments updated.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: zero knowledge zk-SNARKs universal SRS updateable SRS subversion secure
Contact author(s): mary maller 15 @ ucl ac uk
sean @ z cash
History: 2019-07-08: last of 5 revisions; 2019-01-31: received; See all versions
Short URL: https://ia.cr/2019/099
License: CC BY

BibTeX

@misc{cryptoeprint:2019/099,
      author = {Mary Maller and Sean Bowe and Markulf Kohlweiss and Sarah Meiklejohn},
      title = {Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings},
      howpublished = {Cryptology ePrint Archive, Paper 2019/099},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/099}},
      url = {https://eprint.iacr.org/2019/099}
}