Zero-Knowledge Proofs Simplified

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

  • Part 1: Buterin, Vitalik. “Quadratic arithmetic programs: from zero to hero.”, Medium. (2016).
  • Part 2: Buterin, Vitalik. “Exploring Elliptic Curve Pairings.”, Medium. (2017).
  • Part 3: Buterin, Vitalik. “Zk-SNARKs: Under the Hood”, Medium. (2017).

• Vitalik Buterin’s introduction to STARKs

  • Part 1: Buterin, Vitalik. “STARKs, Part I: Proofs with Polynomials”, Vitalik.ca. (2017).
  • Part 2: Buterin, Vitalik. “STARKs, Part II: Thank Goodness It’s FRI-day”, Vitalik.ca. (2017).
  • Part 3: Buterin, Vitalik. “STARKs, Part 3: Into the Weeds”, Vitalik.ca. (2018)..

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 😄