CaptainZ

—— Introduction ——#

ZK Hunt is an on-chain PvP game similar to RTS, exploring different ZK game mechanics and information asymmetry. It is built using the MUD framework, which handles the overall contract architecture, network and client synchronization logic, as well as the circom used for ZK proof generation and verification.

The game was constructed during the 2022 0xPARC Autonomous Worlds residency, where many other teams were also researching their own exciting projects, and you can find a complete list of demos here. If you want a shorter summary of the ZK Hunt mechanics, you can check out my demo video here.

ZK Hunt initially started as a simple idea about implementing private movement in on-chain games, and during the residency, more mechanisms utilizing different cryptographic constructs were added, opening up new gaming experiences.

During the development process, I had ideas about how to expand it into a complete EFT (Escape from Tarkov) style game, where players enter the hunting ground with a certain amount of loot/equipment, kill other players to take their loot, and then try to "extract" their loot before being killed by others. However, over time, I realized that this project works better as a medium for exploring the possibilities of ZK game mechanics, ultimately serving as an educational resource.

So in this article, I will introduce the different mechanisms present in ZK Hunt, the specific technologies used to implement these mechanisms, some thought models I developed around private state, and how these mechanisms can be generalized more broadly.

I will try to explain the core concepts at a higher level while also delving deeper into the technical aspects, so I hope this article can be helpful to readers with varying levels of familiarity with these topics. If any part goes too deep into technical details beyond your preference, feel free to skip it, as you may find further value in later sections that do not rely on the described technical details.

It is best to have a basic understanding of smart contracts, cryptography, hash functions, and ZK proofs.

Disclaimer:

Since it is built on MUD (the two versions 1.x and 2.x are different), the contracts in ZK Hunt follow the ECS pattern. You can learn more about how MUD implements this pattern here, but at a higher level, all "entities" in the game are represented as unique numeric IDs (uint256s in EVM), and the properties of the entities are stored in different component contracts that do not contain business logic (essentially just mappings from entity IDs to values). Players interact with different system contracts that contain business logic but do not contain entity states; they read and write from different component contracts.

When I mention "contract," I am informally referring to specific contracts relevant in specific contexts, which usually differ in each case.

The exploration of ZK circuit implementations assumes some familiarity with the circom language and also uses some newer circom syntax not yet included in the standard documentation. For brevity, certain parts of the circuit code below have been omitted.

—— Jungle/Plains Movement ——#

The video below showcases the core mechanics of ZK Hunt; the dichotomy of public/private movement. In the video, you can see two players, Player A on the left and Player B on the right. Each player controls a unit they generated earlier, highlighted with a white outline, and can see the other player's unit, marked in red to indicate they are enemies.

Movement is executed by selecting a destination and confirming the path. Each movement is submitted as a separate transaction, and a new movement is submitted once the previous movement is confirmed. ZK Hunt runs on an EVM chain configured for a one-second block time, allowing units to move at a rate of one tile per second, while other unit actions can be processed with low latency.

In this world, we have two types of tiles; plains tiles displayed with grass and jungle tiles displayed with trees. Crossing the plains is public, as evidenced by Player B being able to see Player A's position updates as they move. Entering the jungle is also public, but traversing the jungle is private, to the extent that Player A loses track of Player B's position in the jungle and can only simulate a growing set of potential positions, displayed with question marks. Exiting the jungle back to the plains is public, so the potential position set collapses.

This behavior is foundational to ZK Hunt; units have a state fragment (their position) that can transition from public to private based on actions in the game and then back to public. When a unit's position becomes private, it does not transition from unambiguous to completely ambiguous, but rather gains a limited degree of ambiguity that can increase over time due to the constraints of tile-based movement. This allows other players to have a certain degree of confidence about the unit's position, and the earlier they act, the greater their confidence.

Before diving deeper into how this mechanism works, I need to establish some prerequisite understanding regarding ZK proof inputs/outputs and commitments.

Some Thoughts on ZK Circuit Inputs and Outputs#

In a ZK circuit's circom code, you can define public inputs, private inputs, and outputs, where inputs are provided by the user, and outputs are the results of certain computations performed internally by the circuit, which are returned to the user through the proof process:

template Example() {
    signal input a, b;
    signal output c;
    a + b === 7; // Checks a + b is equal to 7
    c <== a * b; // Outputs a * b
}
// a is a public input, b is a private input by omission from the list
component main {public [a]} = Example();

However, it is important to know that outputs are actually just a syntactic abstraction and are viewed as additional public inputs at a lower level. Fundamentally, a ZK circuit accepts a series of inputs and checks whether a set of mathematical constraints between these inputs is satisfied, with the only output being "true" or "false." The above circuit is functionally equivalent to this:

template Example() {
    signal input a, b, c;
    a + b === 7; // Checks a + b is equal to 7
    a * b === c; // Checks that a * b is equal to c
}
component main {public [a, c]} = Example();

The difference here is that if c is defined as an output rather than an input, the user does not have to compute the value of c, as the logic defined internally by the circuit does this for them during proof generation, which is convenient for ensuring that the values used satisfy the circuit.

The fact that outputs are actually just additional public inputs is relevant when looking at the proof verification logic in contracts. The solidity verifier accepts a series of inputs (along with the proof itself), where the outputs defined in the circuit code appear first in this list, followed by the public inputs, with the only real "output" being "success" or "failure."

Nevertheless, conceptually, it is still useful to think of a distinction between public inputs and outputs, especially when it comes to circuits that verify computational processes (like state transitions) that have natural inputs (old state) and outputs (new state).

For circuits in ZK Hunt, public inputs are typically values that have already been computed/verified and stored in the contract from previous proofs, while outputs are the results of new computations executed internally by the new proof, which are then verified by that proof and saved to the contract.

One last point to understand is that while the cost of ZK proof verification is considered constant (at least for certain proof systems like groth16, etc.), it actually increases based on the number of public inputs, which can be significant when performing on-chain verification. Before I understood the lack of functional distinction between public circuit inputs and outputs, I thought you could minimize this cost by converting all public inputs into outputs, but based on the explanation above, this is clearly not feasible.

Some Thoughts on Commitment Methods#

Commitment is a tool that can be used by a zero-knowledge proof (ZK proof) to verifiably reference some private state that the user previously "committed" to without revealing that state to the verifier (in the case of on-chain verification, to everyone observing the chain). The user provides the commitment C as a public input to the proof, the private state s as a private input, and the proof internally computes the commitment generated by s and checks if it matches C:

template Example() {
    signal input state; // Private
    signal input commitment; // Public
    // Calculates the poseidon hash commitment from 'state'
    signal result <== Poseidon(1)([state]);
    result === commitment;
    // The rest of the circuit can now trust the validity of 'state'
    ...
}
component main {public [commitment]} = Example();

When verifying the proof, the verifier will receive the values of the public signals, so when checking whether the provided commitment value is correct (i.e., matches the value previously submitted by the user), they can be confident that the correct private state value was used when generating the proof.

You can use various different commitment schemes, but perhaps the simplest is to take the hash of the state. The use of poseidon hash in ZK Hunt is because it is more efficient to compute within the circuit than other common hash functions. If the private state is a sufficiently random value chosen from a large enough range (like a private key or random seed), then simply taking the hash of that value is sufficient as a commitment.

However, if the range of possible values for the state is relatively small (for example, values between 1 and 10), then an adversary can simply compute the resulting commitments for each of those values and see which one matches the commitment submitted by the user, thereby breaking the privacy of the commitment.

To prevent such brute-force attacks, a "random number" value can be added to the commitment, making it take the form poseidon(state, random number). The random number is provided as an additional private input to the circuit and is chosen randomly from a sufficiently large range to ensure that pre-computing all possible commitments is infeasible, thus preserving the privacy of the state.

If a proof takes a commitment of some private state as input, makes some internal changes to the state according to certain rules, and then outputs a commitment to the new state, then the proof can effectively represent a verifiable private state transition. If you take the output commitment of one proof as the input to another proof, then you can create a series of private state transitions over time.

It is these commitments to private states, along with the process of updating those commitments over time, that form the core of how movement works in ZK Hunt. Now that we have established this prerequisite understanding, we can look at four different movement scenarios:

1. Plains to Plains#

The position of the unit is stored in the PositionComponent. For a unit to traverse the plains, the player submits the expected new position to the PlainsMoveSystem (which inherits from MoveSystem), which checks if the movement is valid and then updates the position value of the unit in the position component.

This verification logic checks that both the old and new positions of the unit are plains tiles, that the new position is within the map, and that the movement is a single basic step (Manhattan distance of 1). Any updates to the unit's public position will be reflected on all players' clients.

2. Plains to Jungle#

The process of entering the jungle is the same as above, except that the contract checks that the new position being moved to is a jungle tile rather than a plains tile. Additionally, the player submits a commitment to the new unit position (similarly stored in the component) along with a ZK proof indicating that the commitment was correctly computed from the new position. This commitment takes the form poseidon(x, y, nonce).

The size of the map in ZK Hunt is relatively small (31*31, but can be configured larger/smaller), meaning the total number of possible positions is limited, so a random number needs to be included to ensure the commitment cannot be brute-forced. Of course, the entry position is already public, so there is no need to brute-force the commitment, but this will not be the case for future position commitments.

This commitment does not commit to a private position but serves as a starting point for subsequent private movement in the jungle. The random number needs to remain private (which will be explained later), so a ZK proof is needed to allow the contract to check that the commitment matches the position without revealing the random number. The circuit is quite simple:

template PositionCommitment() {
    signal input x, y, nonce;
    signal output out;
    out <== Poseidon(3)([x, y, nonce]);
}
component main {public [x, y]} = PositionCommitment();

During verification, the contract provides the input values for x and y and saves the output commitment to the relevant PositionCommitmentComponent. This circuit is called PositionCommitment (rather than JungleEnter, as it is reused in other contexts) because it is reused in other cases where it needs to check whether a publicly provided position matches a commitment without revealing the random number.

3. Jungle to Jungle#

When moving in the jungle, players no longer submit the new position to the contract but only submit a commitment to the new position, along with a ZK proof that verifies the movement from the old position commitment to the new position is valid. This means all other players know that the unit has made some movement, but do not actually know the exact position the unit has moved to.

The ZK proof verifies the state transition from one private position to another, referencing an old position commitment and leading to a new position commitment, so starting from the position commitment submitted when entering the jungle, this can be used to create a chain of movements through the jungle of arbitrary length, where the output commitment of one proof becomes the input of the next.

The validity of the new position commitment depends on the validity of the old position commitment (where validity means that the commitment does not represent a position that the unit should not have reached according to the movement rules), so even though the entry position is also public, the reason for submitting the initial position commitment when entering the jungle is to start the movement chain with a commitment known to be valid by the contract.

From Player A's perspective, the ambiguity of the unit's position is visually represented by the presence of question marks, each representing a potential position the unit could be in. Just after entering the jungle, if the unit makes a new move, they could have moved to any jungle tile adjacent to the entry tile. If they move again, they could have moved to any jungle tile adjacent to their previously potential positions, and so on, which is the flood fill behavior you see.

The verification of the correctness of the movement is quite simple in the JungleMove circuit:

template JungleMove(mapSize, merkleTreeDepth) {
    signal input oldX, oldY, oldNonce, oldCommitment;
    signal input newX, newY;
    // See MerkleDataBitAccess template for signal explanations
    signal input mapDataMerkleLeaf, mapDataMerkleSiblings[merkleTreeDepth];
    signal input mapDataMerkleRoot;
    signal output newCommitment;
    // Check that the supplied oldX, oldY and oldNonce match the oldCommitment
    // stored in the contract
    signal commitment <== Poseidon(3)([oldX, oldY, oldNonce]);
    commitment === oldCommitment;
    // Check that movement is single cardinal step, and stays within the map
    signal xDiff <== CheckDiff(mapSize)(oldX, newX);
    signal yDiff <== CheckDiff(mapSize)(oldY, newY);
    xDiff + yDiff === 1;
    // Check that the new map cell is of type jungle (1)
    signal bitIndex <== newX + newY * mapSize;
    signal tileType <== MerkleDataBitAccess(merkleTreeDepth)(
        bitIndex, mapDataMerkleLeaf, mapDataMerkleSiblings, mapDataMerkleRoot
    );
    tileType === 1;
    // Calculates the new nonce and outputs the new commitment
    signal newNonce <== oldNonce + 1;
    newCommitment <== Poseidon(3)([newX, newY, newNonce]);
}
component main {public [oldCommitment, mapDataMerkleRoot]} = JungleMove(31, 2);

The first part checks that the old (x, y) values are indeed the committed values, with the oldCommitment public input provided by the contract during verification, ensuring that players cannot lie about their old position.

The second part uses CheckDiff to calculate the absolute difference between the old position and the new position for each axis, and it also checks that the difference does not exceed 1 and that the new value is still within the map:

template CheckDiff(mapSize) {
    signal input old;
    signal input new;
    signal output out;
    signal diff <== old - new;
    out <== IsEqualToAny(2)(diff, [1, -1]);
    // Ensures that the absolute diff is 1 or 0
    signal isZero <== IsZero()(diff);
    out + isZero === 1;
    // Ensures that the new value is not outside the map
    signal isOutsideMap <== IsEqualToAny(2)(new, [-1, mapSize]);
    isOutsideMap === 0;
}

While the CheckDiff for each axis limits the unit's movement to a single tile, the line at the end xDiff + yDiff === 1; ensures that the unit only moves along the x or y axis, preventing diagonal movement.

The third part checks that the new position is a jungle tile, but the logic is a bit more complex, so it will be discussed later.

The fourth part outputs the new position commitment, which the contract saves as the unit's new value if the movement is successful.

signal newNonce <== oldNonce + 1;
newCommitment <== Poseidon(3)([newX, newY, newNonce]);

Note that the new random number used for the new commitment is oldNonce + 1, rather than a new random value provided as an additional private input. This is an important choice that has implications for some mechanisms discussed later, which is why the initial random number needs to remain private when entering the jungle.

4. Jungle to Plains#

To leave the jungle, players must reveal the unit's current position in the jungle to the contract (since the contract does not know this position) so that it can check whether the movement from a jungle tile to a plains tile is valid. To prevent players from providing any jungle tile on the boundary of where they are, they must prove that the revealed jungle position matches the position commitment stored in the contract.

However, this does not require submitting a ZK proof, as players can directly reveal the (x, y) coordinates of the unit's position along with the random number used for the position commitment, and then the contract simply compares whether the poseidon hash of these values matches the stored position commitment. Exiting the jungle causes the position ambiguity to disappear, and the unit's position becomes public to all other players.

Circuit Map Data Checks - I#

Since the map tiles in ZK Hunt can only be plains or jungle, their state can be represented with a single bit (plains as 0, jungle as 1). Theoretically, this means we could pack these values into a single integer and represent the entire 16 * 16 tile map with a single uint256.

However, due to the nature of the (default) circom prime field size, circom signals can only represent values up to about 2^253.6, meaning a single signal can only carry 253 "useful" bits of information. This means you cannot represent a 16 * 16 map with a single signal, but you can represent a 15 * 15 map, which uses 225 bits, which is what the first prototype of ZK Hunt did.

If you want to check the tile value at a given (x, y) in the circuit, you calculate the tileIndex, which is x + y * mapSize (in this example, mapSize = 15), decompose the map data signal input into a series of signals representing individual bits using circomlib's Num2Bits(), and then select the tileIndex bit from that array (which is an O(n) operation in circom rather than O(1)). Here’s what it looks like (simplified):

var mapSize = 15;
var mapTileCount = mapSize * mapSize;
signal input x, y;
signal input mapData;
signal mapDataTiles[mapTileCount] <== Num2Bits(mapTileCount)(mapData);
signal tileIndex <== x + y * mapSize;
signal tileType <== SelectIndex(mapTileCount)(mapDataTiles, tileIndex);
tileType === 1;

Circuit Map Data Checks - II#

What if you want to represent a map larger than 15 * 15, like a 22 * 22 map? Well, a map of that size requires 484 bits to represent, so it would fit into two signals, with the first signal storing the first 253 bits and the second signal storing the remaining 231 bits. I call these signals "map data chunks." In the circuit, you would use Num2Bits() to decompose these two chunks into arrays of signals, concatenate the arrays, and then select the tileIndex element from the array:

var mapSize = 22;
var mapTileCount = mapSize * mapSize;
var chunk1TileCount = 253, chunk2TileCount = 231;
signal input x, y;
signal input mapDataChunks[2];
// Note, the Concat template doesn't actually exist in circomlib or ZK Hunt,
// but the implementation would be simple
signal mapDataTiles[mapTileCount] <== Concat(chunk1TileCount, chunk2TileCount)(
    Num2Bits(chunk1TileCount)(mapDataChunks[0]),
    Num2Bits(chunk2TileCount)(mapDataChunks[1])
);
signal tileType <== SelectIndex(mapTileCount)(mapDataTiles, x + y * mapSize);
tileType === 1;

You can expand this method by increasing the number of map data chunks to represent larger maps. However, since the map data chunks need to be provided by the contract as public inputs, the larger the map, the higher the verification cost, as the number of public inputs increases. To address this, the map data chunks can be passed in as private inputs, and then checked against a public commitment to the chunks, meaning that regardless of the size of the map, only a single public input is needed:

signal input mapDataChunks[4]; // Private
signal input mapDataCommitment; // Public
signal commitment <== Poseidon(4)(mapDataChunks);
commitment === mapDataCommitment;
// The map data chunks can now be trusted by the rest of the circuit
...

In the previous scenarios, the commitment was used to allow players to verifiably reference some private state in the circuit, while here it is used to allow the circuit to reference any size of public state provided by the contract while only needing to pass a single public signal rather than a sufficient number of signals containing all the public data. An important point to note is that the poseidon hash implemented in circomlib only supports up to 16 inputs, but you can solve this by chaining hashes like this: poseidon(x1, x2, ..., x15, poseidon(x16, x17, ...)).

Circuit Map Data Checks - III#

While this method solves the linear growth problem of the number of public inputs with the size of the map (in terms of total tiles), the computation required within the circuit to verify the map data commitment still grows linearly with the size of the map, which can lead to very large circuits (many constraints) for very large maps, resulting in longer proof generation times.

To improve this, you could replace the linear/chained commitments to map data chunks with Merkle tree commitments, so that if a single tile needs to be checked in the circuit, you only need to compute the hashes related to the branches of the Merkle tree, making the cost logarithmic in relation to the size of the map rather than linear.

The relevant map data chunks (containing the chunk of the tile being moved to) and the Merkle sibling nodes needed to reconstruct the path from the chunk to the root are passed in as private inputs, while the root of the generated Merkle path is checked against the root of the tree provided as a public input to the contract.

This is the method that ZK Hunt ultimately adopted, and it is what the third part of the JungleMove circuit does, utilizing the MerkleDataBitAccess circuit, which, in addition to performing the described Merkle checks, also decomposes the bits of the map data Merkle leaves and returns the relevant tile value at the provided bitIndex:

This implementation also has the benefit of only performing Num2Bits() on the map data chunks containing the tiles, rather than all of them, and then only needing to select from the number of tiles in one chunk rather than the total number of tiles across all chunks (O(n) operation), but this optimization can also be applied to the linear commitment method, so the main difference between the two is the efficiency of commitment verification.

Circuit Map Data Checks - IV#

The example above shows a binary tree, which matches the implementation in ZK Hunt, but this is actually not the most efficient way to prove tree structures. In the circuit, computing a Poseidon hash with 2 inputs (Poseidon(2)(...)) requires 240 constraints, but interestingly, computing a Poseidon hash with 16 inputs (Poseidon(16)(...)) only requires 609 constraints, so using a six-ary tree instead of a binary tree can yield the greatest returns, although this comes with some additional implementation complexity.

At the time, I was unaware of this fact about Poseidon circuit implementations, which is why I chose a binary tree. However, even considering this, for the number of chunks used to represent the map in ZK Hunt (4 chunks for 31 * 31), there is no difference between linear commitments and tree commitments; in both cases, it is just Poseidon(4)(...), which would be correct for maps requiring up to 16 chunks.

Even when you exceed 16 chunks to the point where there is a difference (linear commitments require chaining multiple hashes, tree commitments require multiple levels), I have a hunch that due to the additional Merkle logic overhead, tree commitments may actually be less efficient than linear ones, only becoming more efficient when the map is sufficiently large. Tree commitments are definitely overkill for ZK Hunt, and linear commitments are likely sufficient for most use cases, but having a proof of concept is good nonetheless.

Since the map data in ZK Hunt is passed into the circuit as inputs rather than hardcoded into the circuit or generated based on a procedurally generated algorithm computed in the circuit, the map can be designed to have arbitrary content (for each game) and can actually change over time. I had an idea during development that players could burn jungle tiles, and new jungle tiles would naturally grow over time, but doing so would break the logic used to compute potential position displays.

The methods described here can be used to pass any type of public dataset into the circuit from which you want to select, just like a lookup table. This could be weapon damage values, item prices, NPC locations, etc. ZK Hunt uses a single bit to represent each element of the dataset since they can only be one of two options, but the implementation could be changed to allow each element to be represented with an arbitrary number of bits, allowing each element to take on an arbitrary number of values.

One last useful thing to know is that the Poseidon implementation generated by circomlibjs can only accommodate a maximum of six inputs (I think due to the limited stack depth of the EVM), so using Poseidon hashes with more than six inputs cannot be created or verified through direct computation in the contract, but you can certainly solve this by using ZK proofs, allowing each hash to have up to 16 inputs.

Jungle/Plains Movement Summary#

At a certain level of abstraction, the movement system described above allows the game to have stealth zones, non-stealth zones, and the ability for entities to move between the two. Specific plains/jungle scenarios could be redesigned for different types of games:

• You could replace it with light and shadow areas, where specific light sources are placed in the world that emit light radially, while solid obstacles create shadow areas by blocking that light (this idea is credited to lermchair). If the light source can move (like a handheld lantern), then the light areas can update over time, although this requires additional logic to handle players transitioning from light to shadow without moving (not to mention on-chain dynamic shadow casting calculations).
• Based on the above idea, you could create an asymmetric multiplayer game, like hide and seek or even Dead by Daylight, where there is a seeker who is always in a public position and emits a vision area that can be blocked by obstacles. There would be some hiders whose positions remain private from the seeker until they enter their line of sight, at which point their positions become public and easier to chase.
• You could create a system where stealth is not bound to specific areas of the map, but rather players can enter stealth at any time, regardless of their location, but only for a limited time/movement count. With this, you could build a game where players can burrow underground and tunnel privately to other places, but they are forced to resurface to avoid running out of energy (or some other reason), limiting the maximum position ambiguity that can be achieved without locking stealth to specific areas.
• You could replace grid-based positioning/movement with graph-based positioning/movement (for example, moving between discrete rooms connected by corridors), which would affect how position ambiguity grows during private movement.

At a higher level of abstraction, the plains/jungle movement system represents a way to give players a certain state that can be public, transition to private (or even be private from the start in some cases), can be effectively updated while remaining private, and can be publicly revealed. In ZK Hunt, this state is used to represent the position of units, but it could easily represent any other type of state with arbitrary update logic:

• Players could have private health states that update privately when damaged by another player and are only revealed when sufficiently damaged and killed.
• Players could have a private stamina meter and a private position, where the stamina they expend while moving determines how far they can move. This means that when players move privately, other players will not be able to tell whether they chose to move a long distance or moved a short distance to conserve stamina, or something in between. This would make position ambiguity (and any visual attempts to represent that ambiguity) much more complex.
• Players could have a private inventory from which they can use items that produce public or private effects (for example, publicly damaging other players or privately healing themselves). To fill such a private inventory, players could open chests that contain one item from a range of possibilities, each with a different probability of occurrence. The items contained in the chests are privately determined, so other players do not know which item the player received, and the contents of their inventory can remain private.
• Alternatively, perhaps players could discover the contents of another player's inventory and then privately steal an item from them. How to implement such a thing will become clearer in later sections.

Clearly, there is a lot that can be done here. However, it must be noted that the core ideas involved here are by no means new...

On the Shoulders of Dark Forest#

The obvious inspiration for this private state/commitment/transitions scheme, and even the general use of ZK to build on-chain games, clearly comes from Dark Forest. However, the approach taken by DF is slightly different from the one used in ZK Hunt. Let’s quickly recap how DF works:

In DF, whether a specific location contains a planet depends on whether the MiMC hash of the integer coordinates of that location is greater than a certain threshold (mimc(x, y) > threshold). This means that to find out which planets are contained in a specific area of space, players simply hash all unique positions in that area and check whether each result is greater than the threshold. This is why you can "mine" the fog of war in DF step by step (the way of generating and checking a bunch of hashes is very similar to how Bitcoin mining works).

Due to the vast size of the DF map and the natural sparsity of planets, mining every position in the map takes quite a bit of time (unless you have sufficiently powerful hardware), so you are forced to strategically choose specific areas of the map to leverage your hashing power.

In DF, players can send resources to multiple planets simultaneously and occupy them, so a "player" can actually be in multiple positions at once, but for simplicity in comparing with ZK Hunt, let’s assume players can only be on one planet at a time. The following explanation should still hold.

When a player appears on their initial planet or moves to another planet, the hash of the planet's position is submitted as a position commitment to the contract, rather than submitting the position directly, along with a ZK proof showing the validity of the commitment (that the hash corresponds to a position that actually contains a planet, and if it is a move, that the new planet is not more than a threshold distance from the old planet), which is how players can keep their position private, similar to the method in ZK Hunt.

Once you discover a position exists with a planet based on its position hash, you can see which players (if any) are on that planet by comparing their most recently submitted position commitments with that position hash. Now, let’s take a moment to establish how these processes of finding planets and finding players fit into a broader conceptual framework.

On-Chain World Discovery/Player Discovery#

Discovering planets in DF by mining the fog of war is a specific method within what I call the larger category of "on-chain world discovery." A simple definition is: the content/state of the game world (non-player) is initially hidden from players, and players must perform certain actions to gradually discover it over time.

The most obvious example might be the fog of war system you see in DF or traditional strategy games, where you reveal the terrain/layout of the world, items, NPCs, etc., but the broadest definition of world discovery could also include things like learning about the backstory of NPCs or even creating novel items through resource combinations.

Since the map in ZK Hunt is fully public from the start, the theme of world discovery is not particularly relevant to ZK Hunt, so I won’t delve deeper into it in this article, but you can find my discussion on different methods of world discovery here, and I will explore some new methods in future projects.

On the other hand, discovering players through mining the fog of war in DF, I believe, is a specific method of "on-chain player discovery," which has a more direct relationship with ZK Hunt, as the name suggests. Again, a simple definition: players (and/or player-controlled entities) have private positions that other players can discover by performing specific actions. A more complete definition might extend to discovering all private attributes of players (like their health status, items they possess, etc.), but for now, we will focus only on position.

It may even make sense to establish world/player discovery as a strict dichotomy; discovering things that belong to "players" and discovering things that belong to "non-players," but if establishing a complex third category of non-player agents makes more sense, then this might break down, as their discovery processes are sufficiently different from world discovery.

As I explore various methods of player discovery, I have encountered several different subcategories. My current model is as follows:

• Public Player Discovery - The discovering player reveals their position to everyone.
• Private Player Discovery - The discovering player only reveals their position to the discoverer.
  Private discovery subcategories:

Symmetric Player Discovery - The discovering player also leads to their discovery.

Asymmetric Player Discovery - Divided into three tiers, each inheriting the permissions of the previous tier:

• Discovering a player without letting them discover you (but they do know whether the search was successful).
• Discovering a player without letting them know whether you successfully searched them (but they do know you searched them).
• Discovering a player without letting them know you searched them at all.

As you can see, the deeper the model goes, the less information is leaked. Given the inherently public nature of blockchains, I find that generally, the stronger the privacy of a category, the more difficult/complex it is to implement. Looking ahead, we can use this framework to evaluate the methods used by DF and ZK Hunt for player discovery.

Dark Forest Analysis#

Since the mining of fog of war in DF and the comparison of planet/player position hashes are entirely external processes that do not require direct interaction with the game world/contract logic/other players, DF's method achieves the highest level of asymmetric player discovery. However, it is not perfect and has several drawbacks:

Spatially Unrestricted: Players can choose to mine any part of the map, regardless of their position. One could argue that given the world narrative (pointing your telescope at distant space), this makes sense for DF to some extent, but for other types of games, the inability to restrict discovery based on player position is a significant drawback. If you are playing a PvP dungeon game, you should not be able to discover players far away from you. Player discovery should have the ability to be localized.

Temporally Unrestricted: The speed at which players discover new planets, and thus any players that may be discovered on those planets, essentially depends on how fast they can compute hashes, which in turn depends on how powerful their hardware is. This creates an inherently unequal playing field, where investing additional capital can make it even more unequal. Your ability to discover players should be entirely determined by the rules/state of the world (e.g., the speed of your character, the strength of your telescope, obstacles between players, etc.).

Permanence: Once you find a planet and determine its position hash, you will be able to see any players moving to/from it for the remainder of the game. While permanence of discovery may be good when it comes to discovering the world (at least for static attributes), it is less so when it comes to discovering players. Just because you accessed a specific area does not mean you should be able to see players accessing that same area after you leave. Player discovery should have dynamics and non-permanence.

In DF, player discovery can be seen as a byproduct of world discovery to some extent, so the drawbacks listed above actually extend the same drawbacks that apply to world discovery. Do not get me wrong; the system design used by DF to allow for private world and player discovery is quite incredible and works well in its use case, but it would be better if there were a method that is not affected by these drawbacks.

The fundamental mechanism supporting player discovery in DF is the ability to "guess and check" (compute and compare) position hashes, and the existence of planets merely narrows down the actual position hashes you check. This is possible because the position commitment submitted by players is simply the hash of the position; mimc(x, y). The DF map is large enough that searching the entire map is no easy task, but not so large that players randomly placed on the map never have a chance to find each other.

The difference with position commitments in ZK Hunt is that it includes a private random number; poseidon(x, y, nonce), and choosing poseidon over mimc has no functional difference (it is just more efficient for the circuit). This addition particularly prevents the ability to "guess and check" position hashes, although the map in ZK Hunt is clearly smaller than DF's, so you cannot find players in this way. If that were the case, how does player discovery work in ZK Hunt? How do you interact with players whose positions are ambiguous in the jungle?

— Spear —#

The spear is a set of four "hit tiles" (or more generally, "challenge tiles") arranged linearly extending from the player, allowing you to aim in one of 32 different directions. To showcase some aspects of the spear, we will also introduce a third player, Player C, located in the lower right corner. Player C does not control any units; they are just a third-party observer representing the perspective of all other players in the game.

In the video above, you see Player A throwing a spear at a unit of Player B on the plains, resulting in their death and dropping their loot, which Player A's unit then picks up. Player B then sends another unit into the jungle for some position ambiguity, and Player A attempts to throw a spear at them. The first attempt misses, maintaining that ambiguity, but the second attempt succeeds, revealing that unit's position, leading to its death and dropping its loot.

This is the first tool included in ZK Hunt that allows you to interact with units whose positions are ambiguous in the jungle. The spear serves both as a combat ability and a method of player discovery, but these aspects can exist independently. You could swap it out for a simple stone thrown in the same way, which, if it hits, would make a unit "shout," revealing their position in the jungle without killing them.

Being hit by a spear reveals the unit's position to all players, as evidenced by Player C also learning the fact of the unit's position, so the spear would be classified as a method of public player discovery. Let’s understand how it works…

Hit Tiles#

This linear arrangement of four hit tiles is actually arbitrary; we could have any number of hit tiles arranged in any kind of configuration. You could create a club with smaller, arc-shaped hit tiles, or perhaps a bomb that generates a larger circular area of hit tiles away from the unit throwing it.

The number of directions the spear can be thrown and the arrangement of tiles in each direction is also completely arbitrary. The complete set of arrangements is hardcoded in the contract as a list of offsets for each direction. When executing a spear throw, the selected directionIndex is sent to the contract, which then determines the resulting position of the hit tiles by adding a set of offsets (corresponding to that direction) to the unit's position.

The hit tiles go through three stages:

1. Potential (shown in translucent white): When the player is still aiming the spear.
2. Pending (shown in solid white): The player has confirmed the throw and submitted the direction to the contract.
3. Resolved (shown in red): The contract has determined whether the hit tiles hit anything. The hit tiles are resolved one by one, as some tiles may resolve before others.

Spear Thrown into the Jungle#

In the video, Player A throws their spear at Player B's unit in the jungle; the first attempt misses, and the second attempt succeeds. But wait, if Player A and the contract do not know the exact position of the unit, how do they know whether the spear throw attempt was successful? The answer is that we force Player B to reveal whether they were hit, using a challenge/response process.

When submitting the spear throw, the contract can immediately determine which (if any) units were hit by the tiles on the plains and kill them in the same transaction. However, if any hit tiles fall in the jungle, then each unit in the jungle will be placed under a "pending challenge," meaning that unit cannot perform any actions until the challenge is resolved (enforced by ActionLib).

To clear a unit's pending challenge, the owning player has two valid options:

1. They were not hit, in which case they generate a zero-knowledge proof (ZK proof) demonstrating this fact, submit it to the contract, and maintain their position's ambiguity. This is what you see in the first attempt.

2. They were hit, in which case they cannot generate such a proof, so they publicly submit their position to the contract, accept the hit, and drop their loot. This is what you see in the second attempt.

This is why you see the hit tiles in the jungle resolving more slowly than those in the plains; because they must wait for the challenged player to respond.

The circuit used for option 1, JungleHitAvoid, is quite straightforward, with the first part matching the JungleMove circuit:

template JungleHitAvoid(hitTileCount) {
    signal input x, y, nonce, positionCommitment;
    signal input hitTilesXValues[hitTileCount], hitTilesYValues[hitTileCount];
    signal input hitTilesCommitment;
    // Checks that the supplied x and y match the commitment
    signal commitment <== Poseidon(3)([x, y, nonce]);
    commitment === positionCommitment;
    // Checks that the passed (x, y) aren't part of the hit tiles, and that
    // the hit tiles match the supplied hit tiles commitment
    signal wasHit <== CoordSetInclusion(hitTileCount)(
        x, y, hitTilesXValues, hitTilesYValues, hitTilesCommitment
    );
    wasHit === 0;
}
component main {public [positionCommitment, hitTilesCommitment]} = JungleHitAvoid(4);

Similar to how the map data is handled in JungleMove, the x and y values of the hit tiles are not passed in as public signals but as private signals, with only a single commitment value passed in as a public signal. For JungleMove, only specific map data chunks from the total set are relevant to the circuit, so when the number of chunks increases, a tree commitment makes sense, but for challenge tiles, each tile in the set needs to be checked, so linear commitments are sufficient regardless of the total number of tiles.

This relates to the second part of JungleHitAvoid, where the CoordSetInclusion circuit determines whether the position provided by the unit matches any of the hit tiles and checks that the hit tiles match the commitment calculated when submitting the spear throw (poseidon(x1, poseidon(x2, poseidon(x3, ...)))).

In the current implementation, if any hit tile is in the jungle, then every unit currently in any jungle tile will be placed under a pending challenge, regardless of how close they are to the hit tile. This is clearly very inefficient, as many players with no chance of being hit still have to respond. Some optimizations could be made, such as only placing pending challenges on units in specific jungle areas touched by the hit tiles, or only on units touching their potential positions, but I chose the simplest approach.

Punishing Non-Response#

When a pending challenge is placed on a unit, aside from the two options above, the player actually has a third option that is not directly prevented by contract logic but violates the "rules of the game"; they can choose not to submit any response at all.

This means that the unit is effectively frozen, which does not directly provide any benefit, but if a player controls multiple units or collaborates with other players, then delaying their opponent by making them wait for a response that will never come could be advantageous. Even if doing so provides no benefit, it is still a simple way to annoy other players, so how do we prevent this behavior?

Let’s return to the beginning. When entering the game, each player must put down a deposit to play. If they leave the game after playing by the rules, they can reclaim this deposit. Each pending challenge has a limited response period. If a unit receives a pending challenge and the owning player does not respond within that period, they can be punished (slashed) by anyone, resulting in their deposit being forfeited and all their units being eliminated.

In this video, I prevented Player B's client from responding to the challenge, so after throwing a spear at the unit in the jungle and waiting about 5 seconds for the response time to expire, Player A punished Player B, resulting in both of their units dying and dropping their loot. Once a player's client detects that the response period has ended without submitting a response, the punishment is automatically executed through the liquidation contract.

Note that throughout the codebase, I have referred to this process as "liquidation," but later decided that "punishment" is a more appropriate term. Also, note that I have not actually implemented the ability for players to put down a deposit when entering the game, so the punishment will only kill the player's units without taking the said deposit, but adding this functionality is quite simple.

Generalizing Punishment#

While the spear serves to reveal the private position of a unit, the underlying challenge/response/punishment system can be used to force players to reveal any type of private state.

More generally, the existence of punishable deposits can be used to ensure players perform any type of interaction required by the world. The contract and circuit logic can be used to determine the exact nature of this interaction, while the use of zero-knowledge proofs can allow for private states to be included in the process. Subsequent mechanisms in ZK Hunt further explore this idea.

The response period should be adjusted to match the expected upper limit of time required to generate a response, submit it, and have it accepted by the contract, while allowing for enough margin of error to account for differences in players' hardware performance and network latency.

To make the threat of punishment effective, the deposit should be significant enough that its loss is more important to the player than any value gained from not acting. This deposit could take various forms; tokens, in-game items, reputation, experience/level of characters that have lived for a while, etc.

Limiting parts of the game to players with only a certain amount of deposit (e.g., different matchmaking tiers, difficulty levels of dungeons, etc.), while allowing players to increase their deposit over time through in-game actions, is a good way to prevent participation in any part of the game from being limited due to the upfront cost of the deposit.

The threat of punishment should provide enough incentive not to break the rules, but if the rules are broken regardless, it is important to have fallback logic. If the game uses a system based on 1v1 matches, then the fallback logic is simple; the match can end immediately, and "victory" (and any other related consequences) can be awarded to the player who was not punished.

World Integrity#

However, if there are two or more players and the game is designed to have a more persistent world (as is the case in ZK Hunt), then this fallback logic may become more complex depending on the nature of the world/punishment context and should be designed to maximize "world integrity." I consider world integrity to be a measure of "how closely the behavior of the world aligns with player expectations, while considering the entire set of consequences arising from its design."

For example, in ZK Hunt, the expectation that "if a unit in the jungle is hit by a spear, it should die and drop loot" would be strongly maintained even if punishment occurs. In contrast, the expectation that "if a unit in the jungle is hit by a spear, it should die within about x seconds" (where x is a reasonable upper limit of time required for the player to respond to being hit and for the consequences to propagate to all other players) is not strongly maintained, as non-responses can occur, leading to a waiting period that exceeds x before punishment occurs.

Similarly, the expectation that "if a unit is killed in the jungle, its loot should drop in the same tile as the unit" is also not strongly maintained. If a player is punished for not responding to a challenge, then the contract does not know the exact position of their unit in the jungle; the best it can do is place the loot at the last known position of the unit (the jungle entry tile). From the perspective of another player who does know the unit's position (obtained through the methods discussed later), this may look like the loot teleported.

You could try to improve this situation by changing it so that the loot drops in one of the hit tiles that intersect with the unit's potential positions, based on the concept that if a player did not respond, they were most likely hit by the spear. While this still allows for teleportation, the potential range of that teleportation is minimized. However, this approach leads to a more complex implementation and does not address the case where no hit tile matches any of the unit's potential positions, which is why I chose the simpler method.

To gain the convenience of punishment, you may have to sacrifice some degree of world integrity. The two ZK Hunt examples above highlight two important considerations of punishment: temporal sensitivity and private state fallback.

Punishment Curve#

In the challenge/response system described above, if players fail to respond in a timely manner, their deposit will be forfeited. A strategically malicious actor would wait until the response period is nearly over to respond, thus avoiding having their deposit forfeited while also delaying the other players waiting for a response.

Plotting the amount lost by players against the time they wait before responding, the graph looks like this:

Clearly, we want to prevent this delaying behavior through punishment, so we can forfeit a portion of the player's deposit when they respond, rather than only forfeit the entire deposit after a strict deadline, with the forfeited proportion determined by how long they waited:

There is still a strict deadline at the end; if they respond before this point, a portion of their deposit will be forfeited, but they can continue to participate in the game, whereas if they respond after the deadline or do not respond at all, their entire deposit will be forfeited, and they will be removed from the game.

Doing this minimally punishes players who respond in a timely manner while heavily punishing players attempting to delay their response. A malicious actor might quantify the value they gain by delaying their response time t and then find a point on the curve where that value minus the forfeited amount is maximized.

The curve can be adjusted to influence the reactions of such actors, and there could even be a self-regulating curve that continuously adjusts based on the average response time of players.

Degree of Information Disclosure#

Throwing a spear is a way to interact with units whose positions are ambiguous, as well as a way to force them to reveal their position, but it can be modified to limit the actual amount of information disclosed. When a unit in the jungle is hit by a spear and dies, revealing its position makes sense because the contract needs to know where to drop the loot. However, if each unit has a certain amount of HP and requires more than one spear hit to kill, then the situation is no longer necessarily the same.

If a unit is hit but not killed, you can only force the owning player to reveal the fact that they were hit so that the contract can reduce their health without revealing their exact position (using a zero-knowledge proof). This effectively reduces the potential positions of the unit to the set of tiles it could have been hit in.

If the unit has a private health status, you can go even further; the challenged player responds by submitting a new health commitment that decreases the health value if they were hit, or keeps it the same if they were not hit (enforced by a zero-knowledge proof). This means other players only see the update of the unit's health commitment, thus not knowing whether the unit was hit, thereby maintaining the complete ambiguity of the unit's position.

You could even have all three degrees of information disclosure exist simultaneously and determine which one to use based on certain attributes or items the unit possesses.

Actions in the Jungle#

Continuing from the first spear-throwing video, we will see that you can also perform actions in the jungle.

After killing Player B's unit in the jungle, Player A picks up the dropped loot. Note that doing so forces Player A to reveal their unit's position so that the contract can ensure they are indeed in the correct position to pick up the loot, but afterward, they can immediately re-enter stealth in the jungle and regain ambiguity of position. The act of throwing a spear from the jungle is the same; the unit's position must be revealed to the contract so it can determine which set of hit tiles should apply.

As you saw earlier, when exiting the jungle, players reveal the unit's position and random number, and the contract checks whether the poseidon hash of these values matches the stored position commitment. Performing actions in the jungle is different from this process; it only reveals the position and uses a zero-knowledge proof to indicate it matches the commitment. This means the random number can remain private, allowing movement in the jungle to continue from the same commitment rather than having to establish a new commitment with a new random number.

This proof reuses the PositionCommitment circuit (the same circuit used when entering the jungle), and both the contracts for picking up loot and throwing spears in the jungle delegate to a single contract that handles revealing the unit's position in this way.

As mentioned earlier, throwing a spear falls under the category of public player discovery, but can we do better? Can we achieve private player discovery?

— Search —#

For this, we have the search ability. While it uses the same linear challenge tile construction as the spear, searching is not a combat ability but an information-gathering ability.

Here we see Player A searching for Player B, but failing to learn anything. They try again, and the search locates Player B, revealing their position. This is the same situation you just saw with the spear (excluding death), but in this case, only Player A learns Player B's position, while Player C does not, as evidenced by the ongoing ambiguity indicator present from Player C's perspective. In fact, Player C not only does not learn the position of that unit, they do not even know whether Player A's search was successful. This achieves private player discovery.

When Player B's unit (after being found by Player A) makes additional movements in the jungle, the ambiguity of position continues to grow as expected from Player C's perspective, but Player A retains precise knowledge of their position. This allows Player A to effectively track Player B's unit over time, a tracking behavior that will continue until the unit exits and re-enters the jungle, at which point the unit can regain ambiguity of position relative to Player A.

How Does Search Work?#

Similar to throwing a spear, Player A submits the search direction to the contract, which determines the resulting challenge tiles and places a pending challenge on Player B's unit in the jungle. When Player B sees this pending challenge, they do not directly submit their position to the contract (if successful), but instead encrypt their position commitment random number (effectively revealing their position, which will be explained in detail later) so that only Player A can decrypt it, then submit the ciphertext along with a proof that the encryption was done correctly.

This explains how Player A can privately learn Player B's position, but how is Player C prevented from at least knowing whether Player A's search was successful? They can certainly observe Player B's response; if they submit ciphertext, it means they are sending their encrypted random number, which means Player A's search was successful, right?

Not, because whether Player B was caught in the search or not, they will submit a ciphertext and the associated proof, but this ciphertext will only contain their random number if they were caught in the search; otherwise, it will contain a meaningless value. This means that, regardless of whether Player A's search was successful or not, Player C, as an external observer, cannot discern the difference.

Night Market#

My thoughts on punishment transitioned from resolving non-response issues with the spear to allowing more general "forced interactions," and the emergence of this mechanism is a result of that thinking. If, with punishable deposits and contract/circuit logic, you can force players to respond to challenges in a specific way, then why not just force them to respond with their position (or position commitment random number) in an encrypted way so that only the challenger can decrypt it?

You have to verify that the encryption is done correctly within the circuit, so the next question becomes which encryption methods are friendly to SNARKs (zero-knowledge proofs)? I did a quick check and realized that this question has already been addressed by the Dark Forest Nightmarket plugin.

The Nightmarket plugin is a way to privately and verifiably sell planet coordinates in Dark Forest. Players can post listings to sell the coordinates of planets they have discovered, and buyers can make offers by depositing some Ethereum into a hosted contract, which sellers can accept by privately revealing the coordinates to buyers using symmetric encryption and withdrawing the deposit.

Using zero-knowledge proofs to ensure that the coordinates actually contain a planet and that the encryption was done correctly, although the full process is a bit more complex than described here, so you can learn more in the blog post linked above. I ultimately reused some shared key derivation and Poseidon encryption circuits from Nightmarket, which itself has made some changes to some circuits in this circomlib pr by maci and Koh Wei Jei.

While both Nightmarket and the search in ZK Hunt involve privately distributing information, there is an interesting distinction between the two in that sales in Nightmarket are voluntary interactions; once a listing is made, buyers choose to make offers, and sellers choose whether to accept, whereas searches are involuntary interactions; once a challenge is posed to a player, if they do not respond correctly, they will be punished.

Search Implementation#

For search (and Nightmarket), Poseidon encryption is used as a symmetric encryption scheme because it is more suitable for SNARKs than traditional asymmetric encryption schemes, possibly for similar reasons that Poseidon hashes are more suitable for SNARKs than traditional hash functions (they share some parts of the circuit implementation).

The shared key between two players is established through an "offline" ECDH key exchange. In practice, this means that when all players enter the game, they each establish a private/public key pair and submit their public keys to the contract. With your private key and another player's public key, you can derive a shared key for encryption without directly interacting with them (hence "offline"), and they can do the same with their private key and your public key, resulting in the same shared key.

Each player does this for every other player, ultimately obtaining unique (and private) shared keys that they can use to communicate with any other player. During the search response, the proof enforces the use of the correct shared key to verify that the encryption was done correctly.

The SearchResponse circuit is a bit dense, so I won’t paste the code directly here, but essentially it:

• Checks whether the response unit's (x, y) and the position commitment nonce provided privately to the circuit match the public position commitment.
• Derives the shared key from the responding player's private key and the searching player's public key while checking that the responding player's private key matches their public key.
• Determines whether the unit was found by checking whether its position matches any of the privately provided challenge tiles. This result is stored in a signal called wasFound.
• Checks whether the publicly provided ciphertext is the correct encryption of the secretNonce and that it was encrypted with the previously derived shared key.
• Finally, checks whether wasFound is false or whether the secretNonce matches the position commitment nonce.

In summary, if the unit was found, the circuit ensures they have encrypted their position commitment nonce, but if they were not found, the circuit allows them to encrypt anything, effectively revealing no information.

The Power of Nonce#

So, if the search response encrypts the unit's position commitment nonce rather than the position itself, how does this still lead to the position being known to the challenger?

Well, the challenger can look at the set of potential positions, compute what the position commitment would be for each position corresponding to the nonce they now know, and see which of those commitments matches the one stored on-chain for that unit.

Revealing the nonce effectively turns the commitment back into a DF type, with the difference being that in this case, because the number of potential positions is small, brute-forcing the commitment is quite easy.

Initially, I chose to encrypt the nonce rather than the position because it meant encrypting a single value rather than two (x, y), and it still led to the position being known to the challenger. Since then, I have realized that encrypting the nonce produces a more significant benefit, or more precisely, a convenience.

When throwing a spear from the jungle, picking up loot in the jungle (and being hit by a spear in the jungle if it does not kill you), the unit reveals its position but can then immediately disappear back into the jungle through subsequent movement, regaining ambiguity of position. However, being discovered through a search would allow the challenger to determine the exact position of the unit for all subsequent movements in the jungle, producing the tracking behavior you see in the latter half of the video.

This is due to the implementation details of JungleMove, which enforces that the nonce used in the new position commitment is the nonce used in the old position commitment + 1 (an arbitrary decision made early on), so knowing the current position commitment nonce allows you to determine all future nonces (and all previous nonces), thus knowing the corresponding positions.

Once the unit leaves and re-enters the jungle, this effect resets, as you can choose a new random nonce for the initial entry position commitment. Of course, if you do not want this tracking behavior, you could allow the nonce for each new position commitment to be completely random, unrelated to previous nonces.

Alternatively, you could allow tracking to persist for a certain number of movements/time rather than until re-entering the jungle. This would require establishing a timer/movement counter referenced in the circuit that only allows the selection of a new random nonce after the duration condition is met, and would also need to enforce reusing the nonce from the previous position if the condition has not been met upon re-entering the jungle.

Of course, this tracking behavior can extend to any type of private state using this commitment scheme; you could track how a player's private health status changes over time, how many resources they have, etc.

Another Option for Encryption#

I recently realized that there is a simpler and more efficient way to implement SNARK-friendly encryption for values from a sufficiently small range.

Commitment nonces do not belong to this category, as they should be chosen from a large range to prevent the commitment from being brute-forced, but unit positions do belong to this category, as both x and y are within the range [0, mapSize - 1], and mapSize is small enough. This means that if you forgo the additional convenience of the tracking functionality provided by encrypting the commitment nonce, you can directly encrypt the unit's position.

The overall approach is as follows: establish a shared key k (you can use ECDH again), and then for a given message value m from a sufficiently small range r, the ciphertext C is simply poseidon(m, k). Player A submits C along with a proof that C was generated from the correct r and m. Player B retrieves C and knows to compute C' = poseidon(m', k) for every possible m' from the range r until they find a C' value that matches C, indicating that the encrypted value m equals the corresponding m'.

You will notice that this decryption process is almost identical to the one described above for determining the unit's position from the revealed nonce and their commitment.

Here, the definition of "sufficiently small range" actually depends on how many hashes you are willing to compute locally to find a match, which can actually be quite large, as many hashes can be computed relatively cheaply. As long as the product of the ranges (r_1 * r_2 * ... * r_n) is small enough, this method can be extended to encrypt any arbitrarily large set of values m_1, m_2, ..., m_n from ranges r_1, r_2, ..., r_n.

As mentioned earlier, increasing the number of inputs to the poseidon hash in the circuit increases the number of constraints, and a single poseidon hash can accept a maximum of 16 inputs, but you can force the set of values to be represented as a single value by performing m = m_1 + m_2 * r_1 + m_3 * r_1 * r_2 + ... and summing to obtain a single value that uniquely represents that set.

Compared to needing about 800 circuit constraints and 4 uint256s to represent the ciphertext of the poseidon encryption (the ciphertext size is rounded to the nearest multiple of 3 of the message size, + 1), using poseidon hashes only requires about 240 constraints and one uint256 to represent the ciphertext.

To replace the encryption used in the search response, the ciphertext would simply be poseidon(x, y, k), or poseidon(x + y * mapSize, k). Of course, the permanent tracking functionality provided by encrypting the nonce is very cool, so you might choose to stick with poseidon encryption here to retain that functionality, but this hash encryption method may find more uses in other scenarios.

Searching in the Jungle#

Searching can also be done in the jungle (i.e., "covert search"), which brings new functionality and adds more encryption complexity.

Here, Player A and Player B have both entered the jungle, meaning Player C does not know where either of them is. Similarly, Player A searches for Player B, and in this case, the first attempt is successful. Just like searching outside the jungle, Player B's position is revealed to Player A, but not to Player C.

However, unlike other actions performed in the jungle (like throwing a spear or picking up loot), Player A's position will not be known to anyone else in the game, only to the player they are searching for. This can be seen in the video, as after the search is completed, Player C remains unaware of the positions of both Player A and Player B.

Another aspect of covert search not shown in the video is that Player C cannot even know exactly what kind of communication occurred.

Unlike previous mechanisms where a pending challenge was placed on a specific unit and that unit responded to that challenge, the challenge of covert search does not explicitly specify which unit it has been placed on, and the response does not specify which challenge it is responding to. This means that Player C knows that Player A has performed a search and that Player B has submitted a response, but they cannot definitively determine whether there is a direct connection between the two.

Clearly, they could infer a connection due to the proximity of the challenge and response times, but if there are many challenges and responses in a short time, they will not be able to know exactly which search corresponds to which response.

If you consider it fully generalized, this effectively allows two players to interact without revealing their private states to anyone else, and even the fact that they interacted is not disclosed precisely. This shifts from private player discovery to private player interaction.

How Do Private Challenges Work?#

The emergence of this mechanism is a natural evolution from searching outside the jungle; if you can encrypt responses to searches to keep the position of the discovered unit private from other players, then why not also encrypt challenges to keep the position of the challenged unit private? This also progresses narratively; searching is the "more covert" version of the spear, so searches conducted from within the jungle should be more covert than throwing a spear from within the jungle.

When throwing a spear from the jungle, the unit must reveal its position to the contract so it can determine the correct set of challenge tiles based on that position and the provided throw direction. You could instead provide the set of challenge tiles to the contract and provide a zero-knowledge proof that the challenge tiles are valid relative to the private position without revealing it, but this does not work.

A series of challenge tiles is effectively an arrow pointing to the origin of the challenge, and for each direction's arrangement of challenge tiles, there can only be one unique possible origin. This means that knowing the challenge tiles submitted by the unit allows you to determine its position, so the challenge tiles must also remain secret from all players (except the challenged one).

This is why we must "encrypt the challenge." In practice, this means encrypting the challenge tiles so that only the challenged player can decrypt them and submitting the ciphertext to the contract instead of directly submitting the challenge tiles. The challenge is encrypted using the same shared key used for encrypting the response, and the correct encryption is similarly enforced by the accompanying zero-knowledge proof.

The determination of the correct arrangement of challenge tiles is also done within the circuit rather than by the contract, but it essentially executes the same logic of selecting the arrangement of tile offsets from a lookup table indexed by the throw direction and then adding them to the unit's position to obtain the position of the challenge tiles.

The fact that knowing the challenge tiles reveals the unit's position is why you see Player B discovering Player A when they receive Player A's challenge, even though Player A did not succeed in the search. Thus, covert searches only achieve the level of symmetric player discovery, as to discover one player, they inevitably also discover you.

Technically, you could achieve the first tier of asymmetric player discovery by allowing the challenge tiles to be offset from the challenger's position (for example, creating a circular area of challenge tiles a certain distance from the unit throwing it), so knowing the challenge tiles does not reveal the challenger's position. However, for "true" asymmetric player discovery, it should work effectively even if the challenge tiles are directly associated with the challenger. This will be explored further in future projects.

How Do Private Interactions Work?#

The second novel aspect of covert search comes from exploring the possibility of how two players could privately interact. The first step is handled by encrypting challenges and responses, but the next step is to prevent all other players from determining any connection between the two players. As mentioned, this is achieved by allowing challenges not to explicitly specify which unit is being challenged, and responses not to explicitly specify which challenge they are responding to.

If this is indeed the case, then how do we ensure that challenges are always responded to correctly? The issue here is that we want the challenger to be able to punish the challenged player if they do not respond, but at the same time want to ensure that if they do respond, the challenger cannot punish them, even if they do not reveal which response corresponds to which challenge to the contract.

In considering this issue, I asked, "Are there examples from other systems that allow two 'distinct' entities to robustly interact without publicly revealing their connection?" The answer is Tornado Cash. How does Tornado Cash ensure the integrity of interactions between these entities? The answer is using nullifiers (and of course, zero-knowledge proofs).

When the challenged player submits their response, they also submit a nullifier derived from the challenge, but do not publicly reveal which challenge it was derived from. Submitting this nullifier indicates that the challenged player has responded to the challenge. If they have not submitted this nullifier by the end of the response period, then the challenger can