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

小資料：

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

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

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

一、N>=3f+1就可以解決拜占庭問(wèn)題

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

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

在左邊的場(chǎng)景中，P2接受到了2個(gè)不同的值（v，u），但是不知道那個(gè)是司令傳來(lái)的。因此無(wú)法做出決策。

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

當(dāng)解決拜占庭將軍問(wèn)題的節(jié)點(diǎn)數(shù)量為N>=3f+1時(shí)，我們?cè)賮?lái)推導(dǎo)一下上述的問(wèn)題，以N>=4，f=1的場(chǎng)景為例：

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

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

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

在右圖的場(chǎng)景中，司令是錯(cuò)的，但是正確的3個(gè)下屬節(jié)點(diǎn)可以達(dá)成一致：

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

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

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

盡管拜占庭系統(tǒng)可以就人類信任決策的問(wèn)題達(dá)成最終一致共識(shí)，有很大的商業(yè)應(yīng)用場(chǎng)景，但是當(dāng)我們想應(yīng)用時(shí)，卻發(fā)現(xiàn)系統(tǒng)是非常低效的。我們知道每一輪決策的代價(jià)是消息傳遞的輪數(shù)以指數(shù)級(jí)的方式增長(zhǎng)，因此使用這個(gè)辦法解決拜占庭問(wèn)題，因?yàn)樾实挠绊懸矡o(wú)法在實(shí)際業(yè)務(wù)中得到應(yīng)用。

二、拜占庭系統(tǒng)的技術(shù)演進(jìn)

PBFT拜占庭系統(tǒng)

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

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

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

HQ拜占庭系統(tǒng)

于是Cowling等人在2006年HQ來(lái)改進(jìn)PBET，下圖為HQ模型的原理圖：

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

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

所以HQ協(xié)議通信模型并沒(méi)有改變PBFT的架構(gòu)，只是當(dāng)客戶端發(fā)送請(qǐng)求，并且沒(méi)有競(jìng)爭(zhēng)的情況出現(xiàn)時(shí)，這個(gè)模式才有效。

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

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

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

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

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

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

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

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

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

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

拜占庭將軍問(wèn)題的難點(diǎn)在于，任意時(shí)間，一個(gè)節(jié)點(diǎn)都要考慮面對(duì)多個(gè)提案進(jìn)行決策的問(wèn)題。

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

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

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