Score:6

How can 4 users generate a provable fair random number?

mo flag

The past few weeks I have been trying to solve a difficult problem. I have asked some cryptography experts but unfortunately they had no clue on how to solve the problem.

The situation is as follows, an online casino wants to host an online bet, each bet can have a variable amount of players. For this example we will use four players. Each player wants to be sure that the outcome of the bet is random and has been calculated in a fair manner, without any interference of malicious parties. These parties could be other players participating in the same bet, or the online casino. This means that the outcome of the bet should be provably fair, meaning the casino and all players can verify the randomness of the outcome.

Solution to Player vs Casino

The situation where only one player plays against the casino is easy to solve. The casino holds a serverseed and the player has a clientseed. The casino commits on its serverseed by revealing the serverseed-hash to the player. After the player chooses his clientseed which is then sent to the server, the outcome will be generated and the casino reveals the serverseed. The client can check if the given serverseed corresponds with the committed serverseed-hash. This way neither party can secretly influence the bet in their favor.

Solution Player vs Player

Unfortunately, the solution presented above does not work for a player vs player bet, because the players would need to send hashes of their clientseeds to each other before revealing their clientseeds. This poses some serious problems like when a player fails to submit their clientseed due to disconnection after revealing their clientseed-hash. Besides the fact that a user could disconnect, there is also the issue of the casino secretly checking the outcome.

Let's say we have a 2 player scenario, player 1 is Alice and player 2 is Bob. Alice is just an honest player, but Bob secretly works at the casino and has access to all website information. Alice could never know that Bob is a casino employee. But Bob could receive Alice’s clientseed and check the outcome. If the outcome is not in Bob’s favor he could just disconnect from the site and leave the bet unplayed and thus has the ability to only choose winning bets without Alice knowing.

To counter this we could give both players the opportunity to submit their clientseed after disconnection but within 48 hours. Once the clientseed-hash is shared the bet is going to have an outcome. Either the bet proceeds as usual or one player disconnects. If one or both player(s) disconnect the bet will be frozen until the clientseed(s) have been submitted. If the clientseed was not submitted by one player within the 48 hours, then the other player automatically wins. If the clientseed was submitted within 48 hours, then the bet will proceed as usual. If neither player submits his/her seed within 48 hours the bet will be canceled.

This way a casino employee has no motive to not send their clientseed, since he will 100% lose if it was not submitted. If a user unwillingly disconnects they would still have the opportunity to submit their clientseed within 48 hours.

More then 2 players

Here is where it gets tricky, the solution above is not perfect in the sense of playability. With a 2 player scenario where the casino employee has no motive to cheat. The only situation where a bet is frozen is when a player accidentally disconnects. Now this will happen sometimes but even if it does the player who disconnected does want to know the outcome and thus has the motive to submit their clientseed as soon as possible.

If there is a bet with 100 players the chances of a disconnection greatly increase. Besides this are there always people who like to keep others in the dark on purpose (trolling the bet).

We would need a solution to ensure that the bet could always proceed as usual without the interference of any malicious party or the ability to be frozen.

Requirements

  • The outcome of the bet must be completely random and verifiable.

  • Either the casino and all players must have influence on the outcome, or neither party should have a direct influence on the outcome.

  • No external sources of randomness like blockchain or a 3rd party such as random.org.

  • The situation where a player disconnects from the casino server as
    well as the situation where the casino’s server goes offline must be accounted for.

  • Any possibilities for malicious behavior should be removed.

  • The entire process/protocol should take no longer than 10-15 seconds.

jp flag
If a majority of participants can be assumed non-faulty then you should look into byzantine-tolerance algorithms. But then your description sounds like you want to tolerate any number of byzantine agents, and the protocol must always output some result, then I strongly doubt this is possible, due to impossibility results on byzantine consensus when the majority of agents are malicious.
Mathijs avatar
mo flag
Good suggestion @user2249675, but I already looked into majority consensus algorithms. The main issue is that the casino employe could pose as 3 players in a 4 player bet and thus holds the majority over honest player.
Score:4
ng flag

There's quite a bit of relevant cryptographic literature on this topic. Significant sticking points are the dual requirements of

The situation where a player disconnects from the casino server as well as the situation where the casino’s server goes offline must be accounted for.

Any possibilities for malicious behavior should be removed.

This two properties are known to be impossible to simultaneously achieve. This initial result is due to Cleve in 1986, but here is a paper which might interest you. A relevant section of the abstract is

A classical result by Cleve [STOC '86] showed that for any two-party $r$-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by $\Omega(1/r)$.

This is true essentially because

  1. in any protocol, there is a time step where each player can compute what their coin flip will be at the end of the protocol
  2. this time step differs for each player --- in particular, for one player they will need to continue talking after this time step for the other player to recover their coin flipr
  3. if they disconnect whenever they get a coin flip they don't like, they can bias the result of the coin flip into something they like more.

This is to say that disconnecting can be done by malicious parties to bias the final result in their favor, so you can't simultaneously rule out all malicious behavior, and allow parties to disconnect.

There are some ways around this, but they use a somewhat non-standard notion of security that makes certain game-theoretic assumptions about the underlying participants (see Fair computation with rational players). Depending on your setting (if the "payoff" for participating in the protocol is fixed) this might be fine. Note for settings with adaptive bet sizes, i.e. poker, this might not be good enough (but I haven't thought about it much).

Edit: While I haven't read this paper, this very recent paper is probably a better pointer for you to look into. Again though, without knowing what you are using the coinflips for, it might not be directly applicable. In particular, it looks like the relevant utility functions for players must be public. For betting on coin flips directly, this should be achievable, but as a source of randomness for something like poker, it might not.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.