Reverie：一个优化的零知识证明系统 - Trail of Bits 博客

零知识证明，曾一度是理论上的奇思妙想，最近已在 Zcash 和 Monero 等区块链系统中广泛部署。然而，大多数区块链应用中的 ZK 证明在证明大小和性能之间做出了权衡，这些权衡并不适合其他用例。特别是，这些协议通常需要复杂的可信设置阶段，并以证明者时间为代价优化证明大小。许多潜在的 ZK 证明应用如此复杂，以至于 Zcash 使用的 ZK-SNARK 协议需要数天（如果不是数月）才能运行。考虑到这一点，我认为为想要尝试 ZK 证明的工程师提供一套替代的权衡方案非常重要。

在 Trail of Bits 实习期间，我实现了一个 ZK 证明系统 Reverie，该系统优化了证明者效率，并且不需要任何可信设置。这些优化以证明大小为代价，但 Reverie 允许证明通过网络流式传输并逐步验证，从而避免一次性将大型证明加载到内存中。Reverie 也可以在 crates.io 上作为 reverie-zk 使用。

本博客的其余部分将解释 Reverie 背后的底层 ZK 证明系统，并提供性能基准。由于该证明系统使用了安全多方计算（MPC）的技术，我将从介绍一些 MPC 基础知识开始，然后展示如何使用 MPC 构建 ZK 证明。

MPC 入门

玩家分别拥有秘密输入 X、Y、Z，并在不透露 X、Y 或 Z 的情况下计算 f(X, Y, Z)。

多方计算协议的目标是允许对不同方的输入进行分布式函数计算，而各方不会相互透露其输入。

例如：

• 在不透露单个投票值的情况下统计投票。
• 在不透露客户数据库的情况下计算共享客户数量。
• 在私有数据集上训练/评估机器学习模型，而不共享机密数据。

零知识证明和多方计算在概念上有相似之处，但存在关键差异：

• MPC 允许对私有数据进行计算，而零知识证明仅允许各方证明私有数据的属性。
• MPC 协议是交互式的（它们的非交互式表亲是功能加密），要求各方在线。零知识证明可以是交互式或非交互式的。

在本文中，我们将通过描述如何将多方计算协议“编译”为零知识证明系统，来看到这两种原语确实是相关的。这是一个美丽的理论结果：本质上，在零知识证明中检查函数的输出总是比使用多方计算计算函数更高效。

此外，它还可以在实践中导致非常简单、具体高效的证明系统，其应用包括实用的后量子签名方案。正如我们将看到的，这是一个非常通用和多功能的构建零知识证明系统的框架。

密码学编译器

我们现在将探索如何将一系列“密码学编译器”应用于任何 MPC 协议，以获得非交互式零知识证明系统。密码学编译器使用密码学工具从现有协议生成新协议。协议设计中“编译器”的优势在于它们是通用的：任何满足一组属性的输入协议都将产生一个新协议，其中保证一组新属性成立。换句话说，你可以以黑盒方式组合密码学原语，以“机械方式”推导出新协议。

IKOS 编译器

给定一个能够计算函数“g(x)”的 MPC 协议，IKOS 编译器为函数“g”的输入/输出对 (w, o) 产生一个零知识证明系统：它使证明者能够说服验证者它知道一个秘密输入“w”，使得对于某个输出“o”有“g(w) = o”，例如，如果“g(x) = SHA-256(x)”，则证明它知道 SHA-256 的输入“w”导致给定哈希“o”，而不透露原像（“w”）。

在高层次上，这是通过证明者本地运行“g(x)”的 MPC 协议来完成的，其中输入“w”在玩家之间共享。例如，在三个玩家的情况下，可以通过选择随机 X、Y、Z 满足 X + Y + Z = w 来完成。这样，仅知道两个输入 X、Y、Z 不会透露任何关于 w 的信息。然后使用多方计算协议计算函数 f(X, Y, Z) = g(X + Y + Z)。为了防止作弊，验证者要求证明者揭示一部分玩家的输入和通信，并检查它们是否正确运行。

IKOS 密码学编译器

更精确地说，IKOS 编译器接受：

• 一个 MPC 协议。
• 一个密码学承诺方案（下面介绍）。

并产生一个交互式（公共硬币）零知识证明协议。密码学承诺方案由一个函数“Commit”组成，该函数接受一个密钥和一个消息，然后返回一个“承诺”Commit(key, msg) -> commitment，具有以下属性：

• 找到具有相同承诺的不同消息是困难的（像抗碰撞哈希函数）。
• 辨别承诺是否由给定消息创建是困难的（使用随机密钥，承诺隐藏 msg，像加密）。

承诺可以从密码学哈希函数构建，例如通过使用 HMAC 构造。对于承诺的物理类比，可以想到一个信封：你可以把一封信放在信封里并密封它（计算“Commit(key, msg)”），信封将隐藏信的内容（“隐藏”），但不允许你用另一封信替换（“绑定”）。在稍后的时间点，可以打开信封以揭示内容（通过向某人提供“key”和“msg”并让他们重新计算承诺）。

使用密码学承诺，MPC 协议被“编译”如下：

• 证明者通过模拟玩家运行协议来“在头脑中”执行 f(X, Y, Z) 的 MPC 协议：本地运行每个玩家，就像它们是分布式的一样。你可以将其视为证明者在虚拟机内执行每个玩家的代码并记录它们之间的网络流量，或者视为证明者扮演一种 MPC 木偶戏，其中它扮演协议中每个玩家的角色。
• 证明者记录不同玩家在协议执行期间发送和接收的所有内容。我们称之为每个玩家的“视图”：玩家在协议期间看到的一切。然后证明者承诺每个玩家的视图（“将其放入信封”），并将承诺（“信封”）发送给验证者。
• 验证者要求证明者提供一部分视图（在我们的示例中为 2 个）。
• 验证者然后检查提供的视图的两个方之间的对应关系是否兼容：玩家发送和接收协议指定的消息。

如下图所示。

证明者在“虚拟/想象”的各方之间执行 MPC 协议并记录它们的视图。验证者检查这些声称视图的子集之间的一致性。

注意：“公共硬币”部分仅意味着验证者通过选择随机数来响应证明者：在这种情况下是打开的索引，即验证者没有必须对证明者隐藏的“秘密”以防止他作弊。这将在后面相关。

为什么这有效？我们需要说服自己两件事：

健全性：如果证明者作弊，它会被抓住

假设证明者没有输入 X、Y、Z 使得 f(X、Y、Z) = 1。如果它正确执行了 MPC 协议，那么计算将不会返回预期的输出“o”（因为 MPC 协议正确计算 f）。因此证明者必须在“头脑中”执行 MPC 协议时作弊。为了作弊，证明者必须要么：

• 在一个玩家中作弊，例如让玩家错误地进行本地计算。
• 在玩家对之间的通信中作弊，例如假装玩家 A 收到了玩家 B 从未发送的消息。

这两种方式涵盖了在 MPC 协议中作弊的唯一方式：要么让玩家违反协议，要么颠覆模拟的通信介质。

现在考虑具有成对通道的 3 个玩家的情况（如 Alice、Hare 和 Hatter 之间所示）。那么作弊的证明者必须至少在玩家对之间作弊。由于它承诺了所有三个玩家的视图，这些承诺中至少有一对必须不一致：如果验证者打开这对，它会观察到要么一个玩家在作弊，要么两个玩家之间的消息不匹配。由于有三对承诺，作弊的证明者被抓住的概率至少为 ⅓。

为了“提高健全性”（以更高概率抓住作弊证明者），零知识证明并行重复：让证明者多次运行 MPC 协议，然后挑战它从每次重复中打开两个方。这样，作弊证明者在 N 次重复后成功的概率随 N 呈指数下降。

零知识：验证者什么也学不到

当两个视图被打开时，验证者了解到两个玩家的消息和输入。由于承诺方案隐藏了未打开玩家的视图，并且 MPC 协议确保了玩家输入的隐私，验证者不会了解到未打开玩家的输入（示例中的 Y），因为输入如上所述共享，提供两个输入（示例中的 X、Z）不会泄露关于“w”的信息。

Fiat-Shamir 编译器

Fiat-Shamir 变换移除了交互式验证者（教授）。

Fiat-Shamir 变换/编译器接受：

• 一个公共硬币零知识证明系统。
• 一个（特别强的）哈希函数。

并产生一个非交互式零知识证明。

Fiat-Shamir 变换的基本观察如下：由于验证者所做的只是选择随机数，我们可以让证明者掷骰子，然后打开骰子显示的索引。然后每个人都可以验证打开的视图是否一致。

只有一个明显的问题：作弊的证明者当然可以假装骰子掷出它想要的任何结果（例如不打开作弊的玩家对）。Fiat-Shamir 变换通过使用哈希函数“以可验证的随机方式掷骰子”来解决这个问题。

这是通过让证明者哈希他的消息（对每个玩家视图的承诺）来完成的，哈希摘要然后被用作随机挑战（例如解释为表示要打开哪些玩家的整数序列）。

作弊的证明者当然可以尝试更改其消息并重新计算哈希，直到得到允许他作弊的挑战，然而，这仅仅对应于在验证者允许他尝试任意次数的设置中多次运行交互式协议。因此，作弊证明者在交互式协议中成功的概率通过作弊证明者可用的计算量放大，例如，如果交互式协议允许证明者以概率 2^{-128} 作弊，那么对手将不得不计算哈希期望 2^{127} 次才能作弊；这显然不可行。

注意：实际上，Fiat-Shamir 变换需要一个“随机预言机”[参见：https://blog.cryptographyengineering.com/2011/09/29/what-is-random-oracle-model-and-why-3/ 了解更多细节]，这是一个无法真正实例化的证明工件。然而在实践中，用“好的哈希函数”替换“随机预言机”，其中哈希函数的输出“看起来随机”就足够了。

Reverie

这最终将我们带到 Reverie。Reverie 是 KKW 2018 中描述的 MPC-in-the-head 证明系统的高效 Rust 实现，通过将前两个编译器应用于一个特别简单的 MPC 协议派生而来。由于该证明系统适用于任何环（例如有限域、复合整数模或向量空间），Reverie 被设计得既快速又灵活，足以支持任何环中的计算。

由于上面涵盖的 MPC-in-the-head 范式非常通用，并且 KKW 中的技术非常容易推广，Reverie 也被设计为通用且易于扩展。这使得添加功能（如在证明系统内在环之间移动和向电路添加“随机门”）更加容易。

优化

为了提高性能，Reverie 使用了许多实现技巧：

• 大量使用位切片。由于底层 MPC 协议中的各方都并行执行相同的简单操作，我们可以通过将玩家的状态连续打包在内存中，然后用单个操作（在传统的 64 位寄存器中或使用 SIMD 指令）并行操作所有玩家来显著提高性能。Reverie 从不操作单个玩家的状态。
• 并行性。由于证明系统需要多次重复以进行“健全性放大”，每个重复可以轻松委托给单独的线程，以实现线性性能提升。
• 快速密码学原语。Reverie 使用 Blake3 和 ChaCha12，因为这些被发现是最快的密码学原语（密码学哈希函数和伪随机函数），同时仍然提供非常舒适的安全边际。
• 流式证明者和流式验证者。Reverie 允许以流式方式生成和验证证明：这使得验证者能够在证明仍在由证明者生成和传输时验证证明。这意味着 Reverie 的证明和验证组件是完全异步的。

基准测试

为了对 Reverie 进行基准测试，我们测量了在此电路上验证 SHA-256 压缩函数的速度。Reverie 在（32 核）AMD EPYC 7601 上平均每秒约 20 次 SHA-256 压缩应用：

结论

Reverie 是在主导的 SNARK 范式之外创建高性能零知识证明的第一步，它相对轻松地处理了数亿个 AND/XOR 门。该项目附带一个简单的“伴侣”程序（在“companion”子目录中），这使得使用 Reverie 相对容易。立即在 Github 和 crates.io 上尝试！

如果你喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News

页面内容 最近的帖子 使用 Deptective 调查你的依赖项 系好安全带，Buttercup，AIxCC 的评分回合正在进行中！ 使你的智能合约超越私钥风险成熟化 Go 解析器中意外的安全隐患 我们从审查首批 DKL 之一中学到的东西 23 个来自 Silence Laboratories 的库 © 2025 Trail of Bits。 使用 Hugo 和 Mainroad 主题生成。