后量子签名聚合：一种折叠方法

作者： 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 s_i}{\substack{\text{聚合} \ \text{签名}}}, \underbrace{g\vphantom{\sum s_i}}{\substack{\text{公共} \ \text{生成器}}} \right) \stackrel{?}{=} e\left( \underbrace{H(m)\vphantom{\sum s_i}}{\substack{\text{哈希后的} \ \text{消息}}}, \underbrace{\sum pk_i}{\substack{\text{聚合} \ \text{公钥}}} \right) $$

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

解决方案是一种新的签名聚合形式，使用简洁的知识论证（SNARK）来为整个签名集生成一个单一的简洁证明（虽然通常为了简单起见被称为常数大小的证明，但现代基于哈希的 SNARK 的证明在技术上是关于陈述大小的多对数级别）。由于验证者分布在点对点网络中，单个节点收集所有签名是不实际的。相反，聚合必须以去中心化的方式进行，不同的节点聚合重叠的签名子集。这种“证明的证明”需求自然引出了递归架构。本文比较了实现这种递归的两种主要范式：

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 的公共输入，确保最终证明证明了这个精确的声明：“该特定位域指示的验证者都提供了有效的签名。”

图 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（聚合）操作显示了其对全局状态（验证者注册表）的依赖。这表明聚合节点必须查询这个全局注册表，以获取其正在验证的签名对应的验证者的公钥，并正确更新生成证明的聚合位域。这些初始证明然后在网络中传播。当聚合节点收到证明时，它们执行 \texttt{Merge} 操作，将它们组合起来以证明逐渐更大的验证者集合。这种分布式合并一直持续到生成一个单一的最终证明，该证明代表整个参与验证者集合的证明。

图 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, w_2)$，并使用轻量级协议计算一个单一折叠对 $(x_{\text{folded}}, w_{\text{folded}})$，用于相同的关系 $R$。这个过程在计算上比在电路内运行完整的 SNARK 验证器便宜得多。此外，折叠证明者比验证相同关系的 SNARK 证明者更便宜。

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

基于格子的折叠

折叠方案是一种协议，它接收一个关系的两个实例，并将它们组合成同一关系的一个新实例。后量子折叠方案的一个突出例子是 Neo，它基于看起来是后量子的格假设。

基于格子的密码学中的一个关键挑战是管理证据的范数。执行诸如线性组合之类的密码学操作会导致这个范数增长。如果范数增长太大，承诺方案的安全性可能会崩溃。Neo 被设计成一个三相循环，仔细管理这种范数增长。

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

图 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} 过程，无论是通过折叠还是累加，都会导致一个单一的最终实例-证据对。这个对在计算上是有效的——它正确地代表了整个聚合签名集——但在传统意义上它并不简洁。证据组件仍然存在，并且为最终证明者所需，使得对象太大，无法直接进行链上验证。

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

1. 递归引擎： 一个为证明者效率而选择的折叠或累加方案。其主要目的是以低计算成本将多个陈述组合成一个。
2. 简洁性引擎： 一个最终的非递归 SNARK，用于生成一个紧凑且可高效验证的链上证明。

最终确定流程如下：

1. 最终的折叠实例-证据对被当作要证明的陈述。
2. 应用多项式交互式预言机证明（PIOP），例如 (Super)Spartan，将证明折叠证据知识的任务简化为一组多线性多项式评估声明。
3. 使用后量子多项式承诺方案（PCS），例如 BaseFold 或 WHIR，来证明这些评估。

这种混合架构分离了高效递归和最终简洁性的功能。它利用了每种方法的各自优势，构建了一个可扩展且能生成紧凑链上证明的系统。

工程挑战：证据管理

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

这个问题可以在协议层使用一种称为证据分块的技术来解决。这种方法通过改变证据的处理方式来减轻带宽需求：

1. 对块进行承诺： 大的证据不被视为一个整体对象，而是被分割成多个更小的、大小恒定的向量。然后证明者单独对每个块进行承诺。

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

3. 高效验证： 虽然这种方法增加了递归验证者必须处理的承诺数量，但像 Neo 这样的方案被设计成能够高效处理这种情况。对证据块的承诺可以在不给验证器电路引入显著复杂性或成本的情况下进行折叠。

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

权衡：基于格子 vs. 基于哈希的原语

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

• 安全假设： 这是基于哈希的方案的主要优势。它们的安全性仅依赖于密码学哈希函数的性质，通常被建模为随机预言机。这是一个最小且广泛信任的假设，尽管是针对折叠/分裂累加。相比之下，基于格子的方案依赖于诸如模块短整数解（Module-SIS）问题之类的结构化假设。虽然被强烈认为是后量子难解的，但特定格子参数化的实际安全性是一个活跃且不断发展的研究领域。密码分析方面的持续进步，例如对混合攻击的实用改进，不断完善我们对具体安全级别的理解，并引入了较简单的基于哈希方法中不存在的长期风险因素。

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

• 专门特性： 像 Neo 这样的基于格子的构造可以提供独特的性能优势。例如，Neo 引入了“按位付费”的承诺成本，其中承诺一个证据的成本与其值的位宽成比例。这对于许多证据值很小的实际计算非常有利，而在基于哈希的系统中，通常所有数据都被视为全尺寸域元素进行 Merkle 哈希，因此不具备此特性。

架构权衡的比较分析

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

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

结论

以太坊共识层向后量子签名方案的过渡需要一种递归聚合架构。这种架构的选择并非简单的决定：zkVM 和折叠方案各自呈现出独特的优势分布和工程挑战。

路径 A，以暴力 SNARK 递归为特征，通过在 zkVM 后面隐藏密码学复杂性来管理这种复杂性。这种方法简化了应用程序逻辑的开发，但通过要求证明者证明 VM 的执行轨迹，在递归步骤中引入了显著的、不可避免的计算开销。

路径 B，使用像折叠和累加方案这样的专用原语，通过为递归使用更高效的密码学引擎来设计高性能。这种设计将复杂性从密码学核心推到 P2P 协议层，协议层必须解决诸如证据数据可用性之类的挑战。

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

• 基于分隔符的参与承诺用于后量子证明聚合
• 为什么以太坊需要一个动态可用协议

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