## Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks

In this post: how to beat map hacks, without a server to hide the information on, using cryptography.

### Map Hacks and Publicly Private Information

Map hacks are a common problem in real time strategy games.

Most RTS’s use a networking model called lockstepping. When lockstepping, the state of each player’s game is not synchronized so much as *kept* synchronized. Actions that players perform are queued, instead of being applied immediately, to give time to tell all players to apply that action at the same game time. This allows each player’s simulation to advance in exactly the same way; in lockstep. It would have been impossible for Age of Empires to keep thousands of units synchronized if they hadn’t used lock-stepping.

The downside of lock-stepping, besides the fact that it does a poor job hiding perception of lag, is that it makes the game vulnerable to map hacks. Lock-stepping *requires* every player’s game to know where every player’s units are. Your game can’t advance its simulation of your enemy’s units if it doesn’t know where they are! Because all the information is present, just not shown, making a maphack can be as easy as nop-ing over the code checking if a unit is visible (and there’s not much game developers can do about it beyond obfuscation).

Another reason the game needs to know about each enemy units is to figure out when units are crossing paths. This is difficult, because each player doesn’t have enough information to solve it on their own. Contrast that with (most) tabletop games, where players never need information they don’t have in order to know what moves they’re allowed to make.

For example, imagine a Magic the Gathering card with the following attribute: `Discard if another player has this card in their hand; otherwise do not reveal you have this card in your hand`

. Imagine you draw the card. You’re faced with a dilemma: you have to ask your opponents if they have the card, otherwise you might break the rules by failing to discard it. But you can’t ask your opponents if they have the card, because if they don’t then asking about it reveals you have it and breaks the rules!

One way to solve these sorts of problems, where a result depends on two private inputs, is to introduce a trusted third party. A judge looks at everyone’s hands, and tells you when you must discard. A server looks at the units of every player, and tells them about units they can see.

But… what if you don’t want to *need* a judge around in order to play your game? Can it still be done? It turns out that it is possible, using secure multi-party computation. That’s what we’ll be experimenting with today.

### Secure Multi Party Computation

I’ve previously explained how to do basic secure multi-party computation (SMPC) in the physical world by using locked suggestion boxes. The locked suggestion boxes allow you to perform an oblivious transfer, and oblivious transfer can be used as the basis for any SMPC protocol. So if we want to do some SMPC-ing in software, we just need a way to do oblivious transfer.

Unfortunately, there aren’t any established software libraries that implement oblivious transfer and implementing it ourselves would be… non-trivial. Really, really non-trivial. Dozens-of-people-checking-each-other’s-work-then-waiting-years-to-see-if-dedicated-cryptographic-analysis-fails-to-find-any-attacks-but-attacks-are-found-so-you-do-it-again levels of non-trivial.

Fortunately, there’s another technique that can be used as a basis for SMPC: secret sharing. Secret sharing lets you split a secret value into multiple shares, and recover the secret value if enough shares are present. Using secret sharing will force us to have at least three players present, but there are also upsides.

Secret sharing is simple enough that implementing it requires only a basic understanding of modular arithmetic and polynomials. Also, because secret sharing has information theoretic security, instead of security based on computational hardness, there’s no risk of a clever algorithm being discovered and ruining our day (though there are still ways to be wrong).

### How Everybody Computes

So we’re going to use secret sharing to do secure multi-party computation. What does that mean *exactly*?

Well, you can think of SMPC as simulating a virtual machine. Players do specific things in order to write private inputs to the machine, read private outputs from the machine, and perform operations within the machine. Let’s start with how to transfer a private value known only to one of the players into the simulated machine.

##### Input

When a player wants to input a value into the simulated machine, they use secret sharing to split the value into a share for each player. We’ll be using Shamir’s Secret Sharing Scheme, which uses polynomials over a finite field. We need at least four x-coordinates in the finite field we’re doing arithmetic in (one for the secret and one for each of the three shares), so we’ll be doing arithmetic modulo 5 (the smallest prime not less than 4).

To split a secret value into shares, such that only two of the shares are needed to reconstruct the point, we will create a line. The line’s offset will be the secret value, and the line’s slope will be a random value. The line’s y-coordinate at is the secret, and the y-coordinates at , , and are the shares for players 1, 2, and 3 respectively.

All in all, inputting a private value looks like this:

Let’s go through an example. Suppose the private value is . First, we pick a random slope . Suppose it happens to be . That means the equation for our line is . To make shares we just evaluate at each x-coordinate. Player 1 gets the share , player 2 gets , and player 3 gets .

Notice that, by changing the slope, we could have made player 2′s share be any of the five possible values in our finite field (just 0, 1, 2, 3 and 4). The reverse is true as well: holding player 2′s share fixed, we find that each possible slope corresponds to a different secret value. This is fundamentally why each player knows nothing about what the secret input is: the slope is hiding it.

##### Output

To extract a value from the simulated machine, player’s must combine their shares. Every player sends their share to the player, or players, that are supposed to get the output. The receiving players do polynomial interpolation on the points to recover the line (or parabola, since there’s three points) and evaluate it at to recover the secret output value.

Because we know we’re working with the integers modulo 5, and that there are always 3 players, this whole process actually simplifies quite a bit. We just multiply each share by a constant and sum them up:

Let’s continue our example from before. Suppose the shares owned by each player happen to be the ones we generated in the input example: , , and . We could figure out that these points are on a line with slope of and work from there… but for three players working modulo five, interpolating then evaluating at zero always simplifies down to this expression: . Computing that gives . As required, that’s the private input from the first example.

##### Addition

Addition of values in the simulated machine is dead simple: each player just adds their share of the value. The value encoded by the resulting shares is the sum of the two inputs. There’s not even any communication, as shown in this diagram:

Just to show that this works, let’s do an addition all the way from input to output.

Suppose player 1 has the private value and player 2 has the private value . They input them into the simulated machine, with the random slope hiding ending up as and the random slope hiding ending up as .

The degree-1 polynomial (a.k.a. a line) encoding is , meaning the players’ respective share are , , and . The polynomial for is , giving respective shares of , , and .

Once each player has been given their share, they add them together. The resulting shares are points on the polynomial that encodes the result. We have the points , , and . A player with all three points can figure out that the polynomial’s equation is , which encodes the value , which is in fact the sum of and .

##### Multiplication

Multiplication of private values is more complicated than addition. You start in the same way, multiplying each player’s share of the inputs together, but this causes a problem. Multiplying polynomials together creates a polynomial of higher degree: the resulting polynomial is quadratic instead of linear. If we didn’t have three shares we wouldn’t even be able to interpolate the result and, if we want to be able to do more multiplications without adding more players, we need to reduce that quadratic polynomial back to a linear one before continuing. (Also the extra degree of freedom would leak bits of private state.)

The way degree reduction is done is kind of amazing in a how-the-heck-does-that-work way: each player splits their share as if they were creating a private value, broadcasts the shares-of-shares to the corresponding players, then recombines the shares-of-shares that they received as if to reveal a private value. The resulting values are shares of the product. I don’t remember what paper I got this from, but there’s all kinds with the necessary information if you google around (like this thesis).

Here’s a diagram showing the process:

This one definitely needs an example from input to output.

Suppose we have private values encoding and , and that the slope hiding is and the slope hiding is . We want to compute , using only the shares.

The polynomial for is , meaning the players’ respective share are , , and . The polynomial for is , meaning the players’ respective share are , , and .

By multiplying the shares each player has together, we get the points , , . The polynomial running through these points is , which has the correct value at : . (We could have avoided interpolation by just using the simplified expression: .) The players never see this polynomial, because they do degree reduction.

Degree reduction starts by splitting each share as if to input it into the machine. Suppose player 1 uses the slope to hide , player 2 uses the slope to hide , and player 3 uses slope to hide . So player 1′s share splits into , player 2′s share splits into , and player 3′s share splits into . They send the corresponding shares to each player. Player 1 ends up with , player 2 ends up with , and player 3 ends up with .

Degree reduction finishes with each player privately recombining the shares-of-shares they received as if to read an output, with player 1 getting , player 2 getting , and player 3 getting .

The polynomial interpolates as , which has degree less-than-2 like we wanted and still encodes the correct answer ().

### Implementation

I used the SMPC explained above to implement a “game” with fog of war computed peer-to-peer, without a server, in Javascript. You can view the source in the below JSFiddle, or play the “game” (I keep using quotes because all you can do is move around) by clicking the ‘Result’ button at the top:

(In case JSFiddle is down, as it was intermittently while I was writing this post, you can view the code on github.)

(I count at least five things in the above code that betray the fact that it’s essentially the first time I’ve written javascript that’s longer than a dozen lines.)

The code implements a stack-based SMPC virtual machine. There are operations to hide+push, pop+reveal, add, and multiply.

To determine who can see what, the code uses those operations to rebuild the primitive we couldn’t start with (oblivious transfer). For each location on the map, and for each player taking their turn acting as the one receiving the result, the information at that location is obliviously transfer to the player.

The oblivious transfer is done by having the two sending players push 1 if they have a unit at that location, or 0 otherwise. That pushes two values onto the stack, which are then added. Since units can’t occupy the same location, the result pushed onto the stack is always either 0 or 1. Then the querying player pushes 0 onto the stack if they can’t see the location in question spot, or 1 if they can. Then a multiplication is performed, and the result is revealed to the querying player. When they can’t see, the result is always 0. When they can see, the result is 1 when there’s a unit present.

All three players are simulated locally, but could be communicating over the network with essentially no architectural changes. They don’t touch each others private information or anything like that.

### Impracticalities

If you’ve been considering how what I’ve been describing would work in more practical scenarios, you’ve probably realized that the answer is: not very well. I’ll quickly go over the issues:

**Trusting players not to lie**. We’re not using a verifiable secret sharing scheme and we’re not checking (after the game has finished) that players didn’t simply lie about what they could see. Dealing with adversarial players makes things a*lot*more complicated, but in practice you must.**Trusting players not to collude**. If two of the three players work together, they can reveal the private information in the “secure” computation. This is fine for an example, but in reality players gang up on each other all the time. Again, dealing with this makes things a lot more complicated, but in practice you must.**Huge bandwidth requirements**. The required network bandwidth is proportional to the size of the map! Players do an oblivious transfer for every location a unit might be in. This is worse even compared to synchronizing every unit, which was already significantly worse compared to just sending actions.**High sensitivity to network hiccups**. RTS games usually allow a player to fail to check in a few times before pausing to wait for them, but we*need*all three players for our computations to advance. If a player’s connection hiccups for even half a second, and the game is scheduling actions at a leisurely rate of 4Hz, the game will have to pause and wait for a moment. This basically means you’d need to be on a LAN to play the game, or else it would need to be redesigned into a turn based game.**Lots of round trips**. A sequence of multiplications requires one network round trip per multiplication. The time it takes to compute anything non-trivial is going to be measured in*seconds*.**High implementation costs**. Working with partial information makes the game simulation and resynchronization code a lot harder to write and get right.

I think those points more than justify this being an *impractical* experiment.

### Summary

Secure multi-party computation can do all the things, except be practical.

—

### Discuss on Reddit

—

### My Twitter: @CraigGidney

—

Terry A Davis

CraigGidney

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

## Archive

- strilanc
- What Quantum Computers Do Faster, with Caveats
- Naming Things: Fail-Useful
- Detecting Simple Cycles Forming, Faster
- Third Party Bit Commitment
- Angular Velocity is Simple
- Collection Equality is Hard
- Deadlocks in Practice: Don’t Hold Locks While Notifying
- Brute Force Parallelization
- A Year’s Worth of Opinions about Objective-C
- Referencing Substrings Faster, without Leaking Memory
- Not Crying Over Old Code
- Exploring Universal Ternary Gates
- Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks
- Achieving Exponential Slowdown by Enumerating Twice
- Using Immortality to Kill Accidental Callback Cycles
- Cancellation Tokens (and Collapsing Futures) for Objective-C
- Visualizing the Eigenvectors of a Rotation
- Collapsing Futures in Objective-C
- Bug Hunting #1: Garbled Audio from End to End
- Impractical Experiments #1: Representing Numbers as Polynomials
- Implementing Quantum Pseudo-Telepathy
- Turn On Your Damn Warnings
- Big-O Made Trivial
- Unfathomable Bugs #7: The Broken Oven
- Solomonoff’s Mad Scientist
- Yearly Blogging Roundup #1
- What isn’t a Monad
- Searching a Sorted Matrix Faster
- How to Read Nested Ternary Operators
- Making Sublime Text 2 Jump to the Correct Line with Unity on OS X
- My Bug, My Bad #4: Reading Concurrently
- Whole API Testing with Reflection
- Optimizing a Parser Combinator into a memcpy
- Don’t Treat Paths Like Strings
- Breaking a Toy Hash Function
- Counting Iterators Lazily
- Unfathomable Bugs #6: Pretend Precision
- My Bug, My Bad #3: Accidentally Attacking WarCraft 3
- Collapsing Types vs Monads (followup)
- Collapsing Futures: Easy to Use, Hard to Represent
- Eventual Exceptions vs Programming in a Minimal Functional Style
- The Mystery of Flunf
- Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation
- Computer Science Blows My Mind
- A visit to Execution Labs in Montréal
- Transmuting Dice, Conserving Entropy
- Rule of Thumb: Ask for the Clock
- Rule of Thumb: Use Purposefully Weakened Methods
- Rule of thumb: Preconditions Should be Checked Explicitly
- Intersecting Linked Lists Faster
- Mouse Path Smoothing for Jack Lumber
- My Bug, My Bad #2: Sunk by Float
- Repeat Yourself Differently
- Grover’s Quantum Search Algorithm
- Followup to Non-Nullable Types vs C#
- Optimizing Just in Time with Expression Trees
- When One-Way Latency Doesn’t Matter
- Determining exactly if/when/where a moving line intersected a moving point
- Emulating Actors in C# with Async/Await
- Making an immutable queue with guaranteed constant time operations
- Improving Checked Exceptions
- Perishable Collections: The Benefits of Removal-by-Lifetime
- Decoupling shared control
- Decoupling inlined UI code
- Linq to Collections: Beyond IEnumerable<T>
- Publish your .Net library as a NuGet package
- When null is not enough: an option type for C#
- Unfathomable Bugs #5: Readonly or not
- Minkowski sums: examples
- My Bug, My Bad #1: Fractal Spheres
- Working around the brittle UI Virtualization in Windows 8
- Encapsulating Angles
- Unfathomable Bugs #4: Keys that aren’t
- How would I even use a monad (in C#)?
- Useful/Interesting Methods #1: Observable.WhenEach
- Unfathomable Bugs #3: Stringing you along
- Anonymous Implementation Classes – A Design Pattern for C#
- Tasks for ActionScript 3 – Improving on Event-Driven Programming
- Minkowski sums and differences
- Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake
- Unfathomable Bugs #2: Slashing Out
- Script templates and base classes
- Unity font extraction
- Abusing “Phantom Types” to Encode List Lengths Into Their Type
- Constructive Criticism of the Reactive Extensions API
- Quaternions part 3
- Quaternions part 2
- Quaternions part 1
- Unfathomable Bugs #1: You can have things! You can have things IN things! You can have …
- Coroutines – More than you want to know
- Asset Bundle Helper
- The Visual Studio goes away
- .Net’s time traveling StopWatch
- Introducing Catalyst