袁勇 倪曉春 曾帥 王飛躍

共識問題是社會科學和計算機科學等領域的經(jīng)典問題，已經(jīng)有很長的研究歷史。目前有記載的文獻至少可以追溯到1959年，蘭德公司和布朗大學的埃德蒙·艾森伯格（Edmund Eisenberg）和大衛(wèi)·蓋爾（David Gale）發(fā)表的《Consensus of subjective probabilities：The parimutuel method》，主要研究針對某個特定的概率空間，一組個體各自有其主觀的概率分布時，如何形成一個共識概率分布的問題。隨后，共識問題逐漸引起了社會學、管理學、經(jīng)濟學、特別是計算機科學等各學科領域的廣泛研究興趣。

計算機科學領域的早期共識研究一般聚焦于分布式一致性，即如何保證分布式系統(tǒng)集群中所有節(jié)點的數(shù)據(jù)完全相同并且能夠?qū)δ硞€提案達成一致的問題，是分布式計算的根本問題之一。雖然共識（consensus）和一致性（consistency）在很多文獻和應用場景中被認為是近似等價和可互換使用的，但二者涵義存在著細微的差別：共識研究側(cè)重于分布式節(jié)點達成一致的過程及其算法，而一致性研究則側(cè)重于節(jié)點共識過程最終達成的穩(wěn)定狀態(tài)；此外，傳統(tǒng)分布式一致性研究大多不考慮拜占庭容錯問題，即假設不存在惡意篡改和偽造數(shù)據(jù)的拜占庭節(jié)點，因此在很長一段時間里，傳統(tǒng)分布式一致性算法的應用場景大多是節(jié)點數(shù)量有限且相對可信的分布式數(shù)據(jù)庫環(huán)境。與之相比，區(qū)塊鏈系統(tǒng)的共識算法則必須運行于更為復雜、開放和缺乏信任的互聯(lián)網(wǎng)環(huán)境下，節(jié)點數(shù)量更多且可能存在惡意拜占庭節(jié)點。因此，即使viewstamped replication（以下簡稱 VR）和Paxos等許多分布式一致性算法早在20世紀80年代就已經(jīng)提出，但是如何跨越拜占庭容錯這道鴻溝、設計簡便易行的分布式共識算法，仍然是分布式計算領域的難題之一。

2008年10月31日，一位化名為“中本聰”的研究者在密碼學郵件組中發(fā)表了比特幣的奠基性論文《Bitcoin：A peer-to-peer electronic cash system》，基于區(qū)塊鏈（特別是公有鏈）的共識研究自此拉開序幕。從分布式計算和共識的角度來看，比特幣的根本性貢獻在于首次實現(xiàn)和驗證了一類實用的、互聯(lián)網(wǎng)規(guī)模的拜占庭容錯算法，從而打開了通往區(qū)塊鏈新時代的大門。

一般而言，區(qū)塊鏈系統(tǒng)的節(jié)點具有分布式、自治性、開放可自由進出等特性，因而大多采用對等式網(wǎng)絡（peer-to-peer network，P2P網(wǎng)絡）來組織散布全球的參與數(shù)據(jù)驗證和記賬的節(jié)點。P2P網(wǎng)絡中的每個節(jié)點均地位對等且以扁平式拓撲結(jié)構(gòu)相互連通和交互，不存在任何中心化的特殊節(jié)點和層級結(jié)構(gòu)，每個節(jié)點均會承擔網(wǎng)絡路由、驗證區(qū)塊數(shù)據(jù)、傳播區(qū)塊數(shù)據(jù)、發(fā)現(xiàn)新節(jié)點等功能。區(qū)塊鏈系統(tǒng)采用特定的經(jīng)濟激勵機制來保證分布式系統(tǒng)中所有節(jié)點均有動機參與數(shù)據(jù)區(qū)塊的生成和驗證過程，按照節(jié)點實際完成的工作量分配共識過程所產(chǎn)生的數(shù)字加密貨幣，并通過共識算法來選擇特定的節(jié)點將新區(qū)塊添加到區(qū)塊鏈。以比特幣為代表的一系列區(qū)塊鏈應用的蓬勃發(fā)展，彰顯了區(qū)塊鏈技術的重要性與應用價值，區(qū)塊鏈系統(tǒng)的共識也成為一個新的研究熱點。

迄今為止，研究者已經(jīng)在共識相關領域做了大量研究工作，不同領域研究者的側(cè)重點也各不相同。計算機學科通常稱為共識算法或者共識協(xié)議，管理和經(jīng)濟學科則通常稱為共識機制。細究之下，這些提法存在細微的差異：算法一般是一組順序敏感的指令集且有明確的輸入和輸出；而協(xié)議和機制則大多是一組順序不敏感的規(guī)則集。就區(qū)塊鏈領域而言，本文認為比特幣和以太坊等可認為是底層協(xié)議或機制，其詳細規(guī)定了系統(tǒng)或平臺內(nèi)部的節(jié)點交互規(guī)則、數(shù)據(jù)路由和轉(zhuǎn)發(fā)規(guī)則、區(qū)塊構(gòu)造規(guī)則、交易驗證規(guī)則、賬本維護規(guī)則等集合；而工作量證明（proof-of work，PoW）、權(quán)益證明（proof-of-stake，PoS）等則是建立在特定協(xié)議或機制基礎上、可靈活切換的算法，其規(guī)定了交易偵聽與打包、構(gòu)造區(qū)塊、記賬人選舉、區(qū)塊傳播與驗證、主鏈選擇與更新等若干類順序敏感的指令集合。因此，本文后續(xù)敘述均采用共識算法的提法。

現(xiàn)有文獻研究的共識問題實際上可以分為算法共識和決策共識兩個分支，前者致力于研究在特定的網(wǎng)絡模型和故障模型前提下，如何在缺乏中央控制和協(xié)調(diào)的分布式網(wǎng)絡中確保一致性，其實質(zhì)是一種“機器共識”；后者則更為廣泛地研究無中心的群體決策中，如何就最優(yōu)的決策達成一致的問題，例如關于比特幣系統(tǒng)擴容問題和分叉問題的社區(qū)討論與路線選擇，其實質(zhì)是“人的共識”。二者的區(qū)別在于：前者是機器間的確定性共識，以工程復雜性為主；而后者則是以“人在環(huán)路中（human-in-the-loop）”的復雜系統(tǒng)為特點的不確定性共識，以社會復雜性為主。區(qū)塊鏈共識算法研究應屬于算法共識分支的子集，而決策共識則大多見于分布式人工智能、多智能體等研究領域。

拜占庭將軍問題是分布式共識的基礎，也是上述兩個研究分支的根源。拜占庭將軍問題有兩個交互一致性條件，即一致性和正確性。由于大多數(shù)情況下，正確性涉及到人的主觀價值判斷，很難施加到分布式節(jié)點上，因此算法共識采用的是“降級的正確性（degraded correctness）”，即從“表達的內(nèi)容是正確的”降級為“正確地表達”，這就導致區(qū)塊鏈的拜占庭共識實際上是一種機器共識，其本身等價于分布式一致性+正確表達（不篡改消息）。與之相對的是，決策共識可以認為是人的共識，不僅要求一致性，而且要求所有節(jié)點相信“表達的內(nèi)容是正確的”，因而決策共識不僅要求內(nèi)容的客觀一致性，而且還要求其在共識節(jié)點間的主觀正確性。由此可見，算法共識處理的是客觀的二值共識，即對（唯一正確的賬本）和錯（所有錯誤的賬本），而決策共識處理的是主觀的多值共識，即意見 1（及其所屬群體）、意見 2（及其所屬群體）……意見N（及其所屬群體），各節(jié)點最終通過群體間的協(xié)調(diào)和協(xié)作過程收斂到唯一意見（共識），而此過程可能失?。ú皇諗浚?/p>

本文致力于按時間順序梳理和討論區(qū)塊鏈發(fā)展過程中的共識算法，以期為未來共識算法的創(chuàng)新和區(qū)塊鏈技術的發(fā)展提供參考。本文的后續(xù)章節(jié)安排如下：首先簡要介紹了分布式共識領域重要的里程碑式的研究和結(jié)論，包括兩軍問題、拜占庭問題和 FLP不可能定理，并介紹了傳統(tǒng)的分布式一致性算法；然后提出了區(qū)塊鏈共識算法的一種基礎模型和分類方法，并對當前主流的區(qū)塊鏈共識算法進行了分析；最后總結(jié)了區(qū)塊鏈共識算法的發(fā)展和研究趨勢。

1 傳統(tǒng)分布式一致性算法

1975年，紐約州立大學石溪分校的阿克云盧（E.A.Akkoyunlu）、?？{德漢姆（K.Ekanadham）和胡貝爾（R.V.Huber）在論文《Some constraints and tradeoffs in the design of network communications》中首次提出了計算機領域的兩軍問題及其無解性證明，著名的數(shù)據(jù)庫專家吉姆·格雷正式將該問題命名為“兩軍問題”。兩軍問題表明，在不可靠的通信鏈路上試圖通過通信達成一致共識是不可能的，這被認為是計算機通信研究中第一個被證明無解的問題。兩軍問題對計算機通信研究產(chǎn)生了重要的影響，互聯(lián)網(wǎng)時代最重要的 TCP/IP協(xié)議中的“三次握手”過程即是為解決兩軍問題不存理論解而誕生的簡單易行、成本可控的“工程解”。

分布式計算領域的共識問題于1980年由馬歇爾·皮斯（Marshall Pease）、羅伯特·肖斯塔克（Robert Shostak）和萊斯利·蘭伯特（Leslie Lamport）提出，該問題主要研究在一組可能存在故障節(jié)點、通過點對點消息通信的獨立處理器網(wǎng)絡中，非故障節(jié)點如何能夠針對特定值達成一致共識。1982年，作者在另一篇文章中正式將該問題命名為“拜占庭將軍問題”，提出了基于口頭消息和基于簽名消息的兩種算法來解決該問題。拜占庭假設是對現(xiàn)實世界的模型化，強調(diào)的是由于硬件錯誤、網(wǎng)絡擁塞或斷開以及遭到惡意攻擊，計算機和網(wǎng)絡可能出現(xiàn)的不可預料的行為。此后，分布式共識算法可以分為兩類，即拜占庭容錯和非拜占庭容錯類共識。早期共識算法一般為非拜占庭容錯算法，例如廣泛應用于分布式數(shù)據(jù)庫的VR和 Paxos，目前主要應用于聯(lián)盟鏈和私有鏈；2008年末，比特幣等公有鏈誕生后，拜占庭容錯類共識算法才逐漸獲得實際應用。需要說明的是，拜占庭將軍問題是區(qū)塊鏈技術核心思想的根源，直接影響著區(qū)塊鏈系統(tǒng)共識算法的設計和實現(xiàn)，因而在區(qū)塊鏈技術體系中具有重要意義。

1985年，邁克爾·費舍爾（Michael Fisher）、南希·林奇（Nancy Lynch）和邁克爾·帕特 森（Michael Paterson）共同發(fā)表了論文《Impossibility of distributed consensus with one faulty process》。這篇文章證明：在含有多個確定性進程的異步系統(tǒng)中，只要有一個進程可能發(fā)生故障，那么就不存在協(xié)議能保證有限時間內(nèi)使所有進程達成一致。按照作者姓氏的首字母，該定理被命名為FLP不可能定理，是分布式系統(tǒng)領域的經(jīng)典結(jié)論之一，并由此獲得了Dijkstra獎。FLP不可能定理同樣指出了存在故障進程的異步系統(tǒng)的共識問題不存在有限時間的理論解，因而必須尋找其可行的“工程解”。為此，研究者們只能通過調(diào)整問題模型來規(guī)避FLP不可能定理，例如犧牲確定性、增加時間等；加密貨幣則是通過設定網(wǎng)絡同步性（或弱同步性）和時間假設來規(guī)避 FLP不可能性，例如網(wǎng)絡節(jié)點可以快速同步，且礦工在最優(yōu)鏈上投入有限時間和資源等。

早期的共識算法一般也稱為分布式一致性算法。與目前主流的區(qū)塊鏈共識算法相比，分布式一致性算法主要面向分布式數(shù)據(jù)庫操作、且大多不考慮拜占庭容錯問題，即假設系統(tǒng)節(jié)點只發(fā)生宕機和網(wǎng)絡故障等非人為問題，而不考慮惡意節(jié)點篡改數(shù)據(jù)等問題。1988年，麻省理工學院的布萊恩·奧奇（Brian M.Oki）和芭芭拉·里斯科夫（Barbara H.Liskov，著名計算機專家、2008年圖靈獎得主）提出了VR一致性算法，采用主機—備份（primarybackup）模式，規(guī)定所有數(shù)據(jù)操作都必須通過主機進行，然后復制到各備份機器以保證一致性。1989年，萊斯利·蘭伯特（Leslie Lamport）在工作論文《The part-time parliament》中提出 Paxos算法，由于文章采用了講故事的敘事風格且內(nèi)容過于艱深晦澀，直到1998年才通過評審、發(fā)表在《ACM Transactions on Computer Systems》期刊上。Paxos是基于消息傳遞的一致性算法，主要解決分布式系統(tǒng)如何就某個特定值達成一致的問題。隨著分布式共識研究的深入，Paxos算法獲得了學術界和工業(yè)界的廣泛認可，并衍生出 Abstract Paxos、Classic Paxos、Byzantine Paxos和DiskPaxos等變種算法，成為解決異步系統(tǒng)共識問題最重要的算法家族。實際上，Liskove等提出的 VR算法本質(zhì)上也是一類Paxos算法。需要說明的是，VR和Paxos算法均假設系統(tǒng)中不存在拜占庭故障節(jié)點，因而是非拜占庭容錯的共識算法。除以上共識算法外，獲得較多研究關注的早期共識算法還有兩階段提交（Two-Phase Commit）算法、三階段提交（Three-Phase Commit）算法、Zab、Zyzzyva、Kafka等，本文限于篇幅不加詳述。

2 主流區(qū)塊鏈共識算法

1993年，美國計算機科學家、哈佛大學教授辛西婭·德沃克（Cynthia Dwork）首次提出了工作量證明思想，用來解決垃圾郵件問題。該機制要求郵件發(fā)送者必須算出某個數(shù)學難題的答案來證明其確實執(zhí)行了一定程度的計算工作，從而提高垃圾郵件發(fā)送者的成本。1997年，英國密碼學家亞當·伯克（Adam Back）也獨立地提出、并于2002年正式發(fā)表了用于哈?，F(xiàn)金（Hash Cash）的工作量證明機制。哈?，F(xiàn)金也是致力于解決垃圾郵件問題，其數(shù)學難題是尋找包含郵件接受者地址和當前日期在內(nèi)的特定數(shù)據(jù)的SHA-1哈希值，使其至少包含 20個前導零。1999年，馬庫斯·雅各布松（Markus Jakobsson）正式提出了“工作量證明”概念。這些工作為后來中本聰設計比特幣的共識機制奠定了基礎。

1999年，Barbara Liskov等提出了實用拜占庭容錯算法（Practical Byzantine Fault Tolerance，PBFT），解決了原始拜占庭容錯算法效率不高的問題，將算法復雜度由指數(shù)級降低到多項式級，使得拜占庭容錯算法在實際系統(tǒng)應用中變得可行。PBFT實際上是Paxos算法的變種，通過改進 Paxos算法使其可以處理拜占庭錯誤，因而也稱為Byzantine Paxos算法，可以在保證活性（liveness）和安全性（safety）的前提下提供（n-1）/3的容錯性，其中n為節(jié)點總數(shù)。

2000年，加利福尼亞大學的埃里克·布魯爾（Eric Brewer）教授在ACM Symposium on Principles of Distributed Computing研討會的特邀報告中提出了一個猜想：分布式系統(tǒng)無法同時滿足一致性（consistency）、可用性（availability）和分區(qū)容錯性（partition tolerance），最多只能同時滿足其中兩個。其中，一致性是指分布式系統(tǒng)中的所有數(shù)據(jù)備份在同一時刻保持同樣的值；可用性是指集群中部分節(jié)點出現(xiàn)故障時，集群整體是否還能處理客戶端的更新請求；分區(qū)容忍性則是指是否允許數(shù)據(jù)分區(qū)，不同分區(qū)的集群節(jié)點之間無法互相通信。2002年，塞斯·吉爾伯特（Seth Gilbert）和南?！ち制妫∟ancy Lynch）在異步網(wǎng)絡模型中證明了這個猜想，使其成為 CAP定理或布魯爾定理。該定理使得分布式網(wǎng)絡研究者不再追求同時滿足3個特性的完美設計，而是不得不在其中做出取舍，這也為后來的區(qū)塊鏈體系結(jié)構(gòu)設計帶來了影響和限制。

2008年10月，中本聰發(fā)表的比特幣創(chuàng)世論文催生了基于區(qū)塊鏈的共識算法研究。前文所提到的傳統(tǒng)分布式一致性算法大多應用于相對可信的聯(lián)盟鏈和私有鏈，而面向比特幣、以太坊等公有鏈環(huán)境則誕生了 PoW、PoS等一系列新的拜占庭容錯類共識算法。

比特幣采用了PoW共識算法來保證比特幣網(wǎng)絡分布式記賬的一致性，這也是最早和迄今為止最安全可靠的公有鏈共識算法。PoW 的核心思想是通過分布式節(jié)點的算力競爭來保證數(shù)據(jù)的一致性和共識的安全性。比特幣系統(tǒng)的各節(jié)點（即礦工）基于各自的計算機算力相互競爭來共同解決一個求解復雜但是驗證容易的 SHA256數(shù)學難題（即挖礦），最快解決該難題的節(jié)點將獲得下一區(qū)塊的記賬權(quán)和系統(tǒng)自動生成的比特幣獎勵。PoW 共識在比特幣中的應用具有重要意義，其近乎完美地整合了比特幣系統(tǒng)的貨幣發(fā)行、流通和市場交換等功能，并保障了系統(tǒng)的安全性和去中心性。然而，PoW 共識同時存在著顯著的缺陷，其強大算力造成的資源浪費（主要是電力消耗）歷來為人們所詬病，而且長達10分鐘的交易確認時間使其相對不適合小額交易的商業(yè)應用。

2011年7月，一位名為Quantum Mechanic的數(shù)字貨幣愛好者在比特幣論壇（www.bitcointalk.org）首次提出了權(quán)益證明 PoS共識算法。隨后，Sunny King在2012年8月發(fā)布的點點幣（Peercoin，PPC）中首次實現(xiàn)。PoS由系統(tǒng)中具有最高權(quán)益而非最高算力的節(jié)點獲得記賬權(quán)，其中權(quán)益體現(xiàn)為節(jié)點對特定數(shù)量貨幣的所有權(quán)，稱為幣齡或幣天數(shù)（coin days）。PPC將 PoW 和 PoS兩種共識算法結(jié)合起來，初期采用PoW挖礦方式以使得Token相對公平地分配給礦工，后期隨著挖礦難度增加，系統(tǒng)將主要由 PoS共識算法維護。PoS一定程度上解決了PoW算力浪費的問題，并能夠縮短達成共識的時間，因而比特幣之后的許多競爭幣都采用PoS共識算法。

2013年 2月，以太坊創(chuàng)始人Vitalik Buterin在比特幣雜志網(wǎng)站詳細地介紹了 Ripple（瑞波幣）及其共識過程的思路。Ripple項目實際上早于比特幣，2004年就由瑞安·福格爾（Ryan Fugger）實現(xiàn)，其初衷是創(chuàng)造一種能夠有效支持個人和社區(qū)發(fā)行自己貨幣的去中心化貨幣系統(tǒng)；2014年，大衛(wèi)·施瓦爾茨（David Schwartz）等提出了瑞波協(xié)議共識算法（Ripple Protocol Consensus Algorithm，RPCA），該共識算法解決了異步網(wǎng)絡節(jié)點通訊時的高延遲問題，通過使用集體信任的子網(wǎng)絡（collectively-trusted subnetworks），在只需最小化信任和最小連通性的網(wǎng)絡環(huán)境中實現(xiàn)了低延遲、高魯棒性的拜占庭容錯共識算法。目前，Ripple已經(jīng)發(fā)展為基于區(qū)塊鏈技術的全球金融結(jié)算網(wǎng)絡。

2013年8月，比特股（Bitshares）項目提出了一種新的共識算法，即授權(quán)股份證明算法（delegated proofof-stake，DPoS）。DPoS共識的基本思路類似于“董事會決策”，即系統(tǒng)中每個節(jié)點可以將其持有的股份權(quán)益作為選票授予一個代表，獲得票數(shù)最多且愿意成為代表的前N個節(jié)點將進入“董事會”，按照既定的時間表輪流對交易進行打包結(jié)算、并且簽署（即生產(chǎn)）新區(qū)塊。如果說PoW和PoS共識分別是“算力為王”和“權(quán)益為王”的記賬方式的話，DPoS則可以認為是“民主集中式”的記賬方式，其不僅能夠很好地解決PoW浪費能源和聯(lián)合挖礦對系統(tǒng)的去中心化構(gòu)成威脅的問題，也能夠彌補 PoS中擁有記賬權(quán)益的參與者未必希望參與記賬的缺點，其設計者認為DPoS是當時最快速、最高效、最去中心化和最靈活的共識算法。

2013年，斯坦福大學的迭戈·翁伽羅（Diego Ongaro）和約翰·奧斯特豪特（John Ousterhout）提出了Raft共識算法。正如其論文標題《In search of an understandable consensus algorithm》所述，Raft的初衷是為設計一種比 Paxos更易于理解和實現(xiàn)的共識算法。要知道，由于Paxos論文極少有人理解，Lamport于 2001年曾專門寫過一篇文章《Paxos made simple》，試圖簡化描述 Paxos算法但效果不好，這也直接導致了Raft的提出。目前，Raft已經(jīng)在多個主流的開源語言中得以實現(xiàn)。

3 共識算法的模型與分類

隨著比特幣的普及和區(qū)塊鏈技術的發(fā)展，越來越多的新共識算法被提出。為使讀者更為深刻地理解不同的共識算法，本節(jié)給出區(qū)塊鏈共識過程的一個主流模型。需要說明的是，該模型并非通用模型，可能無法涵蓋所有種類的共識過程，但是可以體現(xiàn)大多數(shù)主流共識算法的核心思想。

區(qū)塊鏈系統(tǒng)建立在 P2P網(wǎng)絡之上，其全體節(jié)點的集合可記為P，一般分為生產(chǎn)數(shù)據(jù)或者交易的普通節(jié)點，以及負責對普通節(jié)點生成的數(shù)據(jù)或者交易 進行驗證、打包、更新上鏈等挖礦操作的“礦工”節(jié)點集合（記為M），兩類節(jié)點可能會有交集；礦工節(jié)點通常情況下會全體參與共識競爭過程，在特定算 法中也會選舉特定的代表節(jié)點、代替他們參加共識過程并競爭記賬權(quán)，這些代表節(jié)點的集合記為 D；通過共識過程選定的記賬節(jié)點記為 A。共識過程按照輪次重復執(zhí)行，每一輪共識過程一般重新選擇該輪的記賬節(jié)點。

共識過程的核心是“選主”和“記賬”兩部分，在具體操作過程中每一輪可以分為選主（leader election）、造塊（block generation）、驗證（data validation）和上鏈（chain updation，即記賬）4個階段。共識過程的輸入是數(shù)據(jù)節(jié)點生成和驗證后的交易或數(shù)據(jù)，輸出則是封裝好的數(shù)據(jù)區(qū)塊以及更新后的區(qū)塊鏈。四個階段循環(huán)往復執(zhí)行，每執(zhí)行一輪將會生成一個新區(qū)塊。

第一階段：選主。選主是共識過程的核心，即從全體礦工節(jié)點集M中選出記賬節(jié)點A的過程；我們可以使用公式f（M）→A來表示選主過程，其中函數(shù)f代表共識算法的具體實現(xiàn)方式。一般來說，|A|＝1，即最終選擇唯一的礦工節(jié)點來記賬。

第二階段：造塊。第一階段選出的記賬節(jié)點根據(jù)特定的策略將當前時間段內(nèi)全體節(jié)點 P生成的交易或者數(shù)據(jù)打包到一個區(qū)塊中，并將生成的新區(qū)塊廣播給全體礦工節(jié)點M 或其代表節(jié)點 D。這些交易或者數(shù)據(jù)通常根據(jù)區(qū)塊容量、交易費用、交易等待時間等多種因素綜合排序后，依序打包進新區(qū)塊。造塊策略是區(qū)塊鏈系統(tǒng)性能的關鍵因素，也是貪婪交易打包、自私挖礦等礦工策略性行為的集中體現(xiàn)。

第三階段：驗證。礦工節(jié)點 M或者代表節(jié)點D收到廣播的新區(qū)塊后，將各自驗證區(qū)塊內(nèi)封裝的交易或者數(shù)據(jù)的正確性和合理性。如果新區(qū)塊獲得大多數(shù)驗證/代表節(jié)點的認可，則該區(qū)塊將作為下一區(qū)塊更新到區(qū)塊鏈。

第四階段：上鏈。記賬節(jié)點將新區(qū)塊添加到主鏈，形成一條從創(chuàng)世區(qū)塊到最新區(qū)塊的完整的、更長的鏈條。如果主鏈存在多個分叉鏈，則需根據(jù)共識算法規(guī)定的主鏈判別標準，來選擇其中一條恰當?shù)姆种ё鳛橹麈湣?/p>

區(qū)塊鏈共識算法可以根據(jù)其容錯類型、部署方式和一致性程度等多個維度加以分類。例如，根據(jù)容錯類型，可以將區(qū)塊鏈共識算法分為拜占庭容錯和非拜占庭容錯兩類；根據(jù)部署方式，可以將區(qū)塊鏈共識算法分為公有鏈共識、聯(lián)盟鏈共識和私有鏈共識3類；根據(jù)一致性程度，還可以將區(qū)塊鏈共識算法分為強一致性共識和弱（最終）一致性共識等。本文提出一種按照共識過程的選主策略的新分類方法，其優(yōu)點在于便于刻畫共識算法的核心機理。具體來說，可根據(jù)選主策略（即函數(shù)f的具體實現(xiàn)方式）將區(qū)塊鏈共識算法分為選舉類、證明類、隨機類、聯(lián)盟類和混合類共 5種類型。

選舉類共識：即礦工節(jié)點在每一輪共識過程中通過“投票選舉”的方式選出當前輪次的記賬節(jié)點，首先獲得半數(shù)以上選票的礦工節(jié)點將會獲得記賬權(quán)；多見于傳統(tǒng)分布式一致性算法，例如 Paxos和Raft等。

證明類共識：也可稱為“Proof of X”類共識，即礦工節(jié)點在每一輪共識過程中必須證明自己具有某種特定的能力，證明方式通常是競爭性地完成某項難以解決但易于驗證的任務，在競爭中勝出的礦工節(jié)點將獲得記賬權(quán)；例如PoW和PoS等共識算法是基于礦工的算力或者權(quán)益來完成隨機數(shù)搜索任務，以此競爭記賬權(quán)。

隨機類共識：即礦工節(jié)點根據(jù)某種隨機方式直接確定每一輪的記賬節(jié)點，例如下文將要提到的Algorand和PoET共識算法等。

聯(lián)盟類共識：即礦工節(jié)點基于某種特定方式首先選舉出一組代表節(jié)點，而后由代表節(jié)點以輪流或者選舉的方式依次取得記賬權(quán)。這是一種以“代議制”為特點的共識算法，例如DPoS等。

混合類共識：即礦工節(jié)點采取多種共識算法的混合體來選擇記賬節(jié)點，例如PoW+PoS混合共識、DPoS+BFT共識等。

4 區(qū)塊鏈共識算法的新進展

自2014年起，隨著比特幣和區(qū)塊鏈技術快速進入公眾視野，許多學者開始關注并研究區(qū)塊鏈技術，共識算法也因此進入快速發(fā)展、百花齊放的時期。許多新共識算法在這段時間被提出。它們或者是原有算法的簡單變種，或者是為改進某一方面性能而做出的微創(chuàng)新，或者是為適應新場景和新需求而做出重大改進的新算法。需要說明的是，這些共識算法由于提出時間晚，目前大多尚未獲得令人信服的實踐驗證，有些甚至只是科研設想；但這些算法均具有明顯的創(chuàng)新之處，具有一定的大規(guī)模應用的前景，因此我們寫出來以饗讀者，并期待能夠啟發(fā)后續(xù)的創(chuàng)新研究。

4.1 主線一：PoW與PoS算法的有機結(jié)合

研究者基于PoW和PoS算法的有機結(jié)合，相繼提出了權(quán)益—速度證明 （proof of stake velocity，PoSV）、燃燒證明（proof of burn，PoB）、行動證明（proof of activity，PoA）和二跳（2-hop）共識算法，致力于取長補短、解決PoW與PoS存在的能源消耗與安全風險問題。2014年 4月，拉里·雷恩（Larry Ren）在蝸牛幣 Reddcoin白皮書中提出了PoSV共識算法，針對PoS中幣齡是時間的線性函數(shù)這一問題進行改進，致力于消除持幣人的屯幣現(xiàn)象。PoSV算法前期使用 PoW實現(xiàn)代幣分配，后期使用PoSV維護網(wǎng)絡長期安全。PoSV將PoS中幣齡和時間的線性函數(shù)修改為指數(shù)式衰減函數(shù)，即幣齡的增長率隨時間減少最后趨于零。因此新幣的幣齡比老幣增長地更快，直到達到上限閾值，這在一定程度上緩和了持幣者的屯幣現(xiàn)象。2014年 5月發(fā)行的Slimcoin借鑒了比特幣和點點幣的設計，基于PoW和PoS首創(chuàng)提出了PoB共識算法。其中，PoW共識被用來產(chǎn)生初始的代幣供應，隨著時間增長，區(qū)塊鏈網(wǎng)絡累積了足夠的代幣時，系統(tǒng)將依賴PoB和PoS共識來共同維護。PoB共識的特色是礦工通過將其持有的 Slimcoin發(fā)送至特定的無法找回的地址（燃燒）來競爭新區(qū)塊的記賬權(quán)，燃燒的幣越多則挖到新區(qū)塊的概率越高。2014年12月提出的PoA共識也是基于PoW和PoS，其中采用PoW挖出的部分代幣以抽獎的方式分發(fā)給所有活躍節(jié)點，而節(jié)點擁有的權(quán)益與抽獎券的數(shù)量即抽中概率成正比。二跳共識于2017年4月提出，其設計初衷是為解決 PoW 潛在的51%算力攻擊問題，解決思路是在PoW算力的基礎上引入PoS權(quán)益，使得區(qū)塊鏈安全建立在誠實節(jié)點占有大多數(shù)聯(lián)合資源（算力+權(quán)益）的基礎上。換句話說，拜占庭節(jié)點必須同時控制 51%以上的算力和51%以上的權(quán)益，才能成功實施51%攻擊，這無疑極大地提高了區(qū)塊鏈的安全性。

4.2 主線二：原生PoS算法的改進

原生 PoS共識算法的改進目標主要是解決其固有的“無利害關系（nothing at stake）” 問題，形成了Tendermint以及由其衍生出的 Casper、Ouroboros、Tezos和Honeybadger等新共識算法。原生PoS共識一般假設系統(tǒng)中的對等節(jié)點都是靜態(tài)和長期穩(wěn)定的，這在區(qū)塊鏈環(huán)境中并不現(xiàn)實。2014年提出的 Tendermint的重大突破是使用區(qū)塊、哈希鏈接、動態(tài)驗證器集合和循環(huán)的領導者選舉，實現(xiàn)了第一個基于PBFT的PoS共識算法。為解決無利害關系問題，Tendermint節(jié)點需要繳納保證金，如果作惡則保證金就會被沒收。Tendermint是一種拜占庭容錯的共識算法，具有抵御雙花攻擊的魯棒性，并且可以抵御網(wǎng)絡中至多1/3的破壞者的攻擊。

2015年提出的 Casper是以太坊計劃在其路線圖中稱為寧靜（serenity）的第 4階段采用的共識算法，尚在設計、討論和完善階段。目前Casper總共有兩個版本，即由Vlad Zamjir領導的Casper the Friendly Ghost（CTFG）和由Vitalik Buterin帶領實現(xiàn)的 Casper Friendly Finality Gadget（CFFG）。前者是明確的 PoS共識，而后者則是 PoW和PoS共識的有機結(jié)合。同時，PoS共識的兩個主要原理分別是基于鏈的PoS和基于拜占庭容錯的PoS。Tendermint是基于拜占庭容錯的PoS設計。相比之下，CTFG是基于鏈的PoS設計，而CFFG則是兩者的結(jié)合。

2016年提出的HoneyBadger共識是首個實用的異步拜占庭容錯共識協(xié)議，可以在沒有任何網(wǎng)絡時間假設的前提下保證區(qū)塊鏈系統(tǒng)的活性（liveness）。該共識基于一種可實現(xiàn)漸進有效性的原子廣播協(xié)議，能夠在廣域網(wǎng)的上百個節(jié)點上處理每秒上萬筆交易。2017年8月提出的 Ouroboros共識是首個基于 PoS并且具有嚴格安全性保障的區(qū)塊鏈協(xié)議，其特色是提出了一種新的獎勵機制來驅(qū)動 PoS共識過程，使得誠實節(jié)點的行為構(gòu)成一個近似納什均衡，可以有效地抵御區(qū)塊截留和自私挖礦等由于礦工的策略性行為而導致的安全攻擊。

4.3 主線三：原生PoW共識算法的改進

原生PoW共識算法的改進目標主要是實現(xiàn)比特幣擴容或者降低其能耗。2016年3月，康奈爾大學的Ittay Eyal等提出一種新的共識算法Bitcoin NG，將時間切分為不同的時間段。在每一個時間段上由一個領導者負責生成區(qū)塊、打包交易。該協(xié)議引入了兩種不同的區(qū)塊：用于選舉領導者的關鍵區(qū)塊和包含交易數(shù)據(jù)的微區(qū)塊。關鍵區(qū)塊采用比特幣PoW共識算法生成，然后領導者被允許小于預設閾值的速率（例如10 s）來生成微區(qū)塊。Bitcoin NG可在不改變區(qū)塊容量的基礎上通過選舉領導者生成更多的區(qū)塊，從而可輔助解決比特幣的擴容問題。同年8月提出的ByzCoin共識算法借鑒了Bitcoin-NG這種領導者選舉和交易驗證相互獨立的設計思想，是一種新型的可擴展拜占庭容錯算法，可使得區(qū)塊鏈系統(tǒng)在保持強一致性的同時，達到超出 Paypal吞吐量的高性能和低確認延遲。2016年提出的Elastico共識機制通過分片技術來增強區(qū)塊鏈的擴展性，其思路是將挖礦網(wǎng)絡以可證明安全的方式隔離為多個分片（shard），這些分片并行地處理互不相交的交易集合。Elastico是第一個拜占庭容錯的安全分片協(xié)議。2017年，OmniLedger進一步借鑒 ByzCoin和 Elastico共識，設計并提出名為ByzCoinX的拜占庭容錯協(xié)議。OmniLedger通過并行跨分片交易處理優(yōu)化區(qū)塊鏈性能，是第一種能夠提供水平擴展性而不必犧牲長期安全性和去中心性的分布式賬本架構(gòu)。

為改進 PoW 共識算法的效率（能耗）和公平性，研究者相繼提出了消逝時間證明（proof of elapsed Time，PoET）和運氣證明（proof of luck，PoL）。PoET和 PoL均是基于特定的可信執(zhí)行環(huán)境（trusted execution environments，TEE，例如基于IntelSGX技術的CPU）的隨機共識算法。PoET是超級賬本HyperLedger的鋸齒湖 Sawtooth項目采用的共識算法，其基本思路是每個區(qū)塊鏈節(jié)點都根據(jù)預定義的概率分布生成一個隨機數(shù)，來決定其距離下一次獲得記賬權(quán)的等待時間。每當一個新區(qū)塊提交到區(qū)塊鏈系統(tǒng)后，SGX即可幫助節(jié)點創(chuàng)建區(qū)塊、生成該等待時間的證明，而這種證明易于被其他SGX節(jié)點驗證。PoET共識的意義在于使得區(qū)塊鏈系統(tǒng)不必消耗昂貴算力來挖礦、從而提高了效率，同時也真正實現(xiàn)了“一 CPU一票”的公平性。類似地，PoL共識也采用 TEE平臺的隨機數(shù)生成器來選擇每一輪共識的領導者（記賬人），從而可降低交易驗證延遲時間和交易確認時間、實現(xiàn)可忽略的能源消耗和真正公平的分布式挖礦。

2014年提出的空間證明（proof of space，PoSp）和2017年提出的有益工作證明（proof of useful work，PoUW）也是為解決 PoW的能耗問題而提出的共識算法。PoSp共識要求礦工必須出具一定數(shù)量的磁盤空間（而非算力）來挖礦，而 PoUW則將 PoW 共識中毫無意義的SHA256哈希運算轉(zhuǎn)變?yōu)閷嶋H場景中既困難又有價值的運算，例如計算正交向量問題、3SUM問題、最短路徑問題等。

4.4 主線四：傳統(tǒng)分布式一致性算法的改進及其他

傳統(tǒng)分布式一致性算法大多是非拜占庭容錯的，因而難以應用于區(qū)塊鏈場景（特別是公有鏈）。為此，克里斯托弗·科普蘭（Christopher Copeland）等結(jié)合Raft和PBFT算法的優(yōu)勢，于2014年提出拜占庭容錯的 Tangaroa算法。Tangaroa繼承了Raft簡潔和容易理解的優(yōu)勢，同時在拜占庭錯誤環(huán)境下也能夠維持安全性、容錯性和活性。受 Tangaroa共識啟發(fā)，2016年 Github平臺的Juno項目提出一種拜占庭容錯的Raft算法，此后該算法演變?yōu)橐环N稱為 ScalableBFT的專用拜占庭容錯協(xié)議，能夠?qū)崿F(xiàn)比 Tangaroa和Juno更好的性能。

2015年，Stellar.org首席科學官David Mazieres教授提出了恒星共識協(xié)議（stellar consensus protocol，SCP）。SCP在聯(lián)邦拜占庭協(xié)議和Ripple協(xié)議的基礎上演化而來的，是第一個可證明安全的共識機制，具有分散控制、低延遲、靈活信任和漸進安全4個關鍵屬性。同年，超級賬本的鋸齒湖項目將 Ripple和SCP共識相結(jié)合，提出了法定人數(shù)投票（quorum voting）共識算法，以應對那些需要即時交易最終性的應用場景。2016年，中國區(qū)塊鏈社區(qū) NEO（原名小蟻）提出一種改進的拜占庭容錯算法dBFT，該算法在 PBFT的基礎上借鑒了 PoS設計思路，首先按照節(jié)點的權(quán)益來選出記賬人，然后記賬人之間通過拜占庭容錯算法來達成共識。該算法改進了PoW和PoS缺乏最終一致性的問題，使得區(qū)塊鏈能夠適用于金融場景。

2016年，圖靈獎得主、MIT教授 Sivio Micali提出了一種稱為AlgoRand的快速拜占庭容錯共識算法。該算法利用密碼抽簽技術選擇共識過程的驗證者和領導者，并通過其設計的 BA*拜占庭容錯協(xié)議對新區(qū)塊達成共識。AlgoRand只需極小計算量且極少分叉，被認為是真正民主和高效的分布式賬本共識技術。

2017年，康奈爾大學提出了一種稱為 sleepy consensus（休眠共識）的新算法。這種共識針對的是互聯(lián)網(wǎng)環(huán)境下大規(guī)模的共識節(jié)點中可能多數(shù)都處于離線狀態(tài)，僅有少數(shù)節(jié)點在線參與共識過程的實際情況。該研究證明，傳統(tǒng)共識算法無法在這種環(huán)境下保證共識的安全性。而采用休眠共識算法，只要在線誠實節(jié)點的數(shù)量超過故障節(jié)點的數(shù)量，即可保證安全性和魯棒性。

綜上所述，區(qū)塊鏈共識算法的演進歷史，給出了每一種共識算法的提出時間、拜占庭容錯性能、基礎算法以及具有代表性的應用系統(tǒng)或平臺。

5 總結(jié)與展望

共識算法是區(qū)塊鏈系統(tǒng)的關鍵要素之一，已成為當前信息領域的一個新的研究熱點。本文對目前已經(jīng)提出的32種主流區(qū)塊鏈共識算法進行了系統(tǒng)性的梳理與分析。需要說明的是，由于近年來共識算法研究發(fā)展較快，本文討論的共識算法可能僅為實際共識算法的一個子集，尚存在若干新興或者小眾的共識算法未加以討論，同時一些較新的共識算法仍在不斷試錯和優(yōu)化階段。本文工作可望為后續(xù)的研究與應用提供有益的啟發(fā)與借鑒。

以目前的研究現(xiàn)狀而言，區(qū)塊鏈共識算法的未來研究趨勢將主要側(cè)重于區(qū)塊鏈共識算法性能評估、共識算法—激勵機制的適配優(yōu)化、以及新型區(qū)塊鏈結(jié)構(gòu)下的共識創(chuàng)新3個方面。

首先，區(qū)塊鏈共識算法在經(jīng)歷過一段百花齊放式的探索和創(chuàng)新之后，勢必會趨向于收斂到新共識算法的性能評估和標準化方面的研究。目前，共識算法的評價指標各異，但一般均側(cè)重于社會學角度的公平性和去中心化程度，經(jīng)濟學角度的能耗、成本與參與者的激勵相容性，以及計算機科學角度的可擴展性（交易吞吐量、節(jié)點可擴展等）、容錯性和安全性等。如何結(jié)合具體需求和應用場景，自適應地實現(xiàn)針對特定性能評價目標的共識機制設計與算法優(yōu)化，將是未來研究的熱點之一。

其次，區(qū)塊鏈的共識算法與激勵機制是緊密耦合、不可分割的整體，同時二者互有側(cè)重點：共識算法規(guī)定了礦工為維護區(qū)塊鏈賬本安全性、一致性和活性而必須遵守的行為規(guī)范和行動次序；激勵機制則規(guī)定了在共識過程中為鼓勵礦工忠實、高效的驗證區(qū)塊鏈賬本數(shù)據(jù)而發(fā)行的經(jīng)濟權(quán)益，通常包括代幣發(fā)行機制、代幣分配機制、交易費定價機制等。從研究角度來看，如果將區(qū)塊鏈系統(tǒng)運作過程建模為礦工和礦池的大群體博弈過程的話，那么共識算法將決定其博弈樹的結(jié)構(gòu)和形狀、激勵機制將決定礦工和礦池在博弈樹中每個葉子結(jié)點的收益。因此，區(qū)塊鏈共識算法和激勵機制不僅各自存在獨立優(yōu)化的必要性，更為重要地是共識—激勵二元耦合機制的聯(lián)合優(yōu)化、實現(xiàn)共識與激勵的“適配”，這是解決區(qū)塊鏈系統(tǒng)中不斷涌現(xiàn)出的扣塊攻擊、自私挖礦等策略性行為、保障區(qū)塊鏈系統(tǒng)健康穩(wěn)定運行的關鍵問題，迫切需要未來研究的跟進。

最后，隨著區(qū)塊鏈技術的發(fā)展、特別是數(shù)據(jù)層的技術和底層拓撲結(jié)構(gòu)的不斷創(chuàng)新，目前已經(jīng)涌現(xiàn)出若干新興的區(qū)塊“鏈”數(shù)據(jù)結(jié)構(gòu)，例如有向無環(huán)圖（directed acyclic graph）和哈希圖（Hash Graph）等。這些新數(shù)據(jù)結(jié)構(gòu)將以單一鏈條為基礎的區(qū)塊鏈技術的范疇拓展為基于圖結(jié)構(gòu)的區(qū)塊“鏈”或分布式賬本。例如適用于物聯(lián)網(wǎng)支付場景的數(shù)字貨幣IOTA即采用稱為“tangle（纏結(jié)）”的DAG拓撲結(jié)構(gòu)，其共識過程以交易（而非區(qū)塊）為粒度，每個交易都引證其他兩個交易的合法性、形成DAG網(wǎng)絡，因而可以實現(xiàn)無區(qū)塊（blockless）共識；Hash Graph共識則更進一步，基于Gossip of Gossip協(xié)議和虛擬投票等技術，以交易為粒度，在特定的DAG結(jié)構(gòu)上實現(xiàn)公平和快速的拜占庭容錯共識。這些新型區(qū)塊拓撲結(jié)構(gòu)及其共識算法是未來發(fā)展趨勢之一，建立在這些新型數(shù)據(jù)結(jié)構(gòu)之上的共識算法也值得深入研究。

（摘自《自動化學報》網(wǎng)絡優(yōu)先出版 發(fā)表時間：2018年9月27日）