[bgoated01]

I showed this to my two kids, and we all three enjoyed it. The zero knowledge proof portion didnt really click for me, but we liked the four color map theorem stuff. This led me to download some maps for my kids to attempt coloring on paper, and also got me wondering about how this holds or doesn't on non-euclidian spaces. Turns out the maximum is four colors on a sphere, but 7 colors on a torus! More details here: https://mathworld.wolfram.com/TorusColoring.html

Thanks for leading us down this mathematical rabbit hole today.

[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.

[dmurray]

Four colours also isn't enough for some real-world country maps. Countries with enclaves (like Alaska, Kaliningrad or Sint-Maarten, though only the last actually makes 4- colouring impossible) change the topology: you can think of what shape the earth would have if there was also a tunnel connecting Alaska and New York.

[Blammar]

Torus, of course, but how does that relate to enclaves, which are planar ?

[dmurray]

You might want to colour the exclave the same colour as the rest of its country, even though no connection can exist between them on the plane.

[etbebl]

It seems like you're using "enclave" and "exclave" interchangeably, which is causing confusion. What you're referring to is an exclave; an enclave is when one region is completely surrounded by another, like Lesotho or Vatican City.

[dmurray]

You're right, my first post should say exclaves and the three examples I gave are all exclaves.

[pwmtr]

This video helped me a lot to understand the basics of zero knowledge proof: https://www.youtube.com/watch?v=fOGdb1CTu5c

[wonger_]

Great video, thanks. My takeaways:

- The physical demonstrations at 1:16 and 3:48 were helpful

- thinking of proofs as between a prover and a verifier, not as classical deterministic proofs

- insight into the name "zero-knowledge", as in "you can already predict the answer, so you're not gaining any knowledge from that interaction"

[guyomes]

And it turns out that on the Klein bottle, the maximum is 6 colors. More generally, this number depends directly on the number of holes of the surface [1].

[1]: https://en.wikipedia.org/wiki/Heawood_conjecture

[enlyth]

Regarding the zero knowledge proof, there'd be a chance that the two random ones you reveal are the same color, if three weren't enough.

So by doing this over and over again, if the two you choose are always different colors, you approach a 100% certainty that it's legit.

You never really get a 100% proof but the more times you repeat the closer you are to being sure. At 99.999999% after repeating this enough times, you'd most likely be satisfied.

[Aardwolf]

When I read the zero knowledge proof part the first time, my thought was:

The person can just always give two different colors (and never two same colors) when you reveal two post it notes, so you could never proof them false.

Only after re-reading I realized _all_ the colors are to be hidden under the post it notes _beforehand_, not at the time you choose two post it notes.

[Aardwolf]

Does the torus one apply to a wrap-around 2D map then? So if the edges don't wrap, the max amount of colors needed is 4, but if the edges do wrap, you could make a map requiring 7 colors?

EDIT: yep looks like it, the leftmost picture under 'snapshots' here is a 2D map of what's on the torus and looking at e.g. the blue band, it touches all 6 others (just barely the cyan and yellow ones with a few pixels of its tips when wrapping between top/bottom): https://demonstrations.wolfram.com/SevenColoringOfATorus/

[armchairhacker]

Here's my explanation of the ZKP:

First, both you and the oracle know what the uncolored map looks like, and what the 3 colors are.

Step 1: The oracle sends the entire 3-colored map, but asymmetrically encrypted. So you can't see the map, but the oracle can't "un-send" it. If no 3-coloration of the map exists, the oracle has to send you something, and because you know what the map and colors look like, the only thing they can send is a map where some two adjacent regions have the same color.

Steps 2&3: You randomly pick two adjacent regions and ask the oracle for their decryption keys, so you can see their colors. When you initially received the encrypted map, you could not know whether it had two same-colored adjacent regions. But, if you happen to randomly choose the same-colored regions, the oracle has no way of not telling you. If the oracle refuses to send the decryption keys for those regions, or sends ones that don't successfully decrypt, you'll know something is up, and can assume the regions are the same color. And the only keys that successfully decrypt the regions' colors, decrypt into their original colors; so the regions will only decrypt into different colors, if they were different colors in the encrypted map the oracle originally sent.

To further illuminate: the "random pick after the map is received" ensures that the oracle must send you a map where all adjacent regions have different colors, even though you can't see all the colors yourself. Otherwise, the oracle can't guarantee that you won't ask for the two regions with different colors (because they sent the map before you randomly pick), and if you do ask for those regions, they can't respond in a way that re-assures you the colors are different (because the only way to do so is send keys that decrypt the regions into separate colors, and since they decrypt into the same color, such keys don't exist).

Step 4: Repeat steps 1-3 an unbounded number of times. This is necessary because in a single iteration, there's a chance that the oracle sends a map with two adjacent same-colored regions, but you pick two different regions; so the map is un-3-colorable, but you don't find out. In fact, this is a very high chance if it's a large map and only a single pair of adjacent regions have the same color. But more iterations increase the probability that you do find out indefinitely; with enough iterations, the probability that one of them you get lucky and select the same-colored region is 99.999...%.

Also, each time you repeat steps 1-3, the oracle sends the map with a different coloration. Otherwise, you'd slowly reveal the colors to get the fully-colored map, so it wouldn't be a zero-knowledge proof (two colors in each of two maps with different colors doesn't give you any more information than two colors in one map, so even with unbounded iterations the original coloration isn't revealed). If the map isn't 3-colorable, the randomization doesn't affect the probability: when the oracle randomizes the map, they could choose an entirely different coloration and give two different adjacent regions the same color, but the probability of you randomly choosing those two regions stays the same, so the probability of "getting lucky" in one of enough iterations also stays the same, at 99.999...%.

[helboi4]

same that was extremely fun but im not sure i'm going to grasp the zk proof thing