ZERO KNOWLEDGE PROOFS
DOI:
https://doi.org/10.24867/31BE31PoznanovicKeywords:
Zero knowledge proof, ZK-SNARK, ZK-STARK, CryptographyAbstract
This paper presents zero knowledge proofs, their cryptographic significance and applications. It presents a basic classification: interactive and noninteractive zero knowledge proofs. It presents and compares three protocols of non-interactive zero knowledge proofs: ZK-SNARK, ZK-STARK and Bulletproofs. It presents the quadratic residue problem and proofs it with both interactive and non-interactive zero knowledge proofs. The non-interactive protocol used to prove the quadratic residue problem is ZK-SNARK. The proof is implemented in the Python programming language, using python-snark library.
References
[1] Shafi Goldwasser, Silvio Micali, Sharles Rackof, “The knowladge complexity of interactive proof systems”, Society for Industrial and Applied Mathematics, 1985.
[2] https://schor.medium.com/on-zero-knowledge-proofsin-blockchains-14c48cfd1dd1 (pristupljeno u oktobru 2024.) DOI: https://doi.org/10.24867/31BE31Poznanovic
[4] Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, “Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture”, 23rd USENIX Security Symposium (USENIX Security 14). San Diego, CA: USENIX Association, Avg. 2014., str. 781-796. ISBN: 978-1-931971-15-7. Dostupno na: https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/ben-sasson (pristupljeno u oktobru 2024.)
[5] Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Trome, “Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data”, 2012.
[6] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev, “ Scalable, transparent, and post-quantum secure computational integrity”, 2018.
[7] Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, Greg Maxwell, “Bulletproofs: Short Proofs for Confidential Transactions and More”, 2017.
[8] Szepieniec Alan, Zhang Yuncong, “Polynomial IOPs for Linear Algebra Relations”, Springer International Publishing, 2022., str. 523–552. ISBN: 978-3-030-97121-2.
[9] El-Hajj Mohammed, Oude Roelink Bjorn, “Evaluating the Efficiency of zk-SNARK, zk-STARK, and Bulletproof in Real-World Scenarios: A Benchmark Study”, 2024. Dostupno na: https://www.mdpi.com/2078-2489/15/8/463 (pristupljeno u oktobru 2024.)
[10] Shafi Goldwasser, “ Mathematical foundations of modern cryptography: computational complexity perspective”, 2002. arXiv: cs / 0212055 (cs.CR). Dostupno na: https://arxiv.org/abs/cs/0212055 (pristupljeno u oktobru 2024.)
[11] Goldreich Oded, Micali Silvio, Wigderson Avi., “How to Prove all NP Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design”, sv. 263 1986., str. 171-185.
[12] Ryan Lavin, Xuekai Liu, Hardhik Mohanty, Logan Norman, Giovanni Zaarour, Bhaskar Krishnamachari “A Survey on the Applications of Zero-Knowledge Proofs”, 2024. arXiv: 2408.00243 (cs.CR). Dostupno na: https://arxiv.org/abs/2408.00243 (pristupljeno u oktobru 2024.)
[13] Ronald L. Rivest and Michael L. Dertouzos, “On data banks and privacy homomorphisms”, 1978. Dostupno na: https://api.semanticscholar.org/CorpusID:6905087 (pristupljeno u oktobru 2024.)
[14] Yao, Andrew C., “Protocols for secure computations”, 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). 1982., str. 160-164.
[15] What are zero-knowledge proofs, Dostupno na: https://z.cash/learn/what-are-zero-knowledge-proofs/ (pristupljeno u oktobru 2024.) DOI: https://doi.org/10.24867/31BE31Poznanovic
[17] How is Zcash different than Bitcoin, Dostupno na: : https://z.cash/learn/how-is-zcash-different-thanbitcoin/ (pristupljeno u oktobru 2024.) DOI: https://doi.org/10.24867/31BE31Poznanovic
[19] Sean Bowe, Daira Hopwood, Taylor Hornby, Nathan Wilcox, “Zcash Protocol Specification”, 2020.
[20] What are ZK-SNARKS, Dostupno na: https://z.cash/learn/what-are-zk-snarks/ (pristupljeno u oktobru 2024.)
