Paper 2020/278
MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs
Ahmed Kosba, Dimitrios Papadopoulos, Charalampos Papamanthou, and Dawn Song
Abstract
The last few years have witnessed increasing interest in the deployment of zero-knowledge proof systems, in particular ones with succinct proofs and efficient verification (zk-SNARKs). One of the main challenges facing the wide deployment of zk-SNARKs is the requirement of a trusted key generation phase per different computation to achieve practical proving performance. Existing zero-knowledge proof systems that do not require trusted setup or have a single trusted preprocessing phase suffer from increased proof size and/or additional verification overhead. On the other other hand, although universal circuit generators for zk-SNARKs (that can eliminate the need for per-computation preprocessing) have been introduced in the literature, the performance of the prover remains far from practical for real-world applications. In this paper, we first present a new zk-SNARK system that is well-suited for randomized algorithms---in particular it does not encode randomness generation within the arithmetic circuit allowing for more practical prover times. Then, we design a universal circuit that takes as input any arithmetic circuit of a bounded number of operations as well as a possible value assignment, and performs randomized checks to verify consistency. Our universal circuit is linear in the number of operations instead of quasi-linear like other universal circuits. By applying our new zk-SNARK system to our universal circuit, we build MIRAGE, a universal zk-SNARK with very succinct proofs---the proof contains just one additional element compared to the per-circuit preprocessing state-of-the-art zk-SNARK by Groth (Eurocrypt 2016). Finally, we implement MIRAGE and experimentally evaluate its performance for different circuits and in the context of privacy-preserving smart contracts.
Note: Minor updates: This version has a link to the implementation, a clarification and a fix for the universal verification key size, in addition to other typo fixes and clarifications.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. USENIX Security 2020
- Keywords
- zero knowledgezk-SNARKs
- Contact author(s)
-
ahmed kosba @ alexu edu eg
cpap @ umd edu - History
- 2020-08-24: last of 2 revisions
- 2020-03-04: received
- See all versions
- Short URL
- https://ia.cr/2020/278
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/278, author = {Ahmed Kosba and Dimitrios Papadopoulos and Charalampos Papamanthou and Dawn Song}, title = {{MIRAGE}: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-{SNARKs}}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/278}, year = {2020}, url = {https://eprint.iacr.org/2020/278} }