密码学战争迷雾

TL;DR: 我们描述了一种新的游戏机制，由 ZK 和 MPC 启用。

简介

Dark Forest（黑暗森林），一款太空战争游戏，于 2020 年 2 月发布。在接下来的 30 个月里，经过几轮的迭代，Dark Forest 在核心游戏社区中取得了巨大的成功 core gaming community。在这篇博客中，我们认为 DF 是有史以来第一个新的游戏机制的实例，其特征在于以下 3 个要求：

• PvP：没有庄家/可信方
• 隐藏信息（战争迷雾）
• 确定性状态

据我们所知，没有现代游戏引擎可以同时支持所有这 3 个要求。这仅仅是因为要启用此类游戏，我们需要引入一些很酷的新密码学。ZK-Hunt 是对密码学战争迷雾概念的一次美丽的探索。在这篇博文中，我们正式确定了这个概念，并提出了 Oblivious KZG：一种基于双向、可验证、承诺的盲传输（biVOT）的新构造。结合 ZK 证明，biVOT 完善了未来游戏引擎安全构建更多类似 DF 游戏所需的工具箱。

ZK-Hunt（左）和 DF（右），均已停止活动，但代码完全开源：https://github.com/FlynnSC/zk-hunt 和 https://github.com/darkforest-eth

定义游戏

我们首先定义我们的游戏模型。为了本文的写作，我们将侧重于演示，而减少对精确性的关注。

游戏是两个或多个参与者（玩家）之间的协议。公共状态机（游戏物理）定义了一个谓词。每个参与者将其当前状态保存在内存中。该协议分轮（回合）运行。在每一轮中，允许一方采取一个有效的行动并更改其状态一次。此外，在每一轮中，该方将状态更新传达给所有其他玩家，并根据上一轮所有其他方的状态更改的谓词检查有效性。

到目前为止一切顺利！很容易看到 ZK 证明是如何适用的：每个状态更改都可以使用 ZKP 进行验证。事实上，从实际原因出发，在游戏设置中，我们可以直接要求每个参与者将状态更改证明折叠到前一个中，并且仅在游戏结束时发布完整的公开可验证的证明，供所有人验证并就例如获胜者达成一致。我们乐观地信任玩家默认情况下会诚实地行动，但显然可以更频繁地发送状态更改正确性的证明。

我们的游戏模型基于双方之间简单的 MPC 协议

进入战争迷雾

我们的模型尚未考虑隐藏信息。首先，让我们解释一下这个概念。想想经典的战舰游戏。一个恶意的玩家可能会在每次成功击中后更改其船只的位置，并宣布他们未被击中。如果我们更改我们的模型，使得棋盘上秘密的、据称是固定的船只位置不发送给所有其他玩家（保持其为隐藏信息），则 ZKP 将不会捕获任何不当行为——状态更改只会检查相对于任意棋盘位置的基本游戏玩法。

这里的解决方案很简单。我们要求所有玩家在游戏开始时提交棋盘。承诺是隐藏的和有约束力的，并在整个游戏中使用。现在我们可以将承诺包含在玩家状态中，并且 ZKP 将证明相对于同一承诺的任何状态更改。在 MPC 术语中，我们从半诚实对手转向恶意对手。我们注意到，今天的许多在线游戏都是半诚实的，并且在玩家之间共享敏感数据。

战舰游戏是一个很好的玩具例子，但是，战争迷雾可以进一步推广。想想像《反恐精英》这样的 FPS 游戏，或者像《英雄联盟》这样的策略游戏，每个玩家指挥一个单位，或者几个单位，可以在附近的坐标中寻找其他玩家的单位。在这种搜索和摧毁的游戏玩法中，玩家 A 正在探索一张地图，现在，与在设置时隐藏信息是固定的战舰游戏不同，隐藏信息正在每回合发生变化，并且取决于其他玩家的状态，这是使用我们的游戏模型术语。坚持使用双人游戏场景；为了探索地图，玩家 A 必须每回合探测玩家 B 的承诺状态。一个关键的要求是，探测的坐标必须对玩家 B 保持隐藏，否则玩家 B 将仅通过查看探测请求来了解玩家 A 的位置！

解决方案是一种已知且经过充分研究的密码学原语，用于许多 MPC 构造中，称为不经意传输（OT）。在 OT 中，发送者有 n 条秘密消息，接收者想要学习其中的 k 条（这被称为 k-out-of-n OT），而不学习其他消息，并且发送者也不知道学习了哪些消息。

在我们的例子中，接收者是玩家 A，发送者是玩家 B。秘密的 n 条消息编码了玩家 B 的状态：单位的位置及其状态（例如，健康）。一个简单的编码将是一个多项式或向量，其中索引表示固定的地图，值是编码诸如单位类型、健康、物品等的字符串。玩家 A 使用 k-out-of-n OT 来探测其附近的特定索引，并学习 0（此位置没有玩家 B 单位）或一个字符串，该字符串告诉玩家 A 关于敌方单位需要知道的一切。

OT 功能

情节变得更复杂

请记住，我们的游戏在恶意对手设置中运行。因此，就像战舰游戏一样，我们需要添加可验证性。在 OT 的情况下，我们可以直接向发送者添加可验证性，所以现在我们有了可验证 OT（VOT）。具体来说，玩家 B 对 OT 的输入必须相对于对其状态的承诺是可验证的。它在我们的游戏模型中的工作方式是，现在每次状态更改都会产生一个新的承诺和一个用于状态差异正确性的 ZK 证明。相同的承诺也用于 VOT 中，以便接收者玩家 A 仅获得关于探测坐标的知识，并保证发现的内容代表玩家 B 的有效状态。

事实上，我们需要更强大的东西。

我们希望接收者选择要学习的消息也是可验证的。在我们的搜索和摧毁游戏玩法示例中，我们必须确保探测玩家探测的坐标处于根据游戏规则明确定义的探测范围内。我们将此属性直接添加到我们的 VOT 中。我们称之为双向 VOT（biVOT），据我们所知，这是一个新颖的想法。

实现 biVOT

我们的构造基于 KZG 承诺：

我们将游戏地图描述为一个多项式，其中索引是坐标。这些值是编码地图上所有单位数据的字符串。如果玩家 B 的一个单位从索引 i 移动到索引 j，玩家 B 会更新多项式，使得 P(j) 现在取 P(i) 的值，而 P(i) 变为零。例如，如果位置 i 的单位受到攻击但没有改变位置，则 P(i) 值会更新以反映该单位的新健康状态。玩家 B 每次状态更改都会生成一个新的多项式承诺（以及一个用于正确性的 ZKP）。

当然，选择 KZG 多项式承诺并非随机，因为 KZG 承诺在许多 ZKP 方案中使用，可能会重叠我们在 MPC 和 ZK 中实现完整游戏机制所需的密码学和安全假设。

接下来，我们调整 KZG 以添加几种可能的 OT 功能，并在性能上进行不同的权衡，请参阅下表中的成本分析。每个不经意的 KZG 变体都可以在简化的、更高效的版本中使用，其中消息可以从大小为 m 的预定集合中取值（最简单的是单个位来指示敌方单位的存在），或者扩展到通用版本，其中任意长度为 mu 的消息以 B 为基数。我们的构造依赖于离散对数的硬度、配对以及可信设置的存在。

不经意的 KZG 变体及其成本

在其最一般的形式中，Bob（玩家 B/发送者/证明者）和 Alice（玩家 A/接收者/验证者）之间的不经意的 KZG 接口现在看起来像这样：

承诺：

• Bob 承诺一个多项式
• Alice 承诺一个多项式

探测： Alice 向 Bob 发送一条消息，其中包含她希望学习的隐藏索引集和有效探测的证明

证明：

• Bob 验证探测
• Bob 使用 Alice 的消息发送一条包含探测隐藏结果的消息

验证-解码： Alice 解码要在游戏中使用的值，并根据 Bob 的承诺验证其正确性。

我们的 biVOT 协议可以防御恶意对手，一旦我们完成对安全证明的充分同行评审，将在此处和单独的论文中共享。同时——如果你想尽早访问完整的论文和代码并开始破解新的 Dark Forest 体验，请联系 hi@ingonyama.com！

你知道吗

如果你读到这里，你知道 ZK 可以在游戏 GPU 上与图形一起运行，而不会显着相互干扰吗？如果你好奇我们是如何知道的，或者想尝试与图形并行运行 ZK —— 与我们交谈！

关注 Ingonyama

Twitter: https://twitter.com/Ingo_zk

Documentation: https://dev.ingonyama.com/

YouTube: https://www.youtube.com/@ingo_zk

GitHub: https://github.com/ingonyama-zk

LinkedIn: https://www.linkedin.com/company/ingonyama

加入我们: https://www.ingonyama.com/career

• 原文链接： medium.com/@ingonyama/cr...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～