整個區(qū)塊鏈行業(yè)的凜冽寒冬中，價格的漲跌已經(jīng)左右了太多的人頭腦之中的理智?？墒牵娙酥?，究竟有幾個人真正理解了區(qū)塊鏈技術(shù)的密碼學(xué)機制與分布式計算?究竟有幾個人還會關(guān)心區(qū)塊鏈在技術(shù)上的創(chuàng)新?

塵歸塵，土歸土?？赡苤挥芯薮蟮呐菽⒅?，區(qū)塊鏈才能通過技術(shù)創(chuàng)新顯示出真正的影響力。讓區(qū)塊鏈回歸技術(shù)與應(yīng)用的本質(zhì)，這也是區(qū)塊鏈大本營一直以來的定位。然而，傳播這樣的內(nèi)容和話題，離不開貨真價實的技術(shù)干貨，以及有感染力的人物和故事。

我們今天的內(nèi)容就來自于這樣一個女生：

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

[[250842]]

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

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

但是，不了解分布式系統(tǒng)的工作原理，不了解人們?nèi)绾文茉诜稚⒌木W(wǎng)絡(luò)上達成共識，你始終無法真正理解區(qū)塊鏈技術(shù)的創(chuàng)新之處。眾所周知，密碼學(xué)和分布式計算都不是什么新鮮事物;那為什么把它們整合在一起的區(qū)塊鏈技術(shù)，卻能夠迫使科學(xué)家和工程師不得不去重新審視分布式計算的基本范式呢?

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

分布式系統(tǒng)其實不是一個新鮮的話題，有關(guān)這個課題的研究已經(jīng)進行過幾十年了。

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

想真正弄懂區(qū)塊鏈，充分理解分布式系統(tǒng)是必不可少的。

那么，你又該如何去了解分布式系統(tǒng)呢?

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

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

本文正是出于這樣的目的來介紹入門區(qū)塊鏈的這一基礎(chǔ)：

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

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

一、什么是分布式系統(tǒng)?

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

分布式系統(tǒng)是圍繞同一個目標而協(xié)同工作的一群計算設(shè)備。

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

前文中說過，分布式系統(tǒng)有數(shù)百種體系結(jié)構(gòu)。

例如，一臺計算機可以看作成一個分布式系統(tǒng)——CPU、內(nèi)存 和 IO 設(shè)備都是獨立的進程，它們相互協(xié)作完成同一個目標，比如上網(wǎng)、編程、游戲。

再比如，下圖中飛機也可以看做是一個分布式系統(tǒng)，各單元共同協(xié)作，實現(xiàn)飛機的空間轉(zhuǎn)移。

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

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

二、分布式系統(tǒng)的基本性質(zhì)

分布式系統(tǒng)有一些基本的共性，它們包括：

1、并發(fā)性

系統(tǒng)中的進程是同時操作的，多個事件同時發(fā)生。換言之，網(wǎng)絡(luò)中的每臺計算機都在同時、獨立地執(zhí)行任務(wù)。

最大的難題在于協(xié)調(diào)。

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

2、缺少全局時鐘

在分布式計算機系統(tǒng)中，我們需要確定事件發(fā)生的先后順序，但由于各臺計算機在空間上是分開的，所以，我們?nèi)鄙僖粋€全局時鐘。

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

消息發(fā)送在收到之前。

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

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

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

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

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

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

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

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

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

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

3、獨立進程故障

在分布式系統(tǒng)中，每個進程都可能發(fā)生故障，這些故障可能是進程崩潰或失控，可能是信息遺漏、歪曲或重復(fù)，也可能是惡意信息，還可能是網(wǎng)絡(luò)延遲、斷網(wǎng)斷電。

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

這些異?？纱笾路譃槿齻€類型：

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

為了控制網(wǎng)絡(luò)中的分散個體，我們需要設(shè)計一項協(xié)議，讓一定會產(chǎn)生異常的系統(tǒng)仍然能夠提供服務(wù)，完成共同目標，即系統(tǒng)需要具備容錯性。

因此，在構(gòu)建分布式系統(tǒng)時必須做的核心假設(shè)是，在部分異常時系統(tǒng)還能否正常工作，異常是由于非惡意行為還是惡意行為。

一般來說，在構(gòu)建分布式系統(tǒng)時，有兩種模型需要考慮:

(1)簡單容錯

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

但是，如果運行環(huán)境不受控，簡單容錯機制很難發(fā)揮作用。

(2a)拜占庭容錯

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

(2b)BAR 容錯

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

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

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

4、信息傳輸

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

我們首先來了解一下信息傳輸環(huán)境：

(1)同步式

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

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

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

(2)異步式

在異步信息傳輸系統(tǒng)中，假定網(wǎng)絡(luò)可能無限延遲消息的發(fā)送，或者大量重復(fù)或者亂序。這時候，對于信息傳輸所需時間是不確定的。

三、分布式系統(tǒng)中的共識問題

到這里，我們已經(jīng)了解了分布式系統(tǒng)的下列特性：

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

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

復(fù)制狀態(tài)機(Replicated state machine)

復(fù)制狀態(tài)機，通俗點講，就是多個節(jié)點從相同的初始狀態(tài)開始，執(zhí)行相同的一串命令，產(chǎn)生相同的最終狀態(tài)。這一系列節(jié)點的狀態(tài)都是相同的，就是所謂的“復(fù)制狀態(tài)”。

在復(fù)制狀態(tài)機中，如果某一事務(wù)是有效的，將其輸入將導(dǎo)致系統(tǒng)的狀態(tài)向下一個轉(zhuǎn)換。在每個狀態(tài)轉(zhuǎn)換過程中，每個進程決定下一個輸出值。

從一個有效狀態(tài)轉(zhuǎn)換到下一個有效狀態(tài)的邏輯稱為“狀態(tài)轉(zhuǎn)換邏輯”。

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

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

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

復(fù)制狀態(tài)是一種確定性狀態(tài)機，功能與單個狀態(tài)機相同，狀態(tài)機中的單個計算機可能發(fā)生故障，但整個狀態(tài)機依然會正常運轉(zhuǎn)。

故障主要有：

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

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

共識問題的定義

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

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

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

在共識算法中，系統(tǒng)中的進程分別擔(dān)任這三種角色：

• 提議者(Proposers)——也稱作領(lǐng)導(dǎo)者(Leader)，發(fā)出請求或信息
• 決策者(Acceptors)——接收提議者的請求，輸出響應(yīng)值的進程
• 學(xué)習(xí)者(Learners)——系統(tǒng)中的其他進程，獲得系統(tǒng)決定的終止值

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

第一步，選擇

在所有進程中選擇一個領(lǐng)導(dǎo)者。

領(lǐng)導(dǎo)者提出下一個有效的輸出值。

第二步，投票

無故障的進程接收領(lǐng)導(dǎo)者的輸出值，經(jīng)過驗證，把它當(dāng)作下一個有效值提出。

第三步，決策

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

否則，重復(fù)步驟一、二、三，再來一次。

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

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

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

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

FLP 不可能性(FLP impossibility)

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

首先回顧一下同步系統(tǒng)和異步系統(tǒng)的區(qū)別:

• 同步環(huán)境——信息傳輸所用時間是固定的
• 異步環(huán)境——信息傳輸所用時間無法預(yù)估

這個區(qū)別很重要。

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

但是，如果想在同步環(huán)境中操作，就需要一個信息風(fēng)險可控的環(huán)境，比如說在一個配備原子鐘的數(shù)據(jù)中心，現(xiàn)實中很難操作。

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

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

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

其中，F(xiàn)LP 是 Fischer、Lynch、Patterson 這三位學(xué)者名字組合的簡寫。

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

對于分布式計算領(lǐng)域來說，這無疑令人沮喪。盡管如此，科學(xué)家們?nèi)栽诶^續(xù)努力尋找規(guī)避 FLP 不可能性的方法。目前有兩種：

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

四、一些基本的共識算法

方法一：使用同步假設(shè)

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

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

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

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

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

Paxos算法

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

Paxos 的工作機制如下：

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

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

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

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

階段3：學(xué)習(xí)階段

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

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

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

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

Paxos 確實有些難以理解，許多操作細節(jié)都沒有解釋透徹。怎樣知道提議者出錯的時間點?何時重新開始下一輪計算?想確定這些時間點我們是否需要一個同步時鐘來設(shè)置超時時間?這些問題，都需要我們?nèi)ニ伎肌?/p>

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

這樣的設(shè)計理念成為 Paxos 最大的不足之一，理解難、實現(xiàn)難，駕馭分布式系統(tǒng)更難。

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

Raft算法

2013 年，Ongaro 和 Ousterhout 發(fā)布了一種新的共識算法，用于叫做 Raft 的復(fù)制狀態(tài)機，主要注重協(xié)議的實用性和可理解性。

Raft 算法主要有兩個過程，一個是領(lǐng)導(dǎo)者選舉，另一個是日志復(fù)制。系統(tǒng)中的節(jié)點被分為三種角色：

• 領(lǐng)導(dǎo)者——負責(zé)與用戶溝通和日志復(fù)制
• 跟隨者——被動響應(yīng)請求，類似于選民
• 候選者——臨時角色，某節(jié)點想成為領(lǐng)導(dǎo)者，就要發(fā)起投票請求，同時自己變成候選者。如果選舉成功，則成為領(lǐng)導(dǎo)者，否則退回為跟隨者。

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

為了實現(xiàn)共識，候選者需要向跟隨者發(fā)出信息，請求他們的投票，一旦被系統(tǒng)中大多數(shù)認可選定后，就成為領(lǐng)導(dǎo)者，跟隨者們就跟隨其操作。

假設(shè)系統(tǒng)中的節(jié)點總數(shù)為 n，故障節(jié)點為 x，正常節(jié)點只需要比故障節(jié)點多一個，即 x+1，系統(tǒng)就能達成共識。

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

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

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

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

崩潰故障是更容易把控的，因為程序無法進行惡意行為。我們可以將進程建模，以 0 或 1 代表正?；虮罎?。因此，在崩潰容錯系統(tǒng)中，只要大多數(shù)進程能夠達成共識，就可以構(gòu)建分布式系統(tǒng)。

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

所以在拜占庭系統(tǒng)中，不是假設(shè)簡單多數(shù)就可以達成共識的。

對于這種行為，Raft 應(yīng)對乏力。舉例來說，如果選出來的領(lǐng)導(dǎo)者是拜占庭節(jié)點，并且與其他節(jié)點有著緊密的聯(lián)系，那么系統(tǒng)就危險了。之前講過，我們建立的系統(tǒng)模型，要么對簡單故障容錯，要么對拜占庭故障容錯。

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

那么問題來了，拜占庭環(huán)境怎么辦?!

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

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

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

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

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

原因如下：

• 如果出錯節(jié)點個數(shù)為 x，系統(tǒng)如果想正常運轉(zhuǎn)，必須先協(xié)調(diào)的節(jié)點個數(shù)為 n - x，(因為 x 個節(jié)點可能有問題/復(fù)雜，并且沒有響應(yīng))。

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

• n- x - x > x，

即：n > 3x + 1

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

學(xué)者們做了大量的研究工作，力求攻破在拜占庭和異步假設(shè)環(huán)境中的共識問題。

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

我全都想要!!!

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

DLS 算法

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

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

這里的“部分同步”位于同步系統(tǒng)和異步系統(tǒng)之間。

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

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

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

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

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

DLS 算法可以說是一個重大突破，因為它創(chuàng)造了一個新的網(wǎng)絡(luò)假設(shè)類型，即部分同步，并證明了在部分同步中，實現(xiàn)共識是可能的。

那么如何實現(xiàn)呢，我們關(guān)注兩點：安全性和活躍性。

安全性

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

活躍性

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

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

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

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

但是，如果我們設(shè)計一個算法，在這個算法中假設(shè)超時以保證安全性?？梢坏┤绻郊僭O(shè)失敗，就有可能導(dǎo)致有兩個有效的事務(wù)日志生成。

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

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

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

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

PBFT(Practical Byzantine Fault-Tolerance)

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

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

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

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

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

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

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

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

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

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

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

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

方法一小結(jié)

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

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

方法二：使用不確定性

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

中本聰共識(Nakamoto Consensus.)

傳統(tǒng)的共識中，算法的定義是這樣的：一個提議者和一群決策者必須協(xié)調(diào)和溝通，才能決定下一個值。

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

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

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

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

在比特幣網(wǎng)絡(luò)中，區(qū)塊鏈本質(zhì)上是去中心化的賬本，用區(qū)塊記錄每一筆交易，每個節(jié)點都擁有這個賬本，每個節(jié)點都擁有記賬權(quán)。那么誰來記賬呢?

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

搶到了記賬權(quán)，系統(tǒng)就會告知全網(wǎng)節(jié)點，獲得全網(wǎng)確認后，這個區(qū)塊便會被正式添加，這就是達成共識的過程。

每個區(qū)的生成會在區(qū)塊鏈上加蓋一個時間戳，網(wǎng)絡(luò)就在這個鏈條上延續(xù)構(gòu)建。

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

2、區(qū)塊獎勵

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

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

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

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

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

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

流言協(xié)議本身具有分布式系統(tǒng)的容錯性，因為網(wǎng)絡(luò)中任何節(jié)點發(fā)生故障，都不影響信息傳輸。

在異步環(huán)境中“技術(shù)上”不再安全

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

概率低不代表不會發(fā)生，不是嗎?

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

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

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

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

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

中本聰共識 vs 傳統(tǒng)共識

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

我們應(yīng)當(dāng)感謝中本聰?shù)倪@一項偉大創(chuàng)造。

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

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

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

結(jié)語

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

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

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

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

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

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

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

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

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

參考：

• 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