Zero Knowledge Proof Example

Zero knowledge proofs are becoming the new buzzword in blockchain circles. But how can you explain it to your 13 year-old son?

As a thought experiment, I decided to role play my own sample of a zero knowledge proof, which requires only minimal math knowledge. Please bear in mind that this is not an academic paper.

Here we go:

Say, Alice and Bob are master builders of jigsaw puzzles. They want to compete to see who assembles a 1000 piece puzzle faster when neither one knows what the finished puzzle should look like.

They ask Charlie, a random man they met outside the toy store, to buy two sets of the same puzzle model. On the complete set, they ask Charlie to enumerate the pieces of both puzzles randomly with unique numbers between 0 and 999. Charlie uses the same number for the same piece on the different sets (i.e. the piece numbered 255 on set #1 is the same piece numbered 255 on set #2, and so on). Charlie then shuffles both sets, throws the pieces of each puzzle in a plastic bag, and gives one set of 1000 numbered pieces to Alice and the other set to Bob. Charlie then goes back to the store and destroys every remaining copy of the puzzle set.

At this point, Charlie is relieved of his duty and both parties no longer use his services ever again.

The competition begins.

Alice, being the faster of the two, completes her puzzle first. She now wants to prove to Bob that she’s holding a complete set, but since she doesn’t trust Bob not to copy her set and claim victory, she wants to prove her win to Bob without revealing what the completed puzzle looks like.

Given these circumstances, Alice is the “prover” and Bob is the “verifier”, they both perform the following procedure.

Bob selects a random piece from his yet unassembled puzzle set and sends Alice the piece number. Alice then photographs this assembled piece connected to other pieces from every side on her puzzle (edge pieces will have one side unconnected and corner pieces two sides unconnected). She sends the photo to Bob to convince him that, indeed, this random piece he selected is part of the assembled puzzle. Bob compares the piece in Alice’s photo to his own copy of the piece and verifies the match. Consider that by doing so, Bob did not learn anything about the structure of the puzzle that he could not deduce by looking at his piece, except that he now knows that this piece is included in Alice’s puzzle.

If Alice completed only half of the puzzle at this point, she only has about 50% chance to correctly photo a random assembled piece.

They now repeat the process again and again, with each photo of assembled piece Alice sends that shows an assembled piece, Bob becomes more convinced that Alice indeed holds a fully assembled set of the puzzle.

If Alice only completed half of the puzzle, her chance of misleading Bob 128 times in a row is 1 in 2¹²⁸, which is clearly impossible. Even if she completed a higher proportion of the puzzle but not the whole set, repeating this process enough times will eventually expose her bluff.

Still, even after 128 attempts, Bob did not learn anything about the full structure of the puzzle.

The beauty of this system is that even if the puzzle has a million or a billion or 2²⁵⁶ pieces, the same method can be used to prove to Bob that Alice completed the puzzle with the same guarantees.

This method is called an interactive zero knowledge proof. Alice has proven a statement to Bob without Bob learning anything about this statement.

But can Alice prove the same without the tedious interactive communication with Bob? It turns out that she can!

Given that the first number received from Bob is x, Alice can calculate x² mod 1000, x³ mod 1000, … ,x¹²⁸ mod 1000 and send Bob 128 photos of the resulting piece numbers.

Calculation mod 1000 is very simple, all you need to do is use the last three digits of any resulting number.

Examples:

0 mod 1000 = 0, 1 mod 1000 = 1, 2 mod 1000 = 2, … ,999 mod 1000 = 999, 1000 mod 1000 = 0, 1001 mod 1000 = 1, … ,2003 mod 1000 = 3, …, 987654321 mod 1000 = 321

Addition works like this:

(2 + 3) mod 1000 = 5

(2 + 999) mod 1000 = 1001 mod 1000 = 1

Multiplication and powers:

(7*11*13) mod 1000 = 1001 mod 1000 = 1

2¹⁰ mod 1000 = (2*2*2*2*2*2*2*2*2*2) mod 1000 = 1024 mod 1000 = 24

Using this method, assuming the random number provided by Bob is 255, Alice starts to calculate powers of this number, she calculates 255² = 255*255 = 65025, she then calculates 65025 mod 1000 to receive 25 as the 2nd number. She then calculates x³, i.e. 255 * 255 * 255 = 25 * 255 = 6375 and, this time, uses the last 3 digits 375 as the next number. She then calculates 375*255 = 95625 to get 625 and so on. If one of the numbers repeats, she adds 1 to it until receiving a new number, wrapping around from 999 to 0 if necessary, and then continuing to multiply by 255.

She then takes the resulting 128 unique numbers and sends the corresponding photos of these assembled pieces to Bob in a single message. Bob can repeat the calculation and verify that indeed these 128 photos correspond to pieces derived from his initial random number, which Alice could not have known in advance.

Bob is now convinced beyond a shadow of a doubt that Alice completed the puzzle with only a single message to Alice and a single response from her. But still Bob, even though he has to admit his defeat, knows nothing he did not already know about the full structure of the puzzle.

It turns out similar methods, albeit much more sophisticated, can be used in the blockchain world to improve privacy and optimize performance. But more on this in another article.