# Can adversarial agents flip coins?

I was thinking about peer-to-peer games by considering a simple coin tossing game.

You open up your version of P2PCoinFlipping Beta 2.3 and it displays a list of player name servers. After choosing the closest server a scoreboard of the luckiest players appears. You choose the highest ranking player and the game begins. Since you started the battle the opposing player chooses the coin side, heads, and you are assigned tails. A nice little graphic appears displaying a tumbling coin eventually landing on heads. Too bad, you lose.

But how do you know the outcome is fair?

If the outcome is chosen on your computer you can edit the program to choose to win and the same applies to the opponent. The game isn't deterministic so you can't seem to validate the outcome.

Is it possible to have multiple independent adversarial agents agree on a non deterministic event?

• Though not answering the question, this is why server-based multiplayer is good - let the server be the arbitrator. An interesting idea would be to rely on some third party service as the coin flipper. Could one for example use an online GUID generator (like guidgenerator.com) as the basis for a system? Apr 30, 2012 at 16:44

This procedure will do the job:

1. each of the two peers generates a random number.

2. each peer creates a salted hash of its number and sends it to the other peer.

3. either peer rejects the request if it got the same hash that it sent.

4. once both peers confirm reception of each other's hashes, each then sends the other its actual random number.

5. each peer verifies that the hash sent by the other is actually a hash of the random number. reject the exchange.

6. the result of the coin flip is the XOR of the least significant bit of each number, i.e.

(a & 1) ^ (b & 1)

An alternative solution:

1. Each of the two peers decides between them to decide who should go first. Let's call them A and B, just to be original.
2. Peer A generates its random number, creates a salted hash from it and sends the hash to peer B.
3. B generates its random number and sends it to A.
4. A sends its random number to B.
5. B verifies that the salted hash is the hash of the number it has received.
6. the result of the coin flip is the XOR of the least significant bit of each number, as above.

I have asked this question on the cryptography site and have established that it is pretty secure. Apparently this is a variation on the Commitment scheme.

• This protocol as described is vulnerable to a replay attack, where one peer just echoes back the other peer's messages to force the result to be 0. There are several simple modifications that can be made to prevent this attack, though. Apr 30, 2012 at 15:23
• This version should be fine. May 1, 2012 at 9:36
• How does this stop a peer simply choosing a number rather than randomly generating it? May 1, 2012 at 13:22
• @Kylotan: It doesn't, but as long as at least one of the peers chooses randomly, the result will be random. May 1, 2012 at 13:49
• A peer has nothing to gain even out of choose 0 all the time, because then this gives the other peer the advantage. The final result depends equally on the numbers contributed by both peers. May 1, 2012 at 14:38

It turns out that not only can adversarial agents flip coins, but adversarial agents can play poker.

That said, it tends to be extremely computationally expensive, and quite difficult to get right. It's probably not worth the implementation effort. Look at how many multiplayer protocols are hilariously vulnerable to a malicious server (namely: all of them that I'm aware of), and how popular they still are, and it simply doesn't seem like a practical use of time.

StarCraft II is a good example. It's a game where scouting is critical, and knowing what the enemy is doing can give a phenomenal advantage, and five-figure or greater prizes regularly rest on the outcomes . . . and yet both computers have the entire game state stored at all times! It's trivial to write a program that lets you watch the opponent directly and get a huge leg up on them.

Turns out, none of the serious competitors use these programs. It's too easy to detect ("hey, Jim, how do you always know what I'm building the instant I'm building it?") and just not worth the trouble.

That said, if you want more info, you'll want to look into cryptography in detail - this isn't really in the realm of game development.

• Modified servers can also be interesting as well as malicious. I know the game Sauerbraten had/has a "race mode" fad where instead of shooting each other, you just try to run through a level as fast as possible. How do they do custom levels, well, they pretend to be in multiplayer-level-editor mode so they can force you to download the current level state when you join... Feb 23, 2021 at 10:27