[yonilevy]

The best "demonstration" of a Zero-Knowledge proof I've heard is this:

Suppose you and a friend are looking for Waldo in a "Where's Waldo?" book page. You found Waldo first, and would like to prove that, but you don't want to ruin the fun for your friend-- you shouldn't provide any information that would take away from their challenge of finding Waldo themselves. How would you do that?

<Take a minute to think about it>

You take a cardboard several times larger than the "Where's Waldo" frame, and cut a hole the size of Waldo's head right in the middle of it. You then place the book on one side of the cardboard so that the only thing visible from the other side is Waldo's head. You show it to your friend. Notice you have proven you know the solution to "Where's Waldo" without revealing any information about the problem which they haven't known before. That to my understanding is the core concept of ZK proofs.

[rumcajz]

You draw a card from a deck. It's red. You want to convince everyone that it's red without disclosing which card you have drawn. So you take all the black cards from the remaining deck and show them to the public.

[vinchuco]

I think you're assuming all cards are red or black. I think a better zero knowledge proof analogy using cards would be a sorted deck and saying "I know where your favorite card is" by showing them their card.

[3131s]

I was thinking along those lines, but don't you still make it easier by giving away some details about Waldo's facial expression, the relative size of his head, etc.? Still a pretty illustrative analogy though.

How about get the coordinates of Waldo's position in the image and hash them?

[WikipediasBad]

That would work except your friend would have to confirm you know only after finding Waldo himself and hashing it to compare the hash to your hash. The idea is that they don't have to know the secret, but you can demonstrate you know the secret.

[3131s]

Ah duh, in that case then I can't think of anything better :(

[SilasX]

I'm confused on multiple fronts.

My understanding is that ZKPs require you to prove only to the verifier that you have the secret information. If proof is convincing to the whole world, that's "too much knowledge" for ZKP.

See the Wikipedia article [1] where they use the example of the ring cave with a wall halfway through that requires a secret password. If you wanted to prove to the world that you have the secret, it's enough to go in the left side and come out the right (or vice versa). But that isn't (traditional) ZKP because it proves to everyone that you can bypass the wall.

Thus (per discussion page), they have to use a more complicated example, where no one gets to see which side you went in, and the verifier calls out which side you must come out of. [2] In that case, it's only convincing to the verifier. Everyone else (for all they know) can't rule out the possibility that the verifier told you which sides they'd call in advance, allowing you to always go the side that doesn't require you to bypass the wall.

OTOH, maybe zcash-style currencies aren't zero-knowledge in that (stronger) sense, because you are trying to convince the whole world of something!

That's also why ZKPs have the general format:

A) randomize the problem,

B) split the knowledge into two pieces where each is useless by itself,

C) commit to each piece, and

D) allow the verifier to pick which piece you must reveal.

How would that work with your Waldo example? Something like:

1) Prover puts a picture behind the cardboard in a position they can't change.

2) Verifier chooses which challenge to give:

A) Take off the cardboard and reveal the original picture.

B) Punch a hole where Waldo is.

3) Repeat until verifier confidence is high enough.

Only a legit prover can always pass. A faker can pass if they cheat and use a fake picture only when the verifier chooses B. (Edit: or if the verifier always picks A)

This is not convining to people other than the verifier because they can argue "Come on, you could have told the prover which stream of options you'd take."

[1] https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_B...

[2] Each time you play, you have a 50/50 chance to pass by dumb luck, but the odds of passing every round decay exponentially in the number of rounds.

[andromeduck]

Building on the normal discrete log/hamiltonian problems, if you have a random source that can be globally trusted such as some hash, then I think you could pretty easily prove it to the world as such:

1. Create a series of n problems P, based on some secret S, and and publish them. 2. Get some source of randoms everyone can trust, such as PRF(P) where PRF is some expensive secure hash function 3. Publish the proof of knowledge revealing the the piece specified by the random source.

Anyone can create P but only someone with knowledge of S can tractably pass step 3 because being able to do so implies either being able to predict the output of the hash function in which case the PRF is insecure or or getting winning 2^n coin tosses even if an attacker has an infinite pool of half revealed challenges he can pull from.

[betterunix2]

Technically that is not "zero knowledge" since the definition of ZK requires interaction (so there is no "publishing" of a proof). What you described sounds like this construction of "non-interactive ZK:"

https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic

NIZK is a very different concept from ZK, because the verifier does learn something, in the sense that the verifier has received a string it could not compute on its own. In ordinary ZK the verifier cannot compute anything after running the protocol that it could not have computed beforehand (so it gains nothing from the interaction).

[andromeduck]

I'm not quite sure I follow. What does the verifier learn after NIZK? Isn't it the point that the verifier learns nothing other than the prover has some secret knowledge? Seems to me like it's just the same information rescheduled with the help of a PRF.

[betterunix2]

The verifier learns the NIZK itself; i.e. the verifier could not have computed the NIZK independently.

[SilasX]

I agree, in that a proves-for-one ZKP can be converted to a proves-for-n if all n parties can trust the source of randomness used to decide the choice of challenge.

[gonehome]

Some other answers (that kind of fix the issue that you might not be showing the exact Waldo):

Make a copy of the page and have your friend draw a unique repeating pattern on the entire back. Cut out Waldo from the page and have your friend verify the design “signature” on the back.

For a better design signature have your friend paint the back of the copy with a color made from three unique rgb values they choose that you don’t know. When you cut Waldo out of the copy have them verify the color matches their unique color.

Another qualification is that details about Waldo are public so simply describing the stripes on his shirt and such doesn’t help prove to your friend that you’ve found him.

[solotronics]

excellent analogy. I have wondered this myself and haven't seen a simple way of explaining

[bfuller]

So if I print out a pic of waldos head and using sleight of hand put that in the hole I have proven something without having to actually find him? Far from a perfect solution.