區(qū)塊鏈共識機制的演進應(yīng)用以及未來趨勢預(yù)測

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

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

概述

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

2008年11月1日，中本聰發(fā)表了《比特幣：一種點對點的電子現(xiàn)金系統(tǒng)》［1］一文，闡述了基于P2P網(wǎng)絡(luò)技術(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)境下能夠以較低成本建立信任的計算模式和協(xié)作模式，正在悄然改變這個世界。

1.2 共識機制

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

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

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

2.1 分布式一致性問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· 提交請求階段：

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

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

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

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

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)都采用了該算法實現(xiàn)分布式一致性，如Google的Spanner、Chubby、Megastore，還有開源的ZooKeeper等。

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

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

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

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

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

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

· 決議提出與達成：

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

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

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

2.2.3 Raft協(xié)議

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

Raft協(xié)議中每個節(jié)點可能會處于三種狀態(tài)：

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

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

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

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

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

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

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

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

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

2.3.1 拜占庭將軍問題及算法

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

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

拜占庭問題的證明：

證明前，首先看3個概念［11］：

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

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

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

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

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

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

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

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

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

2.3.2 PBFT

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

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

上圖中對于每個請求的處理過程如下：

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

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

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

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

· 返回（Reply）：對客戶端C進行反饋。

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

2.3.3 SBFT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1PoW（Proof of work）

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

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

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

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

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

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

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

PoW算法是唯一一個被成功驗證的公鏈算法，安全性最高。

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

3.2 PoS（Proof of stake）

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

3.2.1基于幣齡的 PoS

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

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

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

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

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

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

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

3.2.2 基于幣數(shù)的PoS

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

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

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

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

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

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

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

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

3.2.3 DPoS

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

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

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

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

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

3.3DAG（Directed Acyclic Graphs）

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

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

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

基于DAG的共識主要有以下幾個優(yōu)點：

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

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

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

3.4VRF（Verifiable Random Function）

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

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

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

對于相同的Input，他的Output是一定是相同的。

VRF的過程主要包括四個步驟：

VRFgen：隨機生成密鑰，生成一對非對稱加密密鑰（一對公私鑰）；

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

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

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

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

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

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

區(qū)塊鏈共識機制發(fā)展趨勢

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

4.1 從單一共識到可插拔共識

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

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

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

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

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

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

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

4.3 從確定性共識到隨機共識

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

除了上面提到的Alogrand使用了基于VRF的共識協(xié)議，Difinity和TASchain也都使用了基于VRF的共識機制，未來該趨勢上相信會有更多適用于工業(yè)級的共識協(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ū)塊鏈共識協(xié)議）及應(yīng)用，主要包括PoW、PoS、DAG和VRF。最后本文總結(jié)了區(qū)塊鏈的發(fā)展趨勢，主要體現(xiàn)三大趨勢，從單一共識向可插拔共識、從鏈?zhǔn)焦沧R向圖式共識、從確定性共識向隨機性共識。

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

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