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 demonstrations 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 full 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 is better served 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 subsequent sections that do not rely on the technical details described.

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

Disclaimer:

Since it is built on MUD (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 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 state; they read from and write to different component contracts.

When I mention "contracts," I am colloquially referring to specific contracts relevant to specific situations, which usually differ in each case.

The exploration of ZK circuit implementations assumes a certain familiarity with the circom language and also uses some newer circom syntax that is 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 an enemy.

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 the foundation of 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 again. When a unit's position becomes private, it does not transition from unambiguous to completely ambiguous; rather, it 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 level of confidence about the unit's position, and the earlier they act, the greater their confidence.

Before delving 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 in the circuit, which are returned to the user through the proof generation 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 that is viewed as additional public inputs at the underlying level. Fundamentally, a ZK circuit takes a series of inputs and checks whether a set of mathematical constraints between those 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 in the circuit does that 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 (such as state transitions), which have natural inputs (old state) and outputs (new state).

For the 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 in 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 verifying ZK proofs 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 (which, in the case of on-chain verification, is 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 receives 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 this brute-force attack, a "random number" value can be added to the commitment, taking the form of 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 precomputing 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, and 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. To allow the unit to traverse the plains, the player submits the expected new position to the PlainsMoveSystem (which inherits from MoveSystem), which checks if the move is valid and then updates the unit's position value 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 move 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 is correctly computed from the new position. This commitment takes the form of poseidon(x, y, nonce).

The map size 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 that all other players know that the unit has made some movement, but do not actually know the exact position to which the unit has moved.

The ZK proof verifies the state transition from one private position to another, referencing an old position commitment and resulting in a new position commitment, so starting from the position commitment submitted when entering the jungle, this can be used to create an arbitrarily long chain of movements through the jungle, 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 that the contract knows is valid.

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 where the unit might be. Just after entering the jungle, if the unit has made 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 logic for the JungleMove circuit is quite simple:

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 and new positions on each axis, and it also checks that the difference does not exceed 1 and that the new values are 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 on each axis limits the unit's movement to a single tile, the line xDiff + yDiff === 1; at the end 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 Check - 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 a maximum value of 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 exactly 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 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 Check - 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 that 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 publicly provided state from 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 Check - III#

While this method solves the linear growth of the number of public inputs with the size of the map (in terms of total tiles), the computational cost required in 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 chunks of the tile being moved to) and the Merkle siblings needed to reconstruct the path from the chunk to the root are passed in as private inputs, while the root of the resulting 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, leveraging the MerkleDataBitAccess circuit, which not only performs the described Merkle checks but 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 advantage 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 could also be applied to the linear commitment method, so the main difference between the two is the efficiency of commitment verification.

Circuit Map Data Check - 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 a tree structure. 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 greater returns, although this introduces some additional implementation complexity.

At the time, I was not aware of this fact regarding the Poseidon circuit implementation, 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 a 31 * 31 map), there is no difference between linear and tree commitments; in both cases, it is just Poseidon(4)(...), which would be correct for a map with 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 large enough. Tree commitments are definitely overkill for ZK Hunt; 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 based on procedurally generated algorithms 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 where 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, 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 believe 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, thus obtaining up to 16 inputs per hash.

Plains/Jungle Movement Summary#

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

• You could replace it with bright 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 bright areas can update over time, although this would require 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 players can enter stealth at any time, regardless of their position, 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 exhausting 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 in some cases even start as private), 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 only reveal when enough damage is taken to be 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 complicate position ambiguity (and any visual representation attempts of that ambiguity).
• 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 containing 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 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 differs slightly from the one used in ZK Hunt. Let’s quickly review 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 see if each result is greater than the threshold. This is how you can "mine" the fog of war in DF step by step (the generation and checking of 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 the sake of simplifying the comparison with ZK Hunt, let’s assume a player 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 no more than the threshold distance from the old planet), which is how players are able to maintain position privacy, similar to ZK Hunt.

Once you discover a position exists 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 by mining the fog of war in DF 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 examples might be the fog of war systems you see in DF or traditional strategy games, where you can reveal the terrain/layout of the world, items, NPCs, etc., but the broadest definition of world discovery could also include things like learning about NPC backstories or even creating novel items through resource combinations.

Since the map in ZK Hunt is completely public from the start, the theme of world discovery is not very relevant to ZK Hunt, so I won’t delve deeper into it in this article, but you can find my discussions 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 relation to 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, items they possess, etc.), but for now, we will focus 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 encounter 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.
  Subcategories of private discovery:

Symmetric Player Discovery - The discovering player also leads to them being discovered.

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 will know whether the search was successful).
• Discovering a player without letting them know whether you successfully searched them (but they will 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 approach 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. You could argue that this makes sense for the world narrative (pointing your telescope at distant space), 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, then 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 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., your character's movement speed, 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 dynamism 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. Don’t 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 did not suffer from these drawbacks.

The fundamental mechanism underpinning 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 just 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 placed randomly on the map never have a chance to find each other.

The difference with position commitments in ZK Hunt is that they include a private random number; poseidon(x, y, nonce), and choosing poseidon instead of mimc has no functional difference (it’s 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 significantly 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 merely an 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 the 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 manner, which, if it hits them, 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 4 hit tiles is actually arbitrary; we could have any number of hit tiles arranged in any way. 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 in, as well as the arrangement of tiles for 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.

Hit tiles go through 3 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. 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 land 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 cleared (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) showing 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 landing in the jungle resolving more slowly than those in the plains; because they have to wait for the challenged player to respond.

The JungleHitAvoid circuit for option 1 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 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 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 computed when submitting the spear throw (poseidon(x1, poseidon(x2, poseidon(x3, ...)))).

In the current implementation, if any hit tile lands 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 tiles. This is clearly very inefficient, as many players who have 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 whose potential positions are touched, 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 the contract logic but violates the "game rules"; they can choose not to submit any response at all.

This means that the unit is effectively frozen, which does not provide any direct benefit, but if the 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 starting point. When entering the game, each player must put down a deposit to play. If they leave the game after playing according to the rules, they can reclaim this deposit. Each pending challenge has a limited response period. If a unit receives a pending challenge and the player who owns the unit does not respond within that period, they can be punished (slashed), resulting in their deposit being forfeited and all their units being eliminated.

In this video, I have 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 elapse, Player A punishes 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 a response being submitted, 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 players' units without taking the said deposit, but adding this feature is quite simple.

Generalizing Punishment#

While the spear's role is 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 a punishable deposit 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 the inclusion of private states 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 the time required to generate a response, submit it, and have it accepted by the contract, while allowing enough margin for differences in players' hardware performance and network latency.

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

Limiting parts of the game to only players with a certain deposit amount (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 limiting participation in any part of the game due to the upfront cost of the deposit.

The threat of punishment should provide sufficient incentive not to break the rules, but if the rules are broken anyway, 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 relevant consequences) can be awarded to the player who was not punished.

World Integrity#

However, if there are more than two players and the game is designed to have a more persistent world (as is the case with ZK Hunt), then this fallback logic can become more complex depending on the nature of the world/punishment context and should be designed to maximize "world integrity." I define world integrity as "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 the 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 wait 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, and the best it can do is drop 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 means discussed later), this may appear as if the loot teleported.

You could try to improve this situation by instead dropping the loot 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 none of the hit tiles match 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 regarding punishment: time 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 yields the following graph:

Clearly, we want to use punishment to deter this delaying behavior, so we can forfeit a portion of the player's deposit when they respond, rather than just forfeit the entire deposit after a strict deadline; the amount forfeited is determined by how long they waited to respond:

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

Doing this minimally punishes players who respond in a timely manner while significantly punishing those who attempt to delay their responses. A malicious actor may 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 reaches a maximum.

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 means of forcing 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, then you could only force the owning player to reveal the fact that they were hit, allowing the contract to reduce their health without revealing their exact position (using a zero-knowledge proof). This effectively reduces the possible positions of the unit to the set of tiles it could have been hit in.

If the unit has a private health state, then you could go even further; the challenged player responds by submitting a new health commitment, which decreases the health value if they were hit, and remains unchanged if they were not hit (enforced by a zero-knowledge proof). This means that other players only see updates to the unit's health commitment, so they do not know whether the unit was hit, thus maintaining complete ambiguity about the unit's position.

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

Actions in the Jungle#

Following the content of 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 their 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 the logic for 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 construct as the spear, searching is not a combat ability but an information-gathering ability.

Here we see Player A searching for Player B, but without success, learning nothing. 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 continued ambiguity indicator present from Player C's perspective. In fact, Player C not only does not learn the unit's position, 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 Searching Works#

Similar to throwing a spear, Player A submits the search direction to the contract, which determines the resulting challenge tiles and initiates a pending challenge against 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 rather 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, and then submit the ciphertext along with a proof that the encryption operation was performed 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, and if they submit ciphertext, that means they are sending their encrypted random number, which means Player A's search was successful, right?

No, because whether Player B is captured 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 captured in the search; otherwise, it will contain a meaningless value. This means that while Player A's search may or may not be successful, Player C, as an external observer, cannot discern the difference.

Night Market#

My thoughts on punishment shifted from solving the non-response issue with the spear to allowing more general "forced interaction," 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 manner, 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 search 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 hosting 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 is done correctly, although the complete 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 cryptographic 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 searching is an involuntary interaction; once a challenge is posed to a player, if they do not respond correctly, they will be punished.

Search Implementation#

For the search (and Nightmarket), Poseidon cryptography is used as a symmetric encryption scheme because it is more suited to snarks than traditional asymmetric encryption schemes, possibly for reasons similar to why Poseidon hashes are more suited to 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 (thus "offline"), and they can do the same with their private key and your public key to arrive at 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 correct shared key is used 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 (x, y) of the responding unit and the position commitment nonce provided privately to the circuit match the public position commitment.
• Derives the shared key from the responder's private key and the searcher's public key, while checking that the responder'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 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 nothing.

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 of those positions 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 would still lead to the position being known to the challenger. Since then, I have realized that encrypting the nonce provides 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 pinpoint the exact position of the unit for all subsequent movements in the jungle, leading to 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, with no relation to previous nonces.

Alternatively, you could allow tracking to persist for a certain number of moves/time rather than until re-entering the jungle. This would require establishing a timer/move counter referenced in the circuit, which would only allow the selection of a new position commitment's random nonce once the duration condition is met, and would also need to enforce reusing the nonce when re-entering the jungle if the condition has not yet been met.

Of course, this tracking behavior can be extended to any type of private state using this commitment scheme; you could track how a player's private health changes over time, how many resources they possess, and so on.

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 a unit's position does 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 behavior gained 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 each possible value of m' within the range r until they find a matching 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 sufficiently small, this method can be extended to encrypt an 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 into a single value by performing m = m_1 + m_2 * r_1 + m_3 * r_1 * r_2 + ... to uniquely represent a single value that represents that set.

Compared to needing around 800 circuit constraints and 4 uint256s to represent the ciphertext for the poseidon encryption (the ciphertext size is rounded to the nearest multiple of 3 for the message size, + 1), using the poseidon hash only requires around 240 constraints and a single 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., "stealth search"), which brings new functionality and adds more encryption complexity.

Here, Players A and 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 when searching outside the jungle, Player B's position is revealed to Player A but not to Player C.

However, unlike performing other actions 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 stealth searching not shown in the video is that Player C cannot even know exactly what kind of communication took place.

Unlike previous mechanisms, where a pending challenge is placed on a specific unit and that unit responds to that challenge, the challenge of stealth searching does not explicitly specify which unit is being challenged, and the response does not specify which challenge it is responding to. This means that Player C knows that Player A performed a search and that Player B 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 the complete generalization, this effectively allows two players to interact without revealing their private states to anyone else, and even the fact that they interacted is not precisely disclosed. This shifts from private player discovery to private player interaction.

How 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 maintain the privacy of the discovered unit's position from other players, then why not also encrypt the challenges to maintain the privacy of the challenged unit's position? This also progresses the narrative; searching is the "stealthier" version of the spear, so searches conducted from within the jungle should be more stealthy 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. Instead, you could 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 is not feasible.

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 be kept secret from all players except the one being challenged.

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 encryption of the challenge is done using the same shared key used to encrypt the responses, 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, then adding them to the unit's position to get 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, stealth searching only achieves the level of symmetric player discovery, as discovering one player necessarily leads to discovering you.

Technically, you could achieve the first tier of asymmetric player discovery by allowing the challenge tiles to be detached from the challenger's position (for example, creating a circular area of challenge tiles at a certain distance from the unit), 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, which will be further explored in future projects.

How Private Interaction Works#

The second novel aspect of stealth searching comes from exploring the possibility of how two players can interact privately. The first step is handled by encrypting the challenges and responses, but the next step is to prevent all other players from determining any connection between the two players. As mentioned above, 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 question here is that we want the challenger to be able to punish the challenged player for not responding, but at the same time, we want to ensure that if they do respond, the challenger cannot punish them, even if they do not reveal to the contract which response corresponds to which challenge.

When considering this issue, I asked, "Are there examples of 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 the 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 they do not publicly reveal which challenge