Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 7 down vote favorite
1

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?

share|improve this question
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? – Tim Holt Apr 30 '12 at 16:44

2 Answers

up vote 6 down vote accepted

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. the last peer to receive the hash from the other 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.

share|improve this answer
1  
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. – Ilmari Karonen Apr 30 '12 at 15:23
This version should be fine. – Michael Slade May 1 '12 at 9:36
How does this stop a peer simply choosing a number rather than randomly generating it? – Kylotan May 1 '12 at 13:22
@Kylotan: It doesn't, but as long as at least one of the peers chooses randomly, the result will be random. – Ilmari Karonen May 1 '12 at 13:49
2  
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. – Michael Slade May 1 '12 at 14:38
up vote 2 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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