區(qū)塊鏈范式中的安全狀態(tài)機(jī)復(fù)制算法Tendermint介紹

Tendermint共識(shí)算法和用于原子廣播（ atomic broadcast）的相關(guān)區(qū)塊鏈。拜占庭容錯(cuò)共識(shí)問(wèn)題將被詳細(xì)討論，并且Tendermint共識(shí)的一個(gè)正式說(shuō)明將以π-calculus的形式給出。Tendermint區(qū)塊鏈已經(jīng)被非正式地證明為滿足原子廣播。將來(lái)我們將以進(jìn)程演進(jìn)的方式來(lái)描述完整的區(qū)塊鏈協(xié)議，并證明相關(guān)特性。區(qū)塊鏈時(shí)代的拜占庭容錯(cuò)：Tendermint（一）

Tendermint綜述

Tendermint是區(qū)塊鏈范式中的一個(gè)安全的狀態(tài)機(jī)復(fù)制算法。其算法形態(tài)為BFT-ABC，并且附加責(zé)任制，便于驗(yàn)證拜占庭節(jié)點(diǎn)的不誠(chéng)實(shí)行為。

Tendermint算法給每個(gè)區(qū)塊賦予一個(gè)增量索引或者高度（height），在某一高度中只存在一個(gè)有效的區(qū)塊，區(qū)塊鏈從高度為0的創(chuàng)世紀(jì)塊開(kāi)始，由一個(gè)驗(yàn)證者集合投票產(chǎn)生下一個(gè)區(qū)塊，其中每一個(gè)驗(yàn)證者由各自的公鑰標(biāo)識(shí)。每一個(gè)驗(yàn)證者需要維護(hù)一份完整的復(fù)制狀態(tài)的拷貝。在投票產(chǎn)生某一高度的區(qū)塊的過(guò)程中，在正式提交（commit）某一高度的區(qū)塊之前，至少需要經(jīng)過(guò)一輪（round）投票（vote）來(lái)達(dá)成共識(shí)。每一輪都會(huì)通過(guò)round robin的方法產(chǎn)生一個(gè)提議者（proposer），該提議者在當(dāng)輪以廣播的形式提出一個(gè)提議（proposal），提議經(jīng)過(guò)驗(yàn)證者的集體投票，來(lái)決定是否最終提交該區(qū)塊或者進(jìn)入下一輪。在提議的區(qū)塊真正被提交（commit）之前，驗(yàn)證者們需要進(jìn)行兩輪投票（pre-vote & pre-commit）， 通過(guò)一個(gè)簡(jiǎn)單的鎖機(jī)制用來(lái)阻止少于總數(shù)1/3的拜占庭節(jié)點(diǎn)攻擊。由于Tendermint網(wǎng)絡(luò)的不同時(shí)性（asynchrony），當(dāng)拜占庭節(jié)點(diǎn)超過(guò)總數(shù)的1/3，網(wǎng)絡(luò)存在癱瘓的可能性。

注意到，tendermint的多輪投票機(jī)制的核心是共識(shí)算法。每一個(gè)區(qū)塊包含一些元數(shù)據(jù)（metadata），稱(chēng)作區(qū)塊頭（header）。區(qū)塊頭里包含本區(qū)塊的高度，提議時(shí)間，本區(qū)塊所有交易的梅克爾根哈希值。

共識(shí)

共識(shí)算法可以大致分為以下幾部分：

提議（Proposals）：在每一輪（round）中，新區(qū)塊的提議者必須是有效的，并且告訴（gossiped）其他驗(yàn)證者。如果在一定時(shí)間內(nèi)沒(méi)有收到當(dāng)輪提議（proposal），當(dāng)前提議者將被后面的提議者接替。

投票（Votes）：兩階段的投票基于優(yōu)化的拜占庭容錯(cuò)。它們分別被稱(chēng)作預(yù)投票（pre-vote）和預(yù)提交（pre-commit）。對(duì)于同一個(gè)區(qū)塊同一輪如果存在超過(guò)2/3的預(yù)提交（pre-commit）則對(duì)應(yīng)產(chǎn)生一個(gè)提交（commit）。

鎖（Locks）：在拜占庭節(jié)點(diǎn)數(shù)少于節(jié)點(diǎn)總數(shù)的1/3的情況下，Tendermint中的鎖機(jī)制可以確保沒(méi)有兩個(gè)驗(yàn)證者在同一高度提交（commit）了兩個(gè)不同的區(qū)塊。鎖機(jī)制確保了在當(dāng)前高度驗(yàn)證者的下一輪預(yù)投票或者預(yù)提交依賴(lài)于這一輪的預(yù)投票或者預(yù)提交。

為了應(yīng)對(duì)單個(gè)拜占庭故障節(jié)點(diǎn)，Tendermint網(wǎng)絡(luò)至少需要包括4個(gè)驗(yàn)證者。每個(gè)驗(yàn)證者擁有一對(duì)非對(duì)稱(chēng)密鑰，其中私鑰用來(lái)進(jìn)行數(shù)字簽名，公鑰用來(lái)標(biāo)識(shí)自己的身份ID。驗(yàn)證者們從公共的初始狀態(tài)開(kāi)始，初始狀態(tài)包含了一份驗(yàn)證者列表。所有的提議和投票都需要各自的私鑰簽名，便于其他驗(yàn)證者進(jìn)行公鑰驗(yàn)證。

驗(yàn)證人在發(fā)起提議（proposal）步驟之后，當(dāng)且僅當(dāng)收到其它驗(yàn)證人超過(guò)三分之二（+2/3）的投票后才會(huì)進(jìn)一步推進(jìn)流程。虛線箭頭表示進(jìn)入下一個(gè)區(qū)塊高度共識(shí)流程的原子廣播。

共識(shí)開(kāi)始于第0輪，第一個(gè)提議者（proposer）是區(qū)塊鏈頭里驗(yàn)證者列表里的第一個(gè)驗(yàn)證者。每一輪最終要么完成了一個(gè)提交（commit），要么直接進(jìn)入當(dāng)前高度的下一輪，每一輪都會(huì)產(chǎn)生一個(gè)新的提議者。

與其他選舉（leader election ）算法不同，Tendermint每一輪都會(huì)產(chǎn)生一個(gè)新的提議者（proposer），驗(yàn)證者投票決定是否進(jìn)入下一輪，這與接受提議的流程類(lèi)似。

每輪的開(kāi)始對(duì)同步有弱的依賴(lài)性。每一輪開(kāi)始期間，存在一個(gè)用來(lái)計(jì)時(shí)的本地同步時(shí)鐘，如果驗(yàn)證者在TimeoutPropose時(shí)間內(nèi)沒(méi)有收到提議，驗(yàn)證者將參與投票來(lái)決定是否跳過(guò)當(dāng)前提交者。TimeoutPropose會(huì)隨著輪數(shù)的增加而增加。

每輪收到提議以后，進(jìn)入完全異步模式。之后驗(yàn)證者的每一個(gè)網(wǎng)絡(luò)決定需要得到2/3驗(yàn)證者以上的同意。這樣降低了對(duì)同步時(shí)鐘的依賴(lài)或者網(wǎng)絡(luò)的延遲。但是這也意味著如果得不到1/3以上驗(yàn)證者的響應(yīng)，整個(gè)網(wǎng)絡(luò)將癱瘓。

簡(jiǎn)言之，每輪，開(kāi)始提議弱同步，之后投票完全異步。

為了增強(qiáng)Tendermint共識(shí)網(wǎng)絡(luò)的安全性，引入了少量的鎖定規(guī)則（locking rules）來(lái)迫使驗(yàn)證者自證其投票的合法性。盡管我們不需要實(shí)時(shí)廣播他們的合法證明，但是我們確實(shí)期望驗(yàn)證者們保存相關(guān)數(shù)據(jù)。這樣當(dāng)網(wǎng)絡(luò)被拜占庭故障節(jié)點(diǎn)癱瘓時(shí)，其可以存留為相關(guān)證據(jù)。這個(gè)問(wèn)責(zé)機(jī)制確保在網(wǎng)絡(luò)故障（例如PBFT）的時(shí)候Tendermint具有一個(gè)更健壯的擔(dān)保（guarantees）。

驗(yàn)證者使用一組不同的消息（messages）來(lái)管理區(qū)塊鏈，應(yīng)用程序狀態(tài)，p2p網(wǎng)絡(luò)和共識(shí)。其中，核心的共識(shí)算法包含兩類(lèi)消息：

ProposalMsg： 對(duì)應(yīng)某一高度及某一輪數(shù)的區(qū)塊的提議（proposal），該提議已經(jīng)由提議者簽名

VoteMsg： 對(duì)某一提議的簽名投票

一。 提議

每輪開(kāi)始于一個(gè)提議（proposal），提議者從內(nèi)存池（Mempool）選取一批交易進(jìn)而構(gòu)成了一個(gè)區(qū)塊，該區(qū)塊隨后被嵌套在ProposalMsg中，最后提議者廣播（broadcast）ProposalMsg。如果這個(gè)提議者是拜占庭節(jié)點(diǎn)，他可能向不同的驗(yàn)證者廣播不同的ProposalMsg。

提議者通過(guò)一個(gè)簡(jiǎn)單并且相對(duì)固定的的roubd robin輪流坐莊，所以每一輪只有一個(gè)有效且被所有驗(yàn)證者公認(rèn)的提議者。如果驗(yàn)證者收到了之前更低輪次的提議或者提議來(lái)自于非法的提議者，該提議將被拒絕。

提議者的輪流坐莊對(duì)于拜占庭容錯(cuò)是必要的。比如，對(duì)于raft算法，如果選舉出來(lái)的leader是拜占庭，并且leader與其他節(jié)點(diǎn)網(wǎng)絡(luò)連接狀態(tài)良好，該leader可以完全控制整個(gè)網(wǎng)絡(luò)，網(wǎng)絡(luò)節(jié)點(diǎn)的安全和正常運(yùn)轉(zhuǎn)將無(wú)從得到保障。Tendermint通過(guò)投票和鎖的機(jī)制（voting and locking mechanisms ）確保了系統(tǒng)的安全性。如果一個(gè)提議者在限定時(shí)間內(nèi)沒(méi)有處理任何交易，排在其后的提議者將會(huì)接替他。更有趣的是驗(yàn)證者能通過(guò)治理模塊投票來(lái)移出或者替換拜占庭驗(yàn)證者。

二。 投票

一旦驗(yàn)證者從網(wǎng)絡(luò)中收到了一份完整的提議（proposal ），他對(duì)該提議進(jìn)行預(yù)投票（pre-vote）簽名，并且廣播到網(wǎng)絡(luò)中。如果驗(yàn)證者在ProposalTimeout時(shí)間內(nèi)沒(méi)有接收到一個(gè)有效的提議，其對(duì)該提議的預(yù)投票為空（nil）。

在存在拜占庭節(jié)點(diǎn)的異步環(huán)境中，單階投票，即每個(gè)驗(yàn)證者對(duì)每個(gè)提議只投一次，不能足以確保整個(gè)系統(tǒng)的安全。本質(zhì)上，因?yàn)轵?yàn)證者可能做出一些不誠(chéng)實(shí)的行為，并且消息的到達(dá)時(shí)間沒(méi)有任何保障，一個(gè)不誠(chéng)實(shí)的驗(yàn)證者可以與其他驗(yàn)證者進(jìn)行協(xié)作來(lái)提交（commit）一個(gè)區(qū)塊，然而其他沒(méi)有看到這個(gè)提交區(qū)塊的驗(yàn)證者進(jìn)入了新的一輪，并提交（commit）了一個(gè)不同的區(qū)塊。

一個(gè)單階的投票允許驗(yàn)證者互相溝通他們知道的關(guān)于該提議的信息。但是為了容忍拜占庭故障，他們也需要互相告訴對(duì)方他們自己了解到的其他驗(yàn)證者聲稱(chēng)了解到的關(guān)于該提交的信息。換句話說(shuō)，二階段提交確保了足夠的驗(yàn)證者見(jiàn)證了第一階段的結(jié)果。

對(duì)于某個(gè)區(qū)塊的非空預(yù)投票是為網(wǎng)絡(luò)提交（commit）區(qū)塊已做好準(zhǔn)備的投票?？疹A(yù)投票是為網(wǎng)絡(luò)直接進(jìn)入下一輪的投票。在理想的一輪中，超過(guò)2/3的驗(yàn)證者為該提議進(jìn)行了預(yù)投票。在任意一輪中，區(qū)塊具有的超過(guò)2/3的預(yù)投票被稱(chēng)作一個(gè)波爾卡（polka）。超過(guò)2/3的空預(yù)投票成為空波爾卡（nil-polka）。

當(dāng)一個(gè)驗(yàn)證者收到了一個(gè)波爾卡（polka），他接受到了一個(gè)信號(hào)，即網(wǎng)絡(luò)準(zhǔn)備提交該區(qū)塊，作為一個(gè)驗(yàn)證者簽名并且廣播預(yù)提交（pre-commit）的背書(shū)。有時(shí)，由于網(wǎng)絡(luò)的不同時(shí)性，驗(yàn)證者可能沒(méi)有收到對(duì)應(yīng)的波爾卡或者波爾卡根本就不存在。在這種情況下，驗(yàn)證者沒(méi)有對(duì)應(yīng)的波爾卡為這個(gè)預(yù)提交背書(shū)，此時(shí)預(yù)提交為空。也就是說(shuō)，在沒(méi)有收到波爾卡背書(shū)的情況下，簽名一個(gè)預(yù)提交被看作是一個(gè)惡意行為。

預(yù)提交（pre-commit）是關(guān)于提交（commit）一個(gè)塊的投票?？疹A(yù)提交則投票進(jìn)入到下一輪。如果驗(yàn)證者收到2/3以上驗(yàn)證者的預(yù)提交，則其在本地提交該塊，計(jì)算結(jié)果狀態(tài)，并移動(dòng)到下一高度的第0輪。如果驗(yàn)證者接收到超過(guò)2/3的空預(yù)提交，則投票進(jìn)入下一輪。

三。 鎖

多輪投票的安全問(wèn)題是棘手的，必須避免同一高度不同輪數(shù)分別提交兩個(gè)不同區(qū)塊的情形。在Tendermint中，這個(gè)問(wèn)題可以通過(guò)鎖機(jī)制（locking mechanism）得到解決。鎖機(jī)制的大致定位在波爾卡附近。本質(zhì)上，預(yù)提交必須有一個(gè)波爾卡為其背書(shū)，驗(yàn)證者被鎖定在其最近預(yù)提交（pre-commit）的區(qū)塊上。

鎖定規(guī)則：

預(yù)投票鎖（Prevote-the-Lock）：驗(yàn)證者只能預(yù)投票（pre-vote）他們被鎖定的區(qū)塊。這樣就阻止驗(yàn)證者在上一輪中預(yù)提交（pre-commit）一個(gè)區(qū)塊，之后又預(yù)投票了下一輪的另一個(gè)區(qū)塊。

波爾卡解鎖（Unlock-on-Polka ）：驗(yàn)證者只有在看到更高一輪（相對(duì)于其當(dāng)前被鎖定區(qū)塊的輪數(shù)）的波爾卡之后才能釋放該鎖。這樣就允許驗(yàn)證者解鎖，如果他們預(yù)提交了某個(gè)區(qū)塊，但是這個(gè)區(qū)塊網(wǎng)絡(luò)的剩余節(jié)點(diǎn)不想提交，這樣就保護(hù)了整個(gè)網(wǎng)絡(luò)的運(yùn)轉(zhuǎn)，并且這樣做并沒(méi)有損害網(wǎng)絡(luò)安全性。

簡(jiǎn)單來(lái)說(shuō)，驗(yàn)證者可以被看作鎖在任意高度-1輪的nil-block上，所以波爾卡解鎖意味著驗(yàn)證者不能預(yù)提交一個(gè)新高度的區(qū)塊直到他們看見(jiàn)一個(gè)波爾卡。

這些規(guī)則可以以例子的形式被更直觀的理解?？紤]4個(gè)驗(yàn)證者，A，B，C，D，假設(shè)有一個(gè)第R輪關(guān)于blockX的提議?，F(xiàn)在假設(shè)blockX已經(jīng)有一個(gè)波爾卡，但是A看不見(jiàn)它，預(yù)提交（pre-commit）為空，然而其他人對(duì)blockX進(jìn)行了預(yù)提交。進(jìn)一步假設(shè)只有D看見(jiàn)了所有的預(yù)提交，然而其他人并沒(méi)有看見(jiàn)D的預(yù)提交（他們只看見(jiàn)他們的預(yù)提交和A的空預(yù)提交）。D現(xiàn)在將要提交（commit）這個(gè)區(qū)塊，然而其他人進(jìn)入到R+1輪。由于任何驗(yàn)證者都可能是新的提議者，如果他們提議并投票了一個(gè)新的區(qū)塊blockY，他們可能提交這個(gè)區(qū)塊?？墒荄已經(jīng)提交了bockX，因此損害了系統(tǒng)的安全性。注意，這里并沒(méi)有任何拜占庭行為，僅僅是不同時(shí)性。

鎖定解決了這個(gè)問(wèn)題通過(guò)強(qiáng)迫驗(yàn)證者粘附在他們預(yù)提交（pre-commit）的區(qū)塊上，因?yàn)槠渌尿?yàn)證者可能居于這個(gè)預(yù)提交進(jìn)行了提交（如上例中的D）。本質(zhì)上，在任何一個(gè)節(jié)點(diǎn)一旦存在超過(guò)2/3預(yù)提交（pre-commit），整個(gè)網(wǎng)絡(luò)被鎖定在這個(gè)區(qū)塊上，也就是說(shuō)在下一輪中無(wú)法產(chǎn)生一個(gè)不同塊的波爾卡。這是預(yù)投票鎖的直接動(dòng)機(jī)。

當(dāng)然這里必須有相應(yīng)的解鎖方式。假設(shè)在某一輪中，A和B預(yù)提交（pre-commit）了blockX，與此同時(shí)C和D的預(yù)提交為空。因此所有的驗(yàn)證者進(jìn)入到下一輪，預(yù)提議（pre-vote）blockY。假設(shè)A是拜占庭，為blockY也進(jìn)行了預(yù)投票（不考慮其被鎖在blockX上），導(dǎo)致了一個(gè)波爾卡。假設(shè)B并沒(méi)有看見(jiàn)這個(gè)波爾卡，預(yù)提交為空，此時(shí)A下線，C，D預(yù)提交bolckY。他們進(jìn)入到下一輪，但是B仍然被鎖定在blockX上，C和D被鎖定在blockY上。這時(shí)因?yàn)锳下線了，他們將永遠(yuǎn)得不到一個(gè)波爾卡。因此即使在拜占庭節(jié)點(diǎn)少于1/3的情況下，這里網(wǎng)絡(luò)的正常運(yùn)轉(zhuǎn)仍然受到了影響。

解鎖的條件是1個(gè)波爾卡。一旦B看見(jiàn)了blockY的波爾卡（用來(lái)為C和D的關(guān)于blockY的預(yù)提交背書(shū)），他應(yīng)當(dāng)能夠解鎖并預(yù)提交（pre-commit）blockY。這是波爾卡解鎖的動(dòng)機(jī)，其允許驗(yàn)證者在看見(jiàn)更高輪數(shù)波爾卡的時(shí)候解鎖并且提交對(duì)應(yīng)的新區(qū)塊。

區(qū)塊鏈

Tendermint對(duì)交易按批或塊進(jìn)行處理。區(qū)塊之間通過(guò)加密哈哈希算法鏈成一個(gè)完整的區(qū)塊鏈。區(qū)塊鏈包括經(jīng)過(guò)排序的交易日志和驗(yàn)證者提交的相關(guān)證據(jù)。

為什么是區(qū)塊？

共識(shí)算法一次提交若干個(gè)交易（transactions）。正如在第二章提到的那樣。從分批原子廣播（batched atomic broadcast）的角度來(lái)看待這個(gè)問(wèn)題，對(duì)應(yīng)兩個(gè)主要的優(yōu)化，其給了我們更多的吞吐量和容錯(cuò)能力：

帶寬優(yōu)化：因?yàn)槊恳淮翁峤唬╟ommit）需要驗(yàn)證者之間的兩輪通訊，以塊為單位交易的批處理，平攤了提交的成本在該區(qū)塊中的所有交易上。

完整性優(yōu)化：區(qū)塊的哈希鏈形成了一個(gè)不可篡改的數(shù)據(jù)結(jié)構(gòu)，跟git倉(cāng)庫(kù)很像，具備歷史任意點(diǎn)的子狀態(tài)認(rèn)證檢查的能力。

區(qū)塊也引起了另外一個(gè)效應(yīng)，看上去更微妙，但是可能更重要。他們?cè)黾恿藛蝹€(gè)交易的最小延遲到區(qū)塊的最小延遲，對(duì)于Tendermint來(lái)說(shuō)在數(shù)百毫秒到數(shù)秒量級(jí)。傳統(tǒng)的序列化數(shù)據(jù)庫(kù)系統(tǒng)提供了提交延遲在毫秒到數(shù)百毫秒量級(jí)。他們的低延遲是因?yàn)檫@些數(shù)據(jù)庫(kù)不是拜占庭容錯(cuò)的，只需要一輪通訊而不是兩輪和來(lái)自于1/2而不是2/3節(jié)點(diǎn)的響應(yīng)。然而，與其他具有快速提交時(shí)間（commit times）的選舉算法不同，Tendermint提供了一個(gè)更常規(guī)的脈沖（pulse ），在節(jié)點(diǎn)故障和網(wǎng)絡(luò)不同時(shí)方面對(duì)整個(gè)網(wǎng)絡(luò)的狀態(tài)具有更好的響應(yīng)度。

脈沖在通訊自治系統(tǒng)一致性方面的角色現(xiàn)在并不明朗，但是由此引發(fā)的延遲在金融市場(chǎng)中是具有前景的。

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

區(qū)塊的目的是打包一批交易，并且鏈接到前面一個(gè)塊。鏈接包含兩種形式：前面一個(gè)區(qū)塊的哈希和前面區(qū)塊的預(yù)提交的集合，其也被稱(chēng)作LastCommit。因此一個(gè)區(qū)塊由三部分構(gòu)成：區(qū)塊頭，交易列表和Lastcommit。

安全性

這里我們簡(jiǎn)要地證明一下Tendermint滿足原子廣播。原子廣播被定義為滿足以下條件：

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

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

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

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

注意到， 如果把m看作一個(gè)區(qū)塊，Tendermint并不滿足有效性，因?yàn)椴⒉荒鼙ＷC提議的區(qū)塊最會(huì)會(huì)被提交，因?yàn)轵?yàn)證者可能進(jìn)入到新的一輪，并提交一個(gè)不同的區(qū)塊。

如果我們把m看作某一區(qū)塊里的一批交易，那么我們能夠滿足有效性通過(guò)驗(yàn)證者重新提議同一批交易直至交易最終被提交。

為了滿足完整性的第一部分，我們必須引入額外的規(guī)則來(lái)禁止一個(gè)合法的驗(yàn)證者提議或者預(yù)提交一個(gè)區(qū)塊，其中這個(gè)區(qū)塊包含的這批交易已經(jīng)被提交過(guò)。幸運(yùn)的是，交易可以被梅克爾根索引，在提議和預(yù)提交以前可以進(jìn)行相關(guān)的查找來(lái)濾除已經(jīng)提交的交易。

或者我們可以把m當(dāng)成一個(gè)交易（transaction），通過(guò)引入內(nèi)存池的持久屬性，可以滿足有效性，即，交易可以駐留在內(nèi)存池中直到它被提交。然而為了滿足完整性的第一部分，我們必須依賴(lài)應(yīng)用程序狀態(tài)（application state）來(lái)制定一些針對(duì)交易的規(guī)則，這樣一個(gè)給定的交易只能進(jìn)行一次。例如，可以通過(guò)基于賬戶的序列號(hào)，正如在以太坊中的那樣?；蛘弑４嬉环菸词褂觅Y源的列表，每一個(gè)資源只能被使用一次，正如在比特幣中使用的那樣。因?yàn)橛卸喾N方法，Tendermint本身并不保證消息只傳達(dá)一次，但是允許應(yīng)用開(kāi)發(fā)者來(lái)指定相關(guān)特性。完整性的第二部分顯而易見(jiàn)，因?yàn)橹挥姓_的提議者提議的區(qū)塊中的交易才能被提交。

為了證明Tendermint滿足“總的順序”，我們引入了一個(gè)新的特性，狀態(tài)機(jī)安全性（state machine safety），并且可以證明滿足狀態(tài)機(jī)安全性的協(xié)議必定滿足“一致性”和“總的順序”。所謂的狀態(tài)機(jī)安全是指如果一個(gè)正確的驗(yàn)證者在高度H提交了一個(gè)區(qū)塊，沒(méi)有其他的驗(yàn)證者在同一高度提交一個(gè)不同的區(qū)塊?？紤]到所有的消息最終被接收，這個(gè)立刻暗示了一致性，因?yàn)槿绻粋€(gè)正確的驗(yàn)證者在高度H提交了一個(gè)區(qū)塊B，包含了交易m，所有其他的正確的驗(yàn)證者不能提交其他的區(qū)塊，因此最終提交了區(qū)塊B，傳達(dá)了消息m。

現(xiàn)在，我們需要證明狀態(tài)機(jī)安全滿足“總的順序”，并且Tendermint滿足狀態(tài)機(jī)安全。為了證明前者，考慮兩個(gè)消息m和m’分別由驗(yàn)證者p和q發(fā)出。狀態(tài)機(jī)安全確保p發(fā)出消息m在高度Hm當(dāng)且僅當(dāng)q發(fā)出消息m在高度Hm，并且p發(fā)出消息m‘在高度Hm’當(dāng)且僅當(dāng)q發(fā)出消息m‘在高度Hm’。不失一般性，因?yàn)楦叨仁菄?yán)格遞增的，假設(shè)Hm

最后，為了證明當(dāng)拜占庭節(jié)點(diǎn)少于1/3的時(shí)候，Tendermint滿足狀態(tài)機(jī)安全，我們采用反證法。假設(shè)Tendermint并不滿足狀態(tài)機(jī)安全，允許在某一高度提交多個(gè)區(qū)塊。那么我們可以證明至少需要1/3的拜占庭節(jié)點(diǎn)，與假設(shè)矛盾。

考慮一個(gè)有效的驗(yàn)證者在高度H和輪數(shù)R提交了一個(gè)區(qū)塊B。提交一個(gè)區(qū)塊意味著驗(yàn)證者在第R輪收到了關(guān)于區(qū)塊B的超過(guò)2/3的預(yù)提交。假設(shè)另一個(gè)區(qū)塊C在高度H提交。我們有兩個(gè)選項(xiàng)：要么在第R輪提交要么在S輪提交（S》R）。

如果區(qū)塊C在第R輪提交，那么超過(guò)2/3的驗(yàn)證者必須為該區(qū)塊預(yù)提交，那么意味著至少1/3的驗(yàn)證者在第R輪同時(shí)對(duì)區(qū)塊B和C進(jìn)行了預(yù)提交，那么顯然這些同時(shí)節(jié)點(diǎn)是拜占庭節(jié)點(diǎn)。假設(shè)區(qū)塊C在S輪提交。因?yàn)槌^(guò)2/3對(duì)B區(qū)塊進(jìn)行了預(yù)提交，他們?cè)赟輪也將被鎖定在區(qū)塊B上，因此他們必須對(duì)B進(jìn)行預(yù)投票。為了對(duì)區(qū)塊C進(jìn)行預(yù)提交，他們必須接收到關(guān)于區(qū)塊C的波爾卡，因此需要關(guān)于區(qū)塊C的超過(guò)2/3的預(yù)投票。然而，超過(guò)2/3的驗(yàn)證者已經(jīng)被鎖定在區(qū)塊B上。節(jié)點(diǎn)為了收到區(qū)塊C的波爾卡至少需要網(wǎng)絡(luò)中1/3的驗(yàn)證者違背鎖機(jī)制，這部分節(jié)點(diǎn)顯然是拜占庭節(jié)點(diǎn)。因此，為了違背狀態(tài)機(jī)安全，至少需要1/3的拜占庭驗(yàn)證者。即若網(wǎng)絡(luò)中的拜占庭節(jié)點(diǎn)少于總數(shù)的1/3，Tendermint滿足狀態(tài)機(jī)安全性。

綜上，Tendermint滿足原子廣播。

在未來(lái)的工作中，我們會(huì)提供關(guān)于Tendermint的安全性的更正式的證明。

責(zé)任制

一個(gè)具有問(wèn)責(zé)制的拜占庭容錯(cuò)算法能夠在存在安全隱患時(shí)標(biāo)識(shí)所有的拜占庭驗(yàn)證者。傳統(tǒng)的拜占庭容錯(cuò)算法并沒(méi)與這個(gè)特性，對(duì)應(yīng)地也沒(méi)有任何相應(yīng)的保證。當(dāng)然，問(wèn)責(zé)制僅能適用在拜占庭節(jié)點(diǎn)在1/3到2/3的情況。如果超過(guò)2/3的節(jié)點(diǎn)是拜占庭，他們能夠完全占據(jù)協(xié)議，此時(shí)無(wú)法保證一個(gè)合法的驗(yàn)證者可以收到任何拜占庭節(jié)點(diǎn)違法的證據(jù)。

進(jìn)一步，問(wèn)責(zé)制是在異步網(wǎng)絡(luò)環(huán)境下最終性的盡力而為，在這樣的網(wǎng)絡(luò)環(huán)境中著安全問(wèn)題，關(guān)鍵消息（critical messages）的延遲使得在探測(cè)到安全問(wèn)題以后才可能發(fā)現(xiàn)拜占庭驗(yàn)證者。事實(shí)上，如果正確的進(jìn)程（correct processes）可以接受拜占庭行為的相關(guān)證據(jù)（evidence），但是在他們能夠通訊之前不可逆地失敗了（fail irreversibly），可能使得問(wèn)責(zé)制永久失效（ Permanently compromised），盡管實(shí)際上這種情形可以通過(guò)高級(jí)備份策略來(lái)克服。

通過(guò)枚舉安全問(wèn)題的各種隱患，拜占庭驗(yàn)證者是可以識(shí)別的，這樣協(xié)議是具有問(wèn)責(zé)制的。與其它競(jìng)選相關(guān)的協(xié)議相比，Tendermint的簡(jiǎn)潔給予了其更簡(jiǎn)單的分析方法。

在Tendermint存在兩類(lèi)安全隱患，每一種都是可問(wèn)責(zé)的。第一種，拜占庭提議者在單輪中產(chǎn)生兩個(gè)沖突的提議，并且拜占庭驗(yàn)證者同時(shí)對(duì)這兩個(gè)提議進(jìn)行投票（vote）。第二種，一些驗(yàn)證者在單輪已經(jīng)提交（commit）之后，拜占庭驗(yàn)證者違反鎖機(jī)制（locking rules），致使其他驗(yàn)證者在隨后的輪數(shù)提交一個(gè)不同的區(qū)塊。注意到，若拜占庭驗(yàn)證者少于2/3，只通過(guò)違反解鎖機(jī)制的方法是無(wú)法引發(fā)安全性問(wèn)題的，同時(shí)超過(guò)1/3的節(jié)點(diǎn)必須違背波爾卡鎖機(jī)制，因?yàn)槊恳粋€(gè)提交（commot）需要有一個(gè)波爾卡為其背書(shū)。

在存在提議或者投票沖突的情況下，同時(shí)接受沖突的提議或者投票，可以根據(jù)這些提議或投票的簽名來(lái)辨別這些拜占庭節(jié)點(diǎn)。

在違反鎖定機(jī)制（locking rules）的情況下，伴隨著相應(yīng)的安全性問(wèn)題，有效的驗(yàn)證者必須廣播在當(dāng)前高度看到的所有投票，這樣證據(jù)可以被收集起來(lái)。少于2/3的正確驗(yàn)證者在所有導(dǎo)致兩個(gè)區(qū)塊被同時(shí)提交的投票中集體隱匿。此時(shí)在這些投票中，如果沒(méi)有1/3或者更多的驗(yàn)證者簽名沖突的投票，那么存在1/3或者更多的驗(yàn)證者違反了鎖定機(jī)制。

如果預(yù)投票（ pre-vote ）或者預(yù)提交（ pre-commit）影響了一個(gè)提交，它一定會(huì)被一個(gè)合法的驗(yàn)證者看見(jiàn)。因此，通過(guò)搜集所有的投票，通過(guò)匹配每一個(gè)預(yù)投票和最近的預(yù)提交，可以探測(cè)到違反鎖機(jī)制的行為（violations of Prevotethe-Lock ）。

類(lèi)似的，通過(guò)匹配預(yù)提交（pre-commit ）和為其背書(shū)的波卡爾卡（polka），可以探測(cè)到違反解鎖機(jī)制的行為（violations of Unlock-on-Polka ）。注意到這就意味著如果拜占庭驗(yàn)證者可以在看見(jiàn)波爾卡之前預(yù)提交（pre-commit），并且如果相應(yīng)的波爾卡最終發(fā)生的話，拜占庭驗(yàn)證者將逃脫責(zé)任制。然而，如果每一個(gè)預(yù)提交有波爾卡背書(shū)的話，這些安全隱患就不存在。

目前的設(shè)計(jì)提供了問(wèn)責(zé)制，伴隨著后危機(jī)廣播協(xié)議（post-crisis broadcast protocol），但是其能夠用來(lái)提高實(shí)時(shí)的問(wèn)責(zé)制。也就是說(shuō)，一旦提交被改變，相應(yīng)的預(yù)提交，為預(yù)提交背書(shū)的預(yù)投都會(huì)發(fā)生改變，這樣一直回退到創(chuàng)世紀(jì)塊。通過(guò)上面的方式，如果發(fā)生安全問(wèn)題，沒(méi)有背書(shū)的投票可以立即被探測(cè)到。

故障和可用性

作為一個(gè)拜占庭共識(shí)容錯(cuò)算法，Tendermint可以容忍拜占庭故障節(jié)點(diǎn)到（但不包括）節(jié)點(diǎn)總數(shù)的1/3。這就意味著節(jié)點(diǎn)可能會(huì)崩潰，發(fā)送不同和沖突的消息到不同的節(jié)點(diǎn)，拒絕中繼消息或者表現(xiàn)異常，安全或者運(yùn)轉(zhuǎn)存在問(wèn)題。

協(xié)議中有兩個(gè)地方我們可以通過(guò)使用本地時(shí)鐘的超時(shí)特性，為不同時(shí)性做一些優(yōu)化：在接收到2/3或者更多預(yù)投票（pre-votes）之后（不針對(duì)單個(gè)區(qū)塊或者nil）和在收到2/3或更多預(yù)提交（pre-commit）以后（不針對(duì)單個(gè)區(qū)塊或者nil）。在每一中情形中，我們可以睡眠一段時(shí)間用來(lái)給延遲的投票一個(gè)被接受的機(jī)會(huì)，因此減少在新的一輪沒(méi)有提交區(qū)塊的可能性。時(shí)鐘不需要在驗(yàn)證者之間同步，因?yàn)轵?yàn)證者在觀測(cè)到2/3或更多的投票時(shí)會(huì)重置各自的時(shí)間。

如果1/3或者更多的驗(yàn)證者崩潰，網(wǎng)絡(luò)癱瘓，因?yàn)槿魏喂沧R(shí)進(jìn)展需要2/3以上驗(yàn)證者的投票。網(wǎng)絡(luò)仍然可以讀取數(shù)據(jù)，但是沒(méi)有新的區(qū)塊的提交。只要驗(yàn)證者重新上線，他們能夠從之前的投票狀態(tài)開(kāi)始。共識(shí)狀態(tài)機(jī)應(yīng)該配置一個(gè)預(yù)寫(xiě)式日志（write-ahead log），這樣重新上線的的驗(yàn)證者可以快速回退到之前機(jī)器崩潰時(shí)的位置，確保沒(méi)有違反規(guī)則。

如果1/3或者更多的驗(yàn)證者是拜占庭，他們能夠以多種方式損害系統(tǒng)的安全性。例如，在同一輪提交兩個(gè)塊，并且投票提交這兩個(gè)區(qū)塊或者通過(guò)通過(guò)違反鎖定機(jī)制在同一高度不同輪提交兩個(gè)不同的區(qū)塊。在每一種情形中，有清晰的證據(jù)顯示哪些驗(yàn)證者是拜占庭節(jié)點(diǎn)。在第一個(gè)例子中，他們?cè)谕惠喓灻麅蓚€(gè)不同的提議，違反規(guī)則。在第二個(gè)例子中，他們鎖定在r-1輪在第r輪提交了一個(gè)不同的區(qū)塊，違反了鎖定機(jī)制。

當(dāng)使用經(jīng)濟(jì)和治理組件來(lái)激勵(lì)和管理共識(shí)，這些額外的責(zé)任制保證是具有決定性的。

結(jié)論

Tendermint本身是弱同步，拜占庭容錯(cuò)，狀態(tài)機(jī)復(fù)制協(xié)議，擁有優(yōu)化的拜占庭容錯(cuò)和額外的責(zé)任制來(lái)保證當(dāng)超過(guò)拜占庭容錯(cuò)假設(shè)上限時(shí)的情形。協(xié)議采用round robin的提議者產(chǎn)生方法，用同樣的機(jī)制跳過(guò)一個(gè)提議者。多輪投票之間的安全性通過(guò)鎖機(jī)制得到了保障。