4 ms·

I love zero knowledge proofs. My professor in college explained the idea in what I thought was an especially clear way: Say that you and a friend are reading a

I love zero knowledge proofs. My professor in college explained the idea in what I thought was an especially clear way: Say that you and a friend are reading a Where's Waldo book, and you want to prove that you have found Waldo, but you don't want to tell your friend where Waldo is. This seems impossible. However, you could take a large piece of cardboard, cut out a Waldo-shaped hole, and place it over the book. Now you have proven that you can find Waldo. "But wait!" cries your friend. "How do I know the book is even under there? Let me see." But you can't do that, since he knows roughly the spot Waldo would be if you lifted the cardboard. So, you get a second piece of cardboard and put it on top of the first. Now, you play a game. You ask your friend whether you should lift one piece of cardboard (to verify the picture of Waldo) or two pieces (to verify that the book is beneath the second piece). You can play this game as many times as required for your partner to gain a reasonable confidence that you're not cheating. And that's a zero knowledge proof.

BinaryIdiot 11y ago
Correct me if I'm wrong but that example doesn't seem quite right. If you lift one piece of cardboard the person now sees roughly where Waldo is, right? Sure the cardboard could be HUGE to obscure the size and position of the book but then asking to lift both pieces will show you the position and size of the book making it immediately obvious where Waldo is.
- gbhn 11y ago
  Perhaps a good intuition pump is this: after every guess the person claiming to have found Waldo gets to position three things: the book, the waldo mask, and the covering cardboard. This then means the subsequent trials don't reveal any side channels about Waldo's location in the book. (And of course in practice the "pieces of cardboard" are big enough to obscure all book information.)
- skj 11y ago
  The idea is that some the time, it's not the book, but just a random small picture of Waldo. Since you don't know if it's the book under there or not, you don't know if this example is a "control". The proportion of times that it is the book has to be the same as the odds that you could randomly guess where Waldo is, I think.
  - edanm 11y ago
    No, that's wrong. The book always has to be under there, otherwise you aren't proving anything (or at least, the odds are worse). The idea is that your counterparty cannot ever ask for both the book under there and to see Waldo, so they never know where the book is. You can spin the book around under the cardboard to put it in arbitrary locations, therefore just seeing the Waldo doesn't help.
- cortesoft 11y ago
  Couple of things: 1) It doesn't have to be THAT big. As long as the cardboard has twice the dimensions of the book, having the cutout be in the center ensures that you could reveal a Waldo anywhere on the page without letting the other person see any bit of the book to try to reason which section the book is under. 2) They only get to choose one piece of cardboard to remove per iteration of the game - they don't get to lift one piece and then immediately the other, they only lift one. That means that the person placing the cardboard can't cheat (because they don't know which piece they are going to lift, the one revealing the whole book or the one revealing the waldo), and the other person can't gain any information from the reveal. You can repeat the process many times (moving BOTH pieces of cardboard each time to ensure no gained information), but you can only do one cardboard lift per cycle.
- caf 11y ago
  The book gets to be repositioned somewhere else under the huge piece of cardboard between each trial.
- BinaryIdiot 11y ago
  Wasn't sure who to reply to but thanks for all the clarifications!
fryguy 11y ago
There's a little bit more to it than that. Someone watching that transaction between you and your friend doesn't learn anything either, since your friend could be colluding with you and placing a printed out piece of paper with waldo on it when your friend would say "show me you know where waldo is" and the book when he would say "show me there's a book under there"
hcarvalhoalves 11y ago
Hmmm, so "knowledge" in this case means having access to the intersection between two sets of information that allows you to hone into the solution? That's an interesting way to think about knowledge (and confidence intervals).
- huntaub 11y ago
  I think that is an acceptable understanding. In a more formal setting, we talk about witnesses [1]. In effect, there is some piece of "knowledge" that will convince someone that you can solve something. With Waldo [2], that would be the actual location (x-y coordinates) of Waldo. If I want to convince you that I know where Waldo is, I can just give you the X-Y coordinates of his location. This has the unfortunate side effect of giving _you_ the ability to convince people you know this knowledge (you now know where Waldo is) - we have revealed the witness to you. In a general sense, a zero knowledge proof is a class of protocols where you convince another party that you know the witness of a problem without having to reveal it to them (they receive zero knowledge about the witness). [1] https://en.wikipedia.org/wiki/Witness_(mathematics) https://en.wikipedia.org/wiki/Witness_(mathematics) [2] http://www.anagram.com/jcrap/Volume_0_1/crv0n1-3.pdf http://www.anagram.com/jcrap/Volume_0_1/crv0n1-3.pdf
icedchai 11y ago
This doesn't make much sense, sorry. Perhaps you could explain it better.
edanm 11y ago
Thank you!! This has always been my favorite "intuitive" explanation of zero-knowledge proofs, but I never even knew the second part about two cardboards, which makes this even better!

BinaryIdiot 11y ago

Correct me if I'm wrong but that example doesn't seem quite right. If you lift one piece of cardboard the person now sees roughly where Waldo is, right? Sure the cardboard could be HUGE to obscure the size and position of the book but then asking to lift both pieces will show you the position and size of the book making it immediately obvious where Waldo is.

gbhn 11y ago
Perhaps a good intuition pump is this: after every guess the person claiming to have found Waldo gets to position three things: the book, the waldo mask, and the covering cardboard. This then means the subsequent trials don't reveal any side channels about Waldo's location in the book. (And of course in practice the "pieces of cardboard" are big enough to obscure all book information.)
skj 11y ago
The idea is that some the time, it's not the book, but just a random small picture of Waldo. Since you don't know if it's the book under there or not, you don't know if this example is a "control". The proportion of times that it is the book has to be the same as the odds that you could randomly guess where Waldo is, I think.
- edanm 11y ago
  No, that's wrong. The book always has to be under there, otherwise you aren't proving anything (or at least, the odds are worse). The idea is that your counterparty cannot ever ask for both the book under there and to see Waldo, so they never know where the book is. You can spin the book around under the cardboard to put it in arbitrary locations, therefore just seeing the Waldo doesn't help.
cortesoft 11y ago
Couple of things: 1) It doesn't have to be THAT big. As long as the cardboard has twice the dimensions of the book, having the cutout be in the center ensures that you could reveal a Waldo anywhere on the page without letting the other person see any bit of the book to try to reason which section the book is under. 2) They only get to choose one piece of cardboard to remove per iteration of the game - they don't get to lift one piece and then immediately the other, they only lift one. That means that the person placing the cardboard can't cheat (because they don't know which piece they are going to lift, the one revealing the whole book or the one revealing the waldo), and the other person can't gain any information from the reveal. You can repeat the process many times (moving BOTH pieces of cardboard each time to ensure no gained information), but you can only do one cardboard lift per cycle.
caf 11y ago
The book gets to be repositioned somewhere else under the huge piece of cardboard between each trial.
BinaryIdiot 11y ago
Wasn't sure who to reply to but thanks for all the clarifications!

fryguy 11y ago

There's a little bit more to it than that. Someone watching that transaction between you and your friend doesn't learn anything either, since your friend could be colluding with you and placing a printed out piece of paper with waldo on it when your friend would say "show me you know where waldo is" and the book when he would say "show me there's a book under there"

hcarvalhoalves 11y ago

Hmmm, so "knowledge" in this case means having access to the intersection between two sets of information that allows you to hone into the solution? That's an interesting way to think about knowledge (and confidence intervals).

huntaub 11y ago
I think that is an acceptable understanding. In a more formal setting, we talk about witnesses [1]. In effect, there is some piece of "knowledge" that will convince someone that you can solve something. With Waldo [2], that would be the actual location (x-y coordinates) of Waldo. If I want to convince you that I know where Waldo is, I can just give you the X-Y coordinates of his location. This has the unfortunate side effect of giving _you_ the ability to convince people you know this knowledge (you now know where Waldo is) - we have revealed the witness to you. In a general sense, a zero knowledge proof is a class of protocols where you convince another party that you know the witness of a problem without having to reveal it to them (they receive zero knowledge about the witness). [1] https://en.wikipedia.org/wiki/Witness_(mathematics) https://en.wikipedia.org/wiki/Witness_(mathematics) [2] http://www.anagram.com/jcrap/Volume_0_1/crv0n1-3.pdf http://www.anagram.com/jcrap/Volume_0_1/crv0n1-3.pdf

icedchai 11y ago

This doesn't make much sense, sorry. Perhaps you could explain it better.

edanm 11y ago

Thank you!! This has always been my favorite "intuitive" explanation of zero-knowledge proofs, but I never even knew the second part about two cardboards, which makes this even better!