夏 清 ,竇文生 ,郭凱文 ,梁 賡 ,左 春 ,張鳳軍,2

1(區(qū)塊鏈技術與應用聯(lián)合實驗室(中國科學院 軟件研究所),北京 100190)

2(計算機科學國家重點實驗室(中國科學院 軟件研究所),北京 100190)

3(中國科學院 軟件研究所 可信計算與信息保障實驗室,北京 100190)

4(中國科學院大學,北京 100049)

5(中科軟科技股份有限公司,北京 100190)

自2009 年比特幣[1,2]系統(tǒng)出現(xiàn)以來,其底層區(qū)塊鏈技術逐漸受到來自學術界和產(chǎn)業(yè)界的關注,并獲得快速的發(fā)展.當前,區(qū)塊鏈技術已經(jīng)得到廣泛使用.例如,基于數(shù)字貨幣的跨境支付作為區(qū)塊鏈技術的一大應用場景,近年來已經(jīng)廣為人知并開始被商家接受[3];一系列基于區(qū)塊鏈技術的金融服務[4,5]、供應鏈技術[5,6]、政府治理[7]、游戲服務[8]等已經(jīng)出現(xiàn)并獲得成功運用.

區(qū)塊鏈作為一種鏈式數(shù)據(jù)結構,由不斷增長的區(qū)塊利用哈希指針前后鏈接而成.區(qū)塊鏈中的數(shù)據(jù)只能追加、不可刪除或篡改.區(qū)塊鏈系統(tǒng)是一個典型的分布式系統(tǒng),其中每個節(jié)點維護一份本地區(qū)塊鏈數(shù)據(jù)備份.在區(qū)塊鏈系統(tǒng)中,區(qū)塊鏈共識協(xié)議制定了一組每個節(jié)點必須遵守的規(guī)則,最終保證分布式系統(tǒng)中各節(jié)點區(qū)塊鏈數(shù)據(jù)備份的一致性.

區(qū)塊鏈共識協(xié)議分為兩個主要步驟:出塊節(jié)點選舉和主鏈共識.在出塊節(jié)點選舉階段,某個節(jié)點(或多個節(jié)點)成為出塊節(jié)點,提出新區(qū)塊.由于分布式網(wǎng)絡中可能存在的惡意節(jié)點及分叉塊的影響,其他節(jié)點在收到新區(qū)塊以后不能直接將其加入自己的本地區(qū)塊鏈中.所有節(jié)點需要利用主鏈共識對新區(qū)塊及其構成的主鏈達成一致.出塊節(jié)點選舉機制和主鏈共識共同保證了區(qū)塊鏈數(shù)據(jù)的正確性和一致性,從而為分布式環(huán)境中的不可信主體間建立信任關系提供技術支撐.

作為區(qū)塊鏈系統(tǒng)的核心組件,共識協(xié)議同時決定了區(qū)塊鏈系統(tǒng)的性能及安全性.例如,流行度最高的比特幣系統(tǒng)[9]采用概率性共識協(xié)議.為了保證區(qū)塊在大規(guī)模分布式系統(tǒng)中的廣泛傳播,比特幣系統(tǒng)將區(qū)塊大小限制為1MB,區(qū)塊間隔設置為10min,從而導致比特幣系統(tǒng)每秒只能處理約7 筆交易(比特幣區(qū)塊大小約1MB,區(qū)塊間隔維持在10min 左右,每筆交易大小約250 字節(jié),因此,理論上每秒交易數(shù)=(1×1024×1024÷250)÷(10×60)≈7).當交易量上升時,系統(tǒng)堵塞現(xiàn)象時有發(fā)生.此外,對于安全性要求較高的大數(shù)額交易,比特幣官方客戶端Bitcoin Core 推薦用戶等待隨后6 個區(qū)塊的確認(約1 個小時)[10],使其具有更高的概率安全性.

為了改善比特幣系統(tǒng)的性能,研究開發(fā)人員不斷對其共識協(xié)議進行優(yōu)化,比如縮短區(qū)塊間隔、區(qū)塊擴容等,然而這些優(yōu)化同時可能帶來對安全性[11-13]的負面影響.自從區(qū)塊鏈技術誕生以來,大量研究工作圍繞設計與分析共識協(xié)議開展,如Bitcoin-NG[11],Algorand[14],Byzcoin[15],Honeybadger[16]等,同時也形成了多個基于區(qū)塊鏈的系統(tǒng),如Ethereum[17],Litecoin[18],Hyperledger Fabric[19]等.

隨著區(qū)塊鏈研究工作的推進,研究人員開始對區(qū)塊鏈技術從不同方面進行梳理[20-23]:文獻[20]討論了比特幣和以太坊工作量證明機制的異同;文獻[21]討論了基于證明的共識協(xié)議,包括工作量證明、權益證明等,并比較了工作量證明和權益證明的異同;文獻[22]從激勵機制的角度討論了非許可鏈共識協(xié)議;文獻[23]按時間順序梳理了主要的區(qū)塊鏈共識協(xié)議.上述研究工作一般將區(qū)塊鏈共識協(xié)議視為整體討論,缺乏對共識協(xié)議的步驟劃分以及不同步驟間詳細比較分析.據(jù)前所述,共識協(xié)議分為出塊節(jié)點選舉和主鏈共識兩個主要步驟.這一分類視角在區(qū)塊鏈協(xié)議設計方面十分常用[2,14,15,24,25].基于對共識協(xié)議主要步驟的劃分,有助于研究及開發(fā)人員理解共識協(xié)議的運行流程.進而,通過比較各步驟采用機制,清晰準確地理解不同機制的優(yōu)劣.最后,不同步驟間的機制組合也可以為協(xié)議設計提供新的想法.

本文中,我們從區(qū)塊鏈共識的兩個主要步驟(出塊節(jié)點選舉和主鏈共識)對共識協(xié)議進行解耦分析.通過對每個步驟采用的機制進行綜合性梳理、對比和分析,觀察共識協(xié)議的發(fā)展趨勢,為研究人員和開發(fā)者提供有用建議.具體而言,在出塊節(jié)點選舉機制部分,我們主要圍繞目前已得到廣泛研究與應用的工作量證明和權益證明展開討論,總結工作量證明和權益證明機制存在的問題,從解決問題的角度討論了隨后出現(xiàn)的各種替代性證明機制.在主鏈共識部分,我們根據(jù)主鏈共識的性質,將主鏈共識分為概率性共識和確定性共識兩類.在概率性共識中,我們討論了各種主鏈選取規(guī)則,包括最長鏈規(guī)則[2]、GHOST[12]、包容性協(xié)議[26]等,并從概率性共識的持久性和活性角度對上述規(guī)則進行分析比較.在確定性共識中,我們首先討論了經(jīng)典的拜占庭協(xié)議[27]以及其應用到區(qū)塊鏈中需要解決的問題,隨后討論了各種基于拜占庭容錯協(xié)議達成一致的共識算法,包括Algorand 的BA*協(xié)議[14]、Byzcoin 的PBFT 協(xié)議[15]、Stellar 的SCP 協(xié)議[28]及Honeybadger[16],并從確定性共識的安全性和活性角度對各種協(xié)議進行分析比較.最后,我們總結了共識協(xié)議發(fā)展趨勢以及可能的研究方向,為未來研究提供參考.

本文第1 節(jié)介紹區(qū)塊鏈共識協(xié)議的運行流程以及區(qū)塊鏈系統(tǒng)的分類.第2 節(jié)描述出塊節(jié)點選舉機制,分析比較工作量證明機制和權益證明機制的現(xiàn)有工作.第3 節(jié)描述主鏈共識,并分析比較各種概率性共識和確定性共識.第4 節(jié)總結研究發(fā)現(xiàn)及未來的展望.

1 區(qū)塊鏈共識協(xié)議

區(qū)塊鏈共識協(xié)議屬于拜占庭容錯協(xié)議,保證區(qū)塊鏈網(wǎng)絡中誠實節(jié)點在惡意節(jié)點干擾下也能達成共識.在分布式系統(tǒng)中,依據(jù)系統(tǒng)對故障組件的容錯能力,共識協(xié)議分為崩潰容錯協(xié)議(crash fault tolerant,簡稱CFT)和拜占庭容錯協(xié)議(Byzantine fault tolerant,簡稱BFT)兩大類[20].CFT 協(xié)議保證系統(tǒng)在組件宕機的情況下也能達成共識,適用于中心化的分布式數(shù)據(jù)集群,例如Google 分布式鎖服務Chubby[29]、Paxos[30]協(xié)議等.BFT 協(xié)議由Leslie Lamport 在1982 年提出,保證分布式系統(tǒng)在故障組件[31,32]的干擾下依然可以達成一致性.由于區(qū)塊鏈網(wǎng)絡的開放性質,區(qū)塊鏈共識協(xié)議需要抵御惡意節(jié)點干擾,因此屬于BFT 協(xié)議.

區(qū)塊鏈系統(tǒng)的運行流程如圖1 所示.用戶利用區(qū)塊鏈客戶端(錢包、網(wǎng)頁等)發(fā)起交易,交易通過點對點(peerto-peer,簡稱P2P)網(wǎng)絡[2,33]廣播,節(jié)點驗證交易格式和內容,若無誤,則加入本地交易池中并廣播給其他節(jié)點;根據(jù)共識協(xié)議的出塊節(jié)點選舉規(guī)則,網(wǎng)絡中的某節(jié)點成為出塊節(jié)點;出塊節(jié)點將交易打包、生成新區(qū)塊,并通過點對點網(wǎng)絡廣播新區(qū)塊;節(jié)點收到區(qū)塊后,驗證區(qū)塊及交易的格式和內容正確性,若無誤,則更新本地區(qū)塊鏈數(shù)據(jù);節(jié)點若收到同一高度的多個區(qū)塊,則根據(jù)共識協(xié)議的主鏈共識對區(qū)塊鏈數(shù)據(jù)達成一致.通過以上分析可看出,區(qū)塊鏈共識協(xié)議主要分為兩個步驟:出塊節(jié)點選舉以及主鏈共識[2,14,15,25].前者用于選舉分布式系統(tǒng)中的出塊節(jié)點、生成新區(qū)塊,后者則對區(qū)塊鏈數(shù)據(jù)達成一致.

Fig.1 Blockchain system running flow diagram圖1 區(qū)塊鏈系統(tǒng)運行流程圖

按節(jié)點準入機制,區(qū)塊鏈系統(tǒng)分為非許可鏈(permissionless blockchain)和許可鏈(permissioned blockchain)兩類[34,35].非許可鏈系統(tǒng)中沒有許可機構對節(jié)點進行身份審查,節(jié)點以匿名形式任意加入或退出系統(tǒng),因此非許可鏈又被稱為公開鏈(public blockchain).基于這種開放性質,非許可鏈系統(tǒng)規(guī)模通常較大,共識節(jié)點甚至可達上萬[36,37].許可鏈系統(tǒng)中節(jié)點需經(jīng)過中心機構的準入審查,獲得授權后才能加入系統(tǒng).因而,許可鏈系統(tǒng)規(guī)模往往較小,節(jié)點數(shù)通常為幾十到幾百[16,38].針對不同應用場景,許可鏈又分為聯(lián)盟鏈(consortium blockchain)和私有鏈(private blockchain)[34,39].聯(lián)盟鏈通常由具有相同行業(yè)背景的多家不同機構組成,共識節(jié)點來自聯(lián)盟內各個機構,區(qū)塊鏈數(shù)據(jù)在聯(lián)盟機構內部共享.私有鏈通常部署在單個機構內部,共識節(jié)點來自機構內部,類似于傳統(tǒng)的分布式數(shù)據(jù)集群.由于區(qū)塊鏈共識協(xié)議的相關研究主要針對非許可鏈,因此我們在本文中主要分析非許可鏈共識協(xié)議,同時也包括一些典型的許可鏈共識協(xié)議.

我們將非許可鏈和許可鏈共識協(xié)議的不同特征總結見表1.針對準入機制,非許可鏈共識協(xié)議允許節(jié)點自由準入,許可鏈共識協(xié)議要求節(jié)點審查準入.基于此特性,非許可鏈一般應用于公開鏈的場景,而許可鏈應用于聯(lián)盟鏈、私有鏈的場景.據(jù)上所述,非許可鏈共識協(xié)議一般具有較高的網(wǎng)絡規(guī)模,許可鏈共識協(xié)議的網(wǎng)絡規(guī)模相對較低.通常情況下,分布式系統(tǒng)網(wǎng)絡規(guī)模越大,達成共識的難度越高,因而非許可鏈吞吐量通常較低,許可鏈較高.在一致性方面:非許可鏈共識協(xié)議通常以一定概率確保數(shù)據(jù)一致,實現(xiàn)弱一致性;許可鏈通常采用確定性方式確保數(shù)據(jù)一致,實現(xiàn)強一致性.

Table 1 Comaprison between permissionless and permissioned blockchains表1 非許可鏈和許可鏈特征比較

2 出塊節(jié)點選舉機制

區(qū)塊鏈共識協(xié)議的出塊節(jié)點選舉機制與傳統(tǒng)分布式協(xié)議中的領導人選舉(leader election)問題[40]類似.該問題于1977 年由Gérard Le Lann[40]正式提出,指分布式系統(tǒng)中采用某種機制選出一個領導人節(jié)點,該節(jié)點負責發(fā)起提案并發(fā)送給其他節(jié)點,其他節(jié)點基于提案更新數(shù)據(jù),以此提升分布式系統(tǒng)運行效率.領導人選舉思想應用于隨后一系列的分布式系統(tǒng)共識協(xié)議研究[30,41,42].在這些研究工作中,領導人節(jié)點的生命周期較長,通常持續(xù)到節(jié)點宕機,因此也被稱為強領導人[42].由于區(qū)塊鏈系統(tǒng)的出塊節(jié)點負責發(fā)起區(qū)塊提案并發(fā)送給其他節(jié)點,以此完成區(qū)塊鏈數(shù)據(jù)的更新,因此,出塊節(jié)點選舉機制類似于領導人選舉問題.有所不同的是,區(qū)塊鏈共識協(xié)議的出塊節(jié)點選舉機制需要抵御開放網(wǎng)絡環(huán)境中的惡意節(jié)點.通過在P2P 網(wǎng)絡中偽造大量虛擬節(jié)點,惡意節(jié)點可以發(fā)起女巫攻擊[43],從而控制區(qū)塊鏈系統(tǒng).為了解決這一問題,區(qū)塊鏈系統(tǒng)在出塊節(jié)點選舉環(huán)節(jié)通常采用“身份定價”機制,例如工作量證明[11,15,17,18]、權益證明[24,44,45]等.下面分別對這兩種機制進行綜述分析.

2.1 工作量證明機制

比特幣[2]首次使用工作量證明(proof of work,簡稱PoW)機制進行出塊節(jié)點選舉,隨后的大量區(qū)塊鏈研究工作及系統(tǒng)都采用這一機制.工作量證明的概念最早由Jakobsson 等人在1999 年提出[46],用于實現(xiàn)可驗證的計算任務.工作量證明包括證明者和驗證者兩個角色,證明者向驗證者出示證據(jù),表明自己在某時間段內完成了一定數(shù)量的計算任務.由于產(chǎn)生證據(jù)需消耗一定量計算資源,工作量證明可用于緩解垃圾郵件和其他拒絕服務攻擊問題.

比特幣基于難題形式實現(xiàn)工作量證明機制.如定義1 所示,比特幣節(jié)點尋找滿足條件的Nonce(number only used once)值,使區(qū)塊哈希低于目標難度值D.解決該工作量證明難題的節(jié)點將成為出塊節(jié)點,負責發(fā)起區(qū)塊提案.

定義1(比特幣工作量證明難題).給定全網(wǎng)統(tǒng)一的難度值D、區(qū)塊元數(shù)據(jù)blockData,尋找滿足條件的Nonce值,使得根據(jù)哈希函數(shù)SHA-256 計算得到的區(qū)塊哈希blockHash低于目標難度值D:

由于哈希算法具備的輸入敏感和抗碰撞[47,48]特點,節(jié)點唯有不斷調整輸入值(Nonce、交易數(shù)據(jù)等)以尋找滿足條件的Nonce,因此,節(jié)點解決難題從而成為出塊節(jié)點的概率與其可用的計算資源成正比.計算資源的投入可被視為一種身份定價機制[46,49],即便攻擊者偽造大量虛擬身份,也無法提升計算資源,從而增加成為出塊節(jié)點的優(yōu)勢.因此,工作量證明難題解決了分布式系統(tǒng)中的女巫攻擊問題[43].另一方面,由于哈希算法具備的正向快速和逆向困難[48]特點,驗證節(jié)點可利用出塊節(jié)點尋找的解快速驗證正確性.因此,工作量證明難題實現(xiàn)了匿名分布式網(wǎng)絡中的可公開驗證.

作為首個區(qū)塊鏈系統(tǒng),比特幣系統(tǒng)所采用的工作量證明機制被應用到大量的區(qū)塊鏈共識協(xié)議研究[11,14-16,25,26,50,51]及新的區(qū)塊鏈系統(tǒng)[44,45,52]中.隨著區(qū)塊鏈研究工作的推進,研究人員逐漸發(fā)現(xiàn)比特幣工作量證明機制的不足,并在此基礎上進行改進.表2 總結了比特幣工作量證明機制(以下簡稱比特幣PoW)的不足及相應改進工作,下面分別對這些不足進行綜述分析.

Table 2 Problems and corresponding solutions of PoW mechanism表2 工作量證明機制的問題及其解決方案

2.1.1 算力中心化

比特幣的工作量證明機制(PoW)具有計算密集型的特點,容易導致網(wǎng)絡算力中心化.在比特幣白皮書中,中本聰(Satoshi Nakamoto)提出了“一處理器一票(one-CPU-one-vote)”的概念.在中本聰?shù)脑O想中,節(jié)點使用個人電腦即可進行PoW 運算,參與出塊節(jié)點選舉,并獲得相應報酬.然而,隨著比特幣價格的上漲,出塊節(jié)點獲得的區(qū)塊獎勵吸引了大量算力加入,比特幣網(wǎng)絡中的哈希算力呈指數(shù)級增長趨勢[64].共識節(jié)點參與PoW 運算的物理設備從早期的個人電腦轉換為GPU,再演變?yōu)槟壳皬V泛使用的專用集成電路(application-specific integrated circuits,簡稱ASIC)礦機.

因比特幣PoW 具備計算資源可聚集和可外包的特點,大多數(shù)節(jié)點選擇加入礦池以保證收入的穩(wěn)定性[1,65].伴隨計算資源的聚集,比特幣網(wǎng)絡出現(xiàn)多個大型礦池.礦池由礦池管理員和礦工構成.如定義2 所示,礦池管理員將計算子任務下發(fā)給礦工,子任務難度值d遠低于全網(wǎng)統(tǒng)一難度值D.礦工找到子任務難題解后,提交給礦池.由于部分子任務難題解也是定義1 中比特幣PoW 難題解,礦池將獲得區(qū)塊獎勵,并根據(jù)礦工根據(jù)提交的子任務解的數(shù)量分配報酬.礦池子任務難題的設計保證礦工收入的穩(wěn)定性.截止2019 年7 月9 日,占比第一的BTC.com礦池擁有21.9%的算力,前兩大礦池擁有33.9%的算力.算力中心化會帶來一系列的安全問題[65-67],例如發(fā)動雙花攻擊、自私挖礦攻擊等.

定義2(礦工工作量證明難題).給定難度值d(d＜＜D)、區(qū)塊元數(shù)據(jù)blockData,尋找滿足條件的Nonce值,使根據(jù)哈希函數(shù)SHA-256 計算得到的區(qū)塊哈希blockHash低于目標難度值d:

針對比特幣PoW 算力中心化問題,一些研究工作和區(qū)塊鏈系統(tǒng)提出了改進措施,包括替換SHA-256 哈希函數(shù)、設計外包困難的PoW 難題、去中心化礦池等.針對SHA-256 哈希函數(shù)計算密集型的特點,一些區(qū)塊鏈系統(tǒng)選擇用內存密集型哈希函數(shù)替代原有函數(shù).例如,萊特幣(Litecoin)[18]和狗狗幣(Dogecoin)[53]采用Scrypt 算法[68],以太坊[17]采用Ethash 算法[69],大零幣(ZeroCash)[54]和小零幣(ZeroCoin)[55]采用Equihash 算法[70].內存密集型哈希函數(shù)由于計算時占用內存多、難以并行計算,能在一定程度上降低ASIC 礦機的算力優(yōu)勢.針對比特幣PoW難題可外包的特點,研究人員修改難題形式使其外包困難,達到區(qū)塊鏈系統(tǒng)去中心化的目標.例如,文獻[56]重新設計比特幣PoW 難題,使礦池管理者將計算任務分發(fā)給礦工后,礦工可修改計算任務中獲取獎勵的地址,并不被礦池管理者發(fā)現(xiàn).文獻[57]實現(xiàn)了基于智能合約的去中心化礦池SmartPool,礦池可自動執(zhí)行子任務難題分發(fā)與確認工作,替代礦池管理員,礦工在獲得穩(wěn)定收入的前提下,共同維護SmartPool,從而保持算力的去中心化.

2.1.2 資源浪費

比特幣工作量證明機制導致的算力資源浪費問題一直被廣為詬病.從2016 年開始,比特幣網(wǎng)絡的哈希率(哈希/秒)呈指數(shù)級增長.截至2019 年7 月,哈希率達到70EH/s(百億億次哈希/秒).現(xiàn)有文獻[71]估計,比特幣網(wǎng)絡年用電量與愛爾蘭或奧地利年用電量相當.

為了解決資源浪費問題,現(xiàn)有研究工作和區(qū)塊鏈系統(tǒng)主要提供了兩種改進措施,即提供有用服務和其他特定能力證明.一些區(qū)塊鏈系統(tǒng)利用PoW 計算過程中消耗的算力提供有用服務.例如,素數(shù)幣(Primecoin)[58]將PoW 難題改進為尋找符合要求的素數(shù),供公眾使用,進而促進數(shù)學領域發(fā)展.素數(shù)幣PoW 難題的解包括3 種形式的素數(shù),即第1 類坎寧安鏈(Cunningham chain of first kind),第2 類坎寧安鏈(Cunningham chain of second kind)和雙鏈(bi-twin chain).有用工作證明(proof of useful work,簡稱PoUW)[59]提出了基于廣泛計算問題的PoW 難題,解決正交向量、最短路徑等問題.

除了利用算力提供有用的服務以外,大量共識協(xié)議利用其他特定能力證明,如權益證明(proof of stake,簡稱PoS)[24,44,50,72,73]、空間證明(proof of space,簡稱PoSp,又被稱為容量證明(proof of capacity,簡稱PoC)、存儲證明(proof of storage,簡稱PoSt)[61]、權威證明(proof of authority,簡稱PoAu)[62]、信譽證明(proof of reputation,簡稱PoR)[63]替代工作量證明.這些特定能力證明中,節(jié)點成為出塊節(jié)點的概率分別與其擁有的某種稀缺資源相關,如權益(即加密貨幣數(shù)量)、內存或硬盤存儲空間、權威、信譽相關,與算力無關.例如,文獻[61]的空間證明用內存消耗型難題替代PoW 算力難題.PoAu 與PoR 思想類似,只有具有較高權威或信譽度的節(jié)點才能成為出塊節(jié)點,由于區(qū)塊帶有節(jié)點簽名,節(jié)點被檢測到作惡后會喪失出塊資格.因此,PoAu 與PoR 只能用于具有準入機制的許可鏈系統(tǒng)中,無法用于非許可鏈系統(tǒng).在這幾類特定能力證明中,權益證明受到廣泛研究與實際應用,因此,我們將在第2.2 節(jié)詳細討論權益證明機制.

2.1.3 性 能

比特幣工作量證明機制是算力競爭型的出塊節(jié)點選舉機制,限制了出塊環(huán)節(jié)的性能提升.如前所述,由于比特幣系統(tǒng)平均區(qū)塊間隔為10min,區(qū)塊大小限制為1MB,因此理論上交易吞吐量約每秒7 筆交易.低吞吐量限制了比特幣系統(tǒng)的廣泛應用.隨著比特幣系統(tǒng)關注度上升,網(wǎng)絡中未確認交易數(shù)增多.截至2019 年7 月10 日,比特幣網(wǎng)絡存在近5 萬筆未確認交易[74].性能問題成為比特幣PoW 中亟待解決的問題.

針對比特幣PoW 的低性能問題,一些研究工作和區(qū)塊鏈系統(tǒng)通過修改參數(shù)和改進出塊節(jié)點選舉機制提升效率.例如,以太坊、萊特幣、狗狗幣系統(tǒng)分別將比特幣PoW 機制中的區(qū)塊間隔調整為15s、2.5min 和1min[75],以此加速交易處理速度.縮短區(qū)塊間隔看起來是改善性能的可行方案,然而一些研究工作發(fā)現(xiàn),縮短區(qū)塊間隔存在安全隱患.文獻[11-13]指出:足夠長的區(qū)塊間隔保證區(qū)塊數(shù)據(jù)在P2P 網(wǎng)絡中廣泛傳播,區(qū)塊間隔縮短會削弱系統(tǒng)安全性.例如,當攻擊者掌握30%系統(tǒng)算力時,為了達到和比特幣系統(tǒng)同等程度的安全性,以太坊、萊特幣、狗狗幣系統(tǒng)需要分別等待至少37 個、28 個、47 個區(qū)塊長度確認[75].

除以上工作外,Bitcoin-NG[11]通過修改比特幣的出塊節(jié)點選舉機制提升交易性能.Bitcoin-NG 將區(qū)塊分為關鍵塊(key block)和微塊(micro block)兩類:關鍵塊包含比特幣PoW 難題的解,體現(xiàn)出塊節(jié)點的工作量證明;微塊包含關鍵塊對應的出塊節(jié)點簽名,但不包含難題的解,不體現(xiàn)工作量證明.節(jié)點生成關鍵塊后,負責在隨后的區(qū)塊間隔時間內將交易打包進微塊并簽名.通過驗證節(jié)點簽名,其他節(jié)點判斷微塊的合法性.通過在區(qū)塊間隔連續(xù)產(chǎn)生微塊,Bitcoin-NG 實現(xiàn)了在出塊節(jié)點選舉環(huán)節(jié)加速交易處理.關鍵塊和微塊的概念隨后也在Byzcoin[15]中得到應用.

2.1.4 總結

工作量證明機制廣泛應用于區(qū)塊鏈共識協(xié)議的出塊節(jié)點選舉環(huán)節(jié).針對算力中心化、資源浪費、低性能等問題,一些研究工作和區(qū)塊鏈系統(tǒng)針對工作量證明機制進行改進.在工作量證明機制的調研過程中,我們發(fā)現(xiàn)一些可行研究點.

· 首先,工作量證明改進工作多以白皮書的形式提出,缺乏理論及實驗數(shù)據(jù)支撐.例如,以太坊系統(tǒng)等白皮書大多從概念層面進行論述,沒有相關實驗數(shù)據(jù)支撐,也沒有進行安全性證明.

· 其次,眾多的工作量證明改進機制之間缺乏相互比較,無法判讀其優(yōu)劣勢.例如,包括 Scrypt[68]、Ethash[69]、Equihash[70]在內的眾多內存密集型哈希函數(shù)沒有相互比較,尚不清楚這些算法針對算力中心化問題的改進程度.值得注意的是,目前已出現(xiàn)針對以上內存密集型哈希函數(shù)的專用礦機.

· 再者,由于分布式系統(tǒng)的各方面復雜因素,對協(xié)議進行參數(shù)調整需要加以嚴格的安全證明.例如,萊特幣等調整參數(shù)的改進方案看似可行,但被證明存在安全隱患[13],最終沒能達到預期效果.

2.2 權益證明機制

針對工作量證明機制的資源浪費問題,比特幣社區(qū)[76]在2011 年首次提出了權益證明機制,根據(jù)節(jié)點掌握的比特幣數(shù)量而不是算力作為權重選舉出塊節(jié)點.權益證明機制的安全性基于權益擁有者比礦工更有動力維護網(wǎng)絡安全的假設[44,72,76],當區(qū)塊鏈系統(tǒng)遭到攻擊,權益擁有者自身利益更容易受損.2012年,權益證明機制首次在點點幣(peercoin/ppcoin)[44]系統(tǒng)中得到應用.點點幣以權益作為選舉權重,提出了權益證明難題.

定義3(點點幣權益證明難題).給定全網(wǎng)統(tǒng)一的難度值D,區(qū)塊元數(shù)據(jù)blockData,尋找滿足條件的時間戳timeStamp,使根據(jù)哈希函數(shù)SHA-256 計算得到的區(qū)塊哈希blockHash低于目標難度值.目標難度值為全網(wǎng)統(tǒng)一難度值D和幣齡coinDay的乘積.幣齡是節(jié)點持有權益(即節(jié)點持有的數(shù)字貨幣數(shù)量,coin)與持有時間(day)的乘積:

與比特幣工作量證明難題相比,點點幣權益證明難題主要有兩處不同:哈希運算中移除隨機數(shù)Nonce,引入幣齡調整難題難度.由于移除隨機數(shù)Nonce,點點幣權益證明難題減輕了工作量證明難題算力競爭問題.在給定元數(shù)據(jù)blockData的情況下,共識節(jié)點在求解點點幣權益證明難題中,可嘗試的只有時間戳變量.由于點點幣采用以秒計數(shù)的UNIX 時間戳,節(jié)點求解難題時嘗試空間有限.因此,點點幣權益證明難題大大縮小了工作量證明難題的計算嘗試空間,減緩了算力競賽帶來的資源浪費問題.

點點幣以幣齡作為權重,實現(xiàn)根據(jù)權益選舉出塊節(jié)點的目標,幣齡的概念隨后在披風幣(Cloakcoin)[77]和新星幣(Novacoin)[78]中也得到應用.幣齡是用戶權益和持有時間的乘積.假設用戶A擁有10 個點點幣并持有90 天,累計900 幣齡.用戶B擁有10 個點點幣并持有45 天,累計450 幣齡.根據(jù)點點幣權益證明難題,用戶A解決難題的可能性2 倍于用戶B.

點點幣權益證明難題創(chuàng)新性地使用幣齡概念衡量權益,使得持有較多數(shù)字貨幣并活躍的節(jié)點更積極參與系統(tǒng)運行,但也存在不足.不活躍節(jié)點可能通過長期持有權益累積大量幣齡,提高自己成為出塊節(jié)點的可能性,從而等待發(fā)動攻擊的時機.針對這一問題,未來幣[45]和黑幣[79]在權益證明難題中以權益替代幣齡,維理幣[80]使用類似幣齡的權益時間(stakeTime)概念,節(jié)點離線后權益時間會逐漸減少,活動證明(proof of activity,簡稱PoA)[50]將權益證明與工作量證明結合,使得只有在線的活躍節(jié)點才能獲得挖礦收益和交易費.這幾種方法都用于改進點點幣系統(tǒng)中不活躍節(jié)點問題.

2.2.1 基于隨機函數(shù)的權益證明

以上所述的權益證明機制在一定程度上緩和了工作量證明機制的算力浪費問題,但采用的仍是基于難題求解的競爭性選舉機制.為了進一步解決算力浪費問題、提高出塊節(jié)點選舉效率,隨后的大量研究工作[14,24,72]采用基于隨機函數(shù)的權益證明機制.這類機制采用以權益作為權重的隨機算法確定出塊節(jié)點,同時,其他節(jié)點可通過隨機算法驗證出塊節(jié)點身份的正確性.由于不再利用算力競爭成為出塊節(jié)點,基于隨機函數(shù)的權益證明屬于非競爭性選舉機制.

活動證明[50]、活動鏈(chains of activity,簡稱CoA)[71]和Ouroboros[24]利用follow-the-satoshi 算法[50]隨機選舉出塊節(jié)點.聰(satoshi)是比特幣的最小貨幣單位,follow-the-satoshi 算法將零和比特幣發(fā)行總量(以聰為單位)間的一個隨機數(shù)作為輸入,通過追溯區(qū)塊數(shù)據(jù),找到目前持有該貨幣的節(jié)點,該節(jié)點即成為出塊節(jié)點.假設用戶A持有10 個比特幣,用戶B持有5 個比特幣,用戶A被follow-the-satoshi 算法選中的概率2 倍于用戶B.因此,followthe-satoshi 算法實現(xiàn)根據(jù)權益進行出塊節(jié)點選舉.

表3 對基于隨機函數(shù)實現(xiàn)權益證明的研究工作及系統(tǒng)進行總結.PoA[50]、CoA[72]和Ouroboros[24]采用不同方式更新follow-the-satoshi 算法的隨機種子.PoA[50]中,出塊節(jié)點首先需要生成滿足PoW 的空區(qū)塊(不包含交易,只包含區(qū)塊元數(shù)據(jù)的空區(qū)塊)哈希,將該哈希作為隨機算法輸入,選出一組背書節(jié)點.出塊節(jié)點搜集一定數(shù)量背書節(jié)點簽名后才能打包交易、生成合法區(qū)塊.因此,PoA[50]的出塊節(jié)點選舉機制實質是PoW 和PoS 的結合,PoW區(qū)塊哈希的不可預測保證了PoS 選舉結果的不可預測.CoA[72]將當前區(qū)塊的前N個區(qū)塊哈希作為隨機算法輸入,選出后N個區(qū)塊的出塊節(jié)點.Ouroboros[24]基于安全多方計算(multi-party computation,簡稱MPC)更新隨機種子.Ouroboros 將多個區(qū)塊間隔稱為一個紀元(epoch),紀元內的出塊節(jié)點共同組成組委員(committee),組委會節(jié)點參與MPC 算法,合作更新隨機種子.Algorand[14]基于可驗證隨機函數(shù)(verifiable random function,簡稱VRF)進行出塊節(jié)點選舉,各節(jié)點利用自己的私鑰和全網(wǎng)統(tǒng)一的隨機種子作為算法輸入,判斷自己是否是本輪的出塊節(jié)點.若成為出塊節(jié)點,節(jié)點將同時出示算法生成的選舉證明,供其他節(jié)點驗證.前一區(qū)塊間隔的出塊節(jié)點利用VRF 函數(shù)更新下一間隔的隨機種子.除了以上基于隨機函數(shù)的出塊節(jié)點選舉機制外,Tendermint[81]采用確定性輪詢算法決定出塊節(jié)點,每個區(qū)塊間隔將確定性產(chǎn)生一個出塊節(jié)點.

Table 3 PoS mechanisms based on random algorithms表3 基于隨機算法的權益證明機制

2.2.2 問題及解決方案

在出塊節(jié)點選舉環(huán)節(jié),PoS 以權益替代算力作為選舉權重,解決了算力浪費問題.隨著對權益證明工作的推進,研究人員發(fā)現(xiàn)PoS 也存在一些問題,主要包括粉碎攻擊、無權益攻擊和長程攻擊.表4 對權益證明機制的問題及其解決方案進行總結.

Table 4 Problems and corresponding solutions of PoS mechanism表4 權益證明機制的問題及其解決方案

粉碎攻擊(grinding attack)指節(jié)點通過嘗試隨機參數(shù)提高成為出塊節(jié)點概率的一類攻擊形式.例如,攻擊者通過嘗試點點幣權益證明難題中的時間戳(timeStamp)和擁有的多個賬戶幣齡提高成為出塊節(jié)點概率[60].與點點幣類似,未來幣中也有時間戳嘗試和公鑰嘗試問題.除此以外,基于隨機函數(shù)的權益證明可提前嘗試隨機種子,提高隨后被選中為出塊節(jié)點的概率[24,50,60].由于隨機種子基于以前的區(qū)塊哈希,CoA[72]可能會遭到粉碎攻擊[24].

粉碎攻擊的解決方案主要包括參數(shù)不可嘗試以及隨機種子限制:前者指權益證明難題中不包括可嘗試參數(shù);后者指隨機種子盡量不依賴區(qū)塊本身信息,否則存在隨機算法偏向某一節(jié)點的可能.例如,Ouroboros[24]和Ouroboros Praos[82]利用多方安全計算產(chǎn)生隨機算法種子,既解決了可嘗試參數(shù)問題,同時保證隨機性與區(qū)塊信息無關.

無權益攻擊(nothing-at-stake)指被選中的出塊節(jié)點在同一高度產(chǎn)生多個區(qū)塊,導致區(qū)塊分叉無法解決的問題.無權益攻擊是出塊節(jié)點出于利益最大化作出的選擇.如圖2 所示,基于權益證明的區(qū)塊鏈系統(tǒng)在高度h處出現(xiàn)分叉,節(jié)點A是高度h+1 的出塊節(jié)點,由于尚不確定在高度h上被最終確認的區(qū)塊,節(jié)點A選擇同時在多個分叉塊后產(chǎn)生區(qū)塊.因此,無論最終哪一區(qū)塊是合法區(qū)塊,節(jié)點A都可獲利.

無權益攻擊的攻擊成本低,出塊節(jié)點無需任何代價即可生成多個區(qū)塊,最終導致多個分叉區(qū)塊齊頭并進,永遠無法達成共識.無權益攻擊的現(xiàn)有解決方案主要包括保證金制度和安全硬件.保證金制度指共識節(jié)點需在賬戶中存取一定金額保證金,若節(jié)點被監(jiān)測發(fā)動無權益攻擊,則罰沒其保證金,從經(jīng)濟激勵角度解決無權益攻擊.例如,以太坊的PoS 提案Slasher[83]和Casper[84]都引入了保證金制度.類似地,Tendermint[85]也引入了保證金機制,且保證金比例和共識票數(shù)成正比.除此以外,文獻[86]基于可信執(zhí)行環(huán)境(trusted execution environment,簡稱TEE)的安全硬件,限制節(jié)點在同一高度只能生成一個區(qū)塊.

Fig.2 Illustration of nothing-at-stake attack圖2 無權益攻擊圖示

長程攻擊(long range)指攻擊者試圖從某一高度區(qū)塊后重新生成后續(xù)所有區(qū)塊,覆蓋這一區(qū)間區(qū)塊數(shù)據(jù),也被稱為歷史攻擊(history attack).由于長程攻擊要求攻擊者的區(qū)塊生成速度快于其他節(jié)點,因此理論上只有掌握超過50%權益的攻擊者才能發(fā)動長程攻擊,然而實際上,攻擊者可通過控制或賄賂歷史時刻擁有大量權益的節(jié)點[86]發(fā)動長程攻擊.例如,攻擊者A擁有21%的權益,節(jié)點B在某一歷史時刻擁有30%的權益,隨后將30%權益轉讓他人,攻擊者可通過控制或賄賂的手段,利用節(jié)點B在歷史時刻擁有的權益,從該時刻重新生成區(qū)塊.

由于節(jié)點轉移權益后不再有維護系統(tǒng)安全的動機,攻擊者可通過賄賂歷史時刻擁有大量權益的節(jié)點發(fā)動長程攻擊.針對這一問題的解決方案主要包括移動檢查點機制和密鑰演進加密技術.移動檢查點機制[87]將某一歷史高度的區(qū)塊作為檢查點,檢查點前的區(qū)塊不可篡改.移動檢查點機制在點點幣[44]、未來幣[45]、黑幣[79]、snow white[88]中得到使用.點點幣和黑幣依賴中心服務器定期發(fā)布檢查點.未來幣[45]不接受720 個區(qū)塊以前的歷史區(qū)塊分叉.與未來幣類似,snow white[88]不接受對距離當前區(qū)塊太遠的歷史區(qū)塊分叉.除了檢查點機制以外,Ouroboros Praos[82]采用密鑰演進加密技術解決長程攻擊[87].節(jié)點隨著時間需要不斷演變私鑰,當攻擊者盜取了節(jié)點目前的密鑰時,由于不能偽造過去的簽名,無法利用節(jié)點的歷史權益發(fā)送長程攻擊.

除以上安全問題外,委托權益證明(delegated proof of stake,簡稱DPoS)[89]通過投票機制縮小共識節(jié)點范圍,使PoS 在大規(guī)模網(wǎng)絡中得以高效應用.DPoS 中的票數(shù)與權益成正比,權益所有者投票選出一部分節(jié)點作為候選出塊節(jié)點,這些節(jié)點再利用PoS 的隨機算法成為出塊節(jié)點.節(jié)點若在給定時間段內未完成出塊,將被移出候選出塊節(jié)點列表.因此,持有權益較少的節(jié)點可通過投票維護系統(tǒng)安全,而不必購買專業(yè)硬件設備成為共識節(jié)點.投票機制還可用于權益所有者修改系統(tǒng)參數(shù),包括交易大小、區(qū)塊間隔、交易費規(guī)則等,實現(xiàn)了區(qū)塊鏈系統(tǒng)自治.

2.2.3 總結

權益證明機制由早期基于難題的競爭性機制,逐漸演變?yōu)榛陔S機函數(shù)的非競爭性出塊節(jié)點選舉機制.后者由于安全且高效,是目前權益證明共識協(xié)議的重點研究方向.我們在調研過程中發(fā)現(xiàn),盡管研究成果眾多,目前尚沒有權益證明機制及其安全問題的綜述研究.因此,本文對權益證明及其3 種主要攻擊方法和對應解決方案進行總結.此外,相比工作量證明機制,采用權益證明機制的區(qū)塊鏈系統(tǒng)仍較少.再者,一些區(qū)塊鏈系統(tǒng)采用工作量證明和權益證明結合的方式,前期利用工作量證明完成權益的初始分配,再逐漸過渡到權益證明機制,例如以太坊、點點幣等.但是,目前尚沒有關于工作量證明如何安全過渡到權益證明的相關研究.

3 主鏈共識

主鏈共識指分布式網(wǎng)絡節(jié)點對區(qū)塊數(shù)據(jù)達成一致的過程.如前所述,在區(qū)塊鏈系統(tǒng)運行流程中,分布式網(wǎng)絡中的節(jié)點根據(jù)出塊節(jié)點選舉機制成為出塊節(jié)點、生成新區(qū)塊并廣播.由于出塊節(jié)點選舉機制存在同一高度產(chǎn)生多個區(qū)塊的可能,節(jié)點本地維護區(qū)塊形成的樹狀結構,即區(qū)塊樹(block tree)[12],因此,節(jié)點需要利用主鏈共識對區(qū)塊樹中最終的區(qū)塊鏈數(shù)據(jù)達成一致.

根據(jù)區(qū)塊數(shù)據(jù)是否滿足最終一致性,主鏈共識可分為概率性共識和確定性共識:概率性共識中區(qū)塊數(shù)據(jù)以一定概率達成一致,隨著時間推移概率逐漸提高,不能保證區(qū)塊數(shù)據(jù)將來不可更改,這種一致性也稱為弱一致性;確定性共識中一旦區(qū)塊數(shù)據(jù)達成一致便不可更改,又被稱為強一致性.

3.1 概率性共識

非許可鏈系統(tǒng)廣泛使用達成概率性共識的主鏈選取規(guī)則.由于非許可鏈網(wǎng)絡規(guī)模較大[36,37],消息傳輸時間長、傳輸代價高,因此通常采用一輪廣播即可達成共識的主鏈選取規(guī)則.在這類規(guī)則中,出塊節(jié)點將生成的新區(qū)塊廣播給其他節(jié)點,節(jié)點使用主鏈選取規(guī)則從本地區(qū)塊樹中確定主鏈區(qū)塊,各節(jié)點的主鏈區(qū)塊隨著時間推移接近一致.

3.1.1 最長鏈規(guī)則

最長鏈規(guī)則在比特幣白皮書[2]中首次提出,選取區(qū)塊樹中的最長分支作為主鏈.由于比特幣采用工作量證明機制,最長鏈累積著最多的工作量證明.根據(jù)比特幣白皮書中“一處理器一票”的思想,最長鏈可被視為分布式網(wǎng)絡中大部分節(jié)點投票做出的決定.因此,只要大部分算力由誠實節(jié)點掌握,分布式網(wǎng)絡就可以利用最長鏈規(guī)則對區(qū)塊數(shù)據(jù)達成一致.最長鏈規(guī)則是目前應用最廣泛的主鏈選取規(guī)則,在一系列研究工作[11,24,50,72]和區(qū)塊鏈系統(tǒng)[17,18]中得到使用.

假設節(jié)點的本地區(qū)塊樹如圖3 所示,區(qū)塊樹中最長的分支(虛線分支)將成為主鏈.交易確認數(shù)指交易所在區(qū)塊的長度,交易未被打包時稱為0 次確認(0-confirmation),交易被區(qū)塊包含稱為1 次確認(1-confirmation).隨著區(qū)塊被后續(xù)區(qū)塊不斷鏈接,確認數(shù)不斷增加.交易確認數(shù)越多,一致性概率越高、安全性越高.在圖3 中,交易3(tx3)為1 次確認,交易1(tx1)為2 次確認,交易2(tx2)則是5 次確認.因此,交易2 安全性高于交易1,交易1 高于交易3.比特幣白皮書[2]中的分析表明:假設攻擊者擁有10%的系統(tǒng)算力,6 次確認交易的安全性高于99.9%.為兼顧系統(tǒng)安全性與系統(tǒng)效率,比特幣客戶端根據(jù)交易金額的大小為交易推薦不同確認數(shù)[90],金額較大交易確認數(shù)越多,保證交易安全性.

Fig.3 Illustration of the longest chain rule圖3 最長鏈規(guī)則圖示

最長鏈規(guī)則性能受到協(xié)議參數(shù)和網(wǎng)絡環(huán)境的影響,如區(qū)塊間隔、區(qū)塊大小、交易大小、網(wǎng)絡規(guī)模、帶寬等.如表5 所示,比特幣系統(tǒng)中,當區(qū)塊大小為1MB、區(qū)塊間隔為10min、交易大小為250 字節(jié)時,交易吞吐量(transaction per second,簡稱TPS)約等于7,比特幣系統(tǒng)從2018 年1 月至今的平均交易確認時延大于10min[91].

Table 5 Performance analysis of probabilistic consensus protocols表5 概率性共識協(xié)議的性能分析

3.1.2 GHOST規(guī)則

文獻[12]發(fā)現(xiàn),在交易請求增多時,比特幣不得不頻繁地創(chuàng)建大區(qū)塊以提高交易吞吐量.大區(qū)塊將導致區(qū)塊傳輸時間延長,使得分叉塊增多、誠實節(jié)點算力分散,此時,惡意節(jié)點將更容易發(fā)動攻擊.為了在交易請求增多時依然保證較高安全性,Sompolinsky 等人提出了GHOST(greedy heaviest-observed sub-tree)[12]規(guī)則作為最長鏈規(guī)則的替代.

圖4 展示了一種網(wǎng)絡中出現(xiàn)多個分叉塊的情形,當誠實節(jié)點的算力被分散時,最長鏈規(guī)則的安全性降低.例如,攻擊者秘密生成一條私有區(qū)塊鏈(黑色鏈條),當私有區(qū)塊鏈長度超過網(wǎng)絡中公開的最長鏈時將其發(fā)布,根據(jù)最長鏈規(guī)則,攻擊者的私有區(qū)塊鏈將成為主鏈.攻擊者可通過私有區(qū)塊鏈發(fā)動雙花攻擊,從而破壞區(qū)塊鏈系統(tǒng)安全性.在最長鏈規(guī)則中,主鏈外區(qū)塊都被視為分叉塊拋棄,不用于維護系統(tǒng)安全性.與最長鏈不同,GHOST 規(guī)則將分叉塊納入主鏈選取規(guī)則,區(qū)塊樹中最重子樹的區(qū)塊將構成主鏈,又被稱為最重鏈.由于最重鏈代表網(wǎng)絡中的大部分算力,文獻[12]認為:只要誠實節(jié)點掌握大多數(shù)算力,GHOST 規(guī)則在網(wǎng)絡交易吞吐量高的情況下也能保證安全性.如圖4 所示,盡管攻擊者生成更長的私有區(qū)塊鏈,由于沒有累積足夠多的工作量證明,無法替代GHOST 規(guī)則選出的最終鏈.GHOST 規(guī)則隨后在包容性協(xié)議[26]和Conflux 中用來選擇主鏈,但據(jù)我們所知,該規(guī)則目前并未直接應用于非許可鏈系統(tǒng)中(我們注意到:以太坊聲稱使用GHOST 規(guī)則來選取主鏈,并實現(xiàn)了一個GHOST 的簡化版本[12],但項目代碼[92]顯示,目前采用的仍是最長鏈規(guī)則).

Fig.4 Illustration of GHOST rule圖4 GHOST 規(guī)則圖示

如表5 所示,當區(qū)塊間隔為1s、區(qū)塊大小為1MB、網(wǎng)絡規(guī)模為1 000 節(jié)點時,GHOST 協(xié)議的吞吐量約為200.文獻[12]中未給出交易確認時延的實驗數(shù)據(jù).值得注意的是,文獻[12]在相同實驗條件下對比了GHOST 與最長鏈規(guī)則的性能,實驗結果顯示:在不同參數(shù)設置中,GHOST 的吞吐量都略低于最長鏈規(guī)則,但其在處理高吞吐量交易時擁有更高安全性能.GHOST 的安全性將在第3.1.6 節(jié)中詳細討論.

3.1.3 包容性協(xié)議

包容性協(xié)議[26]將GHOST 規(guī)則與有向無環(huán)圖(directed acyclic graph,簡稱DAG)結合,進一步提高交易吞吐量.包容性協(xié)議修改了以比特幣為代表的傳統(tǒng)區(qū)塊鏈數(shù)據(jù)結構,區(qū)塊可以指向多個父區(qū)塊而不是唯一一個,新區(qū)塊將所有沒有被指向的區(qū)塊(即葉子區(qū)塊)作為父區(qū)塊,因此,包容性協(xié)議中區(qū)塊構成了有向無環(huán)圖而不是區(qū)塊樹.基于該有向無環(huán)圖,包容性協(xié)議首先利用GHOST 規(guī)則選出主鏈,遍歷主鏈區(qū)塊的多個分叉父區(qū)塊,如果分叉塊中的交易和主鏈交易沒有沖突,則將分叉塊也納入主鏈中.通過利用分叉塊交易內容,包容性協(xié)議進一步提升交易通量,并且對于網(wǎng)絡連接差、不能及時廣播區(qū)塊的節(jié)點更加友好.

如表5 所示,當區(qū)塊間隔為1s、區(qū)塊包含50 筆交易、網(wǎng)絡規(guī)模為100 節(jié)點時,包容性協(xié)議的吞吐量約為30.文獻[26]中未給出交易確認時延的實驗數(shù)據(jù).

3.1.4 SPECTRE協(xié)議

SPECTRE[51]協(xié)議利用成對投票(pair voting)解決沖突區(qū)塊問題,提高系統(tǒng)吞吐量并保證安全性.與包容性協(xié)議類似,SPECTRE 中新區(qū)塊指向多個父區(qū)塊,形成有向無環(huán)圖,在此基礎上運行投票規(guī)則.

假設區(qū)塊x和y是一對包容沖突交易的區(qū)塊,z區(qū)塊將對沖突區(qū)塊進行投票,投票規(guī)則如下.

1)z是x的后代區(qū)塊,不是y的后代區(qū)塊,z投票給x,表示為x≤y.

2)z同時是x和y的后代區(qū)塊,則根據(jù)本區(qū)塊之前有向無環(huán)圖的區(qū)塊投票結果確定.如果投票數(shù)量相等,則根據(jù)預定義規(guī)則決定(區(qū)塊哈希的字典順序等).

3)z既不是x的后代區(qū)塊,也不是y的后代區(qū)塊,則根據(jù)本區(qū)塊之后有向無環(huán)圖的區(qū)塊投票結果確定.如果投票數(shù)量相等,則根據(jù)預定義規(guī)則決定.

圖5 展示了SPECTRE 協(xié)議的運行規(guī)則.交易x和y是攻擊者發(fā)起的兩筆沖突交易,交易x是攻擊者支付給商家的正常交易,交易y是惡意交易.將交易x廣播之前,攻擊者預先生成包含交易y的區(qū)塊及之后兩個區(qū)塊(區(qū)塊13、區(qū)塊14)并隱藏.為了欺騙商家獲得收益,攻擊者首先廣播交易x,并等待交易x被包含到區(qū)塊中.商家確認交易x后,攻擊者將隱藏區(qū)塊鏈發(fā)布出來,企圖替代交易x所在的區(qū)塊鏈.

Fig.5 Illustration of SPECTRE protocol圖5 SPECTRE 協(xié)議圖示

在SPECTRE 協(xié)議中,節(jié)點可并行產(chǎn)生區(qū)塊,隨后再用投票規(guī)則處理沖突區(qū)塊,整體上提升交易處理速率;同時,投票規(guī)則保證攻擊者的隱藏區(qū)塊鏈無法顛覆主鏈.由圖5 可知,除攻擊者產(chǎn)生的所有區(qū)塊都認可交易x.區(qū)塊6～區(qū)塊10 是區(qū)塊x但不是區(qū)塊y的后代,根據(jù)規(guī)則1 投票給x.區(qū)塊1～區(qū)塊5 不是x和y的后代,根據(jù)規(guī)則3 投票給x.區(qū)塊11、區(qū)塊12 是x和y的后代,根據(jù)規(guī)則2 投票給x.SPECTRE 基于工作量證明機制選舉出塊節(jié)點,文獻[51]認為:只要網(wǎng)絡中誠實節(jié)點掌握大多數(shù)算力,投票機制可不斷提升歷史交易優(yōu)勢,從而消除來自惡意節(jié)點隱藏區(qū)塊鏈的威脅[93],保證系統(tǒng)安全性.

如表5 所示,當區(qū)塊間隔為0.1s、區(qū)塊大小為100KB 時,SPECTRE 協(xié)議的交易確認時延約為11s.文獻[51]中未給出交易吞吐量的實驗數(shù)據(jù).

3.1.5 Conflux協(xié)議

Conflux[25]協(xié)議基于有向無環(huán)圖計算出區(qū)塊內交易的全局順序,通過剔除沖突交易,使所有分叉塊內的交易得到利用,從而提升系統(tǒng)吞吐量.Conflux 的區(qū)塊間有兩類指向關系:父邊(parent edge)和引用邊(reference edge).父邊指向父區(qū)塊,每個區(qū)塊只有一條父邊.除父邊外,區(qū)塊可以有多條引用邊,引用邊指向所有目前沒有被父邊引用的葉子區(qū)塊,引用邊代表時間上的發(fā)生在先(happen-before)關系.Conflux 利用GHOST 規(guī)則選出有向無環(huán)圖中的主鏈,利用主鏈和兩類指向關系對所有區(qū)塊進行全局排序.基于區(qū)塊的全局排序,區(qū)塊內的交易也達成全局排序.隨后,Conflux 從交易全局排序中剔除掉重復和沖突的交易,對余下交易達成共識.

與包容性協(xié)議和SPECTRE 協(xié)議相比,Conflux 將共識粒度從區(qū)塊細化到交易,利用交易排序算法將所有分叉塊里的交易得以利用,因而提升了交易吞吐量.文獻[25]將Conflux 協(xié)議與工作量證明的出塊節(jié)點選舉機制結合,同時,Conflux 也可與其他出塊節(jié)點選舉機制結合,例如權益證明機制.

如表5 所示,當區(qū)塊間隔為5s、區(qū)塊大小4MB、交易大小250 字節(jié)、網(wǎng)絡規(guī)模1 萬節(jié)點時,Conflux 的吞吐量為3 200,遠高于相同實驗參數(shù)設置下的最長鏈和GHOST 規(guī)則.但由于使用GHOST 規(guī)則選舉主鏈,Conflux的交易確認時延和GHOST 一致,都是10min.

3.1.6 安全分析

由于大量共識協(xié)議[14,15,24]圍繞持久性和活性進行安全性分析,本節(jié)主要從持久性和活性兩方面對概率性共識進行安全性分析.文獻[13,94,95]基于傳統(tǒng)分布式協(xié)議的安全性和活性目標,提出并總結了區(qū)塊鏈共識協(xié)議中持久性和活性目標.由于大部分概率性共識與工作量證明機制結合,因此概率型共識的安全性分析主要基于工作量證明的出塊節(jié)點選舉機制.

· 持久性(persistence)

持久性衡量概率性共識中區(qū)塊鏈數(shù)據(jù)的一致性.持久性指如果某區(qū)塊在節(jié)點的本地區(qū)塊鏈中擁有k個區(qū)塊的深度,該區(qū)塊在其他節(jié)點的本地區(qū)塊鏈中(極大概率)也擁有k個區(qū)塊的深度.由于網(wǎng)絡傳播等限制,各個節(jié)點的本地區(qū)塊鏈可能暫時不一致,但k個區(qū)塊之前的數(shù)據(jù)(極大概率)是一致的.

· 活性(liveness)

活性衡量概率性共識中區(qū)塊鏈系統(tǒng)的可用性.活性指誠實節(jié)點發(fā)起的交易最終被打包進節(jié)點區(qū)塊鏈中,并滿足持久性.由于網(wǎng)絡吞吐量等限制,誠實節(jié)點發(fā)起的交易可能不會立即被處理,但最終會被處理.

誠實節(jié)點掌握大多數(shù)算力的情況下,最長鏈規(guī)則在同步和異步網(wǎng)絡中都滿足持久性和活性要求.比特幣白皮書[2]對基于工作量證明的最長鏈規(guī)則首先進行了非正式分析,在網(wǎng)絡同步且誠實節(jié)點掌握大多數(shù)算力時,協(xié)議滿足持久性要求.隨后,文獻[13]對最長鏈規(guī)則進行了理論證明,在網(wǎng)絡同步且誠實節(jié)點擁有大多數(shù)算力的情況下,最長鏈規(guī)則滿足持久性和活性要求.在此基礎上,文獻[96]證明了最長鏈規(guī)則在延遲時間有上界的異步網(wǎng)絡中,且誠實節(jié)點擁有大多數(shù)算力的情況下,滿足持久性和活性要求,并可以適應算力動態(tài)變化.

在誠實節(jié)點掌握大多數(shù)算力情況下,GHOST 規(guī)則滿足持久性和活性要求,但活性弱于最長鏈規(guī)則.GHOST規(guī)則[12]作為最長鏈規(guī)則的替代,只要誠實節(jié)點掌握大部分算力,在網(wǎng)絡交易吞吐量高的情況下,依然可以保證安全性.文獻[97]理論證明了GHOST 協(xié)議滿足持久性和活性,然而文獻[97]認為:在網(wǎng)絡交易吞吐量高的情況下,GHOST 規(guī)則相對最長鏈規(guī)則并沒有性能優(yōu)勢.除此以外,文獻[97]提出了一種針對區(qū)塊鏈活性的攻擊方法,通過干擾交易和區(qū)塊的傳播,拖延交易的確認時間,從而破壞活性.在這種攻擊方式下,GHOST 的活性弱于最長鏈規(guī)則.由于Conflux 利用GHOST 協(xié)議選擇主鏈,因此安全性質和GHOST 相同[25].

在誠實節(jié)點掌握大多數(shù)算力的情況下,包容性協(xié)議滿足持久性和活性.文獻[26]未對包容性協(xié)議進行理論證明,但通過實驗方式顯示,協(xié)議可滿足持久性和活性.

在誠實節(jié)點掌握大多數(shù)算力的情況下,SPECTRE 協(xié)議可保證區(qū)塊鏈系統(tǒng)的持久性和弱活性(SPECTRE 協(xié)議中未對持久性(persistence)進行證明,但其中的一致性、安全性與持久性同一定義,因此我們將其看做對持久性的證明)[51].SPECTRE 協(xié)議在交易內容互不沖突時,能保證交易在有限時間內被打包到區(qū)塊中,即滿足活性要求.然而,當攻擊者同時發(fā)起兩筆沖突交易時,合法交易只能滿足弱活性,即交易最終會被打包到區(qū)塊中,但時間有明顯延遲.

在與工作量證明機制結合的情況下,大部分概率性共識協(xié)議存在激勵相容(incentive compatibility)問題.激勵相容問題指節(jié)點的個人目標與系統(tǒng)目標不一致,其中最典型的是自私挖礦問題.在工作量證明機制的基礎上,為鼓勵節(jié)點加入網(wǎng)絡維護安全,系統(tǒng)通常以數(shù)字貨幣形式給出塊節(jié)點一定報酬.然而大量研究工作[65,66,98,99]發(fā)現(xiàn),當節(jié)點掌握算力達到一定程度時,理性節(jié)點選擇不遵守協(xié)議將獲得更高的收益.這些節(jié)點被稱為自私挖礦節(jié)點,他們將生成的新區(qū)塊隱藏起來,并選擇在將來的適當時機公開,從而獲得更高收益.這些隱藏區(qū)塊可能會顛覆網(wǎng)絡的公開區(qū)塊,引發(fā)安全問題.

文獻[65]首次發(fā)現(xiàn)最長鏈規(guī)則中的自私挖礦問題.在自私挖礦影響下,最長鏈規(guī)則的安全邊界從50%降低到33%,即只能抵御算力不超過33%的惡意節(jié)點.隨后,一系列研究工作[66,98]在最長鏈規(guī)則上拓展不同的自私挖礦策略,進一步降低系統(tǒng)安全邊界.與最長鏈規(guī)則類似,GHOST 規(guī)則和包容性協(xié)議也受到自私挖礦的影響[26,66].SPECTRE 協(xié)議沒有說明是否存在自私挖礦問題.此外,由于Conflux 協(xié)議基于GHOST 規(guī)則選擇主鏈,也有同樣的自私挖礦問題.

表6 對以上討論的概率性共識協(xié)議安全性質進行總結.除包容性協(xié)議以外,以上概率性共識都從理論上證明滿足持久性和活性目標.目前僅有最長鏈和GHOST 規(guī)則在持久性和活性上的對比分析工作,其他概率性共識之間缺乏對比.其次,GHOST 規(guī)則在研究工作中備受關注,但缺乏區(qū)塊鏈系統(tǒng)應用,以太坊目前仍采用最長鏈規(guī)則.再者,幾乎所有基于工作量證明的概率性共識都存在自私挖礦問題,目前,自私挖礦問題在最長鏈規(guī)則上得到大量研究,但在其他概率性共識上的研究較少.

Table 6 Analysis of the security properties of probabilistic consensus protocols表6 概率性共識協(xié)議的安全性質分析

3.2 確定性共識

概率性共識在交易延遲與安全性存在天然的權衡問題[100],限制了區(qū)塊鏈技術的應用場景.因此,一些研究工作采用確定性共識確保區(qū)塊數(shù)據(jù)的強一致性.概率性共識的權衡問題源于區(qū)塊數(shù)據(jù)的一致性概率隨著時間推移逐漸提高,為保證交易安全性,用戶不得不等待多個區(qū)塊確認,帶來明顯的交易延時.延時問題限制了基于概率性共識的區(qū)塊鏈系統(tǒng)的商業(yè)應用,因此,一些研究工作[14-16,28]采用確定性共識替代概率性共識.如上所述,在確定性共識中,區(qū)塊一旦寫入節(jié)點本地區(qū)塊鏈,就不存在隨后被改變的可能性.確定性共識有兩個明顯優(yōu)勢[15]:首先,用戶不用等待較長時間確保交易安全性;其次,由于同一高度僅有一個合法區(qū)塊,節(jié)點不用在分叉區(qū)塊上浪費計算資源.

拜占庭容錯協(xié)議用于解決分布式系統(tǒng)中的拜占庭將軍問題,在存在惡意節(jié)點的情況下達成一致性.拜占庭將軍問題由Leslie Lamport 在1982 年[31]提出,誠實將軍在叛徒將軍的干擾下對進攻命令達成一致.拜占庭將軍問題是分布式系統(tǒng)中正常組件在故障組件干擾下達成一致的抽象描述.

經(jīng)典的拜占庭容錯協(xié)議通常面向中心化的分布式集群達成確定一致性,如PBFT[27]、Byzantine Paoxs[101]等,但無法直接應用在區(qū)塊鏈系統(tǒng)中.在這些協(xié)議中,共識節(jié)點數(shù)量固定或者變化緩慢[27],節(jié)點之間需要多輪廣播通信[102],通信復雜度較高.然而區(qū)塊鏈系統(tǒng)中的節(jié)點數(shù)量不斷動態(tài)變化,區(qū)塊鏈系統(tǒng)(特別是非許可鏈)的網(wǎng)絡規(guī)模也不支持節(jié)點間的多輪廣播通信,因此,區(qū)塊鏈拜占庭容許協(xié)議需要適應系統(tǒng)特點進行改進.

3.2.1 非許可鏈拜占庭容錯協(xié)議

為了在網(wǎng)絡規(guī)模較大的非許可鏈系統(tǒng)中達成確定性共識,一些研究工作[14,15]將拜占庭容錯協(xié)議和區(qū)塊鏈的出塊節(jié)點選舉機制相結合,被稱為混合協(xié)議[103].混合協(xié)議也分為出塊節(jié)點選舉和主鏈共識兩個階段:在出塊節(jié)點選舉階段,混合協(xié)議采用區(qū)塊鏈的選舉機制,抵御開放網(wǎng)絡中的女巫攻擊等問題;在主鏈共識階段,混合協(xié)議通常讓多個出塊節(jié)點構成組委會,運行拜占庭容錯協(xié)議,對新區(qū)塊達成一致.組委會成員通常隨著時間變化[103].

Algorand[14]是權益證明和拜占庭容錯協(xié)議結合的混合協(xié)議.在出塊節(jié)點選舉階段,Algorand 利用基于隨機函數(shù)的權益證明選出一組出塊節(jié)點,每個節(jié)點發(fā)起區(qū)塊提案(block proposal)并廣播,各提案附有隨機優(yōu)先級,每個節(jié)點只保留優(yōu)先級最高的區(qū)塊;隨后,節(jié)點再運行一輪拜占庭一致性協(xié)議(BA*),將自己接收到的最高優(yōu)先級區(qū)塊作為輸入,對區(qū)塊達成共識.

Algorand 中的拜占庭一致性協(xié)議分為兩個階段:歸約(reduction)和二進制一致性(binary agreement).

規(guī)約階段保證各節(jié)點持有相同的最高優(yōu)先級區(qū)塊,解決網(wǎng)絡傳輸導致的節(jié)點本地最高優(yōu)先級區(qū)塊可能不一致的問題.在規(guī)約階段,所有節(jié)點廣播自己本地最高優(yōu)先級的區(qū)塊哈希,接收到其他節(jié)點的區(qū)塊哈希后,節(jié)點統(tǒng)計每個區(qū)塊的票數(shù),認定票數(shù)最高的區(qū)塊為最高優(yōu)先級區(qū)塊;沒有票數(shù)最高區(qū)塊時,將空區(qū)塊作為最高優(yōu)先級區(qū)塊.歸約階段達成一致的區(qū)塊將作為二進制一致性階段的輸入.

二進制一致性階段對規(guī)約階段生成的區(qū)塊達成確定性共識.在二進制一致性階段,出塊節(jié)點選舉環(huán)節(jié)發(fā)起區(qū)塊提案的節(jié)點形成組委會,對規(guī)約階段的區(qū)塊投票.區(qū)塊收到一定數(shù)量票數(shù)后,就被確認為最終區(qū)塊.所有節(jié)點將該區(qū)塊更新到本地區(qū)塊鏈中,達成確認性共識.由于網(wǎng)絡原因,二進制一致性階段的投票可能會重復多次.如表7 所示,當區(qū)塊間隔為1min、區(qū)塊大小為1MB、網(wǎng)絡規(guī)模為5 萬節(jié)點時,Algorand 的交易吞吐量達到327MB/h,交易確認時延小于1s.

Table 7 Performance analysis of deterministic consensus protocols表7 確定性共識協(xié)議的性能分析

Byzcoin[15]是工作量證明和實用拜占庭容錯協(xié)議結合的混合協(xié)議.Byzcoin 首先利用工作量證明機制選舉出塊節(jié)點、生成新區(qū)塊,隨后再利用實用拜占庭容錯協(xié)議對新區(qū)塊達成確定性共識.如圖6 所示,在出塊節(jié)點選舉階段,節(jié)點利用工作量證明生成新區(qū)塊并廣播.一個時間間隔(1 天或1 周,可調整)內的出塊節(jié)點構成組委會.組委會成員的票數(shù)為在該時間間隔內的出塊數(shù)量,成員利用實用拜占庭容錯協(xié)議對新區(qū)塊投票達成共識.出塊節(jié)點廣播新區(qū)塊,組委會成員驗證區(qū)塊無誤后返回簽名作為投票,出塊節(jié)點搜集至少2/3 票數(shù)后,廣播組委會成員簽名,證明新區(qū)塊已經(jīng)被組委會接收并驗證.組委會成員接收到廣播信息后,再次返回簽名,表示同意將該區(qū)塊寫入?yún)^(qū)塊鏈中,出塊節(jié)點搜集至少2/3 票數(shù)后,再次廣播區(qū)塊,并寫入?yún)^(qū)塊鏈中.至此,共識節(jié)點對該區(qū)塊達成確定性共識.由于通信過程中涉及大量簽名和驗簽操作,為提高效率,Byzcoin 引入集體簽名技術,可一次同時驗證多個簽名.如表7 所示,當關鍵塊間隔為10min、區(qū)塊大小為32MB、網(wǎng)絡規(guī)模為144 節(jié)點時,Byzcoin 的TPS 為974,時延為68s.

Fig.6 Byzcoin hybrid consensus protocol圖6 Byzcoin 混合共識協(xié)議

不同于Algorand 和Byzcoin 采用混合協(xié)議,Stellar 共識協(xié)議[28]采用聯(lián)邦拜占庭協(xié)議(federated Byzantine agreement,簡稱FBA)達成共識.Stellar 是一個開放的實時跨境支付系統(tǒng)[104],為了使拜占庭協(xié)議支持非許可鏈中開放成員的需求,引入仲裁系統(tǒng)分片(quorum slice)達成共識.在拜占庭協(xié)議中,仲裁系統(tǒng)指可達成共識的一組節(jié)點.仲裁系統(tǒng)分片是仲裁系統(tǒng)子集.Stellar 的仲裁系統(tǒng)基于某種標準劃分,例如聲譽或權益,節(jié)點可同時加入多個仲裁系統(tǒng)分片.仲裁系統(tǒng)分片保持交集,保證共識達成.

Stellar 共識協(xié)議主要分為投票、接收和確認這3 個階段.

· 在投票階段,節(jié)點對接收到的交易進行投票并廣播投票信息.

· 在接收階段,若節(jié)點v-blocking 集合中的所有節(jié)點都投票給該交易,則接收該交易.v-blocking 是和該節(jié)點所在的全部仲裁分片有交集的節(jié)點集合.

· 在確認階段,節(jié)點間通過消息交互對接收階段的交易達成最終共識.仲裁分片互相影響,最終保證所有誠實節(jié)點對交易達成確定性共識.

文獻[28]中未給出Stellar 協(xié)議的實驗數(shù)據(jù).

3.2.2 許可鏈拜占庭容錯協(xié)議

如上所述,許可鏈根據(jù)應用場景不同分為聯(lián)盟鏈和私有鏈,其中,企業(yè)級聯(lián)盟鏈是目前應用最廣的許可鏈系統(tǒng).由于網(wǎng)絡規(guī)模限制、共識一致性要求高,許可鏈更適合采用拜占庭容錯協(xié)議[38].目前的一些研究工作[16]和系統(tǒng)[19,80,105]探索拜占庭容錯協(xié)議在許可鏈中的應用.

HoneyBadger[16]首次將實踐拜占庭容錯協(xié)議應用到純異步許可鏈中.HoneyBadger 系統(tǒng)中,共識節(jié)點身份已知且數(shù)量固定,節(jié)點兩兩建立經(jīng)過認證的可信通道.為了消除出塊節(jié)點廣播區(qū)塊這一環(huán)節(jié)的帶寬瓶頸,HoneyBadger 沒有采用出塊節(jié)點選舉機制,取而代之的是:各節(jié)點在每輪出塊開始時,從本地交易緩沖池中選擇部分交易進行廣播.為了避免拜占庭節(jié)點故意忽略某些交易從而影響系統(tǒng)活性,節(jié)點不廣播交易內容本身而是經(jīng)門限加密后的交易密文.所有節(jié)點收到密文集合后,HoneyBadger 通過拜占庭協(xié)議對一組位向量(bit vector)達成共識,假設位向量第N位為真,則將密文集合對應的第N位密文還原,并將其中包含的交易寫入?yún)^(qū)塊.如表7 所示,當交易大小為250 字節(jié)、網(wǎng)絡規(guī)模為104 節(jié)點時,HoneyBadger 的TPS 為1 500,時延小于6min.

聯(lián)盟鏈系統(tǒng)Tendermint[81]采用基于輪詢機制的實用拜占庭容錯協(xié)議對新區(qū)塊達成共識.在出塊節(jié)點選舉環(huán)節(jié),Tendermint 采用確定性輪詢機制決定出塊節(jié)點.由于未采用類似工作量證明的身份定價機制,為防止拜占庭節(jié)點發(fā)動女巫攻擊,系統(tǒng)規(guī)定節(jié)點必須在賬戶存入保證金才能參與拜占庭容錯協(xié)議的投票過程,保證金數(shù)額與票數(shù)成正比.在網(wǎng)絡弱同步且誠實節(jié)點掌握至少2/3 票數(shù)的情況下,Tendermint 滿足安全性和活性.如表7 所示,當區(qū)塊大小為1 萬筆交易、交易大小為250 字節(jié)、網(wǎng)絡規(guī)模為全球64 節(jié)點時,Tendermint 的TPS 約為4 000,延遲約等于2s[81].

除使用拜占庭容錯協(xié)議外,一些企業(yè)級區(qū)塊鏈系統(tǒng)采用CFT 協(xié)議而非BFT 協(xié)議達成確定性共識.2016 年初,Linux 基金會發(fā)起了Hyperledger 項目,旨在建立企業(yè)級區(qū)塊鏈框架[106],目前已有超過270 個機構加入[107].Hyperledger Fabric(以下簡稱Fabric)是Hyperledger 項目中備受關注的一個子項目,打造面向許可鏈的分布式數(shù)據(jù)平臺.Fabric v0.5 采用了PBFT 協(xié)議在共識節(jié)點之間對交易內容實現(xiàn)共識[106],目前最新的Fabric v1.4 用Raft和Apache Kafka 兩種CFT 協(xié)議實現(xiàn)共識[108].

3.2.3 安全分析

確定性共識需要滿足安全性和活性兩個基本性質對應概率性共識中的持久性和活性.此外,由于不存在分叉,確定性共識不存在概率性共識中的自私挖礦問題[14,15].

· 安全性(safety)衡量確定性共識中區(qū)塊鏈數(shù)據(jù)的一致性[109].如果某區(qū)塊被寫入節(jié)點的本地區(qū)塊鏈中,該區(qū)塊也被其他節(jié)點寫入本地區(qū)塊鏈中.即各節(jié)點在同一高度擁有相同區(qū)塊.

· 活性衡量確定性共識中區(qū)塊鏈系統(tǒng)的可用性.活性指由誠實節(jié)點發(fā)起的交易最終會被打包進區(qū)塊鏈中、并且滿足持久性.由于網(wǎng)絡吞吐量等限制,誠實節(jié)點發(fā)起的交易可能不會立即被處理,但最終會被處理.

在強同步網(wǎng)絡及誠實節(jié)點掌握至少2/3 權益的情況下,Algorand 滿足安全性和活性.Algorand 拜占庭一致性協(xié)議(BA*)基于強同步網(wǎng)絡,大多數(shù)(如95%)誠實節(jié)點發(fā)送的消息在已知時間間隔內可發(fā)送給其他大多數(shù)誠實節(jié)點.BA*在弱同步網(wǎng)絡情況下不能達成一致性,需要等待網(wǎng)絡變?yōu)閺娡?Algorand 采用權益證明的出塊節(jié)點選舉機制,要求誠實節(jié)點掌握系統(tǒng)中至少2/3 的權益.最好情況下,即每個節(jié)點收到的最高優(yōu)先級區(qū)塊一致時,Algorand 需要節(jié)點間的四輪交互達成共識;最壞情況下則需要13 輪.文獻[14]利用1 000 臺虛擬機模擬50 000用戶運行Algorand 協(xié)議,實驗顯示:確認1MB 大小的區(qū)塊需要約22s 延遲;區(qū)塊大小為10MB 時,Algorand 吞吐量為750MB/h.

在弱同步網(wǎng)絡及節(jié)點總數(shù)至少3f+2 的情況下,Byzcoin 滿足安全性和活性.Byzcoin 是實用拜占庭容錯協(xié)議和工作量證明的混合協(xié)議,網(wǎng)絡環(huán)境要求和實用拜占庭容錯協(xié)議一致,即消息延遲有上限但上限不可知的弱同步環(huán)境.當網(wǎng)絡存在f個惡意節(jié)點時,Byzcoin 需要至少3f+2 節(jié)點數(shù)才能達成共識.文獻[15]在1 008 個節(jié)點上運行Byzcoin 協(xié)議,當區(qū)塊大小為1MB～2MB 時,交易延遲為10s～20s,交易吞吐量為700 筆/秒.

在同步網(wǎng)絡及節(jié)點選擇足夠多的仲裁分片的情況下,Stellar 滿足安全性,但惡意節(jié)點故意過濾交易時,Stellar 活性受到影響.Stellar 分為投票、接收和確認這3 個階段,投票和接收階段要求同步網(wǎng)絡,確認階段可以是異步網(wǎng)絡,總體上,Stellar 需運行在同步網(wǎng)絡中.在節(jié)點選擇足夠多的仲裁分片,且仲裁分片中聲譽或權益高的節(jié)點是誠實節(jié)點時,文獻[28]證明:Stellar 滿足安全性,但惡意節(jié)點在Stellar 的交易投票階段故意過濾交易,會影響交易活性.文獻[28]未對Stellar 協(xié)議的性能表現(xiàn)開展實驗.

在純異步網(wǎng)絡及節(jié)點總數(shù)至少為3f+1 時,HoneyBadger 滿足安全性和活性.HoneyBadger 要求節(jié)點身份已知且數(shù)量固定,節(jié)點間需要兩兩建立可信通道.在純異步通信環(huán)境下,HoneyBadger 保持活性.由于采用拜占庭容錯協(xié)議,為抵御f個惡意節(jié)點,HoneyBadger 需要至少3f+1 個節(jié)點保證安全性.HoneyBadger 可用于廣域網(wǎng)中的聯(lián)盟鏈系統(tǒng),系統(tǒng)可擴展至上百節(jié)點數(shù).在跨5 個洲的104 個節(jié)點上運行HoneyBadger 協(xié)議時,交易吞吐量達到1 500 筆/秒,延遲不到6min;在32 個節(jié)點上運行時,交易吞吐量最高達到20 000 筆/秒,延遲為30s 左右[16].

3.2.4 總結

表8 總結了以上所述確定性共識協(xié)議的安全性質.Algorand、Byzcoin 和Stellar 協(xié)議面向非許可鏈場景,HoneyBadger、Tendermint 協(xié)議面向網(wǎng)絡規(guī)模受限的許可鏈應用場景.Algorand 等協(xié)議基本都滿足安全性和活性,但Stellar 系統(tǒng)在存在惡意節(jié)點時,系統(tǒng)活性會受到破壞.在網(wǎng)絡層面上,Algorand 和Byzcoin 要求弱同步網(wǎng)絡,Stellar 要求同步網(wǎng)絡,HoneyBadger 可在純異步網(wǎng)絡中運行.盡管對網(wǎng)絡要求低,HoneyBadger 只能在節(jié)點身份已知且數(shù)量不變的非許可鏈環(huán)境中運行,且要求節(jié)點兩兩建立可信通道,對節(jié)點間通信要求較高.在安全邊界上,大多數(shù)確定性共識協(xié)議繼承了拜占庭協(xié)議3f+1 的安全邊界,Stellar 則要求仲裁分片相交.此外,由于各協(xié)議在實驗設計方面缺乏統(tǒng)一標準,包括節(jié)點數(shù)目、節(jié)點硬件配置、區(qū)塊和交易大小設置等,以致于文獻中各協(xié)議的性能表現(xiàn)實驗結果難以橫向對比.

Table 8 Analysis of security properties of deterministic consensus protocols表8 確定性共識協(xié)議的安全性質分析

4 總結與展望

本文中,我們將區(qū)塊鏈共識協(xié)議分為出塊節(jié)點選舉和主鏈共識兩個主要步驟,通過對每個步驟采用機制進行綜合梳理、對比和分析,發(fā)現(xiàn)如下關鍵問題,值得廣大研究人員關注.

· 在出塊節(jié)點選舉機制,我們圍繞工作量證明和權益證明展開討論.區(qū)塊鏈的出塊節(jié)點選舉機制類似傳統(tǒng)分布式協(xié)議的領導人選舉問題,與之不同的是:為抵御開放網(wǎng)絡環(huán)境中的惡意節(jié)點,出塊節(jié)點選舉機制通?；凇吧矸荻▋r”機制,包括工作量證明和權益證明.

? 工作量證明通過物理資源的投入抵御惡意節(jié)點,存在算力中心化、資源浪費、選舉性能低等若干問題.為了解決這些問題,一些研究工作用內存密集型函數(shù)替代計算密集型函數(shù)、利用算力提供有用服務、調整工作量證明難題參數(shù)等.部分方案改變了系統(tǒng)性質,從而引出了新的研究問題,包括改變區(qū)塊大小、出塊間隔、難度調整算法等,研究人員可針對已有攻擊方式在改進系統(tǒng)中的新型攻擊手段、安全邊界展開研究.

? 權益證明被用于解決工作量證明的資源浪費問題,由早期的競爭性難題機制逐漸演變?yōu)榛陔S機函數(shù)的非競爭性機制.非競爭性機制由于安全和高效,是目前權益證明的重點研究方向.權益證明也存在粉碎攻擊、無權益攻擊和長程攻擊等問題,但目前尚沒有對權益證明及其安全問題的綜述研究.

· 在主鏈共識步驟,根據(jù)區(qū)塊數(shù)據(jù)的一致性性質,我們將主鏈共識分為概率性共識和確定性共識,并分別展開討論.

? 概率性共識從早期基于區(qū)塊樹的選取規(guī)則逐漸演變?yōu)榛谟邢驘o環(huán)圖的選取規(guī)則,且共識粒度從區(qū)塊細化為交易,部分有向無環(huán)圖協(xié)議對交易全局順序達成概率性共識.當前,大部分概率性共識通過理論證明滿足安全性和活性.然而,概率性共識之間缺乏對比工作,目前僅有最長鏈和GHOST 規(guī)則的安全性對比分析.在調研過程中我們發(fā)現(xiàn),最長鏈規(guī)則仍是區(qū)塊鏈系統(tǒng)的主導規(guī)則,GHOST 規(guī)則在研究工作中備受關注但目前缺乏實際應用.此外,幾乎所有基于工作量證明的概率性共識都存在自私挖礦問題,但尚未有研究工作對除最長鏈規(guī)則以外的其他概率性共識度量自私挖礦攻擊的影響.

? 為滿足非許可鏈開放成員及網(wǎng)絡規(guī)模要求,大多數(shù)確定性共識將出塊節(jié)點選舉機制與拜占庭容錯協(xié)議相結合,實現(xiàn)區(qū)塊鏈系統(tǒng)的確定一致性.這些協(xié)議通常運行于異步網(wǎng)絡中,并要求惡意節(jié)點不超過節(jié)點總數(shù)的1/3.據(jù)我們所知,目前尚沒有可運行于大規(guī)模純異步網(wǎng)絡中的確定性共識協(xié)議.HoneyBadger 作為純異步共識協(xié)議,只適用于節(jié)點身份和數(shù)量都已知的非許可鏈系統(tǒng).

區(qū)塊鏈具有去信任、開放自治、匿名可溯源、信息不可篡改等特性,是構建可信數(shù)字經(jīng)濟的重要基礎設施.共識協(xié)議作為區(qū)塊鏈核心技術,近年來得到廣泛關注和大量研究.本文對現(xiàn)有區(qū)塊鏈共識協(xié)議進行綜合梳理,為研究人員和開發(fā)者提供有用參考.