后量子特征聚合：一种折叠方法

作者： Thomas Coratger 、 Srinath Setty

引言：后量子特征转变

在以太坊等权益证明（PoS）系统中，数位签章为数十万个验证者提供问责机制，从而保障网路安全。如此庞大的验证数量带来了巨大的可扩展性挑战：如何有效率地验证如此多的签章？为此，以太坊的共识层采用了BLS签章方案，这项选择对于实现网路的可扩展性至关重要。

BLS 的优点在于其独特的代数结构，它允许使用密码配对（ e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T e : G 1 × G 2 → G T ）进行高效的签章聚合。配对映射的双线性特性带来了一个显著的性质：只需一个方程式即可验证n个签名的有效性。

在以太坊的实际实现中，聚合签章会附带一个位元域（聚合位） ，用于标识委员会中哪些验证者参与了验证。验证者使用此位元域计算聚合公钥∑ pk_i ∑ p k i，然后再执行最终的加密检查。虽然最终检查是常数时间的（两次配对），但整体验证成本包含一个用于建立聚合公钥的线性时间步骤：

该模型对于可扩展性至关重要， Eth2 Book对此进行了非常详细的阐述，但 BLS 的安全性依赖于一些量子电脑无法解决的问题。向后量子替代方案（例如基于哈希的 XMSS）的必要过渡，又重新引入了可扩展性挑战。 XMSS 缺乏 BLS 的代数特性；其签章更大，验证成本更高，使得对每个区块数千个签章进行逐一验证变得不切实际。

解决方案是一种新型的签章聚合方式，它利用简洁知识论证（SNARKs）为整套签章产生一个简洁的单一证明（虽然为了简便起见，通常被称为恒定大小，但实际上，基于现代杂凑的SNARKs产生的证明在技术上是语句大小的多对数级的）。由于验证者分布在点对点网路中，因此单一节点收集所有签名是不切实际的。因此，聚合必须以去中心化的方式进行，不同的节点聚合重叠的签名子集。这种「证明的证明」的需求自然而然地导致了递归架构的出现。本文比较了实现这种递归的两种主要范式：

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

我们分析每种方法的机制、性能和权衡，为以太坊的后量子签章聚合之路提供资讯。

聚合框架

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

美国劳工统计局资料汇总实务：现状

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

验证者按槽位分组组成委员会。当委员会中的验证者创建证明时，签署物件包含一个名为`aggregation_bits` 的栏位。这是一个位元列表，其中每个位置对应于该验证者在该特定委员会中的索引。创建证明的验证者将自己的位元设为 1。

之后，可以将来自不同验证者、对同一链视图进行验证的证明进行聚合。具体做法是将聚合位元 (aggregation_bits)进行位元或运算，并将个别 BLS 签章相加（如同椭圆曲线点的加法运算）。结果是一个包含组合位元域和聚合签章的单一证明物件 (Attestation) 。为了验证该证明，节点只需将最终聚合位元 ( aggregation_bits )中位元设为 1 的验证者的公钥相加，即可重构聚合公钥。该系统仅需一次高效的配对检查即可验证数百个签名，但关键在于它保留了所有参与者的准确记录。

在后量子系统中利用比特域追踪参与度

后量子框架继承了对精确参与追踪的这一关键需求。仅证明一组匿名签名的有效性不足以满足共识协议的要求。因此，该系统仍然采用位元域来识别每个签署者。

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

如图 1 所示，每个后量子签章都关联一个位元域，该位元域将签署者的全域索引标记为 1。当聚合多个证明时，它们对应的位元域会透过位元或运算进行组合。产生的聚合位域会作为 SNARK 的公开输入，从而确保最终证明能够准确地证实以下声明：“由该特定位域指示的验证者均已提供有效签名。”

图 1 292×224 7.72 KB

进阶设计：聚合和合并

该系统基于两种核心加密操作构建，这两种操作构成了递归构造的基础。这些操作允许工作负载进行分配，然后逐步组合。

• 聚合：这是初始的非递归步骤。聚合节点从验证器子集中收集一批原始 XMSS 签章。它分别验证每个签名，然后产生初始 SNARK 证明，证明它们的集体有效性。为了验证这些签章并建立正确的位元域，每个聚合操作节点都必须能够存取全域验证器登录。此注册表将每个验证器的索引对应到其对应的公钥，作为必要的公共输入。此操作将一组庞大且验证成本高的签章转换为单一紧凑的证明对象。

• 合并：这是递归步骤。聚合节点接收两个现有的证明，每个证明都验证了一组不同的签名的有效性，然后将它们合并。输出是一个新的单一证明，它提供的密码学保证与验证了两个输入证明中所有底层签名的保证相同。此操作是可扩展性的关键，允许有效率地合并证明。

为了清楚解释加密过程，我们将聚合建模为逻辑递归树，如图 2 所示。这种树状结构是一种有用的抽象，因为它允许我们清晰地分析两个核心加密步骤——聚合和合并——它们是证明系统的基本构建块。

在实践中，这种逻辑模型在一个动态的对等网路（P2P）中实现。为了因应高频宽需求，验证者集合被划分为多个子网路。验证过程在这些子网路内并行启动，首先使用聚合（Aggregate）操作从本地签名集产生初始证明。如图 2 所示，每个Agg （Aggregate）操作都依赖全域状态（验证者登录）。这意味著聚合器必须查询该全域注册表，以取得与其正在验证签署的验证者对应的公钥，并正确更新所产生证明的聚合位元域。这些初始证明随后在整个网路中传播。随著聚合器节点接收到证明，它们执行合并（Merge）操作，将证明合并，从而验证越来越大的验证者集合。这种分散式合并持续进行，直到产生一个最终证明，该证明代表了所有参与验证者集合的验证结果。

图 2 815×499 32.4 KB

该设计的关键成果在于，只需将最终证明提交到区块链。这个大小恒定的单一物件取代了在链上处理数千个单独签名的需要。所选的加密范式必须能够有效率地支援聚合（Aggregate）和合并（Merge）操作。接下来我们将探讨的根本架构差异，正是这两种操作的具体实作方式。

路径 A：暴力 SNARK 递归

实作递归最直接的架构范式是将一个完整的 SNARK 验证器置于另一个 SNARK 电路中。在这个模型中，合并操作本身就是一个 SNARK，用来证明其他 SNARK 的验证结果。这种「证明验证证明」的方法虽然计算量较大，但却是实现递归的直接途径。

核心机制：证明验证证明

\texttt{ Merge }操作的基本任务是接收两个输入证明\text{proof}_A proof A和\text{proof}_B proof B ，并产生一个新的输出证明\text{proof}_{\text{out}} proof out ，以证明这两个输入证明的有效性。 \texttt{Merge} SNARK所证明的关系可以形式化地表示为：

这里， V_V代表 SNARK 系统的验证演算法。为了产生证明out ，合并步骤的证明器必须在新证明的算术电路中，对两个输入证明执行验证演算法V _V 的全部逻辑。这需要对验证器的每个加密步骤进行算术运算，包括杂凑计算、多项式承诺检查和域运算。现代基于哈希的证明系统非常适合这种需求，因为它们的验证器不需要昂贵的配对操作。

zkVM抽象的作用

这种方法的主要挑战在于验证电路的复杂性。现代SNARK系统的验证器涉及一系列复杂的密码操作，最终形成一个庞大且高度复杂的约束系统。手动建置、审计和维护这样的电路实际上是不可能的，而且极易出错。

这时，零知识虚拟机器（zkVM）就显得格外必要。 zkVM 作为抽象层，能够管理这种复杂性，使开发人员能够使用熟悉的程式设计模型，而无需受限于底层电路。其工作原理如下：

1. 进阶逻辑：开发人员无需设计电路，而是使用简单的高阶指令集架构 (ISA) 为验证器的逻辑编写程式。该程式可以以统一的方式表达聚合(Aggregate)和合并 (Merge)步骤的逻辑。

2. 加密预编译： zkVM 配备了预先编译的、高度最佳化的电路，用于处理昂贵的加密原语。诸如 POSEIDON哈希置换之类的操作可以作为高级程式中的单一高效指令呼叫。

3. 编译和执行追踪：编译器将高阶程式翻译成 zkVM 的字节码。运行该程式时，zkVM 的证明器会产生完整的执行跟踪，记录虚拟机的每一次状态转换——从指令获取到记忆体存取。然后，整个追踪过程会自动转换为最终的、大规模的约束系统，并由 SNARK 进行验证。

zkVM 中的 AggregateMerge程序

zkVM 模型允许在单一统一程式中同时实作聚合(Aggregate)和合并 (Merge)操作。此类程式的简化版本，我们称之为聚合合并 (AggregateMerge) ，其公共输入包括所有验证器公钥清单以及指示此步骤中要验证哪些验证器的位元域。私有输入则包括原始 XMSS 签章和现有 SNARK 证明的混合。

该程式的逻辑如下：

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

然后，zkVM 证明器为整个 AggregateMerge程式的执行产生一个 SNARK 证明。

效能概况和瓶颈

基于 zkVM 的方法的主要缺点是证明器会产生巨大的计算开销。证明器不仅要证明应用程式逻辑（即验证签章和证明），还要证明虚拟机器本身执行的正确性。这种虚拟机器开销涉及对 CPU 的每个内部步骤进行算术运算，从指令获取和解码到暂存器更新、记忆体存取以及跳转等控制流逻辑。

这种额外的工作负载使得每个合并步骤的计算量都非常大，并直接导致更高的延迟，这在对时间要求严格的P2P聚合网路中可能成为瓶颈。这与「固定程式」递归形成鲜明对比，在「固定程式」递归中，验证电路在编译时针对单一预定程式进行专门设计，因此无需通用CPU架构及其相关的开销。

然而，值得注意的是，基于哈希的SNARK的性能格局正在快速变化。如果底层证明系统的原始表现够高，「够好」原则或许适用。证明技术的最新进展展现了极高的吞吐量。如果这种趋势持续下去，zkVM的持续开销或许可以与开发者体验和灵活性带来的优势相抵消，使其成为即使在时间敏感型应用中也可行的选择。尽管证明器成本较高，但现代基于哈希的SNARK可以产生非常紧凑的证明，从而能够满足链上大小目标。

路径 B：专用递归原语

暴力递归的替代方案是利用专为此任务设计的密码学原语：折叠和累积方案。这个范式并非在电路中验证完整的SNARK，而是直接操作证明的底层数学语句。它提供了一种高效的密码学捷径，将多个计算完整性声明合并为一个等价的声明，从而显著降低了证明者在每个递归步骤中的工作量。

实例见证框架

此方法的核心是实例-见证对的概念，记为(x, w ) ，它代表特定 NP 关系R的计算语句。实例x包含语句的公开数据，而见证w包含满足该语句的可能不为人知的秘密数据。这种统一的结构同时用于聚合(Aggregate)和合并 (Merge)操作。

• 聚合步骤：此操作建立第一个实例-见证对。关系R是 XMSS 签章验证演算法。实例x由公共资料（讯息、位元域和相关公钥）组成，见证w由秘密资料（原始 XMSS 签章）组成。输出是一个初始的实例-见证对，可以进行折叠或累积。
• 合并步骤：此操作接受两个实例-见证对(x_1, w_1 )和( x_2 , w_2 ) ，并使用轻量级协定计算相同关系R 的单一折叠对(x_{\text{folded}}, w_{\text{folded}})。此过程的计算成本远低于在电路中运行完整的SNARK验证器。此外，对于相同关系，折叠证明器的计算成本也低于 SNARK 证明器。

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

基于晶格的折叠

折叠方案是一种协议，它将两个关系实例合并成一个相同的新实例。 Neo 是一个著名的后量子折叠方案范例，它基于看似合理的后量子晶格假设。

基于格的密码学面临的关键挑战是管理见证人的范数。执行诸如线性组合之类的密码学操作会导致该范数增长。如果范数成长过大，承诺方案的安全性就会被破坏。 Neo 的设计围绕著一个三阶段循环，该循环能够有效地管理这种范数成长。

在我们的用例中，聚合步骤会为名为矩阵 CCS (MCS)的关系建立一个初始实例-见证对，该关系代表 XMSS 验证电路。合并操作随后会取得这个新的 MCS 实例和一个正在运行的累加器（它是更简单的评估关系 ME 的一个实例），并执行 Neo 的循环（图 3 描述了此工作流程）：

图 3 824×450 65.3 KB

基于哈希的拆分累积

递归的另一种原语是分裂累积方案，它维护一个运作中的累加器，用于验证一组声明的有效性，这些声明甚至可以针对不同的关系。分裂累积方案和折叠方案是同时提出的。尽管它们之间存在一些具体差异，但这些差异与我们的阐述无关。合并操作对应于向此累加器新增一个新的声明。 WARP是后量子分裂累积方案的一个典型例子，它基于看似后量子的杂凑函数，并且专门设计用于最大限度地提高证明器的性能。

分批累积方案

分裂累积方案的核心思想是将累积器分成两部分：一个较小的公共实例部分和一个较大的私有见证部分。在每个递归步骤中，证明器（ P_{ACC} P A C C ）接受旧的累积器和一个新的断言，产生更新后的累积器，并产生该转换的简短证明。

至关重要的是，验证者（ V_{ACC} V A C C ）只需要新旧累加器的公共实例部分即可验证此转换证明。验证者永远不会看到或处理大型见证部分，这使得递归验证步骤极为轻量级。完整的见证仅在流程的最后由最终证明者（「决策者」）需要，决策者会产生链上单一 SNARK。

从电路到多项式：PESAT

在 WARP 框架中，累积的声明被表示为多项式方程式可满足性 (PESAT) 的实例。 WARP 不将计算表示为闸电路，而是将其表示为一组多项式方程，对于给定的实例和见证，所有方程的计算结果都必须为零。这是一个高度通用的框架，可以捕捉常见的约束系统，例如 R1CS 和 CCS。在我们的用例中，XMSS 签章验证演算法和位元域逻辑被编译成一个 PESAT 实例。

线性时间证明器

WARP 的主要优势在于其线性时间证明器。证明器的运行时间（以栏位操作和杂凑计算次数衡量）与计算规模呈线性关系。这对于证明器的效率而言是一项重大突破，避免了其他系统中存在的两大主要开销来源：

• 超线性成本 ( O(N \log N) O ( N log N ) ) 基于群的密码学，主要由大型多标量乘法所构成。
• 通用 zkVM 存在很大的恒定开销，它除了要证明其自身 CPU 架构的执行之外，还要证明其应用程式逻辑的执行。

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

最终确定：生成链上 SNARK

递归合并过程，无论是透过折叠或累积，最终都会产生一个单一的实例-见证对。这个实例-见证对在计算上是有效的－它正确地表示了所有聚合签章－但它并不像传统意义上的那样简洁。见证组件仍然存在，并且是最终证明者所必需的，这使得物件过于庞大，无法直接进行链上验证。

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

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

最终定稿流程如下：

1. 最后一个折叠的实例-证人对被视为待证明的陈述。
2. 多项式互动式预言机证明（PIOP），例如（超级）斯巴达，被应用于将证明折叠见证人的知识的任务简化为一组多线性多项式评估声明。
3. 采用后量子多项式承诺方案（PCS），例如BaseFold或WHIR ，来证明评估结果。

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

工程挑战：证人管理

该路径面临的一项重大工程挑战是跨 P2P 网路管理见证资料。任何合并步骤的证明器都需要存取待合并两个证明的见证资料。一种简单的实作方式需要传输这些庞大的见证数据，这可能会造成严重的频宽瓶颈。

这个问题可以透过协议层面的见证分块技术来解决。这种方法透过改变见证的处理方式来降低频宽需求：

1. 分块承诺：一个大型见证资料并非被视为一个整体，而是被分割成多个较小的、大小恒定的向量。证明者随后分别对每个分块进行承诺。

2. 资料块折叠：当两个证明被折叠时，折叠后的证明本身只是一个很小的向量。因此，递归步骤之间传递的加密状态保持紧凑且大小恒定，从而防止资料量的累积增长。

3. 高效验证：虽然这种方法会增加递归验证器必须处理的承诺数量，但像 Neo 这样的方案旨在有效地处理这种情况。对见证区块的承诺可以折叠，而不会给验证器电路引入显著的复杂性或成本。

该设计将挑战从加密限制重新定义为 P2P 资料可用性问题：确保聚合节点能够从网路中定位和获取所需的见证区块，以执行合并操作。

权衡取舍：基于格的演算法与基于哈希的演算法

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

• 安全假设：这是基于哈希的方案的主要优势。它们的安全性仅依赖密码杂凑函数的属性，通常将其建模为随机预言机。这是一个最小且被广泛认可的假设，尤其适用于折叠/分裂累积演算法。相较之下，基于格的方案则依赖结构化假设，例如模组短整数解（Module-SIS）问题。尽管人们普遍认为模组短整数解是后量子困难的，但特定格参数化的实际安全性仍是一个活跃且不断发展的研究领域。密码分析的持续进步，例如混合攻击的实际改进，不断加深我们对特定安全等级的理解，并引入了更简单的基于杂凑的方法所不具备的长期风险因素。

• 递归开销：这是基于格的方案的关键优势。在基于杂凑的系统中，递归的「合并」步骤需要在下一个证明中验证默克尔路径开集。而在基于格的方案中，折叠操作更偏向代数运算，直接合并数学语句，而无需验证完整的密码物件。这使得递归验证电路更加简单，从而显著降低了计算开销。

• 特殊功能：像 Neo 这样的基于格的构造可以提供独特的性能优势。例如，Neo 引入了「按比特付费」的承诺成本，即承诺一个见证值的成本与其值的位元宽度成正比。这对于许多见证值都很小的实际计算来说非常有利，而基于杂凑的系统通常将所有资料视为 Merkle 杂凑的完整栏位元素，因此不具备这种特性。

建筑权衡比较分析

在系统设计中，选择使用暴力递归还是专门的原语会带来不同的权衡。这两种方法的主要区别在于复杂性的放置位置——是在密码学证明基础设施中还是在点对点协定层——因此，效能和开发抽象之间的平衡也不同。下表总结了这两种架构路径之间的主要差异。

表1：递回聚合架构比较

结论

以太坊共识层向后量子签章方案的过渡需要一种递归聚合架构。选择这种架构并非易事：zkVM 和折叠方案各有其独特的优点和工程挑战。

路径 A 以暴力 SNARK 递归为特征，透过将加密复杂度抽像到 zkVM 之后来管理加密复杂性。这种方法简化了应用程式逻辑的开发，但由于要求证明者证明虚拟机器的执行轨迹，因此在递归步骤中引入了显著且不可避免的计算开销。

路径 B 使用折叠和累积方案等专用原语，并采用更有效率的递归加密引擎，旨在实现高效能。这种设计将复杂性从加密核心转移到 P2P 协定层，后者必须解决诸如见证资料可用性之类的挑战。

最终，以太坊的最佳发展路径尚未确定，目前仍是活跃的研究领域。这项决定将取决于zkVM和折叠技术的持续成熟度、对P2P网路动态的进一步分析、共识层的具体性能和安全需求，以及在通用性与专业化之间的长期价值权衡。基于zkVM的解决方案虽然在当前任务中性能可能稍逊，但它提供了一个灵活的基础设施，可以满足协议未来的其他需求；而专门的折叠方案则代表了一种高度优化但可能应用范围有限的解决方案。本文旨在阐明其中涉及的基本权衡，并为正在进行的讨论提供一个结构化的框架。