Hacker News Reader

Comment by jonhyman | Hacker News Reader

My favorite example of this from my college encryption class is: let's say that there's a giant jar of jelly beans, and I tell you that my super power is that I can count how many jelly beans are in that jar. I don't want to tell you how many there are, and you might not even believe me if I did, so here is the test we'll run:

I'll turn around, and you grab a handful of jelly beans and put them behind your back. I'll then turn back around, count the number of jelly beans in the jar, and tell you how many are in your hand.

After repeating this 100 times, I will have demonstrated that I can count the number of jelly beans in the jar without telling you how many are in it.

View on HN

My preferred example: I want to prove to you I know how to do a card trick. I have you pick a card memorize it and put it in the deck. Then I am able to reproduce your card. I can do this a million times to convince you, but never reveal the method of the trick to you. As long as when the verifier picks a card they don't show it to anyone, any other spectators can't know if we are colluding and can't determine how the trick is done.

I prefer this example as it is easier to visual knowing how to do a card trick than it is to understand how you would identify the number of beans in a jar. It also allows you to further explain things like collisions as a magic trick can have multiple methods. Or how by observing enough cases of the trick and "thinking" really hard you might be able to figure out how the trick is done. The crappier the magician the easier it is to figure out their trick.

You would need 100 different jars with different counts.

Otherwise, you either get lucky on the first time and then you always know the amount, or you (more likely) loose the first time and then it doesn't matter.

No, you don't need 100 different jars. Let's say the jar started with S beans, and the person grabbed X_1, X_2, .. X_n beans in n trials. To prove the superpower, you have to tell him the correct value of X_i every time. Knowing S beforehand does not help you unless you can calculate S-X-i without knowing X_i.

I think you're assuming that you can count the jar between pulls. (That was my initial reading also.) In that case, you guess your first number, count the jar, and then work backwards for all subsequent pulls.

But on rereading, the info to prove isn't "I know how many beans were here to start", it's "I'm capable of counting this jar of beans by looking at it". So if you guess right on the first trial, you still won't know the beans-remaining count, and will have to guess on the next trial too.

This is made super confusing by the claim that it's a ZKP of the initial count. That's narrowly true, but the real question at hand is whether you can count the beans.

Why repeating 100 times? Wouldn't the first time suffice? Ok, you could be lucky, but how probable is that? Update: Given the content of the jar it may happen that the count of items could go down with each experiment :-P

The more times you repeat, the less likely it is that you've just guessed correctly.

Reply on news.ycombinator.com