後量子特徵聚合：一種摺疊方法

作者： 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的解決方案雖然在當前任務中性能可能稍遜，但它提供了一個靈活的基礎設施，可以滿足協議未來的其他需求；而專門的折疊方案則代表了一種高度優化但可能應用範圍有限的解決方案。本文旨在闡明其中涉及的基本權衡，並為正在進行的討論提供一個結構化的框架。