Consensus protocols in multiplayer video games

Question

I'm not 100% sure this appropriate for CS. Sorry.

I'm looking for prior art on an idea I had, but either my Google fu is lacking, or it genuinely hasn't happened.

In distributed systems, there are a number of consensus protocols and implementations (Raft, Paxos, Zookeeper, etc.). There's also the Bitcoin blockchain. Both of these approaches allow the cluster/network system to recover in the face of split brains and sometimes in the face of an evil node.

In the games world, there are really only two architectures in use:

• Client-server, where the server simulates the game and is the source of truth and the clients simply act as a dumb terminal. No cheating possible. (Sometimes the server runs on a client.)
• Peer-to-peer, where all clients broadcast their status to all other clients. Cheating very possible.

I am thinking of a third architecture that enhances the peer-to-peer architecture with a voting-based cheat detection. Desynchronized game state would be rejected by a majority vote. A colluding majority would be required to cheat.

The practical purpose is two-fold:

• To eliminate the necessity of the server-side implementation of game simulation (e.g., game state machine). In the client-server model, you need to either write the implementation of the sim twice or write it generically enough that it will run in both client and server environments. For practical reasons, a shared codebase is difficult to do.
• To eliminate the computational burden of running simulations. For large online games, this burden is not insubstantial.

I'm wondering if there's any research on such a system (either similar systems having been invented and used or even a paper describing it) specifically with respect to multiplayer games.

Answer 1

Section IX of the following paper proposes a variant of your idea:

OpenConflict: preventing real time map hacks in online games. Elie Bursztein, Mike Hamburg, Jocelyn Lagarenne, and Dan Boneh. IEEE Security & Privacy 2011.

The difference is that they propose that detection can be done by the central server, after the fact, by analyzing all of a client's status messages for consistency. Your scheme differs only by having other clients do the same analysis. (Their proposal also has some extra hashing and signatures and cryptography, which can probably be ignored for your purposes.)

Their scheme is basically a more sophisticated version of what you propose: rather than requiring everything to be broadcast, it only has to be uploaded to the server at the end of the game. This has two advantages: (a) it significantly reduces network traffic, because they upload to the server rather than broadcasting to everyone; (b) by using commitments and hashes, they don't have to broadcast the full status messages to all other players on-the-fly; instead, it's enough to batch up all of those messages and upload them at the end (all that they need to broadcast at each step is just a commitment/signed hash, which will be much smaller and thus much more efficient to broadcast). I wouldn't be surprised if they were already familiar with your proposal, but considered it too trivial and too inefficient, and so wrote only about a more sophisticated version that is less obvious and more efficient.

I recommend you take a look at the following book:

Exploiting Online Games: Cheating Massively Distributed Systems. Greg Hoglund and Gary McGraw. Addison-Wesley.