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

共識問題是社會科學(xué)和計(jì)算機(jī)科學(xué)等領(lǐng)域的經(jīng)典問題, 已經(jīng)有很長的研究歷史. 目前有記載的文獻(xiàn)至少可以追溯到 1959 年, 蘭德公司和布朗大學(xué)的埃德蒙· 艾森伯格 (Edmund Eisenberg) 和大衛(wèi)· 蓋爾 (David Gale) 發(fā)表的“Consensus of subjective probabilities: the Pari-Mutuel method", 主要研究針對某個(gè)特定的概率空間, 一組個(gè)體各自有其主觀的概率分布時(shí), 如何形成一個(gè)共識概率分布的問題[1]. 隨后, 共識問題逐漸引起了社會學(xué)、 管理學(xué)、 經(jīng)濟(jì)學(xué)、 特別是計(jì)算機(jī)科學(xué)等各學(xué)科領(lǐng)域的廣泛研究興趣.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1999 年,Barbara Liskov 等提出了實(shí)用拜占庭容錯(cuò)算法 (Practical Byzantine fault tolerance,PBFT)[18], 解決了原始拜占庭容錯(cuò)算法效率不高的問題, 將算法復(fù)雜度由指數(shù)級降低到多項(xiàng)式級, 使得拜占庭容錯(cuò)算法在實(shí)際系統(tǒng)應(yīng)用中變得可行.PBFT實(shí)際上是 Paxos 算法的變種, 通過改進(jìn) Paxos 算法使其可以處理拜占庭錯(cuò)誤, 因而也稱為 Byzantine paxos 算法, 可以在保證活性(Liveness) 和安全性(Safety) 的前提下提供 (n-1)/3 的容錯(cuò)性, 其中 n 為節(jié)點(diǎn)總數(shù).

2000 年, 加利福尼亞大學(xué)的埃里克· 布魯爾(Eric Brewer) 教授在 ACM symposium on principles of distributed computing 研討會的特邀報(bào)告中提出了一個(gè)猜想: 分布式系統(tǒng)無法同時(shí)滿足一致性 (Consistency)、 可用性(Availability) 和分區(qū)容錯(cuò)性 (Partition tolerance), 最多只能同時(shí)滿足其中兩個(gè). 其中, 一致性是指分布式系統(tǒng)中的所有數(shù)據(jù)備份在同一時(shí)刻保持同樣的值; 可用性是指集群中部分節(jié)點(diǎn)出現(xiàn)故障時(shí), 集群整體是否還能處理客戶端的更新請求; 分區(qū)容忍性則是指是否允許數(shù)據(jù)分區(qū),不同分區(qū)的集群節(jié)點(diǎn)之間無法互相通信.2002 年, 塞斯· 吉爾伯特 (Seth Gilbert) 和南希· 林奇 (Nancy Lynch) 在異步網(wǎng)絡(luò)模型中證明了這個(gè)猜想, 使其成為 CAP 定理或布魯爾定理 [19]. 該定理使得分布式網(wǎng)絡(luò)研究者不再追求同時(shí)滿足三個(gè)特性的完美設(shè)計(jì),而是不得不在其中做出取舍, 這也為后來的區(qū)塊鏈體系結(jié)構(gòu)設(shè)計(jì)帶來了影響和限制.

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

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

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

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

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

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

3 共識算法的模型與分類

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

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

共識過程的核心是“ 選主" 和“ 記賬" 兩部分, 在具體操作過程中每一輪可以分為選主 (Leader election)、 造塊 (Block generation)、 驗(yàn)證 (Data validation) 和上鏈 (Chain updation, 即記賬) 四個(gè)階段.如圖 1 所示, 共識過程的輸入是數(shù)據(jù)節(jié)點(diǎn)生成和驗(yàn)證后的交易或數(shù)據(jù), 輸出則是封裝好的數(shù)據(jù)區(qū)塊以及更新后的區(qū)塊鏈. 四個(gè)階段循環(huán)往復(fù)執(zhí)行, 每執(zhí)行一輪將會生成一個(gè)新區(qū)塊.

第一階段: 選主. 選主是共識過程的核心, 即從全體礦工節(jié)點(diǎn)集 M 中選出記賬節(jié)點(diǎn) A 的過程:我們可以使用公式 f(M)! A 來表示選主過程, 其中函數(shù) f 代表共識算法的具體實(shí)現(xiàn)方式. 一般來說,jAj=1, 即最終選擇唯一的礦工節(jié)點(diǎn)來記賬.

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

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

第四階段: 上鏈. 記賬節(jié)點(diǎn)將新區(qū)塊添加到主鏈, 形成一條從創(chuàng)世區(qū)塊到最新區(qū)塊的完整的、 更長的鏈條. 如果主鏈存在多個(gè)分叉鏈, 則需根據(jù)共識算法規(guī)定的主鏈判別標(biāo)準(zhǔn), 來選擇其中一條恰當(dāng)?shù)姆种ё鳛橹麈?

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

選舉類共識: 即礦工節(jié)點(diǎn)在每一輪共識過程中通過“ 投票選舉" 的方式選出當(dāng)前輪次的記賬節(jié)點(diǎn),首先獲得半數(shù)以上選票的礦工節(jié)點(diǎn)將會獲得記賬權(quán)；多見于傳統(tǒng)分布式一致性算法, 例如 Paxos 和 Raft等. 證明類共識: 也可稱為“ Proof of X" 類共識,即礦工節(jié)點(diǎn)在每一輪共識過程中必須證明自己具有某種特定的能力, 證明方式通常是競爭性地完成某項(xiàng)難以解決但易于驗(yàn)證的任務(wù), 在競爭中勝出的礦工節(jié)點(diǎn)將獲得記賬權(quán)；例如 PoW 和 PoS 等共識算法是基于礦工的算力或者權(quán)益來完成隨機(jī)數(shù)搜索任務(wù), 以此競爭記賬權(quán). 隨機(jī)類共識: 即礦工節(jié)點(diǎn)根據(jù)某種隨機(jī)方式直接確定每一輪的記賬節(jié)點(diǎn), 例如下文將要提到的Algorand 和 PoET 共識算法等.聯(lián)盟類共識: 即礦工節(jié)點(diǎn)基于某種特定方式首先選舉出一組代表節(jié)點(diǎn), 而后由代表節(jié)點(diǎn)以輪流或者選舉的方式依次取得記賬權(quán). 這是一種以“ 代議制" 為特點(diǎn)的共識算法, 例如 DPoS 等.

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

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

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

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

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

4.2 主線二: 原生 PoS 算法的改進(jìn)

原 生 PoS 共 識 算 法 的 改 進(jìn) 目 標(biāo) 主 要是 解 決 其 固 有 的 “ 無 利 害 關(guān) 系 (Nothing at stake)" 問 題, 形 成 了 Tendermint[29] 以 及 由 其衍生出的Casper[30]、 Ouroboros[31]、 Tezos[32] 和Honeybadger[33] 等新共識算法. 原生 PoS 共識一般假設(shè)系統(tǒng)中的對等節(jié)點(diǎn)都是靜態(tài)和長期穩(wěn)定的,這在區(qū)塊鏈環(huán)境中并不現(xiàn)實(shí). 2014 年提出的 Tendermint 的重大突破是使用區(qū)塊、 哈希鏈接、 動態(tài)驗(yàn)證器集合和循環(huán)的領(lǐng)導(dǎo)者選舉, 實(shí)現(xiàn)了第一個(gè)基于PBFT 的 PoS 共識算法. 為解決無利害關(guān)系問題,Tendermint 節(jié)點(diǎn)需要繳納保證金, 如果作惡則保證金就會被沒收. Tendermint 是一種拜占庭容錯(cuò)的共識算法, 具有抵御雙花攻擊的魯棒性, 并且可以抵御網(wǎng)絡(luò)中至多三分之一的破壞者的攻擊.

2015 年提出的 Casper 是以太坊計(jì)劃在其路線圖中稱為寧靜 (Serenity) 的第四階段采用的共識算法, 尚在設(shè)計(jì)、 討論和完善階段. 目前 Casper 總共有兩個(gè)版本, 即由 Vlad Zamjir 領(lǐng)導(dǎo)的 Casper the Friendly Ghost (CTFG)[34] 和由 Vitalik Buterin 帶領(lǐng)實(shí)現(xiàn)的 Casper Friendly Finality Gadget(CFFG)[35]. 前者是明確的 PoS 共識, 而后者則是PoW 和 PoS 共識的有機(jī)結(jié)合. 同時(shí),PoS 共識的兩個(gè)主要原理分別是基于鏈的 PoS 和基于拜占庭容錯(cuò)的 PoS.Tendermint 是基于拜占庭容錯(cuò)的 PoS設(shè)計(jì). 相比之下,CTFG 是基于鏈的 PoS 設(shè)計(jì), 而CFFG 則是兩者的結(jié)合.

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

4.3 主線三: 原生 PoW 共識算法的改進(jìn)

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

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

2014 年 提 出 的 空 間 證 明 (Proof of Space, PoSp)[42] 和 2017 年提出的有益工作證明 (Proof of Useful Work, PoUW)[43] 也是為解決 PoW 的能耗問題而提出的共識算法.PoSp 共識要求礦工必須出具一定數(shù)量的磁盤空間 (而非算力) 來挖礦, 而PoUW 則將 PoW 共識中毫無意義的 SHA256 哈希運(yùn)算轉(zhuǎn)變?yōu)閷?shí)際場景中既困難又有價(jià)值的運(yùn)算, 例如計(jì)算正交向量問題、 3SUM 問題、 最短路徑問題等.

4.4 主線四: 傳統(tǒng)分布式一致性算法的改進(jìn)及其它

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

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

2016 年, 圖靈獎(jiǎng)得主、 MIT 教授 Sivio Micali提出了一種稱為 AlgoRand[47] 的快速拜占庭容錯(cuò)共識算法. 該算法利用密碼抽簽技術(shù)選擇共識過程的驗(yàn)證者和領(lǐng)導(dǎo)者, 并通過其設(shè)計(jì)的 BA* 拜占庭容錯(cuò)協(xié)議對新區(qū)塊達(dá)成共識. AlgoRand 只需極小計(jì)算量且極少分叉, 被認(rèn)為是真正民主和高效的分布式賬本共識技術(shù).

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

綜上所述, 區(qū)塊鏈共識算法的演進(jìn)歷史如圖 2所示, 表 1 則給出了每一種共識算法的提出時(shí)間、 拜占庭容錯(cuò)性能、 基礎(chǔ)算法以及具有代表性的應(yīng)用系統(tǒng)或平臺.

5 總結(jié)與展望

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

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

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

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

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

未來智能實(shí)驗(yàn)室是人工智能學(xué)家與科學(xué)院相關(guān)機(jī)構(gòu)聯(lián)合成立的人工智能，互聯(lián)網(wǎng)和腦科學(xué)交叉研究機(jī)構(gòu)。

未來智能實(shí)驗(yàn)室的主要工作包括：建立AI智能系統(tǒng)智商評測體系，開展世界人工智能智商評測；開展互聯(lián)網(wǎng)（城市）云腦研究計(jì)劃，構(gòu)建互聯(lián)網(wǎng)（城市）云腦技術(shù)和企業(yè)圖譜，為提升企業(yè)，行業(yè)與城市的智能水平服務(wù)。

如果您對實(shí)驗(yàn)室的研究感興趣，歡迎加入未來智能實(shí)驗(yàn)室線上平臺。掃描以下二維碼或點(diǎn)擊本文左下角“閱讀原文”

原文標(biāo)題：區(qū)塊鏈共識算法的發(fā)展現(xiàn)狀與展望

文章出處：【微信公眾號：人工智能學(xué)家】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。