2
$\begingroup$

Alice and Bob are sitting on an online casino table which exposes the following game: the table randomly generates a number R and piblishes this number. The player which "bids" the highest number between 0 and R wins. If two players bid the same number, they are both excluded from the game (only unique bids can win). Players must be assured that the table didn't cheat by allowing a colluding player to bid while other players are revealing their bids.

The game is so structured: 1. All players, individually, choose a number and publish a non-malleable commitment to that number, which any player can see. 2. After some time, the table stops accepting bids. 3. Each player reveals their bid along with the commitment proof. 4. The table declares the winner.

The "closing bid" signal doesn't necessarily reach all players at the same time, but there can be a delay of some seconds.

How can the players be sure that table didn't cheat by accepting bids in the middle of the revelation process? Or to figure out that a bid has been made after all others? Is there a way to "timestamp" the bids without trusting any third party?

$\endgroup$
2
$\begingroup$

Let me restate your game to be sure I understood you correctly:

  • There's $n$ players
  • Casino presents number $R$
  • Each player sends commitment to some number $0$ and $R$
  • After that casino sends "betting closed" signal to all players
  • Each player sends his chosen number + proof for commitment
  • Player with highest unique number wins

Your problem is: how to proof that casino will not take any bets after some players send their numbers.

Solution: Use some signature scheme. Casino during "betting closed" signal sends list of all commitments it has received before closing signed with its public key. Only after receiving this list player sends his number + proof. Then if casino declares winner that is not in the list, player can show proof of cheating.

Said that I think there's more fundamental problem with this game: even when casino is perfectly honest, group of colluding players can turn odds in their favor:

  1. if $n=2k, k>0$ then group of at least $k$ players can assure that no one else can win
  2. if $n=2k-1, k>1$ then group of at least $k$ players can assure that they will win

In both cases strategy is the same: group bets $k$ values: $R,R-1,R-2,...,R-k+1$. To any player outside of the group to win it's necessary to match all group bets + have one more bet (between $0$ and $R-k$).

But in case 1 there is only $k$ players outside of the group so you can't have winning bet outside of the group (group can still win if any two players will bet the same number).

In case 2 there is only $k-1$ players outside of the group so at least one of $R,R-1,R-2,...,R-k+1$ will be unique across bets and it'll be for sure highest bet, so group will win every time.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for your answer! I'd like to add one more question: assuming that the time to reveal the commitment expires after a while, is there a way to prevent the casino from rejecting revel requests and using them just to "catch" the revealing value (before rejecting them, let's say cheating by saying "system error, try later"? $\endgroup$ – Philip Mar 5 '18 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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