CaptainZ

CaptainZ

Prompt Engineer. Focusing on AI, ZKP and Onchain Game. 每周一篇严肃/深度长文。专注于AI,零知识证明,全链游戏,还有心理学。可能南方的阳光 照着北方的风。可能时光被吹走 从此无影无踪。
twitter

ZK-Hunt:全链游戏实现隐藏信息的新尝试

—— 介绍 ——#

ZK Hunt 是一款类似 RTS 的链上 PvP 游戏,探索了不同的 ZK 游戏机制和信息不对称性。它是使用 MUD 框架制作的,该框架处理整体合约架构、网络和客户端同步逻辑,以及用于 ZK 证明生成和验证的 circom。

这款游戏是在 2022 年 0xPARC Autonomous Worlds 驻地期间构建的,当时还有许多其他团队在研究他们自己的精彩项目,你可以在这里找到一份完整的演示列表。如果你想要一个更短的 ZK Hunt 机制摘要,那么你可以在这里查看我的演示录像。

ZK Hunt 最初只是一个关于在链上游戏中实现私密移动的新方法的简单想法,而在驻地期间,加入了更多利用不同加密构造的机制,从而开启了新的游戏体验。

在开发过程中,我有关于如何将其扩展成一个完整的 EFT(逃离塔科夫)式游戏的想法,在这个游戏中,玩家带着一定数量的战利品 / 装备进入狩猎场,杀死其他玩家以夺取他们的战利品,然后试图在被其他人杀死之前 “提取” 他们的战利品。然而,随着时间的推移,我意识到这个项目更好地作为一种探索 ZK 游戏机制可能性的媒介,最终作为一个教育资源。

所以在这篇文章中,我将介绍 ZK Hunt 中存在的不同机制,用于实现这些机制的具体技术,我围绕私有状态开发的一些思维模型,以及这些机制如何被更广泛地概括。

我试图在较高的层次上解释核心概念,同时也更深入地探讨技术方面,所以希望这篇文章能对具有这些主题不同熟练程度的合理范围的读者有所帮助。如果任何部分过于深入技术细节而超出了你的喜好,请随时跳过,因为在后续部分中你可能会发现不依赖于所述技术细节的进一步价值。

最好对智能合约、加密、哈希函数和 ZK 证明有基本的了解。

免责声明:

由于是在 MUD(1.x,2.x 两个版本是不同的)上构建的,ZK Hunt 中的合约遵循 ECS 模式。你可以在这里了解更多关于 MUD 如何实现这种模式的信息,但在较高的层次上,游戏中的所有 “实体” 都表示为唯一的数值 ID(EVM 中的 uint256s),实体的属性存储在不同的组件合约中,这些合约不包含业务逻辑(本质上只是从实体 ID 到值的映射),玩家与不同的系统合约互动,这些合约包含业务逻辑但不包含实体状态,它们从不同的组件合约中读取和写入。

当我提到 “合约” 时,我是在口语上指特定情况下相关的特定合约,通常在每种情况下都会有所不同。

ZK 电路实现的探索假定你对 circom 语言有一定的熟悉度,并且也使用了一些尚未包含在标准文档中的较新 circom 语法。为简洁起见,下面的电路代码的某些部分已被排除。

—— 丛林 / 平原移动 ——#

下面的视频展示了 ZK Hunt 的核心机制;公共 / 私有移动的二分法。在视频中,你可以看到两个玩家,左边的玩家 A 和右边的玩家 B。每个玩家控制一个他们之前生成的单位,用白色轮廓突出显示,并可以看到另一个玩家的单位,用红色标出以显示他们是敌人。

移动是通过选择目的地并确认路径来执行的。每个移动都作为单独的交易提交,一旦前一个移动被确认,就提交新的移动。ZK Hunt 运行在一个配置为有一秒钟区块时间的 EVM 链上,也就是单位能够以每秒一个瓦片的速度移动,而其他单位动作能够以低延迟处理。

在这个世界中,我们有两种类型的瓦片;用草显示的平原瓦片,和用树显示的丛林瓦片。穿越平原是公开的,这一点通过玩家 B 能看到玩家 A 的位置更新为他们移动的事实来说明。进入丛林也是公开的,但穿越丛林是私密的,以至于玩家 A 失去了玩家 B 在丛林中的位置的踪迹,并且只能模拟一个不断增长的潜在位置集合,这些位置用问号显示。再次从丛林出来回到平原是公开的,所以潜在位置集合崩溃了。

这种行为是 ZK Hunt 的基础;单位有一个状态片段(它们的位置),可以根据游戏中的动作从公开变为私有,然后再变回公开。当一个单位的位置变得私有时,它不是从没有歧义变为完全歧义,而是获得了一个可以随时间增加的有限歧义度,这是由于基于瓦片的移动的受限性。这允许其他玩家对单位的位置有一定程度的信心,并且他们越早采取行动,信心就越大。

在深入了解这个机制是如何工作的之前,我需要建立一些关于 ZK 证明输入 / 输出和承诺的先决条件理解。

关于 ZK 电路输入输出的一些看法#

在一个 ZK 电路的 circom 代码中,您可以定义公共输入、私有输入和输出,其中输入由用户提供,输出则是电路内部进行的某些计算的结果,这些结果在创建证明时通过证明过程返回给用户:

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();

然而,重要的是要知道输出实际上只是一个语法抽象,在底层被视为额外的公共输入。从根本上讲,一个 ZK 电路接受一列输入,并检查这些输入之间的一组数学约束是否得到满足,唯一的输出是 “真” 或 “假”。上面的电路在功能上等同于这个:

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();

这里的区别在于,如果 c 被定义为输出而不是输入,那么用户不必计算 c 的值,而是在证明生成期间,电路内部定义的逻辑为他们做了这件事,这对于确保使用的值满足电路是方便的。

输出实际上只是额外的公共输入这一事实,在查看合约中的证明验证逻辑时是相关的。solidity 验证器接受一列输入(连同证明本身),其中在此列表中电路代码中定义的输出首先出现,公共输入随后出现,唯一真正的 “输出” 是 “成功” 或 “失败”。

尽管如此,从概念上讲,认为公共输入和输出之间存在区别仍然是有用的,特别是当涉及到验证计算过程(如状态转换)的电路时,这些电路具有自然的输入(旧状态)和输出(新状态)。

对于 ZK Hunt 中的电路,公共输入通常是已经在之前的证明中计算 / 验证并存储在合约中的值,而输出则是新证明内部执行的计算结果,这些结果由该证明验证,然后保存到合约中。

最后要了解的一点是,尽管 ZK 证明验证的成本被认为是恒定的(至少对于某些证明系统,如 groth16 等),但它实际上基于公共输入的数量而增加,这在进行链上验证时可能很重要。在我理解公共电路输入和输出之间缺乏功能区别之前,我认为你可能通过将所有公共输入转换为输出来最小化这种成本,但基于上面的解释,这显然是行不通的。

关于 Commitment 方法的的一些看法#

Commitment(承诺) 是一种工具,它(除其他外)可以被一个零知识证明(ZK proof)用来可验证地引用用户先前 “承诺” 的一些私有状态,而无需向验证者(在链上验证的情况下,就是向观察链的每个人)透露该状态。用户将承诺 C 作为公开输入提供给证明,将私有状态 s 作为私有输入,并且证明在内部计算出由 s 产生的承诺,并检查它是否与 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();

在验证证明时,验证者会获得公共信号的值,因此在检查提供的承诺值是否正确(即与用户先前提交的值匹配)时,他们可以确信在生成证明时使用了正确的私有状态值。

您可以使用各种不同的承诺方案,但也许最简单的就是取状态的哈希值。在 ZK Hunt 中使用 poseidon 哈希是因为它在电路内计算比其他常见的哈希函数更有效率。如果私有状态是从足够大的范围内随机选择的足够随机的值(如私钥或随机种子),那么仅仅取该值的哈希就足以作为一个承诺。

但是,如果状态可能采取的值范围相对较小(例如,介于 1 和 10 之间的值),那么对手只需计算每个这些值的结果承诺,看看哪一个与用户提交的承诺相匹配,从而找出它对应的状态值,破坏了承诺的隐私性。

为了防止这种蛮力攻击,可以向承诺中添加一个 “随机数” 值,使其采取 poseidon(状态,随机数)的形式。随机数作为额外的私有输入提供给电路,并且从足够大的范围内随机选择,以确保预先计算所有可能的承诺是不可行的,从而保留状态的隐私性。

如果一个证明以某些私有状态的承诺作为输入,根据一些规则在内部对状态进行一些更改,然后输出对新状态的承诺,那么证明就可以有效地代表一个可验证的私有状态转换。如果你将一个证明的输出承诺作为另一个证明的输入,那么你可以随着时间创建一系列私有状态转换。

Snip20231013_70

正是这些对私有状态的承诺,以及这种随着时间更新承诺的过程,构成了 ZK Hunt 中移动方式的核心。现在我们已经建立了这种先决条件的理解,我们现在可以看一下四种不同的移动情景:

1. 平原到平原#

Snip20231019_74

单位的位置存储在 PositionComponent 中。为了让单位穿越平原,玩家将期望的新位置提交给 PlainsMoveSystem(继承自 MoveSystem),该系统检查移动是否有效,然后更新位置组件中单位的位置值。

这种验证逻辑检查单位的旧位置和新位置都是平原瓦片,新位置在地图内,并且移动是单一的基本步骤(曼哈顿距离为 1)。任何对单位公开位置的更新都会反映在所有玩家的客户端上。

2. 平原到丛林#

Snip20231019_75

进入丛林的过程与上述相同,不同之处在于合约检查移动到的新位置是丛林瓦片而不是平原瓦片。此外,玩家还提交对新单位位置的承诺(以类似的方式保存到组件中),以及一个 ZK 证明,表明承诺是从新位置正确计算出来的。这个承诺采取 poseidon (x, y, nonce) 的形式。

ZK Hunt 的地图大小相对较小(31*31,但可以配置得更大 / 更小),这意味着可能的位置总数是有限的,因此需要包含一个随机数以确保承诺不能被蛮力破解。当然,入口位置已经是公开的,所以没有必要蛮力破解承诺,但这对未来位置承诺来说将不是这种情况。

这个承诺不是承诺一个私人位置,而是作为随后在丛林中私下移动的起点。随机数需要保持私密(稍后会详细说明为什么),因此需要 ZK 证明来允许合约检查承诺是否与位置相匹配,而不必透露随机数。电路非常简单:

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

在验证期间,合约为 x 和 y 提供输入值,并将输出的承诺保存到相关的 PositionCommitmentComponent 中。这个电路被称为 PositionCommitment(而不是 JungleEnter,因为它在某一点是这样的),因为它在其他情况下被重用,需要检查公开提供的位置是否与一个承诺相匹配,而不揭露随机数。

3. 丛林到丛林#

Snip20231019_76

在丛林中移动时,玩家不再向合约提交新位置,而是只提交对新位置的承诺,以及一个 ZK 证明,证明之前承诺的旧位置和新位置之间的移动是有效的。这意味着所有其他玩家都知道该单位进行了某些移动,但实际上并不知道该单位移动到了哪个确切的位置。

ZK 证明验证了从一个私人位置到另一个私人位置的状态转换,参考了一个旧的位置承诺,并导致一个新的位置承诺,因此从进入丛林时提交的位置承诺开始,这可以用来创建一个任意长度的通过丛林的移动链,其中一个证明的输出承诺成为下一个的输入。

新位置承诺的有效性取决于旧位置承诺的有效性(这里的有效性意味着承诺并不代表单位按照移动规则本不应该到达的位置),因此,即使入口位置也是公开的,但进入丛林时提交初始位置承诺的原因是要以合约已知有效的承诺开始移动链。

从玩家 A 的角度来看,单位的位置模糊性在视觉上通过问号的存在显示出来,每个问号代表单位可能所在的一个潜在位置。刚进入丛林时,如果单位进行了新的移动,那么它们可能已经移动到了与入口瓦片相邻的任何丛林瓦片上。如果他们再移动,那么他们可能已经移动到了他们先前潜在位置相邻的任何丛林瓦片上,依此类推,这就是你看到的洪水填充行为。

验证移动正确性的 JungleMove 电路相当简单:

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);

第一部分检查旧的 (x, y) 值是否真的是已经承诺的值,oldCommitment 公共输入是在验证期间由合约提供的,确保玩家不能对他们的旧位置撒谎。

第二部分使用 CheckDiff 计算每个轴的旧位置和新位置之间的绝对差值,该部分还检查差值不超过 1,并且新值仍在地图内:

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;
}

虽然每个轴的 CheckDiff 限制了单位的移动距离为单个瓦片,但该部分末尾的 xDiff + yDiff === 1; 行确保单位只在 x 轴或 y 轴上移动,防止对角线移动。

第三部分检查新位置是否是丛林瓦片,但逻辑有点复杂,所以稍后再讨论。

第四部分输出新的位置承诺,如果移动成功,合约将其保存为单位的新值。

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

注意,用于新承诺的新随机数是 oldNonce + 1,而不是作为额外私人输入提供的新随机值。这是一个重要的选择,对稍后讨论的一些机制产生了影响,这就是为什么初始随机数在进入丛林时需要保持私密。

4. 丛林到平原#

Snip20231019_77

为了离开丛林,玩家必须向合约揭露单位在丛林中的当前位置(因为合约不知道这个位置),以便它可以检查从丛林瓦片到平原瓦片的移动是否有效。为了防止玩家提供他们所在的丛林区域边界上的任意丛林瓦片,他们必须证明揭露的丛林位置是与合约中存储的位置承诺相匹配的位置。

然而,这并不需要提交一个 ZK 证明,因为玩家可以直接揭露单位位置的(x,y)坐标,以及用于位置承诺的随机数,然后合约简单地比较这些值的 poseidon 哈希是否与存储的位置承诺相匹配。离开丛林会导致位置模糊性消失,并且单位的位置会向所有其他玩家公开。

电路内地图数据检查 - I#

由于 ZK Hunt 中的地图瓦片只能是平原或丛林,因此它们的状态可以用单个比特表示(平原为 0,丛林为 1)。从理论上讲,这意味着我们可以将这些值打包到单个整数中,并使用单个 uint256 表示整个 16 * 16 瓦片地图。

然而,由于(默认的)circom 素数域大小的性质,circom 信号只能表示最大约 2^253.6 的值,因此单个信号只能携带 253 个 “有用的” 信息位。这意味着您无法用单个信号表示一个 16 _ 16 的地图,但您可以表示一个 15 _ 15 的地图,这将使用 225 位,这正是 ZK Hunt 的第一个原型所做的。

如果您想检查电路中给定的(x,y)处的瓦片值,那么您计算 tileIndex,即 x + y * mapSize(在此示例中,mapSize = 15),将地图数据信号输入分解为每个代表单个比特的一系列信号,使用 circomlib 的 Num2Bits (),然后从该数组中选择第 tileIndex 位(在 circom 中是 O (n) 操作而不是 O (1))。下面是它的样子(简化版):

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;

电路内地图数据检查 - II#

如果您想表示大于 15 _ 15 的地图,比如 22 _ 22 的地图怎么办?嗯,这样的大小的地图需要 484 位来表示,所以这将适合两个信号,第一个信号存储前 253 位,第二个信号存储其余的 231 位。我把这些信号称为 “地图数据块”。在电路中,您将使用 Num2Bits () 将这两个块分解为信号数组,连接数组,然后再从数组中选择第 tileIndex 个元素:

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;

您可以通过增加地图数据块的数量来扩展这种方法,以表示更大的地图。然而,因为地图数据块需要由合约提供作为公共输入,地图越大,验证成本就越高,因为公共输入的数量增加了。为了解决这个问题,地图数据块可以作为私有输入传入,然后根据对块的公开承诺进行检查,这意味着无论地图的大小如何,都只需要一个公共输入:

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
...

在之前的场景中,承诺被用来允许玩家在电路中可验证地引用一些私有状态,而在这里,它被用来允许电路引用合约提供的任意大的公共状态,同时只需要传递一个公共信号,而不是包含全部公共数据的足够数量的信号。需要注意的重要一点是,circomlib 实现的 poseidon 哈希仅支持多达 16 个输入,但您可以通过像这样将哈希链接在一起来解决这个问题:poseidon (x1, x2, ..., x15, poseidon (x16, x17, ...))。

电路内地图数据检查 - III#

尽管这种方法解决了公共输入数量与地图大小(就瓦片总数而言)成线性增长的问题,但验证地图数据承诺所需的电路内计算仍与地图的大小成线性增长,对于非常大的地图,可能导致非常大的电路(许多限制),从而导致更长的证明生成时间。

为了改善这一点,可以将对地图数据块的线性 / 链式承诺换成默克尔树承诺,这样,如果电路中需要检查单个瓦片,那么只需计算与默克尔树相关分支有关的哈希,从而使成本与地图的大小呈对数关系,而不是线性关系。

4oGlDSa

相关的地图数据块(包含正在移动至的瓦片的块)和用于重构从块到根的路径所需的默克尔兄弟节点作为私有输入传入,而产生的默克尔路径的根则与合约作为公共输入传入的树的根进行核对。

这是 ZK Hunt 最终采用的方法,也是 JungleMove 电路的第三部分所做的事情,利用了 MerkleDataBitAccess 电路,除了执行描述的默克尔检查外,还进行地图数据默克尔叶子的位分解,并返回提供的 bitIndex 处的相关瓦片值:

这种实现还有一个好处,就是只对包含瓦片的地图数据块执行 Num2Bits (),而不是全部,然后只需要从一个块中的瓦片数量中选择,而不是所有块中的瓦片总数(O (n) 操作),但这种优化也可以应用于线性承诺方法,所以两者之间的主要区别是承诺验证的效率。

电路内地图数据检查 - IV#

上面的示例展示了一个二叉树,这与 ZK Hunt 中的实现方式相匹配,但这实际上并不是最高效的树结构证明方式。在电路内,计算具有 2 个输入的波塞冬哈希(Poseidon (2)(...))需要 240 个约束,但有趣的是,计算具有 16 个输入的波塞冬哈希(Poseidon (16)(...))只需要 609 个约束,因此,使用六叉树而不是二叉树可以让您获得最大的回报,尽管这会带来一些额外的实现复杂性。

当时我并不知道关于波塞冬电路实现的这一事实,这就是为什么我选择了二叉树。然而,即使考虑到这一点,对于 ZK Hunt 用来表示地图的块数量(31 * 31 的 4 块),线性承诺与树承诺之间没有区别;在这两种情况下,它只是 Poseidon (4)(...),对于最多需要 16 块的地图,这将是正确的。

即使当您超过 16 个块以至于存在区别时(线性承诺需要链式多个哈希,树承诺需要多个级别),我有一种预感,由于额外的默克尔逻辑开销,树承诺实际上可能比线性的效率低,只有当地图足够大时,才会更加高效。树承诺对于 ZK Hunt 来说绝对是过度的,线性承诺很可能足以满足大多数用例,但不管怎样拥有概念证明都是好的。

由于 ZK Hunt 中的地图数据是作为输入传入电路的,而不是硬编码到电路中或基于在电路中计算的程序生成算法,所以地图可以被设计为具有任意内容(每场比赛),并且实际上可以随时间变化。我在开发过程中有一个想法是玩家能够烧毁丛林瓦片,新的丛林瓦片会随着时间自然生长,但这样做会破坏用于计算潜在位置显示的逻辑。

这里描述的方法可以用来将任何类型的公共数据集传入电路,您想从中选择,就像查找表一样。这可以是武器伤害值、物品价格、NPC 位置等。ZK Hunt 使用单个比特来表示数据集的每个元素,因为它们只能是两个选项之一,但可以对实现进行更改,以允许每个元素用任意数量的比特表示,使得每个元素可以取任意数量的值。

最后可能需要知道的有用的事情是,circomlibjs 可以生成的 solidity 实现的波塞冬只能容纳最多六个输入(我认为是由于 EVM 的堆栈深度有限),因此,使用超过六个输入的波塞冬哈希不能通过合约中的直接计算创建或验证,但您当然可以通过使用 ZK 证明来解决这个问题,从而每个哈希最多获得 16 个输入。

丛林 / 平原移动概括#

在一定程度的概括层面上,上述描述的移动系统允许游戏拥有隐身区域、非隐身区域,以及实体在这两者之间移动的能力。特定的平原 / 丛林情境可以为不同类型的游戏重新设计:

  • 您可以用光亮和阴影区域来替换它,在那里世界中放置了特定的光源,这些光源径向地发出光线,而固体障碍物通过阻挡这些光线来创建阴影区域(这个点子归功于 lermchair)。如果光源可以移动(例如手持灯笼),那么光亮区域可以随时间更新,尽管这需要额外的逻辑来处理玩家在未移动的情况下从光明过渡到阴影(更不用说链上动态阴影投射计算了)。

  • 基于上述想法,您可以创建一个不对称的多人游戏,比如捉迷藏或甚至是《逃杀》(Dead by Daylight),在那里有一个始终处于公开位置的搜索者,并发出一个可以被障碍物阻挡的视野区域。会有一些隐藏者,他们的位置对搜索者保持私密,直到他们进入其视线,此时他们的位置变得公开并可以更容易地被追捕。

  • 您可以创建一个系统,在该系统中隐身不绑定到地图的特定区域,而是玩家可以随时进入隐身,无论他们的位置如何,但只有有限的时间 / 移动次数。有了这个,您可以构建一个游戏,在这个游戏中,玩家可以钻进地下,并私下地隧道到其他地方,但他们被迫重新浮出水面,以免耗尽能量(或其他一些原因),限制可以实现的最大位置模糊性,而无需将隐身锁定到特定区域。

  • 您可以用基于图的位置 / 移动(例如,在通过走廊连接的离散房间之间移动)来替换基于网格的位置 / 移动,这会影响在私下移动期间位置模糊性的增长方式。
    在更高层次的概括上,平原 / 丛林移动系统代表了一种给予玩家某种状态的方式,这种状态可以是公开的,可以过渡到私密(或在某些情况下甚至开始时就是私密的),可以在保持私密的同时有效地更新,并可以被公开揭示。在 ZK Hunt 中,这种状态用于代表单位的位置,但它可以轻易地代表任何其他类型的状态,具有任意的更新逻辑:

  • 玩家可以拥有私密的健康状况,在受到另一位玩家的伤害时私下更新,并且只有在受到足够的伤害而被杀时才揭示。

  • 玩家可以有一个私人的耐力计和一个私人的位置,他们在移动时耗费的耐力量决定了他们可以移动的距离。这意味着当玩家进行私下移动时,其他玩家将无法判断他们是否选择了移动很远的距离,或是为了保存耐力而移动较短的距离,或是介于两者之间。这将使位置模糊性(以及对这种模糊性的任何视觉表示尝试)变得更加复杂。

  • 玩家可以拥有一个私人物品库,从中他们可以使用产生公共或私人效果的物品(例如,公开伤害其他玩家,或私下治疗自己)。为了填充这样的私人库存,玩家可以打开箱子,其中包含一系列可能性中的一件物品,每件物品都有不同的发生概率。箱子包含的物品是私下确定的,这样其他玩家就不知道玩家收到了哪个物品,他们的库存内容可以保持私密。

  • 或者,也许玩家可以发现另一个玩家库存的内容,然后私下从他们那里偷走一件物品。您如何实现这样的事情将在后续部分变得更加清晰。
    显然,这里可以做很多事情。然而,必须指出的是,这里所涉及的核心思想绝不是全新的……

在黑暗森林的肩膀上#

这种私有状态 / 承诺 / 转换方案的明显灵感,甚至是一般利用 ZK 构建链上游戏,显然来自《黑暗森林》(Dark Forest)。然而,DF 采取的方法与 ZK Hunt 中使用的方法略有不同。先快速回顾一下 DF 的工作原理:

在 DF 中,一个特定位置是否包含行星,取决于该位置的整数坐标的 MiMC 哈希值是否大于某个阈值(mimc (x, y) > threshold)。这意味着,为了让玩家找出空间的特定区域包含哪些行星,他们只需哈希该区域中的所有唯一位置,并查看每个结果是否大于阈值。这就是您可以在 DF 中逐步 “挖掘” 战争迷雾的原因(生成和检查一堆哈希的方式与比特币挖矿的工作方式非常相似)。

由于 DF 地图的庞大尺寸和行星的自然稀疏性,挖掘地图中的每一个位置都需要相当多的时间(除非您拥有足够强大的硬件),因此您被迫战略性地选择利用您的哈希算力开采的地图的特定区域。

eF5OO0n

在 DF 中,玩家可以同时向多个行星发送资源并占领它们,因此一个 “玩家” 实际上可以同时在多个位置,但为了简化与 ZK Hunt 的比较,我们将假设玩家一次只能在一个行星上。以下解释仍应成立。

当玩家在其初始行星上出现或移动到另一个行星时,行星位置的哈希值会作为位置承诺提交给合约,而不是直接提交位置,并附上一个 ZK 证明,显示承诺的有效性(与哈希对应的位置实际上包含一个行星,如果是移动,则新行星与旧行星的距离不超过阈值),这就是玩家能够保持位置隐私的方式,与 ZK Hunt 的方式相同。

一旦您根据其位置哈希发现某个位置存在行星,那么您可以通过将他们最近提交的位置承诺与该位置哈希进行比较,来看看哪些玩家(如果有的话)在那个行星上。现在,让我们花一点时间来建立这些寻找行星和寻找玩家的过程是如何融入更广泛的概念框架中的。

链上世界发现 / 玩家发现#

在 DF 中通过挖掘战争迷雾来发现行星是我所称的 “链上世界发现” 更大类别中的一种特定方法。一个简单的定义是:游戏世界的(非玩家)内容 / 状态最初对玩家是隐藏的,玩家必须执行某些操作才能逐渐随时间发现它。

最明显的例子可能是您在 DF 或传统策略游戏中看到的战争迷雾系统,您可以揭露世界的地形 / 布局、物品、NPC 等,但世界发现的最广泛定义也可以包括像了解 NPC 的背景故事,甚至通过资源组合创建新颖物品之类的事情。

由于 ZK Hunt 的地图从一开始就完全公开,因此世界发现的主题与 ZK Hunt 关系不大,所以我不会在这篇文章中更深入地讨论它,但您可以在这里找到我对世界发现不同方法的讨论,我将在未来的项目中探索一些新方法。

另一方面,通过在 DF 中挖掘战争迷雾来发现玩家,我认为这是 “链上玩家发现” 的一种特定方法,这与 ZK Hunt 有更直接的关系,正如名称所暗示的。再次简单定义:玩家(和 / 或玩家控制的实体)拥有私密的位置,其他玩家可以通过执行特定操作来发现。更完整的定义可能会扩展到发现玩家的所有私密属性(例如他们的健康状况,他们拥有的物品等),但现在我们只关注位置。

甚至可能有意义在定义上建立世界 / 玩家发现作为严格的二分法;发现属于 “玩家” 的事物,和发现属于 “非玩家” 的事物,但是如果建立一个复杂的非玩家代理的第三类别更有意义,那么这可能会崩溃,因为他们的发现过程与世界发现足够不同。

在我探索玩家发现的各种方法时,我遇到了几个不同的子类别。我的当前模型如下:

  • 公开玩家发现 - 发现玩家会向每个人揭露他们的位置
  • 私人玩家发现 - 发现玩家只向发现者揭露他们的位置
    私人发现的子类别:

对称玩家发现 - 发现玩家也会导致他们发现你

非对称玩家发现 - 分为三个层级,每个层级都继承了前一层级的权限:

  • 在不让玩家发现你的情况下发现玩家(但他们确实会知道搜索是否成功)
  • 在不让玩家知道您是否成功搜索他们的情况下发现玩家(但他们确实会知道您搜索了他们)
  • 在不让玩家知道您根本搜索了他们的情况下发现玩家
    正如您所看到的,模型越深入,信息泄露就越少。考虑到区块链的本质上公开性,我发现通常情况下,类别的隐私性越强,实现的难度 / 复杂性就越大。展望未来,我们可以使用这个框架来评估 DF 和 ZK Hunt 用于玩家发现的方法。

黑暗森林分析#

由于 DF 的战争迷雾挖掘和行星 / 玩家位置哈希比较完全是外部过程,不需要与游戏世界 / 合约逻辑 / 其他玩家直接互动,DF 的方法实现了最高层次的不对称玩家发现。然而,它并不完美,有几个缺点:

空间上无限制:玩家可以选择挖掘地图的任何部分,而不论他们的位置。可以说,鉴于世界叙事(将你的望远镜对准遥远的太空),这对 DF 来说在某种程度上是有意义的,但对于其他类型的游戏,无法基于玩家的位置限制发现是这种方法的一个重大缺点。如果你在玩 PvP 地牢游戏,那么你不应该能够发现离你很远的玩家。玩家发现应该有能力被本地化。

时间上无限制:玩家发现新行星的速度,以及因此在这些行星上可能发现的任何玩家,基本上取决于他们计算哈希的速度,因此取决于他们的硬件有多强大。这创造了一个本质上不平等的竞技场,通过投入额外的资本可以使其更加不平等。你发现玩家的能力应该完全由世界的规则 / 状态决定(例如,你的角色的移动速度,你的望远镜的强度,玩家之间的障碍等)。

永久性:一旦你找到一个星球并确定了它的位置哈希,你将能够在游戏剩余时间里看到任何到 / 离它的玩家移动。当涉及到发现世界时(至少对于静态属性而言),永久性发现可能是好的,但当涉及到发现玩家时就不那么是了。仅仅因为你访问了一个特定区域,并不意味着你应该能够看到在你离开后访问该同一区域的玩家。玩家发现应该具有动态性和非永久性。

在 DF 中,玩家发现在某种程度上可以被认为是世界发现的副产品,因此上面列出的缺点实际上只是适用于世界发现的同样缺点的延伸。不要误会,DF 用于允许私人世界和玩家发现的系统设计相当不可思议,并且在其用例中运作良好,但如果有一种方法不受这些缺点的影响,那将会更好。

在 DF 中支撑玩家发现的基本机制是能够 “猜测和检查”(计算并比较)位置哈希的能力,行星的存在只是为了缩小你实际检查的位置哈希。这是可能的,因为玩家提交的位置承诺只是位置的哈希;mimc (x, y)。DF 地图足够大,以至于搜索整个地图并非易事,但也不是如此之大,以至于随机放置在地图中的玩家永远没有找到彼此的机会。

ZK Hunt 中的位置承诺与 DF 的不同之处在于它包括了私有随机数;poseidon (x, y, nonce),选择 poseidon 而不是 mimc 没有功能差异(它只是电路更有效率)。这种添加特别阻止了 “猜测和检查” 位置哈希的能力,尽管 ZK Hunt 的地图明显小于 DF 的,因此你不能通过这种方式找到玩家。如果情况是这样,那么 ZK Hunt 中的玩家发现是如何工作的?你如何与在丛林中位置模糊的玩家互动?

— 矛 —#

矛是一组线性排列的四个 “击中瓦片”(或更通用地说,是 “挑战瓦片”),从玩家身上延伸出去,你可以朝 32 个不同的方向之一瞄准。为了展示矛的一些方面,我们还会引入第三个玩家,玩家 C,位于右下角。玩家 C 不控制任何单位,他们只是作为第三方观察者,代表游戏中所有其他玩家的视角。

在上面的视频中,你看到玩家 A 向平原上玩家 B 的一个单位投掷矛,导致他们被杀并丢下他们的战利品,然后玩家 A 的单位捡起来。然后玩家 B 将他们的另一个单位送入丛林中以获得一些位置模糊性,玩家 A 试图向他们投掷矛。第一次尝试没有命中,这种模糊性得以保持,但第二次尝试成功了,导致该单位的位置被揭示,它死亡并丢下其战利品。

这是 ZK Hunt 包含的第一个工具,允许你与在丛林中位置不明的单位互动。矛既是一种战斗能力,也是一种玩家发现方法,但这些方面可以独立存在。你可以换成以相同方式投掷的简单石头,如果它击中了它们,它会让一个单位 “大声喊叫”,揭示它们在丛林中的位置而不杀死它们。

被矛击中会向所有玩家揭示单位的位置,由玩家 C 也了解到单位位置的事实说明,所以矛会被分类为公开玩家发现的方法。让我们了解它是如何工作的…

击中瓦片#

这种 4 个击中瓦片的线性排列实际上是任意的,我们可以有任何数量的击中瓦片的任何种类的排列。你可以用这个创建一个俱乐部,利用更小的、弧形的击中瓦片,或者也许是一个炸弹,产生一个更大的圆形区域的击中瓦片,远离投掷它的单位。

矛可以被投掷的方向数量,以及每个方向的瓦片排列也是完全任意的。完整的排列集合被硬编码在合约中,作为每个方向的偏移量列表。执行矛投掷时,选择的 directionIndex 会被发送到合约,然后通过将一组偏移量(对应于该方向)加到单位的位置来确定击中瓦片的结果位置。

击中瓦片经历 3 个阶段:

Snip20231019_78

  1. 潜在的(以半透明白色显示):当玩家还在瞄准矛时。
  2. 待定的(以实心白色显示):玩家已经确认投掷并向合约提交了方向。
  3. 已解决的(以红色显示):合约已确定击中瓦片是否击中了任何东西。击中瓦片是基于逐个瓦片解决的,因为有些瓦片可能在其他瓦片之前解决。

矛投入丛林#

在视频中,玩家 A 向丛林中的玩家 B 的单位投掷他们的矛,第一次尝试未命中,第二次尝试成功。但等一下,如果玩家 A 和合约都不知道单位的确切位置,他们怎么知道矛投掷尝试是否成功命中呢?答案是我们迫使玩家 B 揭示他们是否被击中,使用一个挑战 / 响应过程。

提交矛投掷时,合约可以立即确定哪些(如果有的话)单位被平原上的瓦片击中,并在同一交易中杀死它们。然而,如果任何击中瓦片落在丛林中,那么每个在丛林中的单位都会被放置一个 “待定的挑战”,这意味着该单位不能执行任何动作,直到挑战被清除(由 ActionLib 强制执行)。

为了清除一个单位的待定挑战,拥有玩家有两个有效的选项:

  1. 他们没有被击中,这种情况下他们生成一个显示这一事实的零知识证明(ZK proof),提交给合约,并通过这样做保持他们位置的模糊性。这就是你在第一次尝试中看到的情况。

  2. 他们被击中,这种情况下他们不能生成这样的证明,所以他们公开提交他们的位置给合约,接受击中并丢下他们的战利品。这就是你在第二次尝试中看到的情况。

这就是为什么在视频中,落在丛林中的击中瓦片解决得比平原中的击中瓦片更慢;因为它们必须等待被挑战玩家的响应。

用于选项 1 的 JungleHitAvoid 电路相当直接,第一部分与 JungleMove 电路相匹配:

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);

类似于 JungleMove 中处理地图数据的方式,击中瓦片的 x 和 y 值不是作为公共信号传入,而是作为私有信号,只有一个承诺值作为公共信号传入。对于 JungleMove,只有来自总集的特定地图数据块对电路来说是相关的,所以当块的数量变大时,一个树形承诺是有意义的,但对于挑战瓦片,需要每个集合中的每个瓦片,因为它们都需要被检查,所以无论瓦片的总数是多少,线性承诺都是足够的。

这与 JungleHitAvoid 的第二部分相关,在那里 CoordSetInclusion 电路确定单位提供的位置是否与任何击中瓦片匹配,并检查击中瓦片是否与提交矛投掷时计算的公共承诺匹配(poseidon (x1, poseidon (x2, poseidon (x3, ...))))。

在当前的实现中,如果有任何一个击中瓦片在丛林中,那么每个当前在任何丛林瓦片中的单位都会被放置一个待定的挑战,无论它们离击中瓦片有多近。这显然非常低效,因为许多没有被击中机会的玩家仍然必须回应。可以进行一些优化,例如只在被击中瓦片触及的特定丛林区域的单位上放置待定挑战,或者只在触及其潜在位置的单位上,但我选择了最简单的方法。

惩罚不响应#

当一个待处理的挑战被放置在一个单位上时,除了上述的两个选项外,玩家实际上还有第三个选择,这个选择并没有被合约逻辑直接阻止,但是违反了 “游戏规则”;他们可以选择根本不提交任何响应。

这意味着该单位实际上是被冻结的,这并不直接提供任何好处,但是如果玩家控制多个单位,或者与其他玩家合作,那么通过让对手等待一个永远不会到来的回应来拖延对手的时间可能是有利的。即使这样做没有好处,它仍然是一个简单的方法来使其他玩家感到不快,那么我们如何防止这种行为呢?

让我们回到起点。当进入游戏时,每个玩家都要放下一个押金来玩。如果他们在按规则玩过游戏后离开游戏,那么他们可以取回这个押金。每个待处理的挑战都有一个有限的响应期。如果一个单位收到了待处理的挑战,而拥有单位的玩家在该期间内没有响应,那么他们可以被任何人惩罚(slashing),导致他们的押金被清算,所有的单位被消灭。

在这段视频中,我已经阻止了玩家 B 的客户端响应挑战,这样在向丛林中的单位投掷矛后,等待大约 5 秒的响应时间后,玩家 A 惩罚了玩家 B,导致他们的两个单位都死亡并丢下了他们的战利品。一旦玩家的客户端检测到响应期已经结束而没有提交响应,惩罚就会自动执行,并通过清算合约进行。

请注意,在整个代码库中,我一直将该过程称为 “清算”,只是后来决定 “惩罚” 是一个更合适的术语。还要注意的是,我实际上并没有实现让玩家在进入游戏时下押金的能力,所以惩罚只会杀死玩家的单位而不会拿走所说的押金,但添加这一功能是相当简单的。

泛化惩罚#

尽管长矛的作用是揭示单位的私密位置,但底层的挑战 / 响应 / 惩罚系统可以用来强迫玩家揭示任何类型的私密状态。

更一般地考虑,可惩罚的押金的存在可以用来确保玩家执行世界要求的任何类型的互动。合约和电路逻辑可以用来确定这种互动的确切性质,而零知识证明的使用可以允许在过程中包含私密状态。ZK Hunt 中后续的机制进一步探索了这个想法。

响应期应该调整以匹配生成响应、提交它,并由合约接受所需时间的预期上限,同时要有足够的错误边际来考虑玩家在硬件性能和网络延迟方面的差异。

为了使惩罚的威胁有效,押金应该足够大 / 重要,以至于其损失对玩家来说比不采取行动获得的任何价值更为重要。这种押金可以有不同的形式;代币、游戏内物品、声誉、活了一段时间的角色的经验 / 等级等。

将游戏的部分内容限制在只有一定押金金额的玩家(例如不同的匹配等级、地下城的难度等级等),但允许玩家通过游戏内行动随时间增加他们的押金,是防止因押金的前期成本而在游戏的任何部分限制参与的好方法。

惩罚的威胁应该提供足够的激励以不违反规则,但如果规则无论如何都被打破,那么重要的是要有回退逻辑。如果游戏使用基于 1 对 1 比赛的系统,那么回退逻辑很简单;比赛可以立即结束,并将 “胜利”(及任何其他相关后果)归于没有被惩罚的玩家。

世界完整性#

然而,如果有两个以上的玩家,并且游戏旨在拥有一个更持久的世界(如 ZK Hunt 的情况),那么这种回退逻辑可能会根据世界 / 惩罚上下文的性质变得更加复杂,并且应该被设计为最大限度地保持 “世界完整性”。我认为世界完整性是 “世界行为如何紧密符合玩家期望的度量标准,同时考虑到由其设计产生的一整套后果”。

例如,在 ZK Hunt 中,期望 “如果丛林中的一个单位被矛击中,那么它应该死亡并掉落战利品” 即使发生惩罚也会得到强烈的保持。相反,期望 “如果丛林中的一个单位被矛击中,那么它应该在大约 x 秒内死亡”(其中 x 是玩家响应被击中和后果传播给所有其他玩家所需时间的合理上限)没有得到强烈的保持,因为可能发生不响应,这导致在惩罚发生之前的等待期超过了 x。

同样,期望 “如果一个单位在丛林中被杀死,那么它的战利品应该在与单位相同的瓦片中掉落” 也没有得到强烈的保持。如果一个玩家因为没有回应挑战而被惩罚,那么合约不知道他们的单位在丛林中的确切位置,它能做的最好的就是将战利品放在单位的最后已知位置(丛林入口瓦片)。从另一个确实知道单位位置的玩家(通过后面讨论的方式获得)的角度来看,这可能看起来像是战利品在瞬移。

你可以尝试改善这个情况,比如改为在与单位可能位置相交的被击中的瓦片之一中掉落战利品,这基于这样的概念:如果玩家没有响应,那么他们最有可能被长矛击中。尽管这仍然允许瞬移,但这种瞬移的可能幅度被最小化了。然而,这种方法导致了更复杂的实现,并且不处理没有一个被击中的瓦片与单位的任何可能位置匹配的情况,这就是我选择更简单方法的原因。

为了从惩罚中获得便利,你可能不得不牺牲一定程度的世界完整性。上面的两个 ZK Hunt 示例强调了惩罚的两个重要考虑因素:时间敏感性和私有状态回退。

惩罚曲线#

在上述挑战 / 应对系统中,如果玩家未能及时回应,他们的押金将会被罚没。一个策略性的恶意行为者会等到回应期快结束时才作出回应,这样既可以避免被罚没押金,同时还能延误等待回应的其他玩家。

将玩家损失的金额与他们在回应前等待的时间作图,图表如下:

0kdryI8

显然,我们想要通过惩罚来阻止这种拖延行为,因此我们可以在玩家回应时罚没他们押金的一部分,而不仅仅是在一个严格的截止时间之后才罚没玩家的全部押金,罚没的比例由他们等待的时间长短来决定:

Ptf7vI2

在末端依然有一个严格的截止点;如果他们在这个时间点之前回应,他们的押金会被罚没一部分,但他们还能继续参与游戏,而如果他们在截止时间之后回应 / 根本不回应,那么他们的全部押金会被罚没,并且他们将被移除游戏。

这样做最低程度地惩罚了及时回应的玩家,同时大幅惩罚了试图延迟回应的玩家。一个恶意行为者可能会量化他们通过延迟回应时间 t 所获得的价值,然后找到曲线上的一个点,在这一点上,该价值减去罚没的金额达到最大。

可以调整曲线,以影响这类行为者的反应,甚至可以有一种自我调节的曲线,根据玩家平均回应时间的长短不断进行调整。

信息披露的程度#

投矛是一种与位置不明的单位互动的方法,也是迫使他们揭示位置的一种方式,但可以进行更改,以限制实际披露的信息量。当丛林中的一个单位被投矛击中并死亡时,揭示其位置是有意义的,因为合约需要知道在哪里掉落战利品。然而,如果每个单位都有一定的 HP,并且需要多于一次的投矛击中才能杀死,那么情况就不再一定如此。

如果一个单位被击中但没有死亡,那么你可以只强迫拥有玩家揭示它被击中的事实,以便合约可以减少其健康值,而无需揭示其确切位置(使用零知识证明)。这实际上将单位可能的位置减少到了它可能被击中的瓦片集合。

如果单位有私密的健康状况,那么你可以更进一步;被挑战的玩家通过提交一个新的健康承诺来回应,如果他们被击中,承诺会减少健康值,如果他们没有被击中,健康值保持不变(通过零知识证明强制执行)。这意味着其他玩家只看到单位健康承诺的更新,因此不知道单位是否被击中,从而保持了单位的完全位置模糊性。

你甚至可以同时存在所有三种信息披露程度,并根据单位拥有的某些属性或物品来确定使用哪一种。

丛林中的行动#

接着第一段投矛视频的内容,我们将看到你也可以在丛林中进行操作。

在丛林中杀死 B 玩家的单位后,A 玩家捡起了掉落的战利品。请注意,这样做迫使 A 玩家揭示他们单位的位置,以便合约能够确保他们确实处于正确的位置来拾取战利品,但之后他们能够立即重新隐入丛林,并重新获得位置的模糊性。从丛林中投掷矛的行为也是一样,单位的位置必须向合约揭示,以便它可以确定应该是哪一组被击中的瓦片。

正如你之前看到的,当退出丛林时,玩家揭示单位的位置和随机数,合约检查这些值的波塞冬哈希是否与存储的位置承诺相匹配。在丛林中进行操作与此过程不同,它只揭示位置,并使用一个零知识证明来表明它与承诺相匹配。这意味着随机数可以保持私密,因此丛林中的移动可以从相同的承诺继续,而不是必须建立一个带有新随机数的新承诺。

这个证明重复使用了 PositionCommitment 电路(进入丛林时使用的相同电路),并且在丛林中捡起战利品和投掷矛的合约都委托给一个处理以这种方式揭示单位位置的逻辑的单一合约。

如前所述,投矛属于公开玩家发现的范畴,但我们能做得更好吗?我们能实现私人玩家发现吗?

— 搜索 —#

为此,我们有了搜索能力。虽然它使用与投矛相同的线性挑战瓦片构造,但搜索不是一种战斗能力,而是一种信息收集能力。

这里我们看到玩家 A 搜索玩家 B,但没有成功,什么也没了解到。他们再次尝试,搜索定位到玩家 B,他们的位置就被揭露了。这与你刚才看到的投矛是同样的情况(不包括死亡),但在这种情况下,只有玩家 A 得知了玩家 B 的位置,玩家 C 并不知道,这一点通过玩家 C 的视角下持续存在的模糊性指标得以体现。事实上,玩家 C 不仅没有得知该单位的位置,他甚至不知道玩家 A 的搜索是否成功。这实现了私人玩家发现。

当玩家 B 的单位(被玩家 A 找到后)在丛林中进行额外的移动时,从玩家 C 的视角来看,位置的模糊性会如预期的那样继续增长,但玩家 A 会保持对其位置的精确了解。这允许玩家 A 有效地随时间追踪玩家 B 的单位,这种追踪行为将持续,直到单位退出并重新进入丛林,在这一点上,该单位可以重新获得相对于玩家 A 的位置模糊性。

搜索如何工作?#

与投矛相似,玩家 A 向合约提交搜索方向,合约确定结果挑战瓦片并在丛林中对玩家 B 的单位发起待决挑战。当玩家 B 看到这个待决挑战时,他们不是直接向合约提交他们的位置(如果成功的话),而是将他们的位置承诺随机数加密(有效地揭露他们的位置,稍后会详细说明),以便只有玩家 A 能够解密,然后提交密文以及证明加密操作正确的证明。

这解释了玩家 A 如何能够私下了解玩家 B 的位置,但玩家 C 是如何被阻止至少找出玩家 A 的搜索是否成功的呢?他们肯定可以观察玩家 B 的回应,如果他们提交了密文,这意味着他们正在发送他们加密的随机数,也就是说玩家 A 搜索成功,对吧?

不,因为无论玩家 B 是否在搜索中被抓获,他们都会提交一个密文和相关的证明,但这个密文只有在他们在搜索中被抓获时才包含他们的随机数,否则将包含一个无意义的值。这意味着,尽管玩家 A 的搜索可能成功或失败,但作为外部观察员的玩家 C 无法分辨差异。

w98STOb

夜市#

我对惩罚的思考从用矛解决非响应问题的方式变为允许更一般的 “强制互动”,这一机制的出现是这种思考的结果。如果,在有可惩罚的存款和合约 / 电路逻辑的情况下,你可以强迫玩家以特定的方式响应挑战,那么为什么不只是强迫他们用加密的方式响应他们的位置(或位置承诺随机数),这样只有挑战者才能解密它呢?

你必须验证加密在电路内部是正确完成的,所以下一个问题就变成了哪些加密方法对 SNARK(零知识证明)是友好的?我简单查了一下,意识到这个问题已经由 Dark Forest Nightmarket 插件解决了。

Nightmarket 插件是一种在 Dark Forest 中私密且可验证地出售行星坐标的方式。玩家可以发布列表,出售他们发现的行星的坐标,买家可以通过向托管合约存入一些以太坊来提出报价,卖家可以通过使用对称加密私下向买家揭露坐标来接受报价,并提取存款。

使用零知识证明来确保坐标实际上包含一个行星,并且加密是正确完成的,尽管完整的过程比这里描述的要复杂一些,所以你可以在上面链接的博客文章中了解更多。我最终重用了 Nightmarket 的一些共享密钥派生和波塞冬密码电路,而它本身已经对 maci 和 Koh Wei Jei 的这个 circomlib pr 中的一些电路进行了更改。

尽管 Nightmarket 和 ZK Hunt 中的搜索都涉及私下分发信息,但两者之间有一个有趣的区别是 Nightmarket 中的销售是自愿互动;一旦制作了列表,买家选择提出报价,卖家选择是否接受,而搜索是非自愿的互动;一旦对玩家提出挑战,如果他们没有正确响应,他们就会被惩罚。

搜索实现#

对于搜索(以及夜市),Poseidon 密码被用作对称加密方案,因为它比传统的非对称加密方案更适合于 snark,可能的原因与 Poseidon 哈希比传统哈希函数更适合于 snark 的原因类似(它们共享了部分电路实现的一些部分)。

两个玩家之间的共享密钥是通过一个 “离线” ECDH 密钥交换来建立的。实际上,这意味着当所有玩家进入游戏时,他们都会建立一个私钥 / 公钥对,并将他们的公钥提交给合约。有了你的私钥和另一个玩家的公钥,你可以在没有与他们直接互动的情况下(因此是‘离线’的)推导出一个用于加密的共享密钥,他们也可以用他们的私钥和你的公钥做同样的事情,从而得到相同的共享密钥。

每个玩家都会为每个其他玩家做这件事,最终得到独特的(和私有的)共享密钥,他们可以用它们与任何其他玩家通信。在搜索响应期间,证明中强制使用正确的共享密钥以验证加密是否正确完成。

SearchResponse 电路有点密集,所以我不会直接在这里粘贴它,但本质上它:

  • 检查响应单位的(x,y)和私下提供给电路的位置承诺 nonce 是否与公共位置承诺相匹配。
  • 从响应玩家的私钥和搜索玩家的公钥中派生共享密钥,同时检查响应玩家的私钥是否与其公钥相匹配。
  • 通过检查私有位置是否与公开提供的挑战瓦片中的任何一个相匹配来确定单位是否被找到。这个结果存储在一个名为 wasFound 的信号中。
  • 检查公开提供的密文是否是 secretNonce 的正确加密,并且是用先前派生的共享密钥加密的。
  • 最后,检查 wasFound 是 false,还是 secretNonce 与位置承诺 nonce 相匹配。
    总而言之,如果单位被找到,那么电路确保他们已经加密了他们的位置承诺 nonce,但如果他们没有被找到,那么电路允许他们加密任何事情,实际上没有透露任何信息。

nonce 的力量#

那么,如果搜索响应加密的是单位的位置承诺 nonce,而不是位置本身,这如何仍然导致位置被挑战者知晓呢?

嗯,挑战者可以查看单位的潜在位置集,计算他们现在知道的承诺 nonce 对应每个位置的位置承诺是什么,看看这些承诺中的哪一个与链上存储的该单位的承诺相匹配,从而找到相应的位置。

qBdAO6R

揭示 nonce 实际上将承诺转换回了 DF 类型,不同的是在这种情况下,因为潜在位置的数量很小,所以暴力破解承诺非常容易。

最初,我决定加密 nonce 而不是位置,因为这意味着加密单一值而不是两个值(x,y),并且仍然会导致位置被挑战者知晓。从那时起,我意识到通过加密 nonce 产生了一个更重要的好处,或者更确切地说,是一个权宜之计。

当从丛林中投掷矛、在丛林中捡拾战利品(以及在丛林中被矛击中,如果它没有杀死你的话),单位会揭示其位置,但随后可以通过后续移动立即消失在丛林中。然而,被搜索发现将允许挑战者确定单位在丛林中所有后续移动的确切位置,从而产生你在视频后半部分看到的跟踪行为。

这是由于 JungleMove 的实现细节,它强制新位置承诺中使用的 nonce 是旧位置承诺中使用的 nonce + 1(一个类似的早期做出的任意决定),因此,知道当前位置承诺 nonce 允许你确定所有未来的 nonce(以及所有以前的 nonce),从而了解相应的位置。

一旦单位离开并重新进入丛林,这种效果就会重置,因为你可以选择一个新的随机 nonce 用于初始入口位置承诺。当然,如果你不希望有这种跟踪行为,那么你可以允许每个新位置承诺的 nonce 完全随机,与以前的 nonce 没有关系。

或者,你也可以使跟踪持续一定数量的移动 / 一定时间,而不是直到重新进入丛林。这将需要建立电路参考的计时器 / 移动计数器,该计数器只在满足持续时间条件后才允许选择新位置承诺的随机 nonce,并且还需要在重新进入丛林时强制重新使用 nonce,如果条件尚未满足的话。

当然,这种跟踪行为可以扩展到使用这种承诺方案的任何类型的私有状态;你可以跟踪玩家的私人健康状况如何随时间变化,他们拥有多少资源等等。

加密的另一种选择#

我最近意识到有一种更简单、更高效的方法可以实现对范围足够小的值进行 snark 友好加密。

承诺 nonce 不属于此类,因为它应该从大范围中选取,以防止承诺被暴力破解,但单位的位置确实属于此类,因为 x 和 y 都在范围 [0,mapSize - 1] 内,并且 mapSize 足够小。这意味着,如果你放弃通过加密承诺 nonce 获得的跟踪行为的额外便利性,那么你可以使用这种方法直接加密单位的位置。

总体方法如下:建立一个共享密钥 k(你可以再次使用 ECDH),然后对于来自足够小范围 r 的给定消息值 m,密文 C 只是 poseidon (m, k)。玩家 A 将 C 连同证明 C 是从正确的 r 和 m 生成的证明一起提交给合约。玩家 B 检索 C,并知道 k 在本地计算 C'= poseidon (m', k) 用于范围 r 内的 m' 的每个可能值,直到他们找到一个与 C 匹配的 C' 值,这表明加密值 m 等于相应的 m'。

你会注意到,这个解密过程几乎与上面描述的过程相同,用于从揭示的 nonce 和他们的承诺中确定单位的位置,在这里 nonce 代表密钥,承诺代表密文。

这里,“足够小的范围” 的定义实际上只取决于你为了找到匹配而愿意在本地计算的最大哈希数,这实际上可以是相当大的,因为可以相当便宜地计算许多哈希。只要范围的乘积(r_1 * r_2 * ... * r_n)足够小,这种方法就可以扩展到加密任意大的一组值 m_1、m_2、...、m_n,来自范围 r_1、r_2、...、r_n。

正如前面提到的,增加你在电路内输入到 poseidon 哈希的输入数量会增加约束的数量,并且单个 poseidon 哈希最多只能接受 16 个输入,但你可以通过执行 m = m_1 + m_2 * r_1 + m_3 * r_1 * r_2 + ... 来将值集强制转换为单个值,其中每个消息值只是乘以它之前的值的范围的乘积,然后求和以获得唯一代表该集合的单个值。

与需要大约 800 个电路约束和 4 个 uint256 来表示密文的 poseidon 密码(密文大小是消息大小四舍五入到最接近的 3 的倍数,+ 1)相比,只使用 poseidon 哈希只需要大约 240 个约束和一个 uint256 来表示密文。

要替换搜索响应中使用的加密,密文将只是 poseidon (x,y,k),或者 poseidon (x + y * mapSize,k)。当然,加密 nonce 提供的永久跟踪功能非常酷,所以你可能会坚持在这里使用 poseidon 密码以保留该功能,但是这种哈希加密方法可能会在其他场景中找到更多的用途。

在丛林中进行搜索#

搜索也可以在丛林内进行(即 “隐蔽搜索”),这带来了新的功能,并增加了更多的加密复杂性。

在这里,玩家 A 和玩家 B 都进入了丛林,这意味着玩家 C 不知道他们中的任何一个在哪里。同样,玩家 A 搜索玩家 B,在这种情况下第一次尝试就成功了。就像在丛林外搜索一样,玩家 B 的位置被透露给玩家 A,但没有被透露给玩家 C。

然而,与在丛林中执行其他动作(如投掷矛或拾取战利品)不同,玩家 A 的位置不会被游戏中的其他人知晓,而只会被他们正在搜索的玩家知道。这可以在视频中看到,因为搜索完成后,玩家 C 对玩家 A 和玩家 B 的位置仍然一无所知。

隐蔽搜索的另一个方面,视频中没有显示的是,玩家 C 甚至不能确切地知道发生了什么样的通信。

不同于之前的机制,其中一个待处理的挑战被放置在一个特定的单位上,然后该单位回应那个挑战,隐蔽搜索的挑战并没有明确指定它已经被放置在哪个单位上,回应也没有指定是对哪个挑战进行的回应。这意味着玩家 C 知道玩家 A 进行了搜索,玩家 B 提交了一个回应,但他们实际上无法确定两者之间是否有明确的联系。

显然,他们可以由于挑战和回应的时间接近而推断出存在联系,但如果在短时间内有许多挑战和回应,那么他们将无法确切地知道哪个搜索对应哪个回应。

如果考虑到完全的泛化,这实际上允许两个玩家进行互动,而不向任何其他人透露他们的私密状态,甚至他们进行了互动的事实也不会被确切地透露。这从私密玩家发现转变为私密玩家互动。

私密挑战是如何工作的?#

这个机制的出现是从丛林外的搜索自然进化而来的;如果你可以加密对搜索的回应,以保持被发现单位的位置对其他玩家的隐私,那为什么不也加密挑战,以保持挑战单位的位置的隐私呢?这在叙事上也有所进展;相对于玩家发现,搜索是矛的 “更隐蔽” 的版本,因此从丛林中进行的搜索应该比从丛林中投掷矛更隐蔽。

从丛林中投掷矛时,单位必须向合约透露其位置,以便它可以根据该位置和提供的投掷方向确定正确的挑战瓦片集。你可以改为向合约提供挑战瓦片集,并提供一个零知识证明,证明挑战瓦片相对于私密位置是有效的,而不透露它,但这是行不通的。

5qQ8Enn

一系列挑战瓦片实际上是一支箭,它指向挑战的起源,对于每个方向的挑战瓦片排列,只能有一个独特的可能起源。这意味着知道单位提交的挑战瓦片允许你确定它的位置,因此挑战瓦片也必须对所有玩家(除了被挑战的人)保密。

这就是为什么我们必须 “加密挑战”。在实践中,这意味着加密挑战瓦片,以便只有被挑战的玩家能够解密它们,并将密文提交给合约,而不是直接提交挑战瓦片。挑战的加密是用同一个共享密钥进行的,该密钥用于加密对挑战的回应,正确的加密同样由随附的零知识证明来强制执行。

挑战瓦片的正确排列的确定也是在电路内部完成的,而不是由合约完成的,但它本质上执行相同的逻辑,即根据投掷方向索引从所有可能的偏移排列的查找表中选择瓦片偏移的排列,然后将它们加到单位的位置上,以获得挑战瓦片的位置。

知道挑战瓦片就能揭示单位位置的事实,是为什么在视频中你看到玩家 B 在收到玩家 A 的挑战时也发现了玩家 A,即使玩家 A 在搜索中没有成功。因此,隐蔽搜索只达到了对称玩家发现的水平,因为为了发现一个玩家,他们必然也会发现你。

技术上,你可以通过允许挑战瓦片脱离挑战者的位置(例如,创建一个在单位一定距离处的挑战瓦片的圆形区域)来达到非对称玩家发现的第一层级,这样知道挑战瓦片并不会揭露挑战者的位置。然而,对于 “真正” 的非对称玩家发现,即使挑战瓦片直接与挑战者相关联,它也应该有效。这将在后续项目中进一步探索。

私密互动是如何工作的?#

隐蔽搜索的第二个新颖方面来自于探索两个玩家如何能够私下互动的可能性。第一步是通过加密挑战和回应来处理的,但下一步是阻止所有其他玩家确定有关两个玩家之间的联系。如上所述,这是通过允许挑战不明确指定哪个单位受到挑战,而响应不明确指定响应的是哪个挑战来实现的。

如果情况确实如此,那么我们如何确保挑战总是正确地得到回应呢?这里的问题是我们希望挑战者能够在被挑战者不回应时对其进行惩罚,但同时也想确保如果他们确实回应了,挑战者就不能惩罚他们,即使他们没有向合约透露响应对应的是哪个挑战。

在考虑这个问题时,我问道:“有没有其他系统的例子,可以让两个‘不同’的实体健壮地互动,而不会公开揭露它们之间的联系?” 答案是 Tornado Cash。Tornado Cash 如何确保这些实体之间互动的完整性呢?答案是使用空值器(当然还有零知识证明)。

当被挑战者提交他们的回应时,他们也提交了一个从挑战中得出的空值器,但并没有公开揭露它是从哪个挑战中得出的。提交这个空值器表明被挑战者已经对挑战做出了回应。如果他们在回应期结束时还没有提交这个空值器,那么挑战者可以惩罚他们。

在 Tornado Cash 的情况下,空值器被用来阻止接收实体多次执行它们交互的那一侧(防止存款的双重支付),而对于隐蔽搜索,空值器被用来确保回应实体至少执行一次它们交互的那一侧(防止挑战被忽视)。

同样,与 Tornado Cash 类似,这个系统只有在有足够大的匿名集合时才真正有效;在隐蔽搜索的情况下,这基于并发搜索和回应的数量。

在实践中使用空值器#

当提交挑战时,会生成一个与挑战唯一对应的隐式空值器。这个空值器不会由挑战者发布,但可以从挑战的内容中推导出来,这样接收者就可以计算出相同的空值器。它的形式是:

poseidon(challengeTilesCommitment, challengedEntity, sharedKey[0], nullifierNonce)

其中:

  1. challengeTilesCommitment 是对挑战瓦片的承诺(用于矛避开回应和正常搜索回应的相同承诺结构)。这将挑战绑定到一组特定的瓦片。

  2. challengedEntity 是被挑战单位的实体 ID,其中 uint256 ID 与 2^253 - 1 进行位掩码处理,以便它能适应单一信号。这将挑战绑定到一个特定的单位。挑战者可以通过使用一个实际上并不属于被挑战玩家的单位的实体 ID 来创建一个无法回应的挑战,但这样做将阻止他们提交有效的惩罚证明。

  3. sharedKey [0] 是共享密钥的第一部分。这将挑战绑定到一个特定的将用于加密挑战和响应的共享密钥。

  4. nullifierNonce 是为此挑战生成的随机值。这确保了对相同实体的多个挑战,具有相同的挑战瓦片集,将使用相同的共享密钥,仍然会产生唯一的空值器。

challengedEntity 和 nullifierNonce 需要包含在挑战中,以允许接收者推导出正确的空值器,因此这些值会与挑战瓦片一起加密到密文中。这个密文,连同证明其有效性的 ZK 证明,都作为挑战提交给合约。

由于挑战单位没有公开指定,所有玩家都必须监听来自丛林内的所有新提交的搜索,尝试使用与挑战玩家对应的共享密钥解密密文,如果他们能够解密它,那么他们就知道挑战是针对他们的。

一旦正确的接收者解密了挑战,他们就会以与从丛林外部执行搜索时几乎相同的方式构建响应,只是现在证明不再公开引用挑战 / 密文。挑战的内容完全作为私有输入提供,证明根据这些私有提供的值公开输出上述空值器。

当响应提交给合约时,相应的空值器被保存到玩家的固定长度空值器队列中,该队列记录了他们最后 N 个响应的空值器。较旧的空值器将会丢失,但这是可以的,因为空值器只在挑战期结束之前相关,之后挑战者即使空值器不再存在也无法惩罚它们。队列的大小应足够大,以处理单个单位上预期的 “大致同时发生” 的挑战的最大数量。在 ZK Hunt 中,这个大小设置为 10。

诈骗尝试#

因为挑战的内容作为私有值被输入到响应证明中,所以被挑战的玩家在技术上可以创建并提交一个内部引用完全不同的挑战瓦片(或他们的不同单位,或使用不同的共享密钥等)的证明,以避免成功的挑战,而这仍然会被合约接受。然而,这样做将导致证明输出错误的空值器(nullifier)。

玩家可以提交任何任意的响应,但只有结果在正确的空值器的响应才会阻止他们被挑战者惩罚。这就是为什么空值器必须编码上述的一组值,而不仅仅是挑战的唯一标识符。空值器实际上是将响应锚定到挑战的唯一公共值,因此它必须限制被挑战的玩家以正确的方式做出反应。

然而,受挑战的玩家还有另一种方式可以尝试规避系统。在搜寻丛林外部和投矛地点对单位提出挑战并阻止他们做任何事情,直到对挑战做出回应时,隐藏搜索并不这样做。这意味着玩家可能收到一个隐藏的挑战,看到他们在挑战瓦片内,移动到它们之外,然后才回应挑战,避免被发现。

在 ZK Hunt 的当前实现中,合约会允许这种情况,挑战者将无法惩罚被挑战的玩家。这里的问题是系统允许玩家提交关于他们当前位置的响应,而不是他们在提交挑战时所处的位置。为了解决这个问题,你需要记录玩家过去的位置,证明可以参考。

玩家历史#

目前,一个单位的位置承诺采取 poseidon (x, y, nonce) 的形式,玩家可以通过将这个承诺作为一个公开输入来创建引用单位当前位置的证明。如果我们改变公式还包括单位的前一个位置承诺;poseidon (x, y, nonce, prevCommitment),那么证明现在也可以引用单位的前一个位置承诺,从而是他们之前的位置。

引用其之前的位置承诺允许你引用其之前的前一个位置承诺,依此类推。这创建了一系列的承诺,证明可以引用单位的任何前一个位置,只给出他们当前的位置承诺作为一个公开输入。

我们可以利用这个事实来解决上述隐藏搜索的问题。响应证明不是检查被挑战单位的当前位置是否在挑战瓦片内,而是检查它们的最后 N 个位置中的任何一个是否在挑战瓦片内。这意味着即使玩家受到挑战,在移出挑战瓦片外后再做出响应,他们仍然会被发现。

然而,这是一个不完整的修复,因为它允许挑战成功,如果它击中单位的任何以前的位置,即使他们在提交挑战时并不在那个位置。承诺链给予证明访问玩家的历史,但我们还需要它包括时间性的概念,这样证明可以考虑事件的相对时间。

改进的玩家历史记录#

更新这个方案很简单;承诺变成了 poseidon (x, y, nonce, timestamp, prevCommitment),导致每个单位的移动都绑定到一个特定的时间点。对于 ZK Hunt,时间戳将是单位移动所在区块的 EVM block.timestamp,但对于其他类型的游戏,它可以是其他一些依赖时间的值,例如基于回合的游戏的回合索引。

挑战也会有一个提交时间戳与之相关联,现在响应证明将遍历单位的位置承诺历史,找到它在提交挑战时所处的位置,并检查该位置是否包含在挑战瓦片内。挑战时间戳也必须包含在挑战空值器中,以便被挑战的玩家被限制在他们的响应证明中使用正确的时间戳进行比较。

虽然我将这些添加描述为解决隐藏搜索问题的一种方法,但能够在证明中引用单位的位置历史记录可以有许多其他的应用。例如,你可以有跟踪信息披露,意味着每次一个单位在丛林中移动时,它也必须揭示它 N 次移动前的位置,这样在丛林中可以达到的最大位置模糊性就会受到限制。你也可以允许搜索发现单位足迹(过去的位置),而不仅仅是它的当前位置。

对于不同类型的游戏,可能还有更多的应用,特别是当你存储除了位置之外的其他类型的私有状态的历史(库存,玩家行动,交易等)时。

当然,如果你要对 ZK Hunt 的承诺结构进行这些更改,仍然存在被挑战玩家能够在必须回应之前执行一些行动的问题,因为缺少一个挂起的挑战条目来阻止他们这样做。知道他们将被找到,他们可以更好地定位自己,或者甚至直接攻击挑战者,因为他们在收到挑战后会立即找到挑战者的位置。

如果你允许被挑战的玩家在回应隐藏挑战之前进行任何行动都会被惩罚,这可以得到缓解,但那么你就进入了关于他们在被惩罚之前对世界产生了任何影响该怎么办的灰色地带(回滚?),以及提交比赛条件(玩家提交他们认为是有效的举动,但链先接受了对他们的挑战)。总的来说,这显然是一个不完美的系统,但这里有一些有趣的便利条件。

隐藏搜索电路#

再次说明,这个过程的电路有点复杂,所以我不会发布代码,而是高层次地总结它们的功能:

由挑战者使用,HiddenSearch 电路执行以下操作:

  • 检查私下提供的位置是否与公开提供的承诺相匹配。

  • 基于位置和私下提供的挑战方向,计算挑战瓦片的集合。

  • 从被挑战玩家的公钥和挑战者的私钥中导出共享密钥,并检查挑战者的私钥是否与其公钥匹配。

  • 检查公开提供的密文是否是使用前述共享密钥对挑战瓦片、被挑战实体 ID 和空值器随机数的正确加密。
    然后,由被挑战玩家使用,与 SearchResponse 非常相似,HiddenSearchResponse 电路执行以下操作:

  • 检查私下提供的位置是否与公开提供的承诺相匹配。

  • 从挑战者的公钥和被挑战玩家的私钥中导出共享密钥,并检查被挑战玩家的私钥是否与其公钥匹配。

  • 通过检查其位置是否与任何私下提供的挑战瓦片相匹配,来确定单位是否被找到。这个结果存储在一个名为 wasFound 的信号中。

  • 检查公开提供的密文是否是 secretNonce 的正确加密,并且是使用先前导出的共享密钥加密的。

  • 检查 wasFound 是否为假,或者 secretNonce 是否与位置承诺随机数相匹配。

  • 计算并输出上述的空值器。
    如果被挑战的玩家没有提交一个有效的响应来产生正确的空值器,那么由挑战者使用,HiddenSearchLiquidation 电路执行以下操作:

  • 从被挑战玩家的公钥和挑战者的私钥中导出共享密钥,并检查挑战者的私钥是否与其公钥匹配。

  • 检查公开提供的挑战密文是否是私下提供的挑战瓦片、被挑战实体 ID 和空值器随机数的正确加密。

  • 计算将由相关挑战产生的空值器。

  • 检查所述空值器是否不是被挑战玩家的空值器队列的一部分。

更多的隐私#

当挑战者因为被挑战者没有回应而惩罚他们时,尽管这并不暴露挑战者的位置,但它确实透露了他们对被挑战者提交了搜索,这可能泄露了一些关于他们接近度的信息。这是少量的信息,并且由于挑战最初发生和惩罚发生之间的间隔,它甚至可能已经过时,但尽可能少泄露信息可能是有益的。

你可以通过让惩罚证明公开引用所有提交挑战的链上 merkle 累加器,而不是特定挑战,并从与挑战者地址不同的地址提交惩罚交易,从而防止这种泄露,这样就没有引用到原始挑战者。在隐藏搜索的情况下,这不是非常有价值,但是显示这种私密互动的一般化可以保持最大程度的匿名。

全面概括#

现在,让我们拉远视角,从更一般的角度来看看所有这些机制。我们可以这样分类它们:

  • 矛:公开挑战和公开回应

  • 在丛林外搜索:公开挑战和私密回应

  • 在丛林内搜索:私密挑战和私密回应
    或者以另一种方式来描述这些机制,就是它们如何与私有状态进行交互:

  • 矛:公开读取

  • 在丛林外搜索:私密读取

  • 在丛林内搜索:带有私密参数的私密读取(其中参数是读取的性质以及被读取的私有状态)
    这些机制允许不同类别的读取,但用于实现它们的技术也可以很容易地用于写入私有状态。你可以想象公开对另一个单位造成伤害,导致它们的私有健康量减少(公开写入),从玩家的私有库存中私密地偷取物品(私有写入),或者与另一位玩家进行私密交易,而不向任何其他人透露交易的性质或交易的参与者(带有私密参数的私有写入)。

零知识证明、公开承诺、可验证加密和空值器的结合为我们提供了从玩家的私有状态中读取和写入以及智能合约逻辑的方法,并且链上证明验证以及要求玩家提交可被惩罚的存款,使我们能够确保所述流程正确执行。

对此后果的一种思考方式是,它扩展了对玩家私有状态的合约控制 / 所有权,或者相反,将玩家变成了一种 “部分智能合约” 的实体,某种程度上的赛博格。玩家仍然可以对他们的行动和私有状态施加影响,但现在有一种方式可以让其他玩家 “无需许可地” 与该私有状态进行交互。

如果你进一步采取行动并消除代理权,那么你得到的基本上是一个拥有私有状态的智能合约,它可以通过挑战 / 响应异步地进行读取和写入。这实际上允许 “无主” 的私有状态 / 由世界拥有的私有状态的存在,这对于 NPC 和世界发现有重要的影响。

拥有私有状态的 NPC#

注意:在这里必须给 Justin 一些信誉,因为下一节中的许多想法都是在与他们进行的一次对话中产生的。

最简单的情况下,NPC 会有一些私有状态(也许还有一些公开状态)、一个确定性行为模型,以及一些用于驱动行为模型的私有随机种子,使得它对观察者来说看起来是非确定性的。一个用户或 “操纵者” 将存储私有状态和随机种子,为 NPC 提交链上行动,按照行为模型执行,并内部更新私有状态和随机种子。

这样的 NPC 的一个例子是一个在不同城镇之间旅行的商人,为玩家提供买卖物品的机会。商人的当前位置是保密的,但玩家可以进行搜索,看看商人是否和他们在同一个镇上,如果成功,可以与他交易。商人按照固定的时间表在镇子之间移动,但他移动到哪个镇子是由私有随机种子决定的,所以玩家将不断失去对商人的跟踪,并且不得不搜索其他镇子以再次找到他。

操纵者对商人没有任何控制权,他们只是遵循预定义的逻辑,选择初始位置和私有种子的过程也可以设计为防止操纵者对这些有任何不当影响。当然,承担这个角色将要求操纵者放下一个可被惩罚的存款,以便有足够的动机防止他们简单地停止履行职责。

如果操纵者必须锁定存款,而且他们对商人没有任何控制权,也不会从他们的游戏行为中获益,那么他们成为操纵者的动机是什么呢?好吧,你可以为操纵者设置一种类似于抵押奖励的东西,他们在提供操纵服务的同时获得支付。他们不是 “流动性提供者”,更像是 “隐私提供者”。

在操纵者被惩罚的情况下,你还需要一个恢复系统。这看起来像是角色再次被开放,别人接管这个角色,启动一些新的私有随机性,然后继续商人的行为。为了帮助保持世界的完整性,你会希望商人从同一个城镇继续,所以可以为任何能够证明他们知道商人上次在哪个城镇的玩家提供一个限时奖励,否则商人将从一个新的随机城镇继续。

对于长期运行的 NPC,你会希望有一个系统,让操纵者可以合法地辞去他们的职务,结果是他们收回他们的存款 + 累积的抵押奖励,并且机会再次开放,以便其他操纵者可以接管角色。你可以将这个想法扩展到构建一种 “工作板” 的概念,其中有不同的 NPC 角色列表,不同的操纵者可以来接管,执行一段时间,然后放弃让别人接管。

私人世界探索#

对于无主私有状态的另一个重要用例,我认为是世界探索。一个 “世界管理员” 可以私下保存整个世界的状态,或者对于一个程序生成的世界,可以私下保存随机选择的 “世界种子”,当玩家前往世界的新区域时,他们可以向管理员查询那部分世界的内容。查询和响应都将被加密,这样玩家就可以保持他们位置的隐私,而且只有他们知道那部分世界的内容。

这可以被认为实际上是回到了关于世界探索的 “传统游戏服务器” 模型,除了它更健壮,因为有一个预定义的世界模型,管理员无法对其撒谎或操纵,以及他们继续回答世界探索查询的重大激励,在形式上他们必须放下的可减少的存款。也就是说,由于惩罚的后果,这并不是一个适合链上私人世界探索的正确解决方案。

正如上面所描述的,从玩家因未回应标枪投掷而被惩罚,或从木偶师因背叛他们的 NPC 职责而被惩罚中,有可能相当优雅地恢复,由于惩罚对世界的影响相对局部化,以及 “修复” 状态以最大程度保持世界完整性的能力(战利品仍然被丢弃,新的商人被创建,等等)。但是,如果世界管理员背叛并被惩罚,那么世界实际上就丢失了,恢复的唯一方法是创建一个新的。

如果目标是构建一个强大的世界,那么这显然是不可行的。这表明,在使用这种无主私有状态的方法时,必须认真考虑完整的后果。即便如此,这种方法实际上还有一个更深层次的问题。

勾结#

这里的真正问题是勾结。' 守护者 '(用于木偶师 / 世界管理员的更通用术语)拥有对玩家有价值的私有状态 / 信息,因此他们可以将这些信息出售给玩家,以获得除他们的质押奖励之外的额外价值。显然,我们不希望这种事情发生;玩家之间的勾结是可以接受的(甚至可能是预期的,基于游戏的类型),但玩家和守护者之间的勾结是不行的。

因此,我们需要一个抑制守护者分享其私有状态的不利因素,这比他们通过将其卖给玩家所能获得的利益更为重要。这可能采取的形式是,如果玩家可以证明他们在不应该的情况下获得了私有状态的访问权限,他们就能惩罚守护者,并因此获得奖励。这将防止守护者因为害怕被他们惩罚而与玩家勾结。

不幸的是,这种方法有几个问题。首先是我们可能想要在游戏中为玩家提供合法发现私有状态的方式(例如,找到商人的位置),所以你需要阻止这样的玩家惩罚守护者,但即使你实现了这样的逻辑,发现玩家也可以将私有状态给另一个玩家,证明他们无法合法获得状态访问权限,而那个玩家可以代替惩罚守护者。

另一个问题是购买私有状态的玩家可以创建自己的智能合约,他们在其中存入与守护者相同大小的存款,该合约包含允许守护者在玩家惩罚守护者时从玩家那里取得存款的逻辑,从而有效地消除了守护者的惩罚风险,并允许勾结自由发生。当然,这将需要玩家拥有足够的资本来匹配守护者的存款金额,使这种方法对大多数人来说不那么容易接近,但核心缺陷依然存在。

迄今为止,与这种无主状态方法相关的所有问题的核心,是守护者充当了一个失败 / 腐败的单一点。我认为这里的适当长期解决方案(至少在我们得到适当的 IO 之前)是做一些类似 ZAMA 的事情,在那里,守护者的角色被分配给许多参与者,使用 FHE 和 MPC 确保这些守护者实际上从未直接接触到私有状态,防止他们能够将其卖给玩家。

这样一个系统的阈值性质还将有望使其能够抵抗少数守护者的失败,并且有能力更换这些守护者,可能使其对私人世界探索用例可行,而不会有世界丢失的风险。

— 结论 —#

ZK Hunt 最初是作为一种基于简单的丛林 / 平原移动机制的链上游戏的尝试,但在 AW 驻地项目过程中变得越来越复杂,催生了许多我试图在这里记录的想法和构造。希望 ZK Hunt 的开源代码库和这份技术文档可以作为任何想要构建使用 ZK 和私有状态的链上游戏的人的资源。

至于下一步,我已经在一个新项目上工作了一段时间,它利用了 MPC 和 ZK 的组合,同时建立在 ZK Hunt 探索的想法之上。这应该会很快推出,最终会有它自己的技术写作。

必须向 0xPARC 和 Lattice 表示衷心的感谢,因为他们主办了 AW 驻地项目,并支持了我在这个项目上的工作。

如果您对 ZK Hunt、这篇文章或者 ZK 游戏机制有任何疑问,请随时在推特上联系我。

感谢您的阅读。

本文由 @FlynnCalcutt 原创

原文地址:https://0xparc.org/blog/zk-hunt

@hicaptainz 翻译到中文社区

关注作者,web3 不迷路

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.