Dark Forest — One interesting game with zk-SNARK technology
Dark Forest is a MMO (massively multiplayer online) game. I am particularly interested in this game utilizing zero knowledge proof technology. Nowadays, more and more applications of zero knowledge proof technology have been developed, such as privacy, cross-chain, zk Rollup, games, etc. This article will cover the basic strategy of Dark Forest, and how it utilizes the zero-knowledge proof technology. At the end, there will be a brief showcase of the game experience on the latest release v0.6 Round 3 with screenshots.
Currently Dark Forest has released v0.6. However, code regarding the circuit implementation part is not published on github. For the ease of understanding how zero-knowledge proof is utilized, please check out the complete code of v0.3 published on Github.
https://github.com/darkforest-eth/darkforest-v0.3.git
Game Strategy
Check out the source code of smart contract, then you can gain some basic understanding of the Dark Forest game strategy. The code is located at:
darkforest-v0.3/eth/contracts
The universe of the game is made up with “Planet”:
struct Planet {
address owner;
uint256 range;
uint256 population;
uint256 populationCap;
uint256 populationGrowth;
PlanetResource planetResource;
uint256 silverCap;
uint256 silverGrowth;
uint256 silver;
uint256 silverMax;
uint256 planetLevel;
PlanetType planetType;
}A planet has two “resources”: population and mine (only supporting silver at the moment). Both population and mine grow gradually, with an upper limit. DarkForestInitialize.sol defines a couple of types of planet.
struct ArrivalData {
uint256 id;
address player;
uint256 fromPlanet;
uint256 toPlanet;
uint256 popArriving;
uint256 silverMoved;
uint256 departureTime;
uint256 arrivalTime;
}One planet can move resources to another, and there is a speed defined for such moving. One can specify the resources to carry when moving. Upon arrival, if the population landed exceeds current population of the planet, player can take over the planet. Check out the applyArrival function (triggered once moving is completed) at darkforest-v0.3/eth/contracts/DarkForestLazyUpdate.sol for the detail logic:
function applyArrival(
DarkForestTypes.Planet storage _planet,
DarkForestTypes.ArrivalData storage _planetArrival
) private {
// checks whether the planet is owned by the player sending ships
if (_planetArrival.player == _planet.owner) {
// simply increase the population if so
_planet.population = SafeMath.add(
_planet.population,
_planetArrival.popArriving
);
} else {
if (_planet.population > _planetArrival.popArriving) {
_planet.population = SafeMath.sub(
_planet.population,
_planetArrival.popArriving
);
} else {
_planet.owner = _planetArrival.player;
_planet.population = SafeMath.sub(
_planetArrival.popArriving,
_planet.population
);
}
} _planet.silver = Math.min(
_planet.silverMax,
SafeMath.add(_planet.silver, _planetArrival.silverMoved)
);
}
If the destination is the player’s own planet, population and silver mine will accumulate. If the planet belongs to someone else, and the population being moved is less than the population of the planet, the arrving population will decrease. On the other hand, if the operation population is greater than planet population, the planet is taken over and population will be updated due to battle sacrifice.
The planet moving and attacking is the major strategic point of the game. Since it is the moving attack, every planet has a unique coordinate. To enhance the game experience, planet coordinates are kept private. Imagine in the vast universe, and you can only observe (enumerate) the limited surrounding space (with hash collision) to look for other planets. In order to prove the planet moving’s correctness without knowing the coordinates, we utlize the zero-knowledge proof technology.
Zero-knowledge Proof Application
Dark Forest game V0.3 uses zero-knowledge proof technology to prove 2 operations regarding the planet’s location: 1/ planet initialization (init) 2/ planet movement (move). Circuit logic is implemented in darkforest-v0.3/circuits/. Circuit is implemented with circom, and the circuit proof uses Groth16 agreement. Both of the two circuits are rather simple:
init Circuit
init Circuit ensures the coordinate falls in certain range during the creation of planet. Both x and y coordinates cannot exceed 2³².
/* check abs(x), abs(y), abs(r) < 2^32 */
component rp = MultiRangeProof(2, 40, 2 ** 32);
rp.in[0] <== x;
rp.in[1] <== y;Within the circular area of radius r:
/* check x^2 + y^2 < r^2 */
component comp = LessThan(32);
signal xSq;
signal ySq;
signal rSq;
xSq <== x * x;
ySq <== y * y;
rSq <== r * r;
comp.in[0] <== xSq + ySq
comp.in[1] <== rSq
comp.out === 1;mimc(x,y) hash calculates correctly. x/y is private input, while hash value is public input.
/* check MiMCSponge(x,y) = pub */
/*
220 = 2 * ceil(log_5 p), as specified by mimc paper, where
p = 21888242871839275222246405745257275088548364400416034343698204186575808495617
*/
component mimc = MiMCSponge(2, 220, 1); mimc.ins[0] <== x;
mimc.ins[1] <== y;
mimc.k <== 0; pub <== mimc.outs[0];
move Circuit
During the planet’s movement, the move circuit checks the moving range does not exceed a circular area of radius distMax:
/* check (x1-x2)^2 + (y1-y2)^2 <= distMax^2 */ signal diffX;
diffX <== x1 - x2;
signal diffY;
diffY <== y1 - y2; component ltDist = LessThan(32);
signal firstDistSquare;
signal secondDistSquare
firstDistSquare <== diffX * diffX;
secondDistSquare <== diffY * diffY;
ltDist.in[0] <== firstDistSquare + secondDistSquare;
ltDist.in[1] <== distMax * distMax + 1;
ltDist.out === 1;
Consolidate the hash value of both original coordinates and post-moving coordinates. It is rather obvious that the exact coordinates is private input while the hash value is public input.
component mimc1 = MiMCSponge(2, 220, 1);
component mimc2 = MiMCSponge(2, 220, 1); mimc1.ins[0] <== x1;
mimc1.ins[1] <== y1;
mimc1.k <== 0;
mimc2.ins[0] <== x2;
mimc2.ins[1] <== y2;
mimc2.k <== 0; pub1 <== mimc1.outs[0];
pub2 <== mimc2.outs[0];
Many new features are added with iterations of Dark Forest. While more location-related proof circuits are becoming available, the fondamental logics are similar. Please feel free to check them out if you are interested.
Game Experience of v0.6 Round 3
It was a pleasure to experience the latest version v0.6 Round 3 of Dark Forest. As of now participating the game requires invitaion code.
After entering the game, the main UI is as shown above. It is made from 4 parts: 1/ toolbar on the left. Player can check Planets and Artifacts. The game supports various plugins 2/ transaction history on the right, 3/ cosmic planet distribution map in the middle. From player’s viewpoint, entire universe is made up by dark background and fog. Dark background means that part of the world is developed. Foggy area is undeveloped. Different levels of planets exist in the developed cosmic world. 4/ the development scan control panel is located at the bottom, which controls the scanning and starting coordinates. Note that the targeting icon in the distribution map indicates the cosmic space being scanned. At the beginning of the game, there is a guidance walking through these basic function buttons. By default, the scanning program keeps scanning the unknown cosmic space constantly.
Click on certain palnet to check out the specs of such planet. Below shows specific parameters of one palnet that has been taken over:
Red: current population / upper limit of population. Blue: current mine quantity / upper limit of mine quantity. Pink: defense rate (based no percentage) / moving speed / attack range. Brown: equipments. “send” button sends population and mine to other planets. “send” function corresponds to the move operation in circuit. During the moving, two planets are connected with a white line, where shows the current status of moving.
Different planets have various properties. Some produce mine; some produce equipment; some support upgrade and some do not… etc.
Every planet starts from level 1. Target of Round 3 is to attack and to take over planets of level 3+. The closer one planet is to the origin, the higher points and rank player will get. There is a level 9 planet set at origin. Player taking over such planet will score number one of the game.
Conclusion:
Dark Forest is a MMO (massively multiplayer online) game. The planets’ moving and attacking are the major strategic points of the entire game. Zero-knowledge proof technology is utilized in order to prove the planet movement’s correctness without publishing the planet coordinates.
