拜占庭系統(tǒng)發(fā)展到今天，已經30余年了，直至2009年中本聰以比特幣和區(qū)塊鏈的模型，重新優(yōu)化了拜占庭問題的解決方案，拜占庭系統(tǒng)才逐漸被大眾所熟知。既然拜占庭問題可以就人類偉大的信任決策問題達成共識協(xié)議，那么為什么區(qū)塊鏈技術出現(xiàn)之前，拜占庭系統(tǒng)沒有引起大家的關注？區(qū)塊鏈真正做了哪些改變呢？

小資料：

拜占庭問題起源于1982年，由Lamport教授首次提出，其實它可以簡單的理解成：3個或者更多的將軍共同決定進攻還是撤退的問題。

在這個決策過程中，如果一個將軍發(fā)布命令，其他的人作為將軍的下屬，分別決定進攻還是撤退。但是如果一個甚至多個將軍或者下屬叛變，決策就會出現(xiàn)問題，無法達成一致的行動。如果司令叛變，他可能會讓一個下屬進攻，另一個撤退。同樣，如果一個下屬叛變，他可能告訴其他的下屬說司令讓他進攻，而告訴另一個下屬說司令讓他撤退，這樣就無法達成一致的行動。拜占庭系統(tǒng)正是為了在這個復雜的環(huán)境中，取得一致決策而設計。

我們之前創(chuàng)業(yè)做的業(yè)務主要是幫助企業(yè)快速定位App上線后，并發(fā)壓力加大導致的使用緩慢，崩潰等系統(tǒng)問題的原因。所以積累了大量的業(yè)務數(shù)據，所以應用了各類的分布式系統(tǒng)的方案。今年，我們團隊主要在做Lamba分布式存儲的業(yè)務，是要解決區(qū)塊鏈中DApp數(shù)據沒有分布式存儲可用的痛點。所以，我們完整的經歷了分布式系統(tǒng)到區(qū)塊鏈的演進過程。對于拜占庭系統(tǒng)的變化分享給大家。

一、N>=3f+1就可以解決拜占庭問題

首先。我們先來理解拜占庭將軍問題能夠被解決的客觀限制N>=3f+1。也就是說，如果拜占庭將軍問題的節(jié)點數(shù)為N<=3f，那么拜占庭將軍問題將無法解決，我們以3個節(jié)點為例來推導：

在左邊的場景中，下屬P3有故障;對于右邊的情況，司令P1有故障。我們可以看到兩個回合的信息交換：司令發(fā)送的值和兩個中尉相互發(fā)送的值。數(shù)字前綴表面消息來源，并且給出不同的回合數(shù)。

在左邊的場景中，P2接受到了2個不同的值（v，u），但是不知道那個是司令傳來的。因此無法做出決策。

在右邊的場景中，司令有錯誤發(fā)送了2個不同的值。P3也收到了2個不同的值，因此P3也無法判斷哪一個是正確的。

當解決拜占庭將軍問題的節(jié)點數(shù)量為N>=3f+1時，我們再來推導一下上述的問題，以N>=4，f=1的場景為例：

當出現(xiàn)左圖的場景時，majority函數(shù)（最多返回為最終結果）可以取最多數(shù)值作為下屬的最終決定值。因此下屬可以就決策達成一致：

l P2 決定 majority（v,u,v）=v

l P4決定majority（v,v,w）=v

在右圖的場景中，司令是錯的，但是正確的3個下屬節(jié)點可以達成一致：

P2, P3, P4決定majority（u,v,w）= ⊥（表示沒有占多數(shù)的值存在）

這個推導由Lamport教授在1982年時完成，看到這里我們很容易理解，從邏輯的角度解決拜占庭問題的方法其實非常簡單，我們只需要決策的節(jié)點數(shù)量為 N>=3f+1即可。

但是，為什么拜占庭系統(tǒng)在這么多年內中沒有被廣泛的使用和認知呢？

盡管拜占庭系統(tǒng)可以就人類信任決策的問題達成最終一致共識，有很大的商業(yè)應用場景，但是當我們想應用時，卻發(fā)現(xiàn)系統(tǒng)是非常低效的。我們知道每一輪決策的代價是消息傳遞的輪數(shù)以指數(shù)級的方式增長，因此使用這個辦法解決拜占庭問題，因為效率的影響也無法在實際業(yè)務中得到應用。

二、拜占庭系統(tǒng)的技術演進

PBFT拜占庭系統(tǒng)

隨著時間的發(fā)展，效率問題一直是拜占庭系統(tǒng)技術演進的主要方向，Castro 和Liskov 在1999 年提出了Practical Byzantine Fault Tolerance（PBFT）系統(tǒng)，首次將拜占庭協(xié)議的復雜度從指數(shù)級降低到多項式級別，使拜占庭協(xié)議在分布式系統(tǒng)中應用成為可能。

PBFT 的一致性協(xié)議如圖所示，每一個客戶端的請求需要5 個階段才能完成。其通過采用兩次兩兩交互的方式，在服務器達成一致之后再執(zhí)行客戶端的請求。由于客戶端不能從服務器端獲得任何服務器運行狀態(tài)的信息，因此PBFT 協(xié)議中主節(jié)點是否發(fā)生錯誤只能由服務器監(jiān)測。如果服務器在一段時間內都不能完成客戶端的請求，則會觸發(fā)視圖更換協(xié)議（即節(jié)點切換）。

PBFT 采取的設計思路是將所有的工作都放在服務器端進行，例如達成一致性、監(jiān)測拜占庭主節(jié)點等等。因此它的問題就是，盡管復雜度相對于Lamport模型已經降低了，但是一致性協(xié)議設計依然很復雜，其中有兩個階段需要服務器之間的兩兩交互，數(shù)據的處理量大，而且計算復雜。

HQ拜占庭系統(tǒng)

于是Cowling等人在2006年HQ來改進PBET，下圖為HQ模型的原理圖：

我們會看到在HQ協(xié)議通信模型中，取消了主節(jié)點選擇的問題?？蛻舳讼蛩械墓?jié)點發(fā)出請求，并在Write 1階段中檢查是否有3f+1個節(jié)點（最少決策節(jié)點數(shù)）中的2f+1，有共同的返回值。如果有，那么就判定服務器處于相同的狀態(tài)中。

在HQ模型中，將請求分成2個階段。第一個階段，當客戶端發(fā)送請求的同時收集服務器的狀態(tài)，如果有2f+1臺以上的服務器處于相同狀態(tài)，并能夠執(zhí)行客戶端的請求，那么客戶端才執(zhí)行第二階段的操作，暨發(fā)送指令，讓服務器執(zhí)行的客戶端請求。否則說明請求遇到競爭，將執(zhí)行PBFT的流程。

所以HQ協(xié)議通信模型并沒有改變PBFT的架構，只是當客戶端發(fā)送請求，并且沒有競爭的情況出現(xiàn)時，這個模式才有效。

基于Speculation的拜占庭系統(tǒng)

Dahlin 等人在2007 年提出了Zyzzyva 和Zyzzyva5 協(xié)議，將Speculation 技術引入了拜占庭協(xié)議。因為Zyzzyva協(xié)議客戶端不需要等待服務器交互確認，所以極大程度的提高了拜占庭系統(tǒng)的性能。

其主要思想是：服務器絕大部分時間處于正常的狀態(tài)，因此不用每一個請求都在達成一致性之后再執(zhí)行，只需要在錯誤發(fā)生之后再達成一致性即可。

與傳統(tǒng)的協(xié)議相比，Speculation 機制的不同主要在于一致性協(xié)議部分。下圖為Speculation 的執(zhí)行流程，服務器收到客戶端的請求之后，并不像傳統(tǒng)的協(xié)議一樣首先進行代價較大的兩兩交互，而是直接執(zhí)行了客戶端的請求。

只要客戶端接收到所有服務器反饋的信息（執(zhí)行結果、服務器狀態(tài)、執(zhí)行歷史等），并且這些信息是一致的，客戶端認為結果正確，并返回給上層應用;否則，客戶端在接收到 2f+1 服務器反饋的信息后，就執(zhí)行一個序號確認的階段，告訴至少f+1 臺非拜占庭服務器，已經有至少f+1 臺非拜占庭服務器執(zhí)行了請求。

總的來說，在Speculation 中，如果服務器執(zhí)行結果是一致的，那么客戶端采用這個結果。如果不一致，那么客戶端丟棄這個結果，并且反饋給服務器觸發(fā)視圖更換協(xié)議切換主節(jié)點。這樣雖然可能暫時導致系統(tǒng)不一致，但是并不會影響非拜占庭的客戶端請求的執(zhí)行。

如果客戶端是拜占庭的，那么即使系統(tǒng)結果不一致也沒有關系。如果客戶端是非拜占庭的，發(fā)現(xiàn)系統(tǒng)不一致之后，一定會觸發(fā)視圖更換協(xié)議將系統(tǒng)重新調整，從而確保系統(tǒng)的一致性狀態(tài)。

Speculation技術單一請求所需的階段數(shù)較少，從理論上來說達到了最優(yōu)，降低了系統(tǒng)的響應延時。除了基于客戶端的Speculation技術以外，2009年時也提出了基于客戶端的Specutaion技術，其本質是改進型的Zyzzyva 算法，核心思想是客戶端不需要收到所有的服務端返回再執(zhí)行操作，客戶端再收到的第一個服務器請求后，就執(zhí)行響應。當系統(tǒng)沒有拜占庭節(jié)點時，這極大的優(yōu)化了系統(tǒng)的效率，但是當拜占庭節(jié)點出現(xiàn)時，大規(guī)模的部署中依然存在效率問題。所以盡管有廣闊的商業(yè)前景，拜占庭系統(tǒng)一直沒有受到主流媒體的追捧。

三、區(qū)塊鏈對拜占庭將軍問題的優(yōu)化

我們知道，區(qū)塊鏈的很大創(chuàng)新就是進一步優(yōu)化了解決大規(guī)模節(jié)點部署時的拜占庭系統(tǒng)的效率。

拜占庭將軍問題的難點在于，任意時間，一個節(jié)點都要考慮面對多個提案進行決策的問題。

區(qū)塊鏈優(yōu)化了這個模型，引入了POW機制，在同一時刻通過競爭出塊的方式，只允許一個節(jié)點發(fā)出請求。同時通過非對稱加密技術，保證了消息接受方可以確認發(fā)送方的身份，系統(tǒng)也變成了可信的分布式網絡。

此外，區(qū)塊鏈與以往的純粹算法演進來優(yōu)化拜占庭問題的方式不同。區(qū)塊鏈同時引入了經濟模型，讓拜占庭的犯錯成本為負數(shù)。我們知道在安全領域的一個基本觀點是，攻擊的收益必須大于成本。

在區(qū)塊鏈中，下一個節(jié)點由誰作為將軍，由POW工作量證明來決定。如果要做叛徒，攻擊整個網絡，需要付出相應的成本，而這個成本在比特幣的PoW（Proof of Work）工作量共識機制下，就是要掌握整個網絡50%以上的算力。換句話說，有50%以上的叛徒才行，這是比PBFT高得多的容錯率。從經濟學的角度來說，如果真的掌握那么大的算力的話，用這些算力維護網絡（誠實地挖礦）獲得的收益其實會高于破壞網絡。