Dark Forest – 采用零知识证明技术的游戏
Dark Forest是一款实时策略游戏。星球的移动和攻占是整个游戏的策略重点。为了在不公开星球坐标的情况，还能证明星球的移动正确，引入了零知识证明技术。
Dark Forest是一款MMO（大型多人在线游戏类型）游戏。我比较感兴趣的是这款游戏使用了零知识证明技术。零知识证明技术应用越来越丰富：隐私，跨链，zk Rollup，游戏等等。本文介绍Dark Forest的基本策略，如何结合零知识证明技术。在文章的最后，介绍最新版本v0.6 Round 3的游戏体验和截图。 目前Dark Forest版本已经迭代到0.6。但是，github上的最新的代码并没有公开电路的部分。为了方便理解它如何采用零知识证明技术，可以查看github公布的0.3的完整代码： https://github.com/darkforest-eth/darkforest-v0.3.git ## 01 游戏策略 看看智能合约的源代码，可以对Dark Forest的游戏策略有一定的了解。智能合约的源代码在目录： `darkforest-v0.3/eth/contracts` 整个游戏宇宙由“星球”（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; } ``` 一个星球有两种“资源”：人口（population）和矿（目前支持silver-银）。人口和矿慢慢增长，但是有上限。有矿可以升级。`DarkForestInitialize.sol`定义了几种星球类型。 ``` struct ArrivalData { uint256 id; address player; uint256 fromPlanet; uint256 toPlanet; uint256 popArriving; uint256 silverMoved; uint256 departureTime; uint256 arrivalTime; } ``` 从一个星球能将资源移动到另外一个星球。星球的移动存在速度。移动的同时可以指明携带的资源。当到达时，如果携带的人员超过该星球的人口，就可以攻占星球。攻占逻辑可以查看`darkforest-v0.3/eth/contracts/DarkForestLazyUpdate.sol`的`applyArrival`函数（当移动完成后触发）： ``` 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) ); } ``` 如果是到达自己的星球，人口和银矿直接累加。如果是其他人的星球，如果作战人数不够（小于星球人口），到达星球的人口相应减少。如果作战人数大于到达星球人口，攻占星球，并更新人口（作战牺牲）。 星球的移动和攻占是整个游戏的策略重点。既然是移动攻击，每个星球有一个坐标。为了增加游戏的策略体验，星球的具体坐标并不公开。有点像在浩瀚的宇宙中，只能观察（枚举）周围有限空间（hash碰撞）寻找其他星球。为了在不公开星球坐标的情况，还能证明星球的移动正确，引入了零知识证明技术。 ## 02 零知识证明应用 asDark Forest游戏V0.3利用零知识证明技术证明了两个和星球位置有关的操作：1/ 星球初始化(init) 2/ 星球移动(move)。电路逻辑在`darkforest-v0.3/circuits/`中。电路采用circom开发。电路的证明采用Groth16协议。两个电路相对都比较简单： ### init电路 init电路用来确保星球创建的时候，坐标在范围内。x和y坐标都不超过2^32次方。 ``` /* check abs(x), abs(y), abs(r) < 2^32 */ component rp = MultiRangeProof(2, 40, 2 ** 32); rp.in[0] <== x; rp.in[1] <== y; ``` 在半径为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计算正确。x/y是private input，hash值是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电路 在星球移动时，检查移动的范围不能超过半径为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; ``` 确定原始坐标的hash值以及移动后的hash值，显然具体坐标是private input，hash值是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]; ``` 随着Dark Forest版本的迭代，更新了不少新的玩法。和位置有关的证明的电路也变多了，但是基本逻辑类似，感兴趣的小伙伴可以自行查看。 ## 03 体验 v0.6 Round 3 体验了一下最新的游戏版本：v0.6 Round 3。目前参加游戏需要邀请码。  进入游戏的主界面如上，由4部分组成：1/ 最左边是工具栏，玩家可以查看自己的星球（Planets）和装备（Artifacts）。游戏支持各种插件（plugins）。2/ 最右边是交易记录 3/ 中间是整个宇宙星球分布图。从某个玩家的视角看，整个宇宙由黑色背景和雾色组成。黑色背景是已经开拓的宇宙世界。雾色区域是没有开拓的宇宙世界。在开拓的宇宙世界中有各种等级的星球。4/ 底部是开拓扫描控制栏，可以控制扫描是否开始，从什么坐标扫描。注意在宇宙分布图中的靶向图标，这个图标就是指明正在扫描的宇宙空间。进入游戏的时候，向导程序会引导熟悉基本的功能按钮。默认情况下，扫描程序不停的扫描未知宇宙空间。 点击某个星球，可以查看该星球的具体参数。下图是攻占的一个星球的参数信息：  红色：当前人口数/人口上限。蓝色：当前的矿数/矿上限。粉红色：防御率（百分制）/ 移动速度 / 攻击范围。咖啡色：装备。“send”按钮可以发送人口和矿到其他星球上。“send”功能就是对应电路中的move操作。在move的移动过程中，两个星球中间有白色连线。白色连线上会显示移动的进度。 各种星球的属性不同，有些可以产矿，有些有装备，有些能升级，有些不能升级等等。 每个星球从level 1开始。Round 3的目标是攻占并拥有level 3以上的星球。离原点越近的星球，分数越高者排名越高。在原点还设置了level 9的星球，攻占了这个星球的玩家为第一名。 ## 总结： Dark Forest是一款实时策略游戏。星球的移动和攻占是整个游戏的策略重点。为了在不公开星球坐标的情况，还能证明星球的移动正确，引入了零知识证明技术。 
Dark Forest是一款MMO（大型多人在线游戏类型）游戏。我比较感兴趣的是这款游戏使用了零知识证明技术。零知识证明技术应用越来越丰富：隐私，跨链，zk Rollup，游戏等等。本文介绍Dark Forest的基本策略，如何结合零知识证明技术。在文章的最后，介绍最新版本v0.6 Round 3的游戏体验和截图。
目前Dark Forest版本已经迭代到0.6。但是，github上的最新的代码并没有公开电路的部分。为了方便理解它如何采用零知识证明技术，可以查看github公布的0.3的完整代码：
https://github.com/darkforest-eth/darkforest-v0.3.git
01 游戏策略
看看智能合约的源代码，可以对Dark Forest的游戏策略有一定的了解。智能合约的源代码在目录：
darkforest-v0.3/eth/contracts
整个游戏宇宙由“星球”（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;
}一个星球有两种“资源”：人口（population）和矿（目前支持silver-银）。人口和矿慢慢增长，但是有上限。有矿可以升级。DarkForestInitialize.sol定义了几种星球类型。
struct ArrivalData {
uint256 id;
address player;
uint256 fromPlanet;
uint256 toPlanet;
uint256 popArriving;
uint256 silverMoved;
uint256 departureTime;
uint256 arrivalTime;
}从一个星球能将资源移动到另外一个星球。星球的移动存在速度。移动的同时可以指明携带的资源。当到达时，如果携带的人员超过该星球的人口，就可以攻占星球。攻占逻辑可以查看darkforest-v0.3/eth/contracts/DarkForestLazyUpdate.sol的applyArrival函数（当移动完成后触发）：
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)
);
}如果是到达自己的星球，人口和银矿直接累加。如果是其他人的星球，如果作战人数不够（小于星球人口），到达星球的人口相应减少。如果作战人数大于到达星球人口，攻占星球，并更新人口（作战牺牲）。
星球的移动和攻占是整个游戏的策略重点。既然是移动攻击，每个星球有一个坐标。为了增加游戏的策略体验，星球的具体坐标并不公开。有点像在浩瀚的宇宙中，只能观察（枚举）周围有限空间（hash碰撞）寻找其他星球。为了在不公开星球坐标的情况，还能证明星球的移动正确，引入了零知识证明技术。
02 零知识证明应用
asDark Forest游戏V0.3利用零知识证明技术证明了两个和星球位置有关的操作：1/ 星球初始化(init) 2/ 星球移动(move)。电路逻辑在darkforest-v0.3/circuits/中。电路采用circom开发。电路的证明采用Groth16协议。两个电路相对都比较简单：
init电路
init电路用来确保星球创建的时候，坐标在范围内。x和y坐标都不超过2^32次方。
/* check abs(x), abs(y), abs(r) < 2^32 */
component rp = MultiRangeProof(2, 40, 2 ** 32);
rp.in[0] <== x;
rp.in[1] <== y;在半径为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计算正确。x/y是private input，hash值是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电路
在星球移动时，检查移动的范围不能超过半径为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;确定原始坐标的hash值以及移动后的hash值，显然具体坐标是private input，hash值是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];随着Dark Forest版本的迭代，更新了不少新的玩法。和位置有关的证明的电路也变多了，但是基本逻辑类似，感兴趣的小伙伴可以自行查看。
03 体验 v0.6 Round 3
体验了一下最新的游戏版本：v0.6 Round 3。目前参加游戏需要邀请码。
进入游戏的主界面如上，由4部分组成：1/ 最左边是工具栏，玩家可以查看自己的星球（Planets）和装备（Artifacts）。游戏支持各种插件（plugins）。2/ 最右边是交易记录 3/ 中间是整个宇宙星球分布图。从某个玩家的视角看，整个宇宙由黑色背景和雾色组成。黑色背景是已经开拓的宇宙世界。雾色区域是没有开拓的宇宙世界。在开拓的宇宙世界中有各种等级的星球。4/ 底部是开拓扫描控制栏，可以控制扫描是否开始，从什么坐标扫描。注意在宇宙分布图中的靶向图标，这个图标就是指明正在扫描的宇宙空间。进入游戏的时候，向导程序会引导熟悉基本的功能按钮。默认情况下，扫描程序不停的扫描未知宇宙空间。
点击某个星球，可以查看该星球的具体参数。下图是攻占的一个星球的参数信息：
红色：当前人口数/人口上限。蓝色：当前的矿数/矿上限。粉红色：防御率（百分制）/ 移动速度 / 攻击范围。咖啡色：装备。“send”按钮可以发送人口和矿到其他星球上。“send”功能就是对应电路中的move操作。在move的移动过程中，两个星球中间有白色连线。白色连线上会显示移动的进度。
各种星球的属性不同，有些可以产矿，有些有装备，有些能升级，有些不能升级等等。
每个星球从level 1开始。Round 3的目标是攻占并拥有level 3以上的星球。离原点越近的星球，分数越高者排名越高。在原点还设置了level 9的星球，攻占了这个星球的玩家为第一名。
总结：
Dark Forest是一款实时策略游戏。星球的移动和攻占是整个游戏的策略重点。为了在不公开星球坐标的情况，还能证明星球的移动正确，引入了零知识证明技术。
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。
- 发表于 2021-08-17 11:54
- 阅读 ( 566 )
- 学分 ( 1 )
- 分类：零知识
![[译]几种通用的zk-SNARKs 实现的比较](http://qkl12315.com/wp-content/uploads/2024/04/0027a1d44f941906f0c3cf8a5b9f511e-600x129.jpg "[译]几种通用的zk-SNARKs 实现的比较缩略图")
评论