Zero-Knowledge Waldo

Let’s play a game.

post image

Not that kind! The fun kind! Specifically, “Where’s Waldo?” I remember sitting in the dentist office as a kid, dreading what was to come, and finding comfort in the games and toys they had in the waiting room. One such game was a book of “Where’s Waldo?” As my mom flipped through magazines (this was before smartphones), I sat there with a furrowed brow and hunched back intently scanning every point of the page. And although those days are long gone now, I find myself returning to Waldo once more. Not so much to hunt him for sport as I used to, but to illustrate a point. In fact, I am going to show you exactly where that little rascal is right now.

Proof I located Waldo
Proof I located Waldo

Huh? Not the spoiler you were expecting, right? Rather than show you a solved puzzle with a big circle around Waldo (and spoil all the fun), I have shown you only that I have found him. No more, no less. In math teacher terms, I have shown you the answer but not the solution. Just to make sure we are on the same page, try and find him yourself below. Ideally, you will see that, although I have proved I have found Waldo, none of what I showed or told you is any help to find him yourself.

Now find him yourself
Now find him yourself

This is actually a very simplistic example of a more complicated technique: a zero-knowledge proof. Essentially, I “proved” that I know where Waldo is without revealing exactly where that is. There are three properties of a zero-knowledge proof:

  1. Complete - I can prove what is true

  2. Sound - I cannot prove what is false

  3. Zero-knowledge - I can prove f(x) is true without revealing x

If that last one confuses you, the “function” in this case would take coordinates for a guess and be true if Waldo is located there and false otherwise. In a Haskell syntax, we could say

FoundWaldo :: (Integer, Integer) -> Boolean
FoundWaldo (x, y) = x == WaldoX && y == WaldoY

This is a very powerful and fascinating technique, one which is getting readily applied in the cryptocurrency space. For example, you could prove that a certain investment has returned 150% profit without revealing how many shares were purchased.