區(qū)塊鏈中的拜占庭容錯(cuò)

Tendermint是一個(gè)分布式系統(tǒng)狀態(tài)復(fù)制引擎，用于在多臺機(jī)器安全一致地復(fù)制一個(gè)應(yīng)用。所謂安全性，指的是即使有多達(dá)1/3的機(jī)器出現(xiàn)任意故障的情況下， Tendermint仍然能夠正常工作。所謂一致性，指的是每一個(gè)正常工作的機(jī)器都會(huì)有著同樣的交易日志，計(jì)算相同的狀態(tài)。安全一致的復(fù)制是分布式系統(tǒng)中一個(gè)基本原則問題，它在各種應(yīng)用程序（從貨幣到選舉，到基礎(chǔ)設(shè)施規(guī)劃等）中的廣泛應(yīng)用的容錯(cuò)能力方面承擔(dān)了極其重要的作用。

Tendermint被設(shè)計(jì)成易于使用、易于理解，且性能優(yōu)異，適用于廣泛的分布式應(yīng)用。

正文

分布式共識系統(tǒng)成為現(xiàn)代互聯(lián)網(wǎng)基礎(chǔ)設(shè)施中的一個(gè)關(guān)鍵組件，正助力于每一個(gè)主要的互聯(lián)網(wǎng)應(yīng)用。本章節(jié)內(nèi)容介紹了必要的背景材料來理解和探討這些系統(tǒng)。

復(fù)制狀態(tài)機(jī)（Replicated State Machine）

最常見的用來研究和實(shí)施分布式共識（distributed consensus）的范例的是復(fù)制狀態(tài)機(jī)的范例，其中，一個(gè)確定的狀態(tài)機(jī)在數(shù)個(gè)進(jìn)程（processes）之間被復(fù)制，這樣不管部分進(jìn)程是否失敗，這些進(jìn)程看上去像單個(gè)狀態(tài)機(jī)。狀態(tài)機(jī)有一些列輸入驅(qū)動(dòng)，這些輸入被稱作交易（transactions），每一個(gè)交易根據(jù)其是否有效，可能引起一個(gè)狀態(tài)遷移并返回一個(gè)結(jié)果。更正式的，交易為數(shù)據(jù)庫上的原子操作（atomic operation），意味著其要么完成要么根本就沒有發(fā)生，不能返回一個(gè)中間狀態(tài)（ intermediate state）。狀態(tài)交易邏輯（state transition logic）由狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)移函數(shù)決定，這個(gè)函數(shù)映射了一個(gè)交易和目前的狀態(tài)到一個(gè)新的狀態(tài)和一個(gè)返回值。狀態(tài)轉(zhuǎn)移函數(shù)有時(shí)也被稱為應(yīng)用邏輯（application logic）。

訂購交易（order the transactions）并且將相應(yīng)的交易日志（ transaction log ）復(fù)制到每一個(gè)進(jìn)程是共識協(xié)議的責(zé)任。使用一個(gè)確定的（deterministic）狀態(tài)轉(zhuǎn)移函數(shù)意味著在給定同樣的交易日志的情況下，每一個(gè)進(jìn)程將計(jì)算出相同的結(jié)果。

復(fù)制狀態(tài)機(jī)架構(gòu)如圖所示。

如圖：一個(gè)復(fù)制狀態(tài)機(jī)在多個(gè)機(jī)器之間復(fù)制了一個(gè)交易日志和結(jié)果狀態(tài)。交易從客戶端接受，運(yùn)行了共識協(xié)議，在交易日志中訂購（ordered），最后執(zhí)行得到最新狀態(tài)。在圖中，每一個(gè)菱形代表了單個(gè)機(jī)器，其中，虛線代表機(jī)器間的通訊用來承載進(jìn)行訂購交易（ ordering transactions）的共識協(xié)議。

Tendermint的目標(biāo)是創(chuàng)建一個(gè)通用目的，高性能，安全和健壯的復(fù)制狀態(tài)機(jī)。

不同時(shí)性（Asynchrony）

容錯(cuò)復(fù)制狀態(tài)機(jī)（fault-tolerant replicated state machine）的目的是在對上層提供服務(wù)的時(shí)候，協(xié)調(diào)網(wǎng)絡(luò)中的計(jì)算機(jī)的同步，不管是否存在故障節(jié)點(diǎn)。

保持同步意味著成功復(fù)制交易日志；提供一個(gè)有用的服務(wù)意味著在處理新交易的時(shí)候保持狀態(tài)機(jī)的可用性。傳統(tǒng)上系統(tǒng)的這些方面被各自成為安全性（safety）和可用性（liveness）。通俗地，安全性意味著沒有任何壞的事情發(fā)生；可用性意味著好的事情最終發(fā)生。安全違規(guī)（ violation of safety）意味著存在兩個(gè)或者更多的有效的，競爭的交易日志。可用性違規(guī)（violating liveness ）意味著一個(gè)無法響應(yīng)的網(wǎng)絡(luò)。

通過接受所有的交易可以很容易來滿足可用性。通過不接受任何交易可以很容易來滿足安全性。因此，狀態(tài)機(jī)復(fù)制算法可以被看作在兩者之間的一個(gè)平衡。一般地，進(jìn)程在提交一個(gè)新的交易在之前，需要對來自于其他進(jìn)程的信息設(shè)立一個(gè)閾值。在同步的環(huán)境中，我們對網(wǎng)絡(luò)消息的最大延遲或者處理器時(shí)鐘的最大速度作出假設(shè)，通過輪流坐莊來提議新的交易，進(jìn)行大多數(shù)投票表決，如果提議者在同步假設(shè)的區(qū)間內(nèi)并沒有產(chǎn)生任何提議，則跳過（skip）提議者的這一回合。

在一個(gè)異步的環(huán)境中，沒有關(guān)于網(wǎng)絡(luò)延遲或者處理器速度的保證的假設(shè)，權(quán)衡將變得更為困難。事實(shí)上，所謂的FLP不可能性結(jié)果（FLP impossibility result）證明了在確定的異步進(jìn)程（單個(gè)進(jìn)程可能會(huì)崩潰）之間的分布式共識的不可能性。該證明意味著，因?yàn)檫M(jìn)程可能失敗，存在協(xié)議的有效執(zhí)行，但進(jìn)程恰好在某一時(shí)間崩潰這樣就阻止了共識。因此，我們對共識沒有任何保證。

一般地，協(xié)議中的同步是通過管理某些交易時(shí)用到的超時(shí)（timeouts）來進(jìn)行的。在異步環(huán)境中，消息能夠被任意延遲，依賴同步來確保安全性的話可能導(dǎo)致交易日志的分叉。依賴同步來保證系統(tǒng)的可用性能夠引起共識的宕機(jī)，并且服務(wù)無法響應(yīng)。前者通常被看作更為嚴(yán)重，因?yàn)檎{(diào)解沖突日志可能是一個(gè)令人生畏或者不可能的任務(wù)。

實(shí)際上，僅當(dāng)消息延遲能夠被良好的定義和控制的時(shí)候，同步解決方案才會(huì)被使用，例如在一架飛機(jī)上的控制器之間，或者利用同步的原子時(shí)鐘的數(shù)據(jù)中心之間。因此，盡管存在很多高效的同步解決方案，計(jì)算機(jī)網(wǎng)絡(luò)的一般化的不可靠性（general unreliability）太大以至于不能實(shí)際投入使用而不顯著增加額外的成本。

根本上有兩種途徑來克服FLP不可能性結(jié)果。第一個(gè)是采用更強(qiáng)的同步假設(shè)-甚至相當(dāng)弱的假設(shè)也是足夠的，例如，那個(gè)唯一的最終崩潰的進(jìn)程被懷疑崩潰了，正確的進(jìn)程不受影響。一般地，這個(gè)方法利用leaders，其扮演了一個(gè)特別的協(xié)作的角色，并且在超時(shí)并被認(rèn)為發(fā)生故障了以后可以被跳過。實(shí)際上，這樣的領(lǐng)導(dǎo)選取機(jī)制成功運(yùn)轉(zhuǎn)起來很難。

第二種克服FLP的方法是使用非確定性的-包含隨機(jī)化元素，這樣達(dá)成共識的可能性接近為1。盡管第二種方法更智能并且某些高級加密技術(shù)近些年來取得了速度上的提高，依賴隨機(jī)化的方法通常更慢。

廣播和共識

為了讓一個(gè)進(jìn)程復(fù)制狀態(tài)到其它進(jìn)程上，它必須有基本通訊原語的權(quán)限來允許其傳播或者傳遞信息。一個(gè)最有用的原語是可靠廣播（reliable broadcast）?？煽繌V播（RBC）是一個(gè)廣播原語滿足如下特性，對消息m，有：

有效性（validity） - 如果一個(gè)正確的進(jìn)程廣播m，它最終成功傳達(dá)了m

一致性（agreement） - 如果一個(gè)正確的進(jìn)程成功傳達(dá)了m，所有最終所有的進(jìn)程成功傳達(dá)m

完整性（integrity） - m只傳遞一次，并且是以廣播的形式被發(fā)送者發(fā)送出去

本質(zhì)上，可靠廣播使得消息最終到達(dá)所有的進(jìn)程一次。

另外，更有用的原語是原子廣播（ atomic broadcast（ABC）），其滿足可靠廣播（RBC）和另外的一個(gè)屬性：

總的順序（total order） - 如果正確的進(jìn)程p和q分別傳遞出m和m‘，p傳達(dá)m在m’之前，那么q傳達(dá)m在m‘之前

原子廣播是一個(gè)可靠的廣播，其中值（values）以相同的順序被發(fā)送到每個(gè)機(jī)器上。注意到這實(shí)際上復(fù)制交易日志的問題。通俗地講，該問題可以被稱作共識，共識原語的標(biāo)準(zhǔn)定義滿足以下條件：

終止性 - 每個(gè)正確的進(jìn)程最終能做出決定

完整性 - 每個(gè)正確的進(jìn)程最多只做出決定一次

一致性 - 如果一個(gè)進(jìn)程做出了v1的決定， 并且另外一個(gè)進(jìn)程做出了v2的決定，那么v1=v2

有效性 - 如果一個(gè)正確的進(jìn)程做出了v的決定，至少一個(gè)進(jìn)程提議了v

直觀地，共識和原子廣播看上去十分類似，主要的差異在于，原子廣播本身作為一個(gè)協(xié)議是連續(xù)的，然而共識期望終止。這就是說，每一個(gè)可以精簡為另一個(gè)。共識可以被精簡為原子廣播通過決定第一個(gè)原子廣播的值。原子廣播可以精簡為共識，通過依次運(yùn)行許多共識協(xié)議的實(shí)例，然而存在一些微妙的考量，特別是在處理拜占庭故障方面。

一個(gè)完整的參數(shù)空間的關(guān)于原子廣播精簡為共識的描述仍然是一個(gè)開放的研究話題。

歷史上，盡管大多數(shù)用例實(shí)際上需要原子廣播，采用的最為廣泛的算法是稱作Paxos的共識算法，在90年代介紹并且證明該算法正確性的是Leslie Lamport。Paxos同時(shí)賦予和困惑了共識科學(xué)，一方面提供了第一個(gè)真實(shí)世界的，實(shí)用的，容錯(cuò)的共識算法，另一方面又難于理解和解釋。算法的具體實(shí)現(xiàn)使用了其專門的技術(shù)來從Paxos建立原子廣播，使得這個(gè)生態(tài)難于操縱，理解和利用。不幸的是，幾乎沒有任何工作使得提高該框架更容易理解，盡管有嘗試來描繪解決方案中的各種困難。

在2013年，Ongaro和 Ousterhout發(fā)表了Raft，一個(gè)狀態(tài)機(jī)復(fù)制算法，其主要的設(shè)計(jì)動(dòng)機(jī)是可理解性。與其從一個(gè)共識算法開始，并且嘗試建立原子廣播，Raft的設(shè)計(jì)首先考慮的是交易日志，尋求正交組件，其組合在一起來提供最終的原子廣播，盡管其不是被這樣描述的。

Paxos是工業(yè)領(lǐng)域的主要共識算法，在工業(yè)領(lǐng)域像亞馬遜，谷歌和其他擴(kuò)建了高可用性全球互聯(lián)網(wǎng)服務(wù)的公司。

Paxos 共識位于應(yīng)用程序棧的底部，提供了資源管理和分配的一致接口，操作在一個(gè)更慢的時(shí)標(biāo)相比于其他面對用戶的高可用性應(yīng)用程序。

Raft登場以來得到了廣泛的采用，特別是在開源社區(qū)，其具有多個(gè)主流語言的實(shí)現(xiàn)，并且在多數(shù)項(xiàng)目中作為其主干。

Raft與Paxos在設(shè)計(jì)方面主要的不同是先聚焦于交易日志，而不是單個(gè)值，特別是允許一個(gè)leader持續(xù)提交交易直到其卸任，這時(shí)領(lǐng)導(dǎo)選舉開始生效。在某種程度上，這類似于在區(qū)塊鏈中采用的方法，盡管其主要優(yōu)勢是能夠容忍不同種類故障。

拜占庭容錯(cuò)（Byzantine Fault Tolerance）

區(qū)塊鏈通過在共享數(shù)據(jù)庫上責(zé)任的去中心化，減少了對手方風(fēng)險(xiǎn)，因此被稱為“信任機(jī)器”。比特幣由其具有的抵抗任何攻擊和惡意行為的能力而著稱。傳統(tǒng)地，容忍惡意行為的共識協(xié)議被稱為拜占庭容錯(cuò)共識協(xié)議（Byzantine Fault Tolerant ）。術(shù)語“拜占庭”被使用，源于拜占庭將軍們面對的類似問題，這些將軍們嘗試相互協(xié)調(diào)來攻擊羅馬，使用唯一的信使，其中一個(gè)將軍可能是叛徒。

在一個(gè)崩潰故障中，一個(gè)進(jìn)程可能宕機(jī)。在一個(gè)拜占庭故障中，故障節(jié)點(diǎn)能做任何事情。崩潰的故障更容易處理，因?yàn)闆]有進(jìn)程會(huì)對其他進(jìn)程說謊。只存在崩潰故障的系統(tǒng)可以通過簡單的多數(shù)決定規(guī)則（ majority rule）來操作，因此通常能夠同時(shí)容忍近一半的系統(tǒng)故障。如果系統(tǒng)能夠容忍失敗的數(shù)量是f，這樣系統(tǒng)必須至少有2f+1個(gè)進(jìn)程。

拜占庭故障復(fù)雜一些。在一個(gè)具有2f+1進(jìn)程的系統(tǒng)中，如果f是拜占庭，這些拜占庭節(jié)點(diǎn)可以協(xié)作來說任何事情對另外f+1的進(jìn)程。例如，我們嘗試取得單比特共識，并且f=1，所以我們有N=3個(gè)進(jìn)程，A，B，C，其中C是拜占庭，如圖2.2所示。C可以告訴A這個(gè)值是0，告訴B這個(gè)值是1。如果A同意它是0，B同意它是1，那么他們都將認(rèn)為他們獲得了大多數(shù)，提交，這樣就違反了安全條件。因此，拜占庭系統(tǒng)能夠容忍的故障上限小于非拜占庭系統(tǒng)。

如上圖 一個(gè)拜占庭進(jìn)程C，告訴A一件事，告訴B另外一件，致使他們得出關(guān)于網(wǎng)絡(luò)的不同的結(jié)論。這里。簡單的大多數(shù)投票導(dǎo)致了安全違規(guī)，源于單個(gè)拜占庭進(jìn)程。

事實(shí)上，可以證明拜占庭故障的上限為f

在1999年，Castro 和 Liskov 發(fā)表了實(shí)用拜占庭容錯(cuò)（Practical Byzantine Fault Tolerance），提供了第一個(gè)優(yōu)化的適用于實(shí)際的拜占庭容錯(cuò)算法。其為工業(yè)系統(tǒng)中拜占庭容錯(cuò)的實(shí)用性設(shè)定了一個(gè)新的先例，每秒可以處理成千上萬比交易。除此之外，拜占庭容錯(cuò)仍然是被人認(rèn)為是昂貴的，大部分時(shí)間是不必要的，并且最流行的實(shí)現(xiàn)很難建立在其上面。因此，盡管學(xué)術(shù)對其興趣日增，包括大量提高了的變種，但在實(shí)施和配置方面并沒有太多進(jìn)展。進(jìn)一步，如果網(wǎng)絡(luò)中超過1/3的節(jié)點(diǎn)是拜占庭，PBFT將不能提供任何保證。

密碼學(xué)，信任和經(jīng)濟(jì)學(xué)

根本上說，容錯(cuò)這個(gè)問題起源于缺乏信任 - 不知道一些進(jìn)程將如何表現(xiàn)（behave）。正式地，信任需要從理論上被定義成一種信息，其作為一種減少世界模型熵的手段-信任某個(gè)人就是樂觀地減少這個(gè)人對于這個(gè)世界的不確定性，使得可以把注意力放在更高階的組織層面上。

密碼學(xué)原語從根本上與信任問題相關(guān)，主要被定義為允許熵大量減少的機(jī)制-成功認(rèn)證一個(gè)密碼學(xué)函數(shù)把一個(gè)可能結(jié)果的分布坍縮成一個(gè)點(diǎn)，或者在一些例子中一些少量的結(jié)果。

它是做所周知的有著更好制度信任的文明，例如法治具有更高的生產(chǎn)率和更充滿生氣的經(jīng)濟(jì)。結(jié)果產(chǎn)生了一個(gè)直觀的感覺，能夠更多的信任相互作用，減少可能結(jié)果的空間，其需要被主動(dòng)建模，使其更容易協(xié)調(diào)。不幸的是，評價(jià)現(xiàn)代機(jī)構(gòu)的信譽(yù)越來越困難，因?yàn)樗麄兊膹?fù)雜度在近些年增加了很多，增加了可能性，其聲稱的確定性是幻覺。

幸運(yùn)的是，密碼學(xué)形成了社會(huì)中心的信任體系的基礎(chǔ)，奇跡大地提高了人類在全球范圍內(nèi)協(xié)作的能力，由于減少了欺騙和無責(zé)任行動(dòng)的風(fēng)險(xiǎn)。比較有趣的是密碼學(xué)原語在BFT算法中的重要性，為了認(rèn)證和散播不確定性。

最有趣的是，經(jīng)濟(jì)機(jī)制也能當(dāng)作減少熵的一種方式，迄今為止經(jīng)濟(jì)代理可以被激勵(lì)-更有可能被用來執(zhí)行一個(gè)特定的行為。比特幣深入的洞察是密碼原語可以與經(jīng)濟(jì)激勵(lì)結(jié)合起來有效減少公共共識網(wǎng)絡(luò)的熵來取得狀態(tài)安全復(fù)制。

更正式的信任的信息理論根基，密碼學(xué)，共識和經(jīng)濟(jì)學(xué)和他們之間的關(guān)系的調(diào)查將會(huì)在以后的工作中展開。

區(qū)塊鏈

區(qū)塊鏈的核心是一個(gè)關(guān)于拜占庭容錯(cuò)原子廣播的聚焦完整性的方法。例如，比特幣區(qū)塊鏈結(jié)合了經(jīng)濟(jì)學(xué)和密碼學(xué)隨機(jī)化來提供一個(gè)強(qiáng)的概率保證，保證安全違規(guī)不會(huì)發(fā)生，給定了一個(gè)弱同步假設(shè)，即區(qū)塊間的通訊比產(chǎn)生哈希碰撞更迅速。實(shí)際上，然而，眾所周知，比特幣的安全保證容易受到各種狡猾（subtle）的攻擊。

區(qū)塊鏈從兩個(gè)關(guān)鍵的優(yōu)化中得到它的名字，其利用這兩個(gè)優(yōu)化解決了原子化廣播的問題。第一個(gè)是交易以塊為單位進(jìn)行分組來分?jǐn)偢咛峤谎舆t（在10min量級）。第二個(gè)優(yōu)化是通過加密哈希把區(qū)塊鏈接起來成為一個(gè)不可篡改的鏈，這樣就很容易驗(yàn)證歷史記錄。兩個(gè)優(yōu)化都相對于原始的BFT-ABC的有所提高，前者提高了性能，后者提高了容錯(cuò)。

經(jīng)過這幾年的發(fā)展，使用哈希鏈接交易塊并以原子廣播發(fā)送出去已經(jīng)成為公共的區(qū)塊鏈共識算法。據(jù)作者所知，Tendermint是第一個(gè)這樣的提議，升級了知名的80年代的BFT算法，成為了自成體系的共識算法。Tendermint被IBM跟進(jìn)，IBM升級PBFT到區(qū)塊鏈，JP摩根升級了一個(gè)Raft的BFT版本。

過程演算

各個(gè)部分同時(shí)執(zhí)行的分布式系統(tǒng)，因難以設(shè)計(jì)、構(gòu)建和調(diào)試而飽受詬病。它們更難以正式驗(yàn)證，因?yàn)榇蠖鄶?shù)技術(shù)的形式驗(yàn)證，以及實(shí)際上非?；A(chǔ)的計(jì)算機(jī)科學(xué)，都是通過推算得到的，因此很難正式驗(yàn)證。

過程演算是一種為并發(fā)計(jì)算提供了有條理的基礎(chǔ)原理的模型系列。最通常的演算方法，Communicating Sequential Processes（CSP）構(gòu)成了許多現(xiàn)代編程語言的理論基礎(chǔ)。比如Go語言，在設(shè)計(jì)中包含了并發(fā)原語。

我們可以使用一個(gè)正式的邏輯來表達(dá)一個(gè)過程可能滿足的屬性。舉例來說，模態(tài)Hennessy–Milner邏輯可以表示，在某些或所有形式的動(dòng)作發(fā)生后，一個(gè)進(jìn)程將滿足其他一些邏輯表達(dá)式。通過將更復(fù)雜的運(yùn)算方法添加到邏輯中，可以建立正式的系統(tǒng)，可以很容易地描述分布式系統(tǒng)的重要屬性，比如安全性、可用性和本地化等。通過π-calculus編寫的系統(tǒng)可以被正式驗(yàn)證，以滿足使用模型檢查軟件的相關(guān)屬性。

當(dāng)我們使用π-calculus來詳細(xì)說明Tendermint算法時(shí)，我們會(huì)使用相關(guān)的正式邏輯，以及相應(yīng)的屬性驗(yàn)證，以備將來的工作。

Tendermint的需求

比特幣及其衍生物的成功，特別是以太坊和他們的關(guān)于安全，自治，分布式，對任意代碼的容錯(cuò)執(zhí)行的前景引起了事實(shí)上每一個(gè)主要的金融機(jī)構(gòu)的興趣。特別地，出現(xiàn)了對兩種種區(qū)塊鏈技術(shù)：一方面是公鏈，被親切地稱為Big Dad公鏈（Big Bad Public Blockchains），其協(xié)議被內(nèi)建經(jīng)濟(jì)激勵(lì)通過原生貨幣（native currency）的方式所支配。

另一方面是所謂的私有鏈，更準(zhǔn)確的被稱為“聯(lián)盟鏈”（ consortia blockchains），通過哈希樹的使用，數(shù)字簽名，p2p網(wǎng)絡(luò)和加強(qiáng)的問責(zé)制，其對傳統(tǒng)共識和拜占庭算法有一定的提高。

就像現(xiàn)代社會(huì)的基礎(chǔ)設(shè)施持續(xù)的去中心化或者正如商業(yè)的跨組織本質(zhì)，對透明，問責(zé)和高性能的拜占庭系統(tǒng)的需求越來越多，這個(gè)系統(tǒng)支持的應(yīng)用程序從財(cái)政到域名注冊到電子投票和與治理的高級機(jī)制協(xié)作和未來的演進(jìn)。

Tendermint這個(gè)解決方案對聯(lián)盟或者跨組織邏輯進(jìn)行了優(yōu)化，但是足夠靈活來容納任何人，從私有企業(yè)到全球貨幣，并且性能足夠高來與主要的，非拜占庭容錯(cuò)的，共識解決方案競爭例如 etcd， consul， and zookeeper，于此同時(shí)提供了更強(qiáng)的恢復(fù)性，安全保證，對應(yīng)用開發(fā)者的靈活性。