Sonic
Authors:
Open Access
- 6 November 2019
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 2111-2128
Abstract
Ever since their introduction, zero-knowledge proofs have become an important tool for addressing privacy and scalability concerns in a variety of 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 structured reference string that is also updatable, but 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 updatable structured reference string that scales linearly in size. We also describe a generally useful technique in which untrusted "helpers" can compute advice that allows batches of proofs to be verified more efficiently. Sonic proofs are constant size, and in the "helped" batch verification context the marginal cost of verification is comparable with the most efficient SNARKs in the literature.Keywords
Funding Information
- EPSRC (EP/N028104/1Ever since their introduction zero-knowledge proofs)
This publication has 47 references indexed in Scilit:
- Efficient Signatures of Knowledge and DAA in the Standard Model2013
- Quadratic Span Programs and Succinct NIZKs without PCPs2013
- Efficient Zero-Knowledge Argument for Correctness of a Shuffle2012
- Random Oracles in a Quantum World2011
- Constant-Size Commitments to Polynomials and Their Applications2010
- Randomizable Proofs and Delegatable Anonymous Credentials2009
- Zero-Knowledge Proofs from Secure Multiparty ComputationSIAM Journal on Computing, 2009
- Pairings for cryptographersDiscrete Applied Mathematics, 2008
- Short Signatures Without Random Oracles and the SDH Assumption in Bilinear GroupsJournal of Cryptology, 2007
- The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs2006