發布時間：2020-03-17所屬分類：計算機職稱論文瀏覽：1次
摘 要： 摘要共識算法是區塊鏈技術的核心要素，也是近年來分布式系統研究的熱點.本文系統性地梳理和討論了區塊鏈發展過程中的32種重要共識算法，介紹了傳統分布式一致性算法以及分布式共識領域的里程碑式的重要研究和結論，提出了區塊鏈共識算法的一種基礎模型和分類
摘要共識算法是區塊鏈技術的核心要素，也是近年來分布式系統研究的熱點.本文系統性地梳理和討論了區塊鏈發展過程中的32種重要共識算法，介紹了傳統分布式一致性算法以及分布式共識領域的里程碑式的重要研究和結論，提出了區塊鏈共識算法的一種基礎模型和分類方法，并總結了現有共識算法的發展脈絡和若干性能指標，以期為未來共識算法的創新和區塊鏈技術的發展提供參考.
關鍵詞區塊鏈，共識算法，分布式系統，拜占庭容錯，P2P網絡
共識問題是社會科學和計算機科學等領域的經典問題，已經有很長的研究歷史.目前有記載的文獻至少可以追溯到1959年，蘭德公司和布朗大學的埃德蒙·艾森伯格(EdmundEisenberg)和大衛.蓋爾(DavidGale)發表的“Consensusofsubjectiveprobabilities：thepari—mutuelmethod”，主要研究針對某個特定的概率空間，一組個體各自有其主觀的概率分布時，如何形成一個共識概率分布的問題【.隨后，共識問題逐漸引起了社會學、管理學、經濟學、特別是計算機科學等各學科領域的廣泛研究興趣.
計算機科學領域的早期共識研究一般聚焦于分布式一致性，即如何保證分布式系統集群中所有節點的數據完全相同并且能夠對某個提案達成一致的問題，是分布式計算的根本問題之一.雖然共識(Consensus)和一致性(Consistency)在很多文獻和應用場景中被認為是近似等價和可互換使用的，但二者涵義存在著細微的差別：共識研究側重于分布式節點達成一致的過程及其算法，而一致性研究則側重于節點共識過程最終達成的穩定狀態;此外，傳統分布式一致性研究大多不考慮拜占庭容錯問題，即假設不存在惡意篡改和偽造數據的拜占庭節點，因此在很長一段時間里，傳統分布式一致性算法的應用場景大多是節點數量有限且相對可信的分布式數據庫環境.與之相比，區塊鏈系統的共識算法則必須運行于更為復雜、開放和缺乏信任的互聯網環境下，節點數量更多且可能存在惡意拜占庭節點.因此，即使Viewstampedreplication(VR)和Paxos等許多分布式一致性算法早在上世紀8O年代就已經提出，但是如何跨越拜占庭容錯這道鴻溝、設計簡便易行的分布式共識算法，仍然是分布式計算領域的難題之一.
2008年10月31日，一位化名為“中本聰”的研究者在密碼學郵件組中發表了比特幣的奠基性論文“Bitcoin：apeer—to—peerelectroniccashsystem”【2J.基于區塊鏈(特別是公有鏈)的共識研究自此拉開序幕.從分布式計算和共識的角度來看，比特幣的根本性貢獻在于首次實現和驗證了一類實用的、互聯網規模的拜占庭容錯算法，從而打開了通往區塊鏈新時代的大門.
一般而言，區塊鏈系統的節點具有分布式、自治性、開放可自由進出等特性，因而大多采用對等式網絡(Peer—to—peernetwork，P2P網絡)來組織散布全球的參與數據驗證和記賬的節點.P2P網絡中的每個節點均地位對等且以扁平式拓撲結構相互連通和交互，不存在任何中心化的特殊節點和層級結構，每個節點均會承擔網絡路由、驗證區塊數據、傳播區塊數據、發現新節點等功能.區塊鏈系統采用特定的經濟激勵機制來保證分布式系統中所有節點均有動機參與數據區塊的生成和驗證過程，按照節點實際完成的工作量分配共識過程所產生的數字加密貨幣，并通過共識算法來選擇特定的節點將新區塊添加到區塊鏈.以比特幣為代表的一系列區塊鏈應用的蓬勃發展，彰顯了區塊鏈技術的重要性與應用價值，區塊鏈系統的共識也成為一個新的研究熱點[引.
迄今為止，研究者已經在共識相關領域做了大量研究工作，不同領域研究者的側重點也各不相同.計算機學科通常稱為共識算法或者共識協議，管理和經濟學科則通常稱為共識機制.細究之下，這些提法存在細微的差異：算法一般是一組順序敏感的指令集且有明確的輸入和輸出;而協議和機制則大多是一組順序不敏感的規則集.就區塊鏈領域而言，本文認為比特幣和以太坊等可認為是底層協議或機制，其詳細規定了系統或平臺內部的節點交互規則、數據路由和轉發規則、區塊構造規則、交易驗證規則、賬本維護規則等集合;而工作量證明(Proof-ofwork，PoW)、權益證明(Proof-of-stake，PoS)等則是建立在特定協議或機制基礎上、可靈活切換的算法，其規定了交易偵聽與打包、構造區塊、記賬人選舉、區塊傳播與驗證、主鏈選擇與更新等若干類順序敏感的指令集合.因此，本文后續敘述均采用共識算法的提法.現有文獻研究的共識問題實際上可以分為算法共識和決策共識兩個分支，前者致力于研究在特定的網絡模型和故障模型前提下，如何在缺乏中央控制和協調的分布式網絡中確保一致性，其實質是一種“機器共識”;后者則更為廣泛地研究無中心的群體決策中，如何就最優的決策達成一致的問題，例如關于比特幣系統擴容【6j問題和分叉問題的社區討論與路線選擇，其實質是“人的共識”.二者的區別在于：前者是機器問的確定性共識，以工程復雜性為主;而后者則是以“人在環路中(Human—inthe—loop)”的復雜系統為特點的不確定性共識，以社會復雜性為主.區塊鏈共識算法研究應屬于算法共識分支的子集，而決策共識則大多見于分布式人工智能、多智能體等研究領域.
拜占庭將軍問題是分布式共識的基礎，也是上述兩個研究分支的根源.拜占庭將軍問題有兩個交互一致性條件，即一致性和正確性.由于大多數情況下，正確性涉及到人的主觀價值判斷，很難施加到分布式節點上，因此算法共識采用的是“降級的正確性(Degradedcorrectness)，即從“表達的內容是正確的”降級為“正確地表達”，這就導致區塊鏈的拜占庭共識實際上是一種機器共識，其本身等價于分布式一致性+正確表達(不篡改消息).與之相對的是，決策共識可以認為是人的共識，不僅要求一致性，而且要求所有節點相信“表達的內容是正確的”，因而決策共識不僅要求內容的客觀一致性，而且還要求其在共識節點間的主觀正確性.由此可見，算法共識處理的是客觀的二值共識，即對(唯一正確的賬本)和錯(所有錯誤的賬本)，而決策共識處理的是主觀的多值共識，即意見1(及其所屬群體)、意見2(及其所屬群體)、…、意見Ⅳ(及其所屬群體)，各節點最終通過群體問的協調和協作過程收斂到唯一意見(共識)，而此過程可能失敗(不收斂).
本文致力于按時間順序梳理和討論區塊鏈發展過程中的共識算法，以期為未來共識算法的創新和區塊鏈技術的發展提供參考.本文的后續章節安排如下：首先，簡要介紹了分布式共識領域重要的里程碑式的研究和結論，包括兩軍問題、拜占庭問題和FLP不可能定理，并介紹了傳統的分布式一致性算法;然后，提出了區塊鏈共識算法的一種基礎模型和分類方法，并對當前主流的區塊鏈共識算法進行了分析;最后，總結了區塊鏈共識算法的發展和研究趨勢.
1傳統分布式一致性算法
1975年，紐約州立大學石溪分校的阿克云盧(AkkoyunluE.A.)、埃卡納德漢姆(EkanadhamK.)和胡貝爾(HuberR.V.)在論文“Somecon—straintsandtradeofsinthedesignofnetworkcommunications”中首次提出了計算機領域的兩軍問題及其無解性證明【711著名的數據庫專家吉姆.格雷正式將該問題命名為“兩軍問題”-8J.兩軍問題表明，在不可靠的通信鏈路上試圖通過通信達成一致共識是不可能的，這被認為是計算機通信研究中第一個被證明無解的問題.兩軍問題對計算機通信研究產生了重要的影響，互聯網時代最重要的TCP/IP協議中的“三次握手”過程即是為解決兩軍問題不存在理論解而誕生的簡單易行、成本可控的“工程解”.
分布式計算領域的共識問題于1980年由馬歇爾·皮斯(MarshallPease)、羅伯特·肖斯塔克(RobertShostak)和萊斯利·蘭伯特(LeslieLam—port)提出I9j1該問題主要研究在一組可能存在故障節點、通過點對點消息通信的獨立處理器網絡中，非故障節點如何能夠針對特定值達成一致共識.1982年，作者在另一篇文章中正式將該問題命名為“拜占庭將軍問題”【10_，提出了基于口頭消息和基于簽名消息的兩種算法來解決該問題.拜占庭假設是對現實世界的模型化，強調的是由于硬件錯誤、網絡擁塞或斷開以及遭到惡意攻擊，計算機和網絡可能出現的不可預料的行為.此后，分布式共識算法可以分為兩類，即拜占庭容錯和非拜占庭容錯類共識.早期共識算法一般為非拜占庭容錯算法，例如廣泛應用于分布式數據庫的VR和Paxos，目前主要應用于聯盟鏈和私有鏈;2008年末，比特幣等公有鏈誕生后，拜占庭容錯類共識算法才逐漸獲得實際應用.需要說明的是，拜占庭將軍問題是區塊鏈技術核心思想的根源，直接影響著區塊鏈系統共識算法的設計和實現，因而在區塊鏈技術體系中具有重要意義.
1985年，邁克爾·費合爾(MichaelFisher)、南希·林奇(NancyLynch)和邁克爾·帕特森(MichaelPaterson)共同發表了論文“Impossibil—ityofdistributedconsensuswithonefaultypro—cess”[11J.這篇文章證明：在含有多個確定性進程的異步系統中，只要有一個進程可能發生故障，那么就不存在協議能保證有限時間內使所有進程達成一致.按照作者姓氏的首字母，該定理被命名為FLP不可能定理，是分布式系統領域的經典結論之一，并由此獲得了Dijkstra獎.FLP不可能定理同樣指出了存在故障進程的異步系統的共識問題不存在有限時間的理論解，因而必須尋找其可行的“工程解”.為此，研究者們只能通過調整問題模型來規避FLP不可能定理，例如犧牲確定性、增加時間等;加密貨幣則是通過設定網絡同步性(或弱同步性)和時間假設來規避FLP不可能性，例如網絡節點可以快速同步，且礦工在最優鏈上投入有限時問和資源等.
早期的共識算法一般也稱為分布式一致算法.與目前主流的區塊鏈共識算法相比，分布式一致性算法主要面向分布式數據庫操作、且大多不考慮拜占庭容錯問題，即假設系統節點只發生宕機和網絡故障等非人為問題，而不考慮惡意節點篡改數據等問題.1988年，麻省理工學院的布萊恩·奧奇(BrianM.Oki)和芭芭拉·里斯科夫(BarbaraH.Liskov，著名計算機專家、2008年圖靈獎得主)提出了VR一致性算法，采用主機備份(Primary—backup)模式，規定所有數據操作都必須通過主機進行，然后復制到各備份機器以保證一致性【J.1989年，萊斯利·蘭伯特fLeslieLamport)在工作論文“Thepart—timeparliament”中提出Paxos算法，由于文章采用了講故事的敘事風格且內容過于艱深晦澀，直到1998年才通過評審、發表在ACMtransac—tionsoncomputersystems期刊上.Paxos是基于消息傳遞的一致性算法，主要解決分布式系統如何就某個特定值達成一致的問題.隨著分布式共識研究的深人，Paxos算法獲得了學術界和工業界的廣泛認可，并衍生出Abstractpaxos、Classicpaxos、Byzantinepaxos和Diskpaxos等變種算法，成為解決異步系統共識問題最重要的算法家族【MJ.實際上，Liskove等提出的VR算法本質上也是一類Paxos算法.需要說明的是，VR和Paxos算法均假設系統中不存在拜占庭故障節點，因而是非拜占庭容錯的共識算法.除以上共識算法外，獲得較多研究關注的早期共識算法還有兩階段提交(Two—phasecommit)算法、三階段提交(Three—phasecommit)算法、Zab、Zyzzyva、Kafka等，本文限于篇幅不加詳述.
2主流區塊鏈共識算法
1993年，美國計算機科學家、哈佛大學教授辛西婭·德沃克(CynthiaDwork)首次提出了工作量證明思想_15J，用來解決垃圾郵件問題.該機制要求郵件發送者必須算出某個數學難題的答案來證明其確實執行了一定程度的計算工作，從而提高垃圾郵件發送者的成本.1997年，英國密碼學家亞當·伯克(AdamBack)也獨立地提出、并于2002年正式發表了用于哈希現金(Hashcash)的工作量證明機制l16j.哈希現金也是致力于解決垃圾郵件問題，其數學難題是尋找包含郵件接受者地址和當前日期在內的特定數據的SHA一1哈希值，使其至少包含20個前導零.1999年，馬庫斯·雅各布松(MarkusJakobsson)正式提出了“工作量證明”概念-17_.這些工作為后來中本聰設計比特幣的共識機制奠定了基礎.
1999年，BarbaraLiskov等提出了實用拜占庭容錯算法(PracticalByzantinefaulttolerance，PBFT)[18]，解決了原始拜占庭容錯算法效率不高的問題，將算法復雜度由指數級降低到多項式級，使得拜占庭容錯算法在實際系統應用中變得可行.PBFT實際上是Paxos算法的變種，通過改進Paxos算法使其可以處理拜占庭錯誤，因而也稱為Byzantinepaxos算法，可以在保證活性(Live—ness)和安全性(Safety)的前提下提供(n一1)/3的容錯性，其中n為節點總數.
2000年，加利福尼亞大學的埃里克·布魯爾(EricBrewer)教授在ACMSymposiumonPrin—ciplesofDistributedComputing研討會的特邀報告中提出了一個猜想：分布式系統無法同時滿足一致性(Consistency)、可用性(Availability)和分區容錯性(Partitiontolerance)，最多只能同時滿足其中兩個.其中，一致性是指分布式系統中的所有數據備份在同一時刻保持同樣的值;可用性是指集群中部分節點出現故障時，集群整體是否還能處理客戶端的更新請求;分區容忍性則是指是否允許數據分區，不同分區的集群節點之問無法互相通信.
2002年，塞斯.吉爾伯特(SethGilbert)和南希·林奇(NancyLynch)在異步網絡模型中證明了這個猜想，使其成為CAP(Consistency，availability，partitiontolerance)定理或布魯爾定理I1.該定理使得分布式網絡研究者不再追求同時滿足三個特性的完美設計，而是不得不在其中做出取合，這也為后來的區塊鏈體系結構設計帶來了影響和限制.
2008年10月，中本聰發表的比特幣創世論文催生了基于區塊鏈的共識算法研究.前文所提到的傳統分布式一致性算法大多應用于相對可信的聯盟鏈和私有鏈，而面向比特幣、以太坊等公有鏈環境則誕生了PoW、PoS等一系列新的拜占庭容錯類共識算法.
比特幣采用了PoW共識算法來保證比特幣網絡分布式記賬的一致性，這也是最早和迄今為止最安全可靠的公有鏈共識算法.PoW的核心思想是通過分布式節點的算力競爭來保證數據的一致性和共識的安全性.比特幣系統的各節點(即礦工)基于各自的計算機算力相互競爭來共同解決一個求解復雜但是驗證容易的SHA256數學難題(即挖礦)，最快解決該難題的節點將獲得下一區塊的記賬權和系統自動生成的比特幣獎勵.PoW共識在比特幣中的應用具有重要意義，其近乎完美地整合了比特幣系統的貨幣發行、流通和市場交換等功能，并保障了系統的安全性和去中心性.然而，PoW共識同時存在著顯著的缺陷，其強大算力造成的資源浪費(主要是電力消耗)歷來為人們所詬病，而且長達l0分鐘的交易確認時問使其相對不適合小額交易的商業應用【3】_
2011年7月，一位名為QuantumMe—chanic的數字貨幣愛好者在比特幣論壇(www.bitcointalk.org)首次提出了權益證明PoS共識算法【2o_.隨后，SunnyKing在2012年8月發布的點點幣(Peercoin，PPC)中首次實現.PoS由系統中具有最高權益而非最高算力的節點獲得記賬權，其中權益體現為節點對特定數量貨幣的所有權，稱為幣齡或幣天數(Coindays).PPC將PoW和PoS兩種共識算法結合起來，初期采用PoW挖礦方式以使得Token相對公平地分配給礦工，后期隨著挖礦難度增加，系統將主要由PoS共識算法維護.PoS一定程度上解決了PoW算力浪費的問題，并能夠縮短達成共識的時間，因而比特幣之后的許多競爭幣都采用PoS共識算法.
2013年2月，以太坊創始人VitalikButerin在比特幣雜志網站詳細地介紹了Ripple(瑞波幣)及其共識過程的思路.Ripple項目實際上早于比特幣，2004年就由瑞安·福格爾(RyanFugger)實現，其初衷是創造一種能夠有效支持個人和社區發行自己貨幣的去中心化貨幣系統;2014年，大衛·施瓦爾茨(DavidSchwartz)等提出了瑞波協議共識算法(RippleProtocolConsensusAlgo—rithm，RPCA)_21_，該共識算法解決了異步網絡節點通訊時的高延遲問題，通過使用集體信任的子網絡(Collectively—trustedsubnetworks)，在只需最小化信任和最小連通性的網絡環境中實現了低延遲、高魯棒性的拜占庭容錯共識算法.目前，Ripple已經發展為基于區塊鏈技術的全球金融結算網絡.
相關期刊推薦：《電腦知識與技術》是由安徽省科技情報學會、中國計算機函授學院主辦的一本融知識、技術、信息于一體的電腦類雜志，是全國的專業IT類旬刊刊物，讀者對象主要為廣大電腦用戶、電腦愛好者和各企事業單位計算機技術人員。創刊以來，一直本著普及電腦知識、推廣電腦技術、交流經驗技巧、促進電腦應用的辦刊宗旨，注重雜志質量。
2013年8月，比特股(Bitshares)項目提出了一種新的共識算法，即授權股份證明算法(Delegatedproof-of-stake，DPoS)[22J.DPoS共識的基本思路類似于“董事會決策”，即系統中每個節點可以將其持有的股份權益作為選票授予一個代表，獲得票數最多且愿意成為代表的前Ⅳ個節點將進入“董事會”，按照既定的時間表輪流對交易進行打包結算、并且簽署(即生產)新區塊L31.如果說PoW和PoS共識分別是“算力為王”和“權益為王”的記賬方式的話，DPoS則可以認為是“民主集中式”的記賬方式，其不僅能夠很好地解決PoW浪費能源和聯合挖礦對系統的去中心化構成威脅的問題，也能夠彌補PoS中擁有記賬權益的參與者未必希望參與記賬的缺點，其設計者認為DPoS是當時最快速、最高效、最去中心化和最靈活的共識算法.
SCISSCIAHCI
