共識算法是所有區(qū)塊鏈的基礎(chǔ)，它們構(gòu)成了區(qū)塊鏈平臺中的最重要部分。迅雷鏈采用獨創(chuàng)的同構(gòu)多鏈框架，而且通過優(yōu)化的DPoA+PBFT共識算法實現(xiàn)了秒級確認(rèn)。本文從技術(shù)層面深度剖析共識算法的背景、原理及分類，以及迅雷鏈PBFT算法的詳細(xì)解讀。
區(qū)塊鏈?zhǔn)且环N由多節(jié)點共同維護，共同信任的分布式存儲系統(tǒng)，它可以用于登記和發(fā)行數(shù)字化資產(chǎn)、產(chǎn)權(quán)憑證、積分等，并以點對點的方式進行轉(zhuǎn)賬、支付和交易。
區(qū)塊鏈系統(tǒng)與傳統(tǒng)的中心化賬本系統(tǒng)相比，具有完全公開、不可篡改、防止多重支付等優(yōu)點，并且不依賴于任何的可信第三方。
由于點對點網(wǎng)絡(luò)下存在較高的網(wǎng)絡(luò)延遲，各個節(jié)點所觀察到的事務(wù)先后順序不可能完全一致。
因此區(qū)塊鏈系統(tǒng)需要設(shè)計一種機制對在差不多時間內(nèi)發(fā)生的事務(wù)的先后順序進行共識。這種對一個時間窗口內(nèi)的事務(wù)的先后順序達(dá)成共識的算法被稱為“共識算法”。
共識算法在區(qū)塊鏈系統(tǒng)中的位置圖
共識算法通常被應(yīng)用在分布式系統(tǒng)中，區(qū)塊鏈系統(tǒng)從廣義上也可以被看做一個分布式系統(tǒng)。
共識算法保證區(qū)塊鏈系統(tǒng)中每一個節(jié)點之間事務(wù)記錄的一致性，同時起到防范系統(tǒng)遭受諸多種類的安全攻擊，包括拜占庭攻擊、女巫攻擊、51% 攻擊等。
共識算法背景
CAP定律
CAP 定律（Consistency，Availability，Partition Tolerance theorem），說的是在一個分布式計算機系統(tǒng)中，一致性，可用性和分區(qū)容錯性這三種保證無法同時得到滿足，最多滿足兩個。
其中，分區(qū)容錯性指的是在網(wǎng)絡(luò)中斷，消息丟失的情況下，系統(tǒng)照樣能夠工作；一致性說的是分布式系統(tǒng)中，所有節(jié)點在同一時刻看到同一個值；可用性說的是每個請求都會收到一個應(yīng)答，無論該應(yīng)答是成功還是失敗。
而對于分布式數(shù)據(jù)系統(tǒng)，分區(qū)容忍性是基本要求，否則就失去了價值。因此分布式數(shù)據(jù)系統(tǒng)在一致性和可用性之間取一個平衡，不可能二者同時達(dá)到。
對于迅雷鏈而言，數(shù)據(jù)在任何時刻的不一致都是一種不好的用戶體驗，因此迅雷鏈選擇保證數(shù)據(jù)絕對一致性，并以提高強一致性算法的可用性為努力的方向。
FLP 不可能原理
在網(wǎng)絡(luò)可靠，存在節(jié)點失效（即使只有一個）的最小異步模型系統(tǒng)中，不存在一個可以解決一致性問題的確定性算法。即：
異步分布式系統(tǒng)不存在任意場景下都能實現(xiàn)共識的算法。在異步網(wǎng)絡(luò)環(huán)境中只要有一個故障節(jié)點, 任何共識算法都無法保證正確結(jié)束。
因此，在迅雷鏈中，選用了實用拜占庭容錯算法（PBFT），一方面通過容錯性，降低節(jié)點失效對整個分布式系統(tǒng)的影響，另一方面采用多次重試和更換失效節(jié)點機制，降低節(jié)點間長時間失效的概率，保證系統(tǒng)的可用性。
狀態(tài)機復(fù)制
狀態(tài)機復(fù)制是一項很有效的容錯技術(shù)。
在這個模型中，程序（比如一個 apache server）被視為一個一致性狀態(tài)機，意思就是給程序一定順序的輸入請求 ，程序執(zhí)行后相關(guān)處理數(shù)據(jù)結(jié)果就會在多個節(jié)點中達(dá)成一致的狀態(tài)。
也就是說如果給予每個節(jié)點的輸入請求序列順序一致，在執(zhí)行相同操作的前提下，這些節(jié)點就會達(dá)成相同的狀態(tài)。
每個節(jié)點都包含一個狀態(tài)機，在節(jié)點間共識數(shù)據(jù)的結(jié)果將在狀態(tài)機中體現(xiàn)。狀態(tài)機中的數(shù)據(jù)將是外界獲取數(shù)據(jù)的來源。
共識算法分類
在區(qū)塊鏈系統(tǒng)中，共識算法作為保證分布式節(jié)點間數(shù)據(jù)一致性的算法，可以被分為兩大類，即概率一致性算法和絕對一致性算法。
概率一致性算法指在不同分布式節(jié)點之間，有較大概率保證節(jié)點間數(shù)據(jù)達(dá)到一致，但仍存在一定概率使得某些節(jié)點間數(shù)據(jù)不一致。
對于某一個數(shù)據(jù)點而言，數(shù)據(jù)在節(jié)點間不一致的概率會隨時間的推移逐漸降低至趨近于零，從而最終達(dá)到一致性。
例如工作量證明算法（Proof of Work, PoW）、股份證明算法（Proof of Stake, PoS）和委托股權(quán)證明算法（Delegated Proof of Stake, DPoS）都屬于概率一致性算法。
而絕對一致性算法則指在任意時間點，不同分布式節(jié)點之間的數(shù)據(jù)都會保持絕對一致，不存在不同節(jié)點間數(shù)據(jù)不一致的情況。
例如分布式系統(tǒng)中常用的 PAXOS 算法及其衍生出的 RAFT 算法等，以及拜占庭容錯類算法（類 BFT 算法）。
一般而言，回顧上面所述 CAP 原理，概率一致性算法保證了系統(tǒng)的可用性而犧牲了系統(tǒng)的一致性，絕對一致性算法則與之相反，保證了系統(tǒng)的一致性而犧牲了系統(tǒng)的可用性。
各算法之間對比如下表，★數(shù)量越多，代表相應(yīng)對比項表現(xiàn)越好。
迅雷鏈的業(yè)務(wù)需求保證分布式系統(tǒng)中的強一致性，并具備一定的容錯和防拜占庭節(jié)點作惡的能力，因此選擇類 BFT 算法作為共識算法。
在實用拜占庭容錯（PBFT）算法的基礎(chǔ)上，為了解決算法網(wǎng)絡(luò)消耗高的問題，作出了一些優(yōu)化，提高了算法的可用性。
下面首先介紹區(qū)塊鏈中最常用的強一致性算法——實用拜占庭容錯（PBFT）算法。
PBFT 算法介紹
假設(shè)系統(tǒng)中節(jié)點數(shù)量為 R=3f+1，其中 f 為系統(tǒng)中拜占庭節(jié)點的數(shù)量。
在發(fā)送消息的時候通過環(huán)境狀態(tài)、時間戳、請求、回復(fù)信息，客戶端同樣等待 2f+1 個回復(fù)，同時保證簽名、時間戳、回復(fù)信息來保證一致。
這里存在兩種情況，一種是客戶端請求超時，那就再發(fā)送一次，如果是主節(jié)點 P 出故障，那就改變環(huán)境狀態(tài)，新選一個 P 節(jié)點。保證第二次的執(zhí)行過程。
在實際的算法流程中，PBFT 算法定義三個任務(wù)階段：預(yù)準(zhǔn)備（pre-prepare）、準(zhǔn)備 (prepare)、確認(rèn) (commit)。
預(yù)準(zhǔn)備：P 分配一個系統(tǒng)序列號 ID，發(fā)送給所有 B 節(jié)點。
發(fā)送格式（環(huán)境狀態(tài)、ID、信息摘要、客戶端請求）。B 節(jié)點驗證信息摘要和客戶端請求一致，驗證當(dāng)前環(huán)境狀態(tài)編號。
準(zhǔn)備：B 節(jié)點在接收信息后加上自己的消息日志，發(fā)送至其余節(jié)點。P 和 B 節(jié)點同時驗證消息簽名，如果一致，那么就把驗證通過寫入消息日志。每個節(jié)點在準(zhǔn)備階段對每個副本節(jié)點驗證預(yù)準(zhǔn)備的消息和準(zhǔn)備消息一致性檢查完畢。
確認(rèn)：在前面兩個極端一切正常的話，在同一系統(tǒng)環(huán)境中，所有請求序號一致，驗證消息一致，簡單理解就是確認(rèn) 2f+1 個節(jié)點發(fā)送了之前發(fā)送的序號和消息。
每個節(jié)點接受確認(rèn)消息，簽名正確；消息的系統(tǒng)環(huán)境編號 V 與節(jié)點的環(huán)境編號 V 一致；消息的序號 ID 滿足序列要求。節(jié)點通過確認(rèn)至少 2f+1 個副本信息，保證整個系統(tǒng)中算法的正確性。
圖中，C 是客戶端，0、1、2、3 是分布式系統(tǒng)中的節(jié)點成員，其中由 0 節(jié)點提議區(qū)塊，，1、2、3 節(jié)點對提議出來的區(qū)塊進行投票，其中 3 節(jié)點已發(fā)生故障。我們默認(rèn) 3 發(fā)送信息為無效。那么 PBFT 算法執(zhí)行的流程如下：
C 發(fā)起一筆請求到 0 號節(jié)點。
節(jié)點 0 開始對請求排序編號，并把請求序號發(fā)送到 1、2、3 節(jié)點。
1、2 節(jié)點互相之間和 0 節(jié)點之間發(fā)送消息。
0、1、2 之間確認(rèn) 0 節(jié)點的分配序號，互相確認(rèn)。
0、1、2 確認(rèn)信息回復(fù) C。
客戶端 C 判斷收到確認(rèn)是否在 2f+1 內(nèi)，確認(rèn)結(jié)果。
在每一輪共識分三個階段達(dá)成共識：Pre-Prepare、Prepare 和 Commit，整個流程如下：
從全網(wǎng)節(jié)點選舉出一個提議節(jié)點（Proposer），新區(qū)塊由提議節(jié)點負(fù)責(zé)生成。
每個節(jié)點把客戶端發(fā)來的交易向全網(wǎng)廣播，提議節(jié)點將從網(wǎng)絡(luò)收集到需放在新區(qū)塊內(nèi)的多個交易排序后存入列表，并將該列表向全網(wǎng)廣播。
每個節(jié)點接收到交易列表后，根據(jù)排序模擬執(zhí)行這些交易。所有交易執(zhí)行完后，基于交易結(jié)果計算新區(qū)塊的哈希摘要，并向全網(wǎng)廣播。
如果一個節(jié)點收到的 2f 條來自其它節(jié)點發(fā)來的摘要都和自己的相同，就向全網(wǎng)廣播一條 commit 消息。
如果一個節(jié)點收到 2f+1 條 commit 消息，即可提交新區(qū)塊及其交易到本地的區(qū)塊鏈和狀態(tài)數(shù)據(jù)庫。
迅雷鏈共識算法
迅雷鏈采用了同構(gòu)多鏈架構(gòu)，將不同的賬戶錨定在不同的同構(gòu)鏈上，然后接入層將交易路由到發(fā)送方所在的鏈上進行區(qū)塊打包與共識。
共識成功的區(qū)塊中的交易會根據(jù)接收方所在的鏈的不同，跨鏈轉(zhuǎn)發(fā)到相應(yīng)的鏈上。若交易接收方與發(fā)送方同屬于一條鏈，則不再進行交易轉(zhuǎn)發(fā)。
在每一條同構(gòu)鏈上，驗證人節(jié)點對打包好交易的區(qū)塊進行共識。共識采用優(yōu)化過的 PBFT 算法。
以處于某一區(qū)塊高度的共識操作為例，由于共識的達(dá)成需要超過 2/3 的節(jié)點確認(rèn)，因此每一次共識可能需要多輪投票才能達(dá)成。
與傳統(tǒng)的 PBFT 算法類似，對于每一輪共識操作，又包括三個階段：Propose，Prevote 和 Precommit。
當(dāng)在某一輪達(dá)成共識 (收到 +2/3 的 Precommit 投票) 后，就會進入對下一個高度的共識，從第 0 輪開始。下面簡單介紹下詳細(xì)的步驟：
首先介紹關(guān)于鎖定區(qū)塊的概念，表示在某個特定的高度和輪數(shù)，節(jié)點對某個塊收到超過節(jié)點總數(shù) 2/3 的 Prevote 投票集合后，則此節(jié)點對于此高度此輪的區(qū)塊進行鎖定。也就是說，節(jié)點以鎖定區(qū)塊來表示對某一個區(qū)塊的認(rèn)可。
Propose 階段：系統(tǒng)中所有驗證人節(jié)點輪流作為提議者提出提議，而系統(tǒng)中非提議者的節(jié)點在收到提議后，就會進入 Prevote 階段。如果當(dāng)前節(jié)點此前存在已鎖定區(qū)塊，則還需要收集所有針對已鎖定區(qū)塊的 Prevote 投票。
PreVote 階段：當(dāng)節(jié)點進入到 Prevote 階段后，每個節(jié)點廣播自己的 PreVote 投票。
具體的，如果當(dāng)前區(qū)塊高度或投票輪數(shù)高于此前已鎖定的區(qū)塊高度或輪數(shù)，則將原鎖定的區(qū)塊進行解鎖。
如果此時節(jié)點仍含有未解鎖的區(qū)塊，則對此鎖定的區(qū)塊投 PreVote 投票?；蛘呷绻?jié)點收到合法的 Propose 區(qū)塊，則對此區(qū)塊投 ProVote 投票。
當(dāng)階段超時或者接收到大于 2/3 的針對某個塊的投票后，則節(jié)點鎖定此區(qū)塊并進入
PreCommit 階段：當(dāng)節(jié)點存在已鎖定區(qū)塊，則對此區(qū)塊投 PreCommit 投票。當(dāng)節(jié)點收到針對已鎖定區(qū)塊大于 2/3 的 PreCommit 投票是，就可以將這個塊 Commit，并且進入針對下一個高度塊的共識。
若 PreCommit 階段定時器超時，則節(jié)點保存已鎖定區(qū)塊，然后重新返回到 Propose 階段。
各節(jié)點通過在以上階段上循環(huán)，對區(qū)塊進行一致性共識。與 PBFT 算法類似，迅雷鏈共識也經(jīng)過了三階段提交，但通過引入?yún)^(qū)塊鎖定操作，通過緩存待確認(rèn)區(qū)塊，降低了未達(dá)成共識情況下重復(fù)通信區(qū)塊帶來的網(wǎng)絡(luò)壓力，從而提升了共識效率。
