[ianseyer]

The best analogy of zk-proofs I've heard is to suppose you have found Waldo in "Where's Waldo," and want to prove that you have done this without revealing the location.

You could take a piece of paper (much larger than the picture/book), and cut out a waldo-shaped hole it and position the paper such that he is shown in the hole. Then, when you show it to the challenger, they know that you have found him without you revealing where he is.

[delecti]

It took me a minute to fully get this, so I'm adding this so it's a bit more obvious for anyone else: the piece of paper is much larger than the picture/book so that it can hide the book's relative position underneath it.

[thaumasiotes]

Unfortunately that completely defeats the idea of the proof.

Here's an alternative procedure:

1. Get a very large sheet of paper, and cut a Waldo-shaped hole in it.

2. Get some more paper, and paint a picture of Waldo on it.

3. Paste your image of Waldo on the back of the paper you prepared in step 1.

4. Place this composite over a Where's Waldo book.

5. You've found Waldo!

If you can't tell where the book is, there is no evidence that the image of Waldo is part of the book.

[pxx]

if you can tell where the book is, it's not zero-knowledge anymore...

see my other comments -- the idea is that in each round you should be able to verify the construction (there's a Waldo-sized hole and the correct book and page when the pieces are separated) or the proposed solution (Waldo through the hole) but never the offset of the book and hole (because then you can deduce where Waldo is).

a cheating prover (utilizing your strategy, or just Waldo from a different book or whatever) would try to guess which one you will want but only has probability 1/2 of succeeding. through iteration the verifier can be exponentially increasingly confident that the prover knows where Waldo is.

[nroets]

But it's a simplification: One iteration is enough to detect lying.

In a real ZK proof the probability of the prover lying reduces after each iteration but never reached 0.

[pxx]

there is a probabilistic interactive component. this protocol allows the prover to fake it by just using a book where they know where Waldo is. in each iteration you choose whether to confirm it's the original book and page under the paper or see Waldo (but not both). a cheating prover has p = .5 of fooling a verifier.

but your concern is invalid to begin with. nothing in the definition of a zkp requires them to be multi-round interactive. there exist non-interactive zkp.

[isaacfung]

How do I know if it is the original "Where's Waldo" under the paper?

[pxx]

in each iteration you choose whether to confirm it's the original book and page under the paper or see waldo

[IshKebab]

I think that conveys what a zero knowledge proof achieves but it doesn't really correspond to any real zero knowledge proof algorithms. You can't do that over the phone, which is kind of the whole point.

[pxx]

no, that's not even close to the whole point. the analogy is to introduce the concept of proving something to a verifier without giving the verifier the solution

the paint-mixing analogy of diffie-hellman also can't be done over the phone, but it helps people understand how a shared secret can be established even if all communication is intercepted

[IshKebab]

It is the whole point. ZKPs are useless if you can't do them remotely.

> the analogy is to introduce the concept of proving something to a verifier without giving the verifier the solution

Yes that's what I said.