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 knowledgezk-SNARKsuniversal SRSupdateable SRSsubversion 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},
url = {https://eprint.iacr.org/2019/099}
}
