How To Really Understand Zero-Knowledge Proof - An illustration showing a 2-D cross-section of a toroidal cave viewed from top. There is a stick figure that is standing outside the cave and saying "Go where I tell you to". Inside the cave, just inside the entrance is another stick figure replying "Ok!" This stick figure has two possible paths - "A" for clockwise, and "B" for anti-clockwise. At the opposite end of the entrance to the cave is a magic door.

Zero-knowledge proof or zero-knowledge protocol is a technique/method where you prove to someone that you know something without revealing to them what you actually know. If that sounds a bit non-sensical, let me clarify.

Let us say that you know a secret about something. You wish to convince your friend that you know this secret without actually revealing the secret to them. How would you do this? This is where the business of zero-knowledge proofs comes in handy. It turns out that this concept finds very useful applications in the field of cryptography (including cryptocurrencies).

In this essay, I will be covering the intuition behind the notion of zero-knowledge proofs using a couple of illustrated examples. Following this, I will proceed to cover the formal requirements for establishing zero-knowledge proofs. At the end of this essay, you should ideally have an intuitive understanding of the concept as well as the formal requirements for implementing it. Let us begin.

This essay is supported by Generatebg

A product with a beautiful background featuring the sponsor: Generatebg - a service that generates high-resolution backgrounds in just one click. The description says "No more costly photographers" and displays a "Get Started" button beneath the description.

Zero-Knowledge Proof Using a Safe

Suppose that you know the combination to a state-of-the-art safe. This particular safe secures its contents using three different locking technologies. So, it is quite something to have access to.

How To Really Understand Zero-Knowledge Proof — An illustration of a safe with three locking technologies — A key-based-lock, a rotating-wheel-based analogue lock, and a digital lock.
Illustration created by the author

You now wish to prove to your friend that you know the safe’s combination without actually revealing the combination to her. Your method to do so is quite simple. You first ask your friend to write something down on a piece of paper and fold it without revealing the text to you.

Then, you ask your friend to place the folded piece of paper into the open safe (which features a jumbled combination when the door is open). Following this, you ask your friend to shut the safe close. At this point, both of you verify that the safe is locked and cannot be opened by force.

Now, you turn the safe to your point of view such that your friend cannot see you entering the combination. You enter the combination, open the safe, unfold the piece of paper, and read the text. Once you have noted the text in your mind, you fold the piece of paper back, place it inside the safe and lock it once again. You then go on to reveal to your friend the text that she had written on the piece of paper.

If your friend does not find this act convincing, you repeat the process with different pieces of paper/texts enough times to prove to her that you actually know the safe’s combination. Even though you prove your knowledge, note that your friend never got any information about the combination itself. This example is useful to build an initial intuition, but let us take it up a notch with the next example.

Zero-Knowledge Proof Using the Ali Baba Cave

The example we are about to cover now was originally published by Jean-Jacques Quisquater et al. in a paper titled “How to Explain Zero-Knowledge Protocols to Your Children” (linked in the reference section at the end of this essay).

In this hypothetical example, the old Ali Baba cave has been discovered in reality. It was not just fiction, all along! The cave features one entrance and two possible paths around a toroidal geometry with a magical door at the opposite side of the entrance. The door just completes the toroidal circuit when opened.

How To Really Understand Zero-Knowledge Proof — An illustration showing a 2-D cross-section of a toroidal cave viewed from top. There is a stick figure that is standing outside the cave and saying “Go where I tell you to”. Inside the cave, just inside the entrance is another stick figure replying “Ok!” This stick figure has two possible paths — “A” for clockwise, and “B” for anti-clockwise. At the opposite end of the entrance to the cave is a magic door.
Illustration created by the author

Peggy has come to learn about the magic words that open the door, and wants to prove to Victor that she can perform the magic without revealing the magic words to him. To do this, she first goes inside the cave without Victor’s knowledge of which path (of the two) she took.

After this, Victor stands before the fork and shouts out “A” for the clockwise path and “B” for the anti-clockwise path. If Victor shouts “A” and Peggy took path “B”, all she needs to do is open the magic door, and appear from the other side. Assuming that Victor has a 50% chance of calling the same path that Peggy took, Victor needs more convincing.

How To Really Understand Zero-Knowledge Proof — An illustration showing the same cave from before. This time, Victor stands in front of the fork at the entrance, and shouts “B”, while Peggy emerges from the magic door on the side of the anticlockwise exit “B” at the other end of the cave.
Illustration created by the author

If the duo repeats this game 40 times in the honour of the 40 thieves, the probability that Peggy would get all of the instances right purely by luck would be 1 in 2²⁰. In other words, the duo can repeat the game as many times as necessary until Victor is convinced. With this example covered, let us now proceed to examine some of the formal requirements for establishing zero-knowledge proofs.

Formal Requirements for Zero-Knowledge Proof

By formal requirement, any zero-knowledge proof has to satisfy three conditions:

1. Completeness

2. Soundness

3. Zero-Knowledge

Completeness requires that both players stick to the protocol and no one cheats. One interesting thing to note here is that incomplete zero-knowledge proofs explain a lot of magic tricks. The prover (Peggy) uses some kind of deception to convince the verifier (Victor) to perform the magic trick. In an ideal zero-knowledge proof, deception and rule-breaking are not allowed (hence completeness).

How To Really Understand Zero-Knowledge Proof — An illustration of a triangle with “Correctness” written beside the top vertex, “Soundness” written beside the left vertex, and “Zero-Knowledge” written beside the right vertex. Inside the triangle, the following text is written: “Z-K Proof”.
Illustration created by the author

Soundness requires that it is improbable (not impossible!) for a cheating prover to convince an honest verifier. This is what Victor and Peggy achieved by repeating the same game 40 times to achieve a probability of pure luck of 1 in 2²⁰.

Finally, zero-knowledge requires that Victor would never get to know the secret albeit he is convinced that Peggy knows the magic words. Even if an eavesdropper were to listen in on their conversation, the eavesdropper would hear either “A” or “B”. This would give no useful information about the magic words themselves.

However, if Victor used coin-tosses to call out “A” or “B” (to ensure 50% chance of either), and recorded the whole adventure using a video-camera, it would break the zero-knowledge requirement. As to why this is the case, check out the paper I’ve linked at the end of this essay.

Final Remarks

Did you know that I did not choose the names “Peggy” and “Victor” just randomly? It is actually convention in the field of zero-knowledge proofs to refer to the prover as Peggy and to refer to the verifier as Victor.

Furthermore, it is important to note that zero-knowledge “proofs” are unlike mathematical proofs. They just aim to convince the verifier by ensuring that the probability of luck/cheating is negligible. To achieve this, a typical zero-knowledge proof would need to satisfy the formal requirements of completeness, soundness, and zero-knowledge.

This concept finds a wide array of both technological and ethical applications. Anything that requires an authentication system could benefit from zero-knowledge proofs, provided that it is possible to meet the three necessary conditions of completeness, soundness, and zero-knowledge.

Reference and credit: Quisquater et al.

If you’d like to get notified when interesting content gets published here, consider subscribing.

Further reading that might interest you: How To Benefit From Computer Science In Real Life? and How To Really Deal With The Friendship Paradox?

If you would like to support me as an author, consider contributing on Patreon.

Street Science

Explore humanity's most curious questions!

Sign up to receive more of our awesome content in your inbox!

Select your update frequency:

We don’t spam! Read our privacy policy for more info.