共識

CAP理論

一致性consistency

服務可用性availability:請求在一定時間內得到回應，可終止、不會一直等待

磁區容錯性partition-tolerance：網路磁區情況下，被分割的節點仍能對外服務

tendermint

協議中的參與者叫著 “驗證人”（validator），他們輪流對交易區塊進行提議，并對這些區塊進行投票，區塊會被提交到鏈上，每一個塊占據一個“高度”（height），提交塊可能會失敗，如果失敗，協議就會開始下一輪的提交，并且一個新的驗證人會繼續提交那個高度的區塊，要想成功提交一個塊，需要有兩個階段的投票：“預投票”（pre-vote）和“預提交”（pre-commit），在同一輪提交中，只有超過 2/3 的驗證人對同一個塊進行了預提交，這個塊才能被提交到鏈上，
　　上圖右下角有一對夫婦在跳波卡舞，因為驗證人做的事情就像是在跳波卡舞，當超過 2/3 的驗證人對同一個塊進行了預投票，我們就把它叫做一個“波卡”（polka），每一個預提交都必須被同一輪中的一個波卡所證明，
　　由于一些原因，驗證人可能在提交一個塊時失敗：當前提議者可能離線了，或者網路非常慢，Tendermint 允許他們證實一個驗證人應該被跳過，在進行下一輪的投票前，驗證人會等待一小段時間從提議者那里接收一個完整的提議塊，這種對于超時的依賴，使得 Tendermint 成為了一個弱同步協議，而非一個異步協議，但是，協議的剩余部分都是異步的，只有在接收到超過 2/3 的驗證人集合時，驗證人才會采取下一步操作，Tendermint 能夠簡化的一個原因就是它使用了同樣的機制來提交一個塊和跳過直接進入下一輪，
　　基于不到 1/3 的驗證人是拜占庭節點的前提，Tendermint 保證了永遠都不會違背其安全性 – 也就是說，驗證人永遠不會在同一高度提交沖突塊，為了達到這一點，它引入了一些 “鎖定”（locking）的規則，這些規則對流程圖中的路徑進行了模塊化，一旦一個驗證人預提交了一個塊，它就被“鎖定”在了那個塊上，然后，

1. 它必須為被鎖定的那個塊進行預投票
2. 只有在之后的輪中，有了那個塊的一個波卡，它才能夠解鎖，并為一個新塊進行預提交，

PAXOS

raft

leader選舉程序

Raft通過心跳機制發起leader選舉，節點都是從follower狀態開始的，如果收到了來自leader或candidate的RPC，那它就保持follower狀態，避免爭搶成為candidate，Leader會發送空的AppendEntries RPC作為心跳信號來確立自己的地位，如果follower一段時間(election timeout)沒有收到心跳，它就會認為leader已經掛了，發起新的一輪選舉，

選舉發起后，一個follower會增加自己的當前term編號并轉變為candidate，它會首先投自己一票，然后向其他所有節點并行發起RequestVote RPC，之后candidate狀態將可能發生如下三種變化:

• 贏得選舉,成為leader: 如果它在一個term內收到了大多數的選票，將會在接下的剩余term時間內稱為leader，然后就可以通過發送心跳確立自己的地位，(每一個server在一個term內只能投一張選票，并且按照先到先得的原則投出)
• **其他server成為leader：**在等待投票時，可能會收到其他server發出AppendEntries RPC心跳信號，說明其他leader已經產生了，這時通過比較自己的term編號和RPC過來的term編號，如果比對方大，說明leader的term過期了，就會拒絕該RPC,并繼續保持候選人身份; 如果對方編號不比自己小,則承認對方的地位,轉為follower.
• 選票被瓜分,選舉失敗: 如果沒有candidate獲取大多數選票, 則沒有leader產生, candidate們等待超時后發起另一輪選舉. 為了防止下一次選票還被瓜分,必須采取一些額外的措施, raft采用隨機election timeout的機制防止選票被持續瓜分，通過將timeout隨機設為一段區間上的某個值, 因此很大概率會有某個candidate率先超時然后贏得大部分選票.

日志復制程序

一旦leader被選舉成功，就可以對客戶端提供服務了，客戶端提交每一條命令都會被按順序記錄到leader的日志中，每一條命令都包含term編號和順序索引，然后向其他節點并行發送AppendEntries RPC用以復制命令(如果命令丟失會不斷重發)，當復制成功也就是大多數節點成功復制后，leader就會提交命令，即執行該命令并且將執行結果回傳客戶端，raft保證已經提交的命令最終也會被其他節點成功執行，leader會保存有當前已經提交的最高日志編號，順序性確保了相同日志索引處的命令是相同的，而且之前的命令也是相同的，當發送AppendEntries RPC時，會包含leader上一條剛處理過的命令，接收節點如果發現上一條命令不匹配，就會拒絕執行，

zab

Casper

是一種基于保證金的經濟激勵共識協議(security-deposit based economic consensus protocol)，是以太坊的下一代共識演算法，

HotStuff

是基于View的的共識協議，View表示一個共識單元，共識程序是由一個接一個的View組成，在一個View中，存在一個確定Leader來主導共識協議，并經過三階段投票達成共識，然后切換到下一個View繼續進行共識，假如遇到例外狀況，某個View超時未能達成共識，也是切換到下一個View繼續進行共識，

Basic hotStuff基礎版本的共識協議，一個區塊的確認需要三階段投票達成后再進入下一個區塊的共識，pipeline hotStuff是流水線的共識協議，提高了共識的效率，

HotStuff是基于View的的共識協議，View表示一個共識單元，共識程序是由一個接一個的View組成，在一個View中，存在一個確定Leader來主導共識協議，并經過三階段投票達成共識，然后切換到下一個View繼續進行共識，假如遇到例外狀況，某個View超時未能達成共識，也是切換到下一個View繼續進行共識，

Basic hotStuff基礎版本的共識協議，一個區塊的確認需要三階段投票達成后再進入下一個區塊的共識，pipeline hotStuff是流水線的共識協議，提高了共識的效率，

一個區塊的確認需要三階段投票達成后再進入下一個區塊的共識，pipeline hotStuff是流水線的共識協議，提高了共識的效率，

PBFT

PBFT演算法流程：

PBFT演算法前提，采用密碼學演算法保證節點之間的訊息傳送是不可篡改的，

PBFT容忍無效或者惡意節點數：f，為了保障整個系統可以正常運轉，需要有2f+1個正常節點，系統的總節點數為：|R| = 3f + 1，也就是說，PBFT演算法可以容忍小于1/3個無效或者惡意節點，該部分的原理證明請參考PBFT論文，下文有鏈接地址，

PBFT是一種狀態機副本復制演算法，所有的副本在一個視圖（view）輪換的程序中操作，主節點通過視圖編號以及節點數集合來確定，即：主節點 p = v mod |R|，v：視圖編號，|R|節點個數，p：主節點編號，

PBFT演算法主體實作流程圖如下：

PBFT演算法流程

以下詳細說明，每個主體流程內容：

\1. REQUEST：

客戶端c向主節點p發送<REQUEST, o, t, c>請求，o: 請求的具體操作，t: 請求時客戶端追加的時間戳，c：客戶端標識，REQUEST: 包含訊息內容m，以及訊息摘要d(m)，客戶端對請求進行簽名，

\2. PRE-PREPARE：

主節點收到客戶端的請求，需要進行以下交驗：

a. 客戶端請求訊息簽名是否正確，

非法請求丟棄，正確請求，分配一個編號n，編號n主要用于對客戶端的請求進行排序，然后廣播一條<<PRE-PREPARE, v, n, d>, m>訊息給其他副本節點，v：視圖編號，d客戶端訊息摘要，m訊息內容，<PRE-PREPARE, v, n, d>進行主節點簽名，n是要在某一個范圍區間內的[h, H]，具體原因參見垃圾回收章節，

\3. PREPARE：

副本節點i收到主節點的PRE-PREPARE訊息，需要進行以下交驗：

a. 主節點PRE-PREPARE訊息簽名是否正確，

b. 當前副本節點是否已經收到了一條在同一v下并且編號也是n，但是簽名不同的PRE-PREPARE資訊，

c. d與m的摘要是否一致，

d. n是否在區間[h, H]內，

非法請求丟棄，正確請求，副本節點i向其他節點包括主節點發送一條<PREPARE, v, n, d, i>訊息, v, n, d, m與上述PRE-PREPARE訊息內容相同，i是當前副本節點編號，<PREPARE, v, n, d, i>進行副本節點i的簽名，記錄PRE-PREPARE和PREPARE訊息到log中，用于View Change程序中恢復未完成的請求操作，

\4. COMMIT：

主節點和副本節點收到PREPARE訊息，需要進行以下交驗：

a. 副本節點PREPARE訊息簽名是否正確，

b. 當前副本節點是否已經收到了同一視圖v下的n，

c. n是否在區間[h, H]內，

d. d是否和當前已收到PRE-PPREPARE中的d相同

非法請求丟棄，如果副本節點i收到了2f+1個驗證通過的PREPARE訊息，則向其他節點包括主節點發送一條<COMMIT, v, n, d, i>訊息，v, n, d, i與上述PREPARE訊息內容相同，<COMMIT, v, n, d, i>進行副本節點i的簽名，記錄COMMIT訊息到日志中，用于View Change程序中恢復未完成的請求操作，記錄其他副本節點發送的PREPARE訊息到log中，

\5. REPLY：

主節點和副本節點收到COMMIT訊息，需要進行以下交驗：

a. 副本節點COMMIT訊息簽名是否正確，

b. 當前副本節點是否已經收到了同一視圖v下的n，

c. d與m的摘要是否一致，

d. n是否在區間[h, H]內，

非法請求丟棄，如果副本節點i收到了2f+1個驗證通過的COMMIT訊息，說明當前網路中的大部分節點已經達成共識，運行客戶端的請求操作o，并回傳<REPLY, v, t, c, i, r>給客戶端，r：是請求操作結果，客戶端如果收到f+1個相同的REPLY訊息，說明客戶端發起的請求已經達成全網共識，否則客戶端需要判斷是否重新發送請求給主節點，記錄其他副本節點發送的COMMIT訊息到log中，

垃圾回收：

在上述演算法流程中，為了確保在View Change的程序中，能夠恢復先前的請求，每一個副本節點都記錄一些訊息到本地的log中，當執行請求后副本節點需要把之前該請求的記錄訊息清除掉，最簡單的做法是在Reply訊息后，再執行一次當前狀態的共識同步，這樣做的成本比較高，因此可以在執行完多條請求K（例如：100條）后執行一次狀態同步，這個狀態同步訊息就是CheckPoint訊息，

副本節點i發送<CheckPoint, n, d, i>給其他節點，n是當前節點所保留的最后一個視圖請求編號，d是對當前狀態的一個摘要，該CheckPoint訊息記錄到log中，如果副本節點i收到了2f+1個驗證過的CheckPoint訊息，則清除先前日志中的訊息，并以n作為當前一個stable checkpoint，

這是理想情況，實際上當副本節點i向其他節點發出CheckPoint訊息后，其他節點還沒有完成K條請求，所以不會立即對i的請求作出回應，它還會按照自己的節奏，向前行進，但此時發出的CheckPoint并未形成stable，為了防止i的處理請求過快，設定一個上文提到的高低水位區間[h, H]來解決這個問題，低水位h等于上一個stable checkpoint的編號，高水位H = h + L，其中L是我們指定的數值，等于checkpoint周期處理請求數K的整數倍，可以設定為L = 2K，當副本節點i處理請求超過高水位H時，此時就會停止腳步，等待stable checkpoint發生變化，再繼續前進，

View Change：

如果主節點作惡，它可能會給不同的請求編上相同的序號，或者不去分配序號，或者讓相鄰的序號不連續，備份節點應當有職責來主動檢查這些序號的合法性，如果主節點掉線或者作惡不廣播客戶端的請求，客戶端設定超時機制，超時的話，向所有副本節點廣播請求訊息，副本節點檢測出主節點作惡或者下線，發起View Change協議，

副本節點向其他節點廣播<VIEW-CHANGE, v+1, n, C, P, i>訊息，n是最新的stable checkpoint的編號，C是2f+1驗證過的CheckPoint訊息集合，P是當前副本節點未完成的請求的PRE-PREPARE和PREPARE訊息集合，

當主節點p = v + 1 mod |R|收到2f個有效的VIEW-CHANGE訊息后，向其他節點廣播<NEW-VIEW, v+1, V, O>訊息，V是有效的VIEW-CHANGE訊息集合，O是主節點重新發起的未經完成的PRE-PREPARE訊息集合，PRE-PREPARE訊息集合的選取規則：

\1. 選取V中最小的stable checkpoint編號min-s，選取V中prepare訊息的最大編號max-s，

\2. 在min-s和max-s之間，如果存在P訊息集合，則創建<<PRE-PREPARE, v+1, n, d>, m>訊息，否則創建一個空的PRE-PREPARE訊息，即：<<PRE-PREPARE, v+1, n, d(null)>, m(null)>, m(null)空訊息，d(null)空訊息摘要，

副本節點收到主節點的NEW-VIEW訊息，驗證有效性，有效的話，進入v+1狀態，并且開始O中的PRE-PREPARE訊息處理流程，

總結：

PBFT演算法由于每個副本節點都需要和其他節點進行P2P的共識同步，因此隨著節點的增多，性能會下降的很快，但是在較少節點的情況下可以有不錯的性能，并且分叉的幾率很低，PBFT主要用于聯盟鏈，但是如果能夠結合類似DPOS這樣的節點代表選舉規則的話也可以應用于公聯，并且可以在一個不可信的網路里解決拜占庭容錯問題，TPS應該是遠大于POW的，