This is the third 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
We started this series by introducing the notion of a proof and languages in N P that capture this notion. For these we have witnesses/proofs for the membership in a language (for instance providing a particular 3-way coloring of a graph to prove membership in the set of all 3-color graphs). It was crucial that verification of the proof has to be efficient, though finding the witness itself might be a difficult task itself.
This contrast in power is materialized in the more general definition of an interactive proof. Here we have a powerful prover trying to convince an efficient verifier (a verifier whose computational power is bounded polynomially), where the static proof of an N P language is replaced by the interaction between prover and verifier.
Just like this, nothing would be gained as the powerful prover could just run the verifier’s computation and share the transcript of the whole interaction. The real power comes from allowing randomness on the side of the verifier.
Accordingly the completeness and soundness conditions are relaxed: rather than saying that true statements and only true statements have a proof, we allow the verifier to reject true statements and be convinced by a false one with a negligibly small probability.
The set of languages having an interactive proof as described above is denoted by IP and it has been shown that the class 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). It is widely believed that IP encompasses a more extensive range of languages than N P, and hence we can prove more using interaction than just statically conveying proofs.
In this article we are going to introduce a “feature” that can be added on top of an interactive protocol: zero-knowledge. This is in some sense a very paradoxical constraint defying all our intuition about what would be possible. Given a language L and an element x, the prover wants to convince the verifier that x is in the set L.
This could be by providing a static proof (as in the case of L being a language in N P) or by engaging in an interactive proof. The question is how much information about x the prover needs to convey to the verifier to achieve this goal. In particular, can one do this with no information (a.k.a. in zero-knowledge).
For this we first have to formalize the notion of zero-knowledge. Informally, we want the verifier to obtain no further information than the truth of the statement at the end of the interaction.
There should be “no difference” between a verifier that has engaged in the interactive proof and a verifier that has not interacted with the prover but just assumes that the claim is true. So we have reduced the problem to the one of defining “no difference” in the previous sentence.
At this point there are several reasonable definitions with varying levels of soundness that one could take and accordingly one obtains different notions of zero-knowledge: computational, statistical and perfect zero-knowledge.
Let’s defer the details of these notions a bit and elaborate on the Gedankenexperiment with the two verifiers. On the one side we have a verifier that exchanges messages with the prover. On the other side we have a verifier that assumes the validity of the statement to be proven, but that does not talk to the prover. This lonely verifier could of course talk to itself (so the verifier could make up a conversation with the prover).
Now we say that the interactive argument is zero-knowledge if the transcript of the true conversation between the verifier and the prover looks like what is produced by the simulation, i.e. if there is a simulator which produces something indistinguishable from the true interaction.
The intuition is that if this is the case, then there can be no knowledge leaked by the interactive proof, as the verifier could just run the simulation all by itself (without access to the prover) and obtain something that looks from the perspective of the verifier not any different from the true interaction.
There is an important point here. We are talking about “the verifier” and “the interaction between the verifier and the prover”. Who is this verifier?
If you recall the definition of soundness in an interactive proof, it provided a guarantee against a prover trying to convince the verifier of a false statement. Note that the prover could be malicious and not even follow the protocol agreed upon.
The security notion postulated that the probability of accepting a false statement should be negligible, no matter what prover is involved. So it gives assurance against all possible provers.
Zero-knowledge on the other hand gives us a guarantee against all possible verifiers, honest or dishonest. Even if the verifier deviates arbitrarily from the agreed protocol, it should not be able to learn anything but the validity of the statement. The prover P is fixed and we want that for every verifier V*, there exists a simulator S, such that the interaction of the prover P and the verifier V* is indistinguishable from the simulation S. Note in particular that zero-knowledge is a feature of the prover, reflecting its ability to resist attempts by any verifier to extract knowledge.
Notice that we require that the verifier and the simulator are efficient (run in polynomial time). So above we should more precisely say that “…every efficient verifier V*, there exists an efficient simulator S*,… ”.
An important point is that the simulator with indistinguishable output need only be shown to exist for input x ∈ L. We do not care about the behavior of the simulator for input x not in L.
Now that we have introduced the simulation paradigm, we just need to define the notion of indistinguishability. We first have to clarify what it is that needs to be indistinguishable.
We are interested in the output of the verifier. Remember, however, that in an interactive proof both the prover and the verifier have access to some randomness. In particular, given input x, there is not a unique output, but various outcomes depending on the randomness, each occurring with a different probability. Hence rather than the output, we have a probability distribution for the output (the information of what can be the outcome, with which probability).
The randomness on the prover and verifier side cause some variability (distribution) of the outcome of the verifier. When we talk about indistinguishability of the output of the interaction and the output of the simulator, we mean indistinguishability of the corresponding distributions, and this for all possible inputs x ∈ L.
One way the two distributions are indistinguishable is that they are exactly the same distribution. In such a case we are said to have perfect zero-knowledge. In fact there is a subtle point here and one has to slightly relax the definition: one allows the simulator to fail (abort) with a certain probability and asks that the distribution in case (conditioned on) the simulator does not fail to be the same as the distribution of the output of the corresponding verifier. Wwithout relaxing the definition, there is no non-trivial example of a zero-knowledge proof known.
However the verifier is supposed to be computationally bounded — it is assumed to be efficient, i.e. run in polynomial time. This means that perfect zero-knowledge might be too much to ask.
It would in fact be sufficient that from the viewpoint of a computationally bounded observer the two distributions should be indistinguishable. This is what is called computational indistinguishability and yields the definition of computational zero-knowledge. So in other words in the case of computation zero-knowledge, some information might be leaked, but it cannot efficiently be made use of.
Lastly, if we do not restrict the computational power but only the number samples taken from either distribution to be polynomial, and ask for the probability of distinguishing between the two distributions to be negligible we arrive at the notion of almost perfect zero-knowledge. One can rephrase this notion of indisguishability also in terms of the statistical difference between the two distributions. Hence this notion of zero-knowledge is also called statistical zero-knowledge.
Let us finish by giving a perfect zero-knowledge of graph isomorphism. Recall that two graphs are said to be isomorphic if one can be obtained by the 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. Such a bijection is called an isomorphism.
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. Deciding graph isomorphism is in N P.
By exhibiting the bijection however we reveal more information about the pair of graphs than just the fact that they are isomorphic, for instance we reveal an isomorphism between the two.
We want to convince the verifier of the existence of an isomorphism without leaking any further information. So given two graphs G₀ and G₁, the prover knows an isomorphism π : G₀ → G₁ and wants to convince a verifier of its existence.
The protocol proceeds as follows:
- The prover sends the verifier a random isomorphic copy H of the graph G₁, in particular there is an isomorphism φ : G₁ → H (note that as the graph are isomorphic, this will also be isomorphic to G₀.
- The verifier randomly chooses one of the two graphs G₀ and G₁ and asks the prover to provide and isomorphism from the chosen graph to H.
- If the verifier has chosen G₁, the prover just provides φ. If on the other hand the verifier has chosen G₀, the prover provides φ ○ π.
- The verifier checks that this is really an isomorphism.
Completeness is clear. On the other hand, for soundness, in case the two graphs are not isomorphic, the graph H chosen by the prover can only be isomorphic to one of G₀ and G₁ and when fixing it the prover does not know which one the two verifier will challenge him to exhibit an isomorphism to H to. So he only has a 1/2 chance. Repeating this several times (with new randomness!), one can make the success probability of a cheating prover negligibly small.
The proof of the perfect zero-knowledge property is the more involved part. The verifier could in principle cheat and not choose the challenge graph randomly, but choose one which would allow him (using some smart trick we cannot necessarily think of) to extract some further information.
After all, we do not know how a malicious verifier would deviate from the protocol. So we have to secure ourselves against all possible verifiers. For each verifier we have to show the existence of a simulator that in the case of isomorphic graphs creates an output distribution indistinguishable from the output of the verifier.
The difficulty lies in the fact that we do not know the verifier for which we want to come up with a simulator, but in fact we have to prove that for all verifiers (as exotic as they might be) there exists a suitable simulator. The existence of the simulator is shown by explicitly constructing it (using the verifier itself). The simulator works as follows:
- Randomly select one of the two graphs G₀ and G₁ and generate a random isomorphic copy.
- Feed this to the verifier and get a challenge (a choice of G₀ or G₁).
- If you are lucky and the verifier chooses the graph you had chosen in step 1, just return the corresponding isomorphism. If you are unlucky, abort.
Note that there is a 1/2 chance that the prover will abort but this is allowed by the relaxation introduced in the definition of perfect zero-knowledge.
Now one has to prove that the simulator is efficient (it runs in expected polynomial time) and generates the same distribution (for all cases where it does not abort).
We will not delve into the technical proof here and let you figure out zero-knowledge proof for your favorite problems until our next article.
Want to learn more about this? Follow us:
Twitter | Lens Protocol | LinkedIn | Github | Request Audit
