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