Introduction

Introduction and prior work

This project is an experiment in decentralized (serverless) P2P gaming.

In multiplayer games it is essential to synchronize the game state between players. Massive online games use a centralized server which accepts player moves and broadcasts them to other players. LAN games between small groups of people also use a single server, which must be trusted by other players (as it is possible to modify the server software and make it not accept certain moves). Server also provides authentication, so players cannot impersonate other players.

Usage of public key cryptography allows players to sign their moves. In this case they do not have to be broadcasted by the server — players can broadcast their digitally signed moves over the P2P network. However it is still possible for a player to broadcast different versions of his move to different nodes. Thus even in this case a centralized server is needed, which timestamps the moves and signs them its digital signature.

In a protocol was proposed which does not require a server. For timestamping of the moves players must wait till all other players broadcast their moves and update the game state by one time-step after that. First, salted hashes of moves are broadcasted, so the players can accept each other's move without knowing the move beforehand (so they cannot cheat by making their move dependent on other moves within one time-step). Then players reveal the salt and decrypt each other's moves. This still has two drawbacks, which make the game suitable only for small LAN competitions where players know and trust each other:

• player may broadcast two different versions of his move (hash) and unless the P2P network is fully connected some nodes may not detect this and the game state will fork
• player may fail to broadcast his move (refuse intentionally or due to network problems) and slowdown/disrupt the game

Even if we set disqualification rules, such as

• banning a player who broadcasts two versions of move within one time-step
• set a time-out after which player moves are ignored for the current time-step and the game advances

we still cannot guarantee that all the players have the same view of the network state. Due to different packet traversal times, a malicious player may send his move several milliseconds before the time-out. As a consequence some players will reject his move and some will not, thus the game state will fork.

We propose a solution to these problems, which provides consistent game state across all players in perfect information games.

Our approach

In this project we propose to use Nakamoto block-chain (notably used in Bitcoin cryptocurrency and Namecoin decentralized DNS) for timestamping player moves and assuring a consistent game state across all nodes. Proof-of-work is used for sealing all known player moves by the miner node into blocks, which can be easily validated by every other node.

We achieve the following properties:

• Decentralization — lack of single-point-of-failure which could disrupt the game
• Consistency — every node has the same view of the game state (more precisely — of the past game states except several recent states, as there is a small chance of the network being forked for short periods of time, until a consensus is reached, i.e. some chain becomes longer than its alternatives)
• Authenticity — player can only do moves of his character(s) using digital signature
• DDoS protection — it is hard to produce excessive amounts of valid transactions, because they would cost a fee (hash-cash)

Also achievable, but omitted in our prototype implementation:

• Fairness — players cannot see moves of other players for the current timestep, until the game state is advanced

This can be done by introducing two alternating types of blocks. In odd blocks only salted hashes of moves are accepted, in even blocks players reveal salts and make moves (i.e. the two-phase approach proposed by Baughman et al.) It's still possible for a player to not reveal the move if it turns out to be worse than non-moving. This can be penalized e.g. by forcing the player to skip another move after that.

The blocks in Nakamoto chain contain spendable hash-cash ("coins"). We also use this, with 50% going to the miners and 50% dropped randomly onto the game map, where players can collect it.

Implementation

We modified the Namecoin GUI client, as it fits our needs the best. Namecoin is essentially a decentralized storage of key-value pairs with verification that a key cannot be created twice. Value can only be modified either by the creator of the original key (using digital signature) or after the key expires. To assure such a consistency requirement Namecoin creators added some state-based verification rules, which very well suit our needs of maintaining the game state.

For the game we use a separate network, i.e. the Namecoin network is not used in any way.

Keys are player names. Namecoin's name_new operation is used for creating a new player. Values are moves, encoded as JSON strings. Namecoin's name_firstupdate operation is used for spawning a player on the map. name_update is used for performing moves.

Only one move per block is allowed. Moves within one block are unordered, i.e. happen simultaneously. Thus block is a quantum of time (chronon) for the in-game universe.

Normal transactions that transfer coin from one address to another (with no relation to the game) are also supported. Plus there are additional transactions created by the game engine and based on the current game state. Currently there are two types of such transactions:

• game reward, when player collects a coin on the map
• player death, when the game nullifies the key-value pair of the player

Planned (not implemented yet):

• player-to-game payments, allowing players to buy in-game items
• taxes that go to miners, when player harvests some coins inside the game

Taxes will be like transaction fees, except they will be applied to game-to-player transactions. They will motivate miners to include players' transactions into block, instead of ignoring them. This is especially crucial if block reward percentage is decreased, increasing the game reward percentage.

Game transactions are never broadcasted, they are always deterministically recomputed from the game state (which is computed using name_* transactions). They are, however, stored on the disk for a faster lookup. Game transactions have hashes like normal transactions, so they can be spent. For game reward transactions we use the same maturity rule as for block reward — it must mature for 100-120 blocks before it can be spent. In this sense game reward transactions are just like coinbase transactions — they create coins out of nothing, but the total amount of generated coins is limited.

See also

1. Huntercoin
2. Transactions