tendermint共識演算法

內容參考：

1. 詳解Tendermint共識演算法
2. tendermint介紹
3. tendermint中文檔案

圖中的Round/Height為直觀意思，step指圖中的每一狀態（Proposal、PreVote…）
狀態轉換周期：

NewHeight -> (Propose -> Prevote -> Precommit)+ -> Commit -> NewHeight ->...

每輪的開始對同步有弱的依賴性，每一輪開始期間，存在一個用來計時的本地同步時鐘，如果驗證者在TimeoutPropose時間內沒有收到提議，會立刻在本機生成一個特殊結構的空塊，假裝這個空塊是從Proposer節點那里收到的，這樣，無論如何，在時間T內，都會收到一個proposal區塊，要么是一個正常塊要么是一個空塊，然后接著對這個塊進行pre-vote投票和pre-commit投票，如果proposer掛了，絕大部分validator看到的都是一個空塊，因此空塊會獲得多數投票，進入commit階段，commit空塊的時候，不會真的往區塊鏈寫入一個空塊，而是什么都不寫，區塊高度不自增，保持不變，這樣相當于什么也沒有干，這一輪(round)是在空轉，下一輪開始的時候會換下一個validator當proposer，這樣當前那個掛掉的proposer，就不會卡住整個網路，

每輪收到提議以后，進入完全異步模式，之后驗證者的每一個網路決定需要得到2/3驗證者以上的同意，這樣降低了對同步時鐘的依賴或者網路的延遲，但是這也意味著如果得不到1/3以上驗證者的回應，整個網路將癱瘓，Tendermint在Liveness方面有所妥協，換取了更強的Finality，
舉個例子，如果在某一輪中proposer節點廣播出了一個新塊blockX，某個validator A節點沒有按時收到新塊，那么該A就會在本機構造一個空塊，當做是從proposer收到的，發出一個pre-vote nil投票訊息然后進入pre-vote回圈，并啟動一個超時定時器，這時進入了紅色內圈回圈，A開始監聽網路并收集投票資訊，

如果在規定時間內，收集到的投票數，無論是投給空塊的還是blockX的，加起來，沒有超過2/3，則無限等待，直到投票總數超過2/3

收集到了超過2/3的投票總數后，如果投給空塊的票數超過2/3，則發出pre-vote nil投給空塊，依舊留在紅色內圈；如果投給blockX的票數超過2/3，則發出pre-vote投給blockX，切換到藍色外圈；如果空塊和blockX各自的票數，都沒有超過2/3，那么發出pre-vote nil 訊息投票給空塊，進入pre-commit階段，依舊在紅色內圈，

一旦A發出了pre-commit nil的投票訊息，A還是留在紅色內圈回圈，pre-commit流程與上面類似，總而言之，紅色內圈的流程，需要假設網路是半同步的，

簡言之，每輪開始提議弱同步，之后投票完全異步，

tendermint和傳統PBFT的比較

1. Tendermint沒有pBFT那種View Change階段，Tendermint很巧妙的把超時的情況，跟普通情況融合成了統一的形式，都是 propose->pre-vote->pre-commit 三階段，只是超時的時候新塊是一個特殊的空塊，切換proposer是通過提交commit空塊來觸發的，而pBFT是有一個單獨的view change程序來觸發primary輪換，
2. Tendermint的所有資訊都存盤在blockchain里，因為pBFT是1999年提出來的，那時候還沒有blockchain這個東西(blockchain是2009年位元幣出現之后才有的)，因此 pBFT的所有節點雖有有一致的資料，但資料是分散存放的，Blockchain就是一個分布式資料庫，好比在MySQL這類DBMS資料庫沒出現之前，人們都是把資料寫入檔案然后存在硬碟上，發明出各種奇怪的檔案格式和組織方式，有了MySQL后，管理資料就方便多了，同理，Tendermint 把資料全部存入blockchain, pBFT沒有blockchain這樣一個分布式資料庫，所有全節點需要自己在硬碟上管理資料，比如為了壓縮訊息日志，丟棄老的訊息，節省硬碟空間，引入了checkpoint的概念，光是資料管理這一塊就多了很多繁瑣的步驟

股權

驗證者在共識協議中可能具有不同的投票“權重”， 因此，Tendermint并不關注驗證者數目的1/3或2/3， 而是關注總投票權的比例，此外，這個比例可能不是在各個驗證者中均勻分布的，

驗證者持有的貨幣可以系結到保證金中，并且如果發現它們在共識協議中行為不當，則可以將其銷毀， 這為協議的安全性增加了一個經濟因素，當拜占庭節點小于三分之一的假設被打破時，人們可以量化產生的代價，

鎖

波爾卡（Polka）：對提議區塊的預投票數量超過2/3，對應圖中兩個人跳舞的地方
什么時候鎖：驗證者為某一輪的區塊預提交，則鎖定在該輪的區塊上，鎖定的驗證者只能為鎖定的區塊預提交，不能為其他區塊預投票和預提交
什么時候解鎖：當出現一個波爾卡，則解鎖

加入鎖（Lock）主要是用于避免在同一高度的不同輪提交不同的區塊，
舉個例子：考慮4個驗證者A,B,C,D，假設有一個第R輪關于blockX的提議，現在假設blockX已經有一個波爾卡，但是A看不見它，預提交（pre-commit）為空，然而其他人對blockX進行了預提交，進一步假設只有D看見了所有的預提交，然而其他人并沒有看見D的預提交（他們只看見他們的預提交和A的空預提交），D現在將要提交（commit）這個區塊，然而其他人進入到R+1輪，由于任何驗證者都可能是新的提議者，如果ABC提議并投票了一個新的區塊blockY，他們可能達成共識并提交這個區塊，可是D已經提交了bockX，因此損害了系統的安全性，注意，這里并沒有任何拜占庭行為，僅僅是不同時性，
鎖解決了這個問題通過強迫驗證者粘附在他們預提交（pre-commit）的區塊上，因為其他的驗證者可能居于這個預提交進行了提交（如上例中的D），本質上，在任何一個節點一旦存在超過2/3預提交（pre-commit），整個網路被鎖定在這個區塊上，也就是說在下一輪中無法產生一個不同塊的波爾卡，這是預投票鎖的直接動機，
每一個pre-commit（預提交）都必須由同一輪的波爾卡（polka）來證明，

問題：

1. 為什么不能用區塊編號來區磁區塊，最終只提交統計超過2/3投票的區塊？
   原因：tendermint不存在弱中心來統計投票確認的數量
2. 假設驗證者全為非拜占庭節點，超過2/3的節點預投票后，1/3~2/3的節點預提交（預投票的節點網路出現問題掉線），剩下的的節點無法產生波爾卡，如何解鎖？？
3. 為什么會產生多輪，怎樣會觸發新的一輪？
   答：提議節點掉線、無效塊、prevote和precommit票數不夠2/3

提議者的選舉

滿足必要要求Rx和可選要求Ox：
R1:Determinism
在分布式系統中，對于同一高度同一輪，兩個誠實節點生成的提議者是一樣的（原文的process不知道是啥）

proposer_p(h,r) = proposer_q(h,r)

where proposer_p(h,r) is the proposer returned by the Proposer Selection Procedure at process p, at height h and round r.

R2:Fairness
根據權重盡可能地“公平”

Given a validator set with total voting power P and a sequence S of elections. In any sub-sequence of S with length C*P, a validator v must be elected as proposer P/VP(v) times, i.e. with frequency:

f(v) ~ VP(v) / P

where C is a tolerance factor for validator set changes with following values:

C == 1 if there are no validator set changes
C ~ k when there are validator changes

演算法

• 所有地驗證者根據股權向前移動：通過投票權提升優先級
• 優先級佇列的第一個被選為區塊提議者
• 向后移動區塊提議者：通過總投票權降低優先級

節點集
演算法流程圖

節點集更改

1.投票權更改

依然按照原有演算法進行

2.驗證者缺失

為了是優先級總和保持為0，在原有演算法上增添一步：每個驗證者的優先級減去平均優先級

3.驗證者增添

首先，添加的驗證者V的初始優先級為：

A(V) = -1.125*P，P為包括V投票權的總投票權

然后每個驗證者再次減去平均優先級

A(p3)=-1.125*(1+3+8) ≈ \approx ≈-13

提議者選擇的參考鏈接：Proposer selection procedure in Tendermint