Lotteries are supposed to produce a random number, but how do you know if it's actually random?
Suppose you live in a corrupt country and a well-connected person tells you that if you buy his lottery tickets, you'll have a higher chance of winning. Should you believe him?
Ideally, a lottery number can be verified to be randomly generated. If it's publicly verifiable, then whenever the number has been tampered with, the public would be able to find out. If that's the case, then you'd know that the seller won't actually be able to give you higher odds of winning.
That was my motivation for thinking about this problem, but I couldn't think of a way to produce a publicly verifiable random number. Instead, I came up a way to generate a random number which all participants can agree on. I call this agreed randomness.
This is not a good as a publicly verifiable random number, but if you can trust at least one participant in this process, then it's almost as good.
Suppose you're walking down the street with a friend and you see a $20 bill in front of you. As you reach down to grab it, your friend objects, saying that he saw it first so he should get it. The two of you argue a bit and finally decide on tossing a coin to resolve this disagreement. Whoever guesses the random result will take home the $20 bill.
Your friend pulls out a coin. Suddenly, you remember your friend does magic tricks as a hobby, so you object to his coin, thinking that he might be using a weighted coin. You pull out a coin of your own to use, but he also objects.
So what do you do?
One thing you can do is to decide to flip both coins. If the results match, one person wins. If the results differ the other person wins.
If you know that your coin is fair, regardless of whether his coin is fair or not, you can be confident that the result is fair. Similarly, if he knows that his coin is fair, he can be confident that the result is fair.
The good thing about this procedure is that it can be scaled up to multiple participants.
Suppose you and three trickster friends need to pick randomly between two restaurants for dinner. Here you can simultaneously each toss a coin of your own choosing and then count the number of heads that show up. If this count is even, go to one restaurant; if this count is odd, go to the other restaurant.
In all of these cases, the result of your coin completely changes the value of the outcome, so if your coin is fair, you know that the outcome is fair. Additionally, as an outside observer, if you know that at least one coin toss is fair, you can be sure that the entire outcome is fair.
To convert the above procedure into an algorithm, one can split the procedure into five stages: commit, record, reveal, verify and combine.
The steps are outlined below:
Note that the above procedure assumes that all participants are using random values of the same length and are using the same hash function which they've all previously agreed on.
The validity of this algorithm relies on each participant committing to a random value before knowing the random values of the other participants.
Thus, there are a few attacks which might be possible in some special situations:
If the hash function is very weak, then one participant can publish a hash which corresponds to multiple random values. After the record stage, the participant can then use the weak hash function to infer the random value the other participants used to generate their hash. Finally at the reveal stage, the participant can choose one of the multiple corresponding random values which produces the best result for them.
If the number of bits used for the random values is very small, then one participant can build a dictionary mapping the hashes to the values. When it's time for them to reveal their hash, the participant can wait for all the other participants to reveal their hash values, look at all the other participants' hash values, figure out their random values using the dictionary, figure out the best random value to use for themselves and reveal the hash of that.
If the random generator used is very weak, then one participant can predict the random values generated by the other participants and create their own random value such that it produces a desired random value when combined with the other values.
One participant can also hack the other participants, such that he would see the random values of the other participants as they're generated and then generate its own random value based on those. In practice, this is a bit complicated, since the attacker would need to hack all other participants.
Finally, the participants may coordinate with each other to produce a particular random value. The difficulty here is that all participants needs to be part of this coordination. This technique can be made easier if combined with the hacking technique above. This technique can be made more difficult, if there are many participants.
I have created an implementation of this algorithm at /random/pool. You can read more about its implementation details at /random.