6
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user2249675
    Feb 13 at 18:38
  • $\begingroup$ 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. $\endgroup$
    – Mathijs
    Feb 13 at 21:17

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • $\begingroup$ Apologies for the very delayed response, I needed to find the time to read and understand all the information that you provided. To start off I would like to explain how the game works: Each player in a 4 player game has a win chance. These win chances come from the percentage there bet is from the total bet amount. For example player 1, 2, 3 each bet 2 dollars and player 4 bets 4 dollars. Win chances would be 20%-20%-20%-40%. The information you provided mainly revolves around coin-flips. But as you can see in the question, we already have a viable option to ensure a fair coin flip. $\endgroup$
    – Mathijs
    Feb 22 at 18:52
  • $\begingroup$ In addition to my comment above the casino can be trusted in a way that they will enforce any given protocol to ensure a fair outcome. This it the only advantage we have over the 2 party protocols. The main issue stems from the fact that the end calculation needs all inputs, but one users could lie about receiving those inputs. $\endgroup$
    – Mathijs
    Feb 22 at 18:53
  • $\begingroup$ the attack you've mentioned is the standard one in the setting that you want to tolerate aborts. Your response seems to be (effectively) not tolerating aborts, and instead penalizing an aborting party (where "abort" here means "for at least a 48 hr time period"). This can probably work in general. $\endgroup$
    – Mark
    Feb 22 at 22:35
  • $\begingroup$ as for coin-flips vs other things, coin flips suffice for most applications. For your particular example, you want an exact sample from a categorical distribution with probability vector $(.2 .2, .2, .4)\in\mathbb{R}^4_{\geq 0}$. You can reduce this to coin-flips in standard ways, provided the probability vector is of the form $(a_0/2^{k_0},\dots, a_n/2^{k_n})$ for integers $a_i$ (i.e. the probabilities have a finite base-2 representation). Then you can sample using a finite # of coin flips (quite close to the entropy of the underlying distribution) using what is known as Knuth Yao sampling $\endgroup$
    – Mark
    Feb 22 at 22:38
  • $\begingroup$ this is to say you can reduce to exactly sampling from any distribution where the underlying probabilities have finite-length base-2 representations to sampling a finite # of fair coinflips (then post-processing by some explicit function) in a generic and efficient way. if the probability vector is not of that form you can approximate it of that form to approximately sample from a nearby distribution, where "nearby" can mean "in a way not detectable with probability better than $2^{-100}$" without much practical cost. $\endgroup$
    – Mark
    Feb 22 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.