當第一個節點所有參與著都回復“同意”時，協調者會向所有節點發出正式“正式提交”操作請求，參與者節點正式完成操作，並釋放整個事務處理期間佔用的資源，然後參與者會向協調者傳送“完成”訊息。協調者收到所有節點反饋“完成後”，事務完成。當第一個階段有任何一個參與者返回“終止”的訊息，或者存在參與著操作超時，則協調者會向所有參與者發出“回滾操作”，協調者收到所有參與者返回“回滾完成”後取消事務。
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的共識只是其中一種。同時，隨著技術的進一步深入，區塊鏈共識的評估標準也一定會進一步規範。
參考資料
[1].SatoshiNakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System,2008.
[2].wikipedia,https://zh.m.wikipedia.org/zh-hans/%E5%85%B1%E8%AD%98%E6%A9%9F%E5%88%B6,2008.
[3].wikipedia,https://en.wikipedia.org/wiki/CAP_theorem,2010.
[4].wikipedia,https://en.wikipedia.org/wiki/Two-phase_commit_protocol,2004.
[5].exploredatabase,http://www.exploredatabase.com/2014/07/two-phase-commit-protocol-in-pictures.html,2014.
[6].LeslieLamport, The Part-Time Parliament, 2000,
[7].LeslieLamport, Paxos Made Simple, 2001.
[8].LeslieLamport, Fast Paxos, 2006.
[9].DiegoOngaro, John Ousterhout, In Search of an Understandable Consensus Algorithm,2014.
[10].LeslieLamport, The Byzatine Generals Problem, 1982.
[11].MICHAEL J.FISCHER, NANCY A. LYNCH, Impossibility of Distributed Consensus with One FaultyProcess, 1985.
[12].MiguelCastro,Barbara Liskov, Practical Byzantine Fault Tolerance, 1999.
[13]. GG Gueta, SBFT:a Scalable and Decentralized Trust Infrastructure, 2019.
[14].CynthiaDwork, Pricing via Processing or Combatting Junk Mail.
[15].bitcoin, https://en.bitcoin.it/wiki/Proof_of_Stake,2012.
[16].peercoin,https://docs.peercoin.net/#/proof-of-stake, 2012.
[17].PavelVasin, BlackCoin’s Proof-of-Stake Protocol v2, 2014
[18].bitshares,http://docs.bitshares.org/bitshares/dpos.html.
[19].譚待，肖偉等, 百度區塊鏈白皮書V1.0, 2018.
[20].SilvioMicali, Michael Rabin,Salil Vadhan, Verifiable Random Functions, 1999.
[21].Jing Chen,Silvio Micali, ALGORAND, 2017.
本文已被收錄在《區塊鏈應用藍皮書：中國區塊鏈應用發展研究報告（2019）》技術篇中，該書由人民網人民創投區塊鏈研究院策劃編撰，社會科學文獻出版社出版發行。
