What is a Zero-Knowledge Proof?

A simple introduction

Zero-knowledge proofs (ZKP) are proofs that an agent knows some particular piece of information, without revealing what you know. Imagine you are playing “Where’s Waldo” with a friend and they claim that they have found Waldo. The simplest way to prove to you that they found him is to point him out directly. However, there are many reasons why they wouldn’t want to do this; notably, this ruins the game for you. In order to really race, without ruining the game, you would need a trusted 3rd party, to whom both of you could point out where you believe Waldo is.

Why is this useful?

Finding Waldo is nice, but the application of ZKP extends to anything that involves asymmetric information. You can imagine something as extreme as proving to a rival nation that you do indeed have a nuclear bomb (without having to set one off). Alternatively, on the blockchain, ZKPs could be used to prove that someone does in fact have enough money to pay a transaction, without revealing their entire net-worth. However, it’s worth observing that the ability to prove something is true without revealing information about the nature of the truth is ultimately only useful with regards to privacy and asymmetric information. If all parties are trusted and their values are aligned, there is no need for anyone to create a zero-knowledge proof, when they could simply create a proof.

Ali Baba’s Cave

One of the most canonical examples of a ZKP is Ali Baba’s Cave.

Imagine a cave with two entrances; at the back of the cave there is a wall that can only be opened with a special password. My goal is to convince you that I know the password. One way to convince a verifier that I know the password without sharing the password itself is as follows:

1. Prover enters the cave along one of the two tunnels (the verifier cannot see them enter)
2. Once the prover has entered, the verifier shouts to them which side (left or right) they wish the prover to exit from.
3. If the prover entered on that side, the prover simply walks out the way they came in. If the prover entered on the other side, they must use the passcode to exit on the verifier’s stated side.
4. After one round, the verifier believes there is a 50% chance the prover knows the code; as either the prover knew the code, or they happened to be on the right side. The verifier and prover can repeat the previous steps as many times, each time halving the possibility that the prover doesn’t know the code, and was just getting lucky.

Images taken from the Wikipedia article Zero-Knowledge Proofs

It should be noted that this is an interactive proof, and in Ali Baba’s Cave you only prove to a single verifier that you in fact know the passcode, as to any onlooker, it is possible the verifier and prover colluded and agreed the commands ahead of time.

So… Where is Waldo?

Returning to the game of “Where’s Waldo”, we present a simple algorithm for proving that you know where Waldo is.

1. Take a large piece of construction paper (at least 3 times the height and width of the page with Waldo in it), and cut a hole the exact shape and size of Waldo out.
2. Move the book behind the construction paper, so that your partner cannot see the book, and orient the book so that Waldo directly falls behind the hole in the page.

At the end of this, your partner should be able to see Waldo, but not see the book or any of Waldo’s surroundings. You have just proven that you know where Waldo is, without revealing information about where he is. Further, this is a non-interactive proof! Once the prover puts up the construction paper, everyone (for the rest of time) will believe that they did in fact know where Waldo was.

It should be noted that, as far as I understand, all zero-knowledge proof are probabilistic. The proof of knowing Waldo’s location might seem like a deterministic proof, but it is actually probabilistic, as the prover could randomly orient the book behind the construction paper and happen to land on Waldo. Zero-knowledge proofs may be probabilistic, but they are generally structured such that it is incredibly improbable.

This article was adapted from Privacy when Everyone is Watching: An SOK on Anonymity on the Blockchain, a report written with Nilaksh Agarwal.