Dark Forest — game powered by zk-SNARK tech

pub <== mimc.outs[0];

mimc.ins[0] <== x;
mimc.ins[1] <== y;
mimc.k <== 0;

*/
component mimc = MiMCSponge(2, 220, 1)

21888242871839275222246405745257275088548364400416034343698204186575808495617

220 = 2 * ceil(log_5 p), as specified by mimc paper, where
p =

/*

/* check MiMCSponge(x,y) = pub */

pub1 <== mimc1.outs[0];
pub2 <== mimc2.outs[0];

mimc1.ins[0] <== x1;
mimc1.ins[1] <== y1;
mimc1.k <== 0;
mimc2.ins[0] <== x2;
mimc2.ins[1] <== y2;
mimc2.k <== 0;

component mimc2 = MiMCSponge(2, 220, 1);

component mimc1 = MiMCSponge(2, 220, 1);

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;

signal diffX;
diffX <== x1 - x2;
signal diffY;
diffY <== y1 - y2;

/* check (x1-x2)^2 + (y1-y2)^2 <= distMax^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;

/* check x^2 + y^2 < r^2 */

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:

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.

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.

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.

Different planets have various properties. Some produce mine; some produce equipment; some support upgrade and some do not… etc.

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.

Click on certain palnet to check out the specs of such planet. Below shows specific parameters of one palnet that has been taken over:

After logging into the game, the main interface looks as shown above. It consists of 4 parts:

1. Toolbar on the left. The player can view Planets and Artifacts. The game supports various plugins.
2. Transaction history on the right.
3. The map of cosmic planet distribution in the center. From the player's perspective, the entire universe consists of a dark background and fog. The dark background indicates that this part of the world is explored and developed. The foggy area is undeveloped. In the developed cosmic world, there are planets of different levels.
4. The scanning control panel is located at the bottom; it manages the scanning process and initial coordinates.

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.

Conclusion:

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.

Game Experience of v0.6 Round 3

During the planet’s movement, the move circuit checks the moving range does not exceed a circular area of radius distMax:

move Circuit

init Circuit ensures the coordinate falls in certain range during the creation of planet. Both x and y coordinates cannot exceed 2³².

mimc(x,y) hash calculates correctly. x/y is private input, while hash value is public input.

Within the circular area of radius r:

The circuit logic is implemented in the folder: darkforest-v0.3/circuits/. The circuits are built using Circom, and the Groth16 protocol is used for proof generation. Both circuits are relatively simple.

In version v0.3 of the game Dark Forest, zero-knowledge proof technology is used to verify two operations related to the planet’s location:

1. Planet initialization (init)
2. Planet movement (move)

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.

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.

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.

The universe of the game is made up with “Planet”:

darkforest-v0.3/eth/contracts

https://github.com/darkforest-eth/darkforest-v0.3.git

As of now, Dark Forest has released version v0.6. However, the code related to the circuit implementation has not been made public on GitHub. To facilitate a better understanding of how zero-knowledge proof technology is utilized in the game, we recommend reviewing the complete source code of version v0.3, which remains available on GitHub.

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:

init Circuit

Zero-knowledge Proof Application

Game Strategy

This article will explore the basic strategy of the game Dark Forest and how it applies zero-knowledge proof technology. At the end, there will be a brief overview of the gameplay experience in the latest release — version v0.6 Round 3 — with illustrations and screenshots.

address owner;
uint256 range;
uint256 population;
uint256 populationCap;
uint256 populationGrowth;
PlanetResource planetResource;
uint256 silverCap;
uint256 silverGrowth;
uint256 silver;
uint256 silverMax;
uint256 planetLevel;
PlanetType planetType;

}

uint256 id;
address player;
uint256 fromPlanet;
uint256 toPlanet;
uint256 popArriving;
uint256 silverMoved;
uint256 departureTime;
uint256 arrivalTime;

}

component rp = MultiRangeProof(2, 40, 2 ** 32);
rp.in[0] <== x;
rp.in[1] <== y;

/* check abs(x), abs(y), abs(r) < 2^32 */

if (_planet.population > _planetArrival.popArriving) {

} else {

);

_planetArrival.popArriving,
_planet.population

_planet.owner = _planetArrival.player;
_planet.population = SafeMath.sub(

_planet.silverMax,
SafeMath.add(_planet.silver, _planetArrival.silverMoved)

_planet.silver = Math.min(

}

}

);

}

} else {

);

);

_planet.population,
_planetArrival.popArriving

_planet.population = SafeMath.sub(

_planet.population,
_planetArrival.popArriving

_planet.population = SafeMath.add(

// simply increase the population if so

if (_planetArrival.player == _planet.owner) {

// checks whether the planet is owned by the player sending ships

) private {

DarkForestTypes.Planet storage _planet,
DarkForestTypes.ArrivalData storage _planetArrival

function applyArrival(

struct ArrivalData {

struct Planet {