In this post, I’ll try to demystify one of the most confusing topics in cryptography: zero-knowledge proofs.

However, instead of delving into the mathematical details of ZKPs, my goal is to provide you with an easy-to-remember example that explains the basic concept behind ZKPs in plain English.

To start, let’s take a look at how Wikipedia introduces zero-knowledge proofs:

In cryptography, a zero-knowledge proof is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true. The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information.

I really like this explanation, but it’s kinda hard to wrap your head around these ideas without a concrete example. So, for the remainder of this post, let’s examine what a ZKP could look like in real life.

Suppose two friends, Alice and Bob, both love to play Sudoku. As you may know, Sudoku is a game in which players must find the numbers of all remaining spaces based on the known numbers on a 9x9 grid. The difficulty is that the numbers have to fulfill certain requirements. Each row and column must contain every number from 1 to 9. In particular, this implies that no number appears twice in any given row or column. Furthermore, note that we can slice the 9x9 grid into nine distinct 3x3 grids. Similarly to the constraints for the rows and columns, the final solution of the Sudoku requires that each of these 3x3 grids also contains every number from 1 to 9.

One day, Bob worked on a particularly difficult Sudoku that Alice had designed. After banging his head against the wall for days, Bob went to meet Alice and complained to her that it must be an unsolvable problem. To prove Bob wrong, Alice came up with a clever zero-knowledge proof that

• showed Bob that Alice indeed knew the solution and

• did so without explicitly sharing that solution with Bob.

Here’s how Alice did it: First, she retrieves 81 (= 9x9) blank cards and writes a single digit from 1 to 9 on each card so that, in the end, she’d have nine cards with the digit 1, nine cards with the digit 2, ..., and nine cards with the digit 9. Then, she places the cards on a table in a 9x9 grid according to the correct solution of the Sudoku puzzle. BUT: All the cards are placed face down except the ones that correspond to the "starting numbers" of the Sudoku puzzle.

Now, how can Bob confirm that the cards on the table indeed represent the correct solution without peeking under the face-down cards?

Well, the first step is that Alice lets Bob randomly choose a "verification method". In total, there are three different verification methods Bob is allowed to choose from:

• Verification by rows

• Verification by columns

• Verification by 3x3 blocks

Furthermore, Alice prepares nine empty paper bags. (You'll see why she needs these in a second.) Suppose Bob chooses the "verification by rows" method. In that case, Alice would collect all nine cards of the first row and put them in one of the nine paper bags. She would then repeat this process for all the other rows too. Next, Alice would shake each paper bag to ensure the cards were mixed well. Finally, she would hand the bags over to Bob.

Now, Bob opens each of the bags for verification. If Alice has indeed laid out the correct solution, each bag must contain nine cards with the numbers 1 to 9. And Bob finds that this is actually the case!

After checking the bags, Bob is shocked that the Sudoku is indeed solvable. However, he’s not easily deceived: after some thinking, Bob complains that Alice must have correctly guessed the chosen verification method in advance and that she laid out the cards accordingly, i.e., that she simply placed the numbers from 1 to 9 in each row without actually knowing the solution. In other words, Bob claims that Alice was trying to trick him and got lucky by anticipating that he would choose the "verification by rows" method.

Of course, Bob could be correct in this assumption. However, there's an easy way for Alice to prove him wrong: Repetition.

Let's look at this more closely for a second: The probability of Alice passing Bob's verification by trickery is 1/3. However, the probability of her successfully repeating this trick is 1/9.

Now, suppose Bob goes totally overboard and wants Alice to repeat the entire process ten times. In that case, the probability of Alice passing all ten verification procedures without knowing the actual solution is 0.0016 %. Pretty tiny, huh?

After tirelessly performing 20 verifications, Bob reluctantly admits that Alice knows the solution to the answer. Because, after all, the probability of Alice passing the verification by trickery is, by now, 1 in 3.5 billion.

And with that, Alice successfully convinced Bob that she knew the correct solution to the Sudoku without revealing that solution to him!

In this post, I’ll try to demystify one of the most confusing topics in cryptography: zero-knowledge proofs.

However, instead of delving into the mathematical details of ZKPs, my goal is to provide you with an easy-to-remember example that explains the basic concept behind ZKPs in plain English.

To start, let’s take a look at how Wikipedia introduces zero-knowledge proofs:

In cryptography, a zero-knowledge proof is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true. The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information.

I really like this explanation, but it’s kinda hard to wrap your head around these ideas without a concrete example. So, for the remainder of this post, let’s examine what a ZKP could look like in real life.

Suppose two friends, Alice and Bob, both love to play Sudoku. As you may know, Sudoku is a game in which players must find the numbers of all remaining spaces based on the known numbers on a 9x9 grid. The difficulty is that the numbers have to fulfill certain requirements. Each row and column must contain every number from 1 to 9. In particular, this implies that no number appears twice in any given row or column. Furthermore, note that we can slice the 9x9 grid into nine distinct 3x3 grids. Similarly to the constraints for the rows and columns, the final solution of the Sudoku requires that each of these 3x3 grids also contains every number from 1 to 9.

One day, Bob worked on a particularly difficult Sudoku that Alice had designed. After banging his head against the wall for days, Bob went to meet Alice and complained to her that it must be an unsolvable problem. To prove Bob wrong, Alice came up with a clever zero-knowledge proof that

• showed Bob that Alice indeed knew the solution and

• did so without explicitly sharing that solution with Bob.

Here’s how Alice did it: First, she retrieves 81 (= 9x9) blank cards and writes a single digit from 1 to 9 on each card so that, in the end, she’d have nine cards with the digit 1, nine cards with the digit 2, ..., and nine cards with the digit 9. Then, she places the cards on a table in a 9x9 grid according to the correct solution of the Sudoku puzzle. BUT: All the cards are placed face down except the ones that correspond to the "starting numbers" of the Sudoku puzzle.

Now, how can Bob confirm that the cards on the table indeed represent the correct solution without peeking under the face-down cards?

Well, the first step is that Alice lets Bob randomly choose a "verification method". In total, there are three different verification methods Bob is allowed to choose from:

• Verification by rows

• Verification by columns

• Verification by 3x3 blocks

Furthermore, Alice prepares nine empty paper bags. (You'll see why she needs these in a second.) Suppose Bob chooses the "verification by rows" method. In that case, Alice would collect all nine cards of the first row and put them in one of the nine paper bags. She would then repeat this process for all the other rows too. Next, Alice would shake each paper bag to ensure the cards were mixed well. Finally, she would hand the bags over to Bob.

Now, Bob opens each of the bags for verification. If Alice has indeed laid out the correct solution, each bag must contain nine cards with the numbers 1 to 9. And Bob finds that this is actually the case!

After checking the bags, Bob is shocked that the Sudoku is indeed solvable. However, he’s not easily deceived: after some thinking, Bob complains that Alice must have correctly guessed the chosen verification method in advance and that she laid out the cards accordingly, i.e., that she simply placed the numbers from 1 to 9 in each row without actually knowing the solution. In other words, Bob claims that Alice was trying to trick him and got lucky by anticipating that he would choose the "verification by rows" method.

Of course, Bob could be correct in this assumption. However, there's an easy way for Alice to prove him wrong: Repetition.

Let's look at this more closely for a second: The probability of Alice passing Bob's verification by trickery is 1/3. However, the probability of her successfully repeating this trick is 1/9.

Now, suppose Bob goes totally overboard and wants Alice to repeat the entire process ten times. In that case, the probability of Alice passing all ten verification procedures without knowing the actual solution is 0.0016 %. Pretty tiny, huh?

After tirelessly performing 20 verifications, Bob reluctantly admits that Alice knows the solution to the answer. Because, after all, the probability of Alice passing the verification by trickery is, by now, 1 in 3.5 billion.

And with that, Alice successfully convinced Bob that she knew the correct solution to the Sudoku without revealing that solution to him!