Is it possible to implement a secure game without having a reliable arbiter?

Question

N players are playing a perfect information game (the kind of game where everyone knows moves of everyone) by making moves by turn (P1, P2, ..., Pn, P1, ..., Pn, ... till the game will finish). Game has specific rules for every player (if a player makes a move against the rules - he loses automatically) and can finish only if one of the players win. I am trying to figure out whether it is possible to implement a secure game without having a reliable arbiter (who can be trusted). By secure I mean that none of players would be able to cheat and be unnoticed.

Here are some of my thoughts about it:

If none of the players cheat, than nothing should be done: players just make move and in the end the winner is announced. But if players can cheat, each next player can verify that the previous player has not cheated (it is perfect information and the rules are known) and if previous player cheated - he will lose right after this. If players can start to cooperate with each other (player 1 cheated and player 2 decided to cooperate) every player can verify all previous moves and players who cheated or cooperated will lose.

But here is a problem. Nothing prevents a next player to tell that previous player cheated even if he is not. Of course next players can check for this, but if only 2 player are in the game it will not work.

On the other hand it is possible to have a trusted arbiter who verifies every move. Player 1 makes a move - gives it to arbiter. It verifies it and transmits it to other players. And so on.

So is there a way to make a secure game without the arbiter?

P.S.

• if this sounds too abstract, think about this as a chess game. 2 players, perfect information, rules are rules of chess how to move, players can cheat by making illegal move
• I am not really sure that this is a correct place. I hesitated between mathematics, security and cryptography. If I am wrong, please move it to another place.

Answer 1

If everyone has a complete copy of the game state at time T, and the permitted moves can be deduced strictly from knowing the game state, then it's possible to identify cheating without an arbitrator, though telling who is cheating requires that the majority of players are honest.

Everyone starts the game with a complete copy of the game state (implicit in this being a perfect information game), and making a move involves broadcasting it to all the other players.

Claiming person P1 cheated isn't simply a matter of telling the other players that they cheated. Instead, a claim of cheating would be for player P2 to tell all the other players "Given game state S, player P1 told me they made move M, which is against the rules". Everyone can verify this by comparing S against their idea of what the game state should be, comparing M against the move they received from P1, and checking to see that M is against the rules.

At this point, the main issue is distinguishing cheating by P1 from lying by P2.

You can eliminate tampering with moves by having every move cryptographically signed by the player who makes it: if P2's claimed M has a signature that doesn't check, they're lying (if P1 sent a move with a signature that didn't check, P2 would have rejected it).

There's another way of cheating, though: if P1 sends a consistent series of legal moves, but the moves sent to P2 are different from the moves sent to everyone else, it can give P2 a false idea of the game state and induce them to make a false claim of cheating. If the majority of players are honest, this can be thwarted by having everyone compare what move they think was just made, but if the majority are collaborating with P1, they can lie to P2 about what move they just received. In this case, I'm not aware of any way to prevent it.

Answer 2

In short, no, you can't absolutely prohibit, or even detect, cheating 100% of the time, without the presence of some middle ground (an unbiased server). The major problem comes down to the client itself. The binary could be hacked or modified in a way that would be transparent to the network, thus allowing the cheat client to perform several acts maliciously. Since there's no way to verify a client isn't hacked, that means that all sorts of impossible-to-detect scenarios could come into play.

False Cheating Claim

It could try to make false claims of cheating in an attempt to abort a losing round. In a game of more than two, all that has to happen is to have A claim that B cheated to C, which could cause a consensus, forcing B to quit. Even in a two player game, the result would be a cheat-counter-cheat loop, resulting in both clients calling the other cheaters at the same time, forcing a draw or invalid game state.

AI Booster

A hacked client could provide some sort of AI assisted move generator to increase the chances of winning, predicting moves many thousands or millions of moves in advance, leveraging all sorts of algorithms to enhance the player's odds of winning. This is completely undetectable in a well-designed cheat client, as it could employ random or educated guess delay timers to give the appearance of human thought.

Force Invalid Game State

A client could falsify which moves were actually being played, possibly forcing the other end into a position where it has no legal moves and must declare itself a cheater. While this would very likely be obvious in a well-known game such as chess, a new game with new rules that users are not fully familiar with might miss some subtle interaction, and the client could depend on other players missing that move. It could also just send different moves to different clients, all of them legal, until, due to the invalid game state, another client makes an invalid move and itself is declared a cheater.

Exploit Flaws

A client could exploit any flaws in the game engine's "legal-checking" algorithm. Most software usually has a few bugs laying around, and any such bug could be exploited to win a crucial move or force a losing position.

Cooperative Clients

Two or more clients on a single game could maintain their own game state, while the legitimate client is left out of the actual game state. This could help foil two-flags-required algorithms to prevent a single false claim in a greater-than-two-player game. As long as the cooperative clients control at least 50% of the game state, there's really not much anyone else can do about the situation except drop out.

Race Conditions

A modified client A could tell B about C's move before C has a chance to make that move. This would be especially true if the clients are designed to use a token-ring-style system, where client passes the game state to the next client, especially if the clients not only verify that a given game state is valid, but also if the game state is valid as compared to the prior game state. The only way to avoid this would be to make sure that all players broadcast their move to all other nodes, those nodes independently verify the move, and the origin of the play came from the player it claims to have come from.

IP Spoofing

It could be possible to fake another player's move simply by spoofing their IP address. Of course, this won't be a problem for SSL, because it is designed to prevent such communications from occurring. A weak transport layer protocol could cause problems.