This is the second article from our series exploring ZK fundamentals, zero knowledge proofs and related notions.
ZK Fundamental series:
📚 Part I: What is a proof?
📚 Part II: Interactive Proofs
📚 Part III: Zero-Knowledge
📚 Part IV: The Fiat-Shamir Transform
📚 Part V: Succinctness
📚 Part VI: Intermediate representations
In our last article we talked about how computation can be rephrased in terms of membership in a set (a language). We elaborated on the notion of a mathematical proof (a sequence of symbols certifying that a given statement belongs to the set/language of true statements) and how this idea is captured nicely by the class N P: elements of a language in this class have witnesses/proofs, which are efficient to verify (i.e. in polynomial time).
Whether finding a proof is also efficient in this case is, however, not so clear, and in fact a big open question.
We finished by observing that this notion of a proof is very static and does not involve any interaction between the prover and the verifier, except the proof itself once. In real life however we have different ways of convincing people of the truth of our claims, namely through interaction: you (the prover) interact with the verifier and defend your claim. If you manage to satisfiably respond to all challenges of the verifier, you will have convinced the verifier of your claim.
An intriguing question is whether anything is gained by allowing such interactions in our theoretical setup as well. So can we prove more by allowing interaction, i.e. is the class of languages for which you can provide an efficient interactive proof of membership larger than the ones with non-interactive proofs (N P).
The answer is practically yes, as there are problems which are believed to be not in N P (we do not know a way to provide an efficient static proof), for which we can give efficient interactive proofs.
Theoretically, however, the answer is unknown, as for all such examples we do not know if the static proof does not exist, or if it is just our inability to find one and someone with a clever idea will come up with an ingenious static proof tomorrow.
And… (inter)action!
So let’s start by introducing interactive proofs.
Take 1: an incomplete attempt.
We will have two parties, a prover (P) and a verifier (V). Given input x (which P claims to be in the language) they will engage in some interaction, at the end of which the verifier will decide to accept or reject. So the verifier sends a message to the prover, who responds with an answer, after which the verifier sends another challenge, which gets a response from the prover, and so on. At the end of this interaction the verifier either accepts or rejects.
Given the verifier V, we define the language L to be the set of all inputs x, such that V can be convinced by some prover P, i.e., where for some prover P, at the end of the interaction of P and V on input x, the verifier returns accept. Not that we are fixing the verifier, but there can be many provers.
- For each x in L there will be at least one prover P (the honest prover) capable of convincing V of this. But with a small argument, we can interchange the quantifiers: if for each x there is a prover P(x) convincing V, then there is a prover P’, who for each x convinces V, namely the prover who for each x just simulates the capable prover P(x). This property is called completeness: true statements should have a convincing proof.
- On the other hand for x not in L, there is should be no prover P capable of tricking V to believe the claim. This property is called soundness.
Power To The People — Take 7
How to define efficiency for such an interaction?
A way to define efficiency is to restrict the computational power of the prover and the verifier and deem those languages efficient, that can be decided by these impeded parties. So how much computational power should the prover and the verifier have?
As in the case of the class N P, we only require the verification of the proof to be efficient: finding a proof itself might be very difficult, but we do not care. For N P we want efficient verification.
Translated in the interactive setup, we want the verifier to run in time polynomial in the size of the input x. In particular the number of rounds of interaction (the messages back and forth, also known as the round complexity) between the verifier and the prover, as well as the size of each message should be polynomial in the size of x.
So we assume the prover is almighty and has unlimited computational power (might even solve undecidable problems), whereas the verifier is required to be efficient, i.e., to run in polynomial time.
Do we gain anything?
Now the big question is: with all the new bells and whistles can we efficiently prove statements we could not prove before statically?
Let’s think… the prover only sends polynomially many messages of polynomial size, and receives challenges from the verifier. An almighty prover could easily do the work of the verifier as well and compute all responses of the polynomial verifier by itself and foresee the output of the whole interaction so there is no need to wait for the response of the verifier.
Such a prover could just send all its messages in the interaction to follow at the very beginning as a single polynomial sized aggregate w, which the verifier could read bit by bit rather than responding, and be convinced by. But this is not at all different from a N P witness w in the static case. So whatever we can prove with such an interaction, we can prove already with a single message. It seems we do not gain anything.
Take 2: Randomness saves the day
It turns out that giving the verifier access to randomness rendering it probabilistic unleashes the power of interaction. The final judgment of the verifier will depend on its randomness, hence there is a chance that it will be wrong (otherwise, if all random input would give the same result, there would be no gain from randomness to be hoped for).
We want to have a tiny probability of the verifier being wrong. This error can be in two forms: the verifier can wrongfully reject a true statement. We don’t want this to happen frequently, so we want that for x in the language the probability of V accepting to be large for an honest prover. This is called completeness.
On the other hand the verifier should not accept wrong statements (called soundness), so for x not in the language, for all possible provers the probability of the verifier accepting should be small. Here the probability is calculated over the randomness of the verifier. A language, for which there exists such a probabilistic verifier is said to have an interactive proof system, and the class of all such languages is denoted by IP.
What do we gain?
So now the big question is: what do we gain? Clearly N P ⊆ I P. But is this containment strict? In other words, is there a language in IP which is not in N P? So is there a language where elements have interactive proofs but no static proofs?
It is widely believed that this is indeed the case. In fact, it can be shown that IP is equal to PSPACE, the class of languages that can be decided using only a polynomial amount of space (but for instance requiring exponential time).
Just as the question whether P = N P, the question N P = PSPACE is still open. In fact there is a whole hierarchy of classes where (in)equality is waiting to be settled.
Let’s see interactive proofs in action!
Example: Graph (Non-)Isomorphism
Two graphs are said to be isomorphic if one can be obtained by relabeling of its vertices. In other words, they are isomorphic if there is a bijection between the vertices of the two graphs, preserving all adjacency relations: two vertices of the first graph are adjacent (connected by an edge), if their image in the second graph (under the bijection) are adjacent.
Given two graphs, it might be difficult to find an isomorphism between them, but once you have one, it is immediate to prove it to someone else: just exhibit the bijection and the verifier can check it efficiently. Hence deciding graph isomorphism is in N P (but it is not known whether it is in P or not, i.e., if given two graphs one can decide efficiently if they are isomorphic).
How about graph non-isomorphism GNI? Can we prove to someone efficiently that two graphs are not isomorphic? Is GNI in N P? The answer is not known. So for two general graphs that are not isomorphic, we do not know how to write down a proof of non-isomorphism that can be verified efficiently. We can, however, find an interactive proof! So GNI is in IP.
The idea of the interactive proof is nice and simple. As an analogy, imagine you want to prove that regular and decaf coffee taste differently (they are not “isomorphic”). A way to do that would be to take a cup of each, and close your eyes, and have someone randomly hand you one of these and you make your best guess.
If your guess is correct, you will have proven that you can distinguish them, hence that they do not taste the same. But wait! What if they do taste the same and you just guessed randomly? You would be right with a probability of 1/2. What you could do is to repeat the experiment again, say n times, and deem it a valid proof if you guess right on all n of them.
So in case there is no difference in taste and hence you cannot spot any difference, you really need to be very lucky to get it right n times in a row, namely the probability is 1/2ⁿ, and you can make this as small as the verifier wants by just repeating it more and more times by increasing n. So you can make the soundness error as small as you want.
It should be clear now how an interactive proof system for GNI can be constructed. To prove that two graphs G and H are not isomorphic, you let the verifier secretly choose one of them at random, and relabel its vertices.
If you are able to tell the verifier which of the two graphs were chosen, and you can do this correctly say n times in a row, then with overwhelming probability the two graphs will not be isomorphic. If they were isomorphic, the same graph can be obtained by relabeling either of the two graphs, so it is impossible for the prover to determine which of the two graphs was used as input to the relabeling.
Note that here you (the prover) still need to find an isomorphism between G or H and the graph that was presented to you. This might not be an easy task, but that is not of relevance. The process should be easy for the verifier.
Now we are ready to formally define a zero knowledge proof. So stay tuned for the next article from the series!
Want to learn more about Veridise?
Twitter | Lens Protocol | LinkedIn | Github | Request Audit
