共識算法是區(qū)塊鏈技術(shù)的核心要素，也是近年來分布式系統(tǒng)研究的熱點。

一、前言

眾所周知，區(qū)塊鏈架構(gòu)是一種分布式的架構(gòu)。其部署模式有公共鏈、聯(lián)盟鏈、私有鏈三種，對應(yīng)的是去中心化分布式系統(tǒng)、部分去中心化分布式系統(tǒng)和弱中心分布式系統(tǒng)。

分布式系統(tǒng)中，多個主機(jī)通過異步通信方式組成網(wǎng)絡(luò)集群。在這樣的一個異步系統(tǒng)中，需要主機(jī)之間進(jìn)行狀態(tài)復(fù)制，以保證每個主機(jī)達(dá)成一致的狀態(tài)共識。然而，異步系統(tǒng)中，可能出現(xiàn)無法通信的故障主機(jī)，而主機(jī)的性能可能下降，網(wǎng)絡(luò)可能擁塞，這些可能導(dǎo)致錯誤信息在系統(tǒng)內(nèi)傳播。因此需要在默認(rèn)不可靠的異步網(wǎng)絡(luò)中定義容錯協(xié)議，以確保各主機(jī)達(dá)成安全可靠的狀態(tài)共識。

共識理解起來很簡單，就是大家都達(dá)成一致的意思。在現(xiàn)實生活中，有很多達(dá)成共識的場景。比如我們開會討論，需要得出一個結(jié)果；雙方或多方簽訂一份合作協(xié)議時；又或者是哈士奇……呃，不好意思，跑遠(yuǎn)了。

而在區(qū)塊鏈系統(tǒng)中，每個節(jié)點必須要做的事情就是讓自己的賬本跟其他節(jié)點的賬本保持一致。如果是在傳統(tǒng)的軟件結(jié)構(gòu)中，這根本不算事兒，因為有一個中心服務(wù)器，就像是一個公司老板發(fā)布一個通知，員工就照著做一樣。可是區(qū)塊鏈?zhǔn)且粋€分布式的對等網(wǎng)絡(luò)結(jié)構(gòu)，在這個結(jié)構(gòu)中沒有哪個節(jié)點是“老大”，什么事兒都得一起商量。

所以在區(qū)塊鏈系統(tǒng)中，如何讓每個節(jié)點通過一個規(guī)則將各自的數(shù)據(jù)保持一致是一個很關(guān)鍵的問題，這個問題的解決方案就是制定一套共識算法，實現(xiàn)不同賬本節(jié)點上的賬本數(shù)據(jù)的一致性和正確性。這就需要借鑒已有的在分布式系統(tǒng)中實現(xiàn)狀態(tài)共識的算法，確定網(wǎng)絡(luò)中選擇記賬節(jié)點的機(jī)制，以及如何保障賬本數(shù)據(jù)在全網(wǎng)中形成正確、一致的共識。

在20世紀(jì)80年代出現(xiàn)的分布式系統(tǒng)共識算法，是區(qū)塊鏈共識算法的基礎(chǔ)。下面我們就從基本的拜占庭容錯技術(shù)入手，往后逐步介紹適合于私有鏈/聯(lián)盟鏈和公共鏈的共識算法。

二、拜占庭容錯技術(shù)

拜占庭容錯技術(shù)（Byzantine Fault Tolerance， BFT）是一類分布式計算領(lǐng)域的容錯技術(shù)。拜占庭假設(shè)是對現(xiàn)實世界的模型化，由于硬件錯誤、網(wǎng)絡(luò)擁塞或中斷以及遭到惡意攻擊等原因，計算機(jī)和網(wǎng)絡(luò)可能出現(xiàn)不可預(yù)料的行為。拜占庭容錯技術(shù)被設(shè)計用來處理這些異常行為，并滿足所要解決的問題的規(guī)范要求。

1、拜占庭將軍問題

拜占庭容錯技術(shù)來源于拜占庭將軍問題（點此了解：https://ethfans.org/tinyxiong/articles/874）。拜占庭將軍問題（Byzantine Generals Problem），是由萊斯利·蘭波特在其同名論文中提出的分布式對等網(wǎng)絡(luò)通信容錯問題。

這里我們給出分布式計算機(jī)中有關(guān)拜占庭缺陷和故障的兩個定義：

定義1：拜占庭缺陷（Byzantine Fault）：

任何觀察者從不同角度看，表現(xiàn)出不同癥狀的缺陷。

定義2：拜占庭故障（Byzantine Failure）：

在需要共識的系統(tǒng)中由于拜占庭缺陷導(dǎo)致喪失系統(tǒng)服務(wù)。

不是所有的缺陷或故障都能稱作拜占庭缺陷或故障，比如死機(jī)、丟消息這樣的。在分布式系統(tǒng)中，特別是在區(qū)塊鏈網(wǎng)絡(luò)環(huán)境中，也和拜占庭將軍的環(huán)境類似，有運(yùn)行正常的服務(wù)器（類似忠誠的拜占庭將軍），還有破壞者或者中木馬的服務(wù)器（類似叛變的拜占庭將軍）。共識算法的核心是在正常的節(jié)點間形成對網(wǎng)絡(luò)狀態(tài)的共識。

2、拜占庭容錯系統(tǒng)

通常，發(fā)生故障節(jié)點被稱為拜占庭節(jié)點，而正常的節(jié)點即為非拜占庭節(jié)點。

拜占庭容錯系統(tǒng)是一個擁有n 臺節(jié)點的系統(tǒng)，整個系統(tǒng)對于每一個請求，滿足以下條件：

1）所有非拜占庭節(jié)點使用相同的輸入信息，產(chǎn)生同樣的結(jié)果；

2）如果輸入的信息正確，那么所有非拜占庭節(jié)點必須接收這個信息，并計算相應(yīng)的結(jié)果。

拜占庭系統(tǒng)普遍采用的假設(shè)條件包括：

1）拜占庭節(jié)點的行為可以是任意的，拜占庭節(jié)點之間可以共謀；

2）節(jié)點之間的錯誤是不相關(guān)的；

3）節(jié)點之間通過異步網(wǎng)絡(luò)連接，網(wǎng)絡(luò)中的消息可能丟失、亂序并延時到達(dá)，但大部分協(xié)議假設(shè)消息在有限的時間里能傳達(dá)到目的地；

4）服務(wù)器之間傳遞的信息，第三方可以嗅探到，但是不能篡改、偽造信息的內(nèi)容和驗證信息的完整性。

3、實用拜占庭容錯系統(tǒng)

實用拜占庭容錯系統(tǒng)（Practical Byzantine Fault Tolerance， PBFT），降低了拜占庭協(xié)議的運(yùn)行復(fù)雜度，從指數(shù)級別降低到多項式級別（Polynomial），使拜占庭協(xié)議在分布式系統(tǒng)中應(yīng)用成為可能。

PBFT是一類狀態(tài)機(jī)拜占庭系統(tǒng)，要求共同維護(hù)一個狀態(tài)，所有節(jié)點采取的行動一致。為此，需要運(yùn)行三類基本協(xié)議，包括一致性協(xié)議、檢查點協(xié)議和視圖更換協(xié)議。我們主要關(guān)注支持系統(tǒng)日常運(yùn)行的一致性協(xié)議。

一致性協(xié)議至少包含若干個階段：請求（request）、序號分配（pre-prepare）和響應(yīng)（reply）。根據(jù)協(xié)議設(shè)計的不同，可能包含相互交互（prepare），序號確認(rèn)（commit）等階段。

這個協(xié)議把服務(wù)器節(jié)點分為兩類：主節(jié)點和從節(jié)點，主節(jié)點只有一個。

PBFT的一致性協(xié)議如下圖所示。

為了描述方便，PBFT系統(tǒng)通常假設(shè)故障節(jié)點數(shù)為m個，而整個服務(wù)節(jié)點數(shù)為3m+1個。每一個客戶端的請求需要經(jīng)過5個階段，通過采用兩次兩兩交互的方式在服務(wù)器達(dá)成一致之后再執(zhí)行客戶端的請求。由于客戶端不能從服務(wù)器端獲得任何服務(wù)器運(yùn)行狀態(tài)的信息，PBFT中主節(jié)點是否發(fā)生錯誤只能由服務(wù)器監(jiān)測。如果服務(wù)器在一段時間內(nèi)都不能完成客戶端的請求，則會觸發(fā)視圖更換協(xié)議。

上圖顯示了一個簡化的PBFT的協(xié)議通信模式，其中C為客戶端，N0～N3表示服務(wù)節(jié)點，特別的，N0為主節(jié)點，N3為故障節(jié)點。整個協(xié)議的基本過程如下。

1）客戶端發(fā)送請求，激活主節(jié)點的服務(wù)操作。

2）當(dāng)主節(jié)點接收請求后，啟動三階段的協(xié)議以向各從節(jié)點廣播請求。

［2.1］序號分配階段，主節(jié)點給請求賦值一個序列號n，廣播序號分配消息和客戶端的請求消息m，并將構(gòu)造PRE-PREPARE消息給各從節(jié)點；

［2.2］交互階段，從節(jié)點接收PRE-PREPARE消息，向其他服務(wù)節(jié)點廣播PREPARE消息；

［2.3］序號確認(rèn)階段，各節(jié)點對視圖內(nèi)的請求和次序進(jìn)行驗證后，廣播COMMIT消息，執(zhí)行收到的客戶端的請求并給客戶端以響應(yīng)。

3）客戶端等待來自不同節(jié)點的響應(yīng)，若有m+1個響應(yīng)相同，則該響應(yīng)即為運(yùn)算的結(jié)果。

PBFT在很多場景都有應(yīng)用，在區(qū)塊鏈場景中，一般適合于對強(qiáng)一致性有要求的私有鏈和聯(lián)盟鏈場景。例如，在IBM主導(dǎo)的區(qū)塊鏈超級賬本項目中，PBFT是一個可選的共識協(xié)議。
來源： pixabay