通信复杂度的粗略估算

草稿计算：去中心化证明的通信复杂度

本笔记着眼于在 1000 台机器的集群上并行化 10 亿指令周期的计算证明所需的通信复杂度。

我们首先讨论在 RISC Zero 的 Bonsai 上，我们的递归架构中的通信复杂度，然后考虑并行化 folding 的通信复杂度。主要目的是作者整理自己的思路，并检查理解情况；希望这对其他人也有用。

印象总结

我们最初的印象是，在 folding 中管理通信复杂度是一个不小的挑战。

这里的目的是了解这些挑战是真实存在的还是想象出来的，并了解在水平可扩展的 folding 方法方面的最新技术水平。请指出这里的假设存在的问题，并提出改进此分析的正确性/公平性/实用性的建议。

有人建议，我们可以通过选择尽可能小的 folding witnesses 来轻松应对水平扩展的挑战。事实上，我们下面的草稿计算表明，如果我们可以将 folding witness 的大小调整到 250 kB，我们就可以匹配基于 FRI 的系统的通信复杂度。

那么，问题是，将 folding witness 调整到这么小是否真的可行，以及如此小的 witness 大小是否会导致高性能的系统。

witness 大小的下限来自递归验证电路，该电路强制执行 folding 的正确性。在 Nova 中，这个验证电路大约有 10,000 个乘法门。CycleFold 将其改进到接近 1,000 个乘法门。假设每个门由 (3) 个 255 位的域元素组成，并为了简单起见进行一些四舍五入，我们估计电路中每个门大约需要 750 位。这表明 Nova 中 folding witness 的绝对最小大小为 7.5 MB。CycleFold 在此基础上提供了 10 倍的改进，达到 750 kB。

当我们朝着非常小的 witnesses 发展时，我们会遇到一个工程上的权衡：当 folding 的验证在每个步骤中所占的工作比例很小时，folding 的性能提升是最强的。

本说明的其余部分阐述了我们在 Bonsai 上并行化递归证明的方法和一个基于 folding 的类似方法的简单草图，以便阐述每种方法的草稿计算。

并行化递归证明

我们首先介绍当前用于 RISC Zero 的 Bonsai 的证明架构。在下面，我们考虑 folding。

简而言之，我们对当前架构的粗略估计表明，为了使用一个包含 1000 台机器的网络来证明一个 1 TB 的 witness，需要 51 GB 的网络通信，这相当于 10 亿次计算周期的 zkVM 计算。为了更好地理解这些数字，这个大小对于证明以太坊区块的构造来说是典型的。

证明架构概述

当我们要求 Bonsai 证明一个大型的 RISC-V 程序时，我们可以将工作分为四个类别：执行、分段证明、聚合和一个 Groth16 包装器。

1. 执行 - 执行器运行完整的 zkVM 执行，识别要证明的 段（segments），然后将每个 段 分配给动态大小的 AWS 集群中的一台机器。执行过程在单台机器上进行。
2. 分段证明 - 每个段证明器为其段生成完整的 witness，然后证明其段的正确性。分段证明可以完全并行化。
3. 证明聚合 - 使用基于 FRI 的递归，以二叉树形式聚合证明。成对的段证明在递归证明器中进行验证，直到我们得到一个单独的 STARK。聚合的证明工作可以逐层并行化。
4. SNARK 包装 - 为了方便链上证明，我们（可选地）将 STARK 包装在 Groth16 SNARK 中。

这些步骤的详细信息如下图所示，并在我在 zk10 的演讲 中有更详细的讨论。

通信复杂度

在运行完整的网络成本草稿计算之前，我们强调几个关键点：

1. Witnesses 永远不会通过网络发送。

在 Bonsai 上，我们不会通过网络发送完整的 witnesses 或完整 witnesses 的各个部分，而是每 100 万个计算周期拍摄一次内存快照，并将这些快照分发给证明器，然后由证明器重新创建并证明 witness 数据。

2. 发送 zkVM 镜像数据是网络成本的主要部分。 重新创建 witness 数据需要在某一时刻的 zkVM 镜像快照。使用我们当前的图像编码方式，每个快照的大小最多可达 200MB，具体取决于快照时的 RAM 分配情况。我们使用 50MB 进行后续分析，这足以证明大多数 Zeth 区块。
3. 证明聚合的成本可以忽略不计。 在后续草稿计算中出现的 51 GB 网络成本中，只有 1 GB 足以支付所有证明聚合成本；剩余的 50 GB 用于分发 zkVM 镜像快照。

这里的方法利用了该过程每个步骤的简洁性，从而大大减少了对通信复杂性的任何担忧。

网络成本草稿计算

在本节中，我们将快速估算证明 10 亿周期计算的总通信复杂度。

我们假设该计算分为 1000 个段，每个段包含 100 万个计算周期。

为简单起见，我们假设正在执行的二进制文件和该二进制文件的输入的大小可以忽略不计。

• 初始执行生成段。
  • 执行器生成 1000 个 段，每个段的大小约为 50MB。段 包括机器的完整状态：所有寄存器值和内存编码。

• 段分配给证明器。

  • 1000 个段 x 50 MB = 网络上 50 GB。

  分段证明器使用 50 MB 的段数据（包括机器寄存器的状态和给定时刻的 RAM 状态）来重建 witness（~1GB），然后在该 1GB witness 上运行 STARK 证明器。

• 分段证明器返回证明。
  • 1000 个 STARKS x 250 kB = 网络上 250 MB
• 分配 STARK 对进行递归
  • 在第一层中，发送 1000 个 STARKS；返回 500 个。在下一层中，发送 500 个 STARKS；返回 250 个。……
  • 在证明聚合过程中，总共分配了约 2000 个 STARKS，并返回了约 1000 个 STARKS。假设每个 STARK 约为 250kB，则网络上约 750MB。为简单起见，我们将其称为 1GB。
• STARK 到 SNARK 的转换
  • 为了便于计算通信复杂度，我们将此步骤视为可以忽略不计。

TODO 250kB 只是 STARK… 收据元数据有多少额外开销？我猜这完全取决于应用程序？

总而言之，在 1000 台机器的集群上证明 10 亿周期计算涉及 51 GB 的通信复杂度。请注意，此处 95% 的通信复杂度是将初始任务分配给分段证明器。在分配了初始段之后，我们就能够管理整个组织工作者并将工作聚合成 1 GB 通信复杂度的过程。

并行化基于 folding 的证明

我们简要介绍一个简化的并行化 folding 方案。有关更详细的方案，请参阅 Paranova。此处描述的简化方案足以进行草稿计算。

如上所述，我们考虑一个 10 亿周期的计算，其中 witness 的每一行的大小为 1 kB。这里的总 witness 大小为 1 TB。

我们首先像上面一样，将计算分为对应于 100 万个计算周期（1 GB witness 大小）的 段。与上面一样，我们为每个段构建一个内存快照（50MB），并将一个快照分发给集群中的每台机器。每台机器都使用内存快照来重建 1 GB witness。

现在，每台机器都需要对它们的 1 GB witness 做一些处理，并通过网络将一些东西发送回去。假设，每台机器将其 TB witness 分成 1000 个较小的 witnesses，并使用 folding 将它们组合起来。完成这项工作后，每台机器现在都持有一个针对被要求证明的 100 万个周期的 folded witness（1 MB）。

现在，每台机器都通过网络返回它们的 witness；通信复杂度是可管理的，因为 folded witnesses 只有 1 MB。

现在，我们的任务是聚合 1000 个 witnesses，每个 witness 的大小为 1 MB。由于我们在此阶段通过网络发送 witnesses，因此我们无需继续分发内存镜像。

这里的通信复杂度与聚合 1000 个 STARKS 的任务仅略有不同，并且可以通过调整上述设计中的某些参数来实现。

我们得出结论，如果你可以调整 witness 大小以匹配 STARK 的大小，则分发 folding 的通信复杂度可以与基于 FRI 的系统相匹配。有关这种小型 folding witnesses 是否可能/可行的更多讨论，请参见本说明顶部的 印象总结。

参考文献

引发本说明的 Twitter 讨论

Paranova

CycleFold

我的 zk10 演讲和幻灯片

联系方式

对于更正、问题和评论，请联系 paul@risczero.com。

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