Cryptology ePrint Archive: Report 2019/099

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

Mary Maller and Sean Bowe and 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.

Category / Keywords: public-key cryptography / zero knowledge, zk-SNARKs, universal SRS, updateable SRS, subversion secure

Date: received 30 Jan 2019, last revised 7 Feb 2019

Contact author: mary maller 15 at ucl ac uk, sean@z cash

Available format(s): PDF | BibTeX Citation

Version: 20190207:125729 (All versions of this report)

Short URL: ia.cr/2019/099


[ Cryptology ePrint archive ]