| |
BGonline.org Forums
Reducing accusations of rigged electronic dice
Posted By: Timothy Chow
Date: Tuesday, 22 August 2023, at 3:19 a.m.
No matter how one generates dice rolls electronically, someone is going to complain that they are rigged. Nothing that I say below can change this basic fact of life.
Nevertheless, there is a way to generate electronic dice that will satisfy all but the hardest-core skeptics, and that is more secure than most methods that are used in practice. I mentioned this method years ago on rec.games.backgammon, but I think it's worth describing here, because it doesn't seem to be well known.
The linchpin of the method is something called a cryptographic hash function. A good example of a cryptographic hash function is SHA-3, but there are many other candidates out there. For the method below to work, both players have to trust that the chosen hash function is secure. "Secure" here means that
1. the input of the hash function cannot be inferred from the output (i.e., inversion is infeasible), and
2. one cannot devise two different inputs that produce the same output (i.e., collision is infeasible).
A well-known hash function such as SHA-3 has received intense scrutiny by experts, so I maintain that only a diehard skeptic would believe that it is rigged. (And if someone doesn't trust SHA-3 in particular, perhaps because they do not trust the U.S. government, then there should still be some hash function that both players should be able to agree on.) Let's proceed on the assumption that this hurdle has been surmounted.
Suppose I want to play backgammon with someone over the Internet. How do I generate a dice roll? Here's the recipe.
0. We agree on a cryptographic hash function f.
1. I list the 36 possible dice rolls, 11, 12, 13, etc.
2. To each of these dice rolls, I append some long random sequence of characters, giving me 36 strings s1, …, s36 that look something like this:
s1 = 11asgwakjserwlkasejr…
s2 = 12zxicouvoizerkjewlk…
s3 = 13powoeiurneaodufioa…
etc.3. I compute f (s1), …, f (s36) and I send these 36 values in some random order to my opponent.
4. My opponent picks one of these 36 values and sends it back to me. This is my roll.
5. Finally, I send s1, …, s36 to my opponent so that my opponent can verify that I did not cheat.
Here's a brief explanation of why the protocol works. My opponent is not going to be able to figure out which of the 36 values is which, because to do that would require inverting f. So neither player has control over what the roll is. Moreover, the first player can unilaterally ensure that the roll is random by randomizing the order of the 36 values, and the second player can unilaterally ensure that the roll is random by making a random selection. Finally, when the first player reveals s1, …, s36, the only way to cheat would be to produce some fake strings that nevertheless hash to the previously sent values, but this would require the first player to find collisions.
In addition to this cryptographic argument, the protocol has the psychological advantage that both players are active participants in generating the roll. There is great psychological value in giving people some control over what is happening, rather than forcing them to passively accept dice that are handed to them.
It should be pointed out that there are ways one can mess up the protocol. If the random characters are not appended to each roll before applying f or if the random characters are not very random, then the opponent might be able to guess what the supposedly random characters are, and infer which roll is which. But if this happens, then the first player has only himself to blame.
In practice, of course, all the above steps would be handled by some app, and most players would probably trust some reputable third party to write the app. But a trusted third party is not needed. Each player can write their own app to execute the protocol. The only thing that truly requires trust is the security of the function f.
| |
BGonline.org Forums is maintained by Stick with WebBBS 5.12.