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

一、前言

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

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

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

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

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

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

二、拜占庭容錯技術

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

1、拜占庭將軍問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一致性協議至少包含若干個階段：請求（request）、序號分配（pre-prepare）和響應（reply）。根據協議設計的不同，可能包含相互交互（prepare），序號確認（commit）等階段。

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

PBFT的一致性協議如下圖所示。

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

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

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

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

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

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

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

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

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