This is the first one of my article series on Zero Knowledge. It will be a very long serie with utmost details. This is why I call it a Deep Dive. Everything from the mathematics behind Zero Knowledge to implementation of known algorithms will be included. Let us start immediately, hold your breath…

Zero Knowledge is an incredibly complicated topic. So I am not going to be brief nor going to throw every word I know in these paragraphs. I am trying to not assume anything about you and your background. If something is off for you or does not make sense to you, feel free to stop and go to the article in which I am trying to cover that topic for you or throw a question to me. I will do my best to answer. I only assume that you have a pencil 📝 and paper or a tablet with you and you are paying attention. If you have any feedback -good or bad- please let me know. This is not only for me, I would love to make improvements, correct myself or clearify anywhere necessary. I will be referring to Zero Knowledge as ZK for fun. Here we go.

TLDR: Anything is considered as information thus anything that is learnt means you have no ZK, including that you have been in a zero knowledge interaction to begin with.

In essence, ZK is a property. Imagine two parties named Peggy (prover) and Victor (verifier). As their names suggest, Peggy is trying to prove $^{[1]}$ something that Victor can then verify$^{[2]}$. We think like the following when we mention ZKness: Victor knows a bunch stuff. He can compute $^{[3]}$ stuff with what he knows. By computation we do not need a fancy performance, we can simply think that Victor can infer other stuff from what he knows. He can reach conclusions with his knowledge. Whatever he knows right now before interacting with Peggy , let us call it his Knowledge Base KB , and let us call what he can see/conclude from his KB his View V . After Victor ’s interaction with Peggy , Victor should still have his KB and V unchanged except with the addition of the fact that Peggy “may” $^{[4]}$ know something, and she “kind of” proved it; or the opposite Peggy “may” not know since Victor tried to verify but the verification failed. Why did I explicitly used “may” and “kind of” is the essence here. Let us dive into a very popular example directly.

Imagine there is a cave as in Figure 1. At the back of the cave, there is a blocked passage only allowing to those with the secret pass phrase(s) get through. So let us run through a Zero Knowledge Scheme to prove to Victor that Peggy “may” know the pass phrase. As we emphasized before, after this interaction Victor should have the same KB and V with the additional fact of Peggy ’s position on that claim. As you can see, there is an entrance to the cave. If Victor is outside, he cannot see the fork of the passages because light does not reach there, let us call them A and B. Peggy goes in, while Victor waiting outside and not being able to see which way Peggy went.

Figure 1 : Anatomy of a plumbus … just kidding, Ali Baba’s Cave Setup Phase (modified cave image from Tuna Celik’s figures from his game)

Victor will wait for a predetermined amount of time, then will himself go in the cave and stand in front of the fork just like in Figure 2. He then asks Peggy to come either from A or B. She either can do it, or not. This implies 2 scenarios, let us examine both of them.

Figure 2 : Ali Baba’s Cave Peggy went into B, Victor asking her to come from A)

Let us say that Victor asked Peggy to come from A for simplicity. Then:

1. If Peggy can come from A, there are 2 possibilities:
   1. She already went into A’s side, so this run did not put to test Peggy ’s claim that she knows the secret pass phrase. In both cases - she knows the secret or not- she will be able to come from A.
   2. She went into B and she knows the secret pass phrase since she could pass through the passage.
2. Peggy cannot come from A as specified by Victor , hence Victor can conclude that Peggy does not know since she failed the test.

The scenario 2 is not particularly interesting since Peggy was not able to fulfill her claim - knowingly or unknowingly- but scenario 1 is fuzzier. We want to see what happens how Peggy can prove what she knows without revealing anything. If scenario 1 took place, Victor cannot conclude anything, the possibility of Peggy telling the truth is 1/2. He can only state that he noted this run as in Figure 3. They would have to repeat the run until Victor is convinced. In a more different terms, when the probability of Peggy lying and succeed all the rounds becomes overwhelmingly small, Victor can be confident that he verified what Peggy claimed. If let’s say they repeated this protocol $x$ times, the probability of Peggy lying and succeeding all the rounds is $\frac {1} {2^x}$ (every run probability of Peggy cheating and happen to be in the right side is $\frac 1 2$)

Figure 3 : Ali Baba’s Cave Victor noted that this run was ‘succesful’ / Unsplash

When $x$ is large enough, it is practically impossible for Peggy to be that lucky but it is still possible even though it is extremely improbable. We use the term negligable probability in this sense. If such a probability -not special to this example- is extremely low, we can confidently say it is not worth consideration. This is why we stated “may” or “kind of”. This property offers much more as we will see later …

Now, let us dissect all the information there is here.

1. Peggy claimed she knew the secret pass phrase and wanted to prove this to Victor .
2. Victor wanted to verify if she told the truth, so they initialize the protocol.
3. They repeate the protocol $x$ times
4. Victor is convinced that she knows the secret.

But this could have been easier, right? Victor can go inside with Peggy and she can show how she opens the passage with the secret pass phrase. Yes, if Peggy is okay for him to learn her secret. He can shut his ears though! If we trust Victor , maybe. In such cryptographic schemes, we would rather minimize the trust. Furthermore, there is something that can pass unnoticed.

Let us imagine that Victor has a camera. He records everything. In a sense, he produces a transcript $^{[5]}$- in this case visually and voiced- of this interaction. In case Victor is untrustworthy, Peggy ’s secret is in danger of leaking.

There is another thing, let us say Victor accompanied Peggy ,till the entrance of the fork A and B, and he records the whole thing - without voices-. It is possible to see her going in the cave, opening the passage, passing through that passage and leaving the cave. Even though we do not hear what she said, we can CLEARLY see that Peggy knows the secret. Victor extracted the information that she knows the secret. He can prove anyone he wants that Peggy knows the secret. What if Peggy does not want anyone else to know that she knows the secret? Here we lost the ZK property, since now, anyone that watches the video knows Peggy is capable of opening the passage gate. She can now become the target of those who want to know the secret and so on. There are lots of points where someone might not desire to be recognized as they know that specific secret. A witness protection program can require such a property. We may even not desire to be known of the beholder of certain amount bitcoins and so on.

Anyway, if Victor would only record from a fixed point say the entrance of the cave(We even let him record the voices now), what can he record? There is Peggy going in the cave and going either in A or B which cannot be seen from the angle of the camera, then Victor goes in and asks her to come out of somewhere either A and B. Then she can or cannot. Let us say she proves that she knows the secret. She is successfully returning from where Victor asked for. If you watch this video, you cannot know for sure that Peggy knows the secret. They can have a pre-determined script for this. Peggy might know what Victor will ask for in advance. Since you cannot be 100% sure, this secures Peggy in a way that no one other than Victor can be convinced of the claim that she knows the secret.

This also means a colluding pair of actors can simulate a pseudo-successful interaction. Victor and Peggy can coordinate such that they can immitate a desired result, say 100 turns of this protocol in favor of Peggy . They can successfully generate a legitimate-looking transcript containing the interaction of Peggy convincing Victor that she knows the secret. The essence here is not that an outsider can be fooled or not. What we think as outsider is not important. The actors in the protocol matter. Even though we cannot discriminate between a real or synthetic interaction, the actors performing the interaction can indeed know the truth. In a synthetic interaction, Victor will not be convinced that Peggy knows the secret. This is all there is. This possibility of fraudulence in fact secures Peggy ’s desire to not get marked as the possessor the secret.

This might not seem important but in the upcoming part, we will see how this becomes important and defines if a protocol has ZK or not. For now, I hope we have a faint understanding of ZK and how we think about it. We will be diving deeper and deeper and conquer ZK, and learn about everything that makes up ZK.

$^{[1]}$ We can think of proofs as the information conveyed that are related to the claim. In our case proofs are almost always bounded mathematically. Imagine a polynomial, $P(x) = (x^{12} - 1)$. If I tell you that I have a polynomial $F(x)$ that is a factor of $P$, I can prove that by simply showing you the division. So in a sense, we are dealing with cases which have proofs, which can be proved mathematically or rather can convince the verifier and computable, thus verified.
$^{[2]}$ Verification can be thought as authentication of the provided information or the claim itself. Here Victor will be trusting probability theory, a.k.a. analysis of random phenomena, to “verify” the claim for himself. So we can basically think that Victor has a verifier function $V(x)$ such that after certain amount of trials in the protocol, $V(x)$ returns either True or False.
$^{[3]}$ As we mentioned a verification function $V(x)$ for verifier, the computation simply can be considered as a function bounded by the computation power of the Verifier. For now, we will not focus on this, but it can be significant to keep in mind that we are dealing with computable elements, meaning that the computation Verifier and Prover performs will not halt. There will be a result of the computation in a reasonable time.
$^{[4]}$ As we will see in the following paragraphs, “may” refers to probabilistically speaking an enormously likely event. This is obtained by the enourmously small error margin $e$ substracted from the overall probability $1$ -> $1-e$ being very very close to $1$.
$^{[5]}$ Transcript refers to the record of the exchanged information. There are case where we refer an actor called the Extractor who has access to internal states of the actors and their performed computations. In our case it can be thought as reading minds of our actors Victor and Peggy. For now, we will think transcript as record of the interaction event in many forms, a written one such as “Peggy went in A, Victor asked for B, Peggy came out from B…”, or a video in which the whole transaction can be watched from. Note that the amount of information can differ from type to type, but of course we can limit this in real world applications.