什么是拜占庭容錯(cuò)技術(shù)

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

一、前言

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

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

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

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

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

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

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

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

1、拜占庭將軍問題

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

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

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

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

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

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

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

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

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

拜占庭容錯(cuò)系統(tǒng)是一個(gè)擁有n 臺(tái)節(jié)點(diǎn)的系統(tǒng)，整個(gè)系統(tǒng)對(duì)于每一個(gè)請(qǐng)求，滿足以下條件：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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