拖更很久，這次從 CRYPTO 2019 會議上一篇很有意思的論文出發，簡單地介紹一下密碼學中的累加器（Accumulator）對於區塊鏈擴容的價值和意義"
今年以贊助商代表的身份參加美密會，很欣喜地看到與區塊鏈相關的研究工作已經佔據了相當的份額：
除了一個 Blockchain workshop 和一個單獨的 “SNARKs and Blockchains” Session 以外，在其他的 “Zero knowledge”“Proofs of storage”“Memory Hard functions and Privacy Amplification” 等幾個 Session 也有不少與區塊鏈相關的研究工作發表。
在 CRYPTO 2019 收錄的所有論文中，我認為最有趣的一個是有斯坦福大學的 Dan Boneh， Benedikt Bünz 和 Ben Fisch 合作的《Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains》[1]。
接下來我就從這篇文章出發討論一下 Accumulator 的前世今生以及該技術對於區塊鏈擴容的價值和意義。
背景介紹
中本聰在設計比特幣的時候，透過區塊大小和出塊時間將比特幣的吞吐量限制在一個非常低的水平（1MB/10min），一個重要的考慮就是儲存空間的限制。
即便如此，比特幣從創始塊以來所有交易和區塊構成的區塊鏈歷史已經超過 200GB，且還在以每個月 4～5GB 的速度增長；比特幣網路的未花費交易集合（UTXO）的大小也已接近一億，佔用空間超過 6GB。
作為區塊鏈 2.0 的代表，支援智慧合約的以太坊的“世界狀態”則更為巨大。
以太坊現在有超過八千萬個地址，僅僅是儲存這些地址的基本資訊（每個地址至少要約 100B 用來儲存賬戶地址、餘額、nonce、狀態根（state root）等）就已經需要近 10GB 的空間了，算上智慧合約的程式碼和內部狀態則佔用的空間還要再多十倍以上。
而上述資料僅僅是在使用者數量不多、共識吞吐量不到 20Kbps（以簡單轉賬交易計算，最多不超過 30 TPS —— Conflux 在 20 Mbps 的測試網路條件下可以實現 9.38Mbps 的共識吞吐量[2]）的情況下得出的。
如果想要把區塊鏈的吞吐量提升到數千 TPS （與 Visa 相當）的水平，則儲存方面需要承受高兩個數量級的壓力；如果要支援上億使用者大規模使用智慧合約，則地址數量恐怕要超過十億，相應的狀態儲存也至少要比現在多幾十倍。
因此，區塊鏈歷史和狀態的儲存問題是繼共識演算法以後又一個擋在區塊鏈擴容之路上的攔路虎。
在傳統的分散式計算和分散式資料庫場景中，可以透過磁碟陣列（RAID）和雲端儲存技術以較低成本實現高可靠性的大規模資料儲存。
但是這些設計的前提是提供服務的各個節點都是可信的，只存在宕機的風險而不會出現拜占庭錯誤，即沒有惡意的攻擊。
以比特幣為代表的區塊鏈為了在有拜占庭錯誤的前提下實現高可靠性，採用了每個節點（本文中節點均指參與共識的“全節點” full node——“Light nodes aren’t nodes”）儲存一份完整資料的方案（類似 RAID 1）。
因此，區塊鏈網路中的所有交易歷史實際上會被儲存幾千甚至上萬份副本，獲得極高可靠性的同時也付出了不菲的成本。
此外，新節點加入的時候必須耗費數天時間下載並驗證自創始塊以來所有的歷史資料，變相抬高了新節點加入的門檻，降低了區塊鏈系統的去中心性。
學術界和工業界早已注意到區塊鏈上儲存成本過高、擴容困難的問題，並提出了很多降低鏈上資料儲存成本的提案。
其中流傳比較廣泛的是各種各樣的分片（Sharding）、側鏈、多鏈、甚至跨鏈方案。
這些方案的基本原理都是把區塊鏈上的地址、交易和狀態按照一定的方式分組，每組節點只負責處理和驗證全網中的一部分交易，因而也只需要儲存自己分組對應的那部分資料即可。
共識分片（或者說分組）方案的優點是簡單易懂，實現起來技術相對比較簡單。而這類方案的缺點也很明顯：無論何種形式的分片或是分組，都必然會影響區塊鏈系統的安全性，因為不再是每筆交易都被所有節點驗證和儲存了——除非區塊鏈共識的每個參與者都同時執行多個節點，且保證在每個分組內都有至少一個節點。
不過如果要求共識的參與者們都有能力和資源同時維護很多節點，必然會顯著降低整個區塊鏈系統的去中心化程度。
無狀態區塊鏈與成員性證明
另一種降低儲存成本的方案就是採用密碼學技術實現的“無狀態區塊鏈”（Stateless Blockchain）。
以 UTXO 模型為例，節點驗證一筆交易是否合法其實很簡單，只需要交易的發起者證明作為交易的所有輸入都在當前的 UTXO 集合中，且交易金額和簽名都合法即可。
一筆交易的金額和簽名是否合法非常容易檢查，所以關鍵在於交易發起者向驗證者提供“該輸入是當前 UTXO 集合中的元素”的成員性證明（membership proof）。
如果驗證者（節點）持有一份當前的 UTXO 集合，那麼交易的發起者只需提供作為交易輸入的幣的來源（通常為收到這筆錢的交易的雜湊值），驗證者即可在自己的 UTXO 集合中檢查是否有相應條目。這裡驗證者維護一份 UTXO 集合是充分但不必要的。
例如驗證者只儲存了當前的 UTXO 集合的默克爾樹根節點（Merkle Root，既 Merkle Tree 的根節點處儲存的雜湊值），則交易的發起者為了證明交易的合法性，可以為每個輸入附帶一個標準的默克爾樹的成員性證明（Merkle Proof）。
該證明包括從成員葉子節點到樹根整條路徑上所涉及的所有中間節點的雜湊值。
當然，Merkle Root 本身並不是一個足以代替 UTXO 的方案。
因為一來 Merkle Proof 的長度比較長，至少是原本輸入長度的三四十倍（取決於 Merkle Tree 的高度和寬度），這意味著同樣的共識吞吐量下會大幅降低 TPS；
二來更新 UTXO 集合需要重新計算 Merkle Root，而根據交易的輸出（接收方地址）插入新資料往往要用到幾乎整個 Merkle Tree 和 UXTO 集合的資料。
所以為了更新對應於當前 UTXO 的 Merkle Root，共識節點要麼在本地儲存大量資料，要麼在用到時再向別的節點詢問需要的資料。
這時候就輪到我們這次要講的 密碼學累加器（Cryptographic Accumulator）出場了。
基於 RSA 的密碼學累加器
密碼學累加器最早是由 Josh Benaloh 和 Michael de Mare 提出的，原始論文《One-way accumulators: A decentralized alternative to digital sinatures (extended abstract) 》[3] 於 1993 年發表在歐洲密碼學會議（EUROCRYPT）上。這篇論文最初就是為了解決區塊鏈上的資料可訪問性問題而作的。
對！你沒看錯！1993 年的論文，解決了一個區塊鏈的問題！
被解決的問題實際上源自 1991 年的一篇論文。那篇論文首次提出了字面意義上的“區塊鏈” [4] ——不帶共識演算法、工作量證明等，僅用於為檔案提供時間戳功能。
十多年後，區塊鏈才被中本聰同志拿來作為比特幣的基礎 [5]。
順便提一下，工作量證明的想法其實也是上個世紀90年代初就被提出用於抵抗垃圾郵件的，儘管中本聰在比特幣的白皮書裡為此引用的是一篇 2002 年的論文。
改進的累加器方案
今年發表在 CRYPTO 上的 Dan Boneh，Benedikt Bünz 和 Ben Fisch 的工作（下稱 BBF 方案）在非成員性證明和驗證速度這兩點都做出了重大改進。
使用 BBF 累加器方案，就可以實現一條無狀態的區塊鏈。
仍以 UTXO 模型的區塊鏈為例，每次節點驗證一筆交易合法後即可更新 UTXO 聚合器：先利用交易本身附帶“交易輸入屬於當前 UTXO 集合”的成員性證明從當前 UTXO 聚合器中刪除相應的輸入，然後再按照交易的輸出將相應條目加入後得到新 UTXO 集合的聚合器。
在上述整個過程中，節點都不需要用到任何其它交易的資訊（Merkle Tree 可做不到這點），因此只需維護一個當前 UTXO 的聚合器（摘要）而不用存 UTXO 中的任何一個元素。實在是鵝妹子嚶²！
更進一步的，處理整個區塊中的很多筆交易時，不需要對每筆交易單獨進行一次更新，而是可以處理完所有交易以後一次性地更新 UTXO 聚合器。
這個性質除了可以大大提高效率外，稍加改動即可實現類似於 Mimblewimble 的匿名性。真的是太鵝妹子嚶了！
看到這裡是不是已經迫不及待地想用 Accumulator 這個“新歡”換掉“舊愛” Merkle Tree 了？
且慢，上面還只說了累加器好的一面，還是等看完接下來這段以後冷靜一下再做決定。
密碼學累加器的侷限
上面講的基於 RSA 的累加器具有結構簡單、效能優異（至少看上去是）的優點，但是實際實現起來還有很多必須注意的地方。
總之就是這個選取的過程相當複雜難懂，稍不小心就會出錯。技術細節還請參考相關論文。
再次，在工程實現上累加器複雜且難度很高，遠不如 Merkle Tree 簡單可靠。
Merkle Tree 的結構足夠簡單，用不了十分鐘就能給一個訓練有素的程式設計師講明白，即使是比較複雜的 Merkle Patricia Trie 也花不了半天功夫，再花個不到一天時間就足夠寫一個功能正確的實現了。
而如果要向沒有深厚的密碼學背景知識的程式設計師講明白累加器的原理和引數選擇的邏輯，再講明白 BBF 方案裡用到的簡短非互動式證明系統，最終實現出一個累加器，恐怕半年時間都不夠用——而且寫出來的程式碼幾乎可以肯定是有 bug 的。
最後， RSA 假設是一個經典的可被量子計算機攻擊的例子。
近年來量子計算的發展如火如荼，取得了很多里程碑式的進展：Google 剛剛於上個月宣佈實現了“量子霸權”，IBM 也在向著“量子優勢”發力，其它還有很多巨頭比如微軟和國內的 BATH 都在發展量子計算。
因此，基於 RSA 假設實現的累加器從誕生的那一刻起生命就已經進入了倒計時的狀態——按照量子摩爾定律估計，2048位的 RSA 演算法大約也就還能再堅持五十多年了。
那麼除了基於 RSA 的累加器以外，還有沒有其它方式實現的累加器呢？
其實也是有的。今年早些時候 MIT 數字貨幣研究所的 Thaddeus Dryja 發表了一篇題為《Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set》的論文 [6]，就是用一組大小不同的 Merkle Tree 實現累加器的功能，可用於 UTXO 模型的區塊鏈在儲存方面擴容。
Utreexo 實現的累加器功能和效能比 BBF 方案略差，主要優勢在於構造簡單易懂，實現起來也很方便。
然而，即便是有了方便的累加器，直接用來做無狀態區塊鏈也還是不夠的。
累加器的一個重要特性是其證明必須要隨著當前的累加器狀態而更新，這點與 Merkle Tree 類似——Merkle Proof 只對固定的 Merkle Root 有效，如果 Merkle Root 有更新的話證明必須重新做。
也就是說，即便用上累加器，UTXO 或者賬戶狀態對應資料的成員性證明也必須隨著區塊鏈的增長而不斷更新。只由使用者自己離線儲存一個成員性證明是不行的。
累加器與區塊鏈的未來
儘管現有的密碼學累加器方案還不完美，也沒有現成的工業級的程式碼供我們直接使用，但是 BBF 方案依然向我們展現了累加器的巨大潛力和光明的前景。
至少採用累加器以後，有希望在共識節點之間實現儲存上的分工合作，每個節點只需儲存一部分資料。
對於涉及節點本地沒有儲存的資料的交易可以選擇不打包，等別的節點打包以後只需驗證相應的證明並更新累加器狀態即可。這樣已經足以在很大程度上緩解節點的儲存壓力了。
對於證明隨狀態更新的問題，按照現有的 BBF 方案可以先讓儲存了所有交易資料的第三方服務商（類似於以太坊的 Archive Node）收費提供代辦證明的服務。
至於是否可以透過更好的構造降低生成和更新證明的成本，使得任何節點都不需要儲存完整的資料（特別是隨時間線性增長的交易歷史）呢？
這一問題還要留給密碼學家們繼續研究。密碼學累加器除了幫助區塊鏈在儲存方面擴容以外，還可以用在“互動式神諭證明”（IOP， Interactive Oracle Proofs）系統裡，幫助提高證明的效率。
例如零知識證明的 zk-STARK 和 Ligero 方案等典型的 IOP 系統，使用 BBF 方案的累加器後均可以顯著地縮短證明長度和驗證時間。
眾所周知，目前的零知識證明系統沒有被大規模使用的一個主要原因就是效率太低。密碼學累加器有望推動零知識證明向實用化更進一步。
相信在不遠的將來，源自上世紀 90 年代的密碼學累加器技術會繼續進化，並出現工業級的開原始碼實現，最終成為我們工具箱裡一個功能強大的新武器。
其實，密碼學領域裡像累加器這樣被埋沒多年的“黑科技”還有很多。為了讓這些“黑科技”不再被繼續埋沒，有夢想的少年們一起來搞密碼學吧～
參考文獻：
[1] Dan Boneh, Benedikt Bünz, Ben Fisch. Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains. CRYPTO 2019.
[2] Chenxing Li, Peilun Li, Dong Zhou, Wei Xu, Fan Long, Andrew Yao. Conflux: A Decentralized Blockchain with Near Optimal Throughput Latency. In submission.
[3] Josh Benaloh, Michael de Mare. One-way accumulators: A decentralized alternative to digital sinatures (extended abstract) . EUROCRYPT 1993.
[4] S. Haber, W.S. Stornetta. How to time-stamp a digital document. Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
[5] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. 2008.
[6] Thaddeus Dryja. Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set.
