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

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

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

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

迄今為止, 研究者已經(jīng)在共識(shí)相關(guān)領(lǐng)域做了大量研究工作, 不同領(lǐng)域研究者的側(cè)重點(diǎn)也各不相同.計(jì)算機(jī)學(xué)科通常稱為共識(shí)算法或者共識(shí)協(xié)議, 管理和經(jīng)濟(jì)學(xué)科則通常稱為共識(shí)機(jī)制. 細(xì)究之下, 這些提法存在細(xì)微的差異: 算法一般是一組順序敏感的指令集且有明確的輸入和輸出; 而協(xié)議和機(jī)制則大多是一組順序不敏感的規(guī)則集. 就區(qū)塊鏈領(lǐng)域而言,本文認(rèn)為比特幣和以太坊等可認(rèn)為是底層協(xié)議或機(jī)制, 其詳細(xì)規(guī)定了系統(tǒng)或平臺(tái)內(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ù)敘述均采用共識(shí)算法的提法.

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

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

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

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á)成一致共識(shí)是不可能的, 這被認(rèn)為是計(jì)算機(jī)通信研究中第一個(gè)被證明無解的問題. 兩軍問題對(duì)計(jì)算機(jī)通信研究產(chǎn)生了重要的影響, 互聯(lián)網(wǎng)時(shí)代最重要的TCP/IP 協(xié)議中的“ 三次握手" 過程即是為解決兩軍問題不存理論解而誕生的簡(jiǎn)單易行、 成本可控的“ 工程解".

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

早期的共識(shí)算法一般也稱為分布式一致性算法.與目前主流的區(qū)塊鏈共識(shí)算法相比, 分布式一致性算法主要面向分布式數(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 年才通過評(píng)審、 發(fā)表在 ACM transactions on computer systems 期刊上 [13].Paxos 是基于消息傳遞的一致性算法, 主要解決分布式系統(tǒng)如何就某個(gè)特定值達(dá)成一致的問題. 隨著分布式共識(shí)研究的深入,Paxos 算法獲得了學(xué)術(shù)界和工業(yè)界的廣泛認(rèn)可, 并衍生出 Abstract paxos、 Classic paxos、Byzantine paxos 和 Disk paxos 等變種算法,成為解決異步系統(tǒng)共識(shí)問題最重要的算法家族 [14].實(shí)際上,Liskove 等提出的 VR 算法本質(zhì)上也是一類Paxos 算法. 需要說明的是,VR 和 Paxos 算法均假設(shè)系統(tǒng)中不存在拜占庭故障節(jié)點(diǎn), 因而是非拜占庭容錯(cuò)的共識(shí)算法. 除以上共識(shí)算法外, 獲得較多研究關(guān)注的早期共識(shí)算法還有兩階段提交 (Two-phase commit) 算法、 三階段提交 (Three-phase commit)算法、 Zab、 Zyzzyva、Kafka 等, 本文限于篇幅不加詳述.

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

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

1999 年,Barbara Liskov 等提出了實(shí)用拜占庭容錯(cuò)算法 (Practical Byzantine fault tolerance,PBFT)[18], 解決了原始拜占庭容錯(cuò)算法效率不高的問題, 將算法復(fù)雜度由指數(shù)級(jí)降低到多項(xiàng)式級(jí), 使得拜占庭容錯(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 研討會(huì)的特邀報(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ǐng)求; 分區(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ū)塊鏈的共識(shí)算法研究. 前文所提到的傳統(tǒng)分布式一致性算法大多應(yīng)用于相對(duì)可信的聯(lián)盟鏈和私有鏈, 而面向比特幣、 以太坊等公有鏈環(huán)境則誕生了 PoW、 PoS 等一系列新的拜占庭容錯(cuò)類共識(shí)算法.

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

2011 年 7 月, 一 位 名 為 Quantum Mechanic 的 數(shù) 字 貨 幣 愛 好 者 在 比 特幣 論 壇(www.bitcointalk.org) 首次提出了權(quán)益證明 PoS共識(shí)算法 [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)對(duì)特定數(shù)量貨幣的所有權(quán), 稱為幣齡或幣天數(shù) (Coin days).PPC 將PoW 和 PoS兩種共識(shí)算法結(jié)合起來, 初期采用 PoW 挖礦方式以使得 Token 相對(duì)公平地分配給礦工, 后期隨著挖礦難度增加, 系統(tǒng)將主要由 PoS 共識(shí)算法維護(hù).PoS 一定程度上解決了 PoW 算力浪費(fèi)的問題, 并能夠縮短達(dá)成共識(shí)的時(shí)間, 因而比特幣之后的許多競(jìng)爭(zhēng)幣都采用 PoS 共識(shí)算法.

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

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

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

3 共識(shí)算法的模型與分類

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

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

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

第一階段: 選主. 選主是共識(shí)過程的核心, 即從全體礦工節(jié)點(diǎn)集 M 中選出記賬節(jié)點(diǎn) A 的過程:我們可以使用公式 f(M)! A 來表示選主過程, 其中函數(shù) f 代表共識(shí)算法的具體實(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ū)塊的完整的、 更長(zhǎng)的鏈條. 如果主鏈存在多個(gè)分叉鏈, 則需根據(jù)共識(shí)算法規(guī)定的主鏈判別標(biāo)準(zhǔn), 來選擇其中一條恰當(dāng)?shù)姆种ё鳛橹麈?

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

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

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

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

自 2014 年起, 隨著比特幣和區(qū)塊鏈技術(shù)快速進(jìn)入公眾視野, 許多學(xué)者開始關(guān)注并研究區(qū)塊鏈技術(shù),共識(shí)算法也因此進(jìn)入快速發(fā)展、 百花齊放的時(shí)期. 許多新共識(shí)算法在這段時(shí)間被提出. 它們或者是原有算法的簡(jiǎn)單變種, 或者是為改進(jìn)某一方面性能而做出的微創(chuàng)新, 或者是為適應(yīng)新場(chǎng)景和新需求而做出重大改進(jìn)的新算法. 需要說明的是, 這些共識(shí)算法由于提出時(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]、 行動(dòng)證明(Proof of Activity, PoA)[27] 和二跳 (2-hop)[28]共識(shí)算法, 致力于取長(zhǎng)補(bǔ)短、 解決 PoW 與 PoS 存在的能源消耗與安全風(fēng)險(xiǎn)問題.2014 年 4 月, 拉里· 雷恩 (Larry Ren) 在蝸牛幣 Reddcoin 白皮書中提出了 PoSV 共識(shí)算法, 針對(duì) PoS 中幣齡是時(shí)間的線性函數(shù)這一問題進(jìn)行改進(jìn), 致力于消除持幣人的屯幣現(xiàn)象.PoSV 算法前期使用 PoW 實(shí)現(xiàn)代幣分配,后期使用 PoSV 維護(hù)網(wǎng)絡(luò)長(zhǎng)期安全.PoSV 將 PoS中幣齡和時(shí)間的線性函數(shù)修改為指數(shù)式衰減函數(shù),即幣齡的增長(zhǎng)率隨時(shí)間減少最后趨于零. 因此新幣的幣齡比老幣增長(zhǎng)地更快, 直到達(dá)到上限閾值, 這在一定程度上緩和了持幣者的屯幣現(xiàn)象.2014 年 5月發(fā)行的 Slimcoin 借鑒了比特幣和點(diǎn)點(diǎn)幣的設(shè)計(jì),基于 PoW 和 PoS 首創(chuàng)提出了 PoB 共識(shí)算法. 其中,PoW 共識(shí)被用來產(chǎn)生初始的代幣供應(yīng), 隨著時(shí)間增長(zhǎng), 區(qū)塊鏈網(wǎng)絡(luò)累積了足夠的代幣時(shí), 系統(tǒng)將依賴 PoB 和 PoS 共識(shí)來共同維護(hù).PoB 共識(shí)的特色是礦工通過將其持有的 Slimcoin 發(fā)送至特定的無法找回的地址 (燃燒) 來競(jìng)爭(zhēng)新區(qū)塊的記賬權(quán), 燃燒的幣越多則挖到新區(qū)塊的概率越高.2014 年 12 月提出的 PoA 共識(shí)也是基于 PoW 和 PoS, 其中采用 PoW挖出的部分代幣以抽獎(jiǎng)的方式分發(fā)給所有活躍節(jié)點(diǎn),而節(jié)點(diǎn)擁有的權(quán)益與抽獎(jiǎng)券的數(shù)量即抽中概率成正比. 二跳共識(shí)于 2017 年 4 月提出, 其設(shè)計(jì)初衷是為解決 PoW 潛在的 51% 算力攻擊問題, 解決思路是在 PoW 算力的基礎(chǔ)上引入 PoS 權(quán)益, 使得區(qū)塊鏈安全建立在誠(chéng)實(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 共 識(shí) 算 法 的 改 進(jìn) 目 標(biāo) 主 要是 解 決 其 固 有 的 “ 無 利 害 關(guān) 系 (Nothing at stake)" 問 題, 形 成 了 Tendermint[29] 以 及 由 其衍生出的Casper[30]、 Ouroboros[31]、 Tezos[32] 和Honeybadger[33] 等新共識(shí)算法. 原生 PoS 共識(shí)一般假設(shè)系統(tǒng)中的對(duì)等節(jié)點(diǎn)都是靜態(tài)和長(zhǎng)期穩(wěn)定的,這在區(qū)塊鏈環(huán)境中并不現(xiàn)實(shí). 2014 年提出的 Tendermint 的重大突破是使用區(qū)塊、 哈希鏈接、 動(dòng)態(tài)驗(yàn)證器集合和循環(huán)的領(lǐng)導(dǎo)者選舉, 實(shí)現(xiàn)了第一個(gè)基于PBFT 的 PoS 共識(shí)算法. 為解決無利害關(guān)系問題,Tendermint 節(jié)點(diǎn)需要繳納保證金, 如果作惡則保證金就會(huì)被沒收. Tendermint 是一種拜占庭容錯(cuò)的共識(shí)算法, 具有抵御雙花攻擊的魯棒性, 并且可以抵御網(wǎng)絡(luò)中至多三分之一的破壞者的攻擊.

2015 年提出的 Casper 是以太坊計(jì)劃在其路線圖中稱為寧靜 (Serenity) 的第四階段采用的共識(shí)算法, 尚在設(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 共識(shí), 而后者則是PoW 和 PoS 共識(shí)的有機(jī)結(jié)合. 同時(shí),PoS 共識(shí)的兩個(gè)主要原理分別是基于鏈的 PoS 和基于拜占庭容錯(cuò)的 PoS.Tendermint 是基于拜占庭容錯(cuò)的 PoS設(shè)計(jì). 相比之下,CTFG 是基于鏈的 PoS 設(shè)計(jì), 而CFFG 則是兩者的結(jié)合.

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

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

原生 PoW 共識(shí)算法的改進(jìn)目標(biāo)主要是實(shí)現(xiàn)比特幣擴(kuò)容或者降低其能耗.2016 年 3 月, 康奈爾大學(xué)的 Ittay Eyal 等提出一種新的共識(shí)算法 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 共識(shí)算法生成, 然后領(lǐng)導(dǎo)者被允許小于預(yù)設(shè)閾值的速率 (例如 10 秒) 來生成微區(qū)塊.BitcoinNG 可在不改變區(qū)塊容量的基礎(chǔ)上通過選舉領(lǐng)導(dǎo)者生成更多的區(qū)塊, 從而可輔助解決比特幣的擴(kuò)容問題. 同年 8 月提出的 ByzCoin[37] 共識(shí)算法借鑒了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] 共識(shí)機(jī)制通過分片技術(shù)來增強(qiáng)區(qū)塊鏈的擴(kuò)展性, 其思路是將挖礦網(wǎng)絡(luò)以可證明安全的方式隔離為多個(gè)分片 (Shard), 這些分片并行地處理互不相交的交易集合.Elastico 是第一個(gè)拜占庭容錯(cuò)的安全分片協(xié)議.2017 年,OmniLedger[39] 進(jìn)一步借鑒 ByzCoin 和 Elastico 共識(shí), 設(shè)計(jì)并提出名為ByzCoinX 的拜占庭容錯(cuò)協(xié)議.OmniLedger 通過并行跨分片交易處理優(yōu)化區(qū)塊鏈性能, 是第一種能夠提供水平擴(kuò)展性而不必犧牲長(zhǎng)期安全性和去中心性的分布式賬本架構(gòu).

為改進(jìn) PoW 共識(shí)算法的效率 (能耗) 和公平性, 研 究 者 相 繼 提 出 了 消 逝時(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ī)共識(shí)算法.PoET 是超級(jí)賬本 HyperLedger 的鋸齒湖 Sawtooth 項(xiàng)目采用的共識(shí)算法, 其基本思路是每個(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 共識(shí)的意義在于使得區(qū)塊鏈系統(tǒng)不必消耗昂貴算力來挖礦、 從而提高了效率, 同時(shí)也真正實(shí)現(xiàn)了“ 一 CPU 一票" 的公平性. 類似地,PoL 共識(shí)也采用 TEE 平臺(tái)的隨機(jī)數(shù)生成器來選擇每一輪共識(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 的能耗問題而提出的共識(shí)算法.PoSp 共識(shí)要求礦工必須出具一定數(shù)量的磁盤空間 (而非算力) 來挖礦, 而PoUW 則將 PoW 共識(shí)中毫無意義的 SHA256 哈希運(yùn)算轉(zhuǎn)變?yōu)閷?shí)際場(chǎng)景中既困難又有價(jià)值的運(yùn)算, 例如計(jì)算正交向量問題、 3SUM 問題、 最短路徑問題等.

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

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

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

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

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

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

5 總結(jié)與展望

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

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

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

其次, 區(qū)塊鏈的共識(shí)算法與激勵(lì)機(jī)制是緊密耦合、 不可分割的整體, 同時(shí)二者互有側(cè)重點(diǎn): 共識(shí)算法規(guī)定了礦工為維護(hù)區(qū)塊鏈賬本安全性、 一致性和活性而必須遵守的行為規(guī)范和行動(dòng)次序; 激勵(lì)機(jī)制則規(guī)定了在共識(shí)過程中為鼓勵(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] 的話, 那么共識(shí)算法將決定其博弈樹的結(jié)構(gòu)和形狀、 激勵(lì)機(jī)制將決定礦工和礦池在博弈樹中每個(gè)葉子結(jié)點(diǎn)的收益.因此, 區(qū)塊鏈共識(shí)算法和激勵(lì)機(jī)制不僅各自存在獨(dú)立優(yōu)化的必要性, 更為重要地是共識(shí) - 激勵(lì)二元耦合機(jī)制的聯(lián)合優(yōu)化、 實(shí)現(xiàn)共識(shí)與激勵(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)支付場(chǎng)景的數(shù)字貨幣IOTA 即采用稱為“ Tangle (纏結(jié))" 的 DAG 拓?fù)浣Y(jié)構(gòu), 其共識(shí)過程以交易 (而非區(qū)塊) 為粒度, 每個(gè)交易都引證其他兩個(gè)交易的合法性、 形成 DAG 網(wǎng)絡(luò),因而可以實(shí)現(xiàn)無區(qū)塊 (Blockless) 共識(shí)；HashGraph共識(shí)則更進(jìn)一步, 基于 Gossip of gossip 協(xié)議和虛擬投票等技術(shù), 以交易為粒度, 在特定的 DAG 結(jié)構(gòu)上實(shí)現(xiàn)公平和快速的拜占庭容錯(cuò)共識(shí). 這些新型區(qū)塊拓?fù)浣Y(jié)構(gòu)及其共識(shí)算法是未來發(fā)展趨勢(shì)之一, 建立在這些新型數(shù)據(jù)結(jié)構(gòu)之上的共識(shí)算法也值得深入研究.

未來智能實(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)智商評(píng)測(cè)體系，開展世界人工智能智商評(píng)測(cè)；開展互聯(lián)網(wǎng)（城市）云腦研究計(jì)劃，構(gòu)建互聯(lián)網(wǎng)（城市）云腦技術(shù)和企業(yè)圖譜，為提升企業(yè)，行業(yè)與城市的智能水平服務(wù)。

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

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

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