Zero-Knowledge Proofs (ZK or ZKP) are a fascinating topic in modern cryptography. It allows one party, the Prover, to prove they know a fact without revealing what the fact is. In this blog series, we will explore the definitions around ZK, which may not make sense at first glance or are covered with complex math that is hard to grasp. My goal is to explain these definitions using common sense. Yet, from time to time, I will use simple math to give examples.
History of ZK
Everything started with a Big Bang. Then, after 13.7 billion years, a famous German mathematician, David Hilbert, published a list of unsolved problems (at the time) in mathematics. Some of them were solved shortly after, but some are still unsolved. Particularly, the second question asked, “THE COMPATIBILITY OF THE ARITHMETICAL AXIOMS.” Hilbert was a prominent advocate of formalism in the philosophy of mathematics, and he believed mathematics is a formula game. Almost three decades later, he revised this problem and divided it into three parts:
- Is mathematics complete?
- Is mathematics consistent?
- Is mathematics decidable?
While they look like innocently simple questions, completeness, consistency, and decidability are formal logic terms. The first question asks if we start from a set of axioms (undeniable and unprovable true statements), can every mathematical statement be proved using logical reductions. Then, naturally, the second question asks if there can be two provable statements that contradict each other. The last question goes even further by asking if we can even decide which problems are solvable (i.e., there exists an answer or proof that there is no answer).
All questions were negatively answered in the following years. But these results changed the history of humanity forever! Mathematicians and philosophers of that time invented tools to prove the answer is NO. One such tool is a Turing Machine.
A Turing Machine models computation in an abstract way. Let’s say you want to solve a (mathematical) problem. That is your input. Let’s think of an “algorithm” that computes the solution. The algorithm is kept simple: it reads elements from memory (an infinite tape), applies a specific rule (transition function), and saves into memory again. The Turing Machine runs the “algorithm” until it stops. Notice the similarity with Hilbert’s formula game view. But how do we know that the machine will stop?
This is the famous “Halting Problem.” Alan Turing proved that the Halting Problem is undecidable, i.e., there is no algorithm that can answer YES or NO to all questions if the problem is solvable. Be careful, saying there is no algorithm to decide is fundamentally different than saying the answer to the problem is no. Furthermore, if we think of mathematical proofs as a finite sequence of logical reduction steps, what the Turing machine does is produce the proof.
This is the birth of computer science. Throughout the last 100 years, people categorized problems based on the properties of a Turing Machine that would produce a solution to the given problem. For example, how many steps would the machine take to find the solution? That is time complexity. Then, how much memory it would consume is space complexity.
Fast forward to the 1980s. Three computer scientists, Shafi Goldwasser, Silvio Micali, and Charles Rackoff, published a seminal work, “The Knowledge Complexity of Interactive Proof Systems,” where they laid the foundations of zero-knowledge proofs. The paper introduces another dimension to complexity – knowledge complexity.
Interactive Proof Systems
We defined the proof as a transcript of a single Turing Machine where our purpose was to prove a certain (mathematical) statement. The interactive proof system involves two Turing Machines (see the photo): one generates the proof and the other verifies it. Intuitively, they are called the Prover and the Verifier. The GMR paper requires three properties for the system:
- That it should be possible to “prove” a true theorem
- That it should not be possible to “prove” a false theorem
- That communicating the “proof” should be efficient. Namely, regardless of how much time it takes to come up with the proof, its correctness should be efficiently verified.
Nowadays, we call the first and second properties completeness and soundness, respectively.
An important result in that paper is that there exist Interactive Proof systems where no additional knowledge about the theorem is sent to the Verifier, yet she is convinced that the theorem is true. Hence, proofs in such Interactive Proof systems are called zero-knowledge proofs.
How would it be possible to prove a theorem without giving more information about the theorem? It is a bit technical, but the reasoning is if the Prover’s Turing Machine does not write any additional knowledge on the shared tape, but only random bit strings (from the RANDOMNESS TAPE), the resulting proof should be zero-knowledge. For example, let’s say the Prover wants to prove the “25 is a perfect square” theorem. The trivial proof would be sending 5 explicitly to the Verifier. But this proof not only proves the theorem itself but also gives additional knowledge about the theorem, namely, the square root of 25. Thus, it is not zero-knowledge. Can you come up with zero-knowledge proof that “25 is a perfect square”?
Summary
Zero-Knowledge Proofs let someone prove they know something without revealing what it is. This idea started with David Hilbert’s questions about math and was advanced by Alan Turing’s work on computation. In the 1980s, Goldwasser, Micali, and Rackoff formalized ZK proofs, which involve a Prover and a Verifier. These proofs confirm the truth without sharing extra information, making them essential in cryptography.
In the upcoming post, I will discuss the difference between Honest-Verifier Zero-Knowledge (HVZK) and full Zero-Knowledge (ZK). Thanks for reading!
References:
- S Goldwasser, S Micali, and C Rackoff. 1985. The knowledge complexity of interactive proof-systems. In Proceedings of the seventeenth annual ACM symposium on Theory of computing (STOC ’85). Association for Computing Machinery, New York, NY, USA, 291–304. https://doi.org/10.1145/22145.22178