MPC and Games

Posted on 25 Jan 2022

I have been thinking a lot about applications of Secure MPC in games to prevent cheating - especially in strategy games. One might argue that MPC is not developed enough for low latency applications like games yet. But the work that I am doing at MSR, I believe that we are very close - we have already achieved a runtime of 1000 times the cleartext computations. Which might sound very bad to game developers but very hopeful to MPC researchers. Every year we see a new state of the art which is atleast 2x better than previous works. As of now, we can atleast make turn based games, where latency doesn’t matter much.

I will use this blog as an idea dump for applications of MPC in games. I will keep updating as I get new ideas. Please consider giving a shoutout if you happen to work on these ideas :)

Turn based games - Pokemon #

Consider the game of Pokemon Battles. Two players each have a pokemon with stats and 4 moves. These moves can be from a finite set of all moves. Each move affects the opponent pokemon’s stats in a bad way or your own pokemon in a good way. In a single round, the trainers choose a move, and their pokemon attack the other pokemon. The move which affects the other first depends on the speed stat of the pokemon. Finally, the battle ends when the HP stat of one of the pokemon becomes 0.

Now the affects of these moves are so complex that you don’t want to tell the opponent your attack before the round ends. Hence, crypto is important here.

Consider the functionality of each round

Here, only \(\mathsf{move}^1\) and \(\mathsf{move}^2\) are secret choices of party 1 and 2 respectively. Stats are public. This function \(f\) can contain these -

1. Public Array Lookup - Selecting a move from a public list of moves depending on the secret choices.
2. Arithmetic - Once the move is selected, their effect is calculated and stats are updated using some simple addition, subtraction and multiplication.
3. Comparisons - Some moves like Quick Attack always go first.
4. Random Coin Tossing - Whether the attack succeeds or not depends on the probability determined by accuracy stat and the move.

Recent works suggest that all these operations are possible!

Update: I just realized that after the computation, moves can be revealed. So we basically need a commitment scheme and a 2PC coin tossing protocol. Sorry for overengineering, but I am not deleting that. Might be helpful for visualizing other models in such fundamental units.

Games with Maps #

I am writing this section just to demonstrate the application of one branch of MPC to games - Private Set Intersection. This is a branch of MPC where goal is to compute intersection of two sets owned by different parties. Generally in games, there is a tendency to do something when an enemy approaches your region. So knowing when the enemy’s region intersected with yours can be done using PSI. Ofcourse, if we are using eulerian maps with a round range of sight, a simple computation of \((x_1 - x_2)^2 + (y_1 - y_2)^2 < R^2\) can help us detect intersection, without doing any PSI.

3PC and Preprocessing model #

Recent works suggest that 3PC arithmetic is much much better than 2PC arithmetic, both multiplication and divison. But 3PC is an unnecesary load to a central third party.

One really great innovation recently happening is 2PC with preprocessing. In this model, there is a dealer, which generates “keys” or “preprocessing material” or “co-related randomness” for both the parties and leaves the scenario. Now with the help of these keys, the two parties carry out a protocol. Basically with the help of the key, we bring some key features of 3PC - especially faster arithmetic. Functional Secret Sharing is one of the ways to realize this - and it comes with one more great property - low round complexity, which means that the protocol will become less chatty and more homework. Which is good because we want to host our game on the internet and time taken for local computation is much less than the time taken in sending and recieving messages. Also, as the dealer has to leave, the dealer doesn’t need to stay online waiting for the parties to decide what move they want to make. Sweet!