后量子签名聚合：一种折叠方法 - 密码学

markdown 作者：Thomas Coratger, Srinath Setty

介绍：后量子签名过渡

在以太坊等权益证明系统中，数字签名提供了对数十万验证者的问责，这些验证者负责保护网络安全。大量的证明文件产生了一个重大的可扩展性挑战：如何有效地验证如此多的签名？为此，以太坊的共识层采用了 BLS 签名方案，这一选择对于使网络能够扩展至关重要。

BLS 的优势在于其独特的代数结构，该结构允许使用密码学配对 ($e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$) 进行高效的签名聚合。配对映射的双线性允许一个显著的属性：一组 $n$ 个签名的有效性可以通过一个公式来确认。

在以太坊的实际实现中，聚合签名附带一个位域（\texttt{aggregation_bits}），用于标识委员会中哪些验证者参与了签名。验证者使用这个位域来计算聚合公钥 $\sum pk_i$，然后在运行最终的密码学检查。虽然最终的检查是常数时间的（两个配对），但总体的验证成本包括一个线性时间步骤来构建这个聚合公钥：

$$ e\left( \underbrace{\sum si}{\substack{\text{聚合} \ \text{签名}}}, \underbrace{g}{\substack{\text{公开} \ \text{生成器}}} \right) \stackrel{?}{=} e\left( \underbrace{H(m)}{\substack{\text{哈希} \ \text{消息}}}, \underbrace{\sum pki}{\substack{\text{聚合} \ \text{公钥}}} \right) $$

这个模型对于可扩展性至关重要，并且在 Eth2 Book 中有非常详细的描述，但是 BLS 的安全性依赖于对量子计算机不具有抵抗力的问题。向后量子替代方案的必要过渡，例如 基于哈希的 XMSS，重新引入了可扩展性挑战。XMSS 缺乏 BLS 的代数性质；它的签名更大，验证的计算成本很高，使得每个区块单独验证数千个签名变得不可行。

解决方案是一种新的签名聚合形式，它使用简洁的知识论证（SNARKs）来为整个签名集生成一个单一的、简洁的证明（为了简单起见，通常被称为常数大小，但来自现代基于哈希的 SNARKs 的证明在技术上是声明大小的多对数）。由于验证者分布在点对点网络中，因此单个节点收集所有签名是不切实际的。相反，聚合也必须以分散的方式发生，不同的节点聚合重叠的签名子集。这种“证明的证明”的要求自然会导致递归架构。本文比较了实现此递归的两种主要范例：

1. 递归 SNARK 验证： 在另一个 SNARK 电路中验证完整的 SNARK 证明。
2. 专用递归原语： 利用折叠方案直接组合证明的基础数学语句，避免了完整的验证步骤。

我们分析了每种方法的机制、性能和权衡，以为以太坊的后量子签名聚合提供参考。

聚合框架

为了处理可能扩展到数十万参与者的验证者集的证明，后量子聚合系统必须设计为多层、并行化的过程。与 BLS 签名的简单求和不同，聚合基于 SNARK 的证明需要结构化的递归方法。此过程在聚合器节点的点对点网络中展开，最终形成一个用于链上验证的单一、简洁的证明。

BLS 聚合的实践：现状

在详细介绍后量子方法之前，了解目前如何在以太坊的共识层中使用 BLS 签名实现聚合是有用的。核心机制依赖于跟踪参与情况以确保问责制，这对于正确应用奖励和惩罚至关重要。

验证者被组织成每个Slot的委员会。当委员会中的验证者创建证明时，签名对象包含一个名为 \texttt{aggregation_bits} 的字段。这是一个位列表，其中每个位置对应于该特定委员会中验证者的索引。证明验证者将其自己的位设置为 1。

稍后，来自不同验证者的证明相同链视图的证明可以被聚合。这是通过对 \texttt{aggregation_bits} 执行按位 OR 运算并将各个 BLS 签名加在一起（作为椭圆曲线点加法）来完成的。结果是一个包含组合位域和一个聚合签名的单一 \texttt{Attestation} 对象。为了验证它，节点通过仅对那些在最终 \texttt{aggregation_bits} 中设置为 1 的验证者求和公钥来重建聚合公钥。该系统允许仅通过一次高效的配对检查来验证数百个签名，但至关重要的是，它保留了确切的参与者记录。

在后量子系统中通过位域跟踪参与情况

后量子框架继承了精确跟踪参与情况的关键需求。仅证明匿名签名集有效性的证明不足以用于共识协议。因此，该系统继续使用位域来标识每个签名者。

在以太坊的无需许可模型中，验证者集是动态的。为了管理这一点，信标状态维护着在任何给定时间所有活跃验证者的规范的、有序的注册表。验证者的索引是其在特定状态的此全局注册表中的唯一位置。虽然注册表随着验证者的加入或退出而发展，但该索引为任何给定的共识操作提供了稳定且明确的参考。这确保了即使在动态环境中，也可以精确地跟踪参与情况。

如图 1 所示，每个后量子签名都与一个位域相关联，该位域将签名者的全局索引标记为 1。当证明被聚合时，它们对应的位域使用按位 OR 运算进行组合。结果聚合位域将成为 SNARK 的公共输入，确保最终证明证明精确的声明：“此特定位域指示的验证者都提供了有效的签名。”

\ 图 1292×224 7.72 KB

图 1：位域聚合的概念视图。每个签名对应一个位域，用于标记签名者的索引（例如，验证者 0、2 和 8）。聚合签名与通过对各个位域进行按位 OR 运算而创建的新位域配对，从而提供所有参与者的完整且紧凑的记录。

高级设计：\texttt{Aggregate} 和 \texttt{Merge}

该系统建立在构成递归构造基础的两个核心密码学操作之上。这些操作允许工作负载被分配然后逐步组合。

• \texttt{Aggregate}： 这是初始的、非递归的步骤。聚合器节点从验证者的子集中收集一批原始的 XMSS 签名。它单独验证每个签名，然后生成一个初始的 SNARK 证明，以证明它们的集体有效性。为了验证这些签名并构建正确的位域，每个 \texttt{Aggregate} 操作节点都必须访问全局验证器注册表。此注册表将每个验证器的索引映射到其对应的公钥，是必要的公共输入。此操作将一组大型、难以验证的签名转换为单个、紧凑的证明对象。

• \texttt{Merge}： 这是递归步骤。聚合器节点获取两个现有的证明，每个证明都证明了不同签名集的有效性，并将它们组合起来。输出是一个新的单一证明，该证明提供了与验证来自两个输入证明的所有底层签名相同的密码学保证。此操作是可扩展性的引擎，允许有效地组合证明。

为了清楚地解释密码学过程，我们将聚合建模为一个逻辑递归树，如图 2 所示。此树结构是一个有用的抽象，因为它可以让我们区分分析两个核心密码学步骤 — \texttt{Aggregate} 和 \texttt{Merge} — 它们是证明系统的基本构建块。

在实践中，此逻辑模型是在动态的点对点 (P2P) 网络中实现的。为了管理高带宽需求，验证器集被划分为多个子网。该过程在这些子网中并行开始，其中使用 \texttt{Aggregate} 操作从本地签名集生成初始证明。如图 2 所示，每个 Agg（Aggregate）操作都显示了它对全局状态（验证器注册表）的依赖关系。这表明聚合器必须查询此全局注册表以获取与其验证的签名相对应的验证器的公钥，并正确更新生成的证明的聚合位域。然后，这些初始证明在整个网络中传播。当聚合器节点收到证明时，它们会执行 \texttt{Merge} 操作，将它们组合起来以证明更大的验证器集。这种分布式合并一直持续到生成一个最终证明，该证明代表了整个参与验证器集的证明。

\ 图 2815×499 32.4 KB

图 2：递归聚合过程。原始签名 (\sigma_i) 首先由 \texttt{Aggregate} 操作处理，这些操作访问全局验证器注册表以验证它们。这些操作创建初始证明，然后通过 \texttt{Merge} 操作递归组合，直到形成一个最终证明。

此设计的重要结果是只有最终证明被提交到区块链。这个大小恒定的单个对象取代了在链上处理数千个单独签名的需求。所选的密码学范例必须有效地支持 \texttt{Aggregate} 和 \texttt{Merge} 操作。我们将接下来探讨的基本架构差异在于精确地如何实现这两个操作。

路径 A：蛮力 SNARK 递归

实现递归的最直接的架构范例是将完整的 SNARK 验证器放置在另一个 SNARK 电路中。在此模型中，\texttt{Merge} 操作是一个 SNARK，它证明了其他 SNARK 的验证。这种“证明验证证明”的方法是一种直接的、尽管计算密集的方式来实现递归。

核心机制：证明验证证明

\texttt{Merge} 操作的基本任务是获取两个输入证明，$\text{proof}_A$ 和 $\text{proof}_B$，并生成一个新的输出证明，$\text{proof}_{\text{out}}$，以证明它们的有效性。\texttt{Merge} SNARK 正在证明的关系可以正式表示为：

$$ R{\text{Merge}} = { (\text{proof}{\text{out}}) : \exists \ \text{proof}_A, \text{proof}_B \text{ s.t. } V(pk, \text{proof}_A) = \text{accept} \land V(pk, \text{proof}_B) = \text{accept} } $$

这里，$V$ 代表 SNARK 系统的验证算法。为了生成 $\text{proof}_{\text{out}}$，\texttt{Merge} 步骤的证明者必须在新证明的算术电路中执行两个输入证明的整个验证算法 $V$ 的逻辑。这需要对验证器的每个密码学步骤进行算术化，包括哈希计算、多项式承诺检查和字段算法。现代基于哈希的证明系统非常适合这种方式，因为它们的验证器不需要昂贵的配对操作。

zkVM 抽象的作用

这种方法的主要挑战是验证器电路的巨大复杂性。现代 SNARK 系统的验证器涉及一系列复杂的密码学操作，这些操作转化为庞大而高度复杂的约束系统。手动构建、审计和维护这样的电路实际上是不可行的，并且极易出错。

这就是零知识虚拟机 (zkVM) 成为实际必要的地方。zkVM 用作管理此复杂性的抽象层，允许开发人员使用熟悉的编程模型而不是低级电路约束。该过程的工作方式如下：

1. 高级逻辑： 开发人员不是设计电路，而是使用简单的高级指令集架构 (ISA) 为验证器的逻辑编写程序。此程序可以以统一的方式表达 \texttt{Aggregate} 和 \texttt{Merge} 步骤的逻辑。

2. 密码学预编译： zkVM 配备了预编译的、高度优化的电路，用于昂贵的密码学原语。像 \texttt{POSEIDON} 哈希排列这样的操作可以作为高级程序中的单个高效指令来调用。

3. 编译和执行跟踪： 编译器将高级程序转换为 zkVM 的字节码。当此程序运行时，zkVM 的证明者会生成一个完整的执行跟踪，该跟踪记录了 VM 的每个状态转换 — 从指令获取到内存访问。然后，整个跟踪将自动转换为由 SNARK 证明的最终的大规模约束系统。

zkVM 中的 \texttt{AggregateMerge} 程序

zkVM 模型允许在单个统一程序中实现 \texttt{Aggregate} 和 \texttt{Merge} 操作。这样的程序（我们可以称之为 \texttt{AggregateMerge}）的简化版本将所有验证器公钥的列表和指示在此步骤中证明哪些验证器的位域作为公共输入。作为私有输入，它将接收原始 XMSS 签名和现有 SNARK 证明的混合体。

然后程序的逻辑将是：

1. 递归验证输入证明： 对于每个提供的内部证明，它调用 SNARK 验证函数（使用 zkVM 的指令和预编译实现）。
2. 直接验证原始签名： 对于每个提供的原始签名，它执行 XMSS 签名验证算法。
3. 检查位域一致性： 它确保内部证明的位域和原始签名的索引正确组合以形成新的、更大的输出位域。

然后，zkVM 证明者为 \texttt{AggregateMerge} 程序的整个执行生成单个 SNARK 证明。

性能概况和瓶颈

基于 zkVM 的方法的主要缺点是证明者产生的巨大计算开销。证明者的任务不仅是证明应用程序逻辑 — 签名和证明的验证 — 还要证明虚拟机执行本身的正确性。这种 VM 开销涉及对 CPU 的每个内部步骤进行算术运算，从指令获取和解码到寄存器更新、内存访问和控制流逻辑（如跳转）。

这种额外的工作负载使每个 \texttt{Merge} 步骤的计算量都很大，并直接转化为更高的延迟，这可能是时间敏感的 P2P 聚合网络中的瓶颈。这与“固定程序”递归形成对比，在“固定程序”递归中，验证器电路专门用于编译时的单个预定程序，从而无需通用 CPU 架构及其相关的开销。

但是，至关重要的是，基于哈希的 SNARK 的性能前景正在迅速发展。如果底层证明系统的原始性能足够高，则可以使用“足够好”原则。证明技术的最新进展表明了极高的吞吐量。如果这些趋势持续下去，则 zkVM 的恒定开销可能会成为开发人员体验和灵活性的可接受的折衷方案，即使在时间敏感的应用程序中，它也是可行的选择。尽管证明成本很高，但现代的基于哈希的 SNARK 可以生成非常紧凑的证明，从而可以满足链上大小目标。

路径 B：专用递归原语

蛮力递归的替代方法是利用专门为此任务设计的密码学原语：折叠和累积方案。此范例不是在电路中验证完整的 SNARK，而是直接对证明的基础数学语句进行操作。它提供了一种高效的密码学捷径，可将多个计算完整性声明组合为单个等效声明，从而显着减少了每个递归步骤中证明者的工作负载。

实例-见证框架

这种方法的核心是实例-见证对的概念，表示为 $(x, w)$，它代表特定 NP 关系 $R$ 的计算语句。实例 $x$ 包含语句的公共数据，而见证 $w$ 包含满足它的可能秘密数据。这种统一结构用于 \texttt{Aggregate} 和 \texttt{Merge} 操作。

• \texttt{Aggregate} 步骤： 此操作创建第一个实例-见证对。关系 $R$ 是 XMSS 签名验证算法。实例 $x$ 由公共数据（消息、位域和相关公钥）组成，见证 $w$ 由秘密数据（原始 XMSS 签名）组成。输出是一个初始实例-见证对，可以进行折叠或累积。
• \texttt{Merge} 步骤： 此操作采用两个实例-见证对，$(x_1, w_1)$ 和 $(x_2, w2)$，并使用轻量级协议来计算相同关系 $R$ 的单个折叠对 $(x{\text{folded}}, w_{\text{folded}})$。此过程在计算上比在电路中运行完整的 SNARK 验证器便宜得多。此外，对于相同的关系，折叠证明者比 SNARK 证明者便宜。

我们现在探讨两种实现此范例的后量子机制。

基于格的折叠

折叠方案是一种协议，它采用关系的两个实例并将它们组合成_相同_关系的一个新实例。后量子折叠方案的一个突出例子是 Neo，它基于貌似后量子的格假设。

基于格的密码学的关键挑战是管理见证的范数。执行诸如线性组合之类的密码学操作会导致此范数增长。如果范数增长过大，则承诺方案的安全性可能会崩溃。Neo 设计围绕一个三阶段循环，该循环仔细管理此范数增长。

对于我们的用例，\texttt{Aggregate} 步骤为称为 Matrix CCS (MCS) 的关系创建一个初始实例-见证对，该关系表示 XMSS 验证电路。然后，\texttt{Merge} 操作采用这个新的 MCS 实例和一个正在运行的累加器（它是更简单的评估关系 ME 的一个实例），并执行 Neo 的循环（图 3 描述了此工作流程）：

\ 图 3824×450 65.3 KB

图 3：Neo 的多重折叠方案以及生成链上 SNARK 的最终确定步骤的可视化。

基于哈希的拆分累积

用于递归的另一个原语是拆分累积方案，该方案维护一个正在运行的累加器，用于证明一组声明的有效性，这些声明甚至可以用于不同的关系。拆分累积和折叠方案是同时引入的。尽管它们之间存在一些具体的差异，但它们对我们的阐述并不重要。\texttt{Merge} 操作对应于向此累加器添加一个新声明。后量子拆分累积方案的一个主要例子是 WARP，它基于貌似后量子的哈希函数，并且专门为最大证明者性能而设计。

拆分累积方案

拆分累积方案的核心思想是将累加器拆分为两个部分：一个小的公共实例部分和一个大的私有见证部分。在每个递归步骤中，证明者 ($P_{ACC}$) 采用旧的累加器和一个新的声明，生成一个更新的累加器，并生成一个此转换的小证明。

至关重要的是，验证者 ($V_{ACC}$) 只需要旧的和新的累加器的公共实例部分来检查此转换证明。验证者永远不会看到或处理大的见证部分，从而使递归验证步骤非常轻量级。最终证明者（“决策者”）仅在此过程的最后才需要完整的见证，他生成单个链上 SNARK。

从电路到多项式：PESAT

在 WARP 框架中，正在累积的声明表示为多项式方程可满足性 (PESAT) 的实例。WARP 不是将计算表示为门电路，而是将其表示为一组多项式方程，对于给定的实例和见证，这些方程必须全部评估为零。这是一个高度通用的框架，可以捕获常见的约束系统，例如 R1CS 和 CCS。对于我们的用例，XMSS 签名验证算法和位域逻辑被编译为 PESAT 实例。

线性时间证明者

WARP 的主要优势在于其线性时间证明者。证明者的运行时（以字段操作和哈希计算来衡量）与计算的大小成线性关系。这是证明者效率的一项重大突破，避免了在其他系统中发现的两个主要开销来源：

• 基于组的密码学的超线性成本 ($O(N \log N)$)，该成本由大型多标量乘法主导。
• 通用 zkVM 的大型恒定开销，除了应用程序逻辑外，还必须证明其自身 CPU 架构的执行。

对于像签名聚合这样的大规模、重复性任务，线性时间证明者可提供显著的性能改进，使其成为递归引擎极具吸引力的选择。

最终确定：生成链上 SNARK

无论通过折叠还是累积，递归 \texttt{Merge} 过程都会产生单个最终实例-见证对。此对在计算上有效 — 它正确地表示了整个聚合签名集 — 但从传统意义上讲，它并不简洁。Final 证明者仍然需要见证组件，从而使对象太大而无法直接进行链上验证。

因此，最终聚合器节点必须执行一个额外的步骤：生成此最终折叠对的标准非递归 SNARK。这将产生一个混合架构，该架构采用两个不同的密码学引擎：

1. 递归引擎： 为提高证明者效率而选择的折叠或累积方案。其主要目的是以较低的计算成本在每个递归步骤中将多个语句合并为一个。
2. 简洁引擎： 用于生成紧凑且可有效验证的链上证明的最终非递归 SNARK。

最终确定管道如下：

1. 最终折叠实例-见证对被视为要证明的语句。
2. 应用多项式交互式 Oracle 证明 (PIOP)，例如 (Super)Spartan，以将证明折叠见证知识的任务简化为一组多线性多项式评估声明。
3. 使用后量子多项式承诺方案 (PCS)，例如 BaseFold 或 WHIR 来证明评估。

这种混合架构将高效递归的功能与最终简洁的功能分开。它利用每种方法的相应优势来构建一个可扩展且产生紧凑的链上证明的系统。

工程挑战：见证管理

此路径的一个重大工程挑战是在 P2P 网络中管理见证数据。任何 \texttt{Merge} 步骤的证明者都需要访问正在组合的两个证明的见证。一个简单的实现将需要传输这些大型见证，这可能会造成严重的带宽瓶颈。

可以使用见证分块技术在协议级别解决此问题。此方法通过更改见证的处理方式来缓解带宽要求：

1. 对块的承诺： 大型见证不被视为一个整体对象，而是被划分为多个较小的、大小恒定的向量。然后，证明者分别承诺每个块。

2. 块的折叠： 当两个证明被折叠时，生成的折叠见证本身只是一个小的单向量。因此，必须在递归步骤之间传递的密码学状态保持紧凑且大小恒定，从而防止数据的复合增长。

3. 高效验证： 虽然此方法增加了递归验证者必须处理的承诺数量，但 Neo 等方案旨在有效地处理此问题。可以折叠对见证块的承诺，而不会给验证者电路带来显著的复杂性或成本。

此设计将挑战从密码学限制重新定义为 P2P 数据可用性问题：确保聚合器节点可以从网络中找到并获取所需的见证块以执行 \texttt{Merge} 操作。

权衡：基于格的基元与基于哈希的基元

在基于格的折叠方案（如 Neo）和基于哈希的累积方案（如 WARP）之间进行选择涉及架构权衡，主要集中在安全假设与性能和实现复杂性之间。

• 安全假设： 这是基于哈希的方案的主要优势。它们的安全性仅依赖于密码学哈希函数的属性，通常建模为随机 Oracle。这是一个最小且广泛信任的假设，但对于折叠/拆分累积。相反，基于格的方案依赖于结构化假设，例如模块短整数解 (Module-SIS) 问题。虽然人们强烈认为后量子很难破解，但特定格参数化的实际安全性是一个活跃且不断发展的研究领域。密码分析的不断进步，例如混合攻击的实际改进，不断完善我们对具体安全级别的理解，并引入基于哈希的简单方法中不存在的长期风险因素。

• 递归开销： 这是基于格的方案的一个关键优势。在基于哈希的系统中，递归 Merge 步骤需要在下一个证明中验证 Merkle 路径打开。在基于格的方案中，折叠操作更具代数性，直接组合数学语句，而无需验证完整的密码学对象。这导致了更简单的递归验证器电路，可以转化为显著降低的计算开销。

• 专用功能： 基于格的构造（如 Neo）可以提供独特的性能优势。例如，Neo 引入了“按位付费”承诺成本，其中承诺见证的成本随其值的位宽而变化。这对于许多见证值都很小的实际计算非常有利，这是基于哈希的系统中通常没有的功能，后者将所有数据都视为全尺寸字段元素进行 Merkle 哈希处理。

架构权衡的比较分析

在蛮力递归和专用原语之间进行选择涉及系统设计中的不同权衡。这两种方法的主要区别在于它们将复杂性放置在何处 — 密码学证明基础设施中还是点对点协议层中 — 从而导致性能和开发抽象之间的平衡。下表总结了这两个架构路径之间的主要区别。

表 1：递归聚合架构的比较

结论

以太坊共识层向后量子签名方案的过渡需要递归聚合架构。此架构的选择不是一个简单的决定：zkVM 和折叠方案分别具有独特的优势和工程挑战。

路径 A 的特点是蛮力 SNARK 递归，它通过将其抽象到 zkVM 后面来管理密码学复杂性。此方法简化了应用程序逻辑的开发，但通过要求证明者证明 VM 的执行跟踪，在递归步骤中引入了显著的、不可避免的计算开销。

路径 B 使用折叠和累积方案等专用原语，旨在通过使用更高效的密码学引擎进行递归来实现高性能。此设计将复杂性从密码学核心推到 P2P 协议层，然后 P2P 协议层必须解决诸如见证数据可用性之类的挑战。

最终，以太坊的最佳路径尚未确定，并且代表了一个活跃的研究领域。该决定将取决于 zkVM 和折叠技术的持续成熟、对 P2P 网络动态的进一步分析、共识层的精确性能和安全要求，以及对通用性与专业化的长期价值的战略选择。基于 zkVM 的解决方案虽然对于此一项任务的性能可能较低，但它提供了一种灵活的基础架构，可以满足协议的未来需求，而专用折叠方案则代表了一种高度优化但可能狭隘的解决方案。本文旨在阐明所涉及的基本权衡，从而为正在进行的辩论提供一个结构化的框架。

• 原文链接： ethresear.ch/t/post-quan...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～