A Mathematical Introduction to ZK Proofs
The idea behind zero-knowledge proofs, from a mathematical PoV.
This article is the second part of a series of articles explaining how ZK-based architecture works. You can find the first article here.
Proof that a statement X is true typically comprises some explanation of why X is true. Let’s say I have a number n, whose value is 55,928,476,475,257,570,758,258,732,446,588,119,121,542,833,544,497,108,841. n is the product of many large prime numbers, so finding its factors is a non-trivial task. Can I prove that one of n’s prime factors ends with 3 – without revealing its factorization?
Providing mutually distrustful parties with a means to reveal “predetermined pieces of information” is an archetypical cryptography problem. In such situations, the parties involved possess secrets and wish to divulge parts of those secrets. How can we verify the newly revealed parts of these secrets without disclosing other parts of the secret? Is there a way to prove a statement without yielding anything beyond its validity? When such proofs do exist, they are called zero knowledge proofs, which are crucial to the construction of various cryptographic protocols.
Zero knowledge (ZK) proof systems are unusual in that they can be convincing while yielding nothing beyond the claim's validity. Simply put, this means that having a ZK proof that a statement X is true is equivalent to being told by a trusted source that the assertion holds. You could see a ZK proof that n has a prime factor ending with 3, and you’d still be no closer to learning n’s prime factors.
One thing is evident: ZK proofs are amazing. But how do we obtain them? We must first discuss the notion of proofs and what we mean by zero knowledge in order to get there.
The Notion of Proofs
Static Objects or Interactive Processes?
In mathematics, a proof is a fixed sequence of statements that are either self-evident or can be deduced from previous statements following commonly accepted rules. In logic (that is, the formal study of proofs), the commonly accepted statements are known as axioms, whereas the commonly accepted rules are called derivation rules.
For example, In Euclidean geometry, statements like “the sum of all angles in a triangle equals 180 degrees” are facts. Proofs are step-by-step derivations of the statements from the five fundamental postulates. The efficient nature of the verifying algorithm is a feature of such a proof system. In fact, that is the entire purpose of a proof– to provide a series of symbols that make it simple to confirm if a statement is true. Such mathematical proofs have two properties:
Proofs are thought of as static objects.
The proofs are at least as important as their underlying theorems.
However, the concept of a proof is significantly broader in other realms of human endeavour. Rather than a fixed object, a proof is a process used to substantiate the validity of an assertion. Additionally, in many real-life circumstances, the consequences of the proof are deemed to be more important than the proof itself.
To sum up, proofs in "canonical" mathematics are static, whereas proofs in practical applications are dynamic (that is, they are established via an interaction). In our case, where proofs are employed as tools within cryptographic protocols, a dynamic interpretation of the concept of a proof is more pertinent. Furthermore, for the concept of a ZK proof to be non-trivial, a dynamic interpretation (at least in a weak sense) is necessary.
To get to the notion of zero knowledge protocols, Goldwasser and Micali had to take another step– model our dynamic interpretation of proofs as interactive probabilistic protocols between a Prover and a Verifier.
Mental Model
Most cryptographic protocols deal with situations where two parties trusted each other but were concerned about an outsider having access to their communication channel. Now, because the parties do not necessarily trust one another, the situation is somewhat more complicated. In this situation, there is always a "prescribed" or honest course of action that a particular party should follow. However, since we generally don't want the other parties’ security to depend on someone else's good intentions, we also examine the scenario in which a party uses an arbitrary malicious strategy. We occasionally also take into account the honest but odd case in which the adversary is non-aggressive and merely gathers information without deviating from the prescribed course of action.
Prover and Verifier
We’d learnt that:
The Prover P has unbounded computation power, but is untrustworthy.
The Verifier V has bounded computation power, but is always assumed to be honest.
Be it math or real life, the notion of a Prover is implicit in all cases. The Prover is the (occasionally hidden) entity providing the proof. Contrarily, such discussions emphasise the Verification process and the role of Verifier tends to be more explicit. Proofs are described in terms of the verification process. The verification process is rather straightforward, and the prover—the party or individual providing the proof—is responsible for carrying the burden.
The complexity class NP, which may be thought of as a class of proof systems, captures the asymmetry between the complexity of the theorem-proving work and the complexity of the verification task. There is an efficient verification process for proofs of assertions of the form "x ∈ L" in each language L ∈ NP. Each L ∈ NP is characterised by a polynomial time recognisable relation R.
We can say that the the verification process for membership claims of the type x ∈ L consists of applying the polynomial time-method for detecting R to the claim (denoted by x) and a prospective proof (denoted by y). Any y satisfying (x, y) ∈ R is considered proof of membership of x ∈ L. Hence, only these and correct statements (that is, x ∈ L) have proofs in this system. While the verification process is easy, coming up with proofs might be difficult.
It is important to take note of the lack of trust that underlies any proof system. There is no requirement for a proof if the Verifier believes the Prover. Hence, whenever we describe a proof system, one takes into account a situation where the Verifier is suspicious of the Prover and is also skeptical of everything the Prover claims.
Completeness and Soundness
Two properties that fundamental to the very notion of a proof system are:
Soundness: Soundness asserts that a Verifier cannot be tricked into believing false statements, no matter what the Prover does in order to fool the Verifier.
Completeness: Completeness captures the ability of a Prover to convince the Verifier of true statements. If a statement is true, the Prover will ultimately be able to convince the Verifier.
Note: While no false statement can be proved, not every true statement has an efficient proof system in which that statement can be proved. The gist here is that we confine ourselves to the class of valid statements that do have “efficient proof systems”, and this efficiency is in turn associated with the efficiency of the verification process.
Interactive Proof Systems
Let’s start with an informal example: Proof of Tetrachromacy.
Most humans like us have plain regular vision– the basic subscription. We are trichromats– we have three types of cone cells in our eyes. This is the reason we mistakenly think the colour of the sky is blue instead of purple. Yes, the sky is purple. Surprise! Although the colour of the sky is quite different from the blue of a rainbow, the projection of the sky’s colors on our cones is the closest to blue.
There are a few (very very few) people who have four types of cones. The number of colours such tetrachromats can see is a lot higher than us. Here is an interesting question: how can such a person prove to another that they are, in fact, a tetrachromat?
One solution: If Alice is a tetrachromat, she could be able to tell the difference between two pieces of plastic that would otherwise be identical in colour to a trichromat. She wants to prove to a trichromatic Bob that the two pieces are different from one another. They do the following process n times:
Bob flips a coin after Alice turns her back on him. Based on the result of the coin toss, Bob has a 1/2 probability of leaving the pieces exactly as they are, and a 1/2 probability of switching the right piece with the left piece. Alice then guesses whether Bob had exchanged the pieces or not.
If the process had taken place only once, then there was a 50% chance that Alice just got lucky with her guess. But if Alice successfully guesses the answer in all the n repetitions, then Bob will have 1 – 2⁻ⁿ confidence that Alice is telling the truth and that the pieces are truly different. The probability of Alice fooling Bob reduces as the experiment gets repeated n times.
Interesting, right? This is the gist of interactive proof systems. We’ll move to a mathematical example now.
Definition
A pair of interactive Turing machines (P, V) is called an interactive proof system for a language L if machine V is polynomial-time and the following two conditions hold:
Completeness: For every x ∈ L, Pr[〈P, V〉(x) = 1] ≥ 2/3
Soundness: For every x ∈ L and every interactive machine B,
Pr[〈B, V〉(x) = 1] ≤ 1/3
The error probability in this definition can be made exponentially small by repeating the interaction many times.
Zero Knowledge Proofs
No Knowledge Gain
So, we know that zero knowledge proofs are proofs where the Verifier gains no knowledge beyond the validity of the assertion. There are two questions we can ask here: what is knowledge and what does a gain in knowledge mean. We’re not philosophers, so we’ll safely avoid the first question and only pay attention to the second. We demonstrate a generic scenario where it’s safe to claim that no knowledge has been gained.
Let’s consider a conversation between Alice and Bob. Bob is quizzing Alice about a huge graph that is known to both of them. First, Bob asks Alice if the graph is Eulerian. Bob doesn’t gain any knowledge from Alice’s answer here because he could’ve simply found the answer himself by running a simple linear-time decision procedure.
However, what if he asks Alice if the graph is Hamiltonian and Alice (somehow) answers this question? Here, we can’t say that Bob hasn’t learned anything because we don’t know of a reliable method where Bob could have independently figured out the answer (and assuming P ≠ NP, no such efficient procedure exists). Therefore, we claim that Bob has learned from the interaction if his computational ability with regard to the publicly known graph has increased (i.e., if after the interaction he can easily compute something that he could not have efficiently computed before the interaction).
On the other hand, if Bob can efficiently compute the same information about the graph independently (from the graph) as he can after interacting with Alice, then we say that Bob has not learned anything from the interaction. In other words, Bob only learns something if he obtains the result of a calculation that surpasses his computational ability.
Mental Model
In essence, the notion of zero knowledge states that although we cannot stop the Verifier from using an efficient algorithm S on the public input, we nevertheless want to make sure that this is the most that they can learn from this interaction. Many cryptographic applications now define security in accordance with this simulation paradigm.
We bound what a Verifier can learn by postulating a hypothetical adversary under harder conditions (they can’t interact with the prover). We ensure that the Verifier can’t learn anything the hypothetical adversary couldn't have learned either. This is just phrasing security as the existence of a simulation, unlike the commonly used laundry list of bad outcomes that aren’t allowed to happen.
Definition
Let (P, V) be an interactive proof system for some language L. We say that (P, V) is zero knowledge if for every probabilistic polynomial-time interactive machine V∗ there exists a probabilistic polynomial-time algorithm M∗ such that the following two random variables are computationally indistinguishable:
{〈P, V*〉(x) } (that is, the output of the interactive machine V∗ after it interacts with the interactive machine P on common input x)
{ M∗ (x) } (i.e., the output of machine M∗ on input x)
Machine M∗ is called a simulator for the interaction of V∗ with P.
This marks the end of the second part. The next part will focus on the classes of problems that can have ZK proofs.
Subscribe to stay tuned!
If you have any suggestions, or comments or just want to send a meme– you can find me on Twitter at @gryptooo . Thanks for reading. :)