“區(qū)塊鏈（Blockchain）技術(shù)是一種多方維護(hù)，通過密碼學(xué)保證傳輸和安全，實(shí)現(xiàn)一致、難以篡改、防止抵賴的記賬技術(shù)，稱為分布式賬本技術(shù)。而區(qū)塊鏈技術(shù)框架中非常重要的一部分是共識(shí)機(jī)制，是在不可信的分布式環(huán)境下實(shí)現(xiàn)數(shù)據(jù)一致性的關(guān)鍵?！?/span>

本文詳細(xì)解析了PoW、PoS、PBFT…等主流共識(shí)機(jī)制各自特點(diǎn)及優(yōu)劣；也從單一共識(shí)向可插拔共識(shí)、從鏈?zhǔn)焦沧R(shí)向圖式共識(shí)、從確定性共識(shí)向隨機(jī)性共識(shí)，歸納總結(jié)出了共識(shí)機(jī)制的發(fā)展趨勢(shì)。

概述

1.1 區(qū)塊鏈技術(shù)

2008年11月1日，中本聰發(fā)表了《比特幣：一種點(diǎn)對(duì)點(diǎn)的電子現(xiàn)金系統(tǒng)》［1］一文，闡述了基于P2P網(wǎng)絡(luò)技術(shù)、加密技術(shù)、時(shí)間戳技術(shù)、區(qū)塊鏈技術(shù)等的電子現(xiàn)金系統(tǒng)的構(gòu)架理念，標(biāo)志著比特幣的誕生。2009年初，中本聰搭建了以其論文為原型的網(wǎng)絡(luò)——比特幣。區(qū)塊鏈技術(shù)是比特幣網(wǎng)絡(luò)背后的技術(shù)基礎(chǔ)，是一種基礎(chǔ)設(shè)施。區(qū)塊鏈作為一種解決不可信分布式環(huán)境下能夠以較低成本建立信任的計(jì)算模式和協(xié)作模式，正在悄然改變這個(gè)世界。

1.2 共識(shí)機(jī)制

由于區(qū)塊鏈系統(tǒng)多數(shù)采用去中心化的分布式設(shè)計(jì)，節(jié)點(diǎn)是分散在各處，所以必須設(shè)計(jì)一套完善的制度，以維護(hù)系統(tǒng)的運(yùn)作順序與公平性，統(tǒng)一區(qū)塊鏈的版本，并獎(jiǎng)勵(lì)提供資源維護(hù)區(qū)塊鏈的使用者，以及懲罰惡意的危害者。這樣的制度，必須依賴某種方式來證明，是由誰(shuí)取得了一個(gè)區(qū)塊鏈的打包權(quán)（或稱記帳權(quán)），并且可以獲取打包這一個(gè)區(qū)塊的獎(jiǎng)勵(lì)；又或者是誰(shuí)意圖進(jìn)行危害，就會(huì)獲得一定的懲罰，這就是區(qū)塊鏈系統(tǒng)的共識(shí)機(jī)制［2］。

區(qū)塊鏈?zhǔn)且粋€(gè)去中心化的分布式系統(tǒng)，在該系統(tǒng)中，所有的節(jié)點(diǎn)都是一個(gè)全副本，維護(hù)著全部的賬本數(shù)據(jù)。這樣，當(dāng)某一個(gè)或多個(gè)節(jié)點(diǎn)故障時(shí)，用戶可以從其他的節(jié)點(diǎn)讀取數(shù)據(jù)。由于系統(tǒng)中有多個(gè)副本，如何保證副本之間的一致性是整個(gè)分布式系統(tǒng)的理論核心，下面會(huì)詳細(xì)地向大家介紹傳統(tǒng)分布式系統(tǒng)和區(qū)塊鏈系統(tǒng)副本一致性問題。

傳統(tǒng)分布式系統(tǒng)一致性問題

2.1 分布式一致性問題

從傳統(tǒng)的集中式單節(jié)點(diǎn)結(jié)構(gòu)，演變到分布式多節(jié)點(diǎn)結(jié)構(gòu)，碰到的首個(gè)問題就是一致性的保障。如何保障副本之間的一致性是整個(gè)分布式系統(tǒng)的理論核心。

一致性是指分布式系統(tǒng)中的多個(gè)服務(wù)節(jié)點(diǎn)，給定一系列的操作，在約定協(xié)議的保障下，使它們對(duì)外界呈現(xiàn)的狀態(tài)是一致的。換句話說，也就是保證集群中所有服務(wù)節(jié)點(diǎn)中的數(shù)據(jù)完全相同并且能夠?qū)δ硞€(gè)提案（Proposal）達(dá)成一致。

一致性的要求，在分布式系統(tǒng)中，系統(tǒng)可以達(dá)成一致性需要滿足以下三個(gè)要求：

有限性：達(dá)成一致的結(jié)果在有限的時(shí)間內(nèi)完成。

約同性：不同節(jié)點(diǎn)最終完成決策的結(jié)果是相同的。

合法性：決策的結(jié)果必須是系統(tǒng)中某個(gè)節(jié)點(diǎn)提出來的。

一般地，非學(xué)術(shù)角度，分布式系統(tǒng)一致性主要包括以下三類：

· 強(qiáng)一致性（Strong）：數(shù)據(jù)a一旦寫入成功，在任意副本任意時(shí)刻都能讀到a的最新值。

· 弱一致性（Weak）：寫入一個(gè)數(shù)據(jù)a成功后，在數(shù)據(jù)副本上可能讀出來，也可能讀不出來。系統(tǒng)不能保證多長(zhǎng)時(shí)間之后每個(gè)副本的數(shù)據(jù)一定達(dá)成一致。

· 最終一致性（Eventually）：最終一致性是弱一致性的一種特例。寫入一個(gè)數(shù)據(jù)a成功后，在其他副本有可能暫時(shí)讀不到a的最新值，但在某個(gè)不一致的時(shí)間窗口之后保證最終能讀到。不一致性窗口的大小依賴于以下幾個(gè)因素：交互延遲、系統(tǒng)負(fù)載、復(fù)制協(xié)議的副本數(shù)。

2000年，Berkeley大學(xué)計(jì)算機(jī)科學(xué)家埃里克·布魯爾提出了著名的CAP定理，指出對(duì)于一個(gè)分布式計(jì)算機(jī)系統(tǒng)，不可能同時(shí)滿足以下三點(diǎn)［3］：

· 一致性（Consistency）：所有節(jié)點(diǎn)訪問同一份最新的數(shù)據(jù)副本，讀操作總是能讀取到之前完成的寫操作結(jié)果，滿足這個(gè)條件的系統(tǒng)就符合我們前面對(duì)強(qiáng)一致性系統(tǒng)的定義。

· 可用性（Availability）：每次請(qǐng)求都能獲取到非錯(cuò)的響應(yīng)，但是不保證獲取的數(shù)據(jù)為最新數(shù)據(jù)，讀寫操作在單臺(tái)機(jī)器發(fā)生故障的情況下仍然能夠正常執(zhí)行，不需要等到故障的節(jié)點(diǎn)將數(shù)據(jù)遷移到新的節(jié)點(diǎn)。

· 分區(qū)容錯(cuò)性（Partition tolerance）：以實(shí)際效果而言，分區(qū)相當(dāng)于對(duì)通信的時(shí)限要求。系統(tǒng)如果不能在時(shí)限內(nèi)達(dá)成數(shù)據(jù)一致性，就意味著發(fā)生了分區(qū)的情況，必須就當(dāng)前操作在C和A之間做出選擇。

根據(jù)定理，分布式系統(tǒng)只能滿足三項(xiàng)中的兩項(xiàng)而不可能滿足全部三項(xiàng)。理解CAP理論的最簡(jiǎn)單方式是想象兩個(gè)節(jié)點(diǎn)分處分區(qū)兩側(cè)。允許至少一個(gè)節(jié)點(diǎn)更新狀態(tài)會(huì)導(dǎo)致數(shù)據(jù)不一致，即喪失了C性質(zhì)。如果為了保證數(shù)據(jù)一致性，將分區(qū)一側(cè)的節(jié)點(diǎn)設(shè)置為不可用，那么又喪失了A性質(zhì)。除非兩個(gè)節(jié)點(diǎn)可以互相通信，才能既保證C又保證A，這又會(huì)導(dǎo)致喪失P性質(zhì)。

隨著系統(tǒng)規(guī)模逐漸變大，故障的發(fā)生會(huì)是一種常態(tài)，系統(tǒng)的設(shè)計(jì)必須要考慮容錯(cuò)（Fault Tolerant）。依據(jù)分布式系統(tǒng)的部署環(huán)境，容錯(cuò)主要包括兩大類：一是可信環(huán)境下的分布式容錯(cuò)，即我們通常說的CFT（Crash Fault Tolerant）；二是不可信環(huán)境下的分布式容錯(cuò)，即我們通常說的BFT（Byzantine Fault Tolerant）。下面兩節(jié)會(huì)詳細(xì)向大家介紹一下兩類環(huán)境下的分布式一致性問題和容錯(cuò)方案。

2.2 可信環(huán)境分布式一致性問題

傳統(tǒng)的分布式系統(tǒng)中，所有服務(wù)器掌握在一個(gè)公司或者組織內(nèi)部，系統(tǒng)沒有惡意節(jié)點(diǎn)，所有節(jié)點(diǎn)都是可信的，這樣的分布式系統(tǒng)我們稱之為可信環(huán)境分布式系統(tǒng)TEDS（Trusted Environment Distributed System）。

可信環(huán)境分布式系統(tǒng)容錯(cuò)即CFT，該類系統(tǒng)中，只需要考慮單機(jī)故障、磁盤故障等故障恢復(fù)場(chǎng)景。

可信環(huán)境分布式系統(tǒng)的一致性協(xié)議有很多，比較著名的包括兩階段提交協(xié)議、Paxos協(xié)議和Raft協(xié)議。

2.2.1 兩階段提交協(xié)議（2PC）

兩階段提交協(xié)議2PC（Two-phase Commit）［4］是指在計(jì)算機(jī)網(wǎng)絡(luò)以及數(shù)據(jù)庫(kù)領(lǐng)域內(nèi)，為了使基于分布式系統(tǒng)架構(gòu)下的所有節(jié)點(diǎn)在進(jìn)行事務(wù)提交時(shí)保持一致性而設(shè)計(jì)的一種算法。

2PC協(xié)議只有在所有節(jié)點(diǎn)都同意提交事務(wù)后才會(huì)提交事務(wù)［5］。

2PC協(xié)議包括兩類節(jié)點(diǎn)，分別是協(xié)調(diào)者（Coordinator）和參與者（Cohorts），節(jié)點(diǎn)間可以進(jìn)行網(wǎng)絡(luò)通信。該協(xié)議假設(shè)所有的節(jié)點(diǎn)都采用預(yù)寫入日志的方式，且日志被寫入后會(huì)持久化到可靠的存儲(chǔ)設(shè)備上，這樣即使系統(tǒng)故障，也不會(huì)丟失日志。該協(xié)議同時(shí)假設(shè)所有的節(jié)點(diǎn)不會(huì)永久性損壞，即使損壞后也可以恢復(fù)。

2PC協(xié)議主要包括2個(gè)階段：

· 提交請(qǐng)求階段：

這個(gè)階段，協(xié)調(diào)者會(huì)向所有參與者詢問“是否可以執(zhí)行提交”操作，同時(shí)會(huì)開始等待各參與者節(jié)點(diǎn)回復(fù)。參與著執(zhí)行協(xié)調(diào)者的事務(wù)操作，將操作信息寫入日志。如果參與的事務(wù)操作執(zhí)行成功，則返回“同意”消息，否則回復(fù)“終止”消息。

· 提交執(zhí)行階段：

當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)所有參與著都回復(fù)“同意”時(shí)，協(xié)調(diào)者會(huì)向所有節(jié)點(diǎn)發(fā)出正式“正式提交”操作請(qǐng)求，參與者節(jié)點(diǎn)正式完成操作，并釋放整個(gè)事務(wù)處理期間占用的資源，然后參與者會(huì)向協(xié)調(diào)者發(fā)送“完成”消息。協(xié)調(diào)者收到所有節(jié)點(diǎn)反饋“完成后”，事務(wù)完成。當(dāng)?shù)谝粋€(gè)階段有任何一個(gè)參與者返回“終止”的消息，或者存在參與著操作超時(shí)，則協(xié)調(diào)者會(huì)向所有參與者發(fā)出“回滾操作”，協(xié)調(diào)者收到所有參與者返回“回滾完成”后取消事務(wù)。

2PC協(xié)議在現(xiàn)實(shí)分布式系統(tǒng)一般都不采用，主要是由于其有一個(gè)顯著的缺點(diǎn)，其事務(wù)的提交的過程中節(jié)點(diǎn)是處于阻塞狀態(tài)的，及節(jié)點(diǎn)在等待其他節(jié)點(diǎn)返回時(shí)無法響應(yīng)其他服務(wù)。并且如果出現(xiàn)參與者宕機(jī)或者無響應(yīng)時(shí)，協(xié)調(diào)者需要通過超時(shí)機(jī)制來恢復(fù)，系統(tǒng)無法容錯(cuò)且低效。

2.2.2 Paxos協(xié)議

Paxos協(xié)議是Lamport于1989年的一篇論文［6］首次提出，由于該算法晦澀難懂，直到1998年該論文才得以發(fā)表。Lamport后續(xù)又發(fā)表了相關(guān)文章《Paxos Made Simple》和《Fast Paxos》［7］［8］，因此大家習(xí)慣性地將這類算法稱為Paxos算法。

Paxos算法自問世以來就壟斷了可信環(huán)境分布式一致性算法。眾多分布式系統(tǒng)都采用了該算法實(shí)現(xiàn)分布式一致性，如Google的Spanner、Chubby、Megastore，還有開源的ZooKeeper等。

Paxos協(xié)議將系統(tǒng)中節(jié)點(diǎn)分為三類：

· 提議者（Proposer）： Proposer 負(fù)責(zé)提出提案，包括提案標(biāo)號(hào)和提案內(nèi)容。

· 決策者（Acceptor）：參與提案的決策，Acceptor收到提案后會(huì)根據(jù)情況決策是否要接受提案，若足夠多的Acceptor接受提案，則該提案3通過。

· 決策學(xué)習(xí)者（Learner）：不參與提案的提出或者決策過程，Proposer收到足夠多的Acceptor同意后，會(huì)將通過的決議發(fā)送給所有的Learner。

Paxos算法主要包括兩部分，為決議的達(dá)成和決議的發(fā)布，其中決議的達(dá)成又包括2個(gè)階段，整個(gè)過程如下圖所示：

上述圖描述了Paxos算法的流程，如下所述：

· 決議提出與達(dá)成：

準(zhǔn)備階段（Prepare）：Proposer選擇一個(gè)提案標(biāo)號(hào)Proposer ID并將prepare消息發(fā)送給Acceptors中的一個(gè)多數(shù)；Acceptor收到Prepare的消息后，如果提案標(biāo)號(hào)大于它接受的所有歷史提案的標(biāo)號(hào)，就回復(fù)接受，并承諾不再接受提案標(biāo)號(hào)小于該標(biāo)號(hào)的提案。

批準(zhǔn)階段（Accept）：當(dāng)一個(gè)proposer收到了多數(shù)acceptors對(duì)prepare的回復(fù)后，就進(jìn)入批準(zhǔn)階段。它要向回復(fù)prepare請(qǐng)求的acceptors發(fā)送accept請(qǐng)求，Acceptor在不違背其他提案的前提下對(duì)收到的Propose請(qǐng)求進(jìn)行Accept處理。Proposer在收到多數(shù)節(jié)點(diǎn)的accept消息后，提案就已經(jīng)達(dá)成。

· 決議的發(fā)布（Publish）：當(dāng)提案已經(jīng)達(dá)成后，Proposer會(huì)將該提案發(fā)送給所有的Learner。

2.2.3 Raft協(xié)議

Raft也是一種可信環(huán)境分布式一致性算法［9］。相比于Paxos算法，Raft更加容易理解和容易實(shí)現(xiàn)，他強(qiáng)化了領(lǐng)導(dǎo)人的概念，將整個(gè)分布式一致性問題抽象成了兩大階段，領(lǐng)導(dǎo)人選舉（Leader Election）和日志復(fù)制（Log Replication）。

Raft協(xié)議中每個(gè)節(jié)點(diǎn)可能會(huì)處于三種狀態(tài)：

· 領(lǐng)導(dǎo)者狀態(tài)（Leader）：Leader負(fù)責(zé)處理客戶端的請(qǐng)求并將事務(wù)同步給Follwer。

· 跟從者（Follower）：接受Leader的更新事務(wù)請(qǐng)求，并寫入本地的日志文件。

· 候選狀態(tài)（Candidate）： 當(dāng)Follower一段時(shí)間內(nèi)沒有接收到Leader的心跳，會(huì)認(rèn)為L(zhǎng)eader不可用，此時(shí)副本會(huì)進(jìn)入Candidate狀態(tài)，并開始新一輪選主，直到新的主被選擇出來。

其狀態(tài)轉(zhuǎn)換圖如下所示：

第一個(gè)階段選出主后，會(huì)進(jìn)入第二個(gè)階段Log replication，這個(gè)階段Leader就開始處理客戶端的請(qǐng)求，每一個(gè)請(qǐng)求包含一個(gè)被副本狀態(tài)機(jī)執(zhí)行的命令。Leader將該命令作為一個(gè)新的記錄追加在日志結(jié)尾。同時(shí)調(diào)用其他節(jié)點(diǎn)的追加記錄的接口，將操作同步給其他副本。如果某個(gè)Follower宕機(jī)、運(yùn)行地很慢或者網(wǎng)絡(luò)丟包，那么Leader會(huì)一直重試直到副本與與Leader狀態(tài)一致。

2.3 不可信環(huán)境分布式一致性問題

當(dāng)一個(gè)分布式系統(tǒng)中節(jié)點(diǎn)的維護(hù)方不屬于某個(gè)公司單獨(dú)所有，節(jié)點(diǎn)的參與方的利益互不相同時(shí)，就可能會(huì)出現(xiàn)節(jié)點(diǎn)不遵循規(guī)則，對(duì)系統(tǒng)實(shí)施作惡，這樣的環(huán)境就是一個(gè)不可信的環(huán)境。其中作惡的節(jié)點(diǎn)我們叫做拜占庭節(jié)點(diǎn)（Byzantine node），這樣環(huán)境下的分布式系統(tǒng)我們稱之為UTEDS（Untrusted Environment Distributed System）

不可信環(huán)境分布式系統(tǒng)容錯(cuò)即BFT（Byzantine-Fault-Tolerant），該類系統(tǒng)中，我們需要允許部分節(jié)點(diǎn)作惡、欺騙或者偽造消息。

不可信環(huán)境分布式系統(tǒng)一致性算法典型的有BFT、PBFT和SBFT。下節(jié)會(huì)向大家介紹一下著名的拜占庭問題及相應(yīng)算法。區(qū)塊鏈系統(tǒng)是一個(gè)不可性環(huán)境的分布式系統(tǒng)，自2008年比特幣系統(tǒng)創(chuàng)建以來，一批又一批的學(xué)者和科創(chuàng)團(tuán)隊(duì)投入該領(lǐng)域分布式一致性問題的研究，創(chuàng)新性地引入了激勵(lì)以及博弈的思想來促使系統(tǒng)達(dá)成一致。經(jīng)典的算法有PoW、PoS、DAG、VRF等，這些內(nèi)容將在下一章進(jìn)行詳細(xì)地介紹。

2.3.1 拜占庭將軍問題及算法

拜占庭問題是由Lamport于1982年［10］提出的分布式對(duì)等網(wǎng)絡(luò)通信的容錯(cuò)問題。在分布式系統(tǒng)中，所有節(jié)點(diǎn)通過通信交換達(dá)成共識(shí)，按照相同的策略協(xié)同。但是系統(tǒng)中有時(shí)存在節(jié)點(diǎn)由于各種原因，發(fā)送錯(cuò)誤的信息到網(wǎng)絡(luò)中，從而破壞系統(tǒng)的一致性。

拜占庭問題的原始描述是：N個(gè)將軍被分隔在不同的地方，誠(chéng)實(shí)的將軍希望通過某種協(xié)議達(dá)成命令的一致。但是其中一些背叛的將軍會(huì)通過發(fā)送錯(cuò)誤的消息阻撓的誠(chéng)實(shí)的將軍達(dá)成一致。Lamport證明了在將軍總數(shù)大于3f，背叛者為f或者更少時(shí)，忠誠(chéng)的將軍可以達(dá)成命令上的一致。

拜占庭問題的證明：

證明前，首先看3個(gè)概念［11］：

· 仲裁（Quorum）：只作出一次決策至少需要的得到的同意的票數(shù)。

· 活躍度（Liveness）：是指在共識(shí)決策的過程中保持活躍的節(jié)點(diǎn)，不能出現(xiàn)卡死或者無響應(yīng)的狀態(tài)。

· 安全性（Safty）： 是指執(zhí)行過共識(shí)算法后，節(jié)點(diǎn)能夠達(dá)成一致。

證明過程如下，假設(shè)系統(tǒng)中共有N個(gè)節(jié)點(diǎn)，f個(gè)拜占庭節(jié)點(diǎn)，仲裁組節(jié)點(diǎn)為Q。

1. 那么要滿足Liveness，則Q《=N-f，如果Q》N-f，那么f個(gè)拜占庭節(jié)點(diǎn)都作惡時(shí)，算法無法繼續(xù)運(yùn)行。

2. 為了滿足Safety，則需要滿足2Q-N》f，即任意兩個(gè)仲裁組的交集一定要有非拜占庭節(jié)點(diǎn)；

3. 則 N+f《2Q《=2N-2f 且N》3f；

4. 當(dāng)N=3f+1時(shí)，Q》=2f + 1;

根據(jù)以上證明，可以得出在一個(gè)拜占庭將軍問題中，總節(jié)點(diǎn)為N的環(huán)境下，最多只能f個(gè)拜占庭節(jié)點(diǎn)，且N》=3f+1。

2.3.2 PBFT

傳統(tǒng)的BFT算法復(fù)雜度太高，Castro和Liskov于1999年提出了PBFT（Practical Byzantine Fault Tolerance）實(shí)用拜占庭容錯(cuò)算法［12］，該算法能夠?qū)崿F(xiàn)拜占庭容錯(cuò)，同時(shí)能夠大大提升拜占庭容錯(cuò)的效率。

PBFT是一種基于副本狀態(tài)機(jī)復(fù)制的算法。將不可信環(huán)境一致性達(dá)成分成3個(gè)階段，分別是預(yù)準(zhǔn)備、準(zhǔn)備和確認(rèn)。如下圖所示：

上圖中對(duì)于每個(gè)請(qǐng)求的處理過程如下：

· 請(qǐng)求（request）：客戶端c向服務(wù)器0發(fā)起一個(gè)請(qǐng)求；

· 預(yù)準(zhǔn)備階段（pre-prepare）：該階段，服務(wù)器0分配一個(gè)整數(shù)n給收到的請(qǐng)求，并將消息廣播給所有的副本節(jié)點(diǎn)，同時(shí)將消息添加到日志的結(jié)尾，消息格式為，其中v表示發(fā)送消息的視圖、m表示客戶端發(fā)送的消息，d表示消息的摘要。副本收到消息后會(huì)進(jìn)行消息的簽名驗(yàn)證、消息摘要驗(yàn)證、視圖驗(yàn)證和水平線驗(yàn)證，驗(yàn)證通過的消息予以接收。

· 準(zhǔn)備階段（prepare）：當(dāng)副本接受了消息時(shí)，就會(huì)進(jìn)入prepare階段，這個(gè)階段，副本會(huì)廣播消息，同時(shí)將預(yù)準(zhǔn)備消息和準(zhǔn)備消息寫入日志。當(dāng)所有正常節(jié)點(diǎn)對(duì)統(tǒng)一視圖v的請(qǐng)求序號(hào)n達(dá)成一致時(shí)，會(huì)進(jìn)入確認(rèn)階段。

· 確認(rèn)（commit）：該階段，副本會(huì)廣播。其他副本會(huì)進(jìn)行消息驗(yàn)證和確認(rèn)，當(dāng)確認(rèn)后，會(huì)將消息寫入日志。

· 返回（Reply）：對(duì)客戶端C進(jìn)行反饋。

PBFT能夠有效地實(shí)現(xiàn)拜占庭容錯(cuò)，且由于其將容錯(cuò)分為明確的3個(gè)階段，工程上更容易實(shí)現(xiàn)。但是他有個(gè)比較大的缺點(diǎn)是系統(tǒng)中的節(jié)點(diǎn)規(guī)模不能很大，因?yàn)橄到y(tǒng)中的每個(gè)節(jié)點(diǎn)都要頻繁地和其他說有節(jié)點(diǎn)進(jìn)行通信，當(dāng)系統(tǒng)節(jié)點(diǎn)規(guī)模太大后，系統(tǒng)將無法運(yùn)行。

2.3.3 SBFT

為了優(yōu)化PBFT在擴(kuò)展上的不足，業(yè)界也在不斷地進(jìn)行探索。2018年GG Gueta提出SBFT（Scalable Byzantine Fault Tolerance）［13］，旨在提高BFT的擴(kuò)展性。SBFT主要從以下四點(diǎn)進(jìn)行了優(yōu)化：

· 降低通信：通過使用收集器，副本將消息發(fā)送給收集器，收集器將消息廣播給所有節(jié)點(diǎn)，同時(shí)通過使用閾值前面，將收集器消息大小從線性減少到常量;

· 添加快速路徑：在所有副本都非故障且同步的時(shí)候，SBFT使用一種樂觀的快速路徑；

· 將客戶端通信從f+1 減到1：SBFT通過添加一個(gè)使用收集器聚合執(zhí)行閾值簽名的階段，并給每個(gè)客戶端發(fā)送一個(gè)帶簽名的消息，從而將每個(gè)客戶端的線性成本降低為一條消息；

· 通過冗余服務(wù)器進(jìn)行快速路徑；

SBFT在算法的流程如下圖所示：

· 客戶端向主服務(wù)器發(fā)送操作請(qǐng)求；

· 主服務(wù)器收集客戶端請(qǐng)求，創(chuàng)建決策塊，并將此塊作為預(yù)準(zhǔn)備消息轉(zhuǎn)發(fā)給副本；

· 副本使用σ（3f+c+1）-閾值簽名對(duì)決策塊進(jìn)行簽名，并將簽名共享消息發(fā)送給C-收集器；

· 每個(gè)C-收集器收集共享簽名，并為決策塊創(chuàng)建一個(gè)簡(jiǎn)潔的完全提交證明，并將其發(fā)送回副本，這種單消息提交證明具有固定的大小開銷，包含單個(gè)簽名，并且足以副本提交；

· 一旦副本接受到提交證明，它會(huì)提交決策區(qū)塊，并啟動(dòng)執(zhí)行協(xié)議；

當(dāng)副本在提交決策區(qū)塊前，他需要完成序列塊的執(zhí)行，并對(duì)新的狀態(tài)進(jìn)行閾值簽名，然后將其發(fā)送給E-收集器；

每個(gè)E-收集器收集簽名，并創(chuàng)建決策塊的完整證明，然后，它向副本發(fā)送一個(gè)證書，表明狀態(tài)是持久的，向客戶機(jī)發(fā)送一個(gè)證書，表明其操作已被執(zhí)行完畢。

目前SBFT已經(jīng)實(shí)現(xiàn)了最大209個(gè)節(jié)點(diǎn)的測(cè)試網(wǎng)絡(luò)。相比于PBFT，在擴(kuò)展性上提高了2倍。

2.3.4全球部署不可信環(huán)境

一般的公鏈系統(tǒng)，如比特幣、以太坊節(jié)點(diǎn)數(shù)都超過了1W個(gè)。在這樣的系統(tǒng)中PBFT和SBFT都無法很好地工作，這樣大規(guī)模的不可信環(huán)境下的分布式一致性問題近10年來也是區(qū)塊鏈系統(tǒng)的一個(gè)研究熱點(diǎn)。區(qū)塊鏈創(chuàng)造性地引入了激勵(lì)的機(jī)制和博弈的思想來促使大規(guī)模不可信環(huán)境中的節(jié)點(diǎn)達(dá)成一致，下面一章將詳細(xì)介紹比較著名的共識(shí)協(xié)議，包括PoW、PoS、DAG、VRF，并會(huì)簡(jiǎn)要介紹一下使用該共識(shí)的應(yīng)用。

區(qū)塊鏈共識(shí)機(jī)制及其應(yīng)用

共識(shí)機(jī)制是區(qū)塊鏈系統(tǒng)各節(jié)點(diǎn)達(dá)成一致的協(xié)議，對(duì)交易的進(jìn)行合法性和一致性確認(rèn)。早期的區(qū)塊鏈系統(tǒng)采用PoW（Proof of work），后續(xù)隨著區(qū)塊鏈的發(fā)展、出現(xiàn)了PoS（Proof of Stake）、DAG等一系列的算法。下面這個(gè)圖直觀地向大家展示了各個(gè)共識(shí)協(xié)議的使用應(yīng)用。后續(xù)各小節(jié)會(huì)詳細(xì)進(jìn)行介紹各個(gè)協(xié)議，并對(duì)其優(yōu)缺點(diǎn)進(jìn)行簡(jiǎn)要介紹。

3.1PoW（Proof of work）

1993年，Pow［14］思想首次被Cynthia Dwork在論文《Pricing via Processing or Combatting Junk Mail》中被提出。該算法用于解決垃圾郵件的問題，要求郵件發(fā)送者需要計(jì)算某個(gè)數(shù)學(xué)難題以此來提高郵件發(fā)送的成本，從而減少垃圾郵件。

2008年中本聰發(fā)表了文章［1］標(biāo)志著區(qū)塊鏈的誕生，次年初，全球第一個(gè)區(qū)塊鏈系統(tǒng)比特幣誕生。比特幣采用的是PoW共識(shí)算法來保證分布式網(wǎng)絡(luò)記賬的一致性，這是迄今為止最為安全的公鏈共識(shí)算法。

在比特幣網(wǎng)絡(luò)中所有節(jié)點(diǎn)都可以參與競(jìng)爭(zhēng)挖礦。如果想要生成一個(gè)區(qū)塊并寫入賬本中，則需要成為網(wǎng)絡(luò)中最先解出比特幣網(wǎng)絡(luò)中的工作量證明謎題的節(jié)點(diǎn)。

在比特幣中，PoW算法致力于尋找一個(gè)值，使得它SHA256的hash值以若干個(gè)0開始。隨著0的個(gè)數(shù)的增加，算出目標(biāo)hash值的工作量耗費(fèi)會(huì)呈指數(shù)上升，但是可以只通過一次hash運(yùn)算就可以驗(yàn)證謎題。求解謎題的公式如下：

通過修改block中的nonce值，直到算出的block的hash值符合0的個(gè)數(shù)的要求。一旦CPU努力使其滿足工作證明時(shí)，在不進(jìn)行重做的情況下，區(qū)塊無法被改變。由于后面的區(qū)塊會(huì)連接到前一個(gè)區(qū)塊，如下圖六所示，修改一個(gè)塊，需要將后面所有塊的工作量都重做一遍。

PoW解決了群體決策中的確定代表問題。如果絕大數(shù)的是基于IP的投票，那么任何能夠分配多個(gè)IP的人都可能破壞它。PoW強(qiáng)調(diào)One-CPU-One-Vote。大多數(shù)決策是采用最長(zhǎng)鏈的方法，因?yàn)檫@表明工作量投入的最大，如果絕大數(shù)節(jié)點(diǎn)都是善良的，那么誠(chéng)實(shí)鏈會(huì)長(zhǎng)成最快的鏈，超過任何競(jìng)爭(zhēng)的鏈。攻擊者如果想改變一個(gè)區(qū)塊，那么需要修改該塊后所有區(qū)塊，并且能夠長(zhǎng)成最長(zhǎng)的誠(chéng)實(shí)鏈，比特幣網(wǎng)絡(luò)在設(shè)計(jì)的時(shí)候考慮了博弈的思想，生產(chǎn)一個(gè)合法的區(qū)塊需要付出金錢代價(jià)，這使得攻擊者需要掌握足夠的算力才能發(fā)起攻擊，掌握足夠的算力是非常昂貴的，這使得發(fā)起攻擊很難獲利。

為了避免硬件加速等因素導(dǎo)致區(qū)塊打包過快，PoW會(huì)依據(jù)出塊的時(shí)間調(diào)整打包區(qū)塊的難度。如果生成速度太快，難度就會(huì)增加。

PoW算法是唯一一個(gè)被成功驗(yàn)證的公鏈算法，安全性最高。

PoW算法的缺點(diǎn)主要有兩點(diǎn)，一是能耗大，需要消耗巨大的電力。二是效率低，比特幣平均10分鐘才打包一個(gè)區(qū)塊，系統(tǒng)的吞吐低，而且也無法盲目地通過縮短出塊時(shí)間或者增加區(qū)塊大小來提高系統(tǒng)吞吐，縮短出塊時(shí)間會(huì)導(dǎo)致生成區(qū)塊速度太快，而分叉很多，會(huì)造成系統(tǒng)頻繁回滾從而降低性能，目前比特幣的區(qū)塊大小在1M左右，增大區(qū)塊大小，可能會(huì)導(dǎo)致區(qū)塊在網(wǎng)絡(luò)中傳播的效率降低。

3.2 PoS（Proof of stake）

2011年Quantum Mechanic［15］首次提出了PoS算法。在基于PoS的加密貨幣中，下一個(gè)區(qū)塊的創(chuàng)建者是通過隨機(jī)選擇和財(cái)富或幣齡（即股份）的各種組合來選擇的。PoS必須有定義任何區(qū)塊下一個(gè)有效區(qū)塊的方法，不能僅僅按照賬戶余額，這樣會(huì)造成富有的人越富有。PoS的發(fā)展主要經(jīng)歷了3個(gè)階段，第一階段是以Peercoin為代表的的基于幣齡的PoS，第二個(gè)階段是以黑幣為代表的基于幣數(shù)的PoS，第三階段是像EOS、XuperChain這樣為代表的DPoS。

3.2.1基于幣齡的 PoS

Peercoin是Sunny King， Scott Nadal于2012年從中本聰所創(chuàng)造的BTC衍生出來的一種P2P的電子密碼貨幣［16］，以PoS取代PoW來維護(hù)網(wǎng)絡(luò)安全，是基于幣齡（coin age）并由通過與BTC類似的由每個(gè)節(jié)點(diǎn)散列運(yùn)算產(chǎn)生的，只是其搜索空間被限制了。

幣齡（Coin age），定義為貨幣的持有時(shí)間段，假設(shè)a收到10幣，并持有了5天，那么就說明了a積攢了50幣齡。一筆交易所消耗的幣齡可被視為PoS的一種形式。

PoS下生成區(qū)塊如下圖所示：

這種新型區(qū)塊里PoS是一種特殊的交易稱利息幣（coinstake），類似于BTC中的coinbase。在利息幣（coinstake） 交易中，區(qū)塊持有人可以 消耗他的幣齡獲得利息，同時(shí)獲得為網(wǎng)絡(luò)產(chǎn)生一個(gè)區(qū)塊和用PoS造幣的優(yōu)先權(quán)。利息幣的第一個(gè)輸入被稱為核心（Kernel），需要符合某一Hash目標(biāo)協(xié)議。PoS區(qū)塊的產(chǎn)生具有隨機(jī)性，這一過程與PoW相似。但有一個(gè)重要的區(qū)別在于， PoS的隨機(jī)散列運(yùn)算是在的搜索空間比PoW小，在hash/未消費(fèi)錢包的輸出*秒，而不是象PoW那樣在無限制的空間里尋找，因此無需大量的能源消耗。其生成區(qū)塊可以用下面這個(gè)公式表示：

Peercion對(duì)可以參與挖礦的幣齡做了限制，大于30天的幣才可以參與挖礦，幣齡越大、幣數(shù)越多的節(jié)點(diǎn)越容易挖出下一個(gè)區(qū)塊。然而一旦一個(gè)幣用來挖出一個(gè)區(qū)塊，它的幣齡就會(huì)歸零，需要等到30天以上才能再進(jìn)行挖礦。此外為了避免幣齡太老的節(jié)點(diǎn)控制網(wǎng)絡(luò)，幣齡最大不會(huì)超過90天。

基于幣齡的PoS算法，相比于PoW更加環(huán)保，且由于挖礦不完全依賴與CPU，使得系統(tǒng)內(nèi)在的安全系數(shù)提升，黑客無法通過系統(tǒng)外的力量進(jìn)行攻擊。

但是由于Peercoin中僅允許幣天大于30天的幣才可以參與挖礦，所以導(dǎo)致節(jié)點(diǎn)的在線率特別低。很多節(jié)點(diǎn)會(huì)等待快要到幣齡才開啟節(jié)點(diǎn)。

3.2.2 基于幣數(shù)的PoS

前面提到的基于幣齡的PoS有幾個(gè)潛在的安全風(fēng)險(xiǎn)，幣齡會(huì)被惡意利用已發(fā)起雙花攻擊。而且，由于幣齡的存在，誠(chéng)實(shí)節(jié)點(diǎn)會(huì)通過定期開啟節(jié)點(diǎn)的方式來積攢幣齡。

為了進(jìn)一步提供PoS系統(tǒng)的安全性，提升節(jié)點(diǎn)的在線時(shí)長(zhǎng)。2014年P(guān)avel Vasin提出了黑幣，其PoS算法也被稱為PoS2.0［17］。

相比于以往的PoS，黑幣的PoS協(xié)議變化主要有四點(diǎn)，如下所示：

· hash計(jì)算： 執(zhí)行PoS最安全的方式是讓盡可能多的節(jié)點(diǎn)在線。參與的節(jié)點(diǎn)越多，發(fā)生51%攻擊的可能性越低，實(shí)際網(wǎng)絡(luò)中通過這些節(jié)點(diǎn)確認(rèn)事務(wù)的時(shí)間越快。因此，黑幣取消了hash計(jì)算公式中幣齡參數(shù)，新系統(tǒng)計(jì)算謎題的公式變成如下：

· 改變權(quán)益修正因子：為了減少預(yù)計(jì)算攻擊的可能性，權(quán)重修正因子在每一次修正因子間歇時(shí)都會(huì)改變，以便對(duì)將要用來下一個(gè)權(quán)益累積證明的時(shí)間戳的計(jì)算結(jié)果進(jìn)行更好的模糊處理。

· 區(qū)塊時(shí)間戳規(guī)則：通過修改區(qū)塊的時(shí)間戳以更好地使用PoS。預(yù)期的出塊時(shí)間從最初的60s增加到粒度匹配的時(shí)間。假設(shè)節(jié)點(diǎn)有一個(gè)外部時(shí)間，假設(shè)節(jié)點(diǎn)時(shí)間與系統(tǒng)共識(shí)時(shí)間偏離太多，這個(gè)節(jié)點(diǎn)將被孤立。區(qū)塊時(shí)間戳的修改規(guī)則如下：

· hash函數(shù)：黑幣采用SHA256d算法，SHA256d是將SHA256算2遍，這種算法如下所示，

通過上述的優(yōu)化，黑幣將可能的攻擊降到最小，并能夠顯著提升節(jié)點(diǎn)的在線率。使得PoS在進(jìn)一步擴(kuò)大節(jié)點(diǎn)范圍的同時(shí)能夠有效地降低系統(tǒng)風(fēng)險(xiǎn)，提高系統(tǒng)的安全性。

3.2.3 DPoS

DPoS是2014年4月由Bitshares 的首席開發(fā)者 Dan Larimer提出的一種基于代理人機(jī)制的PoS算法［18］。DPoS算法一般每隔預(yù)設(shè)時(shí)間長(zhǎng)度（一個(gè)區(qū)塊周期）選擇N個(gè)候選區(qū)塊生成節(jié)點(diǎn)，確定各候選區(qū)塊生成節(jié)點(diǎn)的區(qū)塊生成順序，并將一個(gè)區(qū)塊生成周期所需的區(qū)塊生成時(shí)間均分為N個(gè)時(shí)間段，再按照區(qū)塊生成順序?qū)⒏鲿r(shí)間段分配給各候選區(qū)塊生成節(jié)點(diǎn)。各個(gè)候選區(qū)塊生成節(jié)點(diǎn)會(huì)按照預(yù)設(shè)的順序協(xié)同出塊；所以DPoS算法主要包括兩個(gè)階段，第一階段是候選人的選舉，第二個(gè)階段是輪值。

第一階段是候選人選舉，在該階段，用戶可以給候選人進(jìn)行投票，候選人一般地可以通過提名的方式限制在指定范圍內(nèi)，也可以不進(jìn)行限制。每到一定的時(shí)間系統(tǒng)會(huì)進(jìn)行礦工選舉，得票高的節(jié)點(diǎn)當(dāng)選為下一輪的礦工。

第二階段是輪值階段，在該階段，第一階段選出的節(jié)點(diǎn)會(huì)按照既定的順序輪流出塊，協(xié)同出塊。

DPoS和上述的共識(shí)協(xié)議相比大幅縮短了打包區(qū)塊的時(shí)間，大大增加了系統(tǒng)的處理能力，交易確認(rèn)時(shí)間降低到秒級(jí)。

百度的超級(jí)鏈實(shí)現(xiàn)了一種改進(jìn)的DPoS［19］，XuperChain 自主研發(fā)實(shí)現(xiàn)了一套 DPoS 共識(shí)，我們稱之為 TDPoS。依據(jù)這種算法，全網(wǎng)持有通證的人都可以給候選人投票。TDPoS 的參數(shù)包括每輪的 proposer 個(gè)數(shù)、出塊間隔、節(jié)點(diǎn)每輪出塊個(gè)數(shù)等，在創(chuàng)建平行鏈的時(shí)候可以指定，也可以通過提案機(jī)制升級(jí)。例如，如果配置的參數(shù)為每輪21個(gè)節(jié)點(diǎn)、出塊間隔為3s、每個(gè)節(jié)點(diǎn)每輪出塊個(gè)數(shù)為 200 個(gè)，則每輪的時(shí)間為 3.5h。傳統(tǒng)的DPoS依賴于相對(duì)同步的網(wǎng)絡(luò)，TDPoS創(chuàng)造性地引入GPS加原子鐘的方式來修正節(jié)點(diǎn)間的時(shí)間同步問題。

3.3DAG（Directed Acyclic Graphs）

DAG第一次被提出與區(qū)塊鏈結(jié)合是在Nxt社區(qū)，為的是解決區(qū)塊鏈的效率問題。DAG是一種圖狀的區(qū)塊鏈。由于其獨(dú)特區(qū)塊結(jié)構(gòu)，DAG內(nèi)在地支持高可擴(kuò)展性，得到了廣泛的應(yīng)用。

從根本上說，任何區(qū)塊鏈系統(tǒng)都具有線性結(jié)構(gòu)，因?yàn)閰^(qū)塊是依次添加到鏈中的。這使得相比于并行向鏈中添加區(qū)塊，線性區(qū)塊鏈在本質(zhì)上是非常緩慢的。但是對(duì)于DAG而言，每個(gè)區(qū)塊和交易只需數(shù)個(gè)前期區(qū)塊得到確認(rèn)，就可以并行地添加到區(qū)塊和交易中。所以DAG在擴(kuò)展性上給人以很大的想象空間。

IOTA和Byteball項(xiàng)目都使用了基于DAG的區(qū)塊鏈應(yīng)用，進(jìn)一步地，他們提出了Blockless無區(qū)塊的概念，讓每一個(gè)事務(wù)直接參與維護(hù)全網(wǎng)的交易順序。這樣交易發(fā)起后直接跳過了打包的階段，直接融入全網(wǎng)，達(dá)到blockless的目的，同時(shí)由于省去了打包的時(shí)間，效率會(huì)進(jìn)一步地提升。

基于DAG的共識(shí)主要有以下幾個(gè)優(yōu)點(diǎn)：

交易速度快：DAG 的并行化結(jié)構(gòu)和blockless的設(shè)計(jì)會(huì)提高系統(tǒng)的效率，交易速度大大提升。

無需挖礦：由于不需要區(qū)塊打包，故無需挖礦；

無手續(xù)費(fèi)：由于blockless的項(xiàng)目中沒有礦工進(jìn)行區(qū)塊打包，所以不需要付手續(xù)費(fèi)給礦工。

3.4VRF（Verifiable Random Function）

2016年， 圖靈獎(jiǎng)得主、MIT 教授Sivio Micali提出了一種稱為 Algorand的快速拜占庭容錯(cuò)共識(shí)算法［20］［21］。該算法是基于VRF，利用密碼抽簽技術(shù)選擇共識(shí)過程的驗(yàn)證者和領(lǐng)導(dǎo)者， 并通過其設(shè)計(jì)的BA* 拜占庭容錯(cuò)協(xié)議對(duì)新區(qū)塊達(dá)成共識(shí)。 Algorand只需要極小的計(jì)算量且不易分叉， 被認(rèn)為是實(shí)現(xiàn)區(qū)塊鏈去中心化、可延展性和安全性不可能三角的區(qū)塊鏈項(xiàng)目。

VRF是可驗(yàn)證隨機(jī)數(shù)，所謂的可驗(yàn)證的隨機(jī)數(shù)可以看做一個(gè)隨機(jī)預(yù)言機(jī)，可以通過任意一個(gè)輸入獲得一個(gè)隨機(jī)數(shù)輸出，主要有兩點(diǎn)：

對(duì)于不同的Input，Output的值是隨機(jī)的，但是均勻地分布在值域范圍內(nèi)。

對(duì)于相同的Input，他的Output是一定是相同的。

VRF的過程主要包括四個(gè)步驟：

VRFgen：隨機(jī)生成密鑰，生成一對(duì)非對(duì)稱加密密鑰（一對(duì)公私鑰）；

VRFval：生成隨機(jī)數(shù)輸出；

VRFproof：隨機(jī)數(shù)輸出的零知識(shí)證明；

VRFver：其他節(jié)點(diǎn)收到輸入和零知識(shí)證明后，結(jié)合生成隨機(jī)數(shù)的節(jié)點(diǎn)的公私鑰，對(duì)隨機(jī)數(shù)進(jìn)行驗(yàn)證。

通過VRF，Alogrand實(shí)現(xiàn)了加密排序，排序需要一個(gè)角色參數(shù)，這樣不同的用戶可能選擇不同的角色，例如，用戶可能被選為區(qū)塊生產(chǎn)者，也可以被選為委員會(huì)成員。Alogrand通過一個(gè)閾值來確定每個(gè)角色選擇的用戶數(shù)。加密排序算法如下所示：

驗(yàn)證加密排序的偽代碼如下所示，通過相同的結(jié)構(gòu)驗(yàn)證用戶是否被選中，函數(shù)返回所選子用戶的數(shù)量，若沒有選出用戶，則返回0。

Alogrand通過VRF實(shí)現(xiàn)了礦工選擇的不可預(yù)測(cè)性，實(shí)現(xiàn)了區(qū)塊鏈的去中心化；并且每個(gè)區(qū)塊隨機(jī)產(chǎn)生，不需要競(jìng)爭(zhēng)出塊，提升了系統(tǒng)的擴(kuò)展性；PoW、PoS當(dāng)惡意節(jié)點(diǎn)積攢到一定數(shù)量時(shí)就可以控制網(wǎng)絡(luò)，一般地是通過博弈的方式來實(shí)現(xiàn)網(wǎng)絡(luò)穩(wěn)定性和安全性保障，Alogrand隨機(jī)產(chǎn)生區(qū)塊生產(chǎn)者，所以即使是惡意節(jié)點(diǎn)，也無法隨意控制網(wǎng)絡(luò)。

區(qū)塊鏈共識(shí)機(jī)制發(fā)展趨勢(shì)

自從2018年中本聰發(fā)布比特幣以來，區(qū)塊鏈系統(tǒng)已經(jīng)經(jīng)歷了10年的發(fā)展。共識(shí)算法的發(fā)展也進(jìn)入了百花齊放的時(shí)期。縱觀區(qū)塊鏈共識(shí)協(xié)議的發(fā)展過程，主要體現(xiàn)以下幾大趨勢(shì)。

4.1 從單一共識(shí)到可插拔共識(shí)

早期的區(qū)塊鏈系統(tǒng)，一般采取單一的共識(shí)機(jī)制，比如BTC的PoW、Peercoin的PoS等、EOS的DPoS等。

在當(dāng)前的技術(shù)背景下，沒有哪一種共識(shí)機(jī)制是完美無缺的，每一種共識(shí)機(jī)制都有其優(yōu)點(diǎn)和缺點(diǎn)，不同的應(yīng)用場(chǎng)景可能需要不同共識(shí)機(jī)制。在區(qū)塊鏈解決方案中，應(yīng)該實(shí)現(xiàn)兼容多種共識(shí)算法，在實(shí)際業(yè)務(wù)落地中有選擇性的使用一種最合適的共識(shí)機(jī)制，甚至整個(gè)網(wǎng)絡(luò)具備讓開發(fā)者自定義共識(shí)機(jī)制的能力。未來可插拔的共識(shí)機(jī)制可能是未來發(fā)展的主要方向。

百度超級(jí)鏈XuperChain實(shí)現(xiàn)了可插拔共識(shí)機(jī)制，目前已經(jīng)支持Pow，DPoS，Pool和Raft等共識(shí)，同時(shí)還允許用戶通過該可插拔共識(shí)框架定義符合其業(yè)務(wù)特征的共識(shí)機(jī)制。

Hyperledger的 Fabric也實(shí)現(xiàn)了可插拔的共識(shí)機(jī)制，目前支持的共識(shí)Solo、Kafka、SBFT。

4.2 從鏈?zhǔn)焦沧R(shí)到圖式共識(shí)

一般地，區(qū)塊鏈?zhǔn)且环N鏈?zhǔn)浇Y(jié)構(gòu)，區(qū)塊只能沿著一條鏈生長(zhǎng)，效率較低。隨著共識(shí)的發(fā)展，有人提出使用DAG的方式，所謂DAG就是有向無環(huán)圖?；谶@種思想，可以有很多新的方式，比如可以并發(fā)地進(jìn)行區(qū)塊打包，從而提高區(qū)塊鏈的擴(kuò)展能力。

除了前面提到的IOTA和Byteball使用了基于DAG的共識(shí)協(xié)議。圖靈獎(jiǎng)得主、清華大學(xué)交叉信息研究院院長(zhǎng)姚期智參與創(chuàng)立的區(qū)塊鏈項(xiàng)目 Conflux也是基于DAG的思想，Conflux的理念設(shè)計(jì)容許不同區(qū)塊同時(shí)生成，并運(yùn)用基于有向無環(huán)圖（directed acyclic graph， DAG）概念的排序算法來避免分叉的問題，先決定所有區(qū)塊的整體排序，再?zèng)Q定衍生的交易排序。

4.3 從確定性共識(shí)到隨機(jī)共識(shí)

前面所述的共識(shí)，為了提高區(qū)塊鏈系統(tǒng)的吞吐能力，一定程度上降低了其去中心化的程度，一定程度上降低了系統(tǒng)的安全性。Alogrand項(xiàng)目出現(xiàn)，使得共識(shí)由確定性向隨機(jī)性發(fā)展，在該共識(shí)中，很多節(jié)點(diǎn)都具有潛在的控制權(quán)，下一個(gè)礦工的是由加密排序函數(shù)隨機(jī)產(chǎn)生，在這種變化下，事實(shí)上雖然只有少數(shù)節(jié)點(diǎn)參與共識(shí)，但是由于參與共識(shí)的節(jié)點(diǎn)在系統(tǒng)中游走，無法提前預(yù)測(cè)，從而實(shí)現(xiàn)系統(tǒng)的安全性。

除了上面提到的Alogrand使用了基于VRF的共識(shí)協(xié)議，Difinity和TASchain也都使用了基于VRF的共識(shí)機(jī)制，未來該趨勢(shì)上相信會(huì)有更多適用于工業(yè)級(jí)的共識(shí)協(xié)議誕生。

總結(jié)與展望

本文從分布式一致性問題切入，分別討論了可信環(huán)境分布式系統(tǒng)和不可信環(huán)境分布式系統(tǒng)的一致性問題。在可信環(huán)境分布式系統(tǒng)一致性問題中，介紹了經(jīng)典的2PC、Paxos和Raft協(xié)議。在不可信環(huán)境分布式系統(tǒng)一致性問題中，介紹了拜占庭教軍問題及PBFT算法，并介紹了公鏈環(huán)境下新型一致性協(xié)議（即區(qū)塊鏈共識(shí)協(xié)議）及應(yīng)用，主要包括PoW、PoS、DAG和VRF。最后本文總結(jié)了區(qū)塊鏈的發(fā)展趨勢(shì)，主要體現(xiàn)三大趨勢(shì)，從單一共識(shí)向可插拔共識(shí)、從鏈?zhǔn)焦沧R(shí)向圖式共識(shí)、從確定性共識(shí)向隨機(jī)性共識(shí)。

區(qū)塊鏈?zhǔn)且粋€(gè)不可信環(huán)境分布式系統(tǒng)，區(qū)塊鏈共識(shí)是不可信環(huán)境分布式系統(tǒng)一致性的一個(gè)重要的研究方向。近年來，區(qū)塊鏈共識(shí)也百花齊放，各種改進(jìn)算法爭(zhēng)相被提出。本文討論的共識(shí)算法只是其中的一個(gè)子集。

未來，隨著區(qū)塊鏈技術(shù)的進(jìn)一步發(fā)展，尤其是伴隨著底層賬本結(jié)構(gòu)的進(jìn)一步優(yōu)化，勢(shì)必會(huì)涌現(xiàn)出更多的新興的共識(shí)算法，本文提到的IOTA的基于DAG的共識(shí)只是其中一種。同時(shí)，隨著技術(shù)的進(jìn)一步深入，區(qū)塊鏈共識(shí)的評(píng)估標(biāo)準(zhǔn)也一定會(huì)進(jìn)一步規(guī)范。
來源： 百度超級(jí)鏈?