在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是一個可選的共識協議。
參考：
1、《區塊鏈技術指南》 （作者：鄒均，張海寧，唐屹，李磊等）
2、《拜占庭系統技術研究綜述》（軟體學報 作者：範捷，易樂天，舒繼武）
http://www.jos.org.cn/jos/ch/reader/create_pdf.aspx?file_no=4395&journal_id=jos
3、《區塊鏈共識演算法的發展現狀與展望》（自動化學報 作者：袁勇，倪曉春，曾帥，王飛躍）
http://html.rhhz.net/ZDHXBZWB/html/2018-11-2011.htm
