區(qū)塊鏈共識(shí)算法研究綜述

靳世雄 ,張瀟丹,葛敬國(guó) ,史洪彬,孫 毅 ,李 鳴 ,林業(yè)明 ,姚忠將

1中國(guó)科學(xué)院大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 北京 中國(guó) 100049

2中國(guó)科學(xué)院信息工程研究所 北京 中國(guó) 100093

3中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 中國(guó) 100190

4中國(guó)電子技術(shù)標(biāo)準(zhǔn)化研究院 北京 中國(guó) 100007

1 引言

2008年,“中本聰”發(fā)表《Bitcoin: A Peer-to-Peer Electronic Cash System》[1],詳細(xì)描述了去中心化的數(shù)字貨幣[2]交易賬本的概念和技術(shù)細(xì)節(jié); 2009年,比特幣系統(tǒng)正式發(fā)布; 隨后,比特幣系統(tǒng)的底層技術(shù)——區(qū)塊鏈技術(shù)進(jìn)入大眾視野。

區(qū)塊鏈?zhǔn)且环N去中心化、不可篡改、可追溯的分布式數(shù)據(jù)庫(kù)系統(tǒng)[3]。區(qū)塊鏈系統(tǒng)中底層網(wǎng)絡(luò)采用對(duì)等式網(wǎng)絡(luò)(P2P網(wǎng)絡(luò))組織各個(gè)獨(dú)立的網(wǎng)絡(luò)節(jié)點(diǎn)。P2P網(wǎng)絡(luò)是扁平式的拓?fù)浣Y(jié)構(gòu),網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)地位對(duì)等,不存在任何中心化的特殊節(jié)點(diǎn)和層級(jí)結(jié)構(gòu)。因此區(qū)塊鏈具備去中心化的特點(diǎn),系統(tǒng)中各節(jié)點(diǎn)相互獨(dú)立,具備相同的功能,存儲(chǔ)同樣的信息,相互監(jiān)督;與傳統(tǒng)分布式數(shù)據(jù)庫(kù)不同,各個(gè)節(jié)點(diǎn)獨(dú)立存儲(chǔ)完整的數(shù)據(jù),任何組織或個(gè)人無(wú)法完全控制所有數(shù)據(jù),只擁有本地?cái)?shù)據(jù)的控制權(quán),任何單個(gè)節(jié)點(diǎn)對(duì)本地?cái)?shù)據(jù)的修改不會(huì)對(duì)整個(gè)區(qū)塊鏈產(chǎn)生影響,因此區(qū)塊鏈具備難以篡改性; 區(qū)塊鏈把數(shù)據(jù)分成不同的區(qū)塊,每一個(gè)區(qū)塊頭都包含前一個(gè)區(qū)塊的哈希摘要信息,如圖1所示,前后順連形成一條鏈,因此區(qū)塊鏈具備可溯性?？傮w來(lái)說(shuō),區(qū)塊鏈融合了經(jīng)濟(jì)學(xué)的博弈論[4]、計(jì)算機(jī)科學(xué)等多種技術(shù),比如P2P網(wǎng)絡(luò)協(xié)議[5],塊鏈結(jié)構(gòu)、共識(shí)算法、非對(duì)稱(chēng)加密[6-8]、激勵(lì)機(jī)制等,解決了數(shù)據(jù)可信問(wèn)題。在無(wú)需借助可信第三方的情況下,實(shí)現(xiàn)互不信任的多方對(duì)等可信的價(jià)值傳輸。

圖1 區(qū)塊鏈?zhǔn)疽鈭DFigure 1 The diagram of blockchain

共識(shí)算法是區(qū)塊鏈系統(tǒng)中的核心機(jī)制,旨在解決系統(tǒng)中各分布式節(jié)點(diǎn)數(shù)據(jù)一致性[9]的問(wèn)題。在分布式對(duì)等網(wǎng)絡(luò)中,不同節(jié)點(diǎn)通過(guò)交換信息達(dá)成共識(shí),而網(wǎng)絡(luò)中可能存在惡意節(jié)點(diǎn)篡改或偽造數(shù)據(jù),或者通信網(wǎng)絡(luò)也可能導(dǎo)致傳輸信息出錯(cuò),從而影響節(jié)點(diǎn)間共識(shí)的達(dá)成,破壞分布式系統(tǒng)的一致性。這個(gè)問(wèn)題于 1982年由 Leslie Lamport、Robert Shostak和Marshall Pease正式建模為“拜占庭將軍問(wèn)題”[10]。傳統(tǒng)的分布式系統(tǒng)共識(shí)算法大多不考慮拜占庭容錯(cuò)問(wèn)題,僅考慮網(wǎng)絡(luò)延時(shí)或部分節(jié)點(diǎn)出現(xiàn)故障無(wú)法響應(yīng)的情況下,非故障節(jié)點(diǎn)如何實(shí)現(xiàn)分布式系統(tǒng)的數(shù)據(jù)一致性。區(qū)塊鏈系統(tǒng)運(yùn)行在更為開(kāi)放并且缺乏信任的網(wǎng)絡(luò)環(huán)境中,節(jié)點(diǎn)數(shù)量眾多且可能存在惡意節(jié)點(diǎn),因此區(qū)塊鏈系統(tǒng)的共識(shí)算法設(shè)計(jì)必須考慮“拜占庭將軍問(wèn)題”。

1985年,由 Michael Fisher、Nancy Lynch 和Michael Paterson共同提出并證明了在分布式系統(tǒng)共識(shí)算法的設(shè)計(jì)中起到重要指導(dǎo)作用的“FLP不可能定理”[11]。該定理指出: 在網(wǎng)絡(luò)可靠的異步通信系統(tǒng)中,當(dāng)存在節(jié)點(diǎn)故障(即使只有一個(gè))的情況下,不存在協(xié)議能保證在有限時(shí)間內(nèi)使系統(tǒng)達(dá)成一致。“FLP不可能定理”指出了在可能存在節(jié)點(diǎn)失效的分布式異步通信系統(tǒng)中,理論上不存在能使系統(tǒng)在有限時(shí)間內(nèi)達(dá)成一致的共識(shí)算法。因而研究者們通過(guò)調(diào)整問(wèn)題模型來(lái)規(guī)避“FLP不可能定理”從而尋找工程上可行的共識(shí)算法,比如比特幣系統(tǒng)中通過(guò)假定網(wǎng)絡(luò)為弱同步性,即網(wǎng)絡(luò)節(jié)點(diǎn)間可以快速同步,以及礦工在一個(gè)區(qū)塊上投入有限的時(shí)間等來(lái)規(guī)避“FLP不可能定理”。

通過(guò)調(diào)整問(wèn)題模型規(guī)避“FLP不可能定理”,使得共識(shí)算法存在“工程解”。2000年,Eric Brewer在一次研討會(huì)的報(bào)告中提出了一個(gè)猜想: 分布式系統(tǒng)無(wú)法同時(shí)滿(mǎn)足一致性 (Consistency)、可用性(Availability)和分區(qū)容忍性(Partition Tolerance),最多只能同時(shí)滿(mǎn)足其中兩個(gè)特性,如圖2所示。該猜想于2002年被Seth Gilbert和Nancy Lynch在異步網(wǎng)絡(luò)模型證明,被命名為“CAP定理”[12]。一致性是指分布式系統(tǒng)中所有節(jié)點(diǎn)在同一時(shí)刻持有同樣的數(shù)據(jù)信息; 可用性是指系統(tǒng)處于服務(wù)狀態(tài),當(dāng)客戶(hù)端發(fā)出請(qǐng)求,服務(wù)端能在有效的時(shí)間內(nèi)返回結(jié)果; 分區(qū)容忍性是指允許網(wǎng)絡(luò)中部分節(jié)點(diǎn)不與其他節(jié)點(diǎn)通信,即允許網(wǎng)絡(luò)發(fā)生分區(qū)(不同區(qū)域之間的節(jié)點(diǎn)不能建立通信)?！癈AP定理”指出即使可以設(shè)計(jì)出工程上可行的共識(shí)算法,這個(gè)共識(shí)算法也無(wú)法完美地做到同時(shí)滿(mǎn)足一致性、可用性和分區(qū)容忍性。該定理的提出為共識(shí)算法的設(shè)計(jì)提供了指導(dǎo)性的原則,使研究者不再追求能同時(shí)滿(mǎn)足三個(gè)特性的共識(shí)算法。比如比特幣系統(tǒng)的工作量證明(Proof of Work,PoW)共識(shí)算法不支持分區(qū)容忍性(要求全網(wǎng)節(jié)點(diǎn)參與競(jìng)爭(zhēng)、驗(yàn)證、最后達(dá)成共識(shí)),同時(shí)盡可能滿(mǎn)足一致性和可用性。比特幣系統(tǒng)首次真正實(shí)現(xiàn)了互聯(lián)網(wǎng)規(guī)模的分布式系統(tǒng)的拜占庭容錯(cuò)類(lèi)共識(shí)算法,并且該系統(tǒng)的穩(wěn)定運(yùn)行也驗(yàn)證了此類(lèi)共識(shí)算法的可行性。

圖2 CAP定理Figure 2 CAP Theorem

迄今為止,研究者已經(jīng)在共識(shí)領(lǐng)域做了大量研究工作,從傳統(tǒng)的分布式共識(shí)算法,到受 PoW 共識(shí)算法啟發(fā)后涌現(xiàn)的大量應(yīng)用于區(qū)塊鏈系統(tǒng)的共識(shí)算法,這些共識(shí)算法試圖從不同角度解決區(qū)塊鏈發(fā)展中的問(wèn)題。本文所做工作: 深入調(diào)研并分析區(qū)塊鏈共識(shí)算法及演化歷程; 基于區(qū)塊鏈共識(shí)算法的共識(shí)過(guò)程,提出共識(shí)算法的分類(lèi)模型,并對(duì)各類(lèi)型中的代表性共識(shí)算法進(jìn)行詳細(xì)分析; 從去中心化、可擴(kuò)展性、安全性、一致性、可用性、分區(qū)容忍性六個(gè)層面建立區(qū)塊鏈共識(shí)算法的評(píng)價(jià)指標(biāo)體系,并對(duì)典型的共識(shí)算法進(jìn)行對(duì)比分析,給出各類(lèi)算法綜合性的性能評(píng)價(jià)。通過(guò)對(duì)共識(shí)算法進(jìn)行分類(lèi)以及評(píng)價(jià)指標(biāo)體系的建立,期望對(duì)未來(lái)共識(shí)算法的創(chuàng)新提供參考。

本文的后續(xù)章節(jié)安排如下: 第二節(jié)梳理了當(dāng)前區(qū)塊鏈共識(shí)算法的演化歷程,并展示這些共識(shí)算法的發(fā)展脈絡(luò); 第三節(jié)提出區(qū)塊鏈共識(shí)算法的分類(lèi)模型,在此基礎(chǔ)上,對(duì)各類(lèi)中代表性的共識(shí)算法進(jìn)行詳細(xì)分析; 第四節(jié)提出區(qū)塊鏈共識(shí)算法的評(píng)價(jià)指標(biāo)體系,并對(duì)代表性的共識(shí)算法進(jìn)行對(duì)比分析,給出各類(lèi)算法綜合性的性能評(píng)價(jià)。最后第五節(jié)對(duì)全文進(jìn)行總結(jié)。

2 共識(shí)算法的發(fā)展

分布式共識(shí)算法是分布式計(jì)算領(lǐng)域的核心問(wèn)題,很多研究者為促進(jìn)其發(fā)展做了大量工作[13]。本節(jié)按照時(shí)間順序給出共識(shí)算法的發(fā)展簡(jiǎn)史,并梳理出這些共識(shí)算法的演進(jìn)關(guān)系,如圖3所示,箭頭方向代表演進(jìn)方向,比如共識(shí)算法A指向B,則代表算法B借鑒算法A; 多個(gè)算法比如A和B共同指向C,則代表算法C同時(shí)借鑒A和B。

圖3 共識(shí)算法匯總Figure 3 Summary of consensus algorithms

1982 年,由 Leslie Lamport、Robert Shostak、Marshall Pease正式提出“拜占庭將軍問(wèn)題” ,并給出了基于口頭消息和簽名消息的解決方案,開(kāi)創(chuàng)了拜占庭容錯(cuò)類(lèi)算法的先河。從此,分布式系統(tǒng)共識(shí)算法被分為拜占庭容錯(cuò)類(lèi)算法和非拜占庭容錯(cuò)類(lèi)算法。由于拜占庭容錯(cuò)類(lèi)算法(Byzantine Fault Tolerance,BFT)的高復(fù)雜度,BFT類(lèi)算法一直未得到實(shí)際應(yīng)用,直到1999 年,Barbara Liskov 等提出了實(shí)用拜占庭容錯(cuò)算法(Practical Byzantine Fault Tolerance,PBFT)[14],將原始拜占庭容錯(cuò)算法的復(fù)雜度由指數(shù)級(jí)降低到多項(xiàng)式級(jí),將拜占庭容錯(cuò)類(lèi)算法真正引入工程領(lǐng)域。

1988年提出的Viewstamped Replication(VR)一致性算法[15]和1989年提出的Paxos算法[16-18]開(kāi)創(chuàng)了非拜占庭容錯(cuò)類(lèi)算法的先河; 基于 Paxos算法,之后出現(xiàn)了多種 Paxos變種算法[19-21]; 除此之外,還有兩階段提交算法(Two-Phase Commit)[22]、三階段提交算法 (Three-Phase Commit)[23]、Zyzzyva[24]、Zab[25]、Kafka[26]以及2013年提出的Paxos算法簡(jiǎn)化版——Raft算法[27]。以上這些算法都是非拜占庭容錯(cuò)類(lèi)算法。

2008年,“中本聰”發(fā)表的比特幣論文開(kāi)啟了區(qū)塊鏈共識(shí)算法研究的先河。比特幣系統(tǒng)的工作量證明共識(shí)算法(Proof of Work,PoW)以基于工作量證明的方式[28-30]開(kāi)創(chuàng)性地解決了互聯(lián)網(wǎng)規(guī)模的分布式系統(tǒng)拜占庭容錯(cuò)問(wèn)題。PoW 的核心思想是通過(guò)算力競(jìng)爭(zhēng)達(dá)成共識(shí)保證數(shù)據(jù)的一致性,同時(shí)保證了比特幣系統(tǒng)的安全性和去中心化程度,但同時(shí)也帶來(lái)了電力資源的大量消耗; 2011年權(quán)益證明機(jī)制(Proof of Stake,PoS)[31]被提出,一定程度上解決了 PoW 電力資源消耗的問(wèn)題; 2013年提出瑞波共識(shí)算法[32],通過(guò)使用集體信任的子網(wǎng)絡(luò) (Collectively-Trusted Subnetworks),實(shí)現(xiàn)了低延遲、高魯棒性的拜占庭容錯(cuò)共識(shí)算法,成功應(yīng)用于基于區(qū)塊鏈技術(shù)的金融結(jié)算網(wǎng)絡(luò); 之后基于Ripple協(xié)議,結(jié)合BFT算法提出的恒星共識(shí)協(xié)議[33]是第一個(gè)可證明安全的共識(shí)協(xié)議;同年超級(jí)賬本鋸齒湖項(xiàng)目(Hyperledger Sawtooth)中提出的法定人數(shù)投票共識(shí)算法(Quorum Voting)旨在確定立即交易的狀態(tài); 授權(quán)股份證明機(jī)制(Delegated Proof-of-Stake,DPoS)[34]也于2013年提出,引入“民主集中式”的共識(shí)準(zhǔn)則,提升了PoS的可擴(kuò)展性,但21個(gè)超級(jí)節(jié)點(diǎn)的引入一定程度上降低了去中心化程度; 除此之外,Sleepy Consenus[35]、Ouroboros[36]等共識(shí)算法中也應(yīng)用了節(jié)點(diǎn)的權(quán)益; 2014年提出的結(jié)合PoS和PBFT的Tendermint[37]共識(shí)算法以及之后基于Tendermint的改進(jìn)方案HoneyBadger[38],旨在解決原PoS面臨的“無(wú)利害關(guān)系”問(wèn)題(Nothing at Stake); 同年提出的Tangaroa共識(shí)算法[39]結(jié)合PBFT對(duì)Raft算法進(jìn)行改進(jìn),繼承了Raft算法的簡(jiǎn)潔易理解特點(diǎn),同時(shí)具有拜占庭容錯(cuò)能力; 之后受 Tangaroa啟發(fā)演變而來(lái)的Scalable BFT算法[40]相比Tangaroa具有更好的性能; 2014—2017年還相繼出現(xiàn)了權(quán)益流通證明(Proof of Stake Velocity,PoSV)[41]、空間證明(Proof of Space,PoS)[42]、燃燒證明(Proof of Burn,PoB)[43]、活動(dòng)證明(Proof of Activity,PoA)[44]、消逝時(shí)間證明(Proof of Elapsed Time,PoET)[45]、幸運(yùn)證明(Proof of Luck,PoL)[46]、有用工作證明(Proof of Useful Work,PoUW)[47]等、權(quán)威證明(Proof of Authority,PoA)[48]等,以不同的競(jìng)爭(zhēng)方式替代PoW中的算力競(jìng)爭(zhēng)以及基于PoW和PoS的二跳(2-hop)算法等解決PoW中的資源消耗和安全問(wèn)題; 2015年以太坊中提出 Casper協(xié)議[49],在PoS中引入權(quán)益抵押; 2016年,國(guó)內(nèi)NEO[50]基于 PBFT和 PoS提出授權(quán)拜占庭容錯(cuò)(Delegated Byzantine Fault Tolerance,DBFT)共識(shí)算法[51],解決了PoW和PoS中的最終一致性問(wèn)題; 同年,由圖靈獎(jiǎng)得主Micali提出的AlgoRand共識(shí)算法[52],利用密碼抽簽算法隨機(jī)選擇部分節(jié)點(diǎn)參與共識(shí)過(guò)程,被認(rèn)為是適用于公鏈的高可擴(kuò)展性共識(shí)算法; 此外,比特幣網(wǎng)絡(luò)擴(kuò)展協(xié)議 Bitcoin-NG[53],基于 Bitcoin-NG的改進(jìn)方案 Byzcoin[54]、基于分片技術(shù)的共識(shí)協(xié)議Elastico[55]、以及基于 Elastico和 Byzcoin提出的ByzCoinX方案[56],這些方案從不同的角度提升區(qū)塊鏈系統(tǒng)的可擴(kuò)展性; 2018年也出現(xiàn)了一些代表性的共識(shí)算法: 3月 OCE(Ontology Consensus Engine,OCE)項(xiàng)目[57]中應(yīng)用的可驗(yàn)證拜占庭容錯(cuò)算法(Verifiable Byzantine Fault Tolerance,VBFT)共識(shí)算法[58],結(jié)合了 PoS、BFT和可驗(yàn)證的隨機(jī)函數(shù)(Verifiable Random Function,VRF)[59]; 5月,康奈爾大學(xué)教授EMin Gun Sirer發(fā)布了基于 PoW和BFT的共識(shí)協(xié)議族Snowflake to Avalanche 共識(shí)算法[60],簡(jiǎn)單、高效且安全; 8月,以太坊的創(chuàng)始人 Vitalik Buterin 發(fā)表“99% Fault Tolerant Consensus”共識(shí)算法[61],僅需要1%的誠(chéng)實(shí)節(jié)點(diǎn)就能保障區(qū)塊鏈系統(tǒng)的正常運(yùn)行; 11月,YEE 項(xiàng)目[62]發(fā)布的基于知識(shí)推理的Tetris共識(shí)算法[62],是一種具備最終一致性的高效共識(shí)算法。

本節(jié)按照時(shí)間順序列出各共識(shí)算法,這些共識(shí)算法包括傳統(tǒng)的分布式共識(shí)算法和區(qū)塊鏈中應(yīng)用的共識(shí)算法,并梳理出這些共識(shí)算法之間的演進(jìn)關(guān)系。第三節(jié)將對(duì)在區(qū)塊鏈中應(yīng)用的共識(shí)算法建立分類(lèi)模型并描述每類(lèi)中代表性的算法。

3 共識(shí)算法分類(lèi)

為了對(duì)現(xiàn)有的共識(shí)算法有更清晰的理解,本節(jié)對(duì)共識(shí)算法的共識(shí)過(guò)程進(jìn)行建模,并從共識(shí)過(guò)程的角度對(duì)當(dāng)前主流的算法進(jìn)行分類(lèi),并詳細(xì)闡述各類(lèi)型中的典型共識(shí)算法。

算法的共識(shí)過(guò)程總體上分為三個(gè)階段,如圖 4所示: 創(chuàng)建區(qū)塊、驗(yàn)證區(qū)塊,提交區(qū)塊。根據(jù)共識(shí)協(xié)議,從參與共識(shí)過(guò)程的節(jié)點(diǎn)中選擇主節(jié)點(diǎn)創(chuàng)建新區(qū)塊(定義主節(jié)點(diǎn)為每輪共識(shí)過(guò)程中產(chǎn)生有效區(qū)塊的節(jié)點(diǎn)); 然后新區(qū)塊交由其他參與共識(shí)的節(jié)點(diǎn)進(jìn)行獨(dú)立驗(yàn)證; 通過(guò)驗(yàn)證的新區(qū)塊會(huì)被節(jié)點(diǎn)提交到本地區(qū)塊鏈中,達(dá)成對(duì)最新高度區(qū)塊的共識(shí); 至此完成共識(shí),開(kāi)啟下一輪共識(shí)過(guò)程。

圖4 共識(shí)過(guò)程及分類(lèi)模型Figure 4 The basic consensus process and classification model

共識(shí)算法的分類(lèi)方式有很多,比如在性能層面:從數(shù)據(jù)一致性的角度將共識(shí)算法分為強(qiáng)一致性共識(shí)算法、弱一致性(最終一致性)共識(shí)算法; 從拜占庭容錯(cuò)的角度將共識(shí)算法分為拜占庭容錯(cuò)共識(shí)算法、非拜占庭容錯(cuò)共識(shí)算法。在應(yīng)用層面: 可以將共識(shí)算法分為適用于公鏈、聯(lián)盟鏈、私鏈的共識(shí)算法。本節(jié)從共識(shí)過(guò)程出發(fā),按照主節(jié)點(diǎn)的產(chǎn)生方式將共識(shí)算法分為競(jìng)爭(zhēng)類(lèi)、選舉類(lèi)、隨機(jī)類(lèi)以及其他類(lèi)型。競(jìng)爭(zhēng)類(lèi): 所有參與共識(shí)的節(jié)點(diǎn)通過(guò)參與特定的競(jìng)爭(zhēng)方式,在競(jìng)爭(zhēng)中獲勝的節(jié)點(diǎn)成為主節(jié)點(diǎn)。競(jìng)爭(zhēng)類(lèi)共識(shí)算法以PoW為代表,還有權(quán)益證明、空間證明等等。選舉類(lèi): 所有節(jié)點(diǎn)通過(guò)投票的方式選擇出部分節(jié)點(diǎn)參與共識(shí)過(guò)程,這些被選擇的節(jié)點(diǎn)依次輪流成為主節(jié)點(diǎn)。選舉類(lèi)共識(shí)算法以區(qū)塊鏈中應(yīng)用的傳統(tǒng) BFT類(lèi)共識(shí)算法為代表,比如PBFT、DBFT等。隨機(jī)類(lèi):通過(guò)設(shè)計(jì)特定的隨機(jī)算法從參與共識(shí)的節(jié)點(diǎn)中隨機(jī)選擇節(jié)點(diǎn)作為主節(jié)點(diǎn)。競(jìng)爭(zhēng)類(lèi)共識(shí)算法以 PoET、Algorand、Ouroboros為代表。以下部分,從共識(shí)過(guò)程角度對(duì)各類(lèi)中的代表算法進(jìn)行詳細(xì)分析。

3.1 競(jìng)爭(zhēng)類(lèi)

PoW 共識(shí)算法在比特幣項(xiàng)目中的成功運(yùn)用,激發(fā)了一系列通過(guò)資源、能力、名譽(yù)、權(quán)益等證明方式來(lái)競(jìng)爭(zhēng)成為主節(jié)點(diǎn)的共識(shí)算法。比如Peercoin項(xiàng)[63]目中的權(quán)益證明(Proof of Stake,PoS)、Parity項(xiàng)目[64]中的權(quán)威證明(Proof of Authority,PoA)、Burstcoin項(xiàng)目[65]中的空間證明(Proof of Sapce,PoSpace)、GoChain項(xiàng)目[66]中的信譽(yù)證明(Proof of Reputation,PoR)等[67]。從命名方式的角度,這些共識(shí)算法應(yīng)該被稱(chēng)為證明類(lèi)算法,但從主節(jié)點(diǎn)的選擇方式角度,相同時(shí)間內(nèi)完成證明最多的節(jié)點(diǎn)才成為主節(jié)點(diǎn),因此把這些共識(shí)算法歸納為競(jìng)爭(zhēng)類(lèi)更為合理。競(jìng)爭(zhēng)類(lèi)共識(shí)算法在每一輪主節(jié)點(diǎn)的選擇中,會(huì)設(shè)置一個(gè)競(jìng)爭(zhēng)成功的標(biāo)準(zhǔn),最先達(dá)到標(biāo)準(zhǔn)的共識(shí)節(jié)點(diǎn)成為主節(jié)點(diǎn)。競(jìng)爭(zhēng)類(lèi)算法的共識(shí)過(guò)程如圖 5所示。本小節(jié)對(duì)典型的PoW、PoS、PoSpace進(jìn)行詳細(xì)分析,幫助理解競(jìng)爭(zhēng)類(lèi)共識(shí)算法。

3.1.1 PoW

PoW 共識(shí)算法中,所有參與共識(shí)的節(jié)點(diǎn)通過(guò)消耗算力解決數(shù)學(xué)難題來(lái)競(jìng)爭(zhēng)成為主節(jié)點(diǎn),由最先解決數(shù)學(xué)難題的節(jié)點(diǎn)成為主節(jié)點(diǎn)。在比特幣系統(tǒng)中,中本聰采用安全散列算法,將數(shù)學(xué)難題設(shè)計(jì)為對(duì)區(qū)塊頭信息的雙SHA256哈希運(yùn)算,即:

其中F為雙 SHA256哈希運(yùn)算函數(shù)[68],T是目標(biāo)哈希值,BlockHeader為區(qū)塊頭信息,其中包含Nonce字段,求解合適的Nonce字段使得對(duì)完整BlockHeader的哈希運(yùn)算結(jié)果滿(mǎn)足目標(biāo)值要求。

共識(shí)過(guò)程如圖 5所示,第一步全網(wǎng)節(jié)點(diǎn)接收并轉(zhuǎn)發(fā)交易信息,將接收到的交易信息打包進(jìn)新區(qū)塊,然后全網(wǎng)所有節(jié)點(diǎn)基于本節(jié)點(diǎn)打包的新區(qū)塊設(shè)置區(qū)塊頭中的Nonce字段,計(jì)算整個(gè)區(qū)塊頭信息的哈希值,使其滿(mǎn)足目標(biāo)值的要求; 率先完成計(jì)算工作的節(jié)點(diǎn)成為主節(jié)點(diǎn),并將自己的區(qū)塊廣播給其余節(jié)點(diǎn);第二步,未競(jìng)爭(zhēng)成功的其余節(jié)點(diǎn)在接收到新區(qū)塊后,放棄計(jì)算本地新區(qū)塊,并對(duì)接收到的新區(qū)塊進(jìn)行驗(yàn)證; 第三步,節(jié)點(diǎn)在驗(yàn)證通過(guò)新區(qū)塊后,將其添加到本地區(qū)塊鏈,所有節(jié)點(diǎn)達(dá)成對(duì)最新高度區(qū)塊的共識(shí)。

圖5 競(jìng)爭(zhēng)類(lèi)算法共識(shí)過(guò)程Figure 5 The consensus process of competition classification algorithms

由于安全散列算法的單向不可逆性,使得 PoW算法難計(jì)算易驗(yàn)證。從CPU到GPU再到ASIC礦機(jī),隨著算力不斷增強(qiáng),越能快速求解滿(mǎn)足條件的Nonce字段值,競(jìng)爭(zhēng)為主節(jié)點(diǎn)的概率也就越大。

PoW 計(jì)算密集型屬性防止了惡意節(jié)點(diǎn)冒充多個(gè)節(jié)點(diǎn)來(lái)實(shí)施惡意攻擊篡改交易數(shù)據(jù)等,保障了區(qū)塊鏈的安全; 同時(shí)帶來(lái)的一個(gè)明顯缺點(diǎn)就是耗費(fèi)大量資源; 另外隨著整個(gè)網(wǎng)絡(luò)新區(qū)塊產(chǎn)生難度的增加,出于成本和收益的博弈,部分虧損的小算力節(jié)點(diǎn)會(huì)退出比特幣系統(tǒng),整個(gè)網(wǎng)絡(luò)的新區(qū)塊的生成趨向于算力高的節(jié)點(diǎn),中心化程度增加。Eyal等[69]提出PoW共識(shí)還存在自私挖礦攻擊的風(fēng)險(xiǎn),自私挖礦的收益比例大于其在全網(wǎng)的算力比例,促使理性的節(jié)點(diǎn)加入自私挖礦礦池,算力集中之后進(jìn)一步增加 51%攻擊的風(fēng)險(xiǎn)。

3.1.2 PoS

Peercoin項(xiàng)目[63]中實(shí)現(xiàn)的 PoS共識(shí)算法是為了降低算力的消耗。PoS延續(xù)了PoW算法的競(jìng)爭(zhēng)理念,只不過(guò)相對(duì)于PoW中Nonce字段的大搜索空間而言,PoS將搜索空間限制在一個(gè)計(jì)算量可接受的范圍;除此外,PoS中還引入了“幣齡”作為權(quán)益,即:

其中,Coinage是“幣齡”,Coin為持有的貨幣,Age為持續(xù)持有的時(shí)間。通過(guò)減小搜索空間以及引入“幣齡”,PoS將數(shù)學(xué)問(wèn)題設(shè)計(jì)為:

其中F為雙SHA256哈希運(yùn)算函數(shù);BlockHeader為區(qū)塊頭信息,其中包含Timestamp字段,取值范圍是上一個(gè)區(qū)塊時(shí)間和當(dāng)前時(shí)間之間,遠(yuǎn)小于 PoW 中Nonce字段的搜索空間大小;Weight是用于競(jìng)爭(zhēng)所消耗的“幣齡”權(quán)重,T是目標(biāo)哈希值,與PoW中的T相同。

PoS的共識(shí)過(guò)程與PoW一致,唯一不同是解決的數(shù)學(xué)問(wèn)題不同,其余過(guò)程均如圖5所示。

與PoW相比,PoS的數(shù)學(xué)問(wèn)題中自變量的搜索空間減小,同時(shí)不等式右側(cè)引入“幣齡”權(quán)重,對(duì)于同一T,在每輪競(jìng)爭(zhēng)中所投入的“幣齡”越多,權(quán)重越大,競(jìng)爭(zhēng)中獲勝的概率也越大。

PoS將算力競(jìng)爭(zhēng)轉(zhuǎn)化為權(quán)益競(jìng)爭(zhēng),不僅節(jié)約算力,權(quán)益的引入也能夠防止節(jié)點(diǎn)發(fā)動(dòng)惡意攻擊; 同時(shí)促使所有節(jié)點(diǎn)有責(zé)任維護(hù)區(qū)塊鏈的安全穩(wěn)定運(yùn)行以保障自身權(quán)益; PoS雖然降低了算力資源的消耗,但是沒(méi)有解決中心化程度增強(qiáng)的問(wèn)題,新區(qū)塊的生成趨向于權(quán)益高的節(jié)點(diǎn)。PoS中需要擁有超全網(wǎng)一半的權(quán)益發(fā)動(dòng) 51%攻擊,但其成本高于擁有超全網(wǎng)一半的算力[70],另外創(chuàng)建區(qū)塊需要消耗權(quán)益,使得PoS持續(xù)進(jìn)行 51%攻擊的難度增加,一定程度上降低了安全風(fēng)險(xiǎn)[31]。

3.1.3 PoSpace

Burstcoin項(xiàng)目[65]中的共識(shí)算法為 PoSpace,基于存儲(chǔ)空間的競(jìng)爭(zhēng)機(jī)制。在PoSpace中節(jié)點(diǎn)分為普通節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)兩種角色。普通節(jié)點(diǎn)下載特定序列的數(shù)據(jù)塊(由節(jié)點(diǎn)用戶(hù)公鑰決定)占據(jù)硬盤(pán)空間參與主節(jié)點(diǎn)的競(jìng)爭(zhēng),校驗(yàn)節(jié)點(diǎn)存儲(chǔ)普通節(jié)點(diǎn)的部分存儲(chǔ)信息以便驗(yàn)證普通節(jié)點(diǎn)。

在每輪創(chuàng)建新區(qū)塊的競(jìng)爭(zhēng)中,校驗(yàn)節(jié)點(diǎn)向普通節(jié)點(diǎn)發(fā)起“挑戰(zhàn)”,“挑戰(zhàn)”為普通節(jié)點(diǎn)所存儲(chǔ)數(shù)據(jù)塊的某種隨機(jī)組合。普通節(jié)點(diǎn)根據(jù)“挑戰(zhàn)”信息,生成對(duì)應(yīng)組合數(shù)據(jù)的哈希摘要,由校驗(yàn)節(jié)點(diǎn)驗(yàn)證哈希值是否正確,驗(yàn)證通過(guò)則說(shuō)明普通節(jié)點(diǎn)確實(shí)存儲(chǔ)了相應(yīng)的數(shù)據(jù)。PoSpace中定義了一個(gè)質(zhì)量函數(shù)作為競(jìng)爭(zhēng)指標(biāo):

其中,hash為普通節(jié)點(diǎn)被驗(yàn)證通過(guò)的哈希值,S為數(shù)據(jù)占用存儲(chǔ)空間的大小。在每輪競(jìng)爭(zhēng)中,質(zhì)量函數(shù)結(jié)果最小的節(jié)點(diǎn)獲勝。

PoSpace的共識(shí)過(guò)程第一步通過(guò)占用存儲(chǔ)空間加入網(wǎng)絡(luò),然后對(duì)“挑戰(zhàn)”得到的哈希結(jié)果計(jì)算質(zhì)量函數(shù),質(zhì)量函數(shù)結(jié)果最小的節(jié)點(diǎn)成為主節(jié)點(diǎn),將區(qū)塊廣播給其余未競(jìng)爭(zhēng)成功的節(jié)點(diǎn); 第二步其余節(jié)點(diǎn)對(duì)接收到的新區(qū)塊進(jìn)行驗(yàn)證,驗(yàn)證通過(guò)后進(jìn)入第三步將新區(qū)塊提交到本地區(qū)塊鏈,達(dá)成對(duì)最新高度區(qū)塊的共識(shí)。從質(zhì)量函數(shù)的定義可以看出,數(shù)據(jù)占用空間S越大,質(zhì)量函數(shù)值越小,獲勝的概率越大。

PoSpace共識(shí)算法使用存儲(chǔ)空間代替計(jì)算,節(jié)約電力資源; 同時(shí)該共識(shí)協(xié)議下,節(jié)點(diǎn)初次接入網(wǎng)絡(luò)時(shí)確定存儲(chǔ)空間大小,之后不能擴(kuò)容,防止了 PoW共識(shí)算法中“礦池”(將不同節(jié)點(diǎn)的算力集合成一個(gè)大的算力節(jié)點(diǎn))的出現(xiàn),一定程度上避免了中心化程度增強(qiáng)的問(wèn)題,同時(shí)降低了安全風(fēng)險(xiǎn)。

3.2 選舉類(lèi)

除了競(jìng)爭(zhēng)方式選擇主節(jié)點(diǎn)外,也可以通過(guò)選舉的方式選擇主節(jié)點(diǎn)。所有節(jié)點(diǎn)投票選擇,根據(jù)投票結(jié)果,有的共識(shí)算法是產(chǎn)生一個(gè)主節(jié)點(diǎn)集合,由這些節(jié)點(diǎn)依次輪流成為主節(jié)點(diǎn); 有的共識(shí)算法是只產(chǎn)生一個(gè)主節(jié)點(diǎn)負(fù)責(zé)創(chuàng)建區(qū)塊,下一輪重新投票。選舉類(lèi)的共識(shí)過(guò)程如圖6所示,第一步是選出信任節(jié)點(diǎn)集合,信任節(jié)點(diǎn)依次輪流作為主節(jié)點(diǎn); 第二步是區(qū)塊驗(yàn)證,區(qū)塊驗(yàn)證方式分類(lèi)兩大類(lèi),一類(lèi)與競(jìng)爭(zhēng)類(lèi)算法相似,主節(jié)點(diǎn)廣播區(qū)塊到其余節(jié)點(diǎn)進(jìn)行驗(yàn)證,一類(lèi)是主節(jié)點(diǎn)的區(qū)塊經(jīng)過(guò)三輪 BFT類(lèi)的投票過(guò)程進(jìn)行驗(yàn)證; 第三步是節(jié)點(diǎn)提交通過(guò)驗(yàn)證的區(qū)塊,達(dá)成共識(shí)狀態(tài)。本節(jié)選擇授權(quán)股份證明算法(DPoS)、實(shí)用拜占庭容錯(cuò)算法(PBFT)、授權(quán)拜占庭容錯(cuò)算法(DBFT)進(jìn)行描述,幫助理解選舉類(lèi)的共識(shí)算法。

圖6 選舉類(lèi)算法共識(shí)過(guò)程Figure 6 The consensus process of delegation classification algorithms

3.2.1 DPoS

EOS項(xiàng)目[71]中實(shí)現(xiàn)的DPoS共識(shí)算法旨在解決PoS中主節(jié)點(diǎn)的產(chǎn)生趨向于高權(quán)益節(jié)點(diǎn)的問(wèn)題,同時(shí)提高了PoS的共識(shí)效率。

DPoS在PoS中引入選舉機(jī)制。DPoS將節(jié)點(diǎn)分為普通節(jié)點(diǎn)和信任節(jié)點(diǎn)兩種角色。普通節(jié)點(diǎn)可以投票選擇信任節(jié)點(diǎn)或者被投票成為信任節(jié)點(diǎn)。在DPoS中,節(jié)點(diǎn)消耗權(quán)益作為投票權(quán),根據(jù)權(quán)益的加權(quán)結(jié)果產(chǎn)生最受信任的N個(gè)節(jié)點(diǎn)成為信任節(jié)點(diǎn)集合D{D1,… ,DN},每個(gè)信任節(jié)點(diǎn)Di,i=1→N依次被賦予固定的期限(比如 2秒)成為主節(jié)點(diǎn),授權(quán)時(shí)間結(jié)束后,創(chuàng)建權(quán)依次交由下一個(gè)信任節(jié)點(diǎn)。信任節(jié)點(diǎn)集合D循環(huán)結(jié)束之后,重新選舉調(diào)整D,惡意節(jié)點(diǎn)將在下輪選舉中失去其他節(jié)點(diǎn)的信任。

共識(shí)過(guò)程僅由信任節(jié)點(diǎn)集合D中所有節(jié)點(diǎn)參與,當(dāng)下被授權(quán)的信任節(jié)點(diǎn)Di創(chuàng)建新區(qū)塊后廣播到其余信任節(jié)點(diǎn)Dj≠i進(jìn)行驗(yàn)證,在驗(yàn)證成功后將區(qū)塊添加到本地,達(dá)成對(duì)最新高度區(qū)塊的共識(shí)。

通過(guò)基于權(quán)益的民主投票產(chǎn)生信任節(jié)點(diǎn)集合,每個(gè)節(jié)點(diǎn)都可以參與到信任節(jié)點(diǎn)的選擇上,Di輪流作為主節(jié)點(diǎn),避免了主節(jié)點(diǎn)的產(chǎn)生趨向于高權(quán)益節(jié)點(diǎn)的問(wèn)題,但選舉的信任節(jié)點(diǎn)全權(quán)負(fù)責(zé)創(chuàng)建區(qū)塊,這在一定程度上降低了去中心化程度; 同時(shí)僅由D{D1,… ,DN}進(jìn)行驗(yàn)證,使得共識(shí)效率得到提升;另外,區(qū)塊的產(chǎn)生不需要消耗算力,相對(duì)于PoS更加節(jié)省能耗。

3.2.2 PBFT

Fabric v0.6.0[72]中實(shí)現(xiàn)了PBFT共識(shí)算法。該共識(shí)算法從全網(wǎng)節(jié)點(diǎn)選擇一個(gè)主節(jié)點(diǎn)負(fù)責(zé)創(chuàng)建區(qū)塊,然后經(jīng)過(guò)三階段投票達(dá)成共識(shí): 預(yù)準(zhǔn)備階段,準(zhǔn)備階段,提交階段。如圖7所示,主要過(guò)程如下:

預(yù)準(zhǔn)備階段: 從全網(wǎng)選擇一個(gè)主節(jié)點(diǎn); 每個(gè)節(jié)點(diǎn)把客戶(hù)端發(fā)來(lái)的交易信息向全網(wǎng)廣播,主節(jié)點(diǎn)收集所有交易信息,創(chuàng)建新區(qū)塊并向全網(wǎng)廣播;

準(zhǔn)備階段: 每個(gè)節(jié)點(diǎn)在收到主節(jié)點(diǎn)發(fā)送的區(qū)塊信息后,從預(yù)準(zhǔn)備階段進(jìn)入到準(zhǔn)備階段,節(jié)點(diǎn)對(duì)區(qū)塊進(jìn)行驗(yàn)證,驗(yàn)證通過(guò)后向其他節(jié)點(diǎn)廣播一條準(zhǔn)備消息;

提交階段: 節(jié)點(diǎn)在向全網(wǎng)廣播準(zhǔn)備消息之后進(jìn)入提交階段,如果節(jié)點(diǎn)收到超過(guò)2/3節(jié)點(diǎn)的準(zhǔn)備消息,就向全網(wǎng)廣播一條提交消息; 如果一個(gè)節(jié)點(diǎn)收到超過(guò)2/3節(jié)點(diǎn)的提交消息,即可提交新區(qū)塊到本地區(qū)塊鏈,達(dá)成對(duì)最新高度區(qū)塊的共識(shí)。

PBFT中無(wú)權(quán)益的抵押或競(jìng)爭(zhēng)資源的消耗,使得惡意節(jié)點(diǎn)的成本降低,PBFT通過(guò)三階段的投票機(jī)制排除惡意節(jié)點(diǎn)對(duì)共識(shí)的影響,提供不超過(guò)1/3總節(jié)點(diǎn)數(shù)量的容錯(cuò)能力,但O(N2) 的通信復(fù)雜度使得系統(tǒng)性能隨著網(wǎng)絡(luò)規(guī)模的增加而下降。

圖7 PBFT三階段示意圖Figure 7 The three-phase process diagram of PBFT

3.2.3 DBFT

NEO項(xiàng)目[50]中提出DBFT算法。DBFT改進(jìn)自PBFT算法,PBFT算法共識(shí)過(guò)程需要全部節(jié)點(diǎn)的參與,且需要通過(guò)3輪網(wǎng)絡(luò)請(qǐng)求確認(rèn)來(lái)達(dá)成共識(shí),網(wǎng)絡(luò)通信復(fù)雜度為O(N2),N為全網(wǎng)節(jié)點(diǎn)的數(shù)量,可擴(kuò)展性差,隨著網(wǎng)絡(luò)規(guī)模增加,難以快速達(dá)成一致。NEO的解決方案是投票選取出部分節(jié)點(diǎn)參與共識(shí),由此減少網(wǎng)絡(luò)通信消耗、提高可擴(kuò)展性、同時(shí)提升交易處理速度。

DBFT共識(shí)過(guò)程: 所有節(jié)點(diǎn)投票選舉記賬節(jié)點(diǎn)集合(記賬節(jié)點(diǎn)即信任節(jié)點(diǎn),此處為了遵從原算法的描述),記賬節(jié)點(diǎn)集合完成共識(shí)過(guò)程,其余節(jié)點(diǎn)為非記賬節(jié)點(diǎn),不參與共識(shí)過(guò)程,只采納最終的共識(shí)結(jié)果。接下來(lái)由記賬節(jié)點(diǎn)集合中選舉出議長(zhǎng)(議長(zhǎng)即負(fù)責(zé)創(chuàng)建區(qū)塊的主節(jié)點(diǎn)),其他記賬節(jié)點(diǎn)為議員; 在每輪共識(shí)中,議長(zhǎng)提出新區(qū)塊,由議員進(jìn)行確認(rèn)并廣播確認(rèn)結(jié)果; 當(dāng)節(jié)點(diǎn)收到超過(guò) 2/3記賬人節(jié)點(diǎn)發(fā)送的確認(rèn)消息后,則在本地添加區(qū)塊,即對(duì)最新高度的區(qū)塊達(dá)成共識(shí); 之后重新選擇議長(zhǎng),開(kāi)啟新一輪共識(shí)過(guò)程。

DBFT將共識(shí)過(guò)程的參與范圍縮小為選舉出來(lái)的記賬節(jié)點(diǎn)集合,雖然通信復(fù)雜度依然為O(N2),但是縮小了共識(shí)節(jié)點(diǎn)網(wǎng)絡(luò)規(guī)模,減少達(dá)成共識(shí)的通信成本。安全性上,DBFT被證明在惡意節(jié)點(diǎn)少于總節(jié)點(diǎn)數(shù)量1/3的情況下也可能導(dǎo)致網(wǎng)絡(luò)分叉[73]。DBFT 2.0中[74]通過(guò)增加commit階段,避免出現(xiàn)分叉,并增加兩種狀態(tài)恢復(fù)機(jī)制,使得離線(xiàn)共識(shí)節(jié)點(diǎn)可以更快地從異常情況中恢復(fù),雖然提升了 DBFT算法的可靠性,但安全性依然沒(méi)有得到徹底解決,目前仍在完善。

3.3 隨機(jī)類(lèi)

除競(jìng)爭(zhēng)、選舉外,也可以通過(guò)隨機(jī)方式選擇主節(jié)點(diǎn)。對(duì)于隨機(jī)方式,可以設(shè)計(jì)隨機(jī)函數(shù)使得每個(gè)節(jié)點(diǎn)成為主節(jié)點(diǎn)的概率與節(jié)點(diǎn)所持有的某種資源成比例,也可以設(shè)計(jì)隨機(jī)函數(shù)使得每個(gè)節(jié)點(diǎn)成為主節(jié)點(diǎn)的概率相等。隨機(jī)類(lèi)的共識(shí)過(guò)程與競(jìng)爭(zhēng)類(lèi)共識(shí)過(guò)程相似,如圖 5所示,只是第一步通過(guò)隨機(jī)算法隨機(jī)選擇主節(jié)點(diǎn)。本節(jié)描述銜尾蛇(Ouroboros)、消逝時(shí)間證明(PoET)兩個(gè)共識(shí)算法,幫助理解隨機(jī)類(lèi)的共識(shí)算法。

3.3.1 Ouroboros

Cardano項(xiàng)目[75]中Ouroboros共識(shí)算法的核心思想是根據(jù)節(jié)點(diǎn)權(quán)益大小,隨機(jī)地選出主節(jié)點(diǎn),節(jié)點(diǎn)權(quán)益越大被選中的概率越大。

如圖8所示,Ouroboros共識(shí)算法將時(shí)間分段劃分,一個(gè)時(shí)間段稱(chēng)為一個(gè)epoch; 以epoch為周期,每個(gè)epoch中劃分多個(gè)時(shí)間slot; 每個(gè)slot時(shí)間期限內(nèi),由隨機(jī)算法隨機(jī)選擇主節(jié)點(diǎn),該隨機(jī)算法在數(shù)學(xué)上證明是不可被預(yù)知的。

其中,S為權(quán)益持有者候選人集合,ρ為隨機(jī)種子,slj表示該epoch中第j個(gè)slot,Si∈S表示主節(jié)點(diǎn)。該隨機(jī)算法從候選人集合S為每個(gè)slot選擇主節(jié)點(diǎn)。在整個(gè)epoch周期中,S和ρ不變,直到周期結(jié)束之后,產(chǎn)生新的ρ,更新S,開(kāi)啟下一個(gè)epoch周期。

圖8 Ouroboros示意圖Figure 8 The diagram of Ouroboros

每個(gè)節(jié)點(diǎn)根據(jù)當(dāng)前epoch的種子ρ,執(zhí)行隨機(jī)函數(shù)F獲得當(dāng)前slot主節(jié)點(diǎn); 若是自己,則打包交易,創(chuàng)建區(qū)塊; 否則等待主節(jié)點(diǎn)出塊并廣播,對(duì)接收到的區(qū)塊進(jìn)行驗(yàn)證,如果長(zhǎng)時(shí)間未收到(超出一個(gè)slot的時(shí)間)則認(rèn)為當(dāng)前slot無(wú)區(qū)塊產(chǎn)生; 在當(dāng)前epoch中不斷重復(fù)這個(gè)過(guò)程直到這個(gè)epoch中的所有slot結(jié)束。

與選舉類(lèi)相似,隨機(jī)產(chǎn)生主節(jié)點(diǎn)的方式也會(huì)減少資源的消耗; 但不同于選舉類(lèi)中主節(jié)點(diǎn)的產(chǎn)生需要節(jié)點(diǎn)之間網(wǎng)絡(luò)通信進(jìn)行投票,隨機(jī)類(lèi)使用隨機(jī)算法產(chǎn)生主節(jié)點(diǎn)的方式無(wú)需網(wǎng)絡(luò)通信,縮短了共識(shí)時(shí)間,提高了共識(shí)效率,增強(qiáng)可擴(kuò)展性。Aggelos Kiayias等[76]對(duì)Ouroboros的安全性給出了嚴(yán)密的證明,并提出了全新的獎(jiǎng)勵(lì)機(jī)制防止自私挖礦攻擊。

3.3.2 PoET

PoET雖然從名字看像是競(jìng)爭(zhēng)類(lèi)的共識(shí)算法,但本質(zhì)上是通過(guò)隨機(jī)時(shí)間長(zhǎng)短來(lái)選擇主節(jié)點(diǎn)。

基于Intel CPU的SGX(Software Guard Extensions)技術(shù),Intel在超級(jí)賬本的鋸齒湖項(xiàng)目中提出并實(shí)現(xiàn)了PoET共識(shí)算法。在這種機(jī)制下,每個(gè)節(jié)點(diǎn)等待一定的隨機(jī)時(shí)間,該隨機(jī)時(shí)間滿(mǎn)足預(yù)定的概率分布函數(shù)F,最先結(jié)束等待時(shí)間的節(jié)點(diǎn)成為主節(jié)點(diǎn)。

其他節(jié)點(diǎn)進(jìn)行驗(yàn)證,通過(guò)兩種方式驗(yàn)證節(jié)點(diǎn)確實(shí)等待了一定的隨機(jī)時(shí)間。第一,產(chǎn)生區(qū)塊的同時(shí)在SGX的協(xié)助下產(chǎn)生一個(gè)等待時(shí)間的證明 ,隨同區(qū)塊一起廣播給其他節(jié)點(diǎn)進(jìn)行區(qū)塊驗(yàn)證以及等待時(shí)間驗(yàn)證; 第二,應(yīng)用概率統(tǒng)計(jì)測(cè)試來(lái)檢驗(yàn)節(jié)點(diǎn)的等待時(shí)間是否符合預(yù)定的概率分布F。

PoET共識(shí)算法將信任依托于硬件,使得區(qū)塊鏈系統(tǒng)不必耗費(fèi)大量算力,實(shí)現(xiàn)了“一CPU一票”的公平性。每個(gè)節(jié)點(diǎn)成為主節(jié)點(diǎn)的概率相等,但不能排除用戶(hù)通過(guò)增加CPU資源提高出塊概率,從而使中心化程度增強(qiáng)。PoET面臨硬件安全造成的單點(diǎn)故障風(fēng)險(xiǎn),惡意節(jié)點(diǎn)只需攻破一臺(tái)SGX就可以控制出塊權(quán)。

3.4 其他類(lèi)

3.4.1 Ripple

Ripple聯(lián)盟鏈[77]項(xiàng)目中提出并實(shí)現(xiàn)了RPCA共識(shí)算法。RPCA中引入了一個(gè)新的概念: 獨(dú)立節(jié)點(diǎn)列表(Unique Node List,UNL)。這是一份“信任”列表,這里的“信任”指的是節(jié)點(diǎn)相信這個(gè)列表里的節(jié)點(diǎn)不會(huì)聯(lián)合起來(lái)作惡,不需要相信這個(gè)列表里的每一個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)維護(hù)自己的UNL,各個(gè)節(jié)點(diǎn)的UNL相互獨(dú)立,可能相同也可能不同。

共識(shí)過(guò)程如下:

1.共識(shí)開(kāi)始之前,每個(gè)節(jié)點(diǎn)接受所有的交易,放到本地的“交易候選集”;

2.每個(gè)節(jié)點(diǎn)把自己UNL列表中的節(jié)點(diǎn)各自維護(hù)的“交易候選集”合并到自己本地,然后以UNL為單位對(duì)每筆交易進(jìn)行投票;

3.當(dāng)UNL中超過(guò)一定數(shù)量比例的節(jié)點(diǎn)都認(rèn)為某筆交易正確的時(shí)候,這筆交易進(jìn)入第4步; 沒(méi)有達(dá)到要求的交易要么被丟棄,要么繼續(xù)被留在“交易候選集”中等待下一輪共識(shí)過(guò)程開(kāi)始后重新被投票;

4.共識(shí)過(guò)程的最后一步,對(duì)于第 3步中通過(guò)的交易,如果在這一步UNL中超過(guò)80%的節(jié)點(diǎn)都認(rèn)為該筆交易正確,則這筆交易滿(mǎn)足共識(shí)要求。所有滿(mǎn)足這一要求的交易被添加進(jìn)賬本。

RPCA共識(shí)算法能夠容忍不超過(guò) 20%數(shù)量的拜占庭錯(cuò)誤節(jié)點(diǎn)即可保證區(qū)塊鏈系統(tǒng)的可用性; 對(duì)于一致性而言,該共識(shí)算法對(duì)節(jié)點(diǎn)的UNL選擇有如下要求:

圖9 連接性示意圖Figure 9 The diagram of connectivity

3.4.2 分片共識(shí)算法

當(dāng)前區(qū)塊鏈面臨的一大問(wèn)題是交易性能低。競(jìng)爭(zhēng)類(lèi)和隨機(jī)類(lèi)共識(shí)算法中系統(tǒng)性能等價(jià)于單節(jié)點(diǎn)性能,選舉類(lèi)共識(shí)算法由于O(n2)的通信復(fù)雜度會(huì)使得隨著節(jié)點(diǎn)數(shù)量的增加整體的交易性能下降。分片技術(shù)中,全網(wǎng)節(jié)點(diǎn)劃分為不同的分組(委員會(huì)),每個(gè)分組并行處理不同的交易集。其關(guān)鍵技術(shù)在于設(shè)計(jì)合理的分片方式以及解決分片交易的原子性問(wèn)題。Elastico[55]是第一個(gè)基于分片技術(shù)的拜占庭容錯(cuò)公鏈方案,之后出現(xiàn)眾多改進(jìn)方案,比如OmniLedger[56]、RapidChain[78]等。

以Elastico為例說(shuō)明分片技術(shù)方案。Elastico周期性地共識(shí)區(qū)塊,每個(gè)周期內(nèi),節(jié)點(diǎn)執(zhí)行以下操作:

1.身份獲取和委員會(huì)分配: 每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)身份信息,身份信息由公鑰、IP地址和一個(gè)PoW難題解組成,PoW 難題解是為了防止惡意節(jié)點(diǎn)偽造多個(gè)身份信息,之后根據(jù)身份信息將節(jié)點(diǎn)劃分到不同的委員會(huì);

2.委員會(huì)內(nèi)部節(jié)點(diǎn)發(fā)現(xiàn): Elastico通過(guò)建立“目錄服務(wù)委員會(huì)”,節(jié)點(diǎn)可以高效地與同一委員會(huì)內(nèi)部的其他成員建立通信連接;

3.委員會(huì)內(nèi)部共識(shí): 委員會(huì)內(nèi)部運(yùn)行 PBFT共識(shí)算法對(duì)交易集達(dá)成共識(shí),將共識(shí)結(jié)果發(fā)送到“共識(shí)委員會(huì)”;

4.最終共識(shí): “共識(shí)委員會(huì)”接受其他委員會(huì)的共識(shí)結(jié)果并重新打包交易,運(yùn)行PBFT共識(shí)算法達(dá)成最終共識(shí)并向全網(wǎng)廣播;

5.產(chǎn)生隨機(jī)數(shù): “共識(shí)委員會(huì)”產(chǎn)生一組隨機(jī)數(shù),用于下一周期中節(jié)點(diǎn)重新構(gòu)建身份信息。

分片技術(shù)通過(guò)并行處理提升系統(tǒng)性能,使其隨著全網(wǎng)節(jié)點(diǎn)數(shù)量的增多而線(xiàn)性提升; 另外每個(gè)節(jié)點(diǎn)只存儲(chǔ)部分?jǐn)?shù)據(jù),減少了節(jié)點(diǎn)數(shù)據(jù)存儲(chǔ)壓力。Elastico中也存在一些問(wèn)題,比如沒(méi)有解決原子性交換問(wèn)題,當(dāng)分片拒絕某筆跨片交易后,原分片中的交易資產(chǎn)被永遠(yuǎn)鎖定。

3.4.3 基于DAG共識(shí)算法

除了分片技術(shù)外,也可以通過(guò)有向無(wú)環(huán)圖(Directed Acyclic Graph,DAG)的結(jié)構(gòu)提升區(qū)塊鏈系統(tǒng)的交易性能,基于 DAG的加密貨幣項(xiàng)目有Obyte[79](Byteball)、DagCoin[80]、IOTA[81]等。DAG中的每個(gè)單元代表用戶(hù)發(fā)起的一筆交易,每一條從子單元指向父單元的有向邊代表一種驗(yàn)證關(guān)系,即用戶(hù)創(chuàng)建交易的時(shí)候需要對(duì)先前的交易單元進(jìn)行驗(yàn)證,將驗(yàn)證有效的交易單元的哈希值包含到自己的交易數(shù)據(jù)結(jié)構(gòu)中,則當(dāng)前的交易單元稱(chēng)為子交易,被驗(yàn)證的交易稱(chēng)為當(dāng)前交易的父交易,每筆交易可以有多個(gè)父交易,每個(gè)交易也可以有多個(gè)子交易,這樣交易單元構(gòu)成有向無(wú)環(huán)圖的結(jié)構(gòu),如圖10所示。

圖10 基于DAG共識(shí)數(shù)據(jù)存儲(chǔ)圖示Figure 10 The diagram of data unit stored based on DAG

以O(shè)byte為例展示基于DAG模式的交易過(guò)程:

1.創(chuàng)建交易: 當(dāng)用戶(hù)需要發(fā)起交易時(shí),創(chuàng)建一個(gè)交易單元,按照交易單元數(shù)據(jù)結(jié)構(gòu)填充對(duì)應(yīng)的內(nèi)容,包括消息類(lèi)型、簽名、以及一個(gè)或多個(gè)先前交易單元的哈希值;

2.廣播交易: 交易創(chuàng)建完成后,將交易單元向全網(wǎng)廣播;

3.驗(yàn)證交易: 其他節(jié)點(diǎn)接收交易,之后發(fā)起交易時(shí)會(huì)選擇驗(yàn)證當(dāng)前交易是否有效。

Obyte系統(tǒng)中選擇12個(gè)可信的“證人”節(jié)點(diǎn),這些節(jié)點(diǎn)發(fā)起的交易按照先后順序連接成為一條主鏈,如圖10中按順序編號(hào)的鏈為主鏈,出現(xiàn)雙花交易時(shí),根據(jù)交易單元與主鏈中交易單元的關(guān)系選擇有效交易[80]。

從以上的過(guò)程中,可以看出 DAG模式中,沒(méi)有礦工和區(qū)塊,節(jié)省了交易費(fèi)以及產(chǎn)生主節(jié)點(diǎn)打包區(qū)塊的時(shí)間,交易得到及時(shí)確認(rèn)。這種異步并發(fā)處理交易的模式使得DAG具有高可擴(kuò)展性,但高并發(fā)情形下可能短時(shí)間內(nèi)出現(xiàn)數(shù)據(jù)不一致的問(wèn)題,不適合強(qiáng)一致性的場(chǎng)景。

本節(jié)建立了共識(shí)算法的分類(lèi)模型,將共識(shí)算法分為四類(lèi): 競(jìng)爭(zhēng)類(lèi)、選舉類(lèi)、隨機(jī)類(lèi)和其他類(lèi)型; 每種類(lèi)型中描述典型的算法共識(shí)過(guò)程,幫助更好地理解各共識(shí)算法及分類(lèi)模型。在此基礎(chǔ)上,第四節(jié)從六個(gè)維度建立共識(shí)算法的評(píng)價(jià)指標(biāo),并對(duì)各類(lèi)型算法進(jìn)行對(duì)比分析,給出各類(lèi)算法在不同性能上的表現(xiàn)。

4 評(píng)價(jià)體系

以太坊項(xiàng)目中,Vitalik Buterin提出區(qū)塊鏈DSS猜想[61]: 區(qū)塊鏈系統(tǒng)中不能從去中心化(Decentralization)、安全性(Security)和可擴(kuò)展性(Scalability)三個(gè)方面同時(shí)做到提升。區(qū)塊鏈的去中心化是指網(wǎng)絡(luò)的控制權(quán)分散到整個(gè)網(wǎng)絡(luò),而不是被少數(shù)用戶(hù)集中控制。既要保證用戶(hù)公平地參與網(wǎng)絡(luò),即使得參與用戶(hù)的收益比例與資源投入比例盡可能相近[82],同時(shí)防止網(wǎng)絡(luò)的控制權(quán)被少數(shù)用戶(hù)控制,網(wǎng)絡(luò)的控制權(quán)越分散,即各用戶(hù)創(chuàng)建區(qū)塊的權(quán)利越平均,網(wǎng)絡(luò)的去中心化程度越高。區(qū)塊鏈系統(tǒng)中面臨的安全性問(wèn)題主要有密碼學(xué)安全性、網(wǎng)絡(luò)安全性、數(shù)據(jù)安全性、共識(shí)算法安全性等,比如比特幣系統(tǒng)的51%算力攻擊,即惡意節(jié)點(diǎn)的算力超過(guò)全網(wǎng)一半的算力時(shí),這些惡意節(jié)點(diǎn)就可以聯(lián)合起來(lái)對(duì)比特幣系統(tǒng)強(qiáng)行分叉,通過(guò)刪除或修改交易信息構(gòu)造新區(qū)塊取代原來(lái)的正常交易數(shù)據(jù),實(shí)現(xiàn)雙重支付等,破壞比特幣系統(tǒng)的安全性。區(qū)塊鏈的可擴(kuò)展性指區(qū)塊鏈系統(tǒng)處理高業(yè)務(wù)量的能力。區(qū)塊鏈可擴(kuò)展性主要面臨以下三點(diǎn)挑戰(zhàn)[83]: (1)分布式系統(tǒng)的網(wǎng)絡(luò)延遲,區(qū)塊鏈系統(tǒng)節(jié)點(diǎn)間網(wǎng)絡(luò)距離以及網(wǎng)絡(luò)環(huán)境無(wú)法控制,所以在網(wǎng)絡(luò)延遲上比傳統(tǒng)的分布式系統(tǒng)受到更大的限制。(2)區(qū)塊鏈的一致性,區(qū)塊鏈要維護(hù)節(jié)點(diǎn)間的一致性需要大量節(jié)點(diǎn)的確認(rèn)。一般來(lái)說(shuō),越是強(qiáng)的一致性確認(rèn)計(jì)算開(kāi)銷(xiāo)也會(huì)越大,同時(shí)系統(tǒng)規(guī)模越大達(dá)成一致的成本也越高。(3)節(jié)點(diǎn)性能限制,比如PoW這類(lèi)共識(shí)算法本身就會(huì)消耗大量的計(jì)算資源,在效率上存在一定限制。同時(shí)隨著區(qū)塊鏈數(shù)據(jù)量的不斷累加,要想達(dá)到較高的交易率,極大的數(shù)據(jù)量對(duì)于節(jié)點(diǎn)的吞吐量有很高的需求。

在比特幣和以太坊中,出于去中心化和安全性的考慮,系統(tǒng)中每筆交易都需要全網(wǎng)節(jié)點(diǎn)廣播,全網(wǎng)節(jié)點(diǎn)驗(yàn)證,并且每個(gè)新區(qū)塊的創(chuàng)建都需要全網(wǎng)節(jié)點(diǎn)共同競(jìng)爭(zhēng),提升去中心化程度和安全性; 共識(shí)過(guò)程需要全網(wǎng)節(jié)點(diǎn)的參與,使得共識(shí)過(guò)程中網(wǎng)絡(luò)通信復(fù)雜度增高,系統(tǒng)處理性能低效,限制了系統(tǒng)的可擴(kuò)展性。EOS項(xiàng)目中采用的DPoS共識(shí)算法,采用21個(gè)超級(jí)節(jié)點(diǎn)參與共識(shí)過(guò)程,這些被認(rèn)為可信的超級(jí)節(jié)點(diǎn)按照順序創(chuàng)建區(qū)塊,提升了區(qū)塊鏈系統(tǒng)的性能,可擴(kuò)展性得到提升,但是降低了區(qū)塊鏈去中心化程度。

DSS猜想僅是Vitalik Buterin用來(lái)解構(gòu)區(qū)塊鏈性能問(wèn)題的方式,理論上并不嚴(yán)謹(jǐn)和完整,但依然給區(qū)塊鏈共識(shí)算法的研究者們提供了一個(gè)性能研究的切入點(diǎn)。

本節(jié)將從去中心化、可擴(kuò)展性、安全性、一致性、可用性、分區(qū)容忍性六個(gè)方面建立共識(shí)算法的評(píng)價(jià)指標(biāo)體系。去中心化要求所有的節(jié)點(diǎn)具有相等的地位,在共識(shí)算法中即要求所有節(jié)點(diǎn)能夠參與共識(shí)過(guò)程且每個(gè)用戶(hù)出塊的權(quán)利越平均,網(wǎng)絡(luò)的控制權(quán)越分散,去中心化程度越高。進(jìn)一步將去中心化細(xì)化為共識(shí)節(jié)點(diǎn)數(shù)量、主節(jié)點(diǎn)選擇方式、共識(shí)節(jié)點(diǎn)權(quán)重三個(gè)指標(biāo),綜合這三個(gè)指標(biāo)建立去中心化程度指標(biāo)。共識(shí)節(jié)點(diǎn)數(shù)量描述的是全網(wǎng)節(jié)點(diǎn)都參與共識(shí)過(guò)程還是部分節(jié)點(diǎn)參與共識(shí)過(guò)程; 主節(jié)點(diǎn)的選擇方式描述主節(jié)點(diǎn)是通過(guò)競(jìng)爭(zhēng)、選舉或隨機(jī)的方式產(chǎn)生; 共識(shí)節(jié)點(diǎn)權(quán)重描述在每輪共識(shí)過(guò)程中,共識(shí)節(jié)點(diǎn)成為主節(jié)點(diǎn)的概率是否相等?？蓴U(kuò)展性方面,系統(tǒng)處理高業(yè)務(wù)量的能力越強(qiáng),可擴(kuò)展性越強(qiáng)。處理高業(yè)務(wù)量的能力主要受到單個(gè)節(jié)點(diǎn)的性能和網(wǎng)絡(luò)通信成本等因素的影響。進(jìn)一步將可擴(kuò)展性分為資源消耗、通信復(fù)雜度兩個(gè)指標(biāo),綜合這兩個(gè)指標(biāo)對(duì)可擴(kuò)展性程度進(jìn)行評(píng)價(jià)。資源消耗是指共識(shí)過(guò)程對(duì)計(jì)算、存儲(chǔ)、網(wǎng)絡(luò)等資源的消耗程度,資源消耗限制單個(gè)節(jié)點(diǎn)的性能; 通信復(fù)雜度是指共識(shí)算法的網(wǎng)絡(luò)通信復(fù)雜度,旨在刻畫(huà)網(wǎng)絡(luò)通信成本(N代表共識(shí)節(jié)點(diǎn)數(shù)量)。共識(shí)算法的安全性主要受到容錯(cuò)能力、對(duì)惡意節(jié)點(diǎn)的處理能力、潛在的攻擊方式種類(lèi)及數(shù)量、攻擊難易程度、以及遭受安全攻擊后的恢復(fù)能力等因素的影響。進(jìn)一步將安全性細(xì)化為容錯(cuò)度、節(jié)點(diǎn)可控性、攻擊多樣性、攻擊成本、安全恢復(fù)性,綜合這五個(gè)指標(biāo)評(píng)估共識(shí)算法安全性。容錯(cuò)度是指共識(shí)算法保證區(qū)塊鏈系統(tǒng)達(dá)成共識(shí)所能接受的拜占庭惡意節(jié)點(diǎn)(或算力等)在全網(wǎng)中的最大占比; 節(jié)點(diǎn)可控性是指共識(shí)算法是否具有排除惡意節(jié)點(diǎn)參與共識(shí)過(guò)程的能力; 攻擊多樣性是指共識(shí)算法可能面臨的攻擊方式的種類(lèi)及數(shù)量,種類(lèi)及數(shù)量越多,則潛在的安全風(fēng)險(xiǎn)越高,目前區(qū)塊鏈共識(shí)算法可能面臨的安全攻擊主要包括:針對(duì)安全性假設(shè)的攻擊、影響可擴(kuò)展性的攻擊和針對(duì)激勵(lì)機(jī)制的攻擊等; 攻擊成本是指惡意節(jié)點(diǎn)發(fā)動(dòng)安全攻擊所消耗的代價(jià),代價(jià)越高,發(fā)動(dòng)攻擊的難度越大; 安全恢復(fù)性是指區(qū)塊鏈?zhǔn)艿桨踩艉?使數(shù)據(jù)恢復(fù)到攻擊發(fā)生之前安全狀態(tài)的能力,進(jìn)行硬分叉的可能性越高,安全恢復(fù)性越強(qiáng)。去中心化程度、可擴(kuò)展性和安全性是從DSS猜想的三個(gè)特性評(píng)價(jià)共識(shí)算法,接下來(lái)從“CAP定理”的一致性、可用性和分區(qū)容忍性三個(gè)特性評(píng)價(jià)共識(shí)算法。進(jìn)一步將一致性層面分為分叉可能性、最終一致性。分叉可能性是指區(qū)塊鏈產(chǎn)生分叉的概率大小; 最終一致性是指各節(jié)點(diǎn)的數(shù)據(jù)是否在有限時(shí)間內(nèi)達(dá)成一致,綜合這兩個(gè)角度刻畫(huà)共識(shí)算法的一致性程度?？捎眯灾笜?biāo)描述系統(tǒng)是否一直處于服務(wù)狀態(tài); 分區(qū)容忍性指系統(tǒng)是否允許部分節(jié)點(diǎn)不與其他節(jié)點(diǎn)通信。

以下基于評(píng)價(jià)指標(biāo)體系,從6個(gè)方面對(duì)各類(lèi)算法進(jìn)行對(duì)比分析,如圖11所示。去中心化程度方面,競(jìng)爭(zhēng)類(lèi)全網(wǎng)節(jié)點(diǎn)全部參與共識(shí)過(guò)程,但是每個(gè)節(jié)點(diǎn)成為主節(jié)點(diǎn)的概率不等,與節(jié)點(diǎn)擁有的競(jìng)爭(zhēng)資源有關(guān),這就造成在實(shí)際區(qū)塊鏈系統(tǒng)中部分擁有大量競(jìng)爭(zhēng)資源的節(jié)點(diǎn)壟斷了主節(jié)點(diǎn)。選舉類(lèi)算法各節(jié)點(diǎn)投票選擇主節(jié)點(diǎn),之后僅由選定的節(jié)點(diǎn)創(chuàng)建區(qū)塊,比如EOS中選出21個(gè)超級(jí)節(jié)點(diǎn)輪流負(fù)責(zé)創(chuàng)建區(qū)塊,這在一定程度上降低了去中心化程度。Ripple算法每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)信任節(jié)點(diǎn)列表,各節(jié)點(diǎn)地位相等,去中心化程度高?？蓴U(kuò)展性方面,競(jìng)爭(zhēng)類(lèi)共識(shí)算法屬于資源消耗型,單個(gè)節(jié)點(diǎn)的性能受到很大限制,因此性能效率偏低,處理大規(guī)模業(yè)務(wù)量能力差,可擴(kuò)展性程度低; 選舉類(lèi)共識(shí)算法雖然共識(shí)過(guò)程不需要消耗大量資源,單個(gè)節(jié)點(diǎn)性能得到提升,但是通信復(fù)雜度高,且隨著網(wǎng)絡(luò)規(guī)模增加,通信成本會(huì)限制可擴(kuò)展性的提升,但相比競(jìng)爭(zhēng)類(lèi)共識(shí)算法,可擴(kuò)展性得到提升; 隨機(jī)類(lèi)共識(shí)算法共識(shí)過(guò)程即不需要消耗大量資源,網(wǎng)絡(luò)通信復(fù)雜度也沒(méi)有選舉類(lèi)算法高,可擴(kuò)展性比選舉類(lèi)更好; Ripple算法通過(guò)將全網(wǎng)節(jié)點(diǎn)分為多個(gè)共識(shí)組提高了可擴(kuò)展性。安全性方面,競(jìng)爭(zhēng)類(lèi)共識(shí)算法容錯(cuò)度高于部分其他類(lèi)算法,選舉類(lèi)算法對(duì)節(jié)點(diǎn)的可控性強(qiáng),發(fā)現(xiàn)惡意節(jié)點(diǎn)之后可以在下一輪主節(jié)點(diǎn)的選舉過(guò)程中將其排除,競(jìng)爭(zhēng)類(lèi)算法面臨的攻擊多樣性高,以 PoW 為例,安全性假設(shè)層面存在51%攻擊、日蝕攻擊[84]等,可擴(kuò)展性層面存在粉塵攻擊、空塊攻擊等; 激勵(lì)層面存在自私挖礦攻擊[69]、扣塊攻擊[85]等,三個(gè)層面均面臨潛在的安全攻擊,攻擊多樣性相對(duì)較高。選舉類(lèi)和隨機(jī)類(lèi)算法也存在一定的安全攻擊,但針對(duì)這兩類(lèi)算法的安全攻擊方式相對(duì)較少,相比于以PoW為代表的競(jìng)爭(zhēng)類(lèi)算法,其攻擊多樣性相對(duì)較低。從攻擊成本角度,相比選舉類(lèi)和隨機(jī)類(lèi),競(jìng)爭(zhēng)類(lèi)算法中由惡意節(jié)點(diǎn)發(fā)動(dòng)較強(qiáng)破壞性安全攻擊的成本較高,比如 PoS中發(fā)動(dòng)51%攻擊,需要控制超過(guò)全網(wǎng)一半的權(quán)益,發(fā)動(dòng)安全攻擊的難度較大。從安全恢復(fù)性角度,選舉類(lèi)算法由選擇的少數(shù)節(jié)點(diǎn)維護(hù)共識(shí),通過(guò)硬分叉進(jìn)行安全恢復(fù)的能力強(qiáng)于競(jìng)爭(zhēng)類(lèi)和隨機(jī)類(lèi)算法。實(shí)際中,采用PoW算法的比特幣已經(jīng)發(fā)生過(guò)數(shù)次大規(guī)模的硬分叉,說(shuō)明競(jìng)爭(zhēng)類(lèi)算法也具有一定的安全恢復(fù)能力。一致性方面,競(jìng)爭(zhēng)類(lèi)算法由于網(wǎng)絡(luò)延時(shí)的存在,可能出現(xiàn)在短時(shí)間間隔內(nèi)出現(xiàn)多個(gè)達(dá)到競(jìng)爭(zhēng)標(biāo)準(zhǔn)的節(jié)點(diǎn),因此有分叉的可能性,不具有最終一致性; 對(duì)于選舉類(lèi)和隨機(jī)類(lèi),算法在同一時(shí)間只產(chǎn)生一個(gè)主節(jié)點(diǎn),因此沒(méi)有分叉的可能性,具有最終一致性; Ripple算法在滿(mǎn)足連接性要求的情況下,也不會(huì)產(chǎn)生分叉。一致性方面,與競(jìng)爭(zhēng)類(lèi)共識(shí)算法相比,選舉類(lèi)、隨機(jī)類(lèi)和 Ripple算法具有強(qiáng)一致性。對(duì)于可用性和分區(qū)容忍性?xún)蓚€(gè)角度,四大類(lèi)共識(shí)算法均具有高可用性,不支持分區(qū)容忍性,滿(mǎn)足“CAP定理”。綜上所述,可以看出四大類(lèi)算法在一致性、可用性和分區(qū)容忍性層面都致力于滿(mǎn)足一致性和可用性,犧牲了分區(qū)容忍性,滿(mǎn)足“CAP定理”; 與“CAP定理”只能滿(mǎn)足其中兩個(gè)特性不同,“DSS猜想”是指去中心化程度、可擴(kuò)展性、安全性三個(gè)層面的性能無(wú)法同時(shí)得到提升。競(jìng)爭(zhēng)類(lèi)算法具有更高的安全性,在安全性不如競(jìng)爭(zhēng)類(lèi)的情況下,隨機(jī)類(lèi)和 Ripple算法提升了去中心化程度和可擴(kuò)展性。因此,網(wǎng)絡(luò)環(huán)境更為復(fù)雜的公鏈中多采用競(jìng)爭(zhēng)類(lèi)算法,比如規(guī)模最大的公鏈比特幣采用PoW,以太坊擬采用PoS; 而聯(lián)盟鏈則多采用選舉類(lèi)、隨機(jī)類(lèi)和其他類(lèi)的共識(shí)算法,比如Hyperledger Fabric中采用PBFT算法,Hyperledger Sawtooth中采用的PoET算法,Ripple聯(lián)盟鏈中采用的Ripple共識(shí)算法。

圖11 共識(shí)算法評(píng)價(jià)指標(biāo)Figure 11 The evaluating indicators of consensus algorithms

本節(jié)從去中心化、可擴(kuò)展性、安全性、一致性、可用性、分區(qū)容忍性六個(gè)方面建立了共識(shí)算法的評(píng)價(jià)體系并完成了初步的定性分析。Garay等[86]提出比特幣骨干協(xié)議,并對(duì)比特幣的一致性(Persistence)和可用性(Liveness,也稱(chēng)活性)進(jìn)行定量分析。該協(xié)議中提出公共前綴和鏈質(zhì)量?jī)煞N特性,并得出一定算力約束條件下這兩個(gè)特性的概率大小,進(jìn)而量化比特幣的一致性和可用性,分析得出在網(wǎng)絡(luò)同步速率大于出塊速率且惡意節(jié)點(diǎn)的算力嚴(yán)格小于全網(wǎng)算力50%的條件下,比特幣具有高一致性和可用性。比特幣骨干協(xié)議分析、抽象比特幣協(xié)議,提取關(guān)鍵元素、提出并證明新特性,并通過(guò)重新實(shí)現(xiàn)比特幣,借助新特性來(lái)證明比特幣的相關(guān)特性,這種分析方法為后續(xù)對(duì)共識(shí)算法評(píng)價(jià)指標(biāo)體系設(shè)計(jì)對(duì)應(yīng)的定量分析方法提供了有效參考。

5 總結(jié)與展望

共識(shí)算法是區(qū)塊鏈系統(tǒng)的核心機(jī)制之一,獲得了研究人員和產(chǎn)業(yè)界的廣泛關(guān)注。近年來(lái)區(qū)塊鏈項(xiàng)目中涌現(xiàn)出各種共識(shí)算法,但缺乏完整技術(shù)分類(lèi)和統(tǒng)一評(píng)價(jià)體系。本文深入分析區(qū)塊鏈共識(shí)算法,從共識(shí)過(guò)程本身出發(fā),提出了共識(shí)算法的分類(lèi)模型,按照主節(jié)點(diǎn)的產(chǎn)生方式將共識(shí)算法分為競(jìng)爭(zhēng)類(lèi)、選舉類(lèi)、隨機(jī)類(lèi)及其他類(lèi)型,并剖析了每種類(lèi)型中代表性共識(shí)算法的共識(shí)過(guò)程及其優(yōu)劣勢(shì); 同時(shí)從去中心化、可擴(kuò)展性、安全性、一致性、可用性、分區(qū)容忍性六個(gè)方面建立了一套共識(shí)算法的評(píng)價(jià)指標(biāo)體系,在此基礎(chǔ)上,對(duì)各類(lèi)共識(shí)算法進(jìn)行初步的對(duì)比分析。

后續(xù)的研究重點(diǎn)將在此評(píng)價(jià)指標(biāo)體系和評(píng)價(jià)分析的基礎(chǔ)上,結(jié)合區(qū)塊鏈的應(yīng)用場(chǎng)景,借鑒比特幣骨干協(xié)議等的分析方法,針對(duì)共識(shí)算法設(shè)計(jì)對(duì)應(yīng)的評(píng)測(cè)方法,進(jìn)一步開(kāi)展科學(xué)化分析,給出區(qū)塊鏈共識(shí)算法在應(yīng)用場(chǎng)景中的定量評(píng)價(jià),為不同的應(yīng)用場(chǎng)景選擇合適的共識(shí)算法提供參考。