共識(shí)算法是所有區(qū)塊鏈的基礎(chǔ)，它們構(gòu)成了區(qū)塊鏈平臺(tái)中的最重要部分。迅雷鏈采用獨(dú)創(chuàng)的同構(gòu)多鏈框架，而且通過(guò)優(yōu)化的DPoA+PBFT共識(shí)算法實(shí)現(xiàn)了秒級(jí)確認(rèn)。本文從技術(shù)層面深度剖析共識(shí)算法的背景、原理及分類(lèi)，以及迅雷鏈PBFT算法的詳細(xì)解讀。

區(qū)塊鏈?zhǔn)且环N由多節(jié)點(diǎn)共同維護(hù)，共同信任的分布式存儲(chǔ)系統(tǒng)，它可以用于登記和發(fā)行數(shù)字化資產(chǎn)、產(chǎn)權(quán)憑證、積分等，并以點(diǎn)對(duì)點(diǎn)的方式進(jìn)行轉(zhuǎn)賬、支付和交易。

區(qū)塊鏈系統(tǒng)與傳統(tǒng)的中心化賬本系統(tǒng)相比，具有完全公開(kāi)、不可篡改、防止多重支付等優(yōu)點(diǎn)，并且不依賴(lài)于任何的可信第三方。

由于點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)下存在較高的網(wǎng)絡(luò)延遲，各個(gè)節(jié)點(diǎn)所觀察到的事務(wù)先后順序不可能完全一致。

因此區(qū)塊鏈系統(tǒng)需要設(shè)計(jì)一種機(jī)制對(duì)在差不多時(shí)間內(nèi)發(fā)生的事務(wù)的先后順序進(jìn)行共識(shí)。這種對(duì)一個(gè)時(shí)間窗口內(nèi)的事務(wù)的先后順序達(dá)成共識(shí)的算法被稱(chēng)為“共識(shí)算法”。

共識(shí)算法在區(qū)塊鏈系統(tǒng)中的位置圖

共識(shí)算法通常被應(yīng)用在分布式系統(tǒng)中，區(qū)塊鏈系統(tǒng)從廣義上也可以被看做一個(gè)分布式系統(tǒng)。

共識(shí)算法保證區(qū)塊鏈系統(tǒng)中每一個(gè)節(jié)點(diǎn)之間事務(wù)記錄的一致性，同時(shí)起到防范系統(tǒng)遭受諸多種類(lèi)的安全攻擊，包括拜占庭攻擊、女巫攻擊、51% 攻擊等。

共識(shí)算法背景

CAP定律

CAP 定律（Consistency，Availability，Partition Tolerance theorem），說(shuō)的是在一個(gè)分布式計(jì)算機(jī)系統(tǒng)中，一致性，可用性和分區(qū)容錯(cuò)性這三種保證無(wú)法同時(shí)得到滿(mǎn)足，最多滿(mǎn)足兩個(gè)。

其中，分區(qū)容錯(cuò)性指的是在網(wǎng)絡(luò)中斷，消息丟失的情況下，系統(tǒng)照樣能夠工作；一致性說(shuō)的是分布式系統(tǒng)中，所有節(jié)點(diǎn)在同一時(shí)刻看到同一個(gè)值；可用性說(shuō)的是每個(gè)請(qǐng)求都會(huì)收到一個(gè)應(yīng)答，無(wú)論該應(yīng)答是成功還是失敗。

而對(duì)于分布式數(shù)據(jù)系統(tǒng)，分區(qū)容忍性是基本要求，否則就失去了價(jià)值。因此分布式數(shù)據(jù)系統(tǒng)在一致性和可用性之間取一個(gè)平衡，不可能二者同時(shí)達(dá)到。

對(duì)于迅雷鏈而言，數(shù)據(jù)在任何時(shí)刻的不一致都是一種不好的用戶(hù)體驗(yàn)，因此迅雷鏈選擇保證數(shù)據(jù)絕對(duì)一致性，并以提高強(qiáng)一致性算法的可用性為努力的方向。

FLP 不可能原理

在網(wǎng)絡(luò)可靠，存在節(jié)點(diǎn)失效（即使只有一個(gè)）的最小異步模型系統(tǒng)中，不存在一個(gè)可以解決一致性問(wèn)題的確定性算法。即：

異步分布式系統(tǒng)不存在任意場(chǎng)景下都能實(shí)現(xiàn)共識(shí)的算法。在異步網(wǎng)絡(luò)環(huán)境中只要有一個(gè)故障節(jié)點(diǎn), 任何共識(shí)算法都無(wú)法保證正確結(jié)束。

因此，在迅雷鏈中，選用了實(shí)用拜占庭容錯(cuò)算法（PBFT），一方面通過(guò)容錯(cuò)性，降低節(jié)點(diǎn)失效對(duì)整個(gè)分布式系統(tǒng)的影響，另一方面采用多次重試和更換失效節(jié)點(diǎn)機(jī)制，降低節(jié)點(diǎn)間長(zhǎng)時(shí)間失效的概率，保證系統(tǒng)的可用性。

狀態(tài)機(jī)復(fù)制

狀態(tài)機(jī)復(fù)制是一項(xiàng)很有效的容錯(cuò)技術(shù)。

在這個(gè)模型中，程序（比如一個(gè) apache server）被視為一個(gè)一致性狀態(tài)機(jī)，意思就是給程序一定順序的輸入請(qǐng)求 ，程序執(zhí)行后相關(guān)處理數(shù)據(jù)結(jié)果就會(huì)在多個(gè)節(jié)點(diǎn)中達(dá)成一致的狀態(tài)。

也就是說(shuō)如果給予每個(gè)節(jié)點(diǎn)的輸入請(qǐng)求序列順序一致，在執(zhí)行相同操作的前提下，這些節(jié)點(diǎn)就會(huì)達(dá)成相同的狀態(tài)。

每個(gè)節(jié)點(diǎn)都包含一個(gè)狀態(tài)機(jī)，在節(jié)點(diǎn)間共識(shí)數(shù)據(jù)的結(jié)果將在狀態(tài)機(jī)中體現(xiàn)。狀態(tài)機(jī)中的數(shù)據(jù)將是外界獲取數(shù)據(jù)的來(lái)源。

共識(shí)算法分類(lèi)

在區(qū)塊鏈系統(tǒng)中，共識(shí)算法作為保證分布式節(jié)點(diǎn)間數(shù)據(jù)一致性的算法，可以被分為兩大類(lèi)，即概率一致性算法和絕對(duì)一致性算法。

概率一致性算法指在不同分布式節(jié)點(diǎn)之間，有較大概率保證節(jié)點(diǎn)間數(shù)據(jù)達(dá)到一致，但仍存在一定概率使得某些節(jié)點(diǎn)間數(shù)據(jù)不一致。

對(duì)于某一個(gè)數(shù)據(jù)點(diǎn)而言，數(shù)據(jù)在節(jié)點(diǎn)間不一致的概率會(huì)隨時(shí)間的推移逐漸降低至趨近于零，從而最終達(dá)到一致性。

例如工作量證明算法（Proof of Work, PoW）、股份證明算法（Proof of Stake, PoS）和委托股權(quán)證明算法（Delegated Proof of Stake, DPoS）都屬于概率一致性算法。

而絕對(duì)一致性算法則指在任意時(shí)間點(diǎn)，不同分布式節(jié)點(diǎn)之間的數(shù)據(jù)都會(huì)保持絕對(duì)一致，不存在不同節(jié)點(diǎn)間數(shù)據(jù)不一致的情況。

例如分布式系統(tǒng)中常用的 PAXOS 算法及其衍生出的 RAFT 算法等，以及拜占庭容錯(cuò)類(lèi)算法（類(lèi) BFT 算法）。

一般而言，回顧上面所述 CAP 原理，概率一致性算法保證了系統(tǒng)的可用性而犧牲了系統(tǒng)的一致性，絕對(duì)一致性算法則與之相反，保證了系統(tǒng)的一致性而犧牲了系統(tǒng)的可用性。

各算法之間對(duì)比如下表，★數(shù)量越多，代表相應(yīng)對(duì)比項(xiàng)表現(xiàn)越好。

迅雷鏈的業(yè)務(wù)需求保證分布式系統(tǒng)中的強(qiáng)一致性，并具備一定的容錯(cuò)和防拜占庭節(jié)點(diǎn)作惡的能力，因此選擇類(lèi) BFT 算法作為共識(shí)算法。

在實(shí)用拜占庭容錯(cuò)（PBFT）算法的基礎(chǔ)上，為了解決算法網(wǎng)絡(luò)消耗高的問(wèn)題，作出了一些優(yōu)化，提高了算法的可用性。

下面首先介紹區(qū)塊鏈中最常用的強(qiáng)一致性算法——實(shí)用拜占庭容錯(cuò)（PBFT）算法。

PBFT 算法介紹

假設(shè)系統(tǒng)中節(jié)點(diǎn)數(shù)量為 R=3f+1，其中 f 為系統(tǒng)中拜占庭節(jié)點(diǎn)的數(shù)量。

在發(fā)送消息的時(shí)候通過(guò)環(huán)境狀態(tài)、時(shí)間戳、請(qǐng)求、回復(fù)信息，客戶(hù)端同樣等待 2f+1 個(gè)回復(fù)，同時(shí)保證簽名、時(shí)間戳、回復(fù)信息來(lái)保證一致。

這里存在兩種情況，一種是客戶(hù)端請(qǐng)求超時(shí)，那就再發(fā)送一次，如果是主節(jié)點(diǎn) P 出故障，那就改變環(huán)境狀態(tài)，新選一個(gè) P 節(jié)點(diǎn)。保證第二次的執(zhí)行過(guò)程。

在實(shí)際的算法流程中，PBFT 算法定義三個(gè)任務(wù)階段：預(yù)準(zhǔn)備（pre-prepare）、準(zhǔn)備 (prepare)、確認(rèn) (commit)。

預(yù)準(zhǔn)備：P 分配一個(gè)系統(tǒng)序列號(hào) ID，發(fā)送給所有 B 節(jié)點(diǎn)。

發(fā)送格式（環(huán)境狀態(tài)、ID、信息摘要、客戶(hù)端請(qǐng)求）。B 節(jié)點(diǎn)驗(yàn)證信息摘要和客戶(hù)端請(qǐng)求一致，驗(yàn)證當(dāng)前環(huán)境狀態(tài)編號(hào)。

準(zhǔn)備：B 節(jié)點(diǎn)在接收信息后加上自己的消息日志，發(fā)送至其余節(jié)點(diǎn)。P 和 B 節(jié)點(diǎn)同時(shí)驗(yàn)證消息簽名，如果一致，那么就把驗(yàn)證通過(guò)寫(xiě)入消息日志。每個(gè)節(jié)點(diǎn)在準(zhǔn)備階段對(duì)每個(gè)副本節(jié)點(diǎn)驗(yàn)證預(yù)準(zhǔn)備的消息和準(zhǔn)備消息一致性檢查完畢。

確認(rèn)：在前面兩個(gè)極端一切正常的話(huà)，在同一系統(tǒng)環(huán)境中，所有請(qǐng)求序號(hào)一致，驗(yàn)證消息一致，簡(jiǎn)單理解就是確認(rèn) 2f+1 個(gè)節(jié)點(diǎn)發(fā)送了之前發(fā)送的序號(hào)和消息。

每個(gè)節(jié)點(diǎn)接受確認(rèn)消息，簽名正確；消息的系統(tǒng)環(huán)境編號(hào) V 與節(jié)點(diǎn)的環(huán)境編號(hào) V 一致；消息的序號(hào) ID 滿(mǎn)足序列要求。節(jié)點(diǎn)通過(guò)確認(rèn)至少 2f+1 個(gè)副本信息，保證整個(gè)系統(tǒng)中算法的正確性。

圖中，C 是客戶(hù)端，0、1、2、3 是分布式系統(tǒng)中的節(jié)點(diǎn)成員，其中由 0 節(jié)點(diǎn)提議區(qū)塊，，1、2、3 節(jié)點(diǎn)對(duì)提議出來(lái)的區(qū)塊進(jìn)行投票，其中 3 節(jié)點(diǎn)已發(fā)生故障。我們默認(rèn) 3 發(fā)送信息為無(wú)效。那么 PBFT 算法執(zhí)行的流程如下：

C 發(fā)起一筆請(qǐng)求到 0 號(hào)節(jié)點(diǎn)。

節(jié)點(diǎn) 0 開(kāi)始對(duì)請(qǐng)求排序編號(hào)，并把請(qǐng)求序號(hào)發(fā)送到 1、2、3 節(jié)點(diǎn)。

1、2 節(jié)點(diǎn)互相之間和 0 節(jié)點(diǎn)之間發(fā)送消息。

0、1、2 之間確認(rèn) 0 節(jié)點(diǎn)的分配序號(hào)，互相確認(rèn)。

0、1、2 確認(rèn)信息回復(fù) C。

客戶(hù)端 C 判斷收到確認(rèn)是否在 2f+1 內(nèi)，確認(rèn)結(jié)果。

在每一輪共識(shí)分三個(gè)階段達(dá)成共識(shí)：Pre-Prepare、Prepare 和 Commit，整個(gè)流程如下：

從全網(wǎng)節(jié)點(diǎn)選舉出一個(gè)提議節(jié)點(diǎn)（Proposer），新區(qū)塊由提議節(jié)點(diǎn)負(fù)責(zé)生成。

每個(gè)節(jié)點(diǎn)把客戶(hù)端發(fā)來(lái)的交易向全網(wǎng)廣播，提議節(jié)點(diǎn)將從網(wǎng)絡(luò)收集到需放在新區(qū)塊內(nèi)的多個(gè)交易排序后存入列表，并將該列表向全網(wǎng)廣播。

每個(gè)節(jié)點(diǎn)接收到交易列表后，根據(jù)排序模擬執(zhí)行這些交易。所有交易執(zhí)行完后，基于交易結(jié)果計(jì)算新區(qū)塊的哈希摘要，并向全網(wǎng)廣播。

如果一個(gè)節(jié)點(diǎn)收到的 2f 條來(lái)自其它節(jié)點(diǎn)發(fā)來(lái)的摘要都和自己的相同，就向全網(wǎng)廣播一條 commit 消息。

如果一個(gè)節(jié)點(diǎn)收到 2f+1 條 commit 消息，即可提交新區(qū)塊及其交易到本地的區(qū)塊鏈和狀態(tài)數(shù)據(jù)庫(kù)。

迅雷鏈共識(shí)算法

迅雷鏈采用了同構(gòu)多鏈架構(gòu)，將不同的賬戶(hù)錨定在不同的同構(gòu)鏈上，然后接入層將交易路由到發(fā)送方所在的鏈上進(jìn)行區(qū)塊打包與共識(shí)。

共識(shí)成功的區(qū)塊中的交易會(huì)根據(jù)接收方所在的鏈的不同，跨鏈轉(zhuǎn)發(fā)到相應(yīng)的鏈上。若交易接收方與發(fā)送方同屬于一條鏈，則不再進(jìn)行交易轉(zhuǎn)發(fā)。

在每一條同構(gòu)鏈上，驗(yàn)證人節(jié)點(diǎn)對(duì)打包好交易的區(qū)塊進(jìn)行共識(shí)。共識(shí)采用優(yōu)化過(guò)的 PBFT 算法。

以處于某一區(qū)塊高度的共識(shí)操作為例，由于共識(shí)的達(dá)成需要超過(guò) 2/3 的節(jié)點(diǎn)確認(rèn)，因此每一次共識(shí)可能需要多輪投票才能達(dá)成。

與傳統(tǒng)的 PBFT 算法類(lèi)似，對(duì)于每一輪共識(shí)操作，又包括三個(gè)階段：Propose，Prevote 和 Precommit。

當(dāng)在某一輪達(dá)成共識(shí) (收到 +2/3 的 Precommit 投票) 后，就會(huì)進(jìn)入對(duì)下一個(gè)高度的共識(shí)，從第 0 輪開(kāi)始。下面簡(jiǎn)單介紹下詳細(xì)的步驟：

首先介紹關(guān)于鎖定區(qū)塊的概念，表示在某個(gè)特定的高度和輪數(shù)，節(jié)點(diǎn)對(duì)某個(gè)塊收到超過(guò)節(jié)點(diǎn)總數(shù) 2/3 的 Prevote 投票集合后，則此節(jié)點(diǎn)對(duì)于此高度此輪的區(qū)塊進(jìn)行鎖定。也就是說(shuō)，節(jié)點(diǎn)以鎖定區(qū)塊來(lái)表示對(duì)某一個(gè)區(qū)塊的認(rèn)可。

Propose 階段：系統(tǒng)中所有驗(yàn)證人節(jié)點(diǎn)輪流作為提議者提出提議，而系統(tǒng)中非提議者的節(jié)點(diǎn)在收到提議后，就會(huì)進(jìn)入 Prevote 階段。如果當(dāng)前節(jié)點(diǎn)此前存在已鎖定區(qū)塊，則還需要收集所有針對(duì)已鎖定區(qū)塊的 Prevote 投票。

PreVote 階段：當(dāng)節(jié)點(diǎn)進(jìn)入到 Prevote 階段后，每個(gè)節(jié)點(diǎn)廣播自己的 PreVote 投票。

具體的，如果當(dāng)前區(qū)塊高度或投票輪數(shù)高于此前已鎖定的區(qū)塊高度或輪數(shù)，則將原鎖定的區(qū)塊進(jìn)行解鎖。

如果此時(shí)節(jié)點(diǎn)仍含有未解鎖的區(qū)塊，則對(duì)此鎖定的區(qū)塊投 PreVote 投票?；蛘呷绻?jié)點(diǎn)收到合法的 Propose 區(qū)塊，則對(duì)此區(qū)塊投 ProVote 投票。

當(dāng)階段超時(shí)或者接收到大于 2/3 的針對(duì)某個(gè)塊的投票后，則節(jié)點(diǎn)鎖定此區(qū)塊并進(jìn)入

PreCommit 階段：當(dāng)節(jié)點(diǎn)存在已鎖定區(qū)塊，則對(duì)此區(qū)塊投 PreCommit 投票。當(dāng)節(jié)點(diǎn)收到針對(duì)已鎖定區(qū)塊大于 2/3 的 PreCommit 投票是，就可以將這個(gè)塊 Commit，并且進(jìn)入針對(duì)下一個(gè)高度塊的共識(shí)。

若 PreCommit 階段定時(shí)器超時(shí)，則節(jié)點(diǎn)保存已鎖定區(qū)塊，然后重新返回到 Propose 階段。

各節(jié)點(diǎn)通過(guò)在以上階段上循環(huán)，對(duì)區(qū)塊進(jìn)行一致性共識(shí)。與 PBFT 算法類(lèi)似，迅雷鏈共識(shí)也經(jīng)過(guò)了三階段提交，但通過(guò)引入?yún)^(qū)塊鎖定操作，通過(guò)緩存待確認(rèn)區(qū)塊，降低了未達(dá)成共識(shí)情況下重復(fù)通信區(qū)塊帶來(lái)的網(wǎng)絡(luò)壓力，從而提升了共識(shí)效率。