5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Can you be more precise about exactly what would qualify? Does it have to be an example of such a protocol that was specifically used in a game? Or proposed for use in a game? What if it was a general consensus protocol that's not specific to games? Possibly vaguely relevant: en.wikipedia.org/wiki/Brooks%E2%80%93Iyengar_algorithm. $\endgroup$ – D.W. Dec 5 '15 at 2:39
  • $\begingroup$ An actual real life usage would be best. A paper describing such a system would be adequate, as would a proposal. Basically, I'm looking for reasons why it hasn't been done or examples of it having been done. $\endgroup$ – nfirvine Dec 7 '15 at 21:45
  • $\begingroup$ Brooks-Iyengar is very useful. If game state could be represented as a scalar (not quite a hash), might be used to detect aberrations (cheating). $\endgroup$ – nfirvine Dec 7 '15 at 22:12
  • $\begingroup$ there are some similar concepts in Tor routing where "cheating" might be breaking the anonymization etc... $\endgroup$ – vzn Dec 8 '15 at 4:45
  • 1
    $\begingroup$ also, Bitcoin is based on the byzantine generals problem which has related study. you seem to be asking about a mix of fixing cheating vs fault tolerance which byzantine generals is a specialized study of & there is related theory, its also considered part of Cryptography. try also Computer Science Chat to clarify/ discuss etc. $\endgroup$ – vzn Dec 8 '15 at 16:04
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is close to but not quite what I was looking for. (Interesting nevertheless, thanks!) One of the intentions of my system is that you can do away with server-side simulation to avoid those costs (development, hosting). I've updated the question to make this more clear. $\endgroup$ – nfirvine Dec 7 '15 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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