Abstract

Tendermint 是一種在對(duì)抗條件下分布式網(wǎng)絡(luò)中的新事件排序協(xié)議，更常見地被認(rèn)為是一致性算法或原子廣播。由于廣泛地成功解決了不需中央集權(quán)的公共設(shè) 置問題在比如比特幣、以太坊的虛擬貨幣領(lǐng)域，這個(gè)問題最近吸引了大量關(guān)注。 Tendermint 將為了提供一個(gè)有問責(zé)保障制度的安全一致性協(xié)議以及在一致性算 法之上建立任意應(yīng)用的接口的經(jīng)典學(xué)術(shù)工作現(xiàn)代化。Tendermint 是高性能的，每 秒可以在全球數(shù)十個(gè)節(jié)點(diǎn)上以大約一秒的延遲完成數(shù)千個(gè)交易，并且在面對(duì)對(duì)抗 攻擊時(shí)，性能受到適度降低。

Chapter 1

介紹
今天，計(jì)算機(jī)工程的殘酷事實(shí)是計(jì)算機(jī)是有缺點(diǎn)的，它們開始宕機(jī)，速度變慢，表現(xiàn)越來越差。更糟糕的是，我們傾向于關(guān)注把電腦連入網(wǎng)絡(luò)(比如互聯(lián)網(wǎng))， 然而網(wǎng)絡(luò)比計(jì)算機(jī)具有更高的不可預(yù)見性。這些挑戰(zhàn)首要任務(wù)是關(guān)注“可容錯(cuò)的 分布式計(jì)算(fault tolerant distributed computing)”，來找到有原則的協(xié)議設(shè)計(jì)， 使得當(dāng)被提供有用的服務(wù)時(shí)，在錯(cuò)誤網(wǎng)絡(luò)中連接的錯(cuò)誤計(jì)算機(jī)保持同步。本質(zhì)上，就是在不可靠當(dāng)中生產(chǎn)出一個(gè)可靠的系統(tǒng)。
然而，在這個(gè)迅速增長的數(shù)字化和全球化世界，系統(tǒng)不能僅僅在面對(duì)不可靠部分時(shí)可靠，還得在面對(duì)惡毒環(huán)境或“拜占庭(Byzantine)”情況可靠。在過去 十年間，大部分關(guān)鍵構(gòu)造的組件已經(jīng)被傳送到有網(wǎng)絡(luò)支持的系統(tǒng)中，就如同世界 經(jīng)濟(jì)的大量組件。作為回應(yīng)，則產(chǎn)生了網(wǎng)絡(luò)戰(zhàn)爭、經(jīng)濟(jì)詐騙和一個(gè)徹底的金融和 政治原則的扭曲。

1.1 比特幣(Bitcoin)

在2009年，一個(gè)自稱Satoshi Nakamoto的匿名軟件開發(fā)者引介了一種解決這些
問題的方法，就是一個(gè)同時(shí)進(jìn)行在計(jì)算機(jī)科學(xué)、金融和政治領(lǐng)域的實(shí)驗(yàn)，一種叫 做比特幣的虛擬電子貨幣。比特幣是第一個(gè)用來解決在面對(duì)惡性對(duì)抗情況下環(huán)境 的容錯(cuò)分布式計(jì)算問題的協(xié)議。用區(qū)塊鏈技術(shù)實(shí)現(xiàn)了一種數(shù)字貨幣，通過經(jīng)濟(jì)激 勵(lì)解決哈希碰撞的人，交易(transactions)達(dá)成共識(shí)。實(shí)質(zhì)上，交易是以區(qū)塊的 形式被那些發(fā)現(xiàn)數(shù)據(jù)交易中的部分哈希碰撞的人排序。通過這種方式，正確順序 就是使得碰撞有最高累計(jì)難度的那個(gè)。這個(gè)解決辦法被叫做Proof-of-Work (PoW)。
比特幣的精妙之處在于它發(fā)明了一種貨幣，一種加密貨幣，而且發(fā)給那些解 決哈希碰撞的人，交換他們做的解決部分哈希碰撞如此昂貴的事情。在精神上，可能假設(shè)解決這些問題的能力將會(huì)作為計(jì)算能力來分發(fā)，這樣使得每個(gè)人都可以 用一個(gè)CPU就能參與其中。不幸的是，比特幣網(wǎng)絡(luò)已經(jīng)成長為這個(gè)星球上最大的 超級(jí)計(jì)算機(jī)實(shí)體，超過所有其他的總和，僅評(píng)估一個(gè)單獨(dú)的功能，通過幾個(gè)數(shù)據(jù) 中心分發(fā)運(yùn)行主要由一小部分中國公司生產(chǎn)的專有集成電路(ASICs)，就要大 概一天消耗兩百萬美元的電力。長遠(yuǎn)地看，它的技術(shù)設(shè)計(jì)也有局限性:需要花費(fèi) 高達(dá)一個(gè)小時(shí)的時(shí)間來確定交易，這樣就很難在頂層建立應(yīng)用，而且無法以一種 維持安全保證的方式來衡量。這還沒有提及由于比特幣社區(qū)的不成熟管理機(jī)制導(dǎo)
致的內(nèi)部政治斗爭。
放下這些問題，令人驚訝的是，比特幣和它的技術(shù)持續(xù)地?cái)噭?dòng)密碼學(xué)和分布式數(shù)據(jù)庫以及合作經(jīng)濟(jì)，同樣也持續(xù)吸引著幾十億的資本投資，包括新公司和新 的加密貨幣，它們都以其獨(dú)特的方式從比特幣中分化出來。

1.2 Tendermint

在 2014 年，Jae Kwon 開始開發(fā) Tendermint，一個(gè)通過使存在了數(shù)十年但是缺少社會(huì)背景，直到今天還需要廣泛部署的問題的解決辦法現(xiàn)代化的方法，尋找解 決排序和執(zhí)行一系列在對(duì)抗環(huán)境下的交易的一致性問題的辦法。
在 2015 年年初，在一項(xiàng)由 Eris Industries 領(lǐng)導(dǎo)的項(xiàng)目中，把實(shí)際區(qū)塊鏈解決 方案應(yīng)用在工業(yè)生產(chǎn)中，作者加入 Jae Kwon 開發(fā) Tendermint 軟件和協(xié)議。
這次合作的產(chǎn)物就是 Tendermint 平臺(tái)，包含一份一致性協(xié)議，一個(gè)高性能的 Go 語言實(shí)現(xiàn)，一個(gè)靈活的可以在一致性基礎(chǔ)上建立任意應(yīng)用的接口，以及一套 部署和管理工具。我們相信，對(duì)比之前的方法，Tendermint 完成了一份極好的設(shè) 計(jì)和實(shí)現(xiàn)。以前的方法包括那些經(jīng)典學(xué)術(shù)文獻(xiàn)和比特幣及其通過組合每個(gè)正確元 素達(dá)到安全性、性能和簡單性平衡的衍生物。
Tendermint 平臺(tái)是開源的，可以在 https://github.com/tendermint/tendermint 獲得，以及相關(guān)的存儲(chǔ)庫在 https://github.com/tendermint。其核心是許可的 GPLv3，大部分的庫都是 Apache 2.0。

1.3 貢獻(xiàn)

這篇文章的主要貢獻(xiàn)參見第三章和第九章。一些重要的意義有: ·一份正式的 Tendermint 的 pi 演算說明書，一份非正式的關(guān)于其安全和義務(wù)
的正確性證明(第三章)。 ·一個(gè)使得其核心一致性狀態(tài)機(jī)更魯棒，更具確定性和更加易于理解的重構(gòu)。 ·軟件在正常，錯(cuò)誤及惡劣環(huán)境下大規(guī)模部署的性能和特征評(píng)估(第九章)。 ·無數(shù)的附加測(cè)試帶來的無數(shù)的 bug 修復(fù)和性能提升。 第四到第八章講述了一個(gè)完整系統(tǒng)中的很多其他的組件。其中一些，比如用來傳播數(shù)據(jù)的子協(xié)議(第四章)和各種底層軟件庫(第八章)，是 Jae Kwon 在 作者加入之前設(shè)計(jì)并實(shí)現(xiàn)的。其余部分是在常規(guī)資訊作者和被作者啟發(fā)設(shè)計(jì)與實(shí) 現(xiàn)的。對(duì)于更多直接詳盡的解釋，請(qǐng)參見 Github。
盡管沒在文章里闡述，作者還在這段時(shí)間做了一些以太坊項(xiàng)目的貢獻(xiàn)，一個(gè) 比特幣的替代品，概括從貨幣到任意應(yīng)用的技術(shù)的應(yīng)用。另外，作者被邀請(qǐng)參加 數(shù)不清的場(chǎng)合，做關(guān)于以太坊和 Tendermint 私下的或公開的演講，包括以指導(dǎo) 人和演講者的身份。
最后一點(diǎn)，盡管第十章被放到了最后，但是如果在第三章之前讀它，它會(huì)提 供極其重要的內(nèi)容并加固理解這篇文章。然而，為了不耽誤讀者認(rèn)識(shí) Tendermint， 它被放在了最后。

Chapter 2

背景
分布式一致性系統(tǒng)已經(jīng)成為現(xiàn)代互聯(lián)網(wǎng)基礎(chǔ)設(shè)施的關(guān)鍵組件，在某些水平上， 為每一個(gè)互聯(lián)網(wǎng)應(yīng)用提供動(dòng)力。本章介紹了理解和討論這些系統(tǒng)的必要背景材料。 另外，還介紹了 pi 演算，一個(gè)描述并發(fā)進(jìn)程的正式語言，它將在第三章中被用 來闡釋 Tendermint 算法。

2.1 復(fù)制狀態(tài)機(jī)(replicated state machine)

最常見的學(xué)習(xí)和實(shí)現(xiàn)分布式一致性的范例就是復(fù)制狀態(tài)機(jī)。在其中，一個(gè)決定性狀態(tài)機(jī)通過一系列進(jìn)程被復(fù)制，為了使其以一個(gè)單狀態(tài)機(jī)運(yùn)行，不去管那些 失敗的進(jìn)程。狀態(tài)機(jī)由一組稱為交易的輸入驅(qū)動(dòng)，每個(gè)交易根據(jù)其有效性可能會(huì) 或可能不會(huì)導(dǎo)致狀態(tài)轉(zhuǎn)換并返回結(jié)果。更正式地說，一個(gè)交易就是一個(gè)數(shù)據(jù)庫原 子操作，意味著它要么完成，要么就沒發(fā)生，不會(huì)出現(xiàn)中間狀態(tài)。狀態(tài)轉(zhuǎn)移邏輯 由狀態(tài)機(jī)的交易函數(shù)控制，映射一個(gè)交易和當(dāng)前狀態(tài)到一個(gè)新的狀態(tài)和返回結(jié)果。 狀態(tài)轉(zhuǎn)移函數(shù)有時(shí)也會(huì)被指向?yàn)閼?yīng)用邏輯。
交易排序是一致性協(xié)議的職責(zé)，這樣，產(chǎn)生的交易日志剛好被每個(gè)進(jìn)程復(fù)制 一遍。使用一個(gè)決定性的狀態(tài)轉(zhuǎn)移函數(shù)意味著每個(gè)進(jìn)程將計(jì)算由相同交易日志提 供的相同狀態(tài)。
圖 2.1 給出了復(fù)制狀態(tài)機(jī)架構(gòu)的總覽。
Tendermint 從渴望創(chuàng)造一個(gè)通用的，高性能的，安全的，以及魯棒的復(fù)制狀 態(tài)機(jī)中獲得激發(fā)。

2.2 異步性(asynchrony)

容錯(cuò)復(fù)制狀態(tài)機(jī)的目的是協(xié)調(diào)一個(gè)計(jì)算機(jī)網(wǎng)絡(luò)，當(dāng)提供有用的服務(wù)時(shí)保持同步，盡管存在那些錯(cuò)誤。
保持同步相當(dāng)于成功地復(fù)制交易日志;提供有用的服務(wù)相當(dāng)于保持狀態(tài)機(jī)對(duì)于新交易可用。系統(tǒng)這兩方面在傳統(tǒng)上分別被認(rèn)知為安全性(safety)和活性 (liveness)。通俗地講，安全性意味著沒有壞事情發(fā)生;活性意味著好事情終 將發(fā)生。違背安全性導(dǎo)致兩個(gè)或更多有效的相互矛盾的交易日志。違背活性導(dǎo)致 無響應(yīng)的網(wǎng)絡(luò)。
通過接受所有交易可以很容易滿足活性。通過不接受任何交易可以很容易滿 足安全性。因此，狀態(tài)機(jī)復(fù)制算法可以被看見地操作在一個(gè)由這些極端條件定義 的范圍內(nèi)。典型地，進(jìn)程需要在提交新交易之前接受從其他進(jìn)程得到的信息的閾值。在同步環(huán)境中，我們做出網(wǎng)絡(luò)消息延遲的最大值或者處理器速度的最大值的假設(shè)，那就足夠容易去輪流提出新交易，贊成得到大多數(shù)投票的提出者，跳過沒有在假設(shè)的限定內(nèi)提議的提議者的回合。
在異步環(huán)境中，在沒有網(wǎng)絡(luò)延遲和處理器速度保障的情況下，交易變得特變 難于管理。實(shí)際上，所謂的 FLP 不可能結(jié)果(FLP impossibility result)論證了在 一個(gè)異步的分布式系統(tǒng)中，即是只是容忍一個(gè)進(jìn)程的錯(cuò)誤，也不存在一個(gè)一致性 算法可以保證正確性。因?yàn)檫M(jìn)程可以失敗，證據(jù)相當(dāng)于顯示了存在協(xié)議的有效執(zhí)行，在恰好的時(shí)機(jī)進(jìn)程失敗來阻止一致性。因此，我們不能保證一致性。
典型地，一個(gè)協(xié)議的同步性由使用超時(shí)反射來管理特定的轉(zhuǎn)變。在異步環(huán)境，消息可能會(huì)反復(fù)延遲，依賴同步(超時(shí))安全會(huì)導(dǎo)致在交易日志中的分歧。依賴同步來確?；钚詴?huì)引起一致性停止和服務(wù)無響應(yīng)。前一種情況通常被認(rèn)為更嚴(yán)重， 因?yàn)檎{(diào)節(jié)沖突日志是令人頭疼甚至無法完成的任務(wù)。
實(shí)際上，同步的方法只應(yīng)用在消息延遲極其好控制的情況下，比如在同一架 飛機(jī)上的控制員之間，或者利用同步原子鐘的數(shù)據(jù)中心之間。因此，雖然存在許 多有效的同步解決方案，但是計(jì)算機(jī)網(wǎng)絡(luò)的一般不可靠性對(duì)于在沒有顯著的額外 成本的實(shí)踐中來說，風(fēng)險(xiǎn)太大。
根本上，有兩個(gè)方法可以克服 FLP 不可能性結(jié)果。第一個(gè)是使用更有力的同步假 設(shè)，即使弱一點(diǎn)的假設(shè)已經(jīng)很充分了。比如說，只有在最終的時(shí)候，崩潰的進(jìn)程 會(huì)被懷疑會(huì)崩潰，正確的則不會(huì)。典型地，這種方法利用那些扮演特定協(xié)調(diào)角色 的，還有那些如果在超時(shí)后被懷疑會(huì)出錯(cuò)被跳過的領(lǐng)導(dǎo)者們。實(shí)際上，這種領(lǐng)導(dǎo)者選舉機(jī)制很難正確。
第二種克服 FLP 的方法是使用非決定論，包含隨機(jī)因素，從人的直觀上來說， 可以克服 FLP，原因就是大概率上，是可以達(dá)成一致的。聰明地，依賴隨機(jī)會(huì)顯著降低速度，盡管某些高級(jí)的密碼編寫的技術(shù)最近幾年在速度上取得了極大的提升。

2.3 廣播和一致性

為了使一個(gè)進(jìn)程可以在其他進(jìn)程上復(fù)制自己的狀態(tài)，它必須有權(quán)限進(jìn)入允許它傳播或者傳送信息的基本通信基元(primitives)。一個(gè)最有用的這種基元之一 就是可靠廣播(reliable broadcast)?？煽繌V播(RBC)是一個(gè)基元，對(duì)于消息 m， 滿足:
·有效性(validity)-如果一個(gè)正確的進(jìn)程廣播 m，它最終會(huì)傳送 m
·一致性(agreement)-如果一個(gè)正確的進(jìn)程傳送 m，所有正確的進(jìn)程最終都會(huì)傳送 m
·完整性(integrity)-m 只會(huì)被傳送一次，而且只在被自己的發(fā)送者廣播的時(shí)候
本質(zhì)上，RBC 使得一條消息最終被所有的正確進(jìn)程傳送一次。
另一種更有用的基元原子廣播(atomic broadcast – ABC)，滿足所有 RBC 的屬性和一條額外的屬性:
·總序性(total order)-如果正確進(jìn)程 p 和 q 傳送 m 和 m’，則如果 q 在傳送 m’前傳送 m，p 就在傳送 m’前傳送 m
當(dāng)值在每個(gè)主機(jī)上以相同的順序傳送，原子廣播也是一個(gè)可靠廣播。注意這 一點(diǎn)恰好是復(fù)制一條交易日志的問題所在。通俗地說，這個(gè)問題會(huì)被歸諸于一致性(consensus)，一致性基元的標(biāo)準(zhǔn)定義滿足一下要求:
·終止性(termination)-每個(gè)正確進(jìn)程最終都會(huì)決定 ·完整性(integrity)-每個(gè)正確進(jìn)程最多決定一次
·一致性(agreement)-如果一個(gè)正確進(jìn)程決定 v1，另外一個(gè)決定 v2，則 v1 = v2
·有效性(validity)-如果一個(gè)正確進(jìn)程決定 v，則至少是有一個(gè)進(jìn)程提議了 v
直觀地看，consensus 和 ABC 驚人的相似，最不同的地方就在于 ABC 是連續(xù)的協(xié)議，而 consensus 需要有終止。也就是說，被人們所知的，它們都可以簡化成彼此。consensus 可以很容易地通過決定第一個(gè)值為原子廣播來簡化為 ABC。 ABC 可以依次地運(yùn)行一致性協(xié)議的多個(gè)實(shí)例來簡化為 consensus，盡管某些微妙的事項(xiàng)一定要注意，尤其那些用來處理拜占庭錯(cuò)誤的。圍繞 ABC 簡化為 consensus 的參數(shù)空間的一個(gè)完整描述依舊是一個(gè)開放的研究話題。
從歷史來看，盡管大部分用例實(shí)際上需求 ABC，但是最廣為被采納的是一個(gè) 用 Leslie Lamport 在 90 年代引入的，也被證實(shí)是正確的一致性算法，Paxos。Paxos 同時(shí)即允許又拒絕一致性科學(xué)(consensus science)的準(zhǔn)則。一方面，它提供第一次真實(shí)世界(first real-world)、實(shí)際的、容錯(cuò)的一致性算法，另一方面，卻又 十分的難以理解和解釋。該算法的每種實(shí)現(xiàn)都使用了自己的專門的技術(shù)包從 Paxos 建立 ABC，使得整個(gè)生態(tài)系統(tǒng)難以操縱、理解、利用。遺憾的是，盡管在針對(duì)不同困難去尋找解決方案付出了很多努力，但是想使其更容易被理解，幾乎 沒有取得任何進(jìn)展。
2013 年，Ongaro 和 Ousterhout 發(fā)表了 Raft，一個(gè)激發(fā)設(shè)計(jì)目的非常易懂的 狀態(tài)機(jī)復(fù)制算法。Raft 的設(shè)計(jì)不是從一致性算法出發(fā)并試圖建立它所需的(ABC)， 它最先也是最重要考慮的是交易日志，并尋找可以組合在一起最終能提供 ABC 的正交組件，雖然它不是被描述成這樣的。
Paxos 已經(jīng)成為行業(yè)內(nèi)主要的一致性算法，超過像 Amazon，Google 等公司， 其他也已經(jīng)建立起了具有高可用性的全球互聯(lián)網(wǎng)服務(wù)。Paxos 一致性算法位于應(yīng) 用棧的最底層，提供一個(gè)統(tǒng)一的資源管理和分配的接口，操作時(shí)間尺度比用戶面 對(duì)的具有高可用性的應(yīng)用更慢。
然而，自問世以來，Raft 已經(jīng)被廣泛采納，尤其是在開源社區(qū)，幾乎被每種 主流語言所實(shí)現(xiàn)，并且在主要項(xiàng)目作為骨干使用，包括 CoreOs 分布式 Linux 發(fā)行 版，以及開源時(shí)間序列數(shù)據(jù)庫，InfluxDB。
Raft 從 Paxos 來的主要不同的設(shè)計(jì)決策是要首先關(guān)注于交易日志，而不是一 個(gè)單獨(dú)的值，特別是要讓一個(gè)領(lǐng)導(dǎo)者堅(jiān)持提交交易直到他傳下去，也就是領(lǐng)導(dǎo)選 舉開始生效的時(shí)候。在某種程度上，這和區(qū)塊鏈采取的方式很相似，雖熱區(qū)塊鏈 的最主要優(yōu)勢(shì)在于它容忍不同錯(cuò)誤的能力。

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

由于區(qū)塊鏈通過在一個(gè)共享的數(shù)據(jù)庫上分發(fā)責(zé)任來降低交易對(duì)手風(fēng)險(xiǎn)的方式，它們已經(jīng)被認(rèn)為是“可信任的機(jī)器(trust machines)”。特別是比特幣，已經(jīng)被 注意到它承受其他參與者攻擊和惡性行為的能力。習(xí)慣上，一致性協(xié)議對(duì)惡性行 為的容忍被作為拜占庭容錯(cuò)(BFT)一致性協(xié)議。使用拜占庭一詞是因?yàn)榕c拜占庭將軍們面對(duì)的問題很相似，當(dāng)將軍之中有一個(gè)可能是叛徒的時(shí)候，他們嘗試只用信使來協(xié)作攻打羅馬。
在一個(gè)宕機(jī)故障中，一個(gè)進(jìn)程很簡單地終止掉。在拜占庭故障中，它可能反 復(fù)出現(xiàn)。宕機(jī)故障比較容易處理，因?yàn)闆]有進(jìn)程會(huì)對(duì)其它進(jìn)程撒謊。只容忍宕機(jī)故障的系統(tǒng)可以通過簡單的多數(shù)原則來處理，因此通常容忍高至半個(gè)系統(tǒng)的同步 失敗。如果系統(tǒng)能容忍錯(cuò)誤的數(shù)量是 f，這樣的系統(tǒng)必須至少有 2f + 1 個(gè)進(jìn)程。
拜占庭故障更復(fù)雜一些，在一個(gè)有 2f + 1 個(gè)進(jìn)程的系統(tǒng)里，如果有 f 個(gè)進(jìn)程是 拜占庭，它們可以協(xié)作對(duì)其他 f + 1 個(gè)進(jìn)程說任意的事情。舉個(gè)例子，假設(shè)我們 要試著在一個(gè)單獨(dú)的比特的值上面達(dá)成一致，f = 1，所以我們一共有 N = 3 個(gè)進(jìn) 程，A，B，C，其中 C 是拜占庭，如圖 2.2 所示。C 可以告訴 A 值為 0，告訴 B 是 1。如果 A 同意是，B 同意是 1 的話，它們就都會(huì)認(rèn)為自己得到多數(shù)答案，并 且提交它們，至此，就違背了安全條件。因此，拜占庭系統(tǒng)的容錯(cuò)邊界要嚴(yán)格 地比非拜占庭系統(tǒng)低。
實(shí)際上，可以看得出來拜占庭故障 f 的上限應(yīng)該是非 f < N/3。因此，容忍一 個(gè)單獨(dú)的拜占庭進(jìn)程，我們需要至少 N = 4 個(gè)進(jìn)程。這樣，故障進(jìn)程就不會(huì)把它 的票以不同的答案分給所有其他進(jìn)程，如圖 N = 3 那樣。
在 1999 年，Castro 和 Liskov 發(fā)表了 Practical Byzantine Fault Tolerance，也稱作 PBFT，它提出了第一個(gè)實(shí)際使用中的拜占庭容錯(cuò)優(yōu)化算法。它為工業(yè)上處理以每秒上萬條為度量的交易量的系統(tǒng)的拜占庭容錯(cuò)在實(shí)際應(yīng)用上開創(chuàng)了先例。放下這些成就不說，拜占庭容錯(cuò)仍然被認(rèn)為是昂貴的并且很大程度上是不必要的，而且最受歡迎的實(shí)現(xiàn)方法是很難建立在頂層上的。因此，盡管在學(xué)術(shù)興趣上有所復(fù)興，包括大量改進(jìn)過的變種，在實(shí)現(xiàn)和部署上，并沒有很大的進(jìn)展。此外，PBFT 不會(huì)提供任何保證是否有三分之一或更多的網(wǎng)絡(luò)協(xié)調(diào)者違反了安全性原則。

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

根本上，容錯(cuò)是一個(gè)源自信任(trust)缺失的問題—一個(gè)掌握其他進(jìn)程如何
表現(xiàn)的能力。正式地，信任可以由信息理論定義為一種降低某個(gè)人的世界模型的 熵的方法—信任某人就是樂觀地降低這個(gè)人對(duì)這個(gè)世界的不確定性，使其把更多 的注意力放在更高的組織形式的秩序上。
加密原語(Cryptographic primitives)同樣也是在根本上與信任問題相關(guān)聯(lián)，而且也可以類似地被定義為一種允許大幅降低熵的機(jī)制—成功驗(yàn)證一個(gè)加密的函數(shù)會(huì)把一個(gè)分布式可能產(chǎn)生的結(jié)果瓦解成單個(gè)，在某些情況也可能會(huì)變成一小部分?jǐn)?shù)量的結(jié)果。
眾所周知，一個(gè)有著更高形式制度信任的文明，比如法律制度，有更高的生產(chǎn)力和更有生氣的經(jīng)濟(jì)。這個(gè)結(jié)果給出直觀的感覺就是可以更容易的協(xié)調(diào)，比如更多地信任一個(gè)互動(dòng)可以降低需要被積極建模的可能輸出結(jié)果的空間。遺憾的是，評(píng)估現(xiàn)代機(jī)構(gòu)的可信度變得越來越難，因?yàn)樵谧罱鼛资陙硭鼈兊膹?fù)雜度飛速增長，也增加了它們所提供的確定性是一種假象的可能性。
幸運(yùn)的是，密碼學(xué)可以形成新的社會(huì)信任機(jī)構(gòu)的基礎(chǔ)，這可能會(huì)因?yàn)槠墼p和/或不負(fù)責(zé)任的活動(dòng)的風(fēng)險(xiǎn)降低，而在全球范圍內(nèi)大大提高人力協(xié)調(diào)能力。特別感興趣的是加密原語在 BFT 算法中的重要性，既用于認(rèn)證也用于播種非確定性。
最有趣的是，經(jīng)濟(jì)機(jī)制也可以作為減少熵的手段，只要經(jīng)濟(jì)主體能被激勵(lì) - 這就是說更有可能執(zhí)行某種特定的行為。事實(shí)上，比特幣的深刻見解是，加密原 語可以與經(jīng)濟(jì)激勵(lì)一起使用，以便能夠有效地減少公共一致性網(wǎng)絡(luò)的熵來實(shí)現(xiàn)狀 態(tài)的安全復(fù)制。
一個(gè)對(duì)信息理論的信任，密碼學(xué)，一致性，經(jīng)濟(jì)，尤其是它們的內(nèi)部關(guān)系的更正式探索，仍然是未來需要做的工作。

2.6 區(qū)塊鏈

一個(gè)區(qū)塊鏈的核心是一個(gè)以拜占庭容錯(cuò)原子廣播為基礎(chǔ)的專注完整性的方法。比如比特幣區(qū)塊鏈，使用經(jīng)濟(jì)學(xué)和加密隨機(jī)化的組合來提供強(qiáng)烈的概率保證不會(huì)違反安全性，給出一個(gè)弱同步假設(shè)，區(qū)塊據(jù)說比通過部分哈希碰撞彩票找到的數(shù)據(jù)塊快得多。然而，實(shí)際上，眾所周知，比特幣的安全保障容易受到一些微妙的攻擊。
區(qū)塊鏈?zhǔn)菑钠湓诮鉀Q ABC 中使用的兩個(gè)關(guān)鍵優(yōu)化獲得的名稱。第一個(gè)是它把交易分成區(qū)塊(blocks)以便在許多交易中分?jǐn)傃舆t(大約十分鐘)。第二個(gè)是將區(qū)塊通過加密哈希鏈接到一個(gè)不可變的鏈，這樣可以很容易驗(yàn)證歷史記錄。這兩個(gè)優(yōu)化都是對(duì)原始 BFT-ABC 的天然改進(jìn)，前者改進(jìn)了性能，后者改善了某些難以建模的拜占庭故障的容忍度。
在過去幾年中，“區(qū)塊鏈化”一致性算法已經(jīng)變得很普遍，也就是使用哈希鏈接交易批次的區(qū)塊鏈模型來適應(yīng) ABC。 據(jù)作者所知，Tendermint 是第一個(gè)這樣的提案，從 80 年代后期升級(jí)了一個(gè)眾所周知的 BFT 算法，盡管它已經(jīng)演變成了一個(gè)自己的一致性算法。隨后，IBM 將 PBFT 升級(jí)成為一個(gè)區(qū)塊鏈，然后摩根大通升級(jí)了一個(gè) Raft 的 BFT 版本。

2.7 進(jìn)程演算

那些部分系統(tǒng)要同時(shí)和其他系統(tǒng)一起執(zhí)行的分布式系統(tǒng)一直因?yàn)樗鼈冸y于設(shè)計(jì)，構(gòu)建，調(diào)試而被人詬病。因?yàn)榇蟛糠中枰徽秸J(rèn)證的技術(shù)和計(jì)算機(jī)科學(xué)的基礎(chǔ)已經(jīng)由順序計(jì)算特定開發(fā)，所以它們很難被正式認(rèn)證。
進(jìn)程演算是被引入提供并發(fā)式計(jì)算正式基礎(chǔ)的一系列模型。最流行的演算，通信順序進(jìn)程 Communicating Sequential Processes (CSP) 為許多現(xiàn)代編程語言提供了理論基礎(chǔ)，比如 Go，在設(shè)計(jì)語言時(shí)就包含了并發(fā)原語。
在 80 年代，Robin Milner 推出了通信系統(tǒng)演算 Calculus of Communicating Systems (CCS)，被設(shè)計(jì)為順序 lambda 演算的并發(fā)類似物，成為大部分函數(shù)式編 程語言的基礎(chǔ)。雖然 lambda 演算有功能應(yīng)用程序作為其基本計(jì)算單位，但 CCS 使用共享通道上的兩個(gè)并發(fā)進(jìn)程之間的通信作為其基本操作原語。CCS 的更一般形式是 pi 演算，使得進(jìn)程之間的通信圖中的移動(dòng)性能夠使得通信信道本身可以 沿其它信道傳遞，從而模糊數(shù)據(jù)，變量和信道之間的區(qū)別。這個(gè)結(jié)果是一個(gè)比前任更強(qiáng)大的連貫簡約的計(jì)算模型。
Pi 演算已被證明是研究并發(fā)系統(tǒng)的高效工具，其應(yīng)用從業(yè)務(wù)流程管理到細(xì)胞 生物學(xué)。非常簡單的注解簡化了并發(fā)協(xié)議的描述。此外，眾所周知的計(jì)算和邏輯 之間的等價(jià)性使得可以將邏輯系統(tǒng)定義為與各種進(jìn)程演算的補(bǔ)充，提供正式的方 式來討論和驗(yàn)證在適當(dāng)?shù)难菟阒兄付ǖ南到y(tǒng)的屬性。
我們對(duì) pi 演算的描述只能指定 Tendermint 算法。 一個(gè)簡單的 pi 演算以 Backus-Naur 形式的語法如下表示:

每個(gè)語法規(guī)則都以其功能意義的參考為標(biāo)記。一個(gè)進(jìn)程可能是空的進(jìn)程，0。 它可能是兩個(gè)進(jìn)程的并行組合，P | P 表示同時(shí)運(yùn)行的兩個(gè)進(jìn)程。一個(gè)被保護(hù)的 進(jìn)程，α.P，只允許進(jìn)程 P 在動(dòng)作α發(fā)生后執(zhí)行。這個(gè)動(dòng)作可以是空動(dòng)作，τ， 或者是 y 沿 x 的發(fā)送，x!(y)，或接收，x?(y)。保護(hù)的選擇將非確定性注入到演算 的運(yùn)算中，使得進(jìn)程α.P + β.Q 將不確定地執(zhí)行α或β，然后分別運(yùn)行 P 或 Q。
可以通過(vx)P 創(chuàng)建一個(gè)新的通道 x，這樣 x 只能在 P 中訪問。函數(shù)形式 Fs(y)允許我們將變量 s 和 y 傳遞到一個(gè)可能導(dǎo)致自身執(zhí)行遞歸的 F 進(jìn)程中。通常，我們讓 s 是像狀態(tài)一樣的變量，而 y 是演算中的通道。最后，由于我們感興趣的是異步網(wǎng)絡(luò)的一致性，我們采用被認(rèn)為是不可靠的故障檢測(cè)器的超時(shí)的抽象，并將其建模為非確定性動(dòng)作。當(dāng)進(jìn)程 i 被懷疑失敗(即在一些超時(shí)后)，suspi 動(dòng)作就被觸發(fā)了。
注意一點(diǎn)，我們可以使用ΣP 表示超過兩個(gè)進(jìn)程的守衛(wèi)選擇，ΠP 表示兩個(gè)以 上進(jìn)程的并行組合。我們也承認(rèn)發(fā)送和接收的多種形式，比如，x?(v, w) | x!(y,z) 等同于 x?(d).d?(v).d?(w) | (vc)x!?.c!(y).c!(z)。
操作語義定義了進(jìn)程可能執(zhí)行的實(shí)際不可逆的計(jì)算步驟。有效的是，唯一相 關(guān)的操作是通信，稱為 comm 規(guī)則:
(x?(y).P | x!(z)) → P{z/y} (2.1)
符號(hào) P{z/y}表示 P 中所有出現(xiàn)的 y 都被替換為 z。換句話說，z 被發(fā)送到 x 上，以 y 的形式接收，并被饋送到 P。
給定一個(gè) pi 演算過程，我們可以通過應(yīng)用 comm 規(guī)則來執(zhí)行它。舉個(gè)例子，
(x?(y).y!(x) | x!(z)) → z!(x) (2.2)
現(xiàn)在，我們可以使用一個(gè)形式的邏輯來表達(dá)進(jìn)程可能滿足的屬性。例如，模 態(tài)的 Hennessy - Milner 邏輯可以表示一個(gè)過程將在一些或所有形式的行動(dòng)發(fā)生之 后滿足一些其他邏輯表達(dá)。通過將更復(fù)雜的運(yùn)算符添加到邏輯中，可以構(gòu)建形式 化的系統(tǒng)，其可以容易地描述分布式系統(tǒng)的重要屬性，例如安全性、活性和本地
化。用 pi 演算寫的系統(tǒng)之后可以被正式驗(yàn)證來用模型檢查軟件滿足相關(guān)屬性。 雖然我們使用 pi 演算來指定 Tendermint 算法，但是我們?nèi)詫⑹褂孟嚓P(guān)的形式邏輯，以及相應(yīng)的屬性驗(yàn)證，以供將來使用。

2.8 Tendermint 的需求

比特幣及其衍生物尤其是以太坊的成功，還有它們對(duì)任意代碼的安全、自主、分布式、容錯(cuò)執(zhí)行的承諾，使得這個(gè)星球上幾乎所有的主要金融機(jī)構(gòu)都對(duì)區(qū)塊鏈 現(xiàn)象產(chǎn)生了興趣。特別是對(duì)兩種形式的技術(shù)有了一種了解:一方面是公共區(qū)塊鏈， 被親切地稱為大壞的公共區(qū)塊鏈或 BBPBs，后者的協(xié)議以原生貨幣為基礎(chǔ)的經(jīng)濟(jì) 激勵(lì)為主。另一方面是所謂的私有區(qū)塊鏈，或者可能應(yīng)該更準(zhǔn)確地被稱為“財(cái)團(tuán) 區(qū)塊鏈”，通過使用哈希樹，數(shù)字簽名，P2P 網(wǎng)絡(luò)和增強(qiáng)功能有效地改進(jìn)了傳統(tǒng) 的一致性算法和 BFT 算法。
隨著我們社會(huì)的基礎(chǔ)設(shè)施越來越分散，隨著業(yè)務(wù)的性質(zhì)變得更加組織化，越 來越需要一個(gè)透明，負(fù)責(zé)任，高性能的 BFT 系統(tǒng)，可以支持從融資到域名注冊(cè)到 電子投票的應(yīng)用，并配備先進(jìn)的治理機(jī)制和未來的演變機(jī)制。Tendermint 是針 對(duì)財(cái)團(tuán)或組織間邏輯進(jìn)行優(yōu)化的解決方案，但足夠靈活，可以容納任何從私營企 業(yè)到全球貨幣的解決方案，以及足以與當(dāng)今主要的非 BFT 一致性算法解決方案例 如 etcd，consul 以及 zookeeper 進(jìn)行競(jìng)爭的高性能，同時(shí)為應(yīng)用程序開發(fā)人員提 供更大的彈性，安全保證和靈活性。

Chapter 3

Tendermint 一致性算法（共識(shí)算法）
這章講解了 Tendermint 一致性算法和一個(gè)相關(guān)的原子廣播區(qū)塊鏈。詳細(xì)描述了 BFT 一致性問題，在 pi 演算中給出了 Tendermint 一致性算法的正式規(guī)范。 Tendermint 區(qū)塊鏈被非正式地證明可以滿足原子廣播。我們將其留在將來的工作中，以便在進(jìn)程演算中捕獲完整的區(qū)塊鏈協(xié)議并驗(yàn)證其屬性。

3.1 Tendermint 總覽

Tendermint 是區(qū)塊鏈模型中的安全狀態(tài)機(jī)復(fù)制算法。它提供了一種 BFT-ABC的形式，使得更加負(fù)責(zé)任—如果安全性被違反，總是可以驗(yàn)證出是誰的惡意行為。 Tendermint 從一組驗(yàn)證者開始，通過其公鑰識(shí)別，每個(gè)驗(yàn)證者負(fù)責(zé)維護(hù)復(fù)制 狀態(tài)的完整副本，并提出新的區(qū)塊(交易批次)，并對(duì)其進(jìn)行表決。每個(gè)區(qū)塊被分配一個(gè)增量索引或高度，使得有效的區(qū)塊鏈在每個(gè)高度只有一個(gè)有效的區(qū)塊。 在每個(gè)高度，驗(yàn)證者輪流提出新的區(qū)塊，這樣在任何輪的時(shí)候最多只有一個(gè)有效的提議者。由于網(wǎng)絡(luò)的不同步，可能會(huì)花費(fèi)多輪來提交給定高度的區(qū)塊，如果三分之一或更多的驗(yàn)證者離線或分區(qū)，則網(wǎng)絡(luò)可能完全停止。驗(yàn)證者在區(qū)塊提交之 前進(jìn)行兩個(gè)階段的投票，并遵循一個(gè)簡單的鎖機(jī)制，防止不到三分之一的驗(yàn)證者 的任何共同惡意損害安全性的行為。
要注意的是，輪流投票機(jī)制的核心是一致性算法，它是捆綁一起組成區(qū)塊來 產(chǎn)生原子廣播。每個(gè)塊都包含一些元數(shù)據(jù)，稱為它的頭，其中包含前一個(gè)高度的 區(qū)塊的散列，產(chǎn)生一個(gè)哈希鏈。頭里還包括區(qū)塊高度，區(qū)塊被提出的當(dāng)?shù)貢r(shí)間， 以及包含在區(qū)塊中的交易的 Merkle 跟散列。
3.2 一致性算法
一致性算法可以大致分為以下幾種幾何正交組件: ·提議(proposals):每個(gè)輪次必須由正確的提議者提出一個(gè)新的區(qū)塊，并
向另一個(gè)驗(yàn)證者進(jìn)行傳播。 如果沒有在足夠的時(shí)間內(nèi)收到提案，則應(yīng)跳過該提 案者。
·投票(votes):必須進(jìn)行兩個(gè)階段的投票，以確保拜占庭的最佳容錯(cuò)能力。 他們被稱為預(yù)投票(pre-vote)和預(yù)提交(pre-commit)。 在同一輪中，來自同 一區(qū)塊的三分之二以上驗(yàn)證者的一組預(yù)提交是一次提交。
·鎖(locks):Tendermint 確保沒有兩個(gè)驗(yàn)證者在相同的高度處提交不同的 區(qū)塊，假設(shè)不到三分之一的驗(yàn)證者是惡意的。這是通過一種鎖機(jī)制實(shí)現(xiàn)的，該機(jī) 制決定驗(yàn)證者如何根據(jù)在同一高度上先前的預(yù)投票和預(yù)提交來預(yù)投票和預(yù)提交。 要注意的是，這種鎖機(jī)制必須仔細(xì)設(shè)計(jì)使其不損害活性。
為了給單獨(dú)的拜占庭故障提供容忍，一個(gè) Tendermint 網(wǎng)絡(luò)必須包含最少四個(gè) 驗(yàn)證者。每個(gè)驗(yàn)證者必須具有用于產(chǎn)生數(shù)字簽名的非對(duì)稱加密密鑰對(duì)。驗(yàn)證者從 共同的初始狀態(tài)開始，其中包含驗(yàn)證器的有序列表 L。每個(gè)驗(yàn)證者都通過其公鑰 進(jìn)行識(shí)別，所有提案和投票必須由相應(yīng)的私鑰簽名。這可以確保任何觀察者總是 能夠?qū)μ岚负屯镀边M(jìn)行驗(yàn)證。假設(shè)多達(dá)三分之一的驗(yàn)證者是惡意的，以任意方式 合作顛覆系統(tǒng)安全或活性的，是非常有幫助的。
一致性算法始于第零輪，第一個(gè)提議者就是 L 中第一個(gè)驗(yàn)證者。一輪的結(jié)果 是做出提交，或決定轉(zhuǎn)入下一輪。新一輪是下一個(gè)提議者。使用多輪可以給驗(yàn)證 者多次機(jī)會(huì)在網(wǎng)絡(luò)異步或驗(yàn)證失敗的情況中達(dá)成一致。與需要一種領(lǐng)導(dǎo)選舉形式 的算法相反，Tendermint 在每一輪都有一個(gè)新的領(lǐng)導(dǎo)者(提議者)。驗(yàn)證者與投 票接受該提議相同的方式跳到下一輪，提供給協(xié)議一個(gè)統(tǒng)一的，在明確的領(lǐng)導(dǎo)選 舉程序算法中缺席的機(jī)制。
每一輪的開始對(duì)同步性的依賴性很弱，因?yàn)樗帽镜貢r(shí)鐘來決定何時(shí)跳過 提議者。 也就是說，如果驗(yàn)證者沒有在本地估量的進(jìn)入新一輪的“超時(shí)提議 (ProposalTimeout)”中收到提議，則可以投票以跳過提議者。在這種機(jī)制中固 有的是一個(gè)弱同步的假設(shè)，即該提議最終將在“超時(shí)提議(ProposalTimeout)” 中傳達(dá)，該延遲本身可能會(huì)隨著每一輪的進(jìn)行而增加。這個(gè)假設(shè)將在第十章中有 更全面的討論。
在提案之后，回合以完全異步的方式進(jìn)行 - 驗(yàn)證者只有在至少三分之二的驗(yàn) 證者聽取之后才能繼續(xù)進(jìn)行。這減輕了對(duì)同步時(shí)鐘或有界網(wǎng)絡(luò)延遲的任何種類的 依賴，但是這意味著如果有三分之一或更多的驗(yàn)證者無響應(yīng)，網(wǎng)絡(luò)就將停止。異 步投票緊接著這個(gè)弱同步提議的流程，如圖 3.1 所示。
為了安全地跳過回合，引入了一些鎖的規(guī)則，迫使驗(yàn)證者證明他們的投票是 合理的。 雖然我們并不一定要求他們實(shí)時(shí)廣播其理由，但我們希望他們保留數(shù) 據(jù)，以便在安全受到足夠的拜占庭故障的影響的情況下將其作為證據(jù)。這種問責(zé) 機(jī)制使得 Tendermint 能夠在面臨這種失敗的情況下提供比例如，如果第三個(gè)或 更多的驗(yàn)證者是拜占庭的話就不會(huì)提供保證的 PBFT，更有力的保證。
驗(yàn)證者使用不同的消息集進(jìn)行通信，以管理區(qū)塊鏈，應(yīng)用狀態(tài)，對(duì)等網(wǎng)絡(luò)和 一致性。 然而，一致性算法的核心只包含兩條消息:
·提議消息(ProposalMsg):由提議者簽字的給定高度和回合的區(qū)塊的提議。 ·投票消息(VoteMsg):一個(gè)簽過字的提議的投票。 實(shí)際上，我們使用額外的消息來優(yōu)化區(qū)塊數(shù)據(jù)和投票的傳播，這會(huì)在第四章
進(jìn)行討論。

3.2.1 提議(Proposals)

每一輪都以提案開始。給定輪次的提議者從本地緩存中(Mempool，參見第四章)拿到一批最近收到的交易，組成一個(gè)區(qū)塊，并廣播包含該塊的簽名的 ProposalMsg。 如果提議者是拜占庭，則可能會(huì)向不同的驗(yàn)證者廣播不同的提議。
提議者通過一個(gè)簡單的，確定性的輪次排序，所以只有一個(gè)提議者對(duì)于給定 的回合是有效的，每個(gè)驗(yàn)證者都知道誰是正確的提議者。如果收到低輪次的提議 或錯(cuò)誤的提議者的提議，它將被拒絕。
對(duì)于拜占庭容忍來說，循環(huán)提出建議是必要的。比如在 Raft 中，如果當(dāng)選的 領(lǐng)導(dǎo)者是拜占庭，并且與其他節(jié)點(diǎn)保持強(qiáng)大的網(wǎng)絡(luò)連接，則它可以完全破壞系統(tǒng)， 破壞所有的安全性和活性的保證。Tendermint 通過投票和鎖機(jī)制保證安全性，并 通過循環(huán)提議保證活性，所以如果一個(gè)提議者不處理任何交易，其他的也可以繼續(xù)。也許更有趣的是，驗(yàn)證者可以通過治理模塊(參見第 6 章)投票去除或替換 拜占庭驗(yàn)證者。

3.2.2 投票(votes)

一旦驗(yàn)證者收到一份完整的提議，它就會(huì)為該提議進(jìn)行預(yù)投票并將其廣播到網(wǎng)絡(luò)。 如果驗(yàn)證者在 ProposalTimeout 中沒有收到正確的提案，則會(huì)投 nil 票。 在與拜占庭驗(yàn)證者的異步環(huán)境中，單個(gè)投票階段每個(gè)驗(yàn)證者只投一票，是不足以 確保安全性的。實(shí)質(zhì)上，由于驗(yàn)證者可以說謊，而且對(duì)消息傳送時(shí)間沒有保障， 一個(gè)流氓驗(yàn)證者可以協(xié)同一些別的驗(yàn)證者提交一個(gè)值，而其他驗(yàn)證者并沒有看到 這次提交就進(jìn)入下一回合，在這個(gè)回合它們會(huì)提交不同的值。
單一的投票階段允許驗(yàn)證者告訴對(duì)方他們對(duì)提案的了解。但是，為了容忍拜 占庭故障(其實(shí)質(zhì)上是謊言，欺詐，欺騙等)，他們還必須告訴對(duì)方他們知道哪 些其他驗(yàn)證者已經(jīng)宣稱對(duì)提議的了解。也就是說，第二階段確保足夠的驗(yàn)證者見 證了第一階段的結(jié)果。(*這個(gè)就是為什么需要三步提交的原因。per-vote 階段: 請(qǐng)求投票，并收集起他人的投票。commit 階段，每個(gè)人收集到其他三分之二的 人的投票，就認(rèn)為自己已經(jīng)見證了這次投票，發(fā)送 pre-commit 消息，然后，收 集到足夠的 per-commit 的消息，就認(rèn)為 commit 成功了。也就是一次是發(fā)起投票， 一次是足夠的人見證了這次投票。)
因此，區(qū)塊的預(yù)投票也是網(wǎng)絡(luò)準(zhǔn)備提交區(qū)塊的投票。為 nil 的預(yù)投票是網(wǎng)絡(luò)準(zhǔn) 備進(jìn)入下一輪的投票。在一個(gè)在線提議者的理想回合中，超過三分之二的驗(yàn)證者 將會(huì)為提議預(yù)投票。在給定回合的單獨(dú)區(qū)塊的一組超過三分之二的預(yù)投票被稱作 polka。單獨(dú)區(qū)塊的一組超過三分之二的為 nil 的預(yù)投票被稱作了 nil-polka。
當(dāng)一個(gè)驗(yàn)證者接收到一個(gè) polka(也就是一個(gè)單獨(dú)區(qū)塊的超過三分之二的預(yù)投 票)時(shí)，它已經(jīng)收到一個(gè)網(wǎng)絡(luò)已經(jīng)準(zhǔn)備好提交區(qū)塊的信號(hào)，它作為驗(yàn)證者對(duì)該區(qū) 塊進(jìn)行簽名和廣播預(yù)提交投票的理由。有時(shí)，由于網(wǎng)絡(luò)異步，驗(yàn)證者可能不會(huì)接 收到 polka，或者可能就沒有。在這種情況下，驗(yàn)證者在為該區(qū)塊簽字預(yù)提交是 不合理的，因此必須為 nil 簽署并發(fā)布預(yù)提交的投票。也就是說，在沒有 polka 的理由的情況下簽署預(yù)提交是一種惡意行為。
一次預(yù)提交實(shí)際上是提交一個(gè)區(qū)塊的投票。一次對(duì) nil 的預(yù)提交實(shí)際上是進(jìn)入 到下一輪的投票。如果一個(gè)驗(yàn)證者接收到一個(gè)區(qū)塊的超過三分之二的預(yù)提交，它 將提交該塊，計(jì)算結(jié)果狀態(tài)，并在下一個(gè)高度移動(dòng)到回合 0。如果驗(yàn)證者收到超 過三分之二的 nil 預(yù)提交，則轉(zhuǎn)到下一輪。

3.2.3 鎖(locks)

確保輪次的安全性可能是棘手的，因?yàn)楸仨毐苊鈱橥桓叨鹊膬蓚€(gè)不同輪次的兩個(gè)不同的區(qū)塊提供合理性這種情況。在 Tendermint 中，這個(gè)問題是通過 圍繞 polka(即相同的區(qū)塊的三分之二以上的預(yù)投票)的鎖機(jī)制來解決的。實(shí)質(zhì) 上，一次預(yù)提交必須由 polka 證明，而且一個(gè)驗(yàn)證者會(huì)被認(rèn)為在上一個(gè)它提交的 區(qū)塊上鎖住。鎖有兩條規(guī)則:
·Prevote-the-Lock:驗(yàn)證者必須對(duì)他們被鎖定的塊進(jìn)行預(yù)投票，如果它們是 提議者，則提出它。這防止驗(yàn)證者在一輪中預(yù)先提交一個(gè)區(qū)塊，然后在下一輪中 為一個(gè)不同的區(qū)塊提供 polka，從而危及安全性。
·Unlock-on-Polka:一個(gè)驗(yàn)證者只可以在一輪看到的 polka 比它鎖定的那輪的 polka 大之后才可以釋放鎖。如果驗(yàn)證者預(yù)提交那些網(wǎng)絡(luò)其余部分不想提交的東西，這允許它們釋放鎖，從而保護(hù)活性，但是不損害安全性。如果有一個(gè)在驗(yàn)證 者鎖定那輪之后的一輪的 polka，只允許解鎖。
為了簡單起見，驗(yàn)證者被認(rèn)為在每個(gè)高度的回合-1 處都被鎖定在 nil，所以 Unlock-on-Polka 意味著驗(yàn)證者直到看到 polka 才能在新的高度預(yù)提交。
通過實(shí)例可以更直觀地理解這些規(guī)則。考慮四個(gè)驗(yàn)證者 A，B，C，D，并且假 設(shè)在第 R 輪有一個(gè)對(duì)區(qū)塊 X 的提議。假設(shè)有一個(gè)區(qū)塊 X 的 polka，但是 A 沒有看 到它，并且預(yù)提交為 nil，而其他的則預(yù)提交區(qū)塊 X?，F(xiàn)在假設(shè)唯一一個(gè)看到所有 預(yù)提交的是 D，而其它則說沒有看到 D 的預(yù)提交(它們只看到它們的兩個(gè)預(yù)提交， 和 A 的 nil 預(yù)提交)。D 現(xiàn)在將提交區(qū)塊，而其它的則進(jìn)入 R + 1 回合。因?yàn)槿魏?驗(yàn)證者都可能是新的提議者，如果他們可以提出并投票支持任何新的區(qū)塊，比如 區(qū)塊 Y，那么他們可能提交它并連累安全性，因?yàn)?D 已經(jīng)提交了區(qū)塊 X。請(qǐng)注意，這里甚至沒有拜占庭行為，只是因?yàn)楫惒叫?
鎖機(jī)制通過強(qiáng)制驗(yàn)證者堅(jiān)持使用它們預(yù)提交的區(qū)塊來解決問題，因?yàn)槠渌?yàn) 證者可能已經(jīng)基于它們所預(yù)提交的提交了(如本例中 D 所示)。實(shí)質(zhì)上，在一個(gè)回合中一旦超過三分之二預(yù)提交一個(gè)區(qū)塊，網(wǎng)絡(luò)就被鎖定在該區(qū)塊上，也就是說，在更高的輪次上一定不可能為一個(gè)不同的區(qū)塊生成一個(gè)有效的 polka。這是 Prevote-lock 的直接動(dòng)機(jī)。
然而，Prevote-the-Lock 是不夠的。必須要有一種方式來解鎖，以免我們犧牲 活性。考慮這樣的一個(gè)回合，其中A和B預(yù)提交區(qū)塊X，而C和D預(yù)提交nil- 分立投票。他們都轉(zhuǎn)到下一輪，并且提出了 C 和 D 所預(yù)投票的區(qū)塊 Y。假設(shè) A 是拜 占庭，并且為 Y 塊預(yù)投票(盡管被鎖在區(qū)塊 X 上)，從而得到一個(gè) polka。假設(shè) 當(dāng) A 離線，C 和 D 預(yù)提交區(qū)塊 Y 時(shí)，B 沒有看到 polka 并且預(yù)提交 nil。他們移動(dòng) 到下一輪，但 B 仍然鎖定在區(qū)塊 X 上，而 C 和 D 現(xiàn)在被鎖定在區(qū)塊 Y 上，并且 由于 A 離線，它們永遠(yuǎn)不會(huì)得到 polka。因此，我們以不到三分之一的拜占庭驗(yàn) 證者(這里只有一個(gè))連累了活性。
解鎖的明顯理由是 polka。一旦 B 看到區(qū)塊 Y 的 polka(C 和 D 之前為區(qū)塊 Y 驗(yàn)證的它們的預(yù)提交)，它就應(yīng)該可以解鎖，因此提交區(qū)塊 Y。這是 Unlock-on-Polka 的動(dòng)機(jī)，如果他們?cè)谝惠喼锌吹揭粋€(gè)比他們鎖定的那輪更大的 polka，它則允許 驗(yàn)證者解鎖(并預(yù)提交一個(gè)新的區(qū)塊)。

3.2.4 正式規(guī)范

既然我們已經(jīng)詳細(xì)解釋了這個(gè)協(xié)議，我們現(xiàn)在提出 pi 演算的正式規(guī)范。 使得 ∏ 表示一組 N 個(gè)驗(yàn)證者的一致性協(xié)議，每個(gè)都互相
執(zhí)行互不相容的一組進(jìn)程中的一個(gè)，Yi。內(nèi)部狀態(tài) S = {r, p, v}由一個(gè)嚴(yán)格增加的 回合，r，一個(gè)提議，p，組成，包含這輪提議的區(qū)塊;和一組包含所有輪的所有 的投票組成。我們?cè)诘?r 輪分別用 和 表示一組預(yù)投票和預(yù)提交，我們讓 vote :: v 表示集合{vote}和 v(即，添加到 v 的 vote)的并集。我們定義 proposer? = r mod N 作為第 r 輪提議者的索引。 我們?cè)趨f(xié)議的特定點(diǎn)表示一個(gè)對(duì)等體為 。在PRi，PVi，PCi 范圍內(nèi)的進(jìn)程 Yi，分別表示提議(proposal)，預(yù)投票(prevote)， 預(yù)提交(precommit)的縮寫。我們引入 PV 和 PC 的附加子功能來捕獲 PV1，PV2 等的遞歸。
對(duì)等體使用廣播信道連接每個(gè)消息類型，即，proposei，prevotei 和 precommiti， 以及用于決定或提交值 di 的渠道。通過大量用這些符號(hào)，可以通過 xxxi 上的每個(gè) 進(jìn)程接收廣播頻道 xxxi 上的單個(gè)發(fā)送。
我們只使用兩種信息類型:提議和投票。每個(gè)都包含一個(gè)回合號(hào)，區(qū)塊(哈 希)和簽名，表示為 msg.round，msg.block，msg.sig。注意，我們可以將簽名吸 收到廣播頻道本身，但是我們需要使用它作為拜占庭行為的證據(jù)。
該規(guī)范分為兩部分，即圖 3.2 和 3.3。

3.3 區(qū)塊鏈(Blockchain)

Tendermint 一次性操作交易的批次或區(qū)塊。通過將每個(gè)區(qū)塊通過其加密哈希明確地鏈接到它之前的一個(gè)區(qū)塊，從而將一個(gè)區(qū)塊維持到下一個(gè)區(qū)塊，從而形成區(qū)塊鏈。區(qū)塊鏈包含有序交易日志和驗(yàn)證者提交區(qū)塊的證據(jù)。

3.3.1 為什么用區(qū)塊?

一致性算法通常通過設(shè)計(jì)一次提交交易，并在其發(fā)生之后實(shí)現(xiàn)批處理。正如第二章中提到過的，從批量原子廣播的角度解決問題，主要得到兩個(gè)優(yōu)化方式，這給我們提供了更多的吞吐量和容錯(cuò)能力:
·帶寬優(yōu)化(bandwidth optimization):由于每次提交都需要所有驗(yàn)證者之 間進(jìn)行兩輪通信，所以區(qū)塊中的批次交易會(huì)分?jǐn)倕^(qū)塊中的所有交易的提交成本。
·整體性優(yōu)化(integrity optimization):區(qū)塊的哈希鏈形成一個(gè)不可變的數(shù) 據(jù)結(jié)構(gòu)，很像 Git 倉庫，可以在歷史記錄中的任何一個(gè)位置對(duì)子狀態(tài)進(jìn)行確定性檢查。
區(qū)塊也產(chǎn)生另一個(gè)效果，這是更微妙但可能更重要。它們將交易的最小延遲 增加到整個(gè)區(qū)塊的最小等待時(shí)間，對(duì)于 Tendermint 來說約為數(shù)百毫秒到幾秒。 而傳統(tǒng)的可序列化數(shù)據(jù)庫系統(tǒng)提供了大概幾毫秒到幾十毫秒的提交延遲。他們能 夠做到這一點(diǎn)，是因?yàn)樗鼈儾皇前菡纪ト蒎e(cuò)的，只需要一輪通信(而不是兩次)， 并且需要超過一半的副本(而不是三分之二)的響應(yīng)。然而，與其他算法中的領(lǐng) 導(dǎo)選舉中斷的快速提交時(shí)間不同，Tendermint 提供了一種更為規(guī)則的脈沖，可以 在節(jié)點(diǎn)故障和異步方面更好地響應(yīng)網(wǎng)絡(luò)的整體運(yùn)行狀況。
盡管有目的地引發(fā)的延遲在金融市場(chǎng)上顯示出希望，這類脈沖在互聯(lián)網(wǎng)通信自治系統(tǒng)的一致性中所起的作用還有待確定。

3.3.2 區(qū)塊結(jié)構(gòu)

區(qū)塊的目的是包含一批交易并鏈接上到之前的區(qū)塊。鏈接以這兩種形式呈現(xiàn):
前一個(gè)區(qū)塊的哈希，和導(dǎo)致前一個(gè)區(qū)塊提交的一組預(yù)提交，或者也可以稱之為 LastCommit。因此，塊由三個(gè)部分組成:區(qū)塊頭，交易列表和 LastCommit。

3.4 安全性(safety)

在這里，我們草擬了一個(gè)簡短的證明，即 Tendermint 滿足原子廣播，滿足:
·有效性(validity)-如果一個(gè)正確的進(jìn)程廣播 m，它最終會(huì)傳送 m ·一致性(agreement)-如果一個(gè)正確的進(jìn)程傳送 m，所有正確的進(jìn)程最終
都會(huì)傳送 m
·整體性(integrity)-m 只被傳送一次，而且只當(dāng)它被自己的發(fā)送者廣播的
時(shí)候
·總序性(total order)-如果正確的進(jìn)程 p 和 q 傳送 m 和 m’，則如果 q 在傳
送 m’之前傳送 m，p 就在傳送 m’之前傳送 m
請(qǐng)注意，如果我們將 m 作為一個(gè)塊，Tendermint 不能滿足有效性，因?yàn)椴荒鼙ＷC提議的區(qū)塊最終被提交，因?yàn)轵?yàn)證者可能移動(dòng)到新一輪并提交不同的區(qū)塊。 如果我們將 m 作為區(qū)塊中的一批交易，那么我們可以通過讓驗(yàn)證者不斷重新提 出相同的批次直到它被提交，來滿足有效性。然而，為了滿足前一半的完整性， 我們必須引入一個(gè)額外的規(guī)則，禁止一個(gè)正確的驗(yàn)證者提出一個(gè)區(qū)，或者提交一 個(gè)包含一批已經(jīng)提交過的交易的區(qū)塊。幸運(yùn)的是，批次可以由它們的根目錄來索 引，并且在提案和預(yù)提交之前進(jìn)行查找。
或者，如果我們將消息 m 作為一個(gè)交易，那么我們可以通過在 mempool 上 斷言一個(gè)持久性(persistence)屬性來滿足有效性，即一個(gè)交易在 mempool 中一 直存在，直到它被提交。然而，為了滿足前一半的完整性，我們必須依靠應(yīng)用狀 態(tài)來對(duì)交易執(zhí)行一系列規(guī)則，使得給定的交易只有效一次。舉個(gè)例子，這可以通 過在帳戶上使用序列號(hào)來完成，就像在以太坊中所做的一樣，或通過保留一個(gè)未 使用的資源的列表，每個(gè)資源只能使用一次，就像比特幣中使用的一樣。由于有 多種方法，Tendermint 本身不能確保一個(gè)消息只被傳遞一個(gè)消息一次，而是允許 應(yīng)用開發(fā)人員指定。請(qǐng)注意，完整性的后半部分是很好滿足的，因?yàn)橹挥姓_提 議者提出的區(qū)塊中的交易才能被提交。
為了表明 Tendermint 滿足其余的屬性，我們引入了一個(gè)新的屬性，狀態(tài)機(jī)安 全性，并表明滿足狀態(tài)機(jī)安全性的協(xié)議也滿足一致性和總序性。狀態(tài)機(jī)安全說明， 如果一個(gè)正確的驗(yàn)證者在某個(gè)高度 H 處提交一個(gè)區(qū)塊，則不會(huì)有其他的正確的 驗(yàn)證者將在 H 處提交不同的區(qū)塊。假設(shè)所有消息最終都會(huì)被接收到，這就馬上 可以證明一致性，因?yàn)槿绻粋€(gè)正確的驗(yàn)證者在包含交易 m 的高度 H 處提交區(qū) 塊 B，所有其他正確的驗(yàn)證者將不能提交任何其他區(qū)塊，因此最終必須提交 B， 從而傳送 m。
現(xiàn)在，需要做的就是證明狀態(tài)機(jī)安全性滿足總序性，Tendermint 滿足狀態(tài)機(jī) 安全性。先看前者，考慮由驗(yàn)證者 p 和 q 傳遞的兩個(gè)消息 m 和 m’。狀態(tài)機(jī)安全 性確保當(dāng)且僅當(dāng) q 在高度 Hm 傳送 m 時(shí)，p 在高度在高度 Hm 傳送 m。并且當(dāng)且 僅當(dāng) q 在高度 Hm’傳送 m’時(shí)，p 在高度在高度 Hm’傳送 m’。不失一般性，由于高度嚴(yán)格上升，所以 Hm < Hm’。這樣，我們就得到了當(dāng)且僅當(dāng) q 在 m’之前傳送 m 時(shí)，p 在 m’之前傳送 m，這也正好是總序性的聲明。
最后，為了證明當(dāng)少于三分之一的驗(yàn)證者是拜占庭的時(shí)候，Tendermint 滿足 狀態(tài)機(jī)安全性，我們以反證的方式進(jìn)行。假設(shè) Tendermint 不滿足狀態(tài)機(jī)安全性， 允許在同一高度提交多個(gè)區(qū)塊。那么我們表明，這種情況至少有三分之一的驗(yàn)證 者必須是拜占庭才能發(fā)生，與我們的假設(shè)相矛盾。
考慮一個(gè)正確的驗(yàn)證者已經(jīng)在高度 H 和回合 R 提交區(qū)塊 B。提交一個(gè)區(qū)塊意 味著驗(yàn)證者在回合 R 從超過三分之二的驗(yàn)證者的情況下見證了區(qū)塊 B 的預(yù)提交。 假設(shè)另一個(gè)區(qū)塊 C 在高度 H 處被提交。我們有兩個(gè)選擇:它在回合 R 被提交， 或在回合 S > R 被提交。
如果是在第 R 回合提交的，那么超過三分之二的驗(yàn)證者必須在第 R 回合中預(yù) 提交，這就意味著至少有三分之一的驗(yàn)證者在第 R 回合中即預(yù)提交了區(qū)塊 B 也預(yù) 提交了區(qū)塊 C，顯然這是拜占庭，假設(shè)區(qū)塊 C 在回合 S > R 中被提交。由于超過 三分之二的驗(yàn)證者預(yù)提交了 B，他們被鎖定在第 S 輪鎖定了 B，因此必須為 B 預(yù) 投票。為了預(yù)提交區(qū)塊 C，他們必須為 C 證明一個(gè) polka，這需要超過 三分之二 的驗(yàn)證者為 C 預(yù)投票。然而，由于超過三分之二驗(yàn)證者被鎖定在區(qū)塊 B 并需要對(duì) B 進(jìn)行預(yù)投票，C 的 polka 將要求至少三分之一的驗(yàn)證者違反 Prevote-the-Lock， 這很顯然是拜占庭。因此，為了違反狀態(tài)機(jī)安全性，至少要有三分之一的驗(yàn)證者 必須是拜占庭。因此，當(dāng)不到三分之一的驗(yàn)證者是拜占庭時(shí)，Tendermint 滿足狀態(tài)機(jī)安全性。
鑒于上述，Tendermint 滿足原子廣播。 在未來的工作中，我們的目標(biāo)是提供一個(gè)更正式的 Tendermint 安全性證明。

3.5 問責(zé)制(accountability)

一旦安全性被違反，一個(gè)負(fù)責(zé)的 BFT 算法可以識(shí)別出所有的拜占庭驗(yàn)證者。
傳統(tǒng)的 BFT 算法沒有這個(gè)屬性，在事件安全性上沒有提供任何保證。當(dāng)然，問責(zé) 制只適用于三分之一到三分之二的驗(yàn)證者是拜占庭的時(shí)候。如果拜占庭超過三分 之二，他們可以完全控制協(xié)議，我們不能保證正確的驗(yàn)證者會(huì)收到任何不當(dāng)行為 的證據(jù)。
此外，問責(zé)制可以在異步網(wǎng)絡(luò)中最大限度地發(fā)揮作用—在違反安全性之后，關(guān)鍵信息的延遲交付可能直到檢測(cè)到安全違規(guī)之后的某個(gè)時(shí)間，才能確定哪些驗(yàn) 證者是拜占庭。事實(shí)上，如果正確的進(jìn)程可以接收拜占庭行為的證據(jù)但是在它們 可以傳播下去之前不可逆轉(zhuǎn)地失敗，那么可能會(huì)導(dǎo)致問責(zé)制受到永久性損害的情況，盡管在實(shí)踐中，這種情況應(yīng)該是可以以高級(jí)的備份解決方案克服的。
通過列舉可能發(fā)生違反安全性的可能方式，并在每種情況下展現(xiàn)，拜占庭式驗(yàn)證器都是可識(shí)別的，協(xié)議可以被證明是有責(zé)任的。Tendermint 的簡單性使其比 管理領(lǐng)導(dǎo)選舉的協(xié)議更簡單。
在 Tendermint 中只有兩種違反安全規(guī)定的方式，兩者都是負(fù)責(zé)任的。第一種， 拜占庭提議者在一輪中提出兩個(gè)沖突的提案，然后拜占庭的驗(yàn)證者對(duì)兩者都投票。 第二種，拜占庭驗(yàn)證者在一些驗(yàn)證者已經(jīng)提交之后違反鎖定規(guī)則，導(dǎo)致其他驗(yàn)證 者在稍后的一輪中提交了一個(gè)不同的區(qū)塊。請(qǐng)注意，不可能通過三分之二或更少 的拜占庭驗(yàn)證者僅使用違反 Unlock-on-Polka 規(guī)則來違背安全性—超過三分之一 的驗(yàn)證者必須違反 Prevote-the-Lock，因?yàn)閼?yīng)該有一個(gè) Polka 證明剩下的誠實(shí)節(jié)點(diǎn) 的提交。
在沖突提議和沖突投票的情況下，通過接收兩個(gè)消息來檢測(cè)這個(gè)沖突，并通過他們的簽名來識(shí)別元兇并不重要。
在違反鎖定規(guī)則的情況下，違反安全性，正確的驗(yàn)證者必須廣播在該高度所看到的所有投票，以便將證據(jù)拼合在一起。數(shù)量不足三分之二的正確的驗(yàn)證者， 是產(chǎn)生兩個(gè)區(qū)塊提交的的全體投票。在這些投票中，如果沒有三分之一或更多的 驗(yàn)證者簽名沖突的投票，則有三分之一以上驗(yàn)證者違反 Prevote-the-Lock。
如果預(yù)投票或預(yù)提交影響到提交，則必須由正確的驗(yàn)證者看到。因此，通過收集所有投票，可以通過匹配每個(gè)預(yù)投票和被同一個(gè)驗(yàn)證者最近的預(yù)提交來檢測(cè) 違反 Prevote-the-Lock 的行為，除非不存在。
相似地，對(duì) Unlock-on-Polka 的違法可以通過匹配每個(gè)預(yù)提交和被證明的 Polka 來檢測(cè)出來。這意味著拜占庭驗(yàn)證者可以在看到 Polka 之前就可以預(yù)提交，而且 如果一個(gè)恰當(dāng)?shù)?Polka 最終到來的話，它可以逃避問責(zé)。然而，如果不管怎樣 Polka 都會(huì)產(chǎn)生的話，這種情況實(shí)際上并不會(huì)對(duì)安全性的違反做出什么貢獻(xiàn)。
目前的設(shè)計(jì)在 post-crisis 廣播協(xié)議中提供了問責(zé)制，但可以進(jìn)一步改進(jìn)以便實(shí) 時(shí)問責(zé)。也就是說，一次提交可以被改變成不僅包含預(yù)提交，而且還包含所有證明預(yù)提交的投票，一路回到該高度的開始。這樣一來，如果安全性被違反，可以立即檢查出不合理的投票。

3.6 故障和可用性

作為一個(gè) BFT 一致性算法，Tendermint 可以忍受最多至(但不包括)三分之
一的驗(yàn)證者的拜占庭故障。這意味著節(jié)點(diǎn)會(huì)崩潰，向不同的對(duì)等點(diǎn)發(fā)送不同且相 互矛盾的消息，拒絕中繼消息，或者在不損害安全性和活性的情況下隨意做出行為(伴有活性的通常 FLP 警告)。
在協(xié)議中有兩個(gè)地方可以通過利用基于本地時(shí)鐘的超時(shí)來優(yōu)化異步:在收到 三分之二或更多的預(yù)投票后，但不是單個(gè)區(qū)塊或 nil，和在收到三分之二或更多的預(yù)提交后，而不是單個(gè)區(qū)塊或 nil。在每種情況中，我們可以睡眠一段時(shí)間， 給予較慢或延遲的投票被接收的機(jī)會(huì)，從而減少?zèng)]提交一個(gè)區(qū)塊就進(jìn)入新一輪的 可能性。時(shí)鐘不需要在驗(yàn)證者上同步，因?yàn)槊慨?dāng)驗(yàn)證者觀察三分之二或更多其他 驗(yàn)證者的投票時(shí)，時(shí)鐘就將被重置。
如果三分之一或更多驗(yàn)證者崩潰，網(wǎng)絡(luò)就會(huì)停止，因?yàn)闆]有驗(yàn)證者可以在沒 有聽到其他超過三分之二驗(yàn)證集的情況下取得進(jìn)展。該網(wǎng)絡(luò)仍然可用于讀取，但不能進(jìn)行新的提交。驗(yàn)證者一旦恢復(fù)在線，就可以從它們離開的地方繼續(xù)下去。 一致性狀態(tài)機(jī)應(yīng)該使用預(yù)先記錄日志，以便恢復(fù)的驗(yàn)證者可以快速返回到其崩潰 時(shí)的步驟，確保它不會(huì)意外違反某項(xiàng)規(guī)則。
如果三分之一或更多的驗(yàn)證者是拜占庭，則他們可以通過多種方式來危及安全性，例如通過在同一輪中提出兩個(gè)區(qū)塊，并且通過將這兩個(gè)都提交進(jìn)行投票， 或者通過違反鎖規(guī)則來預(yù)提交兩個(gè)在相同的高度的區(qū)塊。在每種情況下，都有明 確可靠的證據(jù)表明某些驗(yàn)證者的行為不當(dāng)。在第一個(gè)例子中，他們?cè)谕惠喓炇?了兩項(xiàng)提議，這明顯違反了規(guī)則。在第二個(gè)例子中，他們可能已經(jīng)在第 R 輪中預(yù) 投票了與在 R-1 輪中鎖定的不同的區(qū)塊，這違反了 Prevote-the-Lock 規(guī)則。
當(dāng)使用經(jīng)濟(jì)和治理組件來激勵(lì)和管理一致性(第 6 章)時(shí)，這些額外的問責(zé) 保障變得至關(guān)重要。

3.7 結(jié)論

Tendermint 是一種弱同步的拜占庭容錯(cuò)狀態(tài)機(jī)復(fù)制協(xié)議，在違反 BFT 假設(shè)的 情況下，具有最佳的拜占庭容錯(cuò)能力和額外的問責(zé)制保障。協(xié)議對(duì)提議者使用輪流的方法，并使用相同的機(jī)制來跳過提議一個(gè)已經(jīng)提交的區(qū)塊的提議者。通過一個(gè)簡單的鎖定機(jī)制，可以保持安全。
本章中介紹的協(xié)議忽略了許多重要的細(xì)節(jié)，例如塊的高效傳播，緩沖交易，驗(yàn)證集的更改以及與應(yīng)用邏輯接口。這些重要課題將在后續(xù)章節(jié)中討論。

Chapter 4

Tendermint 子協(xié)議
前一章中的 Tendermint 一致性的介紹，忽略了一些關(guān)于用于傳播區(qū)塊，投票，交易和其他對(duì)等信息的流言協(xié)議的細(xì)節(jié)。這樣做是為了將注意力集中在一致性協(xié)議本身上，排除實(shí)用軟件工程的干擾。本章介紹了通過將組件實(shí)現(xiàn)為在每個(gè)對(duì)等連接上進(jìn)行復(fù)用的相對(duì)獨(dú)立的反應(yīng)器來實(shí)現(xiàn)這些細(xì)節(jié)的一種特定方法。

4.1 點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)(P2P-Networking)

在啟動(dòng)時(shí)，每個(gè) Tendermint 節(jié)點(diǎn)接收要撥打的對(duì)等點(diǎn)的初始列表。對(duì)于每個(gè)對(duì)等點(diǎn)，一個(gè)節(jié)點(diǎn)維護(hù)一個(gè)持久的 TCP 連接，其中多個(gè)子協(xié)議以一種速率限制的 方式進(jìn)行多路復(fù)用。消息被序列化成緊湊的二進(jìn)制表示，以在線上發(fā)送，并且通 過經(jīng)認(rèn)證的加密協(xié)議對(duì)連接進(jìn)行加密。
本章的其余部分描述了在每個(gè)對(duì)等連接上復(fù)用的單獨(dú)反應(yīng)器?？梢赃\(yùn)行一個(gè) 額外的對(duì)等點(diǎn)交換反應(yīng)器，允許節(jié)點(diǎn)請(qǐng)求彼此的其他對(duì)等地址，并跟蹤它們之前 連接到的對(duì)等點(diǎn)，以便保持與其他最小數(shù)量的對(duì)等點(diǎn)的連接。

4.2 一致性傳播(consensus gossip)

一致反應(yīng)器包裝一致狀態(tài)機(jī)，并確保每個(gè)節(jié)點(diǎn)每次更改時(shí)間的時(shí)候向所有對(duì)等點(diǎn)廣播其當(dāng)前狀態(tài)。以這種方式，每個(gè)節(jié)點(diǎn)跟蹤所有對(duì)等點(diǎn)的一致性狀態(tài)，允許它優(yōu)化消息的傳播，以便僅在非常時(shí)刻發(fā)送他們需要的對(duì)等點(diǎn)信息，以及它們不具有的信息。對(duì)于每個(gè)對(duì)等點(diǎn)，節(jié)點(diǎn)維護(hù)兩個(gè)連續(xù)檢查新信息以發(fā)送對(duì)等體的例程，即提議和投票。信息應(yīng)該以“rarest first”方式傳播，以最大限度地提高傳播效率，并盡量降低一些信息不可用的機(jī)會(huì)。

4.2.1 區(qū)塊數(shù)據(jù)(block data)

在第三章中，假設(shè)提案消息包括區(qū)塊。然而，由于區(qū)塊從單一來源出現(xiàn)并且可能相當(dāng)大，這給區(qū)塊提議者帶來了不必要的壓力將數(shù)據(jù)上傳到所有其他節(jié)點(diǎn);
如果將它們分成幾部分傳播，則可以更快地傳播區(qū)塊。
通過各種 p2p 協(xié)議普及的安全傳播數(shù)據(jù)的常見方法是使用 Merkle 樹，允許每個(gè)數(shù)據(jù)片段伴隨有一個(gè)簡短的證據(jù)(數(shù)據(jù)對(duì)數(shù)大小)，該片段是整體的一部分。為了使用這種方法，塊被序列化并且被分割成適當(dāng)尺寸的塊，用于期望的塊大小和驗(yàn)證器的數(shù)量，并且塊被散列到 Merkle 樹中。為了使用這種方法，對(duì)于期望的區(qū)塊大小和驗(yàn)證者的數(shù)量，區(qū)塊被序列化并且被分割成適當(dāng)尺寸的塊，并且塊被散列到一個(gè) Merkle 樹中。已簽署的提議，不是包括整個(gè)區(qū)塊，而是只包括 Merkle 根哈希，允許網(wǎng)絡(luò)在傳播塊上合作。一個(gè)節(jié)點(diǎn)在每次接收到一個(gè)塊時(shí)通 知它的對(duì)等點(diǎn)，以便通過多次發(fā)送相同的塊到一個(gè)節(jié)點(diǎn)來最小化浪費(fèi)帶寬。
一旦接收到所有的塊，區(qū)塊被反序列化和驗(yàn)證，以確保它正確地引用到前面 的區(qū)塊，并且其各種被 Merkle 樹實(shí)現(xiàn)的校驗(yàn)也是正確的。雖然以前假定驗(yàn)證者 在收到提議(包括區(qū)塊)之前不會(huì)預(yù)投票，但可以通過允許驗(yàn)證者在收到提議之 后，在收到完整的區(qū)塊之前進(jìn)行預(yù)投票，可以獲得一些性能收益。這就意味著預(yù) 投票那些最終是無效的票也是可以的。但是，無效區(qū)塊的預(yù)提交必須始終被視為 拜占庭。
被趕上的對(duì)等點(diǎn)(即處于較早高度的)會(huì)被發(fā)送區(qū)塊到它們所在的高度。一
次只處理一個(gè)區(qū)塊。

4.2.2 投票(votes)

在一致性狀態(tài)機(jī)的每個(gè)步驟中，在提案之后，節(jié)點(diǎn)需要等待投票(或本地超時(shí))來往下進(jìn)行。如果一個(gè)對(duì)等點(diǎn)剛進(jìn)入一個(gè)新的高度，它將被從上一個(gè)區(qū)塊預(yù) 提交，所以如果它是一個(gè)提議者，它可能會(huì)在下一個(gè)區(qū)塊的 LastCommit 中包含它們。如果一個(gè)對(duì)等點(diǎn)已經(jīng)預(yù)投票但尚未預(yù)提交，或已經(jīng)預(yù)提交，但尚未到下一輪，則分別發(fā)送預(yù)投票或預(yù)提交。如果一個(gè)對(duì)等點(diǎn)趕上來，那么它會(huì)將已提交區(qū) 塊的預(yù)提交發(fā)送到當(dāng)前的高度。

4.3 內(nèi)存池(mempool)

第 3 章幾乎沒有提到交易，因?yàn)?Tendermint 在每次交易的區(qū)塊上運(yùn)行，并且不關(guān)心單獨(dú)的交易，只要它們的校驗(yàn)和在區(qū)塊中是正確的。 交易在內(nèi)存中的緩存中獨(dú)立管理，而在比特幣之后，它被稱為 mempool。交
易在接收時(shí)被應(yīng)用程序邏輯驗(yàn)證，如果有效，則添加到 mempool，并使用有序 的多播算法來傳播。節(jié)點(diǎn)為每個(gè)對(duì)等點(diǎn)維護(hù)一個(gè)例程，以確保 mempool 中的交易以相同的順序被發(fā)送到對(duì)等點(diǎn)，在該順序中，它們由節(jié)點(diǎn)處理。
提議者從 mempool 中的有序列表中獲取交易，以獲取新的區(qū)塊建議。一旦某 個(gè)區(qū)塊被提交，塊中的所有交易將從內(nèi)存池中刪除，剩余的交易由應(yīng)用程序邏輯 重新驗(yàn)證，因?yàn)樗鼈兊挠行钥赡苡捎谔峤坏钠渌灰锥淖?#xff0c;節(jié)點(diǎn)可能已經(jīng)不 在其內(nèi)存池中。

4.4 同步區(qū)塊鏈

一致性反應(yīng)器提供了與最新的區(qū)塊鏈狀態(tài)同步的相對(duì)較慢的方式，因?yàn)樗辉O(shè)計(jì)為實(shí)時(shí)一致性，意味著對(duì)等點(diǎn)等待接收所有信息以提交單個(gè)區(qū)塊，然后再擔(dān) 心下一個(gè)區(qū)塊。為了適應(yīng)可能不止幾個(gè)區(qū)塊的對(duì)等體，一個(gè)附加的反應(yīng)器，區(qū)塊鏈反應(yīng)器允許對(duì)等點(diǎn)并行下載多個(gè)區(qū)塊，使對(duì)等點(diǎn)能夠比使用一致性反應(yīng)器同步 快幾百倍。
當(dāng)節(jié)點(diǎn)連接到新的對(duì)等點(diǎn)時(shí)，對(duì)等點(diǎn)發(fā)送其當(dāng)前高度。節(jié)點(diǎn)將從其當(dāng)前高度 順序地向所有自發(fā)報(bào)告更高高度的對(duì)等點(diǎn)請(qǐng)求區(qū)塊，同時(shí)下載區(qū)塊，并將其添加 到區(qū)塊池中。另一個(gè)例程連續(xù)地嘗試從池中移除區(qū)塊，并通過驗(yàn)證和執(zhí)行它們， 一次兩個(gè)區(qū)塊，違反區(qū)塊鏈的最新狀態(tài)，將其添加到區(qū)塊鏈。區(qū)塊必須一次被兩個(gè)區(qū)塊驗(yàn)證，因?yàn)橐粋€(gè)區(qū)塊的提交作為 LastCommit 數(shù)據(jù)包含在下一個(gè)區(qū)塊中。
節(jié)點(diǎn)連續(xù)查詢其對(duì)等點(diǎn)的當(dāng)前高度，并繼續(xù)同時(shí)請(qǐng)求區(qū)塊，直到其已經(jīng)達(dá)到其對(duì)等點(diǎn)中的最高高度，此時(shí)它停止請(qǐng)求對(duì)等點(diǎn)高度并啟動(dòng)一致性反應(yīng)器。

4.5 結(jié)論

對(duì)于 Tendermint 區(qū)塊鏈的實(shí)際實(shí)現(xiàn)，需要許多子協(xié)議。這些包括對(duì)一致性數(shù) 據(jù)(投票和提議)，區(qū)塊數(shù)據(jù)和交易的傳播，以及一些新對(duì)等點(diǎn)可以快速趕上最 新的區(qū)塊鏈狀態(tài)的方法。

Chapter 5

建立應(yīng)用
Tendermint 被設(shè)計(jì)為一個(gè)用于復(fù)制一個(gè)確定性狀態(tài)機(jī)的通用目的算法。它使用 Tendermint Socket Protocol (TMSP)來標(biāo)準(zhǔn)化一致性引擎和狀態(tài)機(jī)之間的通信， 使應(yīng)用程序開發(fā)人員能夠以任何編程語言構(gòu)建其狀態(tài)機(jī)，并通過 Tendermint 的 BFT 算法自動(dòng)復(fù)制它們。(*可以參考 etcd 的設(shè)計(jì)，實(shí)際上，完全沒有必要這樣 深度耦合日志和邏輯，日志歸日志，邏輯歸邏輯，這個(gè)部分的設(shè)計(jì)并不是非常的 好。從這個(gè)角度來說，比特幣的設(shè)計(jì)還是非常不錯(cuò)的。)

5.1 背景

互聯(lián)網(wǎng)上的應(yīng)用一般可以體現(xiàn)為包含兩個(gè)基本要素: ·引擎(engine):處理核心安全，網(wǎng)絡(luò)，復(fù)制。當(dāng)為一個(gè) web 應(yīng)用供電(powering)時(shí)，它通常是一個(gè)網(wǎng)絡(luò)服務(wù)器，比如 Apache 或 Nginx，或者當(dāng)它為一個(gè)分布式應(yīng) 用供電(powering)時(shí)，它就是一個(gè)一致性算法。
·狀態(tài)機(jī)(state-machine):處理從引擎接收的交易并更新內(nèi)部狀態(tài)的實(shí)際 應(yīng)用程序邏輯。
這種關(guān)注點(diǎn)的分離使得應(yīng)用的開發(fā)者可以以任何編程語言任意應(yīng)用程序的形 式編寫狀態(tài)機(jī)，位于可能專門用于其性能，安全性，可用性，支持和其他考慮因 素的引擎之上。
與 Web 服務(wù)器及其應(yīng)用程序不同，Web 服務(wù)器及其應(yīng)用程序通常采用通過公 共網(wǎng)關(guān)接口(CGI)協(xié)議在 socket 上進(jìn)行通信的形式，但一致性算法傳統(tǒng)上具有 少得多的可用或通用接口來構(gòu)建應(yīng)用程序。一些像 zookeeper，etcd，consul 和 其他分布式鍵值存儲(chǔ)為一個(gè)簡單的鍵值對(duì)應(yīng)用的一個(gè)特定實(shí)例提供 HTTP 接口， 和一些更有趣的特性比如原子比較交換(compare-and-swap)操作和通知推送。 但是它們不提供給應(yīng)用開發(fā)者狀態(tài)機(jī)代碼本身的控制。
對(duì)于在一致性引擎上運(yùn)行的狀態(tài)機(jī)的高水平控制的需求主要是由于比特幣的 成功以及隨之而來的對(duì)區(qū)塊鏈技術(shù)的興趣驅(qū)引的。通過將更高級(jí)的應(yīng)用程序直接 構(gòu)建到一致性算法，用戶，開發(fā)人員，監(jiān)管機(jī)構(gòu)等之中，可以在任意狀態(tài)機(jī)上實(shí) 現(xiàn)更大的安全保障，遠(yuǎn)遠(yuǎn)超過諸如貨幣，交易所，供應(yīng)鏈管理，治理等鍵值對(duì)存 儲(chǔ)之上。是允許集體實(shí)施代碼的執(zhí)行的系統(tǒng)的潛力吸引了如此多的注意力。它實(shí) 際上是法律制度的許多方面的重新發(fā)明，使用分布式一致性算法和確定性可執(zhí)行 的合同，而不是警察，律師，法官，陪審團(tuán)等。人類社會(huì)發(fā)展的影響力是爆炸式 的，就像民主法治的引入一樣。
Tendermint 旨在提供可能構(gòu)建此類應(yīng)用程序的基本界面和一致性引擎。

5.2 Tendermint Socket Protocol

Tendermint Socket Protocol (TMSP)定義了一致性引擎與應(yīng)用狀態(tài)機(jī)通信的核心接口。接口定義由許多使用 Google 協(xié)議緩沖區(qū)指定的消息類型組成，這些消息類型通過 socket 進(jìn)行長度預(yù)定義和傳輸。圖 5.1 給出了消息類型，參數(shù)，返回 值和目的的列表，并且圖 5.2 中顯示了體系結(jié)構(gòu)和消息流的概述。
TMSP 被實(shí)現(xiàn)為有序的異步服務(wù)器，其中消息類型為請(qǐng)求和響應(yīng)的對(duì)，特殊消 息類型 Flush 通過連接推送任何緩沖的消息并等待所有響應(yīng)。
TMSP 的核心是兩個(gè)消息:AppendTx 和 Commit。


一旦一致性決定了一個(gè)區(qū)塊，引擎將在區(qū)塊中的每個(gè)交易上調(diào)用 AppendTx， 將其傳遞給要處理的應(yīng)用程序狀態(tài)機(jī)。 如果交易有效，將導(dǎo)致應(yīng)用程序中的狀 態(tài)轉(zhuǎn)換。
一旦所有的 AppendTx 調(diào)用都返回，一致性引擎調(diào)用 Commit，導(dǎo)致應(yīng)用程序 提交最新狀態(tài)，并將其持續(xù)到磁盤上。

5.3 分離協(xié)議和執(zhí)行

使用 TMSP 可以讓我們明確分離出一致性，或一致的交易順序，和在狀態(tài)機(jī)上的實(shí)際執(zhí)行情況。具體來說，我們首先在順序上達(dá)到一致性，然后執(zhí)行有序的 交易。這種分離實(shí)際上提高了系統(tǒng)的容錯(cuò)能力:盡管 3f + 1 個(gè)副本仍然需要同意 以容忍 f 個(gè)拜占庭故障，但執(zhí)行只需要 2f + 1 個(gè)副本。也就是說，我們?nèi)匀恍枰?三分之二的多數(shù)來排序(ordering)，但是我們只需要二分之一的多數(shù)來執(zhí)行 (execution)。
但是另一方面，交易在排序后再執(zhí)行可能導(dǎo)致無效的交易，這樣就會(huì)浪費(fèi)系統(tǒng)資源。這可以通過使用由內(nèi)存池調(diào)用的附加 TMSP 消息 CheckTx 來解決，允許 它檢查交易是否對(duì)最新狀態(tài)有效。但是要注意，區(qū)塊的一次提交會(huì)引起 CheckTx 消息處理的復(fù)雜性。特別地，應(yīng)用需要維護(hù)另一個(gè)僅執(zhí)行與交易有效性相關(guān)的主 狀態(tài)機(jī)規(guī)則的狀態(tài)機(jī)。第二個(gè)狀態(tài)機(jī)由 CheckTx 消息更新，并在每次提交后重置 為最新的提交狀態(tài)。 實(shí)質(zhì)上，第二個(gè)狀態(tài)機(jī)描述了交易池的過濾器規(guī)則。
在一定程度上，CheckTx 可以用 optimistic execution，將結(jié)果返回給交易發(fā)送 方，并注意到，如果在提交感興趣的交易之前在區(qū)塊中提交了一個(gè)沖突的交易， 則結(jié)果可能會(huì)出錯(cuò)。這種 optimistic execution 是可擴(kuò)展 BFT 系統(tǒng)的一個(gè)方法的重 點(diǎn)，對(duì)于特殊的應(yīng)用程序，在很少有交易之間的沖突的情況下，這種方法可以很有效率。同時(shí)，由于需要處理可能的無效結(jié)果，它增加了客戶端的額外復(fù)雜性。 該方法在第 10 章進(jìn)一步討論。

5.4 微服務(wù)架構(gòu)(Microservice Architecture)

將應(yīng)用程序設(shè)計(jì)中的關(guān)心點(diǎn)分離為一個(gè)策略是非常明智的做法。特別地，今天許多大規(guī)模應(yīng)用的部署都采用微服務(wù)架構(gòu)，其中每個(gè)功能組件被實(shí)現(xiàn)為獨(dú)立的 網(wǎng)絡(luò)服務(wù)，并且通常封裝在 Linux 容器中(例如使用 Docker)以實(shí)現(xiàn)有效的部署， 可擴(kuò)展性和可升級(jí)性。
運(yùn)行在 Tendermint 一致性算法之上的應(yīng)用程序通?？梢苑纸獬晌⒎?wù)。舉個(gè) 例子，許多應(yīng)用程序利用鍵值對(duì)存儲(chǔ)來存儲(chǔ)狀態(tài)。作為獨(dú)立服務(wù)運(yùn)行鍵值對(duì)存儲(chǔ) 非常常見，以便利用數(shù)據(jù)存儲(chǔ)的特性，如高性能數(shù)據(jù)類型或 Merkle 樹。
應(yīng)用程序的另一個(gè)重要的微服務(wù)是一個(gè)治理模塊，它管理 TMSP 消息的某個(gè) 子集，使應(yīng)用程序能夠控制驗(yàn)證集的更改。這樣一個(gè)模塊可以成為 BFT 系統(tǒng)治理 的強(qiáng)大范例。
一些應(yīng)用程序可能會(huì)為用戶使用本地貨幣或帳戶結(jié)構(gòu)。 因此，提供支持例如 處理數(shù)字簽名和管理帳戶動(dòng)態(tài)的基本元素的模塊可能是有用的。
組合復(fù)雜 TMSP 應(yīng)用程序的可能的微服務(wù)列表繼續(xù)進(jìn)行。實(shí)際上，甚至可以 構(gòu)建一個(gè)可以使用交易中發(fā)送的數(shù)據(jù)啟動(dòng)子應(yīng)用程序的應(yīng)用程序。例如，在交易 中包括 docker 圖像的哈希，使得圖像可以從一些文件存儲(chǔ)后端被拉出，并作為 在一致性算法的未來交易中可能導(dǎo)致其執(zhí)行的子應(yīng)用程序運(yùn)行。這就是以太坊 (ethereum)的方法，它允許開發(fā)人員將一些代碼部署到網(wǎng)絡(luò)中，可以通過未來 的交易以及 IBM 最近的 OpenBlockChain(OBC)項(xiàng)目觸發(fā)在 Ethereum 虛擬機(jī)中 運(yùn)行，從而允許開發(fā)人員發(fā)送完整的 Docker 交易中的內(nèi)容，定義運(yùn)行任意代碼 的容器，以響應(yīng)發(fā)往它們的交易。

5.5 決定論(Determinism)

關(guān)于使用 TMSP 構(gòu)建應(yīng)用程序的最關(guān)鍵的注意事項(xiàng)是它們必須是確定性的。也就是說，對(duì)于復(fù)制的狀態(tài)機(jī)來說，在不損害安全性的情況下，每個(gè)節(jié)點(diǎn)在同一 狀態(tài)下執(zhí)行相同的事務(wù)時(shí)必須得到相同的結(jié)果。
這不是 Tendermint 自己特有的要求。比特幣、Raft、以太坊、任何其他分布 式一致性算法，以及如同 lock-step multi-player 這樣的游戲等應(yīng)用，都必須有嚴(yán) 格地確定性，以免出現(xiàn)一致性失敗的情況。
編程語言中有許多非確定性的來源，最明顯是通過隨機(jī)數(shù)和時(shí)間，但也可以 通過浮點(diǎn)精度的使用，以及通過哈希表的迭代(一些語言，比如 Go，在哈希表 上強(qiáng)制執(zhí)行隨機(jī)迭代，以強(qiáng)制程序員明確地了解何時(shí)需要有序數(shù)據(jù)結(jié)構(gòu))。決定 論的嚴(yán)格限制，以及它每一個(gè)主要編程語言的明顯缺陷，都促使以太坊開發(fā)自己 的圖靈完整的完全確定性的虛擬機(jī)，這些虛擬機(jī)構(gòu)成了應(yīng)用程序開發(fā)人員構(gòu)建位 于以太坊區(qū)塊鏈之上的應(yīng)用程序的平臺(tái)。但是決定性有很多怪癖，比如 32 字節(jié) 堆棧字，存儲(chǔ)鍵和存儲(chǔ)值，并且不支持字節(jié)移位操作—一切都是大數(shù)算術(shù)。
確定性編程在實(shí)時(shí)(real-time)，鎖步(lock-step)，多方游戲(multi-party gaming) 世界中得到了很好的研究。這樣的游戲構(gòu)成復(fù)制狀態(tài)機(jī)的另一個(gè)例子，并且在許 多方面與一致性算法非常相似。使用 TMSP 構(gòu)建應(yīng)用的開發(fā)者被鼓勵(lì)去研究他們 的方法，并且小心的實(shí)現(xiàn)一個(gè)應(yīng)用。一方面，使用功能編程語言和驗(yàn)證方法可以實(shí)現(xiàn)正確程序的構(gòu)建。另一方面，將非確定性程序轉(zhuǎn)化為規(guī)范確定性程序的編譯 器來正在被開發(fā)。

5.6 終止(Termination)

如果決定論對(duì)于保護(hù)安全性至關(guān)重要，則交易執(zhí)行終止對(duì)于保持活性至關(guān)重要。然而，一般來說，確定一個(gè)給定的程序是否停止，即使只是單個(gè)輸入，更不 用說所有輸入，一個(gè)稱為“停止問題(Halting Problem)”的問題，通常是不可能的。
以太坊虛擬機(jī)通過計(jì)量(metering)來解決問題，即對(duì)執(zhí)行中的每個(gè)操作進(jìn) 行計(jì)費(fèi)。這樣一來，當(dāng)發(fā)送者用盡資金時(shí)，交易就保證會(huì)被終止。通過將程序編 譯為自己的計(jì)量版本(metered version)的編譯器，這種 metering 可以在更一般 的情況下是可行的。
沒有顯著的開銷是難以解決這個(gè)問題的。實(shí)質(zhì)上，驗(yàn)證者不能夠判斷一個(gè)執(zhí) 行到底是在一個(gè)無限循環(huán)中，還是只是慢但是幾乎是完成的。使用 Tendermint 一致性協(xié)議來決定交易超時(shí)是可行的，這樣超過三分之二的驗(yàn)證者必須同意一個(gè) 交易超時(shí)，因此被認(rèn)為是無效的(即對(duì)狀態(tài)沒有任何影響)。然而，我們不在這 里繼續(xù)糾纏這個(gè)想法，而是把它留在今后的工作中。與此同時(shí)，預(yù)計(jì)應(yīng)用程序?qū)?在部署到任何一致性系統(tǒng)之前進(jìn)行徹底的測(cè)試，并且在一致性算法失敗的情況下， 將使用監(jiān)控和治理機(jī)制來重啟系統(tǒng)。

5.7 例子

在本節(jié)中，將介紹和討論越來越復(fù)雜的 TMSP 應(yīng)用程序的示例，特別關(guān)注CheckTx 和管理內(nèi)存池。

5.7.1 Merkleeyes

TMSP 應(yīng)用程序的一個(gè)簡單示例是基于 Merkle 樹的鍵值對(duì)存儲(chǔ)。Tendermint 提供 Merkleeyes，一個(gè) TMSP 應(yīng)用程序，它封裝了一個(gè)自平衡的，Merkle 二叉搜 索樹。交易的第一個(gè)字節(jié)決定交易是 get、set 還是 remove 操作。對(duì)于 get 和 remove 操作，剩下的字節(jié)是鍵(key)。對(duì)于 set 操作，剩下的字節(jié)是包含鍵(key)和 值(value)的序列化列表。Merkleeyes 可以使用一個(gè)簡單的 CheckTx 實(shí)現(xiàn)，只對(duì) 交易進(jìn)行解碼，以確保它的格式正確。我們還可以做一個(gè)更高級(jí)的 CheckTx，在 那里 get 和 remove 未知鍵的操作是無效的。一旦調(diào)用 Commit，最新的更新被添 加到 Merkle 樹中，所有的散列都被計(jì)算出來，并且樹的最新狀態(tài)被提交到磁盤。
請(qǐng)注意，Merkleeyes 旨在成為其他 TMSP 應(yīng)用程序使用的模塊，用于基于 Merkle 樹的鍵值對(duì)存儲(chǔ)，而不是獨(dú)立的 TMSP 應(yīng)用程序，盡管 TMSP 接口的簡單 性使其適用于兩者。

5.7.2 Basecoin

一個(gè)更完整的例子是一個(gè)簡單的貨幣，使用由以太坊開發(fā)的帳戶結(jié)構(gòu)，其中 每個(gè)用戶都有一個(gè)公鑰和一個(gè)公共密鑰的余額帳戶。該帳戶還包含一個(gè)序列號(hào)， 該序列號(hào)等于該帳戶發(fā)送的交易的數(shù)字。如果交易包含正確的序列號(hào)，并由正確 的私鑰簽名，則可以從帳戶中發(fā)送資金。沒有序列號(hào)，系統(tǒng)將容易發(fā)生重播攻擊 (replay attack)，即可以重播記錄帳戶的簽名交易借記，導(dǎo)致借記發(fā)生多次。
此外，為了防止多鏈環(huán)境中的重放攻擊，交易簽名應(yīng)該包括一個(gè)網(wǎng)絡(luò)或區(qū)塊鏈標(biāo)識(shí)符。
支持貨幣的應(yīng)用程序自然比簡單的鍵值對(duì)存儲(chǔ)有更多的邏輯。特別地，某些 交易明顯無效，例如簽名無效，序列號(hào)不正確或發(fā)送量大于發(fā)送者賬戶余額的交易。這些條件可以在 CheckTx 中檢查。
此外，為了更新序列號(hào)和帳戶余額，補(bǔ)充應(yīng)用程序狀態(tài)必須被維護(hù)，以便一 次在內(nèi)存池中涉及相同帳戶的多個(gè)交易時(shí)更新序列號(hào)和帳戶余額。當(dāng) commit 被 調(diào)用時(shí)，補(bǔ)充應(yīng)用狀態(tài)被重置為最新的提交狀態(tài)。任何仍然在內(nèi)存池中的交易都 可以通過 CheckTx 以最新的狀態(tài)重播。

5.7.3 以太坊(Ethereum)

Ethereum 使用已經(jīng)描述的機(jī)制將交易從 mempool 中刪除，但它也會(huì)在虛擬機(jī)中運(yùn)行一些交易，從而更新狀態(tài)并返回結(jié)果。CheckTx 中沒有完成虛擬機(jī)的執(zhí)行，因?yàn)樗鷥r(jià)更昂貴，并且在很大程度上取決于交易包含在區(qū)塊中的最終順序。

5.8 結(jié)論

TMSP 提供了一種簡單而靈活的手段，以任何編程語言構(gòu)建任意應(yīng)用程序，從 Tendermint 一致性算法繼承 BFT 狀態(tài)機(jī)復(fù)制。對(duì)于一個(gè)一致性引擎和一個(gè)應(yīng)用程 序來說，它扮演著更多同樣的角色，例如，CGI 扮演 Apache 和 Wordpress。然而， 應(yīng)用程序開發(fā)人員必須特別注意確保其應(yīng)用程序是確定性的，并且交易執(zhí)行是結(jié) 束的。

Chapter 6

管理(Governance)
到目前為止，本文已經(jīng)回顧了 Tendermint 一致性協(xié)議和應(yīng)用環(huán)境的基本要素。
在現(xiàn)實(shí)世界中操作系統(tǒng)的關(guān)鍵要素，如管理驗(yàn)證集的變更和從危機(jī)中恢復(fù)，還沒有討論。
本章提出了一種解決這些問題的方法，以使治理在協(xié)商一致系統(tǒng)中發(fā)揮作用。 當(dāng)驗(yàn)證集包含更多分散的代理集時(shí)，維護(hù)網(wǎng)絡(luò)的有效治理系統(tǒng)將對(duì)網(wǎng)絡(luò)的成功變 得越來越重要。

6.1 Governmint

治理的基本功能是通過一種投票方式來刪除行動(dòng)建議。治理作為軟件最基本 的實(shí)現(xiàn)是使用戶能夠提出提議，投票并統(tǒng)計(jì)投票的模塊。提議可能是程序性的， 在這種情況下，他們可以在成功投票后自動(dòng)執(zhí)行，或者它可能是非程序性的，在 這種情況下，其執(zhí)行是一個(gè)手動(dòng)練習(xí)。
為了在 Tendermint 中啟用某些操作，例如更改驗(yàn)證集或升級(jí)軟件，實(shí)施了一個(gè)稱為 Governmint 的治理模塊。Governmint 是一個(gè)最低限度的可行治理應(yīng)用， 支持多組實(shí)體，每個(gè)實(shí)體可以在內(nèi)部對(duì)提議進(jìn)行投票，其中一些可能導(dǎo)致程序性 執(zhí)行操作，例如更改驗(yàn)證集，或升級(jí) Governmint 本身(例如添加新提議類型或其他投票機(jī)制)。
該系統(tǒng)利用數(shù)字簽名認(rèn)證投票者，并可能使用各種可能的投票方案。特別感興趣的是二次投票方案，其中投票的成本是投票權(quán)的二次方，這已被證明具有滿 足投票者偏好的優(yōu)越能力。

6.2 驗(yàn)證集變更

驗(yàn)證集變更是現(xiàn)實(shí)世界一致性算法的關(guān)鍵組成部分，以前的許多方法都未能明確定義或被遺留為黑色藝術(shù)(black art)。Raft 艱難地闡明了驗(yàn)證集變更的良好協(xié)議，這需要使用新的消息類型通過一致性。Tendermint 采用了類似的方法，盡管它通過使用 EndBlock 消息的 TMSP 接口進(jìn)行標(biāo)準(zhǔn)化，該消息在所有 AppendTx 消息之后運(yùn)行，但在 Commit 之前運(yùn)行。如果交易或一組交易被包括在具有更新 驗(yàn)證集的預(yù)期效果的區(qū)塊中，則應(yīng)用程序可以通過響應(yīng) EndBlock 消息指定其公 鑰和新的投票權(quán)力來返回驗(yàn)證者列表以進(jìn)行更新?？梢酝ㄟ^將其投票權(quán)設(shè)置為零 來刪除驗(yàn)證者。這為應(yīng)用程序提供了更新驗(yàn)證集而不必指定交易類型的通用方法。
如果在高度 H 處的區(qū)塊返回已更新的驗(yàn)證集，則高度 H + 1 處的區(qū)塊將反射 更新。但是請(qǐng)注意，H + 1 區(qū)塊中的 LastCommit 必須使用與 H 處一樣的驗(yàn)證集， 因?yàn)樗赡馨驯粍h除的驗(yàn)證器的簽名。
投票權(quán)的更改適用于 H + 1，以便下一個(gè)提議者可以受到更新的影響。否則的 話，應(yīng)該是下一個(gè)提議者的驗(yàn)證者可能會(huì)被刪除。輪流算法應(yīng)該優(yōu)雅地直接地轉(zhuǎn) 到下一個(gè)提議者來處理。由于相同的區(qū)塊在至少三分之二的驗(yàn)證者上被復(fù)制，并 且輪流是確定性的，所以它們將全部都進(jìn)行相同的更新，并期望同一個(gè)下輪提議者。

6.3 懲罰拜占庭驗(yàn)證者

比特幣設(shè)計(jì)的一個(gè)顯著特點(diǎn)是它的激勵(lì)結(jié)構(gòu)，目前為止，協(xié)議的目標(biāo)是通過獎(jiǎng)勵(lì)驗(yàn)證者來激勵(lì)驗(yàn)證者的正確行為。雖然這在比特幣一致性協(xié)議的背景下是有 道理的，但優(yōu)越的激勵(lì)可能會(huì)提供強(qiáng)烈的抑制效果，使得驗(yàn)證者具有真正的 skin-in-the-game，而不是一個(gè)軟機(jī)會(huì)成本(soft opportunity cost)。
在 Tendermint 中可以使用 Vitalik Buterin 提出的方法作為所謂的 Proof-of-Stake 協(xié)議來實(shí)現(xiàn)消除負(fù)面效果。實(shí)質(zhì)上，驗(yàn)證者必須提供保證金(“他們必須保證一 定的賭注”)才能參與一致性。如果他們被發(fā)現(xiàn)簽署雙重提議或投票，其他驗(yàn)證 者可以以交易形式發(fā)布違規(guī)的證據(jù)，應(yīng)用程序狀態(tài)可以通過刪除違規(guī)者來修改驗(yàn) 證集，從而燒毀其存款。這具有將明確的經(jīng)濟(jì)成本與拜占庭行為聯(lián)系起來的效果， 并且能夠通過將三分之一或更多的驗(yàn)證者賄賂為拜占庭來估計(jì)違反安全性的成本。
請(qǐng)注意，一致性協(xié)議可以指定懲罰更多的行為，而不僅僅是雙重簽名。特別是，我們有興趣懲罰不公正的任何強(qiáng)烈的信號(hào)行為—通常為任何不是基于其他人報(bào)告的狀態(tài)報(bào)告的狀態(tài)變化。舉個(gè)例子，在 Tendermint 的一個(gè)版本中，所有預(yù)提交必須伴隨 polka 來證明它們，驗(yàn)證者可能會(huì)因廣播為被裁定的預(yù)提交而受到懲罰。但要注意的是，我們不能懲罰所有未預(yù)期到的行為—比如說，一個(gè)驗(yàn)證者在不是它提議的回合做出提議可能是優(yōu)先考慮異步和節(jié)點(diǎn)崩潰優(yōu)化的基礎(chǔ)。
實(shí)際上，沿著這兩條線概況 Tendermint，1)更為寬松的判定形式，2)允許 驗(yàn)證者在其任期之前提出建議，從而產(chǎn)生一個(gè)性質(zhì)與 Vlad Zamfir 所提出的相似 的協(xié)議族，以 guise Casper 作為未來以太坊版本的一致性機(jī)制。關(guān)于協(xié)議之間的 關(guān)系和反拜占庭判定的特征的更正式的說明仍然是未來的工作。

6.4 軟件更新(Software Upgrades)

Governmint 也可以作為在可能分散的網(wǎng)絡(luò)上協(xié)商軟件升級(jí)的自然手段。在公共互聯(lián)網(wǎng)上的軟件升級(jí)是一個(gè)非常具有挑戰(zhàn)性的操作，需要仔細(xì)規(guī)劃來維護(hù)不再 升級(jí)的用戶的向后兼容性，并且不會(huì)通過引入漏洞，刪除功能，增加復(fù)雜性，或 者可能最糟糕的，未經(jīng)許可自動(dòng)更新來使軟件的忠實(shí)用戶沮喪。
比特幣尤其明顯地提高了分散式一致性系統(tǒng)的更新難度。以太坊由于其強(qiáng)大的領(lǐng)導(dǎo)力和統(tǒng)一的社區(qū)已經(jīng)管理了一個(gè)成功的非向后兼容的升級(jí)版本，而 Bitcoin， 放下軟件工程中過多的弊病不說，由于一個(gè)惡性分裂的社區(qū)和缺乏強(qiáng)有力的領(lǐng)導(dǎo)， 而無法進(jìn)行一些必要的升級(jí)。
就變更的范圍而言，區(qū)塊鏈的更新一般分為 soft forks 和 hard forks。Soft forks 旨在向后兼容，并且使用協(xié)議中可能被尚未升級(jí)的用戶忽略的自由度，為用戶提 供新功能。另一方面，hard forks 是非向后兼容的升級(jí)，在比特幣的例子中，可 能會(huì)導(dǎo)致違背安全性，而在 Tendermint 的例子中，會(huì)導(dǎo)致系統(tǒng)終止。
為了應(yīng)對(duì)，比特幣軟件的開發(fā)人員推出了一系列 soft forks，驗(yàn)證者可以通過 在新的區(qū)塊中發(fā)信號(hào)來投票。一旦驗(yàn)證器的某個(gè)閾值是更新的信號(hào)，至少對(duì)于支 持更新的軟件版本的用戶，它將自動(dòng)在網(wǎng)絡(luò)上生效。由于這些 soft forks，比特幣 系統(tǒng)的效用大大增加，預(yù)計(jì)在未來將而繼續(xù)這樣做。有趣的是，社區(qū)未能成功地 hard fork 軟件，一方面引起了人們對(duì)該系統(tǒng)長期穩(wěn)定性的擔(dān)憂，另一方面引發(fā)了人們對(duì)該系統(tǒng)對(duì)腐敗治理—它的不可治理性—的恢復(fù)力的興奮和鼓舞。
鑒于今天世界上過多的政府腐敗，有很多理由采取后一種立場(chǎng)。然而，密碼 學(xué)和分布式一致性算法提供了一套新的缺乏強(qiáng)大的身份驗(yàn)證系統(tǒng)的工具，可以在 現(xiàn)代政府的“紙、筆、握手”的世界中甚至是傳統(tǒng)網(wǎng)絡(luò)的數(shù)字世界中產(chǎn)生不可想 象的一定程度的透明度和責(zé)任感。
在使用 Governmint 的系統(tǒng)中，開發(fā)人員將是區(qū)塊鏈上的標(biāo)識(shí)實(shí)體，可以提交 軟件升級(jí)提議。該機(jī)制與 Github 的 Pull Request 非常相似，只有它被集成到現(xiàn)場(chǎng) 運(yùn)行系統(tǒng)中，共識(shí)通過一致性協(xié)議傳遞?？蛻舳藨?yīng)寫入可配置的更新參數(shù)，這樣 他們可以指定是自動(dòng)更新還是更新前需要通知。
當(dāng)然，任何未經(jīng)徹底審查的軟件升級(jí)都可能對(duì)系統(tǒng)構(gòu)成危險(xiǎn)，所以通常應(yīng)該采取保守的方式升級(jí)。

6.5 危機(jī)恢復(fù)(Crisis Recovery)

在發(fā)生危機(jī)的情況下，比如交易日志中的 fork，或者系統(tǒng)陷入停頓，傳統(tǒng)的一致性系統(tǒng)很少甚至沒有提供保證，通常需要人工來干預(yù)。
Tendermint 保證，違反安全性責(zé)任的可以被識(shí)別，使得任何可以訪問至少一個(gè)誠實(shí)的驗(yàn)證者的客戶端都可以識(shí)別不誠實(shí)的驗(yàn)證者的加密確定性，從而選擇將 誠實(shí)的驗(yàn)證者跟蹤到具有一個(gè)不包括拜占庭的驗(yàn)證集的新鏈上。
舉個(gè)例子，假設(shè)三分之一或更多的驗(yàn)證者違反鎖規(guī)則，導(dǎo)致在高度 H 處有兩 個(gè)區(qū)塊要被提交。誠實(shí)的驗(yàn)證者可以通過傳播所以投票來確定是誰雙重簽名的。 在這一點(diǎn)上，由于基本的錯(cuò)誤假設(shè)被違反，它們不能使用一致性協(xié)議。注意，能 夠在這一點(diǎn)上為 H 累積所有的投票意味著關(guān)于在危機(jī)期間網(wǎng)絡(luò)連接和可用性的 重要假設(shè)，如果他不能由 p2p 網(wǎng)絡(luò)提供，它可能需要驗(yàn)證者們使用替代方案，比 如社交媒體和高可用性的服務(wù)來交流證據(jù)。一旦其中至少有三分之二收集了所有 的證據(jù)，全套的余留誠實(shí)節(jié)點(diǎn)可以啟動(dòng)一個(gè)新的區(qū)塊鏈。
或者，修改 Tendermint 協(xié)議，以便預(yù)提交要求 polka 將確保負(fù)責(zé) fork 的可以 立即受到懲罰，并且不需要額外的發(fā)布期。這個(gè)更改工作留給以后來做。
使用更復(fù)雜的 Governmint 來適應(yīng)各種特定的危機(jī)是可行的，比如永久性崩潰 故障和私鑰的危害。但是，這些方法必須仔細(xì)考慮，因?yàn)樗鼈兛赡軙?huì)破壞基礎(chǔ)協(xié) 議的安全性保障。我們以后將對(duì)這些方法進(jìn)行調(diào)查，但是要注意，理解其從危機(jī) 中恢復(fù)的能力的嵌入?yún)^(qū)塊鏈的社會(huì)經(jīng)濟(jì)背景的重要性。
不管危機(jī)如何恢復(fù)，其成功取決于與客戶端的整合。如果客戶端不接受新的 區(qū)塊鏈，則該服務(wù)實(shí)際上處于脫機(jī)狀態(tài)。因此，客戶端必須了解特定區(qū)塊鏈所用 的恢復(fù)規(guī)則。在上述違背安全性的情況下，他們還必須收集證據(jù)，確定要?jiǎng)h除哪 些驗(yàn)證者，并用剩余的驗(yàn)證者計(jì)算新的狀態(tài)。在違反活性的情況下，必須保持 Governmint。

6.6 結(jié)論

治理是分布式一致性系統(tǒng)的一個(gè)關(guān)鍵因素，盡管有關(guān)治理系統(tǒng)仍然知之甚少。
Tendermint 以一種叫做 Governmint 的 TMSP 提供治理，旨在促進(jìn)在分布式系統(tǒng)的基于軟件的治理中的增強(qiáng)實(shí)驗(yàn)。

Chapter 7

客戶端注意事項(xiàng)(Client Considerations)
本章回顧了與托管在 Tendermint 上的應(yīng)用程序交互的客戶端的一些注意事項(xiàng)。

7.1 發(fā)現(xiàn)

網(wǎng)絡(luò)發(fā)現(xiàn)只需通過 TCP 連接一些種子節(jié)點(diǎn)即可。p2p 網(wǎng)絡(luò)使用經(jīng)過身份驗(yàn)證的加密，但是驗(yàn)證者的公鑰必須以某種方式從 band 中驗(yàn)證，即通過一種替代的 媒介，而不是在協(xié)議的范圍內(nèi)。實(shí)際上，在這些系統(tǒng)中，起源狀態(tài)本身必須要被 傳出 band 以外，理想情況下，也是唯一必須要被通信出去的東西，因?yàn)樗€應(yīng) 該包含驗(yàn)證者使用的用來驗(yàn)證加密的公鑰，與在一致性中用于簽署投票的方式是 不同的。
對(duì)于可能隨時(shí)間變化的驗(yàn)證集，通過 DNS 注冊(cè)所有驗(yàn)證者以及在新的驗(yàn)證者 實(shí)際成為驗(yàn)證者之前注冊(cè)它們是有用的，并在其以驗(yàn)證者身份被刪除后將其刪除。 或者，驗(yàn)證者位置可以注冊(cè)在另一個(gè)容錯(cuò)分布式數(shù)據(jù)存儲(chǔ)中，可能包括另一個(gè) Tendermint 集群本身。

7.2 廣播交易

作為通用應(yīng)用平臺(tái)，Tendermint 僅為廣播交易的客戶端(clients)提供簡單
的接口(interface)。一般范例是客戶端通過代理連接到 Tendermint 的一致性網(wǎng) 絡(luò)，該代理可以在其本地機(jī)器上運(yùn)行，也可以托管在其他提供商。代理功能作為 網(wǎng)絡(luò)上的非驗(yàn)證者節(jié)點(diǎn)，這意味著它可以跟上一致性并處理交易，但不會(huì)簽署投 票。該代理使客戶端交易能夠通過傳播層快速廣播到整個(gè)網(wǎng)絡(luò)中。
節(jié)點(diǎn)只需要連接到網(wǎng)絡(luò)上的另一個(gè)節(jié)點(diǎn)來廣播交易，但默認(rèn)情況下會(huì)連接到 許多節(jié)點(diǎn)，從而最小化交易不會(huì)被接收的機(jī)會(huì)。交易被傳遞到內(nèi)存池，并通過要在所有節(jié)點(diǎn)的內(nèi)存池中被緩存的內(nèi)存池反應(yīng)器傳播，以便最終它們其中的一個(gè)可以將它包含在一個(gè)區(qū)塊中。
請(qǐng)注意，交易在進(jìn)入一個(gè)區(qū)塊之后才會(huì)執(zhí)行它的狀態(tài)，所以客戶端不會(huì)馬上 得到結(jié)果，而不是確認(rèn)它被接受到 mempool 并廣播給其他對(duì)等點(diǎn)?？蛻舳藨?yīng)該 在一個(gè)區(qū)塊的提交過程中計(jì)算出來的時(shí)候?qū)Υ磉M(jìn)行注冊(cè)，以接收其作為推送通 知的結(jié)果。
客戶端連接到當(dāng)前提議者并不是必需的，因?yàn)樽罱K任何在其內(nèi)存池中具有交 易的驗(yàn)證者都可以提出它。然而，在網(wǎng)絡(luò)處于高負(fù)荷下的某些情況下，對(duì)下一個(gè)提案的優(yōu)先廣播可能會(huì)降低交易的延遲。不然的話，交易應(yīng)該迅速被傳播到每個(gè)驗(yàn)證器。

7.3 內(nèi)存池(Mempool)

內(nèi)存池負(fù)責(zé)在內(nèi)存被包含在區(qū)塊中之前緩存交易。它的行為很微妙，對(duì)整個(gè)系統(tǒng)架構(gòu)構(gòu)成了一系列的挑戰(zhàn)。首先，在內(nèi)存池中緩存任意數(shù)量的交易可以直接 拒絕可能會(huì)使網(wǎng)絡(luò)癱瘓服務(wù)攻擊。大多數(shù)區(qū)塊鏈?zhǔn)褂闷湓泿艁斫鉀Q這個(gè)問題， 并且只允許花費(fèi)一定費(fèi)用的交易留在內(nèi)存池中。
在一個(gè)更廣泛的，不必須一種貨幣支付的系統(tǒng)中，比如 Tendermint，系統(tǒng)必 須建立更嚴(yán)格的過濾規(guī)則，并依靠更智能的客戶端重新提交被丟棄的交易。然而， 這種情況更為微妙，因?yàn)樵?mempool 中過濾交易的規(guī)則集必須是應(yīng)用程序本身 的一個(gè)功能。因此，TMSP 的 CheckTx 消息，mempool 可以使用來針對(duì)應(yīng)用程序 的瞬態(tài)狀態(tài)(transient state)運(yùn)行交易，以確定是否應(yīng)該保留或丟棄。
盡管在許多示例應(yīng)用程序中提供了例子，但處理瞬態(tài)是不重要的，并且可以 把它留給應(yīng)用程序開發(fā)人員。在任何情況下，客戶端必須監(jiān)視內(nèi)存池的狀態(tài)(即 未確認(rèn)的交易)，以確定他們是否需要重新廣播他們的交易，這可能發(fā)生在高度 并發(fā)的，其中一個(gè)交易的有效性取決于已處理的另一個(gè)交易的設(shè)置中。

7.4 語義(Semantics)

Tendermint 的核心一致性算法只提供至少一次(at-least-once)的語義，也就是說系統(tǒng)常受到重放攻擊(replay attacks)的影響，即同一個(gè)交易可以被多次提交。然而，許多用戶和應(yīng)用程序期望能從數(shù)據(jù)庫系統(tǒng)得到一個(gè)更強(qiáng)的保證。 Tendermint 系統(tǒng)的靈活性把這些語義的嚴(yán)格性留給應(yīng)用程序開發(fā)人員。通過利用 CheckTx 消息，和充分管理應(yīng)用程序中的狀態(tài)，應(yīng)用程序開發(fā)人員可以提供適合 他們和他們的用戶的需求的數(shù)據(jù)庫語義。比如說，如第 5 章所述，使用基于具有 序列號(hào)的帳戶系統(tǒng)可以減輕重放攻擊，并將語義從至少一次(at-least-once)更 改為恰好一次(exactly-once)。

7.5 讀取(Reads)

客戶端將讀請(qǐng)求發(fā)送到用于廣播交易(寫入)的同一個(gè)代理節(jié)點(diǎn)。即使網(wǎng)絡(luò)
停止了，代理始終都可用于讀取。然而，在分區(qū)的情況下，代理可以與網(wǎng)絡(luò)的其余部分分開，繼續(xù)制造區(qū)塊。在這種情況下，代理的讀取可能會(huì)過時(shí)。
為了避免過時(shí)的讀取，讀取請(qǐng)求可以作為交易發(fā)送，假定應(yīng)用程序允許這樣 的查詢。通過使用交易，保證讀取返回最新的提交狀態(tài)，即在下一個(gè)區(qū)塊中提交讀取交易時(shí)。這當(dāng)然比查詢狀態(tài)的代理更昂貴?？梢允褂脝l(fā)式方法來確定讀取 是否過期，例如代理與其對(duì)等點(diǎn)是否良好連接，并且正在制作區(qū)塊;或者是否它 被卡在有三分之一或以上的驗(yàn)證者的投票的回合中，但沒有替換執(zhí)行實(shí)際的交 易。

7.6 Light Client Proofs

在傳統(tǒng)數(shù)據(jù)庫中，區(qū)塊鏈的主要?jiǎng)?chuàng)新之一是他們有意識(shí)地使用 Merkle 哈希樹來支持系統(tǒng)子狀態(tài)的緊湊證明的成果，即所謂的 light-client 證明。一個(gè) light client proof 是一個(gè)允許客戶端驗(yàn)證一些鍵值對(duì)是在有一個(gè)給定跟哈希的 Merkle 樹中的 Merkle 樹的路徑。狀態(tài)的 Merkle 根哈希包含在區(qū)塊的頭(header)中，這樣就 足以讓客戶端只有最新的頭來驗(yàn)證狀態(tài)的任何組件。當(dāng)然，要知道 header 本身 是有效的，它們必須已經(jīng)驗(yàn)證了整個(gè)鏈，或者只保持最新的驗(yàn)證集更改，并且依 賴于狀態(tài)轉(zhuǎn)換是正確的經(jīng)濟(jì)保證。

7.7 結(jié)論

Tendermint 網(wǎng)絡(luò)功能的客戶端與任何其他分布式數(shù)據(jù)庫的相似，盡管必須要考慮到基于區(qū)塊的提交的性質(zhì)以及內(nèi)存池的行為。另外，客戶端必須考慮到以特 定的應(yīng)用設(shè)計(jì)。 雖然這增加了一些復(fù)雜性，但是它具有極大的靈活性。

Chapter 8

實(shí)現(xiàn)
Tendermint 的參考實(shí)現(xiàn)是由 Go 編寫的，托管在 Github 上。Go 是一種具有豐富標(biāo)準(zhǔn)庫的，輕量級(jí)大規(guī)模并發(fā)執(zhí)行的并發(fā)原語，以及為簡化和高效率優(yōu)化的開 發(fā)環(huán)境的，類似 C 的語言。
代碼使用了大量足夠模塊化來隔離成自己的庫的包。這些包大部分是由 Jae Kwon 編寫的，包括漏洞修復(fù)，測(cè)試，以及一些作者貢獻(xiàn)的偶然特性。這些包中 最重要的部分在下面的小節(jié)中描述。

8.1 二進(jìn)制序列號(hào)(Binary Serialization)

Tendermint 使用了一種為簡單性和決定性優(yōu)化的二進(jìn)制序列化算法。它支持所有整數(shù)類型(包括使用一個(gè)字節(jié)長度的前綴編碼的變體)，字符串，字節(jié)數(shù)組 和時(shí)間(毫秒精度的 unix 時(shí)間)。它還支持任何類型和結(jié)構(gòu)體的數(shù)組(編碼為 有序值的列表，忽略鍵)。在某種程度上，它靈感來自 Go 的類型系統(tǒng)，特別是 它使用的接口類型，可以實(shí)現(xiàn)為許多具體類型之一。可以注冊(cè)接口，并且每個(gè)具 體實(shí)現(xiàn)都在其編碼中給出了一個(gè)領(lǐng)先的類型字節(jié)。
詳情參見 https://github.com/tendermint/go-wire。

8.2 密碼學(xué)

一致性算法，如 Tendermint 使用三個(gè)主要加密原語:數(shù)字簽名，哈希函數(shù)和驗(yàn)證加密。雖然存在這些原語的許多實(shí)現(xiàn)，但為企業(yè)軟件選擇加密庫亦不是輕松 的任務(wù)，特別是世界上最常用的安全庫 OpenSSL 的深刻的不安全性。
導(dǎo)致加密系統(tǒng)不安全的原因是，有像與 NIST 合作，設(shè)計(jì)并標(biāo)準(zhǔn)化了當(dāng)今使用 的許多最流行的加密算法的 NSA，這樣的政府機(jī)構(gòu)有意的破壞其安全屬性。鑒于 這些機(jī)構(gòu)明顯不合法，例如愛德華斯諾登(Edward Snowden)，以及試圖破壞公 共密碼標(biāo)準(zhǔn)的歷史，許多密碼學(xué)社區(qū)更傾向于使用在開放的學(xué)術(shù)環(huán)境中設(shè)計(jì)的算 法。同樣，Tendermint 也只使用這種算法。
Tendermint 使用了 RIPEMD160 作為它的加密哈希函數(shù)，它產(chǎn)生 20 字節(jié)的輸 出。它用于交易和驗(yàn)證簽名的 Merkle 樹，并用于計(jì)算塊散列。Go 在其擴(kuò)展庫中 提供了一個(gè)實(shí)現(xiàn)。在從公鑰派生的地址中，比特幣也使用 RIPEMD160 作為兩種 哈希函數(shù)中的一種。
作為其數(shù)字簽名方案，Tendermint 在 ED25519 橢圓曲線上使用 Schnorr 簽名。 ED25519 是由丹伯恩斯坦(Dan Bernstein)開源設(shè)計(jì)的，其目的是高性能，易于 實(shí)現(xiàn)，但不引入漏洞。伯恩斯坦還引入了 NaCl，一個(gè)高級(jí)庫，用于使用 ED25519 曲線進(jìn)行經(jīng)過身份驗(yàn)證的加密。Tendermint 使用其擴(kuò)展庫中提供的實(shí)現(xiàn)。

8.3 Merkle 哈希樹

Merkle 樹的功能非常類似于其他基于樹的數(shù)據(jù)結(jié)構(gòu)，還有額外的功能，它可以生成樹中一個(gè)鍵的成員身份證明，而樹的大小是對(duì)數(shù)的。這是由遞歸地連接和 哈希鍵組合完成的，直到只剩下一個(gè)哈希，樹的根哈希。對(duì)于樹上的任何葉子， 從它到根的一條哈希的痕跡作為它的成員的證明。這使得 Merkle 樹特別適用于 p2p 文件共享應(yīng)用程序，在該應(yīng)用程序中，可以將大型文件的片段作為屬于文件 的內(nèi)容進(jìn)行驗(yàn)證，而不需要所有的片段。Tendermint 將此機(jī)制用于網(wǎng)絡(luò)上的傳播 塊，其中根哈希被包含在區(qū)塊提議中。
Tendermint 還提供了一個(gè)自我平衡的 Merkle 二叉樹，以 AVL 樹為模型，作為 一個(gè)名為 Merkleeyes 的 TMSP 服務(wù)。IAVL 樹可以用于存儲(chǔ)動(dòng)態(tài)大小的狀態(tài)，允 許在對(duì)數(shù)時(shí)間內(nèi)查找、插入和刪除。

8.4 RPC

Tendermint 公開了 HTTP API，用于查詢區(qū)塊鏈、網(wǎng)絡(luò)信息、一致性狀態(tài)以及廣播交易。同樣的 API 可以通過三種方法獲得:使用 URI 編碼參數(shù)的 GET 請(qǐng)求， 使用 JSONRPC 標(biāo)準(zhǔn)的 POST 請(qǐng)求，以及使用 JSONRPC 標(biāo)準(zhǔn)的 websockets。 Websockets 是高交易吞吐量的首選方法，也是接收事件的必要條件。

8.5 P2P 網(wǎng)絡(luò)

第 4 章更詳細(xì)地描述了 Tendermint 使用的 P2P 子協(xié)議。

8.6 反應(yīng)器(Reactor)

Tendermint 節(jié)點(diǎn)由多個(gè)并發(fā)反應(yīng)堆組成，每一個(gè)都管理一個(gè)狀態(tài)機(jī)在網(wǎng)絡(luò)上給對(duì)等點(diǎn)發(fā)送和接收消息，如第 4 章所述。反應(yīng)器通過鎖定共享數(shù)據(jù)結(jié)構(gòu)來同步， 但是同步的點(diǎn)被保持在最小值，這樣每個(gè)反應(yīng)器就會(huì)和其他反應(yīng)器同時(shí)運(yùn)行。

8.6.1 內(nèi)存池(Mempool)

Mempool 反應(yīng)器管理 mempool，在它們被打包在區(qū)塊上并提交之前緩存交易。
Mempool 使用應(yīng)用程序狀態(tài)機(jī)的一個(gè)子集來檢查交易的有效性。交易保存在一 個(gè)并發(fā)鏈表結(jié)構(gòu)中，允許安全寫入和許多并發(fā)讀取。新的、有效的交易被添加到 列表的末尾。每個(gè)對(duì)等點(diǎn)遍歷列表，將每個(gè)交易只需要一次有序地發(fā)送到對(duì)等點(diǎn)。 該列表還被掃描為一個(gè)新的提議收集交易，并在每次提交一個(gè)區(qū)塊時(shí)更新:提交 了的交易被刪除，未被提交的交易通過 CheckTx 被重新運(yùn)行，以及那些已經(jīng)失效 的交易被刪除。

8.6.2 共識(shí)(Consensus)

一致性反應(yīng)器管理一致性狀態(tài)機(jī)，它處理提議、投票、鎖和實(shí)際提交區(qū)塊。
狀態(tài)機(jī)使用一些持久化的例行程序(go-routines)來管理，這些例行程序接收到 消息，并使它們能夠確定地回放，以調(diào)試狀態(tài)。這些例行程序包括 readLoop，用于讀取接收到的消息隊(duì)列和 timeoutLoop，用于注冊(cè)和觸發(fā)超時(shí)事件。
在一致性狀態(tài)機(jī)中，當(dāng)收到完整的提議和區(qū)塊時(shí)，或者在給定的回合中收到 超過三分之二的預(yù)投票或預(yù)提交時(shí)，則會(huì)進(jìn)行轉(zhuǎn)換。轉(zhuǎn)換導(dǎo)致了建議、區(qū)塊數(shù)據(jù) 或投票的廣播，這些數(shù)據(jù)在內(nèi)部隊(duì)列(internalReqQueue)上排隊(duì)，由 readLoop 在串行上處理從對(duì)等點(diǎn)接收到的消息。這將內(nèi)部消息和對(duì)等消息放在平等的基礎(chǔ) 上，并將其輸入到一致性狀態(tài)機(jī)中，但允許內(nèi)部消息被更快地處理，因?yàn)樗鼈儾?像來自對(duì)等點(diǎn)那樣處于相同的隊(duì)列中。

8.6.3 區(qū)塊鏈(Blockchain)

區(qū)塊鏈反應(yīng)器采用比一致性反應(yīng)器更快的技術(shù)來同步區(qū)塊鏈。也就是說，驗(yàn)證者請(qǐng)求區(qū)塊的遞增高度，直到他們的對(duì)等點(diǎn)沒有任何更高的高度的區(qū)塊。區(qū)塊被收集在一個(gè)區(qū)塊池(blockpool)中，并通過一個(gè)工作例程同步到區(qū)塊鏈，它周 期性地從池中取區(qū)塊，并對(duì)當(dāng)前鏈進(jìn)行驗(yàn)證。
一旦區(qū)塊鏈反應(yīng)器完成同步，它就會(huì)啟動(dòng)一個(gè)一致性反應(yīng)器來接管。

8.7 結(jié)論

Tendermint 的 Go 語言實(shí)現(xiàn)充分利用了語言的并發(fā)原語、垃圾回收和類型安全性，以提供一個(gè)清晰的、模塊化的、易于閱讀的，包含許多可重用組件的代碼。 如第 9 章所示，該實(shí)現(xiàn)獲得高性能，并對(duì)許多不同類型的錯(cuò)誤具有強(qiáng)大的魯棒性。

Chapter 9

性能和容錯(cuò)
Tendermint 被設(shè)計(jì)為一種拜占庭容錯(cuò)的狀態(tài)機(jī)復(fù)制算法。只要不到三分之一的驗(yàn)證者是拜占庭，它就保證安全性，類似地，只要網(wǎng)絡(luò)信息最終和用來傳播協(xié) 議的有關(guān)網(wǎng)絡(luò)同步的弱假設(shè)被傳送，它就保證了活性。在本節(jié)中，我們通過注入 宕機(jī)故障和拜占庭故障來經(jīng)驗(yàn)性地評(píng)估 Tendermint 的容錯(cuò)能力。目標(biāo)是，表明 在發(fā)生這種故障的情況下，Tendermint 一致性的實(shí)現(xiàn)并不會(huì)影響安全性，因此可 以最小化性能受到的影響，并且可以很快地恢復(fù)。
Tendermint 算法的性能可以通過幾種關(guān)鍵方式進(jìn)行評(píng)估。最明顯的措施是區(qū) 塊提交時(shí)間，它是最終延遲的度量，以及衡量網(wǎng)絡(luò)容量的交易吞吐量。我們?yōu)槊?個(gè)分布在全球范圍內(nèi)的驗(yàn)證者收集數(shù)據(jù)，驗(yàn)證者的數(shù)量范圍都是 2 從 2 到 64 的 倍數(shù)。

9.1 總覽

本章的實(shí)驗(yàn)用例存儲(chǔ)在 https://github.com/tendermint/network_testing 數(shù)據(jù)倉庫。所有的實(shí)驗(yàn)都在 docker 容器中進(jìn)行，這些容器運(yùn)行在 t2.medium 或 c3.8xlarge 類型的 Amazon EC2 實(shí)例上。t2.medium 有 2 個(gè) vCPU 和 4 GB 的 RAM，c3.8xlarge 有 32 個(gè) vCPUs 和 60 GB 的 RAM。實(shí)例分布在橫跨五大洲 的 7 個(gè)數(shù)據(jù)中心。另一個(gè)負(fù)責(zé)生成交易的 docker 容器在每個(gè)實(shí)例上運(yùn)行。交易的大小是 250 字節(jié)(一個(gè)包括 32 或 64 字節(jié)的哈希和簽名的合理的大小)，并被 構(gòu)造成可調(diào)試的，可以快速生成的，并包含一些隨機(jī)性的。因此，前面的字節(jié)是 表示該實(shí)例的交易號(hào)和驗(yàn)證者索引的 Big-Endian 編碼整數(shù)，后面的 16 個(gè)字節(jié)是 從操作系統(tǒng)中隨機(jī)生成的，中間的字節(jié)全是零。
使用網(wǎng)絡(luò)監(jiān)視工具來維護(hù)每個(gè)驗(yàn)證者的 Tendermint RPC 服務(wù)器的活動(dòng)的 websocket 連接，并且在第一次接收到新的提交的區(qū)塊作為該區(qū)塊的官方提交時(shí) 間時(shí)，使用其本地時(shí)間。實(shí)驗(yàn)首先在沒有監(jiān)視器的情況下運(yùn)行，通過復(fù)制驗(yàn)證者 中的所有數(shù)據(jù)來進(jìn)行分析，并使用 2/3th 驗(yàn)證者提交區(qū)塊的本地時(shí)間作為提交時(shí) 間。使用監(jiān)視器的速度要快得多，能夠在線監(jiān)測(cè)，而且被發(fā)現(xiàn)只要區(qū)塊頭信息(不 是整個(gè)區(qū)塊)通過 websockets，就不會(huì)影響結(jié)果。
遠(yuǎn)程機(jī)器上的 Docker 容器很容易使用 Docker-machine 工具進(jìn)行管理，而網(wǎng)絡(luò) 測(cè)試存儲(chǔ)庫提供了一些工具，可以利用 Go 的并發(fā)特性，同時(shí)在許多遠(yuǎn)程機(jī)器上 執(zhí)行 Docker 容器上的操作。
每個(gè)驗(yàn)證者都直接連接彼此，以避免網(wǎng)絡(luò)拓?fù)涞幕煜?yīng)。
對(duì)于涉及宕機(jī)故障或拜占庭行為的實(shí)驗(yàn)，故障節(jié)點(diǎn)的數(shù)量由 Nfault = [(N - 1) / 3] 給出，其中 N 是驗(yàn)證者的總數(shù)。

9.2 吞吐量和延遲(Throughput and Latency)

本節(jié)描述了在非對(duì)抗性條件下測(cè)試 Tendermint 的原始性能的實(shí)驗(yàn)，其中所有節(jié)點(diǎn)都在線并同步，并且不為異步提供任何設(shè)施。也就是說，使用了一個(gè)人為的 高的 TimeoutPropose(10 秒)，所有其他超時(shí)參數(shù)均設(shè)置為 1 毫秒。此外，所 有的 mempool 活動(dòng)都是禁用的(在提交之后不會(huì)傳播交易或重新檢查它們)， 而在進(jìn)程內(nèi)的 nil 應(yīng)用程序則用于繞過 TMSP。這可以作為一個(gè)控制場(chǎng)景，用于評(píng) 估在故障和/或異步的情況下的性能下降。
實(shí)驗(yàn)運(yùn)行在大小為 2 的從 2 到 64 倍的驗(yàn)證集和大小為 2 的從 128 到 32768 被的區(qū)塊上。交易被預(yù)先加載到每個(gè)驗(yàn)證器上。每個(gè)實(shí)驗(yàn)運(yùn)行 16 個(gè)區(qū)塊。
從圖 9.1 可以看出，Tendermint 可以輕松在大約一秒鐘的區(qū)塊延遲里處理每 秒數(shù)千個(gè)交易，盡管每秒大約有一萬個(gè)交易的容量限制。16384 個(gè)交易的區(qū)塊的 大小約為 4 MB，網(wǎng)絡(luò)帶寬分析顯示每個(gè)連接很容易達(dá)到 20MB / s 以上，盡管日 志分析表明，在高的區(qū)塊大小時(shí)，驗(yàn)證者可以花費(fèi)高至兩秒鐘時(shí)間等待區(qū)塊部分。 此外，如圖 9.2 所示，在單個(gè)數(shù)據(jù)中心進(jìn)行的實(shí)驗(yàn)表明，在更大的機(jī)器上進(jìn)行的 實(shí)驗(yàn)可以得到更高的吞吐量的可能，而在更大的機(jī)器上的實(shí)驗(yàn)顯示出更一致的性 能，從而消除了容量限制，如圖 9.3 所示。我們將在未來進(jìn)一步進(jìn)行調(diào)查這一容 量限制的工作。
在隨后的實(shí)驗(yàn)中，注入了各種形式的故障，并給出了延遲的統(tǒng)計(jì)數(shù)據(jù)。每個(gè) 實(shí)驗(yàn)都是在大小為 2 的從 4 到 32 倍的驗(yàn)證集，不同的 TimeoutPropose 值，和大 小為 2048 個(gè)交易的區(qū)塊上運(yùn)行的。

9.3 宕機(jī)故障(Crash Failure)

為了評(píng)估一個(gè)常遭受宕機(jī)故障的網(wǎng)絡(luò)的性能，每 3 秒鐘 Nfault 個(gè)驗(yàn)證者被隨機(jī)選擇，停止，并在三秒鐘后重新啟動(dòng)。
在表 9.1 中的結(jié)果表明，在這個(gè)宕機(jī)故障場(chǎng)景下的性能下降了大約 50%，而更大的 TimeoutPropose 值有助于調(diào)節(jié)延遲。當(dāng)平均延遲時(shí)間增加到大約 2 秒時(shí)， 中間值接近 1 秒，延遲可能高達(dá) 10 到 20 秒，但在一個(gè)情況下，它高達(dá) 70 秒。
很有可能修改時(shí)間的提議是稍微不確定的，這可能會(huì)降低這種極端的延遲的可能 性。將 TimeoutPropose 修改為稍微不確定可能會(huì)降低這種極端延遲的可能性。

9.4 隨機(jī)網(wǎng)絡(luò)延遲(Random Network Delay)

可能歸因于拜占庭行為或網(wǎng)絡(luò)異步的另一種形式的故障是在每次讀取和寫入網(wǎng)絡(luò)連接時(shí)注入隨機(jī)延遲。在這個(gè)實(shí)驗(yàn)中，在每個(gè)網(wǎng)絡(luò)連接讀取和寫入之前， Nfault 個(gè)驗(yàn)證者睡眠 X 毫秒，其中 X 被均勻地繪制在(0，3000)上。 從表 9.2 可 以看出，延遲與宕機(jī)故障的情況類似，盡管 TimeoutPropose 的增加有相反的效 果。由于并非所有驗(yàn)證者都有故障，所以小 TimeoutPropose 值可以允許快速地 跳過錯(cuò)誤的驗(yàn)證者。如果所有驗(yàn)證者都受到網(wǎng)絡(luò)延遲的影響，因?yàn)椴粫?huì)有無故障 的驗(yàn)證者跳過，則較大的 TimeoutPropose 值會(huì)減少延遲，并且將會(huì)提供更多的 時(shí)間來接收延遲的消息。

9.5 拜占庭故障(Byzantine Failures)

通過以下修改可以將更明確的拜占庭故障注入狀態(tài)機(jī):
·沖突提議(conflicting proposals):在提議時(shí)，拜占庭驗(yàn)證者會(huì)簽署兩個(gè)沖
突的提議并且廣播兩者，并附上預(yù)投票和預(yù)提交，以將其連接的對(duì)等點(diǎn)分為兩半。
·無 nil 投票(no nil votes):一個(gè)拜占庭驗(yàn)證者從不簽署一個(gè) nil 投票。
·簽署每個(gè)提議(sign every proposal):一旦一個(gè)拜占庭驗(yàn)證者看到一次提
議，它就為每個(gè)它看到的提議提交一個(gè)預(yù)投票和一個(gè)預(yù)提交。
綜上所述，這些行為明確地違反了雙簽名和鎖規(guī)則。然而，請(qǐng)注意，這種行 為主要是由相互矛盾的建議的傳播和最終它們其中之一的提交所主導(dǎo)的。更復(fù)雜的拜占庭戰(zhàn)略安排留給未來的工作。
從表 9.3 可以看出，盡管被注入了將導(dǎo)致許多系統(tǒng)立即徹底失敗的拜占庭故 障，但是，Tendermint 仍然保持著令人預(yù)期的延遲。由于這些故障與異步無關(guān)， 所以在 TimeoutPropose 上沒有實(shí)際的影響。性能也會(huì)隨著更大的驗(yàn)證集而消失， 這可能是處理拜占庭投票的簡單算法的結(jié)果。

9.6 相關(guān)工作

本章中的吞吐量實(shí)驗(yàn)建模在[67]中，其基準(zhǔn)是 PBFT 實(shí)現(xiàn)的性能和稱為
HoneyBadgerBFT 的新的隨機(jī) BFT 協(xié)議。在其結(jié)果中，PBFT 在四個(gè)節(jié)點(diǎn)上實(shí)現(xiàn)了 每秒超過 15000 次交易，但隨著節(jié)點(diǎn)數(shù)量的增加而呈指數(shù)下降，而 HoneyBadgerBFT 每秒大概達(dá)到 10000 到 15000 次交易。然而，HoneyBadgerBFT 中的區(qū)塊延遲要高得多，對(duì)于大小為 8，16 和 32 的驗(yàn)證器集，更接近 10 秒，對(duì) 于更大的驗(yàn)證集延遲甚至可能更大。
Jepsen 是研究一致性實(shí)現(xiàn)的一個(gè)著名工具，它通過模擬多種形式的網(wǎng)絡(luò)分區(qū) 來測(cè)試數(shù)據(jù)庫的一致性保證。用 Jepsen 測(cè)試 Tendermint 是留給未來的一個(gè)令人 興奮的領(lǐng)域的工作。
面對(duì)持續(xù)的拜占庭故障，作者并沒不了解任何的吞吐量實(shí)驗(yàn)，就像其他在這里描述的那樣。

9.7 結(jié)論

由作者和 Jae Kwon 編寫的 Tendermint 的實(shí)現(xiàn)輕松地在分布在全球范圍內(nèi)機(jī)器上的多至 64 個(gè)節(jié)點(diǎn)上達(dá)到了每秒數(shù)千筆的交易，延遲主要在 1 到 2 秒范圍內(nèi)。 這比其他解決方案更具競(jìng)爭力，尤其是在區(qū)塊鏈的目前狀態(tài)，例如，比特幣的上 限為每秒 7 筆交易。此外，我們的實(shí)現(xiàn)被證明對(duì)崩潰故障、消息延遲和故意的拜 占庭故障都很魯棒，能夠在每個(gè)場(chǎng)景中保持每秒超過 1000 個(gè)交易。

Chapter 10

相關(guān)工作
拜占庭一致性算法有著豐富的歷史，包括密碼學(xué)、分布式計(jì)算和經(jīng)濟(jì)學(xué)，但其部署在工業(yè)上的產(chǎn)品的社會(huì)經(jīng)濟(jì)背景直到最近才出現(xiàn)，至少在傳統(tǒng)的關(guān)鍵實(shí)時(shí) 系統(tǒng)之外，比如飛行器控制。一方面，比特幣的發(fā)明和“區(qū)塊鏈”一詞的產(chǎn)生， 使一種不受單一實(shí)體控制的分布式分類帳的概念得到普及，使用密碼學(xué)和一致的經(jīng)濟(jì)激勵(lì)措施來保護(hù)面對(duì)拜占庭故障的安全性。另一方面，服務(wù)器的持續(xù)商品化， 以“云(The Cloud)”的形式，以及 Raft 的發(fā)明，在主流開發(fā)者文化中推廣了 分布式計(jì)算，并再次把關(guān)注點(diǎn)引向分布式一致性算法使得成為在大規(guī)模部署中的協(xié)調(diào)中心。
在這個(gè)十字路口，有一系列的解決方案，通常適用于銀行和金融應(yīng)用，也適用于治理，物流和其他一般的協(xié)調(diào)形式，借鑒經(jīng)典學(xué)術(shù) BFT 修改的和現(xiàn)代化的各種方式。本章回顧了這些想法的歷史和多樣性，目的是提供一個(gè)豐富的背景來理 解區(qū)塊鏈現(xiàn)象。

10.1 開始

分布式算法首先出現(xiàn)在 19 世紀(jì)后期的電信和鐵路行業(yè)，試圖有效地處理傳輸中的多個(gè)并發(fā)消息流，或者是同一組軌道上的多個(gè)列車。 關(guān)于這個(gè)問題的學(xué)術(shù)研究似乎是由 Edsger Dijkstra 在互斥問題上的開創(chuàng)性工作和 Tony Hoare 在描述通信進(jìn)程的模型發(fā)起的。 在這段時(shí)間里，一系列有好記名字的并發(fā)性問題都得到了推廣，其中包括吸煙者的問題，吸煙者圍坐在一張桌子周圍，每個(gè)人都有不同的原料，并且必須成 功地卷一支完整的香煙;哲學(xué)家就餐問題，坐在桌子周圍的哲學(xué)家必須輪流吃飯 和思考，但每個(gè)人只能在他的鄰居都在思考時(shí)才能吃飯;兩軍問題或協(xié)同攻擊問 題，兩名將軍必須同時(shí)從遠(yuǎn)處協(xié)調(diào)進(jìn)攻一個(gè)敵人的城市。
這些問題將重點(diǎn)放在如如信號(hào)量、互斥和通信信道的同步原語上，并將為未來幾十年的許多改進(jìn)打下基礎(chǔ)。

10.1.1 故障(Faulty Things)

在 70 年代末，容錯(cuò)分布式計(jì)算有效地出現(xiàn)在了利用微處理器進(jìn)行飛機(jī)控制的努力中，從而產(chǎn)生了許多早期的系統(tǒng)。今天，它成為為了 NASA 對(duì) BFT 研究的標(biāo) 準(zhǔn)和商用飛機(jī)對(duì) BFT 系統(tǒng)，如 SAFEbus，的使用。
然而，許多系統(tǒng)不需要容忍拜占庭故障，因?yàn)樗鼈冊(cè)谑芸丨h(huán)境中運(yùn)行時(shí)，可 能不存在惡意行為，而且代碼是正確編寫的。在這種情況下，在像谷歌或 Amazon 這樣的大公司管理的數(shù)據(jù)中心中，容錯(cuò)計(jì)算被用來防御無論是網(wǎng)絡(luò)鏈接中斷，還 是服務(wù)器機(jī)架的電源故障，亦或是是硬盤報(bào)廢的各種錯(cuò)誤是很常見的。

10.1.2 時(shí)鐘(Clocks)

然而，在 Leslie Lamport 在他的“時(shí)間、時(shí)鐘和分布式系統(tǒng)中的事件排序”中引入了分布式一致性的問題時(shí)，才正式出現(xiàn)。在那項(xiàng)工作中，Lamport 演示了如 何從基于通信的因果關(guān)系的定義中產(chǎn)生局部的事件排序。也就是說，發(fā)生在在通 信事件之間的并發(fā)進(jìn)程中的事件，實(shí)際上發(fā)生在同一時(shí)間，因?yàn)樗鼈儾荒芟嗷ビ?響。因此，一個(gè)邏輯時(shí)鐘系統(tǒng)可以根據(jù)個(gè)人的順序進(jìn)程和消息在接收前發(fā)送的事 實(shí)來定義。然后，可以通過在局部排序之上分配任意但一致的總排序來完全排序 事件，例如，通過為系統(tǒng)中的每個(gè)進(jìn)程分配一個(gè)索引和排序事件，這些事件發(fā)生 在同一邏輯時(shí)間內(nèi)，由它們所發(fā)生的進(jìn)程的索引進(jìn)行。該算法相當(dāng)簡單，要求每 個(gè)進(jìn)程從彼此的進(jìn)程中獲得消息，以確定事件的順序。
Lamport 的工作確立了時(shí)間作為設(shè)計(jì)容錯(cuò)分布式系統(tǒng)的主要障礙，因?yàn)樵诘?理位置上同步時(shí)鐘需要信息的通信，而這些信息最終受到光的速度的限制。這個(gè)問題的形成與現(xiàn)代物理學(xué)的相對(duì)論有密切的聯(lián)系，其中參考系和觀察者相關(guān)，而 光的速度限制了信息傳播。

10.1.3 FLP

如第 2 章所述，設(shè)計(jì)一致性算法的主要因素之一是關(guān)于網(wǎng)絡(luò)和/或處理器同步的假設(shè)。同步網(wǎng)絡(luò)是指在固定的已知時(shí)間內(nèi)傳遞消息的網(wǎng)絡(luò)。類似地，同步處理 器的時(shí)鐘是保持在某些固定的、已知的相互運(yùn)轉(zhuǎn)數(shù)目之間的。在早期的一致性研 究中，盡管在異步和宕機(jī)故障之間的密切關(guān)系是很明顯的，這一區(qū)別并沒有被很 好的定義。Lamport 最初的協(xié)商一致算法能夠在異步環(huán)境中運(yùn)行，只要所有的消 息最終都可以從每個(gè)進(jìn)程中傳遞。然而，該算法顯然不是容錯(cuò)的，因?yàn)閮H僅一個(gè) 進(jìn)程的失敗就可以永久地終止該算法。
由 Fischer、Lynch 和證明了在異步環(huán)境中即使有個(gè)單獨(dú)的進(jìn)程失敗，決定性 分布式一致性的都是不可行的 Patterson，正式地提出了在一個(gè)單獨(dú)故障阻撓的 一致性協(xié)議基礎(chǔ)上的直覺。結(jié)果并不適用于同步上下文，因?yàn)殛P(guān)于網(wǎng)絡(luò)同步的假 設(shè)允許處理器使用超時(shí)來檢測(cè)故障，這樣如果某個(gè)進(jìn)程在給定的時(shí)間內(nèi)沒有響應(yīng)， 則假定它已經(jīng)崩潰。此外，這個(gè)結(jié)果只適用于決定性一致性協(xié)議，因?yàn)樗淖C明 依賴于網(wǎng)絡(luò)從一個(gè)二價(jià)狀態(tài)，即不是所有的進(jìn)程都持有相同的值，到一種單價(jià)的 狀態(tài)，即它們都持有相同的值，變成決定性的時(shí)刻。由于轉(zhuǎn)換點(diǎn)是時(shí)間上的一個(gè) 決定性的點(diǎn)，如果一個(gè)單獨(dú)的進(jìn)程恰好在那個(gè)時(shí)刻崩潰，那么一致性就會(huì)失敗。

10.1.4 常見幣(Common Coin)

FLP 的結(jié)果成為了分布式系統(tǒng)科學(xué)家的警鐘，在新興領(lǐng)域的心臟地帶建立了一個(gè)明顯的不可能的結(jié)果。之后，這種方法將推廣到更多不可能的結(jié)果，并將花 費(fèi)大量的學(xué)術(shù)研究來放松同步或決定論假設(shè)，以推導(dǎo)出繞過結(jié)果的算法。
特別地，在簡短的說明中，Ben Or 演示了包含簡單量的非確定性的算法可以 如何規(guī)避 FLP 結(jié)果。該算法容忍異步環(huán)境中多達(dá)一半進(jìn)程的故障。從本質(zhì)上說， 為了在單個(gè)比特的值上達(dá)成一致，如果一個(gè)進(jìn)程沒有從同一個(gè)價(jià)值的多數(shù)獲得投 票，那么它會(huì)隨機(jī)地改變它下一輪投票的值。隨著每個(gè)人都在改變價(jià)值觀，最終 一半以上都會(huì)投同樣值的票。由于與公有地翻轉(zhuǎn)硬幣以獲得一個(gè)共享的值的過程 相似，這種方法被認(rèn)為是一種常見幣(common coin)。
Ben Or 的 common coin 的問題在于，在異步情況下，算法需要在驗(yàn)證者數(shù)量 上以指數(shù)形式來表示。這被 Rabin 的后續(xù)行動(dòng)迅速糾正，Rabin 表示，如 Shamir 首創(chuàng)的，common coin 可以用秘密共享的方式構(gòu)建。該方法對(duì)于 BFT 也是有用的， 并且在后面的章節(jié)中將更詳細(xì)地討論。

10.1.5 交易處理(Transaction Processing)

同步開發(fā)容錯(cuò)一致性算法是第一個(gè)商業(yè)數(shù)據(jù)庫系統(tǒng)的出現(xiàn)形式。雖然他們沒有首先使用正在開發(fā)的一致性協(xié)議，但他們是在分布式計(jì)算和并發(fā)的不斷增長的 工作體之上構(gòu)建的。特別是 Jim Gray 的開創(chuàng)性工作，他將這個(gè)術(shù)語，交易 (transaction)，作為一個(gè)數(shù)據(jù)庫系統(tǒng)中的原子工作單元引入。也就是說，一個(gè) 交易要么完全應(yīng)用，要么根本不應(yīng)用。
Grey 還介紹了其他現(xiàn)代數(shù)據(jù)庫的經(jīng)典特征，如原子性(Atomicity)、一致性 (Consistency)、隔離性(Isolation)和持久性(Durability)的原則，也是交易
(transaction)概念的一部分和包裝，以及為了在被執(zhí)行前把交易日志記錄到磁 盤上以便從在交易執(zhí)行時(shí)才是的錯(cuò)誤中恢復(fù)而使用的 write-ahead-logs。
在分布式數(shù)據(jù)庫設(shè)置中，這種處理交易、原子性和一致性的工作導(dǎo)致了一系 列以原子提交(atomic commit)的概念為中心的數(shù)據(jù)庫復(fù)制的方法，其中交易 在所有機(jī)器上都以原子方式復(fù)制。這些方法被稱為兩階段提交 (two-phase-commit)，以及它的非區(qū)塊替代，三階段提交(three-phase-commit)。
兩階段提交和三階段提交協(xié)議都只在同步設(shè)置中工作，在那里可以檢測(cè)到宕機(jī)故障，并利用協(xié)調(diào)進(jìn)程作為協(xié)議的領(lǐng)導(dǎo)者。

10.1.6 廣播協(xié)議(Broadcast Protocols)

第 2 章介紹了兩個(gè)最重要的廣播協(xié)議，RBC 和 ABC。在[27]中提供了對(duì)該問題解決方案的分類和調(diào)查。

10.2 拜占庭(Byzantine)

許多容錯(cuò)協(xié)議只關(guān)注宕機(jī)故障，因?yàn)樗鼈兪亲畛Ｒ姷?#xff0c;而對(duì)于潛在的任意的問題，包括惡意軟件的行為，卻很少關(guān)注。這個(gè)更普遍的問題被稱為拜占庭容錯(cuò)。

10.2.1 拜占庭將軍(Byzantine Generals)

Lamport 在[78]中引入了拜占庭容錯(cuò)問題，但是在后來的論文中，因?yàn)槊鎸?duì)拜占庭軍隊(duì)協(xié)調(diào)攻擊敵方城市的問題做出分析，才給它起了名字。軍隊(duì)由多個(gè)部門 組成，每個(gè)部門由一個(gè)將軍領(lǐng)導(dǎo)。將軍之間的交流只能通過信使進(jìn)行。如果一名 或幾名將軍是叛徒，那么將軍如何達(dá)成共同的行動(dòng)計(jì)劃?
原始論文提供了能夠容忍 f 個(gè)拜占庭的故障的第一種證明，系統(tǒng)必須具有至 少 3f + 1 個(gè)節(jié)點(diǎn)。這一結(jié)果基礎(chǔ)上的直覺如圖 2.2 所示，并在第 2 章和第 3 章中 進(jìn)行了討論。這兩篇論文中提供了許多算法作為問題的第一個(gè)解決方案，盡管它 們被設(shè)計(jì)為僅在同步情況下工作，其中可以檢測(cè)到不存在消息。

10.2.2 隨機(jī)共識(shí)(Randomized Consensus)

異步拜占庭式一致性以 Ben Or 和 Rabin 介紹的 common coins 的形式出現(xiàn)了第一個(gè)解決方案。然而，這兩種解決方案都不能達(dá)到3f +1個(gè)機(jī)器中有f個(gè)故障的 最佳拜占庭容錯(cuò)能力。Ben Or 的解決方案需要 5f + 1 臺(tái)機(jī)器，而 Rabin 需要 10f + 1 臺(tái)機(jī)器。該解決方案被迭代地改進(jìn)，以達(dá)到以低的開銷優(yōu)化拜占庭。

10.2.3 局部同步(Partial Synchrony)

BFT 的下一個(gè)重大進(jìn)展是所謂的 DLS 一致性算法的形式，是以作者 Dwork，Lynch 和 Stockmeyer 命名的。DLS 的創(chuàng)新是定義稱為局部同步(partial synchrony) 的在同步和異步之間的中間地帶(middle ground)。局部同步的秘訣是假設(shè)以下 之一:
·消息保證在一定固定但未知的時(shí)間內(nèi)傳送。
·從未來的某未知的時(shí)間開始，消息保證在一段已知的時(shí)間內(nèi)交付。
DLS 算法通過一系列回合進(jìn)行，每一回合分為嘗試(trying)和鎖定釋放
(lock-release)階段。每一回合都有一個(gè)相應(yīng)的提議者，如果他們認(rèn)為提議者會(huì) 提出這個(gè)值，進(jìn)程可以在這一輪鎖定這個(gè)值。一回合開始于進(jìn)程廣播它們可以接 受的值。如果提議者從至少 N – f 個(gè)可接受該值的進(jìn)程中收到來信，它即可以提出這個(gè)值。任何接收提議值的進(jìn)程都應(yīng)該鎖定它，并發(fā)送一個(gè)確認(rèn)消息表示它已 經(jīng)這樣做了。如果提議者接收到 f + 1 個(gè)進(jìn)程的確認(rèn)，它就會(huì)提交該值。
對(duì)基本協(xié)議的變化進(jìn)行了不同的假設(shè)組合的討論，并提供了許多證明。然而，盡管它取得了成功，但 DLS 算法從未被廣泛用于 BFT。Tendermint 最初的設(shè)計(jì)是基于 DLS 的，更確切的說采用的是假設(shè)一個(gè)局部同步網(wǎng)絡(luò)但是全部同步處理器時(shí) 鐘的版本。實(shí)際上，由于使用了像網(wǎng)絡(luò)時(shí)間協(xié)議 Network Time Protocol (NTP)這 樣的協(xié)議，同步時(shí)鐘可能是一個(gè)合理的假設(shè)。然而，NTP 很容易受到一系列攻擊， 而且假設(shè)同步時(shí)鐘的協(xié)議從宕機(jī)故障中恢復(fù)得很慢。在 2015 年夏天，核心的 Tendermint 一致性協(xié)議被重新設(shè)計(jì)為更加完全的異步，如第 3 章所描述的，因此 它變得更加接近于另一種 BFT 算法，即實(shí)用拜占庭容錯(cuò) Practical Byzantine Fault Tolerance (PBFT)。

10.2.4 PBFT

PBFT 在 1999 年被引入，被廣泛認(rèn)為是第一個(gè)實(shí)用的 BFT 算法，適合在異步網(wǎng)絡(luò)中使用，盡管它實(shí)際上會(huì)產(chǎn)生微弱的可能會(huì)被一個(gè)謹(jǐn)慎的對(duì)手所違背的同步假設(shè)。PBFT 通過一系列視圖進(jìn)行，每個(gè)視圖都有一個(gè)提議者，稱為主視圖 (primary)，它是按回合順序選擇的。主視圖從客戶端接收請(qǐng)求，分配它們一個(gè)序列號(hào)，然后廣播一個(gè)簽署過的預(yù)準(zhǔn)備(pre-prepare)消息到其他包含視圖和 序列號(hào)的進(jìn)程。如果副本還沒有接受相同的視圖和序列號(hào)，它們就接受預(yù)準(zhǔn)備消 息，假設(shè)消息是針對(duì)當(dāng)前視圖并由正確的主視圖簽名的。
一旦一個(gè) pre-prepare 被接受，一個(gè)副本廣播一個(gè)簽署過的準(zhǔn)備消息(prepare message)。當(dāng)一個(gè)副本收到一個(gè)給定客戶端的具有相同視圖和序列號(hào)的請(qǐng)求的 2f 個(gè) prepare messages 時(shí)，這個(gè)副本就可以說是準(zhǔn)備好的了(prepared)。預(yù)準(zhǔn)備(pre-prepare)和準(zhǔn)備(prepare)的組合根據(jù)其序列號(hào)確保單個(gè)視圖中的請(qǐng)求的總序性(total order)。一旦一個(gè)副本已經(jīng)準(zhǔn)備好(prepared)，它會(huì)廣播一個(gè)簽署過的提交消息(commit message)，只要它被正確簽名并且視圖是正確的，它就被接受。當(dāng)一個(gè)副本接受提交消息時(shí)，它會(huì)針對(duì)狀態(tài)機(jī)運(yùn)行客戶端請(qǐng)求，并將結(jié)果返回給客戶端。
PBFT 采用了一種額外的機(jī)制，以方便在主視圖故障時(shí)幫助視圖更改。副本維持一個(gè)超時(shí)，每次接收新客戶端請(qǐng)求時(shí)重新啟動(dòng)，并在收到該請(qǐng)求的 pre-prepare 時(shí)終止。如果沒有收到 pre-prepare，則副本超時(shí)，并觸發(fā)視圖更改協(xié)議。視圖 的變化是微妙的，而且有些復(fù)雜，因?yàn)樗枰晥D應(yīng)該進(jìn)行更改的一致性，并且自從上次提交的所有客戶端請(qǐng)求都必須被引入新的視圖。
Tendermint 通過使用區(qū)塊并更換每個(gè)區(qū)塊的提議者來回避了這些問題，允許 使用與提交提議的區(qū)塊相同的機(jī)制來跳過一個(gè)提議者。此外，區(qū)塊的使用允許 Tendermint 在下一個(gè)區(qū)塊中包含上一個(gè)區(qū)塊預(yù)提交的消息集，消除了顯式提交消息的需要。

10.2.5 BFT 改進(jìn)

自從 PBFT 被發(fā)表以來，許多改進(jìn)方案已經(jīng)被提出來。其中一些關(guān)注在所謂的樂觀執(zhí)行(optimistic execution)上，這樣交易可以在它們被提交以前執(zhí)行以便 為客戶端提供低延遲和樂觀的回復(fù)。這些方法的問題在于，管理不一致性的責(zé)任 被轉(zhuǎn)移到客戶端，然而可能他們?cè)谝婚_始使用一致一致性協(xié)議(consistent consensus protocol)的原因就是為了避免這種責(zé)任?；蛘?#xff0c;在低故障情況下，這可能是一種有用的方法。這種現(xiàn)象在比特幣中被稱為 zero-conf 交易，并受到廣泛的警告，鑒于接受交易的不安全性已經(jīng)在它們之前提交了足夠的工作。
其他人則專注于同時(shí)運(yùn)行獨(dú)立交易的可能性，以實(shí)現(xiàn)更高的吞吐量。這是在區(qū)塊鏈社區(qū)中開始研究的方法，尤其是以太坊，以便產(chǎn)生可擴(kuò)展的區(qū)塊鏈結(jié)構(gòu)。

10.3 非拜占庭

與 BFT 算法并行，出現(xiàn)了一些非 BFT 算法，并且已經(jīng)建立了一些重要的高可用性互聯(lián)網(wǎng)服務(wù)。

10.3.1 Paxos

在一致性科學(xué)中，人們通常認(rèn)為，只有一種一致性算法，即 Paxos。這一方面說明了 Paxos 算法對(duì)該領(lǐng)域的重要性，另一方面是對(duì)共識(shí)一致性協(xié)議的普遍基礎(chǔ)的反射，這在每種情況下都是“類似 Paxos(Paxos-like)”的。
Lamport 在九十年代初期引入了 Paxos，盡管那篇文章直到將近十年以后才被 接受發(fā)表。許多人已經(jīng)指出，該算法實(shí)際上與上世紀(jì)八十年代末期出版的 Viewstamped Replication 極為相似，并且兩者都代表了相同協(xié)議的獨(dú)立發(fā)現(xiàn)。
這些協(xié)議與之前的 PBFT 非常相似，但只需要 2f + 1 臺(tái)機(jī)器就能夠容忍 f 個(gè)故障，如同它們不是 BFT。另一個(gè)類似的協(xié)議，Zookeeper 原子廣播協(xié)議(ZAB)是 為 Apache Zookeeper 分布式鍵值存儲(chǔ)開發(fā)的。在[99]中，每個(gè)算法的相似性和差 異性都有所闡釋。

10.3.2 Raft

引進(jìn) Raft 后，非 BFT 一致性科學(xué)得到了重大改進(jìn)，這一設(shè)計(jì)是從根本上可以理解的，通過用戶調(diào)查證明了它甚至比 Paxos 更容易理解。
Raft 在精神上類似于 Paxos 和 Viewstamped Replication，但它強(qiáng)調(diào)復(fù)制一個(gè)交易日志，而不是一個(gè)單個(gè)的比特，并引入隨機(jī)化來進(jìn)行更有效的領(lǐng)導(dǎo)者選舉。此 外，Raft 的安全性保障已經(jīng)使用 Coq 證明助手(Coq proof assistant)和一個(gè)在 Coq 上面構(gòu)建的以正式驗(yàn)證分布式系統(tǒng)的框架，Verdi，正式地證明過了。Verdi 將如何與基于過程演算的方法進(jìn)行比較還有待觀察。

10.4 區(qū)塊鏈(Blockchain)

本文的主要?jiǎng)訖C(jī)是介紹以比特幣形式出現(xiàn)的區(qū)塊鏈技術(shù)，和從此看到的許多迭代。 直到最近才有人成功地將區(qū)塊鏈置于經(jīng)典一致性科學(xué)的背景下。

10.4.1 比特幣(Bitcoin)

在[71]中介紹的，比特幣是第一個(gè)區(qū)塊鏈。它通過巧妙地利用經(jīng)濟(jì)學(xué)在公開的對(duì)抗設(shè)置中解決了原子廣播問題。特別地，交易順序是由解決部分哈希沖突的人 提出的，其中被散列的數(shù)據(jù)是交易的區(qū)塊。由于計(jì)算部分哈希沖突是昂貴的，需要在大空間中進(jìn)行強(qiáng)力搜索，所以這種努力通過每個(gè)區(qū)塊的發(fā)行貨幣，比特幣，進(jìn)行補(bǔ)貼。該協(xié)議已經(jīng)非常成功，貨幣已經(jīng)達(dá)到十億美元市值，原有的克隆產(chǎn)品市值也達(dá)數(shù)百萬。
然而，比特幣并非沒有問題。一些設(shè)計(jì)缺陷使應(yīng)用程序開發(fā)人員很麻煩也很難使用它。此外，一些學(xué)術(shù)著作也闡明了協(xié)議中的激勵(lì)不相容問題，削弱了人們對(duì)該協(xié)議的安全性的普遍假設(shè)。
很多方法被提出以改善比特幣，包括那些對(duì)部分哈希碰撞函數(shù)性質(zhì)的改變， 那些為了改善許多經(jīng)濟(jì)學(xué)和潛在性能的特征而對(duì)協(xié)議中領(lǐng)導(dǎo)者選舉的性質(zhì)的改 變以及那些旨在實(shí)現(xiàn)可伸縮性對(duì)協(xié)議進(jìn)行的討論。

10.4.2 以太坊(Ethereum)

以太坊由 Vitalik Buterin 引出，作為 Bitcoin 之后的一種加密貨幣的擴(kuò)散的解決方案，具有不同的功能。以太坊尋求更純粹的任務(wù):沒有功能。 相反，以太坊 提供了一個(gè)圖靈完整虛擬機(jī)(Turing complete virtual machine)，即以太坊虛擬 機(jī) Ethereum Virtual Machine (EVM)，用于在一致性之上執(zhí)行交易，并為用戶上傳 代碼到可以在將來的交易處理中執(zhí)行的 EVM 上提供了一種手段。所謂的智能合 同(smart contracts)使用強(qiáng)大的密碼學(xué)和 BFT 復(fù)制提供了在公共設(shè)置中自動(dòng)執(zhí) 行代碼的承諾。以太坊項(xiàng)目在迄今為止規(guī)模最大的眾基金(crowd-funds)之一 中取得了成功，超過了 1800 萬美元，而它的本地 token(用于支付交易執(zhí)行和 代碼上傳的費(fèi)用)的市值已經(jīng)達(dá)到 10 億美元。
Ethereum 目前使用一種叫做貪婪最終觀察子樹 Greedy Heaviest Observed Sub Tree (GHOST)的 Proof-of-Work 的修改形式，但正計(jì)劃轉(zhuǎn)向圍繞 Proof of Stake 建 模的更安全的經(jīng)濟(jì)一致性算法。

10.4.3 Proof-of-Stake

Proof-of-Stake (PoS)最開始作為在 PPCoin 中使用 Proo-of-Work 的一種替代方案被提出來。在 PoS，提議由那些可以證明網(wǎng)絡(luò)中硬幣獎(jiǎng)金的所有權(quán)的人提出并 投票。雖然消除了 PoW 的過高成本，但對(duì)于 PoS 的樸素實(shí)現(xiàn)很容易受到所謂的 “nothing-at-stake”的攻擊，在給定的高度，驗(yàn)證者可以在多個(gè)區(qū)塊上提議和投 票，從而導(dǎo)致了嚴(yán)重的安全性的違背，沒有任何激勵(lì)以收斂。雖然樸素 PoS 的問 題眾所周知，但許多流行的加密貨幣仍在使用它。
Nothing-at-stake 問題可以通過一個(gè)名為 slasher 的機(jī)制進(jìn)行糾正，即驗(yàn)證者必 須交一個(gè)安全保證金，以便有資格驗(yàn)證塊，這樣可以在發(fā)現(xiàn)驗(yàn)證者提議或投票支 持沖突區(qū)塊時(shí)削減它的押金。Tendermint 是這種方法的第一個(gè)實(shí)現(xiàn)，盡管其他的 BFT 算法也可以發(fā)揮作用。
10.4.4 超級(jí)賬本(HyperLedger) 比特幣、以太坊和其他加密貨幣的成功激發(fā)了社會(huì)越來越多元化的領(lǐng)域，包括監(jiān)管機(jī)構(gòu)、銀行家、企業(yè)高管、審計(jì)人員、客戶經(jīng)理、物流師等等。尤其是， Linux 基金會(huì)(Linux Foundation)最近發(fā)起的一個(gè)項(xiàng)目，由 IBM 和一家名為“數(shù) 字資產(chǎn)控股”(Digital Asset Holdings, DAH)的新成立的以區(qū)塊鏈為基礎(chǔ)的新公司， 旨在為工業(yè)應(yīng)用提供一個(gè)統(tǒng)一的區(qū)塊鏈架構(gòu)。這個(gè)項(xiàng)目被稱為“超級(jí)賬本” (HyperLedger)，以一個(gè)同名的公司命名，該公司提供了一個(gè)基于 PBFT 的區(qū)塊 鏈的基本實(shí)現(xiàn)，已經(jīng)被 DAH 收購。
對(duì) HyperLedger 倡議的兩項(xiàng)貢獻(xiàn)尤為相關(guān)。第一個(gè)是 JP Morgan 團(tuán)隊(duì)運(yùn)作的 Juno 和 Hopper 的合并。Juno 是 Tangaroa(一個(gè) BFT 版本的 Raft)的實(shí)現(xiàn)。Hopper 是一個(gè)新的虛擬機(jī)設(shè)計(jì)，基于線性邏輯(linear logic)和依賴類型系統(tǒng)(dependent type system)，它的目標(biāo)是為對(duì)于得出和證明關(guān)于系統(tǒng)狀態(tài)的陳述或者合同行為 而配備的一個(gè)正式的邏輯的智能合同系統(tǒng)提供一個(gè)執(zhí)行環(huán)境。Juno 和 Hopper 都 是用 Haskell 寫的。
另一個(gè)項(xiàng)目是 IBM 的 OpenBlockchain，一個(gè)由 Go 編寫的基于 PBFT 的區(qū)塊鏈，它的應(yīng)用程序狀態(tài)支持任意 docker 容器的部署。由于任意 docker 容器可能包含非決定性，它們的 PBFT 實(shí)現(xiàn)用在可能的非決定性執(zhí)行的情況下保護(hù)安全性的額 外步驟來修改。
IBM 的另一個(gè)相關(guān)貢獻(xiàn)是最近的一篇評(píng)論文章，類似于本章。

10.4.5 HoneyBadgerBFT

盡管在異步環(huán)境中運(yùn)行良好，所有與 Paxos-like 的一致性協(xié)議，包括 Raft、PBFT 和 Tendermint，都不是完全異步的。這是因?yàn)槊總€(gè)協(xié)議都在協(xié)議的某個(gè)地方使用超時(shí)，通常是為了檢測(cè)故障領(lǐng)導(dǎo)者。另一方面，像 common coin 這樣的隨機(jī)一致 性協(xié)議提供了在完全異步環(huán)境中，沒有超時(shí)的解決方案。
所有一致性協(xié)議都以某種方式依賴于最終消息的傳遞。異步的假設(shè)簡單地指 出，沒有消息被傳遞的上限。大多數(shù)時(shí)候，網(wǎng)絡(luò)行為是同步的，在某種意義上，大多數(shù)消息是在一定范圍內(nèi)傳遞的。完全異步協(xié)議與有超時(shí)協(xié)議之間的差異在于， 當(dāng)網(wǎng)絡(luò)同步運(yùn)行時(shí)，異步協(xié)議總能取得進(jìn)展。這一點(diǎn)在[67]中清楚地顯示，其中引 入了 HoneyBadgerBFT，第一個(gè)完全異步區(qū)塊鏈設(shè)計(jì)，基于 common coin 一致性。
對(duì)網(wǎng)絡(luò)進(jìn)行任意控制的對(duì)手以及一次可以使得任何一個(gè)節(jié)點(diǎn)崩潰的能力可能導(dǎo)致 PBFT 任意長時(shí)間停止。這可以通過在網(wǎng)絡(luò)同步時(shí)崩潰當(dāng)前的主視圖/提議者 /領(lǐng)導(dǎo)者，并將其恢復(fù)為異步的時(shí)間段來完成。網(wǎng)絡(luò)仍然最終傳遞消息，具有一 些平均的同步性，但是精確的時(shí)序可以停止所有的系統(tǒng)進(jìn)程。在 PBFT 的直接實(shí) 驗(yàn)在[67]中，并且與 Tendermint 工作類似。
HoneyBadgerBFT 利用一系列加密技術(shù)，包括秘密共享，擦除編碼和閾值簽名， 以設(shè)計(jì)出高性能異步 BFT 一致性協(xié)議來克服這種困難，因?yàn)樗峭耆珶o領(lǐng)導(dǎo)的而 導(dǎo)致的沒有任何同步的假設(shè)。然而，它需要一個(gè)受信任的經(jīng)銷商(dealer)進(jìn)行 初始設(shè)置和驗(yàn)證者變更，并且它依賴于尚未經(jīng)得起時(shí)間考驗(yàn)的某些問題的難度的 相對(duì)新的加密假設(shè)。

10.5 結(jié)論

Tendermint 出現(xiàn)并補(bǔ)充了豐富的一致性科學(xué)的歷史，涵蓋了同步和容錯(cuò)假設(shè)的范圍。 區(qū)塊鏈和 Raft 的發(fā)明重新啟動(dòng)了一致性的研究，并產(chǎn)生了新一代通過 互聯(lián)網(wǎng)協(xié)調(diào)的協(xié)議和軟件。

Chapter 11

總結(jié)
拜占庭容錯(cuò)一致性提供了一個(gè)豐富的基礎(chǔ)，用來構(gòu)建不依賴于集中式、可信任方的以及可能被社會(huì)用來管理社會(huì)經(jīng)濟(jì)基礎(chǔ)設(shè)施的關(guān)鍵組成部分的服務(wù)。本文中提出的 Tendermint，旨在滿足這些系統(tǒng)的需求，并以可理解的安全性和易于高 性能的方式以及允許任意系統(tǒng)按一致性協(xié)議和最少的無關(guān)事進(jìn)行交易來進(jìn)行設(shè)計(jì)。
在部署分布式一致性系統(tǒng)時(shí)，需要謹(jǐn)慎考慮，尤其是在沒有中央授權(quán)的情況下，在危機(jī)發(fā)生時(shí)調(diào)解潛在的爭端并重置系統(tǒng)。Tendermint 試圖通過明確的治理 模塊和問責(zé)保障制度來解決這些問題，使 Tendermint 部署融入到現(xiàn)代法律和經(jīng) 濟(jì)基礎(chǔ)設(shè)施中。
現(xiàn)在仍然有許多工作要做。這其中包含算法保證的正式驗(yàn)證，性能優(yōu)化，以及架構(gòu)變更以使得系統(tǒng)用額外的機(jī)器增加容量。而且，當(dāng)然，還有許多許多 TMSP 的應(yīng)用要構(gòu)建。
我們希望本文更好的解釋了在分布式一致性算法和區(qū)塊鏈架構(gòu)中的問題，并且啟發(fā)其他人建立一些更好的東西。

總結(jié)

以上是生活随笔為你收集整理的Tendermint: Byzantine Fault Tolerance in the Age of Blockchains的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。