Commitment for bid

Question

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?

Answer 1

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.