Show HN: I made a puzzle game that gently introduces my favorite math mysteries

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.

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.

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

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.

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

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

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

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/

Very glad you enjoyed it!

For the ZK example, the math behind it is this: if there are m bordering regions and I am lying, you have a 1/m chance of catching me each time. Thus after k repetitions the chance you haven't caught me is (1-1/m)^k \approx e^{-k/m} which is extremely small for k sufficiently larger than m.

Now, you may rightfully say: hey that's still not a "proof," you could still be lying! There are two responses to this:

1. The probability can be made incredibly small, like smaller than the the chance, say, your computer got hit by a gamma ray burst that would flip bits from 0 to 1 (I really have no idea if this actually happens but people have said it to me).

2. It turns out it is mathematically impossible to get the zero knowledge property if you want true proofs (i.e., no probability of being wrong). So, there's a trade off: if you want zero knowledge, you have to accept some (small) failure probability

P.S. Adding an easter egg for coloring the larger graph is on the todo list :)

I think the answer is that each time you reveal the colours, you observe that they are within the set of three colours illustrated at the beginning of the proof. Whichever you reveal, you never find a fourth colour.

This confused me at first.

I've got another problem about this zero knowledge proof. The digital version doesn't make a lot of sense to me. It depends on the fact we don't have a fast integer factorization algorithm. But integer factorization is not proven to be NP-complete, and 3-coloring is NP-complete.

So isn't it possible that there is a polynomial time algorithm for integer factorization, but no polynominal time algorithm for 3-coloring, and therefore the "zero knowledge proof" actually reveals the answer?

OP: Although I'm not really in the target audience for this demo (I already knew all the punchlines), it does occur to me that it might be helpful to readers like the parent-commenter — and even perhaps thought-provoking to us know-it-alls — if you provided a mode at the end of the demo where the graph was in fact not three-colorable, and the computer actually would lie about its being three-colorable. So it would generate a "three-coloring" with a flaw somewhere, and display its representation as products of primes, and you'd get to choose two adjacent products and receive their factors... and so you could see for yourself exactly how long it took for you to luck into catching the computer in one of its lies.

And the demo could also tell you the expected number of iterations to catch the lie with (50/90/99%) probability. It'd be a pretty large number even for such a small graph, I'd bet.

(Of course the computer could also lie about the factorizations, since it's unlikely a human would bother to catch it in that kind of lie; but let's assume it doesn't ever do that.)

Readers might also be interested in the https://mathworld.wolfram.com/McGregorMap.html (reported, on 1 April 1975, to require five colors!)

E.g. "By repeating the process enough times, the probability that you never catch me becomes smaller than, say, getting struck by lightning" doesn't seem to show it's a proof?

That's fine though, because the point isn't really to publish math papers without disclosing proofs. For example, presenting a valid digital signature is sometimes colloquially called a proof that you had the private key, even though there is 1 in gazillion chance that you didn't. For such practical tasks, very high chance tends to be good enough.

Thanks for pointing this out! Switched to "British Isles" -- update should be percolating now

'British Isles' identify the geographic islands.

These kind of things are also why four colours are actually _not_ always enough, in the real world. Countries can have exclaves :)

Good point! I'll try to think about a better way to phrase this (happy to hear suggestions)

That Coq proof is not "without computer assistance". No Coq proof is, as Coq is literally an "assistant" that runs on a computer.

And those many jobXtoY.v and taskXtoY.v files sure look like they also do the same as the Appel and Haken proof, namely enumerate lots and lots of cases that are then machine-checked. So I don't think the computerized Coq proof is really qualitatively different from other computerized proofs that enumerate so many cases that a manual check would be impractical.

I would consider a proof to be a "repeatable argument". One you could show to someone and expect them to be convinced by it. I think it is a defensible viewpoint that a proof in coq is not 100% convincing. If you think otherwise, then how can you reconcile the existence of falso (a coq verified proof of "false")?

https://github.com/clarus/falso

Proof and belief I think are pretty strongly intertwined, but I'm not going to pretend to have a particularly rigorous philosophy on the matter. Similarly, when the proof of Fermat's last theorem was published, I don't know if I should consider that to be a proof because it is well beyond my comprehension. I have no reason to question it, but should I consider it a proof? I know that people smarter than me (e.g. Wiles) thought the original version of it was a proof, but it had a subtle error in it which required a fix. While I haven't looked at the proof and revision, I would be surprised if I could look at the two versions as labelled and tell which one is the correct version.

Whoops! Switched to "British Isles" -- update should be percolating now

It's about as "trivial" a distinction as considering Crimea (or the entirety of Ukraine, for that matter) a part of Russia.

Many, many people have died for this triviality.

"Somewhat fraught" is a very interesting choice of words, but then again, so is "The Troubles" (when the subject matter is decades of bombings and killings).

Why would it be necessary for a graph requiring 5 colours to have a 5-clique (as it's called [1])? The western-US example in the OP [2] has no 4-clique, yet it requires 4 colours. (Try drawing out the incidence graph of the faces, i.e. a vertex is a US state and an edge is two states bordering. Lots of 3-cliques (triangles), but no 4-clique!)

Side note: indeed, 5-cliques are not planar: that is to say, there is no map you can draw that has five regions all bordering each other. This is not too difficult to prove, actually. Proving that 4 colours is enough is a whole different league!

[1]: https://en.wikipedia.org/wiki/Clique_(graph_theory)

[2]: https://www.rahulilango.com/coloring/wus

I've always found what happens in the third dimension weird.

A 0-dimensional space needs up to: 1 color.

A 1-dimensional space needs up to: 2 colors.

A 2-dimensional space needs up to: 4 colors.

A 3-dimensional space needs up to: ∞ colors.

I can easily picture why a 3D space has no limit to the number of colors (personally I always imagine color blocks hanging in space connected to every other color block by bendable wires), but I don't quite understand why the pattern is that way.

You do need to prove that you have assigned the colors before the choice of what to reveal is made, I think. Physically this is guaranteed by the presence of the colors under the post-its (barring dynamic e-paper or something).

I'm not sure how it works with the example of the primes, I lost the link to the later pages of the game so I can't read over it again, but I think it's guaranteed because there's just one number encoding all the assignments and you just get to unlock a single pair with the key given in response to your choice. There's an assumption that there isn't enough information in the key to fake any response, it has to reveal something that was already in there.

Thanks for the feedback! As hcs suggests, this is part of the physical post-it assumption. I'll think about ways to make it more clear -- adding an FAQ is a good idea :)

If someone has signed something cryptographically, wouldn't you say that the signature was a proof of someone with the private key signing it? (Even though it is possible to construct a valid signature without the private key - you just have to be very very very lucky)

I guess you also don't like the name Proof of Work.

It might help to think of the sense of "proof" that's synonymous with "trial", rather than a specific formal math sense of proving a theorem from axioms by formal transformations.

zero knowledge corroboration isn't the same thing as a zero knowledge proof. If the provided evidence isn't enough, then you keep iterating until it's proven.

there has to be a layman's explanation. I knew the easiest way to get four colors was to put a split square inside another split square "donut", but the reason you can't force 5 colors is that word "inside". There has to be a nice, tidy "verbal proof" that no matter what, one or more colors will be "trapped" inside at most 3 other colors.

It was really enjoyable to try. I got an optimal 4-color map on the first try, so I was over confident. My approach was something like: put a bunch of the 4-color maps next to a long Chile-like thing. When that didn't work I added borders until my device couldn't render it any longer. Very very fun.

Hmm, my guess is you're trying to use the box's borders as lines (they don't count, only the lines you draw count). Let me know if that's not the issue. Also, I'll think about ways to make this more clear!

i appreciate the intention to let you struggle with it on your own for a bit, but not go crazy.

a better experience might be having the warning reveal more after a few attempts, but I don't mind starting with a "warning it's surprisingly tricky"

well, i knew there was no answer and i still tried for 15 minutes. I think that's the point!

Will look into this. Did it happen on the first page (map of Britain + Ireland)?

Good catch -- I'll look into this!

the easiest 3 is an equilateral triangle split in half with any shape containing it - for 4 split the container perpendicular to the split in the triangle.

|-/|\-|

ZKP is the subject. The maps part is a helper lemma.

It would help to clarify that in the beginning. The game is a bit of a shaggy dog tail. It would be good to give an outline and progress bar at the start (without spoilers)

In reality, the entire map should be sent first to the verifier (with colors hid behind the post-it) so if it was a bogus randomly colored map, you may find two adjacent points having same color if you try extremely many(think hundreds or thousands in the website's case) times. If you sufficiently try many times and fail to find the adjacent points, you will convince that the prover have the map which is correctly 3-colored.

Note that the entire map is sent again, shuffled its color each time after you choose the two points.

Absolutely!! Talk to MoMath in NYC too

I'm happy to find a contact there if you want

Well it does not generalize into 3 dimensions: https://math.stackexchange.com/a/4767802