易 黎，盧新宇，湯 鯤，王 恒，龔子怡

（1.武漢郵電科學研究院，湖北武漢 430074；2.南京烽火星空通信發(fā)展有限公司，江蘇 南京 210019）

進入21 世紀后，人類已邁入了數(shù)字時代，特別是關乎國家、政府、企業(yè)和個人的信息安全和數(shù)據(jù)信任問題，已被提上日程。盡管目前采用的中心化管理數(shù)據(jù)方式已經(jīng)趨于成熟并取得一定成果，但仍存在管理成本高、安全性能差、數(shù)據(jù)不透明等缺點。而區(qū)塊鏈技術具有去中心化、公開透明、公眾參與度高和可以追溯等優(yōu)勢，得到了國家政府、學術界和產(chǎn)業(yè)界的高度重視。如中國國家科技部在2022 年科研規(guī)劃中專門安排了1.78 億元用于區(qū)塊鏈研究，對區(qū)塊鏈基礎理論、體系構建、安全管理、實驗平臺和重點示范應用等急需攻克的關鍵領域給予了資助。

2008 年10 月31 日，中本聰在線發(fā)表了《Bitcoin:A Peer-to-Peer Electronic Cash System》[1]的論文，構思設計了一種點對點直接交易不需要第三方背書的數(shù)字貨幣，其核心內(nèi)容是引入了工作證明（Proof of Work,PoW）機制。2009 年1 月3 日，其設計的比特幣系統(tǒng)正式上線，中本聰挖掘了第一枚創(chuàng)世區(qū)塊，獲得50BTC 的獎勵，這標志著不需要政府或銀行背書的點對點支付數(shù)字貨幣系統(tǒng)正式誕生[2]。在隨后的數(shù)十年間，以比特幣、以太坊和超級聯(lián)盟鏈為代表的區(qū)塊鏈技術取得了長足的發(fā)展。2015 年，支持圖靈完備的智能合約及開源可編程的智能合約平臺大幅度地擴展了區(qū)塊鏈的應用場景[3]，其已廣泛應用于貨幣金融、通信網(wǎng)絡、信息安全、物聯(lián)網(wǎng)和社會職能管理等多個領域[4-5]。

區(qū)塊鏈目前存在的主要問題是通信延遲、吞吐量與實際應用場景要求相差甚遠。如證券公司要求每秒鐘處理的交易達到幾十萬甚至百萬，而超級聯(lián)盟鏈Hyperledger Fabric 每秒鐘的吞吐量也只有幾千筆；公有鏈的處理量每秒鐘僅有數(shù)筆到幾十筆，如比特幣每秒能最多處理七筆交易量，以太坊處理的上限是40 筆交易[6]。而要想改善并解決區(qū)塊鏈吞吐量小、通信延遲、分叉等問題，最終均要回歸到共識算法上。因此，有必要系統(tǒng)性地對區(qū)塊鏈共識算法進行歸納總結。

1 區(qū)塊鏈組成、分類、架構及上鏈流程

區(qū)塊鏈是融合了共識、加密、數(shù)計簽名、哈希函數(shù)、經(jīng)濟學獎勵機制等內(nèi)容，以將數(shù)據(jù)區(qū)塊寫入鏈式賬本，實現(xiàn)去中心化為目的的創(chuàng)新性技術。區(qū)塊由塊頭和塊體組成，通過哈希指針銜接形成的一種鏈式數(shù)據(jù)結構，由于哈希函數(shù)具有唯一性、不可逆等特性，所以區(qū)塊鏈體現(xiàn)了不可追加、不可篡改、不可刪除和各節(jié)點數(shù)據(jù)備存一致性等特點[7]。區(qū)塊中的具體內(nèi)容如圖1 所示。由圖1 可知，區(qū)塊頭由版本號、前區(qū)塊哈希值、時間戳、默克爾根、隨機數(shù)和目標Hash 等組成，區(qū)塊體由二叉默克爾樹組成。由于新上鏈的區(qū)塊在區(qū)塊頭中保留了上一區(qū)塊的特征，如果想改變交易記錄，必須更改其后所有區(qū)塊頭部值，這也是區(qū)塊鏈不可篡改的另一個原因[8]。

圖1 區(qū)塊鏈的單個區(qū)塊結構

按照節(jié)點參與并達成共識的機制和鏈的開放程度可將區(qū)塊鏈分為公有鏈（Public Blockchain）、聯(lián)盟鏈（Consortium Blockchain）和私有鏈（Private Blockchain）三種[9]。公有鏈是指所有節(jié)點都參與共識過程，都有可能通過驗證將數(shù)據(jù)上傳到區(qū)塊鏈上，交易信息公開透明，其本質是一個分布式賬本，采用工作量證明算法達成共識，完成去中心化。比特幣、以太坊等數(shù)字貨幣是其典型代表；聯(lián)盟鏈是由有交集的行業(yè)或部門組成，它們之間并不信任或信任程度較低，其特點介于公有鏈和私有鏈之間，具有準入資格的信任節(jié)點才具有投票、共識和驗證權限，其采用拜占庭容錯機制達成共識，與公有鏈相比可顯著降低能源消耗，具有弱中心化的特點，如超級聯(lián)盟鏈Hyperledger Fabric 等；私有鏈是指大型集團公司自建的區(qū)塊鏈系統(tǒng)。節(jié)點需要授權才能參與投票、記賬，只有注冊、驗證后，才能查看相關數(shù)據(jù)，主要用于集團內(nèi)部的財務、稅收、物流、供應和銷售等，其本質是一個中心化的賬本，但與傳統(tǒng)的中心化賬本不同，具有區(qū)塊鏈的可追溯、不可篡改等特性，如國外的IBM 公司，國內(nèi)的阿里、百度等公司均采用私有鏈。區(qū)塊鏈不同類型的特征如表1 所示。

表1 不同類型區(qū)塊鏈特征對比

由表1 可知，公有鏈采用證明類共識，完全去中心化；聯(lián)盟鏈主要采用拜占庭容錯算法，部分去中心化；私有鏈采用非拜占庭容錯算法，完全中心化。

區(qū)塊鏈的架構主要包括數(shù)據(jù)層、網(wǎng)絡層、共識層、激勵層、合約層和應用層。數(shù)據(jù)層、網(wǎng)絡層為底層，激勵層、合約層和應用層為頂層，共識層為中間核心層[10]，區(qū)塊鏈分層架構結構如表2 所示。由表2可知，底層主要分裝存儲數(shù)據(jù)，構成區(qū)塊鏈的根基，點對點分布式完成數(shù)據(jù)的傳輸和驗證；中層完成數(shù)據(jù)的一致性，通過激勵機制鼓勵誠實節(jié)點參與區(qū)塊鏈的記賬和交易工作、同時懲罰惡意節(jié)點；頂層通過腳本代碼、智能合約等合約層技術推廣到應用。

表2 區(qū)塊鏈分層架構結構表

區(qū)塊鏈共識算法交易流程一般采用“執(zhí)行—排序—驗證—上鏈”四步驟法，如圖2 所示。通過提案的提交、執(zhí)行、節(jié)點排序、廣播共識、驗證、上鏈等步驟完成。其可廣泛應用于政務、金融、溯源、存證、版權保護、司法和物聯(lián)網(wǎng)等應用場景。

圖2 區(qū)塊鏈制作流程圖

2 共識算法原理簡介

共識問題是分布式網(wǎng)絡技術的核心問題之一，也是區(qū)塊鏈的靈魂。區(qū)塊鏈中每個節(jié)點都具有決策權，即整體決策權被分散，各節(jié)點通過共識算法達成共識，維護了鏈塊數(shù)據(jù)的一致性：使不同節(jié)點之間達成信任；規(guī)定并計算各節(jié)點的權益；解決了誰來創(chuàng)建上傳區(qū)塊的問題。

1980 年Leslie Lamport 就傳統(tǒng)分布式領域共識相關的問題進行了探索研究，在分布式數(shù)據(jù)的某個節(jié)點，如果不存在故障或錯誤，僅考慮網(wǎng)絡延時，導致系統(tǒng)無響應的情況下，只要使用Paxos、Raft 等支持CFT（Crash Fault Tolerance）的算法即可，通過特定值的對比達成共識[11]。

分布式共識算法的設計原則遵循FLP 不可能原理和CAP 定理。FLP 不可能原理是1985 年Fischer等[12]提出的，在異步網(wǎng)絡通信場景中，分布式系統(tǒng)中只要有一個進程發(fā)生故障，任何共識算法都不能保證其完全的準確性。但如果系統(tǒng)在運行過程中沒有進程終止，只要有半數(shù)以上的進程正常，那么存在一個部分正確的共識算法能夠保證所有的正常進程可以達成一致。CAP 定理是2000 年Brewer 對一致性（系統(tǒng)中的任何操作都應該是原子或串行的，所有操作都是按照全局排序）、可用性（任何正常節(jié)點收到請求命令后，都應該在規(guī)定的時間給出回復）、容忍性（當網(wǎng)絡在某一時刻發(fā)生分區(qū)時，系統(tǒng)仍然能夠滿足一致性和可用性）三者無法在分布式系統(tǒng)同時被滿足，最多只能滿足其中兩個。目前，所有共識算法的設計都遵從這兩個定理。基于上述原理，區(qū)塊鏈分布式系統(tǒng)共識算法主要解決：1）存在作惡節(jié)點；2）通信發(fā)生故障；3）節(jié)點發(fā)生故障三方面的問題。

廣義的共識算法面對分布式計算機節(jié)點，解決節(jié)點存在惡意、崩潰、宕機等行為。而區(qū)塊鏈中的共識算法，不僅要解決上述問題，確保不同節(jié)點之間產(chǎn)生的區(qū)塊鏈副本都相同，還要避免出現(xiàn)分叉或者重復交易等問題，從而保證區(qū)塊鏈的安全性和正確性。

3 拜占庭容錯節(jié)點共識算法

3.1 PoW共識算法

美國微軟歌德爾獎得主算法科學家Dwork C 等人在1993 年首次提出工作量證明的思路，用于解決垃圾郵件的處理問題，要求郵件發(fā)送者通過計算一定難度的數(shù)學難題獲得郵件發(fā)送的資格，目的是增加郵件發(fā)送者的發(fā)送成本，減少不必要的垃圾郵件的發(fā)送[13]。1999 年，文獻[14]正式提出工作量證明的定義。著名的比特幣就采用PoW 算法，目前已成為主流共識算法之一。其原理是利用哈希函數(shù)的單向性，即（F（N））有N→F（N），但幾乎不可能由F（N）反推出N。將其應用到區(qū)塊鏈中便是給全網(wǎng)所有節(jié)點發(fā)布一個目標難度值（D），尋找滿足Hash(Block Date，Nonce)＜＜D 的隨機數(shù)（Nonce）。由此，用戶可以通過窮舉試驗，得到隨機數(shù)答案，從而達成工作量證明，如SHA256 函數(shù)可以通過窮舉演算得到答案。相反地，其驗算非常簡單，驗算一次就可完成。

中本聰將PoW 共識算法引入到比特幣的設計中，所有節(jié)點通過算力競爭獲得記賬權。第一個計算出滿足規(guī)則隨機數(shù)的節(jié)點，將向全網(wǎng)廣播，全網(wǎng)其他節(jié)點驗證確認后并儲存，該節(jié)點獲得創(chuàng)建區(qū)塊的權利和出塊獎勵，比特幣從交易到上鏈過程如圖3所示。其主要步驟為：1）收集比特幣網(wǎng)絡中的交易，并制作成交易單；2）每個節(jié)點嘗試，計算隨機數(shù)，爭奪創(chuàng)建新區(qū)塊的權利（記賬權），最終出塊人在這一過程中產(chǎn)生；3）第一個算出符合要求的隨機數(shù)的節(jié)點，立刻產(chǎn)生時間戳，并將區(qū)塊發(fā)布到全網(wǎng)節(jié)點驗證；4）當半數(shù)以上節(jié)點驗證通過，共識達成區(qū)塊上鏈。PoW 共識算法通過引入獎勵機制，成功解決了節(jié)點共識一致性的問題。

圖3 PoW共識流程圖

PoW 共識算法具有以下特點：①算法邏輯簡單、易于實現(xiàn)；②節(jié)點之間點對點直接交換信息達成共識；③節(jié)點之間進出自由；④攻擊破壞難度大；⑤完全去中心，缺點是吞吐量太小和能耗太高。以比特幣為例，PoW 共識協(xié)議中規(guī)定一個區(qū)塊的大小為1 MB，10 min 產(chǎn)生一個區(qū)塊，其吞吐量為7 TPS，太小的容量不能滿足比特幣發(fā)展的需要，擴容迫在眉睫。為此，最直接的方法是增加單個區(qū)塊的大小，然而區(qū)塊容量過大，必然會增加信息傳輸?shù)臅r間延遲；如果增加區(qū)塊的生成速度，會出現(xiàn)更多的分叉，導致區(qū)塊鏈的安全性、穩(wěn)定性降低，并且算力競爭會造成電力和各種資源的浪費，尋找到隨機哈希值，也并沒有任何實際價值。為此，研究者們采用不同的策略方法對PoW 共識算法的擴容問題進行了創(chuàng)新性的研究。文獻[15]采用異步共識將整個網(wǎng)絡分成不同的片區(qū)，即分片。每個獨立的片區(qū)獨自達成共識，礦工可以平行維護，挖掘多區(qū)域的區(qū)塊，從而達到擴容的效果。但分片存在單個片區(qū)容易被51%算力攻擊的問題。文獻[16]提出了一種Bitcoin-NG 的擴容方案，Bitcoin-NG 共識算法相對于PoW 共識算法吞吐量增加30～60 倍，出塊時間在10～100 s，且其與比特幣類似，也是基于最長鏈原則。文獻[17]提出的貪婪子樹協(xié)議（GHOST，Greedy Heaviest-Observed Sub-Tree protocol）用于解決以太坊中大礦池PoW 算力過度壟斷，小礦池幾乎拿不到出塊獎勵、區(qū)塊鏈分叉后能夠快速合并的一種PoW 矯正協(xié)議。如圖4 所示主鏈的選擇考慮了分叉支鏈，完全沒有用的孤塊被拋棄，礦工將不會獲得任何獎勵收益，而被后續(xù)子塊打包吸納的塊將按一定的算法給予獎勵。GHOST 通過對PoW 算法的改進，解決了鏈分叉中算力浪費和主鏈難以確定的問題，提高了獨立礦工和小礦池挖礦的積極性，減少了時延和算力浪費。

圖4 GHOST主鏈選擇改進PoW算法

博弈對PoW 共識算法中節(jié)點共識的達成具有重要的影響，文獻[18]從PoW 共識算法挖礦困境入手，采用納什均衡理論，利用零行列式（Zero determinant）策略對PoW 算法中礦工挖礦策略進行優(yōu)化，實驗結果顯示，優(yōu)化后的PoW 算法可以使系統(tǒng)的收益達到最大化。文獻[19]針對PoW 算法分叉問題，構建了一種哈希最小證明算法（Proof of Minimum，PoM），其核心是利用抗碰撞性降低分叉，強混淆性提高去中心化程度，仿真實驗設計了211個礦工，進行了104次PoM 共識，結果顯示沒有出現(xiàn)分叉，只出現(xiàn)了三次空塊，去中心化也得到了大幅度的提升。

綜上，對PoW 共識算法的改進研究較少，主要因為PoW 的設計初衷是通過大量算力、能源和資源的消耗來增加惡意節(jié)點參與共識的成本。當前PoW 改進的重點在增加其性能、效率和改善安全性上，資源消耗的本質問題無法有效根除。

3.2 權益證明（Proof of Stake,PoS）共識算法

PoS 本質上是采用權益證明代替PoW 算力證明，具有最大權益的節(jié)點獲得記賬權。權益的量化由幣齡（Coin Age）多少決定，幣齡等于貨幣數(shù)量與貨幣持有時間的乘積，幣齡多的節(jié)點挖礦難度小，成為出塊節(jié)點概率大，獲益及獎勵多。同時，為了自身的利益，權益多的節(jié)點會主動維護區(qū)塊鏈的安全，讓偽區(qū)塊無法上鏈，并對偽區(qū)塊出塊者采取懲戒措施。PoS 共識算法如圖5 所示。

圖5 PoS共識流程圖

PoS 算法在點點幣中獲得成功應用，其數(shù)學函數(shù)計算設計為F（區(qū)塊頭/時間戮＜目標哈希值×幣齡權重），即幣齡越多，權重就越大，節(jié)點為出塊節(jié)點的概率也越大。PoS 若要發(fā)生攻擊，需要擁有51%以上的權益，其攻擊成本高于全網(wǎng)半數(shù)算力，且節(jié)點的權益是動態(tài)的，當區(qū)塊上鏈后其權益減少，這使得PoS 發(fā)生51%攻擊幾乎不可能，從而在一定程度上增加了區(qū)塊鏈的安全性。PoSpace 是PoS 算法的變形，是利用硬盤儲存空間競爭機制，將節(jié)點分為普通節(jié)點與校驗節(jié)點兩種類型，普通節(jié)點參與出塊節(jié)點競爭，通過哈希函數(shù)生成哈希摘要，這個哈希摘要將用于證明該節(jié)點確實存儲了特定的數(shù)據(jù)。校驗節(jié)點對其進行驗證，如果儲存了規(guī)定的數(shù)據(jù)，將對其全網(wǎng)廣播、達成共識，生成新區(qū)塊。一般來說，節(jié)點存儲空間越大，出塊概率就越大。文獻[20]針對PoS 共識算法區(qū)塊生成存在局限性，不能滿足實際場景的需要，融合了Raft 算法選舉主節(jié)點，改進了Silkworm 算法，通過智能合約對區(qū)塊生成速度進行了定義，即無論有無交易發(fā)生，都能保證Silkworm 算法高效生成區(qū)塊，實驗證實改進的Silkworm 算法能夠提升PoS 共識算法的性能，保證區(qū)塊鏈健壯性和安全性。文獻[21]針對PoS 共識算法存在富者愈富的“馬太效應”問題，引入評估方法，提出了一種基于動態(tài)分組的重要性共識優(yōu)化算法（DPoI）。算法依據(jù)節(jié)點的活躍度、交易、尋找隨機數(shù)的時間和信譽度計算每輪節(jié)點的重要性分數(shù)值，使用斐波那契數(shù)列分組，DPoI 投票機制，選出備選節(jié)點，有效地避免了系統(tǒng)停止的問題。

綜上，PoS 算法效率高、能耗低，基本上解決了PoW 節(jié)點挖礦資源浪費的問題，所有持幣者都能夠分享到獎勵，不易發(fā)生51%攻擊，安全性能得到加強。但是，也導致了“贏者通吃”的結果：該方案初期擁有大量貨幣的礦工會比其他礦工更容易獲得出塊權拿到利息獎勵，從而不斷擴大幣齡優(yōu)勢，容易形成富者越富的馬太效應。且?guī)帕闩c持幣時間掛鉤，會導致鼓勵礦工存幣拿利息，不利于流動性，不利于長久發(fā)展。

3.3 授權股份證明(Delegated Proof of Stake,DPoS)共識算法

DPoS 共識算法是在PoS 基礎上發(fā)展而來的，其共識思路是借鑒了現(xiàn)代企業(yè)管理制度“董事會”管理制度，即分布系統(tǒng)中的每個節(jié)點將自己持有的股份（持幣數(shù)量）作為選票委托授予一個代表，獲得票數(shù)最多的前101 節(jié)點作為代表性的節(jié)點，代表全部節(jié)點按照時間順序輪流坐莊進行記賬和驗證，生成新區(qū)塊，每個代表性的區(qū)塊將會獲得交易費的10%作為報酬。DPoS 共識算法如圖6 所示。與PoS 相比，DPoS 參與的共識節(jié)點的數(shù)量大幅減少，從而縮短了區(qū)塊鏈的出塊時間。

圖6 DPoS共識流程圖

DPoS 共識算法相對于PoS 共識算法，大幅度提高了效率，減少了資源浪費，增加了區(qū)塊鏈的安全性；但DPoS 算法仍然存在節(jié)點不主動積極、容易產(chǎn)生雙花、腐敗攻擊、權益不均等問題。為此，區(qū)塊鏈的研究者對DPoS 共識算法進行了一系列的優(yōu)化探索。文獻[22]針對DPoS 算法容易被惡意節(jié)點攻擊的問題，提出了一種基于節(jié)點權重的NW-DPoS（Delegated Proof of Stake based on Node Weight）共識算法，算法以埃歐塔（IOTA）為基礎，統(tǒng)籌考慮節(jié)點的歷史行為，具體是指將節(jié)點的信息、機制和在線狀態(tài)綜合考慮，并給予權重來達成共識，保證了誠實節(jié)點的高效出塊、作惡節(jié)點的處罰和作惡節(jié)點的清除。實驗表明，NW-DPoS 共識算法在雙花攻擊、賄賂攻擊方面優(yōu)于DPoS。文獻[23]針對DPoS 共識算法存在惡意節(jié)點聯(lián)合串通投票或權益過渡集中等問題，引入神經(jīng)網(wǎng)絡自適應學習能力，提升了共識節(jié)點的可信度，通過動態(tài)博弈信譽獎勵機制，提升了見證人區(qū)塊打包的安全性，通過沙普利值均衡了節(jié)點之間的收益，優(yōu)化了DPoS 共識算法節(jié)點選舉、見證人出塊順序及權益分配。由50 輪共識結果可知，改進后的算法出塊的穩(wěn)定性、安全性都得到了大幅度提升。文獻[24]對DPoS 共識算法選舉時間過長、惡意節(jié)點難以及時清除等問題，引入股票市場的“熔斷機制”，設置了反對票，對作惡節(jié)點直接踢出。為了進一步加快DPoS 共識，給節(jié)點設置了信用分數(shù)和信用等級，通過探針節(jié)點動態(tài)調整節(jié)點的信用，可及時地對作惡節(jié)點進行清除。

3.4 拜占庭容錯(Byzantine Fault Tolerance,BFT)算法

拜占庭將軍問題具體到區(qū)塊鏈中是指在交易中可能出現(xiàn)網(wǎng)絡擁擠堵塞、設備硬件故障、惡意節(jié)點攻擊、網(wǎng)絡節(jié)點之間缺乏信任等問題時，在保證活性和安全性的條件下，當惡意節(jié)點占比小于51%時，不會改變BFT 共識算法達成一致性。

1982 年Leslie 等對于網(wǎng)絡節(jié)點存在故障、錯誤或作惡的問題，首次提出了拜占庭將軍問題。BFT是一種基于消除或避免錯誤節(jié)點不超過某一臨界值時，正確節(jié)點之間就目標達成共識形成一致，不會因為錯誤節(jié)點的存在，影響共識的形成的共識算法。拜占庭容錯算法使用節(jié)點之間多頻率的信息交互，容忍一定量的惡意節(jié)點、強一致性來完成共識，不需要消耗算力挖礦，從而降低了計算機能源消耗。

BFT 本質上是通過每個節(jié)點之間發(fā)送信息，對客戶端提案、指令最終達成一致共識的結果。然而，隨著節(jié)點的增加，節(jié)點之間傳遞交換的信息呈指數(shù)級別增長，其復雜度也大幅增加，共識時間過長。另外，其加入退出需要單獨處理，其應用并未落地。1999 年文獻[25]構建了實用拜占庭容錯（Practical Byzantine Fault Tolerant,PBFT）算法，其繼承了BFT的優(yōu)點，創(chuàng)造性地將算法難度系數(shù)由指數(shù)級別降低到了多項式級別，容錯能力大幅提升。即如果一個區(qū)塊鏈系統(tǒng)中存在F個惡意節(jié)點，則系統(tǒng)至少需要3F+1 個節(jié)點才能完成共識，節(jié)點數(shù)為N的區(qū)塊鏈的容錯能力為(N-1)/3，只要惡意節(jié)點小于1/3 拜占庭節(jié)點，通過多次信息交換，誠實的共識信息將得到認可和執(zhí)行[26]，系統(tǒng)的活性及安全性將得到保證，拜占庭容錯算法的應用場景大幅增加。

PBFT 是BFT 共識算法代表性的共識協(xié)議，PBFT共識算法流程如圖7 所示。PBFT 共識主要分為預準備、準備和接受三個階段，節(jié)點分為主節(jié)點和副節(jié)點，主節(jié)點功能主要是收集數(shù)據(jù)、排序，并提出提案，副節(jié)點驗證提案的正確性，并按照順序將結果摘要組播至全網(wǎng)，各節(jié)點接受組網(wǎng)投票結果。PBFT 共識算法相對于BFT 共識算法在數(shù)據(jù)信息處理、共識時長、吞吐容量方面有了較大的改善，但仍然存在請求節(jié)點過多時，主節(jié)點容易過載、共識效率下降、主節(jié)點無退出機制、系統(tǒng)的可用性及安全性較低等問題。如三階段廣播在點對點分布式傳輸中，已造成傳遞次數(shù)劇烈增加，引起網(wǎng)絡擁擠等問題。為此，研究者對其從節(jié)點選取機制、引入長鏈制度等多方面進行了改進和優(yōu)化。

圖7 PBFT共識算法流程

文獻[27]針對PBFT 共識算法主節(jié)點選取終身制、通信開銷大等問題，對其共識節(jié)點的選取設置了動態(tài)加入和退出機制，使網(wǎng)絡節(jié)點由靜態(tài)轉為動態(tài)，同時增加了主節(jié)點選組最長鏈過程，保證了主節(jié)點的可信度。實驗結果表明，該算法提高了共識速度，減少了時延，提供了F=(N-1)/3 的容錯性，通信開銷比PBFT 算法降低了50%，使分布式通信系統(tǒng)的一致性、安全性和有效性都得到改善。改進后的實用拜占庭容錯（Evolution of Practical Byzantine Fault Tolerance，EPBFT）算法流程如圖8 所示。

圖8 EPBFT算法流程

文獻[28]在PBFT 共識算法的基礎上引入了一種動態(tài)加權機制，提出了一種聯(lián)盟鏈的加權共識算法（Weighted Byzantine Fault Tolerance，WBFT），算法流程如圖9 所示。算法賦予每個節(jié)點一個動態(tài)權重，限制惡意或故障節(jié)點參與共識過程。

圖9 WBFT算法流程

由圖9 可知，與PBFT 相比較，實驗結果顯示，WBFT 平均吞吐量增加了17.18%，平均時延降低了18.01%，其綜合性能得到了較大的改善，其代表性的產(chǎn)品為Fabric v0.6.0。文獻[29]提出的可擴展拜占庭容錯算法(Scalable Byzantine Fault Tolerance，SBFT)很好地解決了拜占庭算法的吞吐量擴容問題，SBFT算法采用收集器的線性傳輸模式，每個節(jié)點將信息直接發(fā)送給收集器，收集器直接廣播、驗證，只要惡意節(jié)點數(shù)小于3F+1，即可達成共識，SBFT 可完成200 個節(jié)點的共識。文獻[30]針對PBFT 通信資源浪費、效率低下的情況，提出了一種最短通信時間分組的GBFT 共識算法，算法的核心是設計減少節(jié)點之間的傳遞消息數(shù)來縮短共識時間。具體步驟是引入節(jié)點探針，通過節(jié)點探針獲取共識節(jié)點的IP 位置，以此構建一個通信時間矩陣，在矩陣中分割多個節(jié)點中心，并選取組長，組長采取與信用等級掛鉤的辦法輪換，做到探測節(jié)點動態(tài)感知新節(jié)點的加入和共識的自動達成。文獻[31]基于車輛聯(lián)網(wǎng)提出了一種安全高效的分布式共識算法SG(Score Groupingpbft)-PBFT 。設計的分布式結構可以減輕中心服務器的壓力，降低單節(jié)點攻擊的風險。SG-PBFT 共識算法改進了傳統(tǒng)的PBFT 共識算法，優(yōu)化了PBFT 共識過程，并使用評分分組機制，實現(xiàn)了更高的共識效率。實驗結果表明，該算法提高了區(qū)塊鏈一致性效率，有效防止單節(jié)點攻擊。當共識節(jié)點數(shù)量達到1 000 個時，算法的共識時間為傳統(tǒng)PBFT 共識算法的27%。

3.5 Ripple共識（consensus of Ripple）算法

Ripple 是一個基于互聯(lián)網(wǎng)的開源支付協(xié)議，其提供一種數(shù)據(jù)正確性優(yōu)先的支付解決方案，旨在通過使用分布式賬本技術來實現(xiàn)全球貨幣之間的實時結算和轉賬。其共識工作流程如圖10 所示。

圖10 Ripple算法共識流程

共識主要步驟為：1）驗證節(jié)點對交易直接驗證后，剔出不合法的交易，合法的交易進入候選集；2）每個驗證節(jié)點將自己的候選集作為提案點對點發(fā)送給其他驗證節(jié)點；3）當交易得到超過50%的票數(shù)進入下一步，反之，交易參與下一次共識過程；4）驗證節(jié)點將提案發(fā)送給其他節(jié)點，同時提高所需票數(shù)的閾值達到80%；5）將交易寫入本地賬本。共識算法的容錯能力為(N-1)/5，與PoW 相比，其交易確認時間只有數(shù)秒鐘，且任何時間都不會產(chǎn)生硬分叉，能夠維護全網(wǎng)的一致性和有效性。缺點是當新節(jié)點加入時，共識時間有所延長[32]。

4 非拜占庭容錯節(jié)點算法

4.1 Paxos共識算法

Paxos 算法是著名的算法工程師Lamport 在微軟研究院工作時設計的，是一種基于消息傳遞的一致性算法，用于解決復雜問題中確定值的問題。Paxos算法設計了提議者、決策者、接受者和學習者四種角色，其算法運行流程如圖11 所示[33]，共識過程通過三步完成：1）客戶端首先向儲存節(jié)點發(fā)出提案，儲存節(jié)點編制好提案編號、提案價值發(fā)送給決策者，當獲得決策者接受時，提案獲得成功，否則返回，等待下一次提案，決策者在這里相當于中間過程，其功能主要用于回復提議者提案；2）當一個提議者收到副本數(shù)半數(shù)以上的接受者回應，就選取一個值向所有儲存節(jié)點的接受者發(fā)送接受請求。如果之前接受者有回應值，這個請求的值就是該值，否則由提議者自己決定接收值；3）提議者如果收到半數(shù)以上的接受者回應，表示該次請求成功，通知各儲存節(jié)點的學習者，反之，返回重新提案。

圖11 Paxos算法共識流程

Paxos 共識算法能夠容忍部分節(jié)點信息缺失、延時和亂序等，其容錯能力為2F+1，在網(wǎng)絡存在異?；蚬?jié)點故障小于1/2 時能正常運轉。

4.2 Raft共識算法

Raft 算法相對于Paxos 算法采用許多假設，簡化了共識流程，使得其更容易應用。Raft 算法共識步驟：首先，采用心跳觸發(fā)機制選舉領導人，領導人定期向跟隨者發(fā)送心跳，跟隨者將自己的任期號遞進一位，將角色變成候選人，然后，向所有跟隨者發(fā)出投票請求，當該候選人獲得50%的跟隨者投票時，將成為下一位領導人，領導人將依據(jù)客戶端的請求，將日記條目加入到它的日記中復制，當日記被復制到多數(shù)服務器時，即認為達成了共識[34]。

Paxos 共識算法是單條日志項復制，進而組合多次決策實現(xiàn)一致，其安全性、活性較好，但其構建系統(tǒng)復雜且難以理解，技術一直未落地使用。Raft 算法對Paxos 共識算法進行了一些限制，要求新的連續(xù)日志才能當選領導人，跟隨者日志都是領導人的子集，而Paxos 算法無此要求，改進后的Raft 共識算法更容易。目前Raft 共識算法主要從優(yōu)化選舉方法、增加跟隨者對數(shù)據(jù)塊的校驗方法兩個方面進行改進，希望提高選舉成功率和屏蔽或剔除惡意節(jié)點。文獻[35]針對Raft 算法領導者選舉過程中投票分裂造成的時延問題，提出了一種基于PoW 高效共識的RPFT 算法，其步驟為先用PoW 共識算法選出副領導節(jié)點，然后給每一個節(jié)點一個等待時間，依據(jù)節(jié)點行為調整等待時間，建立時間選舉模型，快速選出高效領導者節(jié)點。實驗證實，RPFT 較Raft 算法性能提高了75%，共識效率提高了40%。

5 共識算法比較及場景應用

文中對目前成熟獲得應用的PoW、PoS、DPoS、PBFT 和Raft 等主流算法從設計思想、吞吐量、時延和優(yōu)缺點方面進行了對比，結果如表3 所示[16-18,21,25-27,29,32-34,36-38]?；谒懔Ω偁幍腜oW 算法完全去中心化、抗51%的攻擊，其應用場景主要在公有鏈，如比特幣將PoW 算法發(fā)揮的淋漓盡致，但其存在資源消耗大、容量小等問題；PoS 算法采用幣齡權益競爭機制，資源消耗、共識時間都大幅度減少，但容易產(chǎn)生雙花問題；投票類DPoS、BFT 等共識算法，采用節(jié)點投票選取代表節(jié)點達成共識，中心化程度有所降低，大多呈弱中心化，容錯概率也有所下降，如PBFT 的容錯率只有1/3，但其吞吐量大幅增加，其應用場景主要在公有鏈，也可用于私有鏈；Raft 等非拜占庭算法采用主從日志復制方案，識效率高、一致性好，主要用于聯(lián)盟鏈和私有鏈。

表3 共識算法比較

6 結束語

文中在研究區(qū)塊鏈結構、組成及架構的基礎上，對目前主流共識算法進行了概括總結，總結了PoW算法、PoS 權益類工作證明算法基本完全去中心化，其規(guī)模、安全性得到了很好的擴展，以公有鏈為應用場景；DPoS、DBFT 投票結果類共識算法擴展性好，適應于聯(lián)盟鏈；Raft 是推選領導，復制日志的算法，共識一致性好、可擴展性強，適合聯(lián)盟鏈、私有鏈。

受制區(qū)塊鏈去中心化、安全性及擴展性“三元悖論”的制約，只能弱化一方功能來提升另外兩方面性能，目前開發(fā)的多種算法都不能同時解決去中心化、網(wǎng)絡延遲、吞吐量擴容問題。為了解決網(wǎng)絡延遲、吞吐量擴容問題，建議研究者從如下幾個方面進行優(yōu)化：1）考慮在拜占庭算法引入“征信”、“網(wǎng)格化”增加惡意節(jié)點參與共識的成本，通過網(wǎng)格化管理。減少參與共識的節(jié)點數(shù)，節(jié)省底層網(wǎng)絡和通信資源，提升共識算法的效率和安全性；2）將證明類共識與選舉類共識算法進行加成融合，期望融合后的算法性能優(yōu)于單一算法，如PoW 與PoS 融合，PoW 與DBFT 融合等；3）現(xiàn)有共識算法與機器學習結合，通過有向無環(huán)圖選舉、排序和去重，提升區(qū)塊鏈共識效率及擴展性；4）研究并鏈、串鏈相關的技術，提升共識算法的擴展性、通用性等。