The magic of participatory randomness(cryptography.dog)
cryptography.dog
The magic of participatory randomness
https://cryptography.dog/blog/rng-day-2024/
2 comments
Great article! I have some miscellaneous comments, in no particular order.
The digital commitment scheme as described has a subtle vulnerability. Suppose there are two participants, A and B. B decides to wait until A's hash is shared. Once A shares it, B shares that same hash as their commitment. Then, after A reveals their number, B also "reveals" that same number.
Since the described protocol is to XOR these revealed numbers together, the resulting output will be 0 and B will have known that in advance, meaning it was not fair. With N honest participants and 2N (or more) dishonest colluding participants it gets worse. Consider participants A (honest) and B and C (dishonest/colluding). B "cancels out" A's result as described above, and then C's result is XORed in, allowing the dishonest participants to chose whatever arbitrary output bits they like.
There are several solutions, of course. You could specifically check for and disallow duplicated commitments, or use something other than XOR to combine. Note that addition is not a great choice here: since N+N is even, the least-significant bit is certain to be 0. Better would be to sort the numbers and then hash their concatenation.
Another serious problem with commitment schemes in practice is last-revealer bias. After everyone has committed, and everyone has revealed except for the last participant, that last participant knows the final outcome and nobody else does. If the resulting random number is disadvantageous to the last revealer for any reason, they may simply choose to not reveal it. Then what does the protocol do? After a timeout period, use all the values except for the unrevealed one? If so, the last-revealer gets "another chance", and has managed to bias the result in their favour. This also gets worse with colluding participants. After everyone has revealed except the dishonest cartel of N participants, they have 2^N possible outcomes they can choose from, by choosing which combination of their N numbers to reveal.
The only general solution to this is to have some sort of punishment for failure to reveal (slashing your stake, in blockchain lingo).
> A random stream's fairness can also be compromised if it continues to be used beyond the point of a player's decision. For example, if you decide to play a game of Monopoly over the internet then you will probably have to re-seed the RNG on each player's turn.
An interesting solution to this is a "progressive reveal scheme". Each participant generates a random number and hashes it. And then they hash that hash, and keep doing this N times. Then each commits to the Nth hash with the usual commit-reveal scheme. Afterwards, at every turn in the game, each player reveals their previous pre-image, which they're locked in to (assuming a collision-resistant hash function).
> the rejection sampling method described earlier will sometimes require that you "re-roll" a die
The average number of attempts you'll have to make is 1/P, where P is the probability of any one being accepted. The wikipedia article shows this using calculus, but I wrote up a much simpler derivation here: https://metacpan.org/pod/Session::Token#EFFICIENCY-OF-RE-ROL...
> The Fisher-Yates shuffle [...] guarantees equal probability of all possible orderings.
A somewhat counter-intuitive observation is that the number of possible orderings often exceeds the number of possible seeds for your PRNG. For example, even if you're using 256 bits of seed, lists of size 58 or greater cannot possibly have all possible orderings equally probable, simply because 58! > 2^256.
> If you're comfortable with the idea that physical or analog finger dice can simulate a coin flip by holding up either one or two fingers
I found it strange the author feels the need to introduce and describe "finger dice" in such an elementary way. This game is universally known as odds and evens, and has been played continuously at least since the days of ancient Greece: https://en.wikipedia.org/wiki/Odds_and_evens_(hand_game)
The digital commitment scheme as described has a subtle vulnerability. Suppose there are two participants, A and B. B decides to wait until A's hash is shared. Once A shares it, B shares that same hash as their commitment. Then, after A reveals their number, B also "reveals" that same number.
Since the described protocol is to XOR these revealed numbers together, the resulting output will be 0 and B will have known that in advance, meaning it was not fair. With N honest participants and 2N (or more) dishonest colluding participants it gets worse. Consider participants A (honest) and B and C (dishonest/colluding). B "cancels out" A's result as described above, and then C's result is XORed in, allowing the dishonest participants to chose whatever arbitrary output bits they like.
There are several solutions, of course. You could specifically check for and disallow duplicated commitments, or use something other than XOR to combine. Note that addition is not a great choice here: since N+N is even, the least-significant bit is certain to be 0. Better would be to sort the numbers and then hash their concatenation.
Another serious problem with commitment schemes in practice is last-revealer bias. After everyone has committed, and everyone has revealed except for the last participant, that last participant knows the final outcome and nobody else does. If the resulting random number is disadvantageous to the last revealer for any reason, they may simply choose to not reveal it. Then what does the protocol do? After a timeout period, use all the values except for the unrevealed one? If so, the last-revealer gets "another chance", and has managed to bias the result in their favour. This also gets worse with colluding participants. After everyone has revealed except the dishonest cartel of N participants, they have 2^N possible outcomes they can choose from, by choosing which combination of their N numbers to reveal.
The only general solution to this is to have some sort of punishment for failure to reveal (slashing your stake, in blockchain lingo).
> A random stream's fairness can also be compromised if it continues to be used beyond the point of a player's decision. For example, if you decide to play a game of Monopoly over the internet then you will probably have to re-seed the RNG on each player's turn.
An interesting solution to this is a "progressive reveal scheme". Each participant generates a random number and hashes it. And then they hash that hash, and keep doing this N times. Then each commits to the Nth hash with the usual commit-reveal scheme. Afterwards, at every turn in the game, each player reveals their previous pre-image, which they're locked in to (assuming a collision-resistant hash function).
> the rejection sampling method described earlier will sometimes require that you "re-roll" a die
The average number of attempts you'll have to make is 1/P, where P is the probability of any one being accepted. The wikipedia article shows this using calculus, but I wrote up a much simpler derivation here: https://metacpan.org/pod/Session::Token#EFFICIENCY-OF-RE-ROL...
> The Fisher-Yates shuffle [...] guarantees equal probability of all possible orderings.
A somewhat counter-intuitive observation is that the number of possible orderings often exceeds the number of possible seeds for your PRNG. For example, even if you're using 256 bits of seed, lists of size 58 or greater cannot possibly have all possible orderings equally probable, simply because 58! > 2^256.
> If you're comfortable with the idea that physical or analog finger dice can simulate a coin flip by holding up either one or two fingers
I found it strange the author feels the need to introduce and describe "finger dice" in such an elementary way. This game is universally known as odds and evens, and has been played continuously at least since the days of ancient Greece: https://en.wikipedia.org/wiki/Odds_and_evens_(hand_game)
I have seen this framed as "evens or odds": instead of asking "heads or tails", you ask "evens or odds". Each person reveals either one or two fingers, and the caller wins if the sum of fingers is in the class of numbers they called.
It's like rock-paper-scissors but it takes a deterministic amount of time (one round) whereas RPS can take arbitrarily long if the participants are deep in each others' meta.