EdwardAThomson/psi-demo

# 私有集合交集演示 这是一个关于私有集合交集（PSI）的最小化工作演示。 其目的是证明这可以在即时战略游戏中生效，正如研究论文 [OpenConflict: Preventing Real Time Map Hacks in Online Games](https://www.shiftleft.org/papers/openconflict/) 中所展示的那样。 这里有一个在线演示：[PSI Demo @ Vercel](https://psi-demo-delta.vercel.app/)。 请参阅[项目路线图](./ROADMAP.md)了解已发布的功能和接下来的计划。 **近期更新：** 从 C++ 移植版本（[Private-Set-Intersection](https://github.com/EdwardAThomson/Private-Set-Intersection)）中移植了两个安全修复程序和一个协议改进。hash-to-group 函数现在生成具有未知离散对数的点（基于 SHA-512 的 ristretto255 元素派生，与 libsodium 的 `crypto_core_ristretto255_from_hash` 匹配）；旧的 `H(x)*G` 结构允许参与者从一次运行中恢复 `b*G` 并离线枚举另一个集合。通信消息不再携带任何明文元素；它们仅包含固定的 32 字节值（成员标签、盲化点、转换点）。Bob 现在发送单向的 BLAKE3 成员标签而不是密文，因此最终处理变为 O(A) 次 hash 查找，无需试解密。这是一个破坏性的通信格式变更。 **威胁模型：** 该协议针对“诚实但好奇”的参与者是私密的；恶意参与者可以使用伪造的输入探测成员身份。 ## 描述 这段代码是一个关于 PSI 计算如何工作的简单演示。 OpenConflict 解决方案的一个缺陷是，它无法防止玩家对自己的位置或可见性撒谎。我认为撒谎这个问题是可以解决的。本质上，玩家会在游戏结束时展示他们所有的位置和可见性集合。然后，玩家可以根据游戏规则检查这些信息，以确保计算是正确的并且符合游戏的物理规律。 此外，还需要一个争议解决协议，以便在一名玩家与另一名玩家意见不一致时进行裁决。当一名玩家作弊并拒绝承认时，就会发生这种情况。 我在 2020 年 6 月写的一篇博客中概述了整体的顶层策略：[Preventing cheaters in Fog Of War Games](https://edward-thomson.medium.com/preventing-cheaters-in-fog-of-war-games-69f202fbe107)。 ### 实现选择 以下是我在此应用中做出的一些技术实现选择。 * ristretto255 group（[@noble/curves](https://github.com/paulmillr/noble-curves)），通过 SHA-512 和 RFC 9496 元素派生进行 hash-to-group（未知离散对数） * BLAKE3 单向成员标签（[@noble/hashes](https://github.com/paulmillr/noble-hashes)），采用上下文为 `PSI-membership-tag-v1` 的 derive-key 模式 * 多级网格系统 * Web workers 选择这些是因为它们的运行速度快，或者可以减少开销。每个通信条目都是一个固定的 32 字节值；各方之间不传输任何明文位置。未来我可能需要研究 Wasm，或者制作一个桌面应用程序。 运行 `npm run selftest` 以检查协议核心（正确的交集、不相交集合的空交集，以及没有任何输入元素出现在任何序列化消息中）。 ### PSI 解释器 我整理了一个页面，解释了关于什么是 PSI 以及它是如何工作的更多细节：[PSI 解释器](./explanations/psi_explainer.md)。 ## 使用此应用 ### 主页 演示协议的运行。单位和可见性是静态/简单的点。只需点击“Run”按钮即可。  ### PSI 可视化 这是一个简单的可视化，展示了在盒子内移动的简单点粒子（Bob 的单位）。可见性圆圈是静态的，但与主页上的测试不同，它们会扫过 2D 区域。目前代码效率低下，但它表明该协议适用于动态移动。PSI 代码每 5 秒触发一次，并且计算速度非常慢（**会导致巨大的可视化延迟**）。 为了提高性能，应用将位置和可见性转换为单元格，这是对像素更粗糙的表示。1 个单元格是 50x50 像素。后来我添加了多级网格和 Web workers 来提高性能。虽然性能有了很大提升，但仍然有点慢。 使用基于标签的协议，最终处理是对每个 Alice 元素进行集合查找，而不是对每个数据包进行试解密，这消除了旧的平方级步骤。剩余的成本是椭圆曲线标量乘法，它与单元格数量呈线性比例增长。  这里有一个传统的可见性计算，有助于校准应该看到的内容。您真的应该打开控制台日志来检查结果。 ### Roguelike 演示 我添加了一个非常简单的演示游戏。这是一个 Roguelike 游戏，玩家可以在房间里移动以寻找怪物。每当怪物进入视野时，只有在 PSI 计算确认后才会渲染它。 代码的性能不是很好，但我相信它能正常工作。  ## 安装 1. 克隆仓库： ``` git clone https://github.com/EdwardAThomson/psi-demo.git cd psi-demo ``` 2. 安装依赖： ``` npm install ``` 3. 运行应用： ``` npm start ``` 这将在 http://localhost:3000 启动应用。 ## 许可证 该项目基于 Apache 2.0 许可证授权 - 有关详细信息，请参阅 [LICENSE](LICENSE) 文件。 ## 致谢 非常感谢以下人员： - Anuj Gupta，与我分享这个想法的研究员。 - 一路上使用的 AI 编程助手（Claude、ChatGPT）。 - Decentralized Gaming Association 的所有人 [DGA Discord](https://discord.com/invite/eZEVrSd)

标签：RTS游戏, 密码学, 手动系统调用, 数据可视化, 游戏安全, 私有集合交集, 网络安全, 自定义脚本, 防作弊, 隐私保护