What is Zero Knowledge?
Let’s suppose that I wish to convince you of something without telling you anything about that thing. It sounds impossible, but with zero-knowledge protocols, it can actually be done. Perhaps the simplest example of a zero-knowledge protocol is as follows: suppose Alice wishes to prove to here colorblind friend, Bob, that she can distinguish a red ball from a green ball without telling Bob which ball is which. The procedure runs as follows:
- Bob presents Alice the two balls – one in each hand.
- Bob randomly swaps the balls behind his back.
- Alice tells Bob whether or not he swapped the balls.
Because Alice can distinguish the two balls, she can always correctly tell Bob whether or not Bob swapped them. However, since Bob cannot distinguish the two balls, and Alice never tells Bob which ball is which, Bob learns only that Alice is able to distinguish the two balls. In this regard, he has gained zero knowledge about how to distinguish the two balls.
The Importance of Randomness
If Bob had two identical red balls, the best Alice can hope to accomplish is to randomly guess whether or not Bob swapped the balls. In one iteration, she has a 1/2 chance of guessing correctly. If they repeat this procedure n times, she has a 1/(2^n) chance of guessing correctly every time. By selecting n to be large enough, Bob can guarantee to his acceptable threshold that Alice is not actually guessing.
Consider the above protocol again, but this time imagine that Alice wishes to cheat. Suppose that she has a friend, Chuck, standing behind Bob’s back who can watch whether or not Bob has switched the balls. Chuck may signal to Alice whether or not Bob switched the balls, even if the two balls Bob has are indistinguishable. In this way, Alice can deceive Bob into believing that she can distinguish the two balls even when she cannot. In our setting with a colorblind man and two different balls, this may not have real significance. However, when we apply this zero-knowledge concept to cryptocurrencies (e.g. Zerocoin), Alice’s manipulations become much moredangerous. She could, for example, convince Bob that she has more money than she actually does even without telling Bob how much money she has.
If we remove Chuck, but instead suppose that Bob decides whether or not two swap the balls using some predetermined sequence, Alice can perform this same manipulation on her own if she knows what sequence Bob will use. It might seem crazy to assume that Alice could read Bob’s mind, but in practice, this may not be as crazy as it seems. To demonstrate my case, I implemented a zero-knowledge protocol for the discrete logarithm. As an attempt to attack my own implementation, I used brute force, combined with the exposed bits from Java’s random to attempt to create a set of all possible random seeds that yield the same sequence of swaps that Bob makes.
To see the results of my case study, with a more in-depth analysis, check out my report: