Conference proceeding
MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs
PROCEEDINGS OF THE 29TH USENIX SECURITY SYMPOSIUM, pp.2129-2146
01 Jan 2020
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.
Metrics
3 Record Views
Details
- Title
- MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs
- Creators
- Ahmed Kosba - Alexandria UniversityDimitrios Papadopoulos - HKUST, Hong Kong, Peoples R ChinaCharalampos Papamanthou - Univ Maryland, College Pk, MD 20742 USADawn Song - Univ Calif Berkeley, Berkeley, CA USAUSENIX Assoc
- Publication Details
- PROCEEDINGS OF THE 29TH USENIX SECURITY SYMPOSIUM, pp.2129-2146
- Conference
- 29TH USENIX SECURITY SYMPOSIUM, 29th
- Publisher
- Usenix Assoc
- Number of pages
- 18
- Grant note
- NIST; National Institute of Standards & Technology (NIST) - USA ECS-26208318 / Hong Kong RGC; Hong Kong Research Grants Council N66001-15-C-4066 / DARPA; United States Department of Defense; Defense Advanced Research Projects Agency (DARPA) Center for Long-Term Cybersecurity (CLTC) 1514261; 1652259 / NSF; National Science Foundation (NSF)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Mathematics
- Identifiers
- 991020531962004721
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Information Systems