Zero-Knowledge Proofs Simplified
Demonstrating how these go beyond 'take my word for it' with a simple python example
| UPDATED
UPDATE 11/13/2019: This post originally had a Where’s Waldo image used as an analogy, but it turns out the publisher didn’t like that. I’ve replaced it with a different example. UPDATE 06/20/2020: Scott Moses Sunarto has created “Dark Forest”, a massively multiplayer online real-time strategy (MMORTS) space conquest game build on top of the Ethereum blockchain. It’s based on the concept of ZK-SNARKS mentioned in this article, as well as the popular “The Body Problem” Trilogy. I had no involvement in the creation of this game, but if you enjoy this post below you should definitely go check it out. UPDATE 10/21/2021: zk-SNARKs are great, but you know what might do them better? zk-STARKs. My current hypothesis is that zk-SNARKs will become more popular for web3 applications, before being quickly taken over by zk-STARKs.
References
- Gleick, James. “A new approach to protecting secrets is discovered.” The New York Times 18 (1987): C1.
- Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. Journal of the ACM(JACM), 38(3):690–728, 1991.
- Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186–208, 1985.
- Ronen Gradwohl, Moni Naor, Benny Pinkas, and Guy N Rothblum. Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles. In International Conference on Fun with Algorithms pages 166–182. Springer, 2007.
- Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE transactions on fundamentals of electronics, communications, and computer sciences, 86(5):1052–1060, 2003.
- Green, Matthew. “Zero knowledge proofs: an illustrated primer.” Cryptography Engineering (2014).
- What are zk-SNARKs?
- “The Functionality of zk-SNARK” challenge set in “The Hunting of the SNARK”.
- “Probabilistic Proof Systems” course notes
-
Vitalik Buterin’s introduction to SNARKs
-
Vitalik Buterin’s introduction to STARKs
Cited as:
@article{mcateer2019zkproof,
title = "Zero-Knowledge Proofs Simplified",
author = "McAteer, Matthew",
journal = "matthewmcateer.me",
year = "2019",
url = "https://matthewmcateer.me/blog/zk-proofs-simplified/"
}
If you notice mistakes and errors in this post, don’t hesitate to contact me at [contact at matthewmcateer dot me
] and I will be very happy to correct them right away! Alternatily, you can follow me on Twitter and reach out to me there.
See you in the next post 😄