MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs. Kosba, A., Papadopoulos, D., Papamanthou, C., & Song, D. abstract bibtex 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.
@article{kosba_mirage_nodate,
title = {{MIRAGE}: {Succinct} {Arguments} for {Randomized} {Algorithms} with {Applications} to {Universal} zk-{SNARKs}},
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.},
language = {en},
author = {Kosba, Ahmed and Papadopoulos, Dimitrios and Papamanthou, Charalampos and Song, Dawn},
pages = {19},
}
Downloads: 0
{"_id":"yiajS2QwQ25P7rYbH","bibbaseid":"kosba-papadopoulos-papamanthou-song-miragesuccinctargumentsforrandomizedalgorithmswithapplicationstouniversalzksnarks","author_short":["Kosba, A.","Papadopoulos, D.","Papamanthou, C.","Song, D."],"bibdata":{"bibtype":"article","type":"article","title":"MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs","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.","language":"en","author":[{"propositions":[],"lastnames":["Kosba"],"firstnames":["Ahmed"],"suffixes":[]},{"propositions":[],"lastnames":["Papadopoulos"],"firstnames":["Dimitrios"],"suffixes":[]},{"propositions":[],"lastnames":["Papamanthou"],"firstnames":["Charalampos"],"suffixes":[]},{"propositions":[],"lastnames":["Song"],"firstnames":["Dawn"],"suffixes":[]}],"pages":"19","bibtex":"@article{kosba_mirage_nodate,\n\ttitle = {{MIRAGE}: {Succinct} {Arguments} for {Randomized} {Algorithms} with {Applications} to {Universal} zk-{SNARKs}},\n\tabstract = {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.},\n\tlanguage = {en},\n\tauthor = {Kosba, Ahmed and Papadopoulos, Dimitrios and Papamanthou, Charalampos and Song, Dawn},\n\tpages = {19},\n}\n\n","author_short":["Kosba, A.","Papadopoulos, D.","Papamanthou, C.","Song, D."],"key":"kosba_mirage_nodate","id":"kosba_mirage_nodate","bibbaseid":"kosba-papadopoulos-papamanthou-song-miragesuccinctargumentsforrandomizedalgorithmswithapplicationstouniversalzksnarks","role":"author","urls":{},"metadata":{"authorlinks":{}},"html":""},"bibtype":"article","biburl":"https://api.zotero.org/users/8315324/collections/M4HD3YSJ/items?key=7RWXUCZduzev33wfxHBTrvdq&format=bibtex&limit=100","dataSources":["JjeknPEFzCt2M8MXt"],"keywords":[],"search_terms":["mirage","succinct","arguments","randomized","algorithms","applications","universal","snarks","kosba","papadopoulos","papamanthou","song"],"title":"MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs","year":null}