Zero-knowledge proofs in the real world

‘It was a really good film and it was so sad and unexpected when the hero dies at the end’…

A film critic has to prove to someone that a film is worth going to see (or not), but in doing so they must not give away knowledge of certain aspects of the plot. No ‘spoilers’.

This is proving a claim about a thing while keeping some aspects of the thing itself hidden. In extreme cases you can prove a claim about a thing while keeping all of the thing private: a zero-knowledge proof (ZKP). While I was reading about ZKPs I kept coming up against paragraphs like this:

“First I will enter the warehouse, cover the floor with paper, and draw a blank representation of my cell network graph. Then I’ll exit the warehouse. Google can now enter enter, shuffle a collection of three crayons to pick a random assignment of the three agreed-upon crayon colors, and color in the graph in with their solution. Note that it doesn’t matter which specific crayons they use, only that the coloring is valid. Before leaving the warehouse, Google covers up each of the vertices with a hat.”

That didn’t make it any clearer. But now I think I have it. A zero-knowledge proof (ZKP) is not one breakthrough and generally applicable cryptographic technique. Instead it is a class of proofs within which there are loads of different techniques.

Indeed there are lots of real-world techniques as well. These real-world examples are not physical versions of cryptographic techniques, they are simply real-world proofs that just happen to belong in the same pool of ZK proofs that some of the cryptographic techniques do. So here are some real-world techniques for ZKP. They are all different and some may even be similar to cryptographic techniques:

Where’s Wally?

I claim that I have found him on this page, but how do I prove my claim to a friend without giving away Wally’s location? This requires a complex cutout exercise with cardboard. And can my friend be sure that it’s not an elaborate hoax?

Snooker balls

I have two snooker balls. I claim they are different colours. How can I prove this to my friend without showing him what colours they actually are? This requires a repeated Q&A request while my friend keeps his eyes closed. As we repeat the process my friend builds up a confirmation that gets closer and closer to 100%.

Twenty boxes

‘Are we the same age?’ asks Alice to Bill. ‘Can we find out without revealing our ages?’ Bill buys 30 petty cash boxes and labels them from 21 to 50. He locks them all up and then keeps the key of the box with his age written on it (42) and throws the other keys away. Then Alice writes 30 cards. 29 with crosses on and one with a big tick on it. She posts a cross into each box except the box that corresponds to her age. Into that box she posts the big tick.

When she has finished she shuts her eyes and Bill uses his key to open the box that corresponds to his age, box 42, and looks to see if Alice has put a tick or a cross in it. This way he finds out if they are the same age or not. If they are not, neither of them has any idea how old the other is.

Just as there are many real-world examples, so too are there many cryptographic examples of differing complexity and sometimes involving third parties.

ZKP that you are over 18

You can prove you are over 18 without showing your age. You just need a third-party that can vouch for your age like this…

The third-party age authority says: “Thanks for the copy of the birth certificate, we can see you are 25 years old. Here’s a long secret number, keep it secret and safe. You will need it at a later step.

“Right, we’re now going to hash your secret number 26 times to make a final age hash code for you (yes, it has to be age+1 to make it all work). So there are 26 hashing steps between the secret number we gave you and this final age hash code.

“Then we’re going to wrap up your name, a time stamp and this final age hash code. That’s the proof kit that you will give to others.”

Now, if you want to prove to someone that you are over 18 then you effectively have to prove that there are more than 18 hashing steps to get from your secret number to your final age hash code.

To do this you just want to show them the last 18 hashing steps, you do this by doing the first 8 hashing steps yourself (hashing your secret number 8 times) and then giving them the result; the 8th hash.

They then hash this 18 times and (because we’ve now done a total of 26 hashes on your secret number) they will end up with the final age hash code and can verify this because this is in with the proof kit.

In effect the verifier is saying; ‘Send us a value that we can hash 18 times to get a match with your final age hash code’. If you are not 18 then you won’t have 18 steps in your final age hash code and you won’t be able to give us a starting point that we can hash 18 times to get your final age hash code.