重新審視後量子內存池中的 Falcon 簽名聚合技術

作者：Antonio Sanso @asanso, Thomas Thiery @soispoke, Benedikt Wagner @b-wagn

摘要： 本文在不同的金鑰恢復與聚合假設下，比較了使用 Falcon 簽章（定義於 Falcon 規範）的交易簽章與聚合簽章的大小。

導言

以太坊的後量子（PQ）工作 最近已從長期研究轉向更具應用性的研究與工程努力。隨著後量子交易簽章距離部署越來越近，一個限制變得顯而易見：後量子簽章的體積龐大，其成本在網路頻寬（例如：記憶體池傳播）與節點儲存需求方面感受最為深刻。

Falcon 簽章方案 仍然是一個極具吸引力的參考對象，因為它被 NIST 選中進行標準化，且與其他後量子替代方案相比，其簽章相對精簡。

然而，即使是 Falcon，當許多交易共存時，其簽章大小（666 位元組）所產生的記憶體池與儲存成本，也與 ECDSA（< 100 位元組）截然不同。這激發了人們對聚合（特別是在記憶體池或區塊構建層級）的重新關注，將其視為在現實假設下值得檢驗的假設。

在本文中，我們使用標準 Falcon 方案對 Falcon 簽章聚合 進行了定量分析，比較了在不同的公鑰恢復與聚合假設下，簽章與聚合簽章的總大小，旨在釐清與後量子以太坊交易相關的權衡。

這裡探討的核心問題是：在什麼時候、以及在什麼條件下，在記憶體池中聚合後量子簽章能顯著減少交易數據的總大小。

先前工作

雖然前量子簽章通常具有原生聚合的代數結構（例如：BLS 簽章），但後量子方案的聚合通常更為複雜。

Falcon 及相關基於格（lattice-based）的簽章聚合已在先前的密碼學與以太坊相關研究中被探討，包括一篇研究使用 LaBRADOR 證明系統進行聚合的論文，該研究以非顯著的聚合與驗證開銷為代價，實現了較為精簡的聚合簽章。

以太坊研究社群中的相關討論檢視了區塊鏈環境下基於格的簽章聚合，並在一篇 ethresearch 貼文中強調了關於證明大小、驗證時間和可實施性之間的實際權衡。

免責聲明：我們在此不考慮 SPHINCS+ 或 Dilithium 簽章（它們比 Falcon 簽章更大）。本文僅專注於 Falcon 及其在以太坊相關假設下的聚合特性。

關於後量子以太坊交易簽章的更廣泛背景，包括先前對 Falcon 和帳戶抽象（Account Abstraction）的討論，請參閱之前的系列文章：第一部分、第二部分 和 第三部分。

為什麼選擇 Falcon？

Falcon 已被 NIST 選中進行標準化。在這些入選的方案中，它擁有最小的簽章大小，且其聚合性也在文獻中得到了研究。

如上圖所示，Falcon 在此討論中特別具有吸引力，因為在 NIST 選定的後量子簽章方案中，它結合了相對較小的簽章大小與較有利的聚合特性。特別是，Falcon 是少數幾個能以與以太坊式交易流水線相關的方式探索聚合的實際候選方案之一。

我們強調，本文並非主張以太坊必須使用 Falcon，而只是研究如果我們使用 Falcon 會發生什麼。

Falcon 快速回顧

粗略來說，Falcon 的驗證方程形式為 H(m,r) = s_1 + s_2 h，此外還會檢查向量 (s_1,s_2) 的範數限制。這裡 h 是公鑰，H 是雜湊函數。簽章可以有兩種形式之一：

• 標準版本： 形式為 (s_2,r)，其中 r 是隨機鹽值（salt）。s_1 的值在驗證期間重新計算為 s_1 = H(m,r) - s_2 h。

• 金鑰恢復模式版本： 簽章為 (s_1,s_2,r)。在這種情況下，可以從簽章和訊息中重新計算出公鑰（及其雜湊值），參見 Falcon 規範 的第 3.12 節。

我們不深入探討這些簽章是如何生成的，也不討論這些對象存在於哪些域中，這兩者與我們的討論無關。

在全文中，我們假設在聚合時雜湊函數不會改變（例如：我們不會將其替換為 Poseidon2）。此外，我們假設鹽值不會被聚合。也就是說，在聚合簽章中，我們擁有所有 s_2（或 s_1,s_2）的聚合版本以及所有個別的鹽值。這是合理的假設（參見此處的討論），並且使使用簡潔證明（succinct proofs）的聚合更有效率，因為待證明的陳述純粹是代數性的，不涉及雜湊。

我們在全文中使用以下符號。當公鑰已知時，Falcon 簽章的大小為 S+R，其中 R 表示鹽值部分的大小，S 表示上述 s_2 的大小。當公鑰未知且僅有其雜湊值（即地址）可用時，根據上述金鑰恢復機制，簽章大小增加到 \tilde{S} + R，其中 \tilde{S} > S。

地址表示為公鑰的雜湊值，大小為 h，而完整公鑰的大小為 p。我們用 N 表示所考慮的交易數量。

我們用 a_N 表示聚合簽章大小，它取決於聚合簽章的數量 N 並包含鹽值。a_N 的具體數值可以使用先前關於 Falcon 聚合研究（論文）提供的腳本計算。在我們的分析中，我們使用了該儲存庫的分支版本，其中也包含用於生成本文圖表的代碼。

使用 Falcon 的變體方案

我們現在比較三種不同 Falcon 使用變體的總儲存成本。請注意，雖然我們討論的是儲存，但同樣的情況也適用於頻寬。

案例 1：具備金鑰恢復，無聚合

在這種情況下，我們使用金鑰恢復模式的 Falcon 版本（見上文），這意味著可以從簽章中重新推導出公鑰，進而推導出其雜湊值（地址）。因此，對於每筆交易，我們需要儲存包含隨機數（nonce）的簽章和發送者的地址。具體來說，每筆交易儲存：

• 鹽值：R
• 簽章（不含鹽值）：\tilde{S}
• 總計： N(\tilde{S}+R)

發送者地址不顯式儲存：它是在驗證期間從簽章中恢復的，類似於以太坊目前從 ECDSA 簽章中恢復發送者的方式。

案例 2：無金鑰恢復，無聚合

如果我們改用標準 Falcon 版本（無金鑰恢復，見上文），則可以節省簽章大小，但需要額外顯式儲存公鑰。我們不需要儲存地址，因為地址可以從公鑰中推導出來。具體來說，每筆交易儲存：

• 公鑰：p
• 鹽值：R
• 簽章（不含鹽值）：S
• 總計： N(p+S+R)

案例 3：無金鑰恢復，具備聚合

現在，假設我們聚合簽章，且 N 個簽章的聚合大小為 a_N。那麼，我們不再需要儲存個別簽章。具體來說，每筆交易儲存：

• 公鑰：p
• 鹽值：R

此外，我們有一個大小為 a_N 的聚合簽章。

• 總計： N(p+R) + a_N

註 1： 在下方的腳本中計算 a_N 時，我們以黑箱方式調用了來自 使用 LaBRADOR 的 Falcon 簽章聚合 的腳本。當然，不僅 LaBRADOR 可以用於聚合，任何 SNARK 都可以。我們注意到，基於雜湊的 SNARK（目前在以太坊中較受青睞）比 LaBRADOR 更大，因此使用 LaBRADOR 是對聚合簽章大小的一個非常樂觀的估計。

註 2： 我們不考慮具備金鑰恢復的聚合情況，因為 Falcon 簽章聚合的研究 並未涵蓋此部分。這主要是因為此處待證明的陳述將涉及雜湊，且代數結構較少，這意味著其證明效率低於標準變體所考慮的陳述。

結果

我們計算了（代碼在此）三種案例在不同交易數量 N 下的總大小（以 KiB 為單位）。

案例 2 在整個範圍內都是最昂貴的。每筆交易都攜帶一個完整的公鑰 (p) 和一個標準簽章 (S + R)，因此總大小增長迅速。

案例 1 較便宜，因為金鑰恢復消除了儲存完整公鑰或地址的需求，因為兩者都可以從簽章本身恢復。

案例 3 用一個大小為 a_N 的單一聚合簽章取代了 N 個個別簽章。但每筆交易仍需要一個完整的公鑰和一個個別鹽值，因此固定的證明開銷使得案例 3 在 N 較小時（~50 KiB）比案例 1 更貴。隨著 N 增加，較低的邊際成本開始佔優，案例 3 在 N \approx 200 附近與案例 1 交叉（圖中虛線）。

即使超過了這個交叉點，聚合帶來的節省也相當有限。在當前以太坊典型的區塊大小（~250 筆交易）下，案例 3 僅比案例 1 節省一點點。差距擴大緩慢，只有當簽章數量遠超目前的單區塊水平時，聚合才會產生實質性的回報。

結論

我們的結果表明，案例 1（金鑰恢復，無聚合）可能是以太坊上基於 Falcon 的後量子交易的一個實際平衡點。它在目前的區塊大小下具有最低的儲存成本，且不需要聚合基礎設施，其簡單性使其成為最直接的部署路徑。

聚合（案例 3）最終確實在儲存上勝出，但僅限於大 N 的情況，且在目前典型的區塊大小附近，節省的空間仍然有限。

除了證明大小之外，聚合還引入了巨大的系統複雜性。必須有人執行聚合，且在區塊時間內生成數百個簽章的證明可能在計算上非常昂貴。要在記憶體池層級實現頻寬節省，可能還需要像 基於遞迴 STARK 的頻寬高效記憶體池 這樣的架構，其中每個節點都充當證明者，並在 Gossip 傳播過程中增量地摺疊證明。

儘管如此，聚合技術正在不斷改進。諸如 Hatchi 之類的方案未來可能會減小證明大小，而最近關於 更快速聚合驗證 的研究則降低了檢查聚合證明的計算成本。如果這些改進得以實現，權衡關係可能會發生變化。

最後，我們注意到此分析專注於目前規範下的 Falcon。未來對方案本身的修改（例如：去隨機化）可能會改變每個簽章的成本並改變相對比較結果。我們將對此類修改的探索留待未來的工作。

        1 則貼文 - 1 位參與者

        [閱讀完整主題](https://ethresear.ch/t/revisiting-falcon-signature-aggregation-for-pq-mempools/24431)