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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2020/278}},
      url = {https://eprint.iacr.org/2020/278}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.