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!
Ah okay -- the second one had a map with the same shape as the border, which I think made me mentally lump the map's border with the box's borders and invalidate the claim that it's looking at the box's borders as part of the map. I also assumed you wouldn't possibly expect someone to have to explicitly draw all their borders when they can piggyback off the box.
Entirely my mistake because I was kind of ignoring everything you said lol
You could automatically "zoom out" what they draw if they get too close to the border.
Alternatively, you could automatically "close" figures after they have at least three points, and give a hint of a handle that allows dragging a new point out of the middle of an existing side.
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 :)
Yeah, I got tripped up by that formulation as well and it's actually something that annoys me with a lot of algorithms that have some properties proven in a limit: It's "easy" (or at least possible) to mathematically prove that in the limit of some variable, the property will hold: If you repeat the challenge increasingly often, the probability of being lied to will get arbitrarily close to zero; for sufficiently large input sizes, some algorithm runs in linear time; with sufficiently large amounts of training data and iterations, some prediction error will become arbitrarily small, etc etc.
But none of that is telling you how much is "sufficient", or even which order of magnitude we're talking about. If the quantity has a real life cost, this would result in enormous practical differences.
(With the formula you have given for the ZK proof, we're at least one step further: You can start with the desired probability, e.g. the gamma ray burst und calculate the required minimum k from that - also, it's easy to see that the color problem lends itself well to such proofs because the probability of failure drops exponentially quickly with growing k, so the actual k you choose can be relatively small. But if all you have is a proof in the limit, that's not possible)
The problem with doing this on a computer is getting us to believe you didn't just make up the colors as we tell you to reveal them (after being “dishonest” before).
That's the idea at the end about presenting the "sticky notes" as products of primes. Assuming you can't factor the primes yourself, you can be given the whole grid of those products and then interactively ask for the factors or a pair of them. The requestor can't give an alternative factorization (ie. make up a color on the spot) since each number can only be factored one possible way and its easy to verify.
Thanks for the explanation, it seems the definition was slightly different than I assumed it to be previously and that was my missing link to it all making sense. Thanks also for the demonstration to share this info!
You're exactly right. The definition via primes ensures there is only one color consistent with each number (formally, this is called a perfectly binding commitment scheme). Also, here's the link if you want to go back: rahulilango.com/coloring/zk
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 :)
All that's missing is more info in the answer to this question:
> Question: How do you do this in the digital world, without post-it notes?
Answer:
"When I give you a map labelled with numbers for each region, the numbers are the "post-it notes", "covering" the list of factors (which encodes a color). You can't see the primes factors inside them, because, even though generating an multiplying large primes is easy for computers, factoring numbers is much, much harder.)"
I think if, when the player checks "reply the demo, with numbers", you move the game down to where the prime number discussion is, it's easier to understand.
Also, note that the digital versionis better than the physical version. In the physical version, you can't stop me from removing extra notes. (A better example might be to put each color in a locked box, each with a different lock/key.)
In the digital version, the factor lists are the "keys".
Thanks for the response, this and the rest of the comments here helped it finally click for me. I'm "recreationally" familiar with ZKPs, and always found the example of "video recording of alibaba" the most disappointing explanation, and the "I'm not color blind" demonstration the easiest to understand.
This demo was fun, and cool, and short (a undervalued virtue!). Awesome work. Thanks.
Nah, actually I agree with you. What counts as believe and what as fact is rather abitrary. Is 2+2=4 a fact? Is global warming a fact? What about man-made global warming? Ask 100 people whether something is a fact or a believe.
To top that up, it's fact that there have been "proves" that were wrong (or maybe that's just my believe? :^]) even for a long time.
Hence, I think we can say that there are 4 options for a theorem:
1) Some mathematician believes the theorem is correct (but can't prove it)
2) Some mathematician believes the theorem is incorrect (but can't prove it)
3) Some mathematician believes the proof of a theorem is correct
4) Some mathematician believes the proof of a theorem is incorrect
Proving that a proof is correct is kind of meaningless. At that point it's all believe anyways.
Well.. there is. Middle ground being a very complex, but somehow convincing argument that no one can reasonably check. There was one of these cases in number theory some years ago, can't remember the details. Proofs can be only true or false, but accepting proofs is in the end a social process.
A convincing argument that cannot be checked is not a proof. If you want to extend the definition of proofs you're welcome to do that, but for academic mathematics the meaning of proof doesn't contain a middle ground.
The British Isles is also a somewhat controversial term with colonial implications, and it's not used by the government of Ireland[1]. "Britain and Ireland" would be a safer bet, as the map doesn't include any other islands.
Diving into Wikipedia, apparently variations of the name "Britain" have been in use since 30BC, and referred to the big island, with the smaller islands grouped with it, e.g. British Isles.
The Irish may not like it, but they're fighting against two millenia of history.
Sure, but more recent history should have a higher weight. It is reasonable that our names for things reflect recent history and current affairs more than ancient history.
Two thousand years ago Britain and Ireland were ethnically and linguistically pretty similar (I believe). Since then they have diverged in many ways - most significantly during the Reformation period when people in Britain largely left Catholicism, but people in Ireland remained Catholic. Changes like this and the legacy of colonialism this have ultimately resulted in Ireland having distinctly non-British identity. It is reasonable that our naming for things reflect this current state of affairs.
As always, it useful to consider other examples to clarify the point. For example, by the same argument, should we deprecate the phrase "Latin America"? After all, Latin Europeans only arrived in the Americas 500 years ago and the continent has had people for 10 thousand years before that. Are people who include a European adjective in the name of this cultural area "fighting against ten millenia of history"?
And it's use in English only comes from the mid 16th and 17th centuries, right around the time that much of Ireland was being colonized by the British.
Frankly, I find the term offensive, and think it should be discouraged in much the same way people have shifted away from "the Ukraine" to simply Ukraine.
I prefer the term “Atlantic Archipelago”. The “British Isles” encompassing a non-british sovereign state is contentious. Other good terms are “Britain and Ireland” or the “British-Irish isles”
