Preventing cheaters in Fog Of War Games

tl;dr: I think we can use blockchains to solve cheating in Fog of War games.

Can Fog of War be solved for decentralised blockchain games? I think so! Moreover, the nature how blockchains work make them uniquely suited to solving this problem.

So what’s the big deal?

On Twitter, I recently posted a picture that suggests two players are looking for each other within some gaming world.

Link: https://twitter.com/EAThomson/status/1264994996807176199

It is typical that games have some element of surprise, where the initial map may not be fully revealed or that player positions are initially hidden from each other. In addition, the respective fields of view should also not be known to each other.

It turns out that players who are skilled programmers can actually cheat and peek into the hidden parts of the map and even look at hidden player positions. Naturally, this seems like it would also be a problem for blockchain games where actions are stored publicly.

Part of the solution to the problem involves an interesting piece of cryptography known as Private Set Intersections. This is something that I also mentioned recently on Twitter:

I believe this is an important piece of technology that we need to enable real-time decentralised games such as RTS and FPS games. While PSI helps, it isn’t robust against players who are dishonest. I’ll discuss what all of this means in this blog.

What is Fog of War?☁️

“FoW is the uncertainty in situational awareness experienced by participants in military operations.”

The concept applies to many different types of games not just those about war. Fundamentally, it is about having some piece of the gaming map that’s hidden from the player’s view.

Gamers from the 1990s and early 2000s should fondly remember the Real-Time Strategy genre that was dominated by titles such as Command & Conquer, Red Alert, and Total Annihilation. FoW was an important part of these games as they forced players to make plans, have a strategy, and mange their risk.

When a new game is started only a small section of the map is shown to the player, the rest is hidden until a player moves into the respective unrevealed terrain. Certain units had better “eyesight” so could reveal the map faster as they moved.

Total Annihilation had both Fog of War and true line of sight (source)

Quick note: Fog of war and line of sight are similar problems in spirit and probably even have similar solutions. For simplicity, I will ignore references to line of sight, but I do think they can be both be solved in a similar way.

Cheaters, Peekers👀

This is a problem for multiplayer gamers where a person with such a tool could easily cheat and win the game. For RTS games, the multiplayer mode was always done in a peer-to-peer manner meaning that there was no central server to dictate which units should be revealed.

Can we solve the peeking problem?💡

The nature of this problem feels like it could be solved by throwing cryptographic at it, somehow. If we can throw a multiparty computation, homomorphic encryption, or zero-knowledge-”something” then we ought to be able to solve it. It’s fine to dream what the solution might look like, but better to have something practical.

Interestingly, back in 2011, a team of researchers demonstrated a practical solution, but it has the caveat of honest players (can’t lie about the position of your units). The following is a link to their paper:

OpenConflict: preventing real-time map hacks in online games

Firstly, the team created a tool that let them peek into computer memory in order to prove that cheating was possible. They were able to see the map and their opponent’s units, as expected.

Picture showing the in-game view and a representation of memory (source)

In addition, they also developed a practical cryptographic solution to help hide a player’s units in memory. This is where they used Private Set Intersections (interestingly, this is also a technique that has been proposed to be used for contact tracing for COVID-19).

A simplified protocol run (source)

What PSI allows is for players to share their units with each other in such a way that the position of the units, and their respective fields of view, are not revealed unless the opponent should actually be able to see them in accordance to the proper rules of the game.

One extra important point to add is that the naive method of implementing PSI doesn’t hide the number of units that a player has. Therefore, the researchers suggested to add padding in order to obfuscated the true number of units.

For the games studied by these researchers, the computation time was actually reasonably rapid even back in 2011. So the extra complication here does not add much overhead.

The PSI solution works whenever players only desire to peek into memory of their own computer (passive cheaters). The solution fails whenever a player lies about their position in order to gain better visibility of the map. When a player lies about their position they are an active attacker. Such an attack would require creating a custom tool, but not impossible for a programmer with the right skills.

Huge thanks to Anuj Das Gupta for linking me to this piece of research.

How can we prevent active attackers?🔨

As homomorphic encryption improves I do expect something to come out of it that solves this problem in general (assuming that isn’t already the case!). I also hope that the solution can be efficient.

For FoW in games there might be some way to encode all the game logic with the same cryptographic mechanisms as previously presented, but I don’t have a clear picture of that in my head.

In a practical sense, we ultimately need to reveal the end state of the game and all the actions that happened and then determine who the honest winner was.

A simple approach is to appoint an trusted-third party as an arbiter. This could be a single person or a group of people, but if this is done using a simple centralised architecture then it will be prone to collusion. For a decentralised blockchain game, this isn’t a solution.

Can blockchain prevent active attackers?⛓️

Blockchains can help solve the problems of trust, but there are still a few more tricks required since the player moves cannot be put on-chain where they reveal data that is supposed to be hidden.

The Xaya team have built a battleships game (Xayaships) that uses game channel technology to hide the positions of the 2 players’ battleships. The processing of gameplay happens off-chain in what they call a game channel (state channel in Ethereum parlance), which means that gameplay can happen almost in real-time. The resolution and determination of the winner is at the end of the game and settled on-chain.

This is something that sounds inspiring for finding a solution to FoW in a decentralised game; however, what Xayaships doesn’t have is moving pieces nor a visibility for each ship. In fairness, it doesn’t need it.

In the example mentioned in the research paper, players play in a purely peer-to-peer manner which in itself sounds like a game channel. A reasonable guess is to use the Private Set Intersection method used in that previous research paper where players share obfuscated positions and visibility sets, but the determination of the winner has to occur at the end of gameplay in a decentralised way.

To solve the decentralised arbitration problem, players could use a transaction to put hashed positions of their units on-chain. The hashes would be unique per unit and be computed from their position and a unique per-unit salt. (There might be a better scheme, this is just a suggestion). This means that the players can’t later change their starting positions to alter the outcome of the game.

As with the research on PSI in the previous section, it is likely necessary to add padding in order to obfuscated the true number of units.

At the end of the game, these initial positions (held on-chain) would be revealed along with a log of all the actions performed. The game physics must be deterministic so it would be possible to determine from knowing the initial starting state, which is public but initially hidden, and then checking that the actions lead to the correct end-state.

Should a player try to cheat during the game and say that they were in position where they weren’t then verification of the game actions would show whether the player was in the correct position or if they lied.

This method does all the verification at the end of the game, but there may be alternative methods where unit hashes are committed to the chain with every move. This puts a lot more data on-chain, but may be necessary in order to find a working solution for an open-world MMO game.

Acknowledgements 🏅

About me🎯

One of the main projects of the foundation is the Polkadot network. A next generation blockchain platform. To read more about the innovation that Polkadot is bringing to the blockchain industry I invite you to read the following blog post: link.

Questions / Comments?❓

Blockchain, Gaming, Web 3. (previously: https://web3.foundation)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store