“區塊鏈（Blockchain）技術是一種多方維護，通過密碼學保證傳輸和安全，實現一致、難以篡改、防止抵賴的記賬技術，稱為分布式賬本技術。而區塊鏈技術框架中非常重要的一部分是共識機制，是在不可信的分布式環境下實現數據一致性的關鍵。”

本文詳細解析了PoW、PoS、PBFT…等主流共識機制各自特點及優劣；也從單一共識向可插拔共識、從鏈式共識向圖式共識、從確定性共識向隨機性共識，歸納總結出了共識機制的發展趨勢。

概述

1.1 區塊鏈技術

2008年11月1日，中本聰發表了《比特幣：一種點對點的電子現金系統》［1］一文，闡述了基于P2P網絡技術、加密技術、時間戳技術、區塊鏈技術等的電子現金系統的構架理念，標志著比特幣的誕生。2009年初，中本聰搭建了以其論文為原型的網絡——比特幣。區塊鏈技術是比特幣網絡背后的技術基礎，是一種基礎設施。區塊鏈作為一種解決不可信分布式環境下能夠以較低成本建立信任的計算模式和協作模式，正在悄然改變這個世界。

1.2 共識機制

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

區塊鏈是一個去中心化的分布式系統，在該系統中，所有的節點都是一個全副本，維護著全部的賬本數據。這樣，當某一個或多個節點故障時，用戶可以從其他的節點讀取數據。由于系統中有多個副本，如何保證副本之間的一致性是整個分布式系統的理論核心，下面會詳細地向大家介紹傳統分布式系統和區塊鏈系統副本一致性問題。

傳統分布式系統一致性問題

2.1 分布式一致性問題

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

一致性是指分布式系統中的多個服務節點，給定一系列的操作，在約定協議的保障下，使它們對外界呈現的狀態是一致的。換句話說，也就是保證集群中所有服務節點中的數據完全相同并且能夠對某個提案（Proposal）達成一致。

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

有限性：達成一致的結果在有限的時間內完成。

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

合法性：決策的結果必須是系統中某個節點提出來的。

一般地，非學術角度，分布式系統一致性主要包括以下三類：

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

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

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

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

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

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

· 分區容錯性（Partition tolerance）：以實際效果而言，分區相當于對通信的時限要求。系統如果不能在時限內達成數據一致性，就意味著發生了分區的情況，必須就當前操作在C和A之間做出選擇。

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

隨著系統規模逐漸變大，故障的發生會是一種常態，系統的設計必須要考慮容錯（Fault Tolerant）。依據分布式系統的部署環境，容錯主要包括兩大類：一是可信環境下的分布式容錯，即我們通常說的CFT（Crash Fault Tolerant）；二是不可信環境下的分布式容錯，即我們通常說的BFT（Byzantine Fault Tolerant）。下面兩節會詳細向大家介紹一下兩類環境下的分布式一致性問題和容錯方案。

2.2 可信環境分布式一致性問題

傳統的分布式系統中，所有服務器掌握在一個公司或者組織內部，系統沒有惡意節點，所有節點都是可信的，這樣的分布式系統我們稱之為可信環境分布式系統TEDS（Trusted Environment Distributed System）。

可信環境分布式系統容錯即CFT，該類系統中，只需要考慮單機故障、磁盤故障等故障恢復場景。

可信環境分布式系統的一致性協議有很多，比較著名的包括兩階段提交協議、Paxos協議和Raft協議。

2.2.1 兩階段提交協議（2PC）

兩階段提交協議2PC（Two-phase Commit）［4］是指在計算機網絡以及數據庫領域內，為了使基于分布式系統架構下的所有節點在進行事務提交時保持一致性而設計的一種算法。

2PC協議只有在所有節點都同意提交事務后才會提交事務［5］。

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

2PC協議主要包括2個階段：

· 提交請求階段：

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

· 提交執行階段：

當第一個節點所有參與著都回復“同意”時，協調者會向所有節點發出正式“正式提交”操作請求，參與者節點正式完成操作，并釋放整個事務處理期間占用的資源，然后參與者會向協調者發送“完成”消息。協調者收到所有節點反饋“完成后”，事務完成。當第一個階段有任何一個參與者返回“終止”的消息，或者存在參與著操作超時，則協調者會向所有參與者發出“回滾操作”，協調者收到所有參與者返回“回滾完成”后取消事務。

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

2.2.2 Paxos協議

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

Paxos算法自問世以來就壟斷了可信環境分布式一致性算法。眾多分布式系統都采用了該算法實現分布式一致性，如Google的Spanner、Chubby、Megastore，還有開源的ZooKeeper等。

Paxos協議將系統中節點分為三類：

· 提議者（Proposer）： Proposer 負責提出提案，包括提案標號和提案內容。

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

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

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

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

· 決議提出與達成：

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

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

· 決議的發布（Publish）：當提案已經達成后，Proposer會將該提案發送給所有的Learner。

2.2.3 Raft協議

Raft也是一種可信環境分布式一致性算法［9］。相比于Paxos算法，Raft更加容易理解和容易實現，他強化了領導人的概念，將整個分布式一致性問題抽象成了兩大階段，領導人選舉（Leader Election）和日志復制（Log Replication）。

Raft協議中每個節點可能會處于三種狀態：

· 領導者狀態（Leader）：Leader負責處理客戶端的請求并將事務同步給Follwer。

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

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

其狀態轉換圖如下所示：

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

2.3 不可信環境分布式一致性問題

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

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

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

2.3.1 拜占庭將軍問題及算法

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

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

拜占庭問題的證明：

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

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

· 活躍度（Liveness）：是指在共識決策的過程中保持活躍的節點，不能出現卡死或者無響應的狀態。

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

證明過程如下，假設系統中共有N個節點，f個拜占庭節點，仲裁組節點為Q。

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

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

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

4. 當N=3f+1時，Q》=2f + 1;

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

2.3.2 PBFT

傳統的BFT算法復雜度太高，Castro和Liskov于1999年提出了PBFT（Practical Byzantine Fault Tolerance）實用拜占庭容錯算法［12］，該算法能夠實現拜占庭容錯，同時能夠大大提升拜占庭容錯的效率。

PBFT是一種基于副本狀態機復制的算法。將不可信環境一致性達成分成3個階段，分別是預準備、準備和確認。如下圖所示：

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

· 請求（request）：客戶端c向服務器0發起一個請求；

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

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

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

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

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

2.3.3 SBFT

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

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

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

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

· 通過冗余服務器進行快速路徑；

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

· 客戶端向主服務器發送操作請求；

· 主服務器收集客戶端請求，創建決策塊，并將此塊作為預準備消息轉發給副本；

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

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

· 一旦副本接受到提交證明，它會提交決策區塊，并啟動執行協議；

當副本在提交決策區塊前，他需要完成序列塊的執行，并對新的狀態進行閾值簽名，然后將其發送給E-收集器；

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

目前SBFT已經實現了最大209個節點的測試網絡。相比于PBFT，在擴展性上提高了2倍。

2.3.4全球部署不可信環境

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

區塊鏈共識機制及其應用

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

3.1PoW（Proof of work）

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

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

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

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

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

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

為了避免硬件加速等因素導致區塊打包過快，PoW會依據出塊的時間調整打包區塊的難度。如果生成速度太快，難度就會增加。

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

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

3.2 PoS（Proof of stake）

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

3.2.1基于幣齡的 PoS

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

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

PoS下生成區塊如下圖所示：

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

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

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

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

3.2.2 基于幣數的PoS

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

為了進一步提供PoS系統的安全性，提升節點的在線時長。2014年Pavel Vasin提出了黑幣，其PoS算法也被稱為PoS2.0［17］。

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

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

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

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

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

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

3.2.3 DPoS

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

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

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

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

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

3.3DAG（Directed Acyclic Graphs）

DAG第一次被提出與區塊鏈結合是在Nxt社區，為的是解決區塊鏈的效率問題。DAG是一種圖狀的區塊鏈。由于其獨特區塊結構，DAG內在地支持高可擴展性，得到了廣泛的應用。

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

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

基于DAG的共識主要有以下幾個優點：

交易速度快：DAG 的并行化結構和blockless的設計會提高系統的效率，交易速度大大提升。

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

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

3.4VRF（Verifiable Random Function）

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

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

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

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

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

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

VRFval：生成隨機數輸出；

VRFproof：隨機數輸出的零知識證明；

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

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

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

Alogrand通過VRF實現了礦工選擇的不可預測性，實現了區塊鏈的去中心化；并且每個區塊隨機產生，不需要競爭出塊，提升了系統的擴展性；PoW、PoS當惡意節點積攢到一定數量時就可以控制網絡，一般地是通過博弈的方式來實現網絡穩定性和安全性保障，Alogrand隨機產生區塊生產者，所以即使是惡意節點，也無法隨意控制網絡。

區塊鏈共識機制發展趨勢

自從2018年中本聰發布比特幣以來，區塊鏈系統已經經歷了10年的發展。共識算法的發展也進入了百花齊放的時期。縱觀區塊鏈共識協議的發展過程，主要體現以下幾大趨勢。

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

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

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

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

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

4.2 從鏈式共識到圖式共識

一般地，區塊鏈是一種鏈式結構，區塊只能沿著一條鏈生長，效率較低。隨著共識的發展，有人提出使用DAG的方式，所謂DAG就是有向無環圖。基于這種思想，可以有很多新的方式，比如可以并發地進行區塊打包，從而提高區塊鏈的擴展能力。

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

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

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

除了上面提到的Alogrand使用了基于VRF的共識協議，Difinity和TASchain也都使用了基于VRF的共識機制，未來該趨勢上相信會有更多適用于工業級的共識協議誕生。

總結與展望

本文從分布式一致性問題切入，分別討論了可信環境分布式系統和不可信環境分布式系統的一致性問題。在可信環境分布式系統一致性問題中，介紹了經典的2PC、Paxos和Raft協議。在不可信環境分布式系統一致性問題中，介紹了拜占庭教軍問題及PBFT算法，并介紹了公鏈環境下新型一致性協議（即區塊鏈共識協議）及應用，主要包括PoW、PoS、DAG和VRF。最后本文總結了區塊鏈的發展趨勢，主要體現三大趨勢，從單一共識向可插拔共識、從鏈式共識向圖式共識、從確定性共識向隨機性共識。

區塊鏈是一個不可信環境分布式系統，區塊鏈共識是不可信環境分布式系統一致性的一個重要的研究方向。近年來，區塊鏈共識也百花齊放，各種改進算法爭相被提出。本文討論的共識算法只是其中的一個子集。

未來，隨著區塊鏈技術的進一步發展，尤其是伴隨著底層賬本結構的進一步優化，勢必會涌現出更多的新興的共識算法，本文提到的IOTA的基于DAG的共識只是其中一種。同時，隨著技術的進一步深入，區塊鏈共識的評估標準也一定會進一步規范。
來源： 百度超級鏈?