Zero-Knowledge Proofs Simplified

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.

A term that’s reached buzzword prominence in blockchain circles is “Zero-Knowledge Proofs”. Since most people now know that transactions in Bitcoin and Ethereum are on a very public ledger for all the world to see, zero-knowledge proofs have been touted as some kind of ultimate privacy tool.

But what are Zero-knowledge proofs?

References

• [1] 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.
• [2] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186–208, 1985.
• [3] 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.
• [4] 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.

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 😄