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

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

概述

1.1 區(qū)塊鏈技術

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

1.2 共識機制

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

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

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

2.1 分布式一致性問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

隨著系統(tǒng)規(guī)模逐漸變大，故障的發(fā)生會是一種常態(tài)，系統(tǒng)的設計必須要考慮容錯（Fault Tolerant）。依據分布式系統(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)中，所有服務器掌握在一個公司或者組織內部，系統(tǒng)沒有惡意節(jié)點，所有節(jié)點都是可信的，這樣的分布式系統(tǒng)我們稱之為可信環(huán)境分布式系統(tǒng)TEDS（Trusted Environment Distributed System）。

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

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

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

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

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

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

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

· 提交請求階段：

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

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

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

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

2.2.2 Paxos協議

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

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

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

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

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

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

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

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

· 決議提出與達成：

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

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

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

2.2.3 Raft協議

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

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

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

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

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

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

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

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

當一個分布式系統(tǒng)中節(jié)點的維護方不屬于某個公司單獨所有，節(jié)點的參與方的利益互不相同時，就可能會出現節(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é)會向大家介紹一下著名的拜占庭問題及相應算法。區(qū)塊鏈系統(tǒng)是一個不可性環(huán)境的分布式系統(tǒng)，自2008年比特幣系統(tǒng)創(chuàng)建以來，一批又一批的學者和科創(chuàng)團隊投入該領域分布式一致性問題的研究，創(chuàng)新性地引入了激勵以及博弈的思想來促使系統(tǒng)達成一致。經典的算法有PoW、PoS、DAG、VRF等，這些內容將在下一章進行詳細地介紹。

2.3.1 拜占庭將軍問題及算法

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

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

拜占庭問題的證明：

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

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

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

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

證明過程如下，假設系統(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. 當N=3f+1時，Q》=2f + 1;

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

2.3.2 PBFT

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

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

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

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

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

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

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

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

PBFT能夠有效地實現拜占庭容錯，且由于其將容錯分為明確的3個階段，工程上更容易實現。但是他有個比較大的缺點是系統(tǒng)中的節(jié)點規(guī)模不能很大，因為系統(tǒng)中的每個節(jié)點都要頻繁地和其他說有節(jié)點進行通信，當系統(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ā)送一個帶簽名的消息，從而將每個客戶端的線性成本降低為一條消息；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1PoW（Proof of work）

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

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

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

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

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

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

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

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

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

3.2 PoS（Proof of stake）

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

3.2.1基于幣齡的 PoS

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

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

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

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

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

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

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

3.2.2 基于幣數的PoS

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

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

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

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

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

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

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

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

3.2.3 DPoS

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

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

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

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

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

3.3DAG（Directed Acyclic Graphs）

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

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

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

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

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

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

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

3.4VRF（Verifiable Random Function）

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

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

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

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

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

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

VRFval：生成隨機數輸出；

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

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

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

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

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

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

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

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

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

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

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

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

4.2 從鏈式共識到圖式共識

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

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

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

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

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

總結與展望

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

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

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