Non-interactive zero-knowledge proof
Non-interactive
The key advantage of non-interactive zero-knowledge proofs is that they can be used in situations where there is no possibility of interaction between the prover and verifier, such as in online transactions where the two parties are not able to communicate in real time. This makes non-interactive zero-knowledge proofs particularly useful in decentralized systems like blockchains, where transactions are verified by a network of nodes and there is no central authority to oversee the verification process.[1]
Most non-interactive zero-knowledge proofs are based on mathematical constructs like
History
![]() | This section needs expansion with: history of how zero-knowledge proofs are used in real applications and apps, and for what purposes. You can help by adding to it. (October 2020) |
Blum, Feldman, and Micali[2] showed in 1988 that a common reference string shared between the prover and the verifier is sufficient to achieve computational zero-knowledge without requiring interaction. Goldreich and Oren[3] gave impossibility results[clarification needed] for one shot zero-knowledge protocols in the standard model. In 2003, Shafi Goldwasser and Yael Tauman Kalai published an instance of an identification scheme for which any hash function will yield an insecure digital signature scheme.[4]
The model influences the properties that can be obtained from a zero-knowledge protocol. Pass
Blockchain applications
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/17/STARK_proofs_diagram.jpg/400px-STARK_proofs_diagram.jpg)
In 2012, Alessandro Chiesa et al developed the zk-SNARK protocol, an acronym for zero-knowledge succinct non-interactive argument of knowledge.[6] The first widespread application of zk-SNARKs was in the Zerocash blockchain protocol, where zero-knowledge cryptography provides the computational backbone, by facilitating mathematical proofs that one party has possession of certain information without revealing what that information is.[7] Zcash utilized zk-SNARKs to facilitate four distinct transaction types: private, shielding, deshielding, and public. This protocol allowed users to determine how much data was shared with the public ledger for each transaction.[8] Ethereum zk-Rollups also utilize zk-SNARKs to increase scalability.[9]
In 2017, Bulletproofs
In 2018, the zk-STARK (zero-knowledge Scalable Transparent Argument of Knowledge)[13] protocol was introduced by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev,[14] offering transparency (no trusted setup), quasi-linear proving time, and poly-logarithmic verification time. Zero-Knowledge Succinct Transparent Arguments of Knowledge are a type of cryptographic proof system that enables one party (the prover) to prove to another party (the verifier) that a certain statement is true, without revealing any additional information beyond the truth of the statement itself. zk-STARKs are succinct, meaning that they allow for the creation of short proofs that are easy to verify, and they are transparent, meaning that anyone can verify the proof without needing any secret information.[14]
Unlike the first generation of zk-SNARKs, zk-STARKs, by default, do not require a trusted setup, which makes them particularly useful for decentralized applications like blockchains. Additionally, zk-STARKs can be used to verify many statements at once, making them scalable and efficient.[1]
In 2019, HALO recursive zk-SNARKs without a trusted setup were presented.[15] Pickles[16] zk-SNARKs, based on the former construction, power Mina, the first succinctly verifiable blockchain.[17]
A list of zero-knowledge proof protocols and libraries is provided below along with comparisons based on transparency, universality, and plausible post-quantum security. A transparent protocol is one that does not require any trusted setup and uses public randomness. A universal protocol is one that does not require a separate trusted setup for each circuit. Finally, a plausibly post-quantum protocol is one that is not susceptible to known attacks involving quantum algorithms.
ZKP system | Publication year | Protocol | Transparent | Universal | Plausibly post-quantum secure |
---|---|---|---|---|---|
Pinocchio[18] | 2013 | zk-SNARK | No | No | No |
Geppetto[19] | 2015 | zk-SNARK | No | No | No |
TinyRAM[20] | 2013 | zk-SNARK | No | No | No |
Buffet[21] | 2015 | zk-SNARK | No | No | No |
vRAM[22] | 2018 | zk-SNARG | No | Yes | No |
vnTinyRAM[23] | 2014 | zk-SNARK | No | Yes | No |
MIRAGE[24] | 2020 | zk-SNARK | No | Yes | No |
Sonic[25] | 2019 | zk-SNARK | No | Yes | No |
Marlin[26] | 2020 | zk-SNARK | No | Yes | No |
PLONK[27] | 2019 | zk-SNARK | No | Yes | No |
SuperSonic[28] | 2020 | zk-SNARK | Yes | Yes | No |
Bulletproofs[29] | 2018 | Bulletproofs | Yes | Yes | No |
Hyrax[30] | 2018 | zk-SNARK | Yes | Yes | No |
Halo[15] | 2019 | zk-SNARK | Yes | Yes | No |
Virgo[31] | 2020 | zk-SNARK | Yes | Yes | Yes |
Ligero[32] | 2017 | zk-SNARK | Yes | Yes | Yes |
Aurora[33] | 2019 | zk-SNARK | Yes | Yes | Yes |
zk-STARK[14][34] | 2019 | zk-STARK | Yes | Yes | Yes |
Zilch[35][36] | 2021 | zk-STARK | Yes | Yes | Yes |
Definition
Originally,[2] non-interactive zero-knowledge was only defined as a single theorem-proof system. In such a system each proof requires its own fresh common reference string. A common reference string in general is not a random string. It may, for instance, consist of randomly chosen group elements that all protocol parties use. Although the group elements are random, the reference string is not as it contains a certain structure (e.g., group elements) that is distinguishable from randomness. Subsequently, Feige, Lapidot, and Shamir[37] introduced multi-theorem zero-knowledge proofs as a more versatile notion for non-interactive zero-knowledge proofs.
Pairing-based non-interactive proofs
Proof systems under the
Under strong
References
- ^ S2CID 248267862.
- ^ a b Manuel Blum, Paul Feldman, and Silvio Micali. Non-Interactive Zero-Knowledge and Its Applications. Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988). 103–112. 1988
- ^ Oded Goldreich and Yair Oren. Definitions and Properties of Zero-Knowledge Proof Systems. Journal of Cryptology. Vol 7(1). 1–32. 1994 (PS)
- ^ Shafi Goldwasser and Yael Kalai. On the (In)security of the Fiat–Shamir Paradigm. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03). 2003
- ^ Rafael Pass. On Deniability in the Common Reference String and Random Oracle Model. Advances in Cryptology – CRYPTO 2003. 316–337. 2003 (PS)
- S2CID 2576177.
- ^ Ben-Sasson, Eli; Chiesa, Alessandro; Garman, Christina; Green, Matthew; Miers, Ian; Tromer, Eran; Virza, Madars (18 May 2014). "Zerocash: Decentralized Anonymous Payments from Bitcoin" (PDF). IEEE. Retrieved 26 January 2016.
- ^ Ben-Sasson, Eli; Chiesa, Alessandro. "What are zk-SNARKs?". z.cash. Retrieved 3 November 2022.
- ^ "Zero-Knowledge rollups". ethereum.org. Retrieved 2023-02-25.
- S2CID 3337741.
- S2CID 3337741. Retrieved 2 December 2022.
- ^ Odendaal, Hansie; Sharrock, Cayle; Heerden, SW. "Bulletproofs and Mimblewimble". Tari Labs University. Archived from the original on 29 September 2020. Retrieved 3 December 2020.
- ^ http://www.cs.technion.ac.il/RESEARCH_DAY_17/POSTERS/michael_riabzev.pdf
- ^ a b c Eli Ben-Sasson; Iddo Bentov; Yinon Horesh; Michael Riabzev (March 6, 2018). "Scalable, transparent, and post-quantum secure computational integrity" (PDF). International Association for Cryptologic Research. Retrieved October 24, 2021.
- ^ a b Bowe, Sean; Grigg, Jack; Hopwood, Daira (2019). "Recursive Proof Composition without a Trusted Setup". Cryptology ePrint Archive.
- ^ "Meet Pickles SNARK: Enabling Smart Contracts on Coda Protocol". Mina Protocol. Retrieved 2023-02-25.
- )
- S2CID 1155080.
- S2CID 3343426.
- ISBN 978-3-642-40084-1.
- )
- S2CID 41548742.
- ISBN 978-1-931971-15-7.
- ^ Kosba, Ahmed; Papadopoulos, Dimitrios; Papamanthou, Charalampos; Song, Dawn (2020). "MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs". Cryptology ePrint Archive.
- S2CID 60442921.
- S2CID 204772154.
- ^ Gabizon, Ariel; Williamson, Zachary J.; Ciobotaru, Oana (2019). "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge". Cryptology ePrint Archive.
- S2CID 204892714.
- S2CID 3337741.
- S2CID 549873.
- S2CID 209467198.
- S2CID 5348527.
- S2CID 52832327.
- S2CID 199501907.
- ^ Computing, Trustworthy (2021-08-30). "Transparent Zero-Knowledge Proofs With Zilch". Medium. Retrieved 2023-02-25.
- S2CID 222069813.
- ^ Uriel Feige, Dror Lapidot, Adi Shamir: Multiple Non-Interactive Zero-Knowledge Proofs Under General Assumptions. SIAM J. Comput. 29(1): 1–28 (1999)
- ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: Perfect Non-interactive Zero Knowledge for NP. EUROCRYPT 2006: 339–358
- ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: Non-interactive Zaps and New Techniques for NIZK. CRYPTO 2006: 97–111
- ^ Jens Groth, Amit Sahai: Efficient Non-interactive Proof Systems for Bilinear Groups. EUROCRYPT 2008: 415–432
- ^ Jens Groth. Short Pairing-Based Non-interactive Zero-Knowledge Arguments. ASIACRYPT 2010: 321–340
- ^ Helger Lipmaa. Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. TCC 2012: 169–189