Rock-paper-scissors over network, how to protect from cheating server?

Question

I'm trying to design cryptographic protocol to play Rock-Paper-Scissors with two parties, neither trusting each other, nor trusting server they use for communication, so game is 'provably fair'.

So there are Alice and Bob. They don't know about each other, and they've came to server to match them with each other, with server prompting them to make a bet.

1. Alice comes to server and deposits some money
2. Bob comes to server and deposits some money independently of Alice
3. Alice thinks out of her bet (say, 'rock'), but tells server HMAC('rock', 'some_random_secret') instead of just plain text, to prevent server from implementing always winning bot.
4. Bob tells server HMAC('paper', 'secret string by bob')
5. Now server has both commitments, and it publishes them to parties, so Alice gets Bob's commitment, and Bob gets Alice's commitment. Server does not know actual moves.
6. Now server expects for Alice and Bob to disclose their choices and secrets, and depending on disclosed choices, pay out the pot to winner (minus some server royalty), or if draw just returns money.

Now here is problematic case: imagine there is no Bob, but only server pretending to be Bob.

1. Alice deposits her bet to clearance account and sends pseudo-Bob commitment of her 'rock' move.
2. Server responds Alice with clearance of some random move.
3. Alice discloses to server plaintext of her move.
4. Now server checks if it's own move was winning — if it was, server claims victory and gets money Alice deposited, providing Alice with proof. If server appears to be losing, it just pretends pseudo-Bob left the game due to connection problems or whatever, cancelling the deal and returning Alice money.

It's not possible for real Bob to cheat this way, because when Bob gets Alice plaintext, he had already sent his own plaintext, so server knows who had won and who hadn't.

I've been thinking about closing deal by timeout if second party does not respond with plaintext within some reasonable time (or had provided plaintext that does not evaluate to commitment given before), but in cheating server case it's possible to pretend server just hadn't received Alice's plaintext to make her always losing.

Does a solution to this exist, or is this more like "pigeon chess"? How to convince both Alice and Bob server is fair?

Answer 1

If they don't trust the server they sure shouldn't send any money. The "trusted" third party is used to solve the problem of participants who don't trust each other. So by definition, your problem can only be somewhat mitigated, not solved completely.

I'm not sure what you mean by "provably fair". If the server can't prove he cannot cheat, it's not provably fair.

One way to do that is to award the bet to the remaining player if one leaves the game for any reason. Now if the server decides to keep the money by becoming unresponsive, Alice will know not to trust that server in the future, instead of keep losing money to it.

Another is to start communicating with Bob before the game begins and agree on a server at random. Now the probability of a server ripping off Alice is equal to the probability of Bob colluding with that server.

Lastly rock-paper-scissors doesn't depend on some input from the server, so the server can't prove fairness ahead of time.