### 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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Contact author(s)
mary maller 15 @ ucl ac uk
sean @ z cash
History
2019-07-08: last of 5 revisions
See all versions
Short URL
https://ia.cr/2019/099

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.