Cryptographic Fog of War

Published on:

Mar 28, 2024

TL;DR: We describe a new game mechanic, enabled by ZK and MPC.

Introduction

Dark Forest, a space warfare game, was announced in February 2020. In the following 30 months and across several rounds, Dark Forest achieved a great amount of success within the core gaming community. In this blog we suggest that DF was the first ever instance of a new game mechanic, characterized by the following 3 requirements:

PvP: No dealer/trusted party
Hidden information (fog of war)
Deterministic state

To our knowledge, no modern game engine supports all 3 requirements at the same time. This is simply because to enable such games, we need to introduce some cool new cryptography. ZK-Hunt is a beautiful exploration into the concept of cryptographic Fog of War. In this blog post we formalize this notion and present Oblivious KZG: a new construction based on bi-directional, verifiable, committed oblivious transfer (biVOT). Together with ZK proofs, biVOT completes the required toolbox for future game engines to enable building more games like DF securely.

ZK-Hunt (Left) & DF (Right), both inactive but code is fully open source: https://github.com/FlynnSC/zk-hunt and https://github.com/darkforest-eth

Define a Game

We start by defining our game model. For the sake of this write-up, we will focus on presentation and less on precision.

A game is a protocol between two or more parties (players). A public state machine (game physics) defines a predicate. Each party keeps in memory its current state. The protocol is run in rounds (turns). In each round, a party is allowed to make one valid move and change its state once. In addition, in each turn, the party communicates a state update to all other players and checks validity against the predicate of all other parties’ state change of the previous round.

So far so good! It is easy to see how ZK Proofs fit in: every state change can be verified using ZKP. As a matter of fact, from practical reasons, in a game setting, we can just ask each party to fold a state change proof into the previous one and only at the end of the game publish the full publicly verifiable proof for everyone to verify and agree on the winner for example. We optimistically trust players to behave honestly by default but obviously proofs for state change correctness can be sent much more frequently.

Our game model is based on a simple MPC protocol between two parties

Enter Fog of War

Our model does not account for hidden information yet. First, lets explain the concept. Think of the classic game of Battleship. A malicious player might change the positions of their ships after every successful hit, and announce that they were misses instead. If we change our model such that the secret, and supposedly fixed, ship placements on the board are not sent to all other players (keeping it an hidden information), the ZKP will not catch any misbehavior — state changes will only check the basic gameplay relative to some arbitrary board positions.

The solution here is straightforward. We ask all players to commit to the board at the beginning of the game. The commitment is hiding and binding and used throughout the game. Now we can include the commitment in the player state and the ZKP will prove any state change with respect to this same commitment. In MPC lingo, we move from semi-honest to malicious adversary. We note that many online games today are semi-honest, with sensitive data shared between players.

Battleship is a good toy example, however, Fog of War can be further generalized. Think about FPS like Counter-Strike or a strategy game like League of Legends, where each player commands a unit, or several units, that can look for the other player’s units in nearby coordinates. In this seek-and-destroy gameplay, player A is exploring a map, that now, as opposed to Battleship where the hidden information is fixed at setup, the hidden information is, using our game model terminology, changing every turn, and depends on the state of the other players. Sticking to a two-player scenario; to explore the map, player A must probe player B’s committed state, every turn. A critical requirement is that the probed coordinates must remain hidden from player B, otherwise player B will learn the location of player A just by seeing the probing requests!

The solution is a known and well studied cryptographic primitive used in many MPC constructions called Oblivious Transfer (OT). In OT, a sender has n secret messages, and a receiver wants to learn k out of them (this is known as k-out-of-n OT) without learning the others, and without the sender knowing which messages were learned.

In our case the receiver is player A and the sender is player B. The secret n messages encode player B state: location of units and their status (e.g. health). A simple encoding will be a polynomial or vector with indices representing the fixed map and where values are strings encoding information like type of unit, health, items etc. Player A is using a k-out-of-n OT to probe specific indices in its proximity, and learn either 0 (no player B units in this location) or a string that tells player A everything it needs to know about the enemy unit.

The Plot Thickens

Remember that our game operates in a malicious adversary setting. Therefore, just like with Battleship, we need to add verifiability. In the case of OT, we can add verifiability directly to the sender, so now we have verifiable OT (VOT). Concretely, player B input to OT must be verifiable with respect to a commitment to its state. The way it works in our game model is that now every state change produces a new commitment and a ZK proof for state diff correctness. The same commitment is also used in the VOT so that the receiver, player A, gains knowledge only on probed coordinates and has a guarantee that what was discovered represents the valid state of player B.

In fact, we need something stronger.

We would like the receiver’s choice of messages-to-learn to be verifiable as well. In our example of seek-and-destroy gameplay, we must make sure that the probing player is probing coordinates that are in a well defined probing range according to the game rules. We add this property directly to our VOT. We call this a bidirectional-VOT (biVOT), and to our knowledge it is a novel idea.

Implementing biVOT

Our constriction is based on KZG commitments:

We describe the game map as a polynomial such that indices are coordinates. The values are strings encoding all data of the units on the map. If a unit of player B is moved from index i to index j, player B updates the polynomial such that P(j) now takes the value of P(i) and P(i) becomes zero. If a unit at location i takes a hit for example but doesn’t change location, P(i) value is updated to reflect the new health status of the unit. Player B produces a new polynomial commitment with every state change (together with a ZKP for correctness).

The choice of KZG polynomial commitment is not random of-course, as KZG commitments are used in many ZKP schemes, potentially overlapping the required cryptography and security assumptions in the MPC and ZK we need to implement the full game mechanic.

Next, we adjust KZG to add several possible OT functionalities with different trade-offs on performance, see cost analysis in the table below. Each of the oblivious KZG variants can be used either in a simplified, more efficient version, where messages can take values from a predetermined set of size m (most simple is a single bit to indicate presence of enemy unit), or expanded to a generic version, with arbitrary messages of length mu in base B. Our construction leans on the hardness of discrete log, pairings and the existence of a trusted setup

In its most general form, our Oblivious KZG interface between Bob (player B/Sender/Prover) and Alice (Player A/Receiver/Verifier) now looks like this:

Commit:

Bob commits to a polynomial
Alice commits to a polynomial

Probe: Alice sends a message to Bob containing a hidden set of indices she wishes to learn and a proof for valid probing

Prove:

Bob verifies probing
Bob uses Alice’s message to sends a message containing the hidden result of the probing

Verify-decode: Alice decodes the values to be used in the game and verifies their correctness against Bob’s commitment.

Our biVOT protocol is secure against malicious adversaries and will be shared here and in a separate paper once we complete sufficient peer-review on the security proof. Meanwhile — reach out to hi@ingonyama.com if you want to get early access to the full paper and code and start hacking on new Dark Forest experiences.

Did you know

If you reached this far, did you know that ZK can run on a gaming GPU together with graphics without significantly interfering with each other. If you are curious how we know or want to experiment with running ZK in parallel to graphics — talk to us!