整個區塊鏈行業的凜冽寒冬中，價格的漲跌已經左右了太多的人頭腦之中的理智。可是，眾人之中，究竟有幾個人真正理解了區塊鏈技術的密碼學機制與分布式計算?究竟有幾個人還會關心區塊鏈在技術上的創新?

塵歸塵，土歸土。可能只有巨大的泡沫消散之后，區塊鏈才能通過技術創新顯示出真正的影響力。讓區塊鏈回歸技術與應用的本質，這也是區塊鏈大本營一直以來的定位。然而，傳播這樣的內容和話題，離不開貨真價實的技術干貨，以及有感染力的人物和故事。

我們今天的內容就來自于這樣一個女生：

她是工業與系統工程專業出身，做過頂級投行高盛的分析師，做過著名風投 a16z 的合伙人——這都是許多人夢寐以求的工作。但是，功成名就的路上，她卻發現編程才是自己想要的生活。

[[250842]]

笨辦法學會編程?她沒學會。如何用 HTML/CSS 做一個網頁?她開始上癮了。所以，沒有選擇斯坦福、MIT 的編程學位，她更喜歡 Hack Reactor 的全棧動手實踐。先學 JavaScript、React，后面的想法是機器學習、計算機視覺……這個女生就是 Preethi Kasireddy。

接觸區塊鏈之后，金融從業背景和全棧編程能力讓 Preethi 更加如魚得水。從 Coinbase 工程師到智能合約設計的自由職業者，究根問底的天性讓她開始用最淺顯易懂的語言來向大家解釋區塊鏈技術的真相。

但是，不了解分布式系統的工作原理，不了解人們如何能在分散的網絡上達成共識，你始終無法真正理解區塊鏈技術的創新之處。眾所周知，密碼學和分布式計算都不是什么新鮮事物;那為什么把它們整合在一起的區塊鏈技術，卻能夠迫使科學家和工程師不得不去重新審視分布式計算的基本范式呢?

接下來，我們就聽 Preethi 從分布式系統的基本概念說起，一步一步說到公式算法，特別是中本聰共識的真正精妙之處，進而抓住區塊鏈技術不會隨泡沫而飄散的真實內涵：

分布式系統其實不是一個新鮮的話題，有關這個課題的研究已經進行過幾十年了。

隨著比特幣、區塊鏈等話題在網絡上風生水起，分布式系統也逐漸走進大眾的視野。區塊鏈始于比特幣，它本身就是一種新型的分布式系統，它們的流行反過來又促使分布式計算領域的研究發生翻天覆地的變化。

想真正弄懂區塊鏈，充分理解分布式系統是必不可少的。

那么，你又該如何去了解分布式系統呢?

這個話題很難三言兩語說清楚，因為它所涉及的知識實在是太廣泛、太瑣碎了。關于分布式計算的資料文獻要么晦澀難懂，要么不成體系。況且，隨著應用場景不斷拓展，分布式系統又衍生出數百種不同架構，分別服務于數百種不同的需求，這一切讓整個問題愈顯復雜。

而如何把復雜的問題簡單化，把生僻的話題講明白，也就難上加難了。所以，在區塊鏈概念滿天飛的今天，如何 Get 到分布式系統和共識機制的基本概念而不被忽悠，就顯得愈加迫切了。

本文正是出于這樣的目的來介紹入門區塊鏈的這一基礎：

1. 什么是分布式系統?
2. 分布式系統的基本性質
3. 分布式系統中的共識問題
4. 一些基本的共識算法(Paxos、Raft、DLS 和 PBFT)
5. 中本聰共識為什么這么牛?

請記住，如果讀讀這篇文章，你就想成為行業大拿，這肯定是不現實的。

一、什么是分布式系統?

分布式系統是一組不同、分散的的進程，它們之間能夠互相協調，通過相互間的信息傳遞完成一個共同的目標。盡管這些進程是分開的，但呈現給用戶的，是一個系統、一個整體。

分布式系統是圍繞同一個目標而協同工作的一群計算設備。

進程可以是“節點”、“個體”、“計算機”或“組件”，在本文中，它們的意思都是一樣的。與之類似，“網絡”與“系統”表達的也是同一個意思。

前文中說過，分布式系統有數百種體系結構。

例如，一臺計算機可以看作成一個分布式系統——CPU、內存 和 IO 設備都是獨立的進程，它們相互協作完成同一個目標，比如上網、編程、游戲。

再比如，下圖中飛機也可以看做是一個分布式系統，各單元共同協作，實現飛機的空間轉移。

https://www.weetech.de/en/news-info/tester-abc/distributed-system-1/

類似的例子不勝枚舉，在本文中，我們主要討論進程是獨立分散的計算機的分布式系統。

二、分布式系統的基本性質

分布式系統有一些基本的共性，它們包括：

1、并發性

系統中的進程是同時操作的，多個事件同時發生。換言之，網絡中的每臺計算機都在同時、獨立地執行任務。

最大的難題在于協調。

Lamport, L (1978). Time, Clocks and Ordering of Events in a Distributed System

2、缺少全局時鐘

在分布式計算機系統中，我們需要確定事件發生的先后順序，但由于各臺計算機在空間上是分開的，所以，我們缺少一個全局時鐘。

在《分布式系統中的時間、時鐘和事件順序》這篇論文中，Leslie Lamport 展示了他的排序方法，首先需要記住以下兩點：

消息發送在收到之前。

每臺計算機都有一系列的事件。

通過確定某兩個事件的先后，我們可以知道系統中事件的部分順序。

譯注：部分順序——對應于總體順序，例如：三個事件的特定順序是 A>B>C，在一次計算中，我們只要求 A>C，不在乎 B 何時發生，這就是部分順序，那么 A > B > C, A > C > B 和 B > A > C 都滿足部分順序。

Lamport 的論文中闡述了一種算法，它要求每臺計算機都能從另一臺上收到信息。通過這種方式，得到部分順序后，總體順序也可以逐步推出來。

在這里，我們是完全根據每臺計算機收到信息的時間來排序的，那就會產生一些異常狀況。因為各地的時鐘或多或少都會有差別，這就導致系統順序與外部用戶感知到的順序是不同的。

為了處理這種異常，Lamport 想出一個辦法，同步各地的物理時鐘!

問題這樣就能解決了嗎?太天真了，年輕人!

同步大量獨立的時鐘絕不是一個簡單的事情，而是一個非常復雜的計算機科學問題。即使你在最初精確地設置了一大堆時鐘，由于時鐘漂移的存在，隨著時間推移，時鐘一定會有所變化。

譯注：時鐘漂移——各個時鐘的計時速度存在細微差別，隨著時間推移，一個時鐘的運行速度與其參考時鐘不完全相同，失去同步。計算機中使用的以晶體為基礎的時鐘也會發生漂移。容易被定時攻擊所利用。

因此，在分布式計算機系統中，時間和事件順序是根本障礙。

3、獨立進程故障

在分布式系統中，每個進程都可能發生故障，這些故障可能是進程崩潰或失控，可能是信息遺漏、歪曲或重復，也可能是惡意信息，還可能是網絡延遲、斷網斷電。

單個進程的故障率其實很低，但隨著系統中的進程越來越多，系統會發生故障就從一個偶然事件變為必然事件。我們要做的就是開發分布式協議，保證系統在各種異常情形下仍能正常工作。因此分布式系統也被稱為“容錯分布式計算”。

這些異常可大致分為三個類型：

• 崩潰：進程在沒有任何警告的情況下停止工作，如計算機崩潰。屬于非惡意行為。
• 遺漏：進程發送消息，但其他節點收不到，如消息丟失。屬于非惡意行為。
• 拜占庭：進程的行為隨機。如果是在受控環境(例如 Google 或 Amazon 的數據中心)中，這種情況可以不做考慮。我們主要關心故障發生在“沖突地帶”中的情形，他們的行為相當隨意，可能會惡意更改和阻斷信息，或者根本就不發送。屬于惡意行為。

為了控制網絡中的分散個體，我們需要設計一項協議，讓一定會產生異常的系統仍然能夠提供服務，完成共同目標，即系統需要具備容錯性。

因此，在構建分布式系統時必須做的核心假設是，在部分異常時系統還能否正常工作，異常是由于非惡意行為還是惡意行為。

一般來說，在構建分布式系統時，有兩種模型需要考慮:

(1)簡單容錯

在簡單的容錯系統中，我們假設系統的所有進程的行為方式都是固定的：要么遵守協議，要么失敗。這種類型的系統能夠妥善處理脫機或故障節點，并且不必擔心節點發出任意或惡意的行為。

但是，如果運行環境不受控，簡單容錯機制很難發揮作用。

(2a)拜占庭容錯

在拜占庭容錯系統中，我們假設節點可能產生故障或者惡意。在分散系統中，網絡是開放的、不受限制的，節點由獨立的個體控制，因此行為有很大的隨意性，在設計系統模型時，這種情況必須考慮。

(2b)BAR 容錯

還有一種故障叫做“理性”故障，即節點為了自身利益，可能會背離系統整體的目標。換句話說，節點可以老實，也可以不老實，這取決于其動機。如果“籌碼”足夠高，那么甚至大多數節點都會“叛變”。正所謂忠誠，取決于背叛的籌碼。

這被正式定義為 BAR 模型，它考慮到了拜占庭式故障和理性故障。BAR 模型假設系統中有三種角色：

• 拜占庭節點：是惡意的，只想作惡 ——壞人
• 無私節點：誠實的，總是遵循協議 ——老實人
• 理性節點：符合自身利益才會遵循協議 ——普通人

4、信息傳輸

分布式系統中的計算機之間通過“信息傳輸”實現溝通和協調，信息傳輸協議可以任選，無論是 HTTP、RPC 還是特定場景中的自定義協議。

我們首先來了解一下信息傳輸環境：

(1)同步式

在同步信息傳輸系統中，假定信息傳輸時間是固定的、已知的。

概念上并不復雜，用戶發送了消息，接收組件就會在固定的時間內得到消息。這樣用戶可以根據信息傳輸所需的固定時間上限來設計他們的協議。

然而，在分布式系統的實際操作中，這種傳輸環境應用有限。因為計算機可能崩潰或掉線，消息可能丟失、重復、延遲或亂序。

(2)異步式

在異步信息傳輸系統中，假定網絡可能無限延遲消息的發送，或者大量重復或者亂序。這時候，對于信息傳輸所需時間是不確定的。

三、分布式系統中的共識問題

到這里，我們已經了解了分布式系統的下列特性：

• 并發性
• 缺少全局時鐘
• 獨立進程故障
• 信息傳輸

接下來，我們將重點理解在分布式系統中“達成共識”的意義。最常見的一種模型稱為復制狀態機。

復制狀態機(Replicated state machine)

復制狀態機，通俗點講，就是多個節點從相同的初始狀態開始，執行相同的一串命令，產生相同的最終狀態。這一系列節點的狀態都是相同的，就是所謂的“復制狀態”。

在復制狀態機中，如果某一事務是有效的，將其輸入將導致系統的狀態向下一個轉換。在每個狀態轉換過程中，每個進程決定下一個輸出值。

從一個有效狀態轉換到下一個有效狀態的邏輯稱為“狀態轉換邏輯”。

事務是數據庫上的原子操作，這種操作一旦開始，就一直運行到結束，中間不會有任何切換。

換句話講就是操作要么完全完成，要么根本不發生。在復制狀態機中，這一系列被維護的事務集合稱為“事務日志”。

所謂的“達成共識”意味著所有的計算機必須一致同意在每個狀態轉換過程中的輸出值，也就是說，每臺計算機上的事務日志都是相同的。

復制狀態是一種確定性狀態機，功能與單個狀態機相同，狀態機中的單個計算機可能發生故障，但整個狀態機依然會正常運轉。

故障主要有：

• 計算機崩潰。
• 網絡不穩定，信息傳遞可能會延遲、亂序或者失敗。
• 沒有全局時鐘，事件順序難以確定。

即使是在局部故障的情況下，復制狀態機仍然必須不斷地接受新事務到事務日志，從而提供服務。這其實也是每一種共識算法的基本目標。

共識問題的定義

如果一個算法滿足以下條件，它就會達到共識：

• 一致性：所有非故障進程必須決定相同的輸出值。
• 終止性：所有非故障節點最后必須在某個值上終止，不能無限循環下去。

注意：不同的算法有不同的條件。例如，有些算法將一致性劃分為穩定性和整體性，還有些算法具有合法性、完整性或高效性的概念。在這里，如此細微的差別，就不贅述了。

在共識算法中，系統中的進程分別擔任這三種角色：

• 提議者(Proposers)——也稱作領導者(Leader)，發出請求或信息
• 決策者(Acceptors)——接收提議者的請求，輸出響應值的進程
• 學習者(Learners)——系統中的其他進程，獲得系統決定的終止值

定義一個共識算法的過程，通常有以下三個步驟：

第一步，選擇

在所有進程中選擇一個領導者。

領導者提出下一個有效的輸出值。

第二步，投票

無故障的進程接收領導者的輸出值，經過驗證，把它當作下一個有效值提出。

第三步，決策

所有非故障的進程必須達成共識，以此決定正確的最終值，具體根據所有進程的投票數是否達到預設值。

否則，重復步驟一、二、三，再來一次。

這里需要注意，各種共識算法在一些細節上有所區別，比如：

• 術語(例如：回合、階段、輪次)
• 處理投票的程序
• 決定最終值的標準(例如：有效性條件)

上面是共識算法定義的一般過程，滿足定義中的一般條件，我們就可以構建一種算法，從而創建一個能夠達成共識的分布式系統。

好像很簡單的樣子，有木有?

FLP 不可能性(FLP impossibility)

還差得遠呢，我們要面對的最大的難題就是——FLP 不可能性(FLP impossibility)

首先回顧一下同步系統和異步系統的區別:

• 同步環境——信息傳輸所用時間是固定的
• 異步環境——信息傳輸所用時間無法預估

這個區別很重要。

在同步環境中，我們可以設定信息傳輸所需的最大時間，允許系統中的不同節點輪流提出新的事務，然后投票確定一項，跳過沒有提出事務的節點。這種環境中，達成共識是可能的。

但是，如果想在同步環境中操作，就需要一個信息風險可控的環境，比如說在一個配備原子鐘的數據中心，現實中很難操作。

原子鐘：一種高精度計時裝置，利用原子吸收或釋放能量時發出的電磁波來計時，精度可達每 2000 萬年誤差 1 秒。

然而異步環境中，信息傳輸時間是不固定的，如果有某個進程出故障的話，實現終止將非常困難。

這種情況，被正式稱為“FLP 不可能性結果”。

其中，FLP 是 Fischer、Lynch、Patterson 這三位學者名字組合的簡寫。

他們在 1985 年發表過這樣一篇論文——《分布式共識的達成毀于一個出錯的進程》，論文指出——在一個異步系統中，即使只有一個進程出錯，那么分布式共識就無法達成。因為進程出錯的時間是隨機的，如果恰巧在共識達成的時候，那么就枉費工夫了。

對于分布式計算領域來說，這無疑令人沮喪。盡管如此，科學家們仍在繼續努力尋找規避 FLP 不可能性的方法。目前有兩種：

• 方法一：使用同步假設
• 方法二：使用不確定性

四、一些基本的共識算法

方法一：使用同步假設

FLP 不可能性原理表明，在異步傳輸系統中，如果一個系統無法終止，那么就不能達成共識。

但是，如果不知道異步信息傳輸所需的時間，那該如何保證每個非故障進程都會決定一個輸出值呢?

需要明確的是，這一發現并不代表共識無法達成，而是在異步傳輸環境中不能在固定的時間內達成。那就是說共識在某些時段還是可以達成的，只不過我們無法確定這個時間點。

解決這個問題的一種方法是使用超時。如果系統遲遲無法在一個值上終止，就等待一個超時，然后重新開始一輪運算。

這需要一些共識算法來支撐，其中的比較出名的是 Paxos 和 Raft。

Paxos算法

Paxos 是由 Leslie Lamport 在上世紀 90 年代提出的，這是第一個實用的容錯共識算法，它已被谷歌和亞馬遜(Amazon)等互聯網巨頭用于構建分布式服務。

Paxos 的工作機制如下：

階段1：準備請求(prepare request)

• 提議者選擇一個新的提議版本號 n，然后向決策者發送 “prepare request”。
• 如果決策者接收到這個 prepare request(“prepare”,n)，如果 n 大于任何他們已經回應過的 prepare request 的版本號，決策者就會發出 (“ack,” n, n’, v’) 或 (“ack,” n, ^ , ^)。
• 決策者的答復是保證不接受任何版本號小于 n 的提議。
• 決策者把已接收到的最高版本號的提議中的值 v 作為建議值。否則，他們用 ^ 回應。

階段2：接受請求( accept request )

• 如果提議者接收到多數決策者的響應，那么它可以發出一個 accept request (“accept,” n, v)，其編號為 n，值為 v。
• n 是 prepare request 中出現的數字。
• v 是響應中編號最高的提議中的值。
• 如果決策者接收到 accept request (“accept,” n, v)，則它通過該提議，除非它已經響應了一個大于 n 的 prepare request。

階段3：學習階段

1. 當決策者通過一個提議時，它會對所有學習者進行響應 (“accept,” n, v)。
2. 學習者收到大多數決策者發出的 (“accept,” n, v)，就會以 v 為最終決定值，并把 (“accept,” n, v) 通知到所有其他的學習者。
3. 學習者收到 (“accept,” n, v)，把 v 作為最終決定值。

https://www.myassignmenthelp.net/paxos-algorithm-assignment-help

講到這里，相信很多同學應該已經懵逼了，但是先別急，更讓人懵逼的可能還在后頭。

我們都知道，每個分布式系統都會有發生異常。在這種算法中，如果提議者由于信息丟失等原因出錯，那么最終決定可能會被延遲，Paxos 算法在第一階段中使用了一個新版本號，來避免之前的計算產生的影響。

Paxos 確實有些難以理解，許多操作細節都沒有解釋透徹。怎樣知道提議者出錯的時間點?何時重新開始下一輪計算?想確定這些時間點我們是否需要一個同步時鐘來設置超時時間?這些問題，都需要我們去思考。

此外，為了在實際應用中更加靈活，Paxos 關鍵領域的不少規范都是開放式的。諸如領導者選擇、故障檢測和日志管理等概念都比較模糊或完全沒有定義。

這樣的設計理念成為 Paxos 最大的不足之一，理解難、實現難，駕馭分布式系統更難。

在 Paxos 中，雖然超時在算法中沒有明確提及，但在實際操作中，想要實現終止，等待一個超時后，必須選擇一個新的提議者。否則，決策者就不會輸出下一個值，整個系統就停止了。

Raft算法

2013 年，Ongaro 和 Ousterhout 發布了一種新的共識算法，用于叫做 Raft 的復制狀態機，主要注重協議的實用性和可理解性。

Raft 算法主要有兩個過程，一個是領導者選舉，另一個是日志復制。系統中的節點被分為三種角色：

• 領導者——負責與用戶溝通和日志復制
• 跟隨者——被動響應請求，類似于選民
• 候選者——臨時角色，某節點想成為領導者，就要發起投票請求，同時自己變成候選者。如果選舉成功，則成為領導者，否則退回為跟隨者。

這三種角色都不是固定的，可以隨著環境條件互相轉換，但是在某一個時刻只能擔任其中一種。

為了實現共識，候選者需要向跟隨者發出信息，請求他們的投票，一旦被系統中大多數認可選定后，就成為領導者，跟隨者們就跟隨其操作。

假設系統中的節點總數為 n，故障節點為 x，正常節點只需要比故障節點多一個，即 x+1，系統就能達成共識。

因此，Raft 算法支持的最大故障節點數量是(n-1)/2。

Raft 算法的容錯機制只支持故障節點，不能支持惡意節點，并且使用共享超時來實現終止。

如果進程崩潰并重新啟動，在聲明自己的領導者身份之前，至少需要等待一個超時時間，并保證會取得進展。

Paxos 和 Raft 是比較傳統的共識算法，它們能夠使用同步假設(即超時)在異步環境中一展身手，它們只對崩潰故障容錯，面對拜占庭故障無能為力。

崩潰故障是更容易把控的，因為程序無法進行惡意行為。我們可以將進程建模，以 0 或 1 代表正常或崩潰。因此，在崩潰容錯系統中，只要大多數進程能夠達成共識，就可以構建分布式系統。

而在開放和分散的系統(如公鏈)中，網絡中的節點是不受用戶控制的，節點有不同的動機，可以撒謊、配合或隨心所欲，一半以上的可靠節點可以約定好互相撒謊，互相之間必然發生沖突。

所以在拜占庭系統中，不是假設簡單多數就可以達成共識的。

對于這種行為，Raft 應對乏力。舉例來說，如果選出來的領導者是拜占庭節點，并且與其他節點有著緊密的聯系，那么系統就危險了。之前講過，我們建立的系統模型，要么對簡單故障容錯，要么對拜占庭故障容錯。

總之，Raft 和 Paxos 具有簡單的容錯能力，但對拜占庭故障無能為力。

那么問題來了，拜占庭環境怎么辦?!

在解決這個問題之前，我們先來了解一個概念——

拜占庭將軍問題(Byzantine Generals Problem)

拜占庭將軍問題由 Leslie Lamport、Robert Shostak 和 Marshall Pease 在同名論文中提出，分布式系統依靠交換信息來整體協作，然而其中的節點會作惡，網絡會崩壞，因此系統不能達成一致。

拜占庭容錯協議就是為了應對節點的惡意行為，論文為解決拜占庭將軍問題提供了第一個證明：

• 如果一個系統共有 n 個節點，其中有 x 個是拜占庭節點，該系統如果想達成共識，n 必須滿足：n>3x + 1

原因如下：

• 如果出錯節點個數為 x，系統如果想正常運轉，必須先協調的節點個數為 n - x，(因為 x 個節點可能有問題/復雜，并且沒有響應)。

然而不排除這種可能，不響應的x也許并不是出錯了,也可能是有響應的只不過由于網絡等原因未被察覺。如果我們想要非故障節點的數量多于故障節點，n 必要滿足：

• n- x - x > x，

即：n > 3x + 1

然而，該論文所演示的算法僅適用于同步環境，那貌似拜占庭環境、異步環境兩者我們只能解決一個了，或者只能等待奇跡的發生。

學者們做了大量的研究工作，力求攻破在拜占庭和異步假設環境中的共識問題。

下面便是見證奇跡的時刻——

我全都想要!!!

接下來，我們將研究兩種算法(DLS 和 PBFT)，打破拜占庭+異步的障礙的奇跡，我們在慢慢靠近。

DLS 算法

Dwork、Lynch 和 Stockmeyer(“DLS”算法的由來)在 1988 年曾發表論文《部分同步存在的共識》，文中闡述了關于拜占庭容錯共識的一個重大進展：在“部分同步系統”中達成共識。

你可能還記得，在同步系統中，信息從發送到接收所需的時間是有固定上限的，而在異步系統中，該上限不存在。

這里的“部分同步”位于同步系統和異步系統之間。

本文解釋了部分同步假設的兩個版本:

• 假設信息傳輸所需的時間上限是存在的，但是是未知的。目標是達成共識，先不考慮實際的上限。
• 假設信息傳輸所需的時間上限是已知的，但是它只能保證在某個未知的時間(也稱為“全球標準化時間”，GST)啟動。目標是設計一個能夠達成共識的系統，無論這個未知的時間在什么時候。

以下是 DLS 算法的工作原理：

• 運算的每一輪都被分為“試探”階段和“鎖定-釋放”階段。N 是系統的總節點數量，x 是系統的容錯節點數量。
• 每一輪都有一個提議者，回合的開始時候，每個進程傳輸各自認為正確的值。
• 如果一個值最少被 N − x 個進程程傳達過，那么提議者將把它作為建議值。
• 當某個進程從提議者接收到建議值時，它必須鎖定該值，然后散布這個信息。

如果提議者接收到 x + 1 個進程發出的建議值，這個值將會作為最終值提交。

DLS 算法可以說是一個重大突破，因為它創造了一個新的網絡假設類型，即部分同步，并證明了在部分同步中，實現共識是可能的。

那么如何實現呢，我們關注兩點：安全性和活躍性。

安全性

這是“一致性”(Agreement)的另一個術語。其中所有非故障進程都贊成相同的輸出值。如果我們能保證足夠的安全性，就能夠保證整個系統保持同步;而如果安全性不夠，將會導致需要更多的事務日志來終止這一輪的信息傳輸。我們希望所有節點都遵從事務日志的順序，盡管故障和惡意進程是無法避免的。

活躍性

這是“終止性”(Termination)的另一個術語。其中每個非故障節點都會以某個輸出值作為最終決定值。在區塊鏈設置中，新的區塊不斷生成，區塊鏈不斷延伸，這就是活躍性。只有保持活躍，這個網絡才有用處，否則，區塊鏈就“爛尾”了。

從 FLP 不可能性中我們知道，在完全異步的系統中，共識是不可能達成的。DLS 的論文則認為，如果進行部分同步假設，就可以營造活躍環境，而這就足以攻克 FLP 不可能性。

因此，本文證明了該算法無需進行同步假設，安全條件都可以保證。

如果節點沒有決定某個輸出值，系統就會停止。為了保證終止，也就是保證活躍性，我們可以做一些同步假設(即超時)。但如果某一次同步假設失敗，系統也會停止。

但是，如果我們設計一個算法，在這個算法中假設超時以保證安全性。可一旦如果同步假設失敗，就有可能導致有兩個有效的事務日志生成。

兩個事務日志要比系統停止要危險得多——如果不安全，那么活躍無意義。

可以說，即使整個區塊鏈停止，那也好過于生成兩個不同的區塊鏈。

分布式系統總是在權衡取舍。如果你想突破一個限制(比如 FLP 不可能性)，你必須在別的地方做出讓步。在這種情況下，把關注點分成安全性與活躍性是非常合理的。這樣我們可以構建一個在異步假設中的安全系統，但仍然需要超時來保證有新的值持續輸出。

DLS 的論文已經講得足夠詳細，但到如今，DLS 從未真正地被廣泛應用，甚至沒有在實際的拜占庭場景中使用。這可能因為 DLS 算法的核心假設之一是使用同步時鐘，以便有一個共同的時間概念。實際上，同步時鐘很容易受到多重攻擊，在一個拜占庭容錯假設中往往不夠可靠。

PBFT(Practical Byzantine Fault-Tolerance)

Miguel Castro 和 Barbara Liskov 在 1999 年發表了論文《Practical Byzantine Fault-Tolerance》(《實用的拜占庭容錯》)，其中提出了 PBFT 算法。對于拜占庭系統來說，這種算法正如其名——更加“實用”。

這篇論文認為，以前的算法雖然“理論上可行”，但要么太慢而無法使用，要么為了安全性必須做同步假設。我們前文中提過，這在異步環境中是非常危險的。

PBFT 中的 “P”(Practical)意味著該算法可以在異步環境中應用，并且做了一些優化，運行速度會更快。

在 PBFT 中，無論有多少故障節點，系統都能夠提供安全性。如果系統內的節點總數是 n，那么算法的容錯節點數量 x 的最大值是 (n-1)/3，而且消息延遲的增長速度不會超過一定的時間限制。

因此，PBFT 進行同步假設并不是為了安全，而是為了活躍，并以此規避 FLP 不可能性。

算法通過一系列“視圖”(view)運行，每個視圖都有一個“主”節點(即領導者)，其余的都是“備份”。下面是 PBFT 詳細的工作步驟：

• 客戶端有一項新事務，將其發送給主節點。
• 主節點將這項事務傳遞給所有備份。
• 各備份執行該事務并向客戶端發送回復。
• 客戶端收到來自 x+1 個節點的相同消息后，則該響應就是這次運算的結果，共識已經正確完成。

如果主節點不出錯，協議就能正常運行。然而，如果主節點出錯，或者惡意，備份節點能夠通過 timeout 機制檢測到主節點是否已經廢掉。當出現這些異常情況時，這些備份節點就會觸發視圖更換(view change)協議來選舉出新的主節點。但是這個過程非常緩慢，為了達成共識，PBFT 需要進行二次通信——每臺計算機必須與網絡中的所有計算機都進行通信。

注意：想要完整地解釋PBFT算法，得非常大的篇幅!這里說一下關鍵部分就好。

雖然 PBFT 相比以前的算法已經有了長足的改進，但對于有大量參與者的實際場景(如公鏈)來說，它還不夠實用。但是，至少在故障檢測和領導者選舉方面，它給出了一些具體的做法，這要比 Paxos 強多了。

PBFT 的貢獻是舉足輕重的，它整合了一系列重要的有變革意義的算法思想，不少新的共識協議從中受益匪淺，尤其是后區塊鏈時代(post-blockchain world)。

比如，Tendermint 是一種新的共識算法，從 PBFT 中獲益頗豐，且設計更加實用。在“驗證”階段，Tendermint 使用兩個投票步驟來決定最終值;Tendermint 每輪都會更換新領導者。如果當前一輪的領導者在一段時間內沒有響應，那么它就會被跳過，算法直接進入下一輪，并產生新的領導者。而在 PBFT 中，每次視圖更換選新的領導人，都需要一次繁瑣耗時的點對點連接，相比起來，Tendermint 運行更簡潔，更有實用意義。

方法一小結

• Paxos 和 Raft，具有簡單容錯能力，對系統崩潰或網絡延遲等故障容錯，需要同步信息傳輸環境，適用于嚴格受控的私鏈環境。
• DLS 和 PBFT，可對拜占庭故障容錯，在異步信息傳輸環境中需要做某種形式的同步假設(超時)，適用于新加入節點需要驗證的聯盟鏈。

五、中本聰共識為什么這么牛?

方法二：使用不確定性

下面我們來介紹另一種克服 FLP 不可能的方法：不確定性。所謂不確定性，就是用概率論和不確定的方式來解決共識問題。

中本聰共識(Nakamoto Consensus.)

傳統的共識中，算法的定義是這樣的：一個提議者和一群決策者必須協調和溝通，才能決定下一個值。

這太復雜了，因為它需要知道網絡中的每個節點，而且各個節點之間都必須溝通，即二次通信消耗。簡單地說，它的拓展性有限，也不能在開放的、沒有限制的系統中工作，在這種系統中，任何人都可以隨時加入和離開。

中本聰共識使上述的難題成為概率性的事件，這是其高明之處所在。用不著每個節點都同意一個值，只需要所有節點都同意這個值為正確的可能性。

我們從一下幾個板塊來理解：

1、拜占庭容錯機制——工作量證明(PoW，proof of work)

在比特幣網絡中，區塊鏈本質上是去中心化的賬本，用區塊記錄每一筆交易，每個節點都擁有這個賬本，每個節點都擁有記賬權。那么誰來記賬呢?

在中本聰共識中，記賬的節點是不確定的，哪個節點解決難題最快，算力最強，它就能夠在區塊鏈中添加新區塊。而這個需要節點們去解決的難題也沒有確定的公式去解決，只能依靠窮舉法。

搶到了記賬權，系統就會告知全網節點，獲得全網確認后，這個區塊便會被正式添加，這就是達成共識的過程。

每個區的生成會在區塊鏈上加蓋一個時間戳，網絡就在這個鏈條上延續構建。

規范鏈是指累積了最多工作量，也就是花費了最多的計算量的鏈條，也就是最長的鏈條。它不僅可以證明該鏈堆積了最多的 CPU 算力，還可以作為區塊序列的證明。因此，只要大多數 CPU 資源是由誠實的節點掌控的，它們就能繼續生成最長的鏈。

2、區塊獎勵

網絡中的節點通過算力的競爭來爭奪下一個區塊的記賬權，那么如何使節點們都能心甘情愿地消耗巨大的算力去爭奪呢?中本共識的算法設計了區塊獎勵(比特幣)，爭奪到記賬權就可以獲得比特幣獎勵，這樣是節點們的目標都能保持一致且相對單純。

3、抵抗女巫攻擊(Sybil Attack)

女巫攻擊：在 P2P 網絡中，節點是可以隨時加入和退出的。為了維持網絡穩定，同一份數據通常需要備份到多個分布式節點上，這就是數據冗余機制。單個惡意節點偽裝多重身份，把原來要備份到多個節點上的數據欺騙到了同一個惡意節點，這種攻擊數據冗余機制的手段，就叫做女巫攻擊。

中本聰共識采用工作量證明(PoW)，節點要證明自己是節點，只能依靠其計算能力，不能依靠分裂或偽裝，這樣極大地增加了攻擊的成本。因此中本聰共識本身具有 sybil 抵抗能力，不需要 PKI 或任何其他花哨的身份驗證方案。

4、點對點流言協議(P2P gossip)

中本聰共識的一個主要貢獻是使用了流言協議(gossip protocol)，它更加適合 P2P 網絡環境。在網絡中，一個節點如果想傳遞信息，它會隨機選擇周圍的幾個節點進行散播，收到嘻嘻的節點重復上述過程，最終全網所有節點都能收到信息。簡單的說，就是一傳十、十傳百。

流言協議本身具有分布式系統的容錯性，因為網絡中任何節點發生故障，都不影響信息傳輸。

在異步環境中“技術上”不再安全

在中本聰共識中，安全保證是概率性的。新區塊不斷生成，區塊鏈在不斷加長，惡意節點能夠建立有效的替代鏈的概率會隨之降低。

概率低不代表不會發生，不是嗎?

所以，中本聰共識在“技術上”并不能保證異步假設中的安全性。這是為什么呢?

因為比特幣區塊鏈中可能存在一個網絡分區，在網絡分區中，如果攻擊者的算力足夠強大，那他就可以在此分區建立一條比規范鏈還長的“替身鏈”,這樣的話，交易發生所在的規范鏈就可能廢掉，而“替身鏈”成為主鏈，攻擊者就改變了自己的那筆交易，支付出去的錢又回到了自己手中。

然而，這需要攻擊者獲得全網算力的 51%，如此巨大的算力需要耗費巨額的經濟成本，試問又有誰能承擔得起呢?而且即使攻擊者掌握了 51% 的算力，還需要與另外的 49% 展開 6 次區塊的爭奪，只有連續 6 次成功，才能成功創建“替身鏈”。

從本質上講，“替身鏈”理論上是可以創建的，但是可能性非常低，這也是前面為什么說“技術上”不安全的原因。

但這個可能性低到可以忽略不計，比特幣區塊鏈的不可篡改性就來源于此。

中本聰共識 vs 傳統共識

從實際應用來看，中本聰共識本身是一種拜占庭容錯機制。但很明顯，它并沒有達到傳統意義上的共識。因此在最初，它被認為完全脫離了拜占庭容錯世界。

我們應當感謝中本聰的這一項偉大創造。

中本聰共識允許任意數量的節點都可以公開參與進來，任意進入，任意退出，而且沒有人必須得知道其他的參與者都是誰。

中本聰共識比以往的共識算法更簡單，消除了以前算法在點對點連接、領導者選舉、二次通信消耗等方面的復雜性。簡單到在一臺計算機上啟動比特幣協議軟件，就可以挖礦。

正因為它簡單且有效，所以在現實中有著很廣闊的應用場景，可以說是 PBFT 的更“實用”的版本。

結語

長篇大論之后，前面的一些細節你可能已經忘了，這里我們小小總結一下：

這篇文章中，我們首先介紹了分布式系統的概念和特性，然后講到了分布式系統中最重要的問題——如何達成共識。達成共識面臨的最大障礙是FLP不可能性。要跨越這個障礙，我們有兩種途徑。

第一種是使用同步假設，其中 Paxos 和 Raft 都是在同步環境中，對簡單的故障容錯;而 DLS 和 PBFT 是在異步環境中，使用某種形式的同步假設(即超時)，實現都拜占庭故障容錯。

但是在開放(如：公鏈)網絡中，實用性依然有限。

第二種是利用不確定性。其中中本聰共識是顯著的代表，它給予誠實節點獲利的機會，讓系統達成共識成為一個概率性(不確定性)的事件，同時也讓惡意節點造成損害的結果的概率低到可以忽略不計。適用于節點可以任意進入和退出的開放式網絡。

讀懂中本聰共識后，區塊鏈技術的其他進展，我們也就更容易 Get 到了，比如 POS、Plasma、Casper，等等。Preethi 說她將在下一篇文章中詳解 Proof-of-Steak 的概念和原理，它真的會比中本聰共識更好嗎?

(你沒看錯，是 Proof-of-Steak)

相信這篇長文，會有助于大家來區分區塊鏈領域資本方面的缺點與技術方面的優點。資本逐利的狂熱總會制造出一些迷惑人的泡沫與假象，但總有一些愛好技術的年輕人，喜歡默默無聞地創新出一些很酷的產品或服務。假以時日，當這些很小的產品或服務長成參天大樹的時候，大多數人才會后知后覺地感受到——這個世界要變天了!

畢竟，任何時候，肯沉下心來鉆研技術本質的，始終只是那聰明的一小撮人。

參考：

• https://medium.com/s/story/lets-take-a-crack-at-understanding-distributed-consensus-dad23d0dc95
• https://techglider.github.io/review/time-clocks-and-ordering-of-events-in-a-distributed-system/
• http://www.cs.utexas.edu/~dahlin/projects/bft/#BAR
• https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf
• http://pages.cs.wisc.edu/~sschang/OS-Qual/reliability/byzantine.htm
• https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf
• https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf
• http://pmg.csail.mit.edu/papers/osdi99.pdf
• https://bitcoin.org/bitcoin.pdf