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

一、前言

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

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

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

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

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

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

二、拜占庭容錯技術

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

1、拜占庭將軍問題

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

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

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

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

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

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

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

2、拜占庭容錯系統

通常，發生故障節點被稱為拜占庭節點，而正常的節點即為非拜占庭節點。

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

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

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

拜占庭系統普遍采用的假設條件包括：

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

2）節點之間的錯誤是不相關的；

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

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

3、實用拜占庭容錯系統

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

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

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

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

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

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

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

1）客戶端發送請求，激活主節點的服務操作。

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

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

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

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

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

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