密碼學的累加器基于RSA 有希望實現共識節點的分工存儲

來源:區塊網 | 2019-11-01 15:20:34 |

拖更很久,這次從 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 年代的密碼學累加器技術會繼續進化,并出現工業級的開源代碼實現,最終成為我們工具箱里一個功能強大的新武器。

其實,密碼學領域里像累加器這樣被埋沒多年的“黑科技”還有很多。為了讓這些“黑科技”不再被繼續埋沒,有夢想的少年們一起來搞密碼學吧~(Conflux研究組)

除非特別注明,本站所有文章均不代表本站觀點。投訴QQ:55313 8779
网络游戏赛车