拜占庭容錯演算法

1. 共識演算法都包括了什麼演算法

下面列出30種共識演算法。
1. 工作量證明(PoW，Proof of Work)
2. 權益證明(PoS，Proof of Stake)
3. 延遲工作量證明(dPoW，Delayed Proof-of-Work)
4. 授權 PoS(DPoS，Delegated Proof-of-Stake)
5. 權威證明(PoA，Proof-of-Authority)
6. 權重證明(PoWeight，Proof-of-Weight)
7. 聲譽證明(PoR，Proof of Reputation)
8. 所用時間證明(PoET，Proof of Elapsed Time)
9. 容量證明(PoC，Proof of Capacity)，也稱為空間證明(PoSpace，Proof of Space)
10. 歷史證明(PoHistory，Proof of History)
11. 權益流通證明(PoSV，Proof of Stake Velocity)
12. 重要性證明(PoImportance，Proof of Importance)
13. 燒毀證明(PoBurn，Proof of Burn)
14. 身份證明(PoI，Proof of Identity)
15. 活動證明(PoActivity，Proof Of Activity)
16. 時間證明(PoTime，Proof of Time)
17. 存在證明(PoExistence，Proof of Existence)
18. Ouroboros
19. 可收回證明(PoR，Proof of Retrievability)
20. 拜占庭容錯(Byzantine Fault Tolerance)
21. 授權拜占庭容錯演算法(dBFT，Delegated Byzantine Fault Tolerance)
22. RAFT
23. 恆星共識(Stellar Consensus)
24. 置信度證明(PoB，Proof of Believability)
25. 有向無環圖(DAG，Directed Acyclic Graphs)
26. Tangle(IOTA)
27. Hashgraph
28.Holochain
29. Block-Lattice(Nano)
30.SPECTRE

2. 共識演算法4 (BFT)

拜占庭將軍問題（Byzantine Generals Problem），由Leslie Lamport、Robert Shostak和Marshall Pease，在其同名論文中提出（1982年）。拜占庭將軍問題現在主要指分布式對等網路節點間的通信容錯問題。在分布式網路中，不同的計節點通過交換信息達成共識。但有時候，系統中的成員節點可能出錯而發送錯誤的信息，用於傳遞信息的通訊網路也可能導致信息損壞，也可能存在惡意節點或被黑客攻破的節點故意發送錯誤的信息，從而導致系統無法達成共識或者達成錯誤的共識。（參考： BFT Wikipedia ）

拜占庭將軍問題提出後，有很多的演算法被提出用於解決這個問題。這類演算法統稱拜占庭容錯演算法（BFT: Byzantine Fault Tolerance）。BFT從上世紀80年代開始被研究，目前已經是一個被研究得比較透徹的理論，具體實現都已經有現成的演算法。

BFT演算法中最典型的是PBFT（Practical BFT）。PBFT是由Miguel Castro和Barbara Liskov於1999年提出。PBFT演算法解決了之前拜占庭容錯演算法效率不高的問題，將演算法復雜度由指數級降低到多項式級，使得拜占庭容錯演算法在實際系統應用中變得可行。PBFT在保證安全性和可用性的前提下，提供了 (n-1)/3 的容錯性。（細節請參考： PBFT ）

PBFT之後，很多進一步提升性能或魯棒性的BFT演算法先後被提出，例如Zyzzyva、ABsTRACTs、Aardvark、RBFT等等。近幾年，由於區塊鏈的熱度，無數針對區塊鏈應用場景優化過的BFT演算法也不斷涌現出來。雖然目前PBFT已經不能說是最好的，或最適合區塊鏈的BFT演算法。但是PBFT已經足夠好了，而且在實際應用中已經非常成熟。

在BFT共識機制中，網路中節點的數量和身份必須是提前確定好的。BFT共識機制無法做到PoW共識機制中實現的任何人都可以隨時加入挖礦。另外，BFT演算法無法應用到大量的節點，業內普遍認為100個節點是BFT演算法的上限。所以BFT演算法無法直接用於公有鏈，BFT演算法適合的場景是私有鏈和聯盟鏈。業內大名鼎鼎的聯盟鏈Hyperledger fabric v0.6採用的是PBFT，v1.0又推出PBFT的改進版本SBFT。這里再順便提一句，在可信環境下共識演算法一般使用傳統的分布式一致演算法PAXOS或者RAFT。

公有鏈使用BFT的一個例外是NEO，NEO使用了DBFT（delegated BFT）共識機制。DBFT共識機制下投票選出7個共識節點。這些代理節點是通過靜態選出的，並完全由項目方部署。這也是NEO被外界質疑過於中心化的原因。（參考： 早期公有鏈明星項目-NEO ）

BFT演算法和公有鏈合適的結合點在於基於BFT的PoS共識演算法（BFT based PoS）。基於BFT的PoS共識演算法要點有：一，網路節點通過鎖定虛擬資產申請成為區塊鏈系統的驗證者（或礦工）。系統驗證者的數量是動態變化的。二，系統從當前驗證者中隨機選擇一個人作為區塊提案人。三，系統驗證者對區塊提案進行投票表決，投票可能要進行多輪才能達成共識。每個人的投票比重與鎖定的虛擬資產成比例。

基於BFT的PoS的典型例子是tendermint（Cosmos採用了tendermint作為共識核心）。

3. 共識演算法系列之一：私鏈的raft演算法和聯盟鏈的 pbft 演算法

對數據順序達成一致共識是很多共識演算法要解決的本質問題
Fabic的pbft演算法實現
現階段的共識演算法主要可以分成三大類：公鏈，聯盟鏈和私鏈
私鏈，所有節點可信
聯盟鏈，存在對等的不信任節點
私鏈：私鏈的共識演算法即區塊鏈這個概念還沒普及時的傳統分布式系統里的共識演算法，比如 zookeeper 的 zab 協議，就是類 paxos 演算法的一種。私鏈的適用環境一般是不考慮集群中存在作惡節點，只考慮因為系統或者網路原因導致的故障節點。

聯盟鏈：聯盟鏈中，經典的代表項目是 Hyperledger 組織下的 Fabric 項目， Fabric0.6 版本使用的就是 pbft 演算法。聯盟鏈的適用環境除了需要考慮集群中存在故障節點，還需要考慮集群中存在作惡節點。對於聯盟鏈，每個新加入的節點都是需要驗證和審核的。

公鏈：公鏈不僅需要考慮網路中存在故障節點，還需要考慮作惡節點，這一點和聯盟鏈是類似的。和聯盟鏈最大的區別就是，公鏈中的節點可以很自由的加入或者退出，不需要嚴格的驗證和審核。

在公有鏈中用的最多的是pow演算法和pos演算法，這些演算法都是參與者的利益直接相關，通過利益來制約節點誠實的工作，解決分布式系統中的拜占庭問題。拜占庭容錯演算法是一種狀態機副本復制演算法，通過節點間的多輪消息傳遞，網路內的所有誠實節點就可以達成一致的共識。

使用拜占庭容錯演算法不需要發行加密貨幣，但是只能用於私有鏈或者聯盟鏈，需要對節點的加入進行許可權控制；不能用於公有鏈，因為公有鏈中所有節點都可以隨意加入退出，無法抵擋女巫攻擊（sybil attack）

raft 演算法包含三種角色，分別是：跟隨者（ follower ），候選人（candidate ）和領導者（ leader ）。集群中的一個節點在某一時刻只能是這三種狀態的其中一種，這三種角色是可以隨著時間和條件的變化而互相轉換的。

raft 演算法主要有兩個過程：一個過程是領導者選舉，另一個過程是日誌復制，其中日誌復制過程會分記錄日誌和提交數據兩個階段。raft 演算法支持最大的容錯故障節點是（N-1）/2，其中 N 為 集群中總的節點數量。

國外有一個動畫介紹raft演算法介紹的很透徹，鏈接地址為： http://thesecretlivesofdata.com/raft/ 。這個動畫主要包含三部分內容，第一部分介紹簡單版的領導者選舉和日誌復制的過程，第二部分內容介紹詳細版的領導者選舉和日誌復制的過程，第三部分內容介紹的是如果遇到網路分區（腦裂），raft 演算法是如何恢復網路一致的。

pbft 演算法的提出主要是為了解決拜占庭將軍問題
要讓這個問題有解，有一個 十分重要的前提 ，那就是 信道必須是可靠的 。如果信道不能保證可靠，那麼拜占庭問題無解。關於信道可靠問題，會引出兩軍問題。兩軍問題的結論是，在一個不可靠的通信鏈路上試圖通過通信以達成一致是基本不可能或者十分困難的。
拜占庭將軍問題最早是由 Leslie Lamport 與另外兩人在 1982 年發表的論文《The Byzantine Generals Problem 》提出的， 他證明了在將軍總數大於 3f ，背叛者為f 或者更少時，忠誠的將軍可以達成命令上的一致，即 3f+1<=n 。演算法復雜度為 o（n^(f+1)) 。而 Miguel Castro (卡斯特羅)和 Barbara Liskov （利斯科夫）在1999年發表的論文《 Practical Byzantine Fault Tolerance 》中首次提出 pbft 演算法，該演算法容錯數量也滿足 3f+1<=n ，演算法復雜度為 o（n^2）。

首先我們先來思考一個問題，為什麼 pbft 演算法的最大容錯節點數量是（n-1）/3，而 raft 演算法的最大容錯節點數量是（n-1）/2 ？

對於raft演算法，raft演算法的的容錯只支持容錯故障節點，不支持容錯作惡節點。什麼是故障節點呢？就是節點因為系統繁忙、宕機或者網路問題等其它異常情況導致的無響應，出現這種情況的節點就是故障節點。那什麼是作惡節點呢？作惡節點除了可以故意對集群的其它節點的請求無響應之外，還可以故意發送錯誤的數據，或者給不同的其它節點發送不同的數據，使整個集群的節點最終無法達成共識，這種節點就是作惡節點。

raft 演算法只支持容錯故障節點，假設集群總節點數為n，故障節點為 f ，根據小數服從多數的原則，集群里正常節點只需要比 f 個節點再多一個節點，即 f+1 個節點，正確節點的數量就會比故障節點數量多，那麼集群就能達成共識。因此 raft 演算法支持的最大容錯節點數量是（n-1）/2。

對於 pbft 演算法，因為 pbft 演算法的除了需要支持容錯故障節點之外，還需要支持容錯作惡節點。假設集群節點數為 N，有問題的節點為 f。有問題的節點中，可以既是故障節點，也可以是作惡節點，或者只是故障節點或者只是作惡節點。那麼會產生以下兩種極端情況：

第一種情況，f 個有問題節點既是故障節點，又是作惡節點，那麼根據小數服從多數的原則，集群里正常節點只需要比f個節點再多一個節點，即 f+1 個節點，確節點的數量就會比故障節點數量多，那麼集群就能達成共識。也就是說這種情況支持的最大容錯節點數量是 （n-1）/2。
第二種情況，故障節點和作惡節點都是不同的節點。那麼就會有 f 個問題節點和 f 個故障節點，當發現節點是問題節點後，會被集群排除在外，剩下 f 個故障節點，那麼根據小數服從多數的原則，集群里正常節點只需要比f個節點再多一個節點，即 f+1 個節點，確節點的數量就會比故障節點數量多，那麼集群就能達成共識。所以，所有類型的節點數量加起來就是 f+1 個正確節點，f個故障節點和f個問題節點，即 3f+1=n。
結合上述兩種情況，因此 pbft 演算法支持的最大容錯節點數量是（n-1）/3

pbft 演算法的基本流程主要有以下四步：

客戶端發送請求給主節點
主節點廣播請求給其它節點，節點執行 pbft 演算法的三階段共識流程。
節點處理完三階段流程後，返回消息給客戶端。
客戶端收到來自 f+1 個節點的相同消息後，代表共識已經正確完成。
為什麼收到 f+1 個節點的相同消息後就代表共識已經正確完成？從上一小節的推導里可知，無論是最好的情況還是最壞的情況，如果客戶端收到 f+1 個節點的相同消息，那麼就代表有足夠多的正確節點已全部達成共識並處理完畢了。

3.演算法核心三階段流程
演算法的核心三個階段分別是 pre-prepare 階段（預准備階段），prepare 階段（准備階段）， commit 階段（提交階段）

流程的對比上，對於 leader 選舉這塊， raft 演算法本質是誰快誰當選，而 pbft 演算法是按編號依次輪流做主節點。對於共識過程和重選 leader 機制這塊，為了更形象的描述這兩個演算法，接下來會把 raft 和 pbft 的共識過程比喻成一個團隊是如何執行命令的過程，從這個角度去理解 raft 演算法和 pbft 的區別。

一個團隊一定會有一個老大和普通成員。對於 raft 演算法，共識過程就是：只要老大還沒掛，老大說什麼，我們（團隊普通成員）就做什麼，堅決執行。那什麼時候重新老大呢？只有當老大掛了才重選老大，不然生是老大的人，死是老大的鬼。

對於 pbft 演算法，共識過程就是：老大向我發送命令時，當我認為老大的命令是有問題時，我會拒絕執行。就算我認為老大的命令是對的，我還會問下團隊的其它成員老大的命令是否是對的，只有大多數人 （2f+1） 都認為老大的命令是對的時候，我才會去執行命令。那什麼時候重選老大呢？老大掛了當然要重選，如果大多數人都認為老大不稱職或者有問題時，我們也會重新選擇老大。
四、結語
raft 演算法和 pbft 演算法是私鏈和聯盟鏈中經典的共識演算法，本文主要介紹了 raft 和 pbft 演算法的流程和區別。 raft 和 pbft 演算法有兩點根本區別：

raft 演算法從節點不會拒絕主節點的請求，而 pbft 演算法從節點在某些情況下會拒絕主節點的請求 ;
raft 演算法只能容錯故障節點，並且最大容錯節點數為 （n-1）/2 ，而 pbft 演算法能容錯故障節點和作惡節點，最大容錯節點數為 （n-1）/3 。

pbft演算法是通過投票來達成共識，可以很好的解決包括分叉等問題的同時提升效率。但僅僅比較適合於聯盟鏈私有鏈，因為兩兩節點之間通信量是O(n^2)（通過優化可以減少通信量），一般來說不能應用於超過100個節點。
pbft有解的前提是 信道必須是可靠的 ，存在的問題是 可擴展性（scalability）差

部分來自： https://blog.csdn.net/kojhliang/article/details/80270223
區塊鏈在設計上就是為了BFT

4. 拜占庭協議

拜占庭將軍問題是指「在存在消息丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的」。因此在系統中存在除了消息延遲或不可送達的故障以外的錯誤，包括消息被篡改、節點不按照協議進行處理等，將會潛在地會對系統造成針對性的破壞。

改進型實用拜占庭容錯 （Practical Byzantine Fault Tolerance/PBFT）

PBET共識機制是少數服從多數，根據信息在分布式網路中節點間互相交換後各節點列出所有得到的信息，一個節點代表一票，選擇大多數的結果作為解決辦法。PBET將容錯量控制在全部節點數的1/3，即如只要有超過2/3的正常節點，整個系統便可正常運作。

授權拜占庭容錯演算法（Delegated Byzantine Fault Tolerance/dBFT）

dBFT，是基於持有權益比例來選出專門的記賬人（記賬節點），然後記賬人之間通過拜占庭容錯演算法（即少數服從多數的投票機制）來達成共識，決定動態參與節點。dBFT可以容忍任何類型的錯誤，且專門的多個記賬人使得每一個區塊都有最終性、不會分叉。

拜占庭協議採用的方法是確保可以通過分布式的方法達成共識，即使出現了拜占庭式的失敗也不會影響。「拜占庭失敗」指的則是分布式系統中演算法執行過程中的任意一個錯誤,也包括非理性的行為。

而聯邦拜占庭協議的主要特點是權力下放和任意行為容忍：

FBA帶來了開放的成員名單以及對拜占庭協議的去中心化控制；

任何人都可以加入其中；

通過分布式的方式，FBA使得法定人數或者節點足夠的群體能夠達成一致。每個節點決定信任對象，不同的節點也不需要依賴於信賴相同的參與者組合，即可完成共識。

非聯邦拜占庭協議的主要特點包括了中心化和任意行為容忍。它要求所有參與者對系統成員資源達成一致共識——這意味著這是一個中心化的系統。網路中的每個節點必須提前知曉且驗證過。

和非聯盟的拜占庭協議相比，比特幣設定理性行為者控制著大多數的計算能力，並通過分發硬幣來激勵潛在攻擊者遵守協議。因此，拜占庭協議可以抵禦擁有巨大計算能力的外部攻擊者，但是成員名單是非公開的。

而SCP靈感正是來源於比特幣。同時它從比特幣中汲取經驗，同時在低算力環境中擴展了對非理性行為的容忍能力。

5. 拜占庭問題與共識演算法

「拜占庭將軍問題」（Byzantine Generals Problem）是一個經典難題，這個難題是這樣描述的：拜占庭是東羅馬帝國的首都，它的軍隊分成多個師，每個師都由一個將軍統領。這些將軍通過信使進行交流，來達成一個共同作戰方案，有些將軍可能是叛徒，想故意破壞這個過程，這會造成那些忠誠的將軍也無法達成一個統一的作戰計劃。這個難題在於如何讓那些忠誠的將軍在這樣的情況下達成統一作戰方案，而避免那些叛徒對作戰方案的誤導。

在點對點、分布式的區塊鏈中，常常用拜占庭問題來比喻節點如何達成共識的問題。將軍即對應著一個個節點，達成統一作戰方案即達成共識，正確的打包與驗證區塊數據，防止惡意節點（叛徒將軍）破壞區塊鏈的運行。

顧名思義，就是能夠解決拜占庭問題，使各個節點達成共識，解決共識問題的各種機制也被稱為共識演算法。在各種各樣的共識演算法中，又一直存在一個「不可能三角」的難題，這三角是指「安全性」、「去中心化」和「速度」，也就是說難以同時保證速度、安全性和去中心化程度，三者之間往往會顧此失彼。

現在各種共識演算法算起來有好幾十種，計算機界也一直處於研究階段，並沒有說哪種演算法已經完美。
下面盤點一下講解pBET和POW兩種演算法，以及它們的「安全性」、「去中心化」和「速度」如何。

實用拜占庭容錯是一種較早的共識演算法。pBFT的一個原則，就是少數服從多數。節點通過在相互傳遞有關決策的消息，誰的決策贊同的人數多，就採用誰的。所以在這個系統中，安全性隨著誠實節點的數量而增加。誠實節點同意正確的決策，拒絕惡意節點的錯誤決策，只要惡意節點的數量少於總數的1/3，就能保證達成共識。

達成共識可以簡化為四步：

pBFT 使用投票機制以循環方式選舉領導節點。
領導者發起決策並將其廣播給輔助節點。
所有節點，包括領導節點和輔助節點，都發送響應。
當 ⅔ + 1 個節點發送相同的響應時，該響應被認為是有效的。

如果領導者有惡意行為，它可以被大多數節點刪除。

按少數服從多數的原則。那按理來說，只要惡意節點的數量少於1/2就夠了啊，那麼為什麼PBFT演算法的容錯數量要滿足惡意節點的數量少於總數的1/3呢？

因為 PBFT 演算法的除了需要支持容錯故障節點之外，還需要支持容錯作惡節點。假設集群節點數為 N，有問題的節點為 f。有問題的節點中，可以既是故障節點，也可以是作惡節點，或者只是故障節點或者只是作惡節點。那麼會產生以下兩種極端情況：

（1）這f 個有問題節點既是故障節點，又是作惡節點，那麼根據少數服從多數的原則，集群里正常節點只需要比f個節點再多一個節點，即 f+1 個節點，正確節點的數量就會比故障節點數量多，那麼集群就能達成共識，即總節點數為f+(f+1)=n，也就是說這種情況支持的最大容錯節點數量是 (n-1)/2。
（2）故障節點和作惡節點都是不同的節點。那麼就會有 f 個作惡節點和 f 個故障節點，當發現節點是作惡節點後，會被集群排除在外，剩下 f 個故障節點，那麼根據少數服從多數的原則，集群里正常節點只需要比f個節點再多一個節點，即 f+1 個節點，確節點的數量就會比故障節點數量多，那麼集群就能達成共識。所以，所有類型的節點數量加起來就是 f+1 個正常節點，f個故障節點和f個作惡節點，即 3f+1=n。

結合上述兩種情況，因此PBFT演算法支持的最大容錯節點數量是(n-1)/3，即少於1/3。

pBFT的優缺點
pBFT 系統不需要高計算資源或大量能源來運行。pBFT 在節點少的時候可以快速達成共識，因為所有節點都在不斷地相互通信。一旦節點就決策達成一致，交易就完成了。

然而，pBFT的缺點也很明顯：頻繁的通信使它只能在節點數量有限的網路中正常工作。隨著每個新節點加入網路，通信開銷呈指數增長，響應所需的時間也隨之增加。

pBFT 網路也容易受到女巫(Sybil)攻擊，女巫就是惡意黑客製造的不同節點，黑客可以控制多個節點，使其超過1/3，那系統將無法達成正確的共識。

從不可能三角的角度來看，由此可見pBFT在節點少的時候速度快，但安全性差，去中心化低；節點多了又會導致速度很慢。

中本聰設計了POW共識機制來解決上面pBFT這個經典共識的可擴展性問題。

上面說到，pBFT通過不斷廣播然後計算節點的消息數，時間花費過長。POW是怎麼做的：我不要計算節點數是否超過2/3，我直接選一個節點，按它的決策，其他節點全部同步它的決策。這樣就省去在全節點通信然後計算節點數的費時操作。

那麼，對於哪個節點來打包區塊，那就很重要，萬一是惡意節點呢？必須對打包的節點進行要求，哪個節點有權力進行打包呢？那就是解決復雜的數學問題，俗稱挖kuang。節點必須花費大量算力和電費來爭取某次打包區塊的權力。這樣的成本就限制了黑客的女巫攻擊。

如果打包區塊的權力真的被黑客搶到了，那可能會有什麼問題？

（1）竊取冰糖橙
黑客能夠竊取屬於另一個用戶，不受她控制的地址里的冰糖橙嗎？答案是否定的。即使這一輪是由黑客打包區塊鏈上的下一個區塊，她也不可能竊取別人的比特幣。這么做的話，黑客需要發起一筆有效的交易來轉移比特幣到自己的地址。這就要求黑客偽造比特幣擁有者的簽名，然而如果數字簽名機制是安全的，她是無法辦到的。只要背後的密碼學基礎是牢靠的，她就無法輕易竊取比特幣。
（2）拒絕服務攻擊
讓我們來考慮另一種攻擊。假設黑客不喜歡叫鮑勃的某個用戶，黑客可以決定她不把鮑勃發起的任何交易放進她所提議的區塊里。換言之，她拒絕提供服務給鮑勃。盡管這是黑客可以開展的有效的攻擊，但幸好這不過是個小問題。如果鮑勃的交易沒有被放進黑客所打包的下一個區塊，鮑勃只要等到下一個誠實節點發起區塊的時候，他的交易記錄就會被放進這個區塊里。所以這其實也不算是一個有效的攻擊。

也就是說，黑客花費重大成本取得的打包，但並不能起到有效的攻擊。由於對惡意節點進行懲罰、對誠實節點進行獎勵這樣的機制下，共識就達成了。

盡管有所改進，POW也引入了其他問題。工作量證明需要所有節點解決復雜的數學問題，這會消耗大量的能源，就是大家所熟知的挖kuang耗費電力。並且解決復雜的數學問題的時間也要求不短，10分鍾左右。

從不可能三角的角度來看，POW去中心化高，安全性高，但速度還是慢，但至少已經不會像pBFT那樣由於節點多導致花費時間呈指數增長。

共識演算法各式各樣，冰糖橙的POW並不是真正去解決分布式共識問題，它不能完美的套用到其他場景。但它在貨幣系統的這個特定場景下解決了冰糖橙的共識問題。POW在冰糖橙里運行得非常好。

6. 拜占庭容錯和PBFT共識演算法

實用的拜占庭容錯演算法
BFT 是區塊鏈共識演算法中，需要解決的一個核心問題。比特幣的POW，eos的dpos，以及共識演算法pos，這些公鏈演算法，解決的是共識節點眾多情況下的bft問題。

拜占庭將軍問題。也稱為拜占庭容錯。
用來描述分布式系統一致性問題。

背景如下：
拜占庭帝國想要進攻一個強大的敵人，為此派出了10支軍隊去包圍這個敵人。這個敵人雖不比拜占庭帝國，但也足以抵禦5支常規拜占庭軍隊的同時襲擊。這10支軍隊在分開的包圍狀態下同時攻擊。他們任一支軍隊單獨進攻都毫無勝算，除非有至少6支軍隊（一半以上）同時襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵騎馬相互通信來協商進攻意向及進攻時間。困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進攻意向或者進攻時間。在這種狀態下，拜占庭將軍們才能保證有多於6支軍隊在同一時間一起發起進攻，從而贏取戰斗？

單從上面的說明可能無法理解這個問題的復雜性，我們來簡單分析一下：

先看在沒有叛徒情況下，假如一個將軍A提一個進攻提議（如：明日下午1點進攻，你願意加入嗎？）由通信兵通信分別告訴其他的將軍，如果幸運中的幸運，他收到了其他6位將軍以上的同意，發起進攻。如果不幸，其他的將軍也在此時發出不同的進攻提議（如：明日下午2點、3點進攻，你願意加入嗎？），由於時間上的差異，不同的將軍收到（並認可）的進攻提議可能是不一樣的，這是可能出現A提議有3個支持者，B提議有4個支持者，C提議有2個支持者等等。

再加一點復雜性，在有叛徒情況下，一個叛徒會向不同的將軍發出不同的進攻提議（通知A明日下午1點進攻， 通知B明日下午2點進攻等等），一個叛徒也會可能同意多個進攻提議（即同意下午1點進攻又同意下午2點進攻）。

叛徒發送前後不一致的進攻提議，被稱為「拜占庭錯誤」，而能夠處理拜占庭錯誤的這種容錯性稱為「Byzantine fault tolerance」，簡稱為BFT。

使用密碼學演算法保證節點之間的消息傳送是不可篡改的， 通過下面的演算法我們可以保證A將軍收到B將軍發來的消息確實是B將軍本人的真實請求 。

我們採用的是哈希函數（散列演算法）SHA256 -- 從數據（byte）值中創建獨一無二的hash值，並壓縮成摘要，將數據格式固定下來。通過這個摘要與個人私鑰生成Digital Signature 和個人公鑰Public-key certificate，接收方驗證簽名和摘要，如果是通過驗證，即證明摘要內容沒有經過篡改。

pbft容忍無效或者惡意節點數量 e 。為了保證整個系統可以正常運作，需要有2f+1個正常節點，系統的總結點數為 ：3f+1。即pbft演算法容忍小於1/3的惡意或者無效節點。 原因見節點作惡的極端情況

pbft是一種狀態機副本復制演算法，所有副本在一個view輪換過程中操作，哪些是主節點（進攻的提議者的大將軍們，輪流當）通過view中其他節點（其他將軍）賦予的編號和節點數集合來確定，即：主節點p=v mod |R| 。 v：view編號，|R|節點個數，p：主節點編號。 關於狀態機復制演算法、view change的意義（主要是防止主節點作惡），主節點詳見論文。

基於拜占庭將軍問題，PBFT演算法一致性的確保主要分為這三個階段：預准備（pre-prepare）、准備(prepare)和確認(commit)。流程如下圖所示：

[圖片上傳失敗...(image-e3329d-1562488133052)]

首先解釋一下上面各個符號表達的意思：

下面結合上圖，詳細說一下PBFT的步驟：

根據上述流程，在 N ≥ 3F + 1 的情況下一致性是可能解決， N為總計算機數，F為有問題的計算機總數 。

下面所有的校驗流程略去對消息內容、簽名和身份的驗證，即已經保證了節點之間消息傳播是不可篡改的

上述演算法中，比較重要的一個點是view change，為了能恢復之前的請求，每一個副本節點收到消息之後或者發送消息的時候都會記錄消息到本地的log記錄中。當執行請求後，副本節點需要把之前該請求的記錄消息清除掉。最簡單的做法是在reply消息後，在執行一次當前狀態的共識同步，但是為了節省資源，一般在多條請求K後執行一次狀態同步。這個狀態同步就是checkpoint消息。

為了節省內存，系統需要一種將日誌中的 無異議消息記錄 刪除的機制。為了保證系統的安全性，副本節點在刪除自己的消息日誌前，需要確保至少 f+1 個正常副本節點執行了消息對應的請求，並且可以在視圖變更時向其他副本節點證明。另外，如果一些副本節點錯過部分消息，但是這些消息已經被所有正常副本節點刪除了，這就需要通過 傳輸部分或者全部服務狀態實現該副本節點的同步 。因此，副本節點同樣需要證明狀態的正確性。

在每一個操作執行後都生成這樣的證明是非常消耗資源的。因此，證明過程只有在請求序號可以被某個常數（比如100）整除的時候才會周期性地進行。我們將這些請求執行後得到的狀態稱作 檢查點（checkpoint） ，並且將具有證明的檢查點稱作 穩定檢查點（stable checkpoint） 。

上述情況是理想情況，實際上當副本節點i向其他節點發出checkpoint消息之後，其他節點還沒有完成K條請求的相互共識，所以不會立即對i的請求作出響應。其他節點會按照自己的處理步驟和順序，向前行進和共識。但是此時i發出的checkpoint沒有形成stable，為了防止i太快，超過自己太多，於是被便會設置一個高水位H=h+L，其中L就是我們指定允許的高度差，等於checkpoint周期處理數K的整數倍，可以設置為L=2K。當副本節點i處理請求超過高水位H時，副本節點即使接受到請求也會視為非法請求。等待stable checkpoint發生變化，再繼續向前推進處理。

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

我們在上面講到，當網路中有F台有問題的計算機時，至少需要3F+1台計算機才能保證一致性問題的解決，我們在這里討論一下原因。

我們可以考慮：由於有F個節點為故障或被攻擊的節點，故我們只能從N-F個節點中進行判斷。但是由於非同步傳輸，故當收到N-F個消息後，並不能確定後面是否有新的消息。（有可能是目前收到的N-F個節點的消息中存在被攻擊的節點發來的消息，而好的節點的消息由於非同步傳輸還沒有被收到。）

我們考慮最壞的情況，即剩下F個都是好的節點，收到的中有F個被攻擊的節點，故我們需要使得收到的中好節點的數量 (N-F)-F 大於被攻擊節點的數量 F ，於是有 N-2F>F ，即 N>3F ，所以N的最小整數為 N=3F+1 。

pbft是需要參與認證的節點進行的。所以一個完整的共識演算法包括DPOS+PBFT。其速度是可以達到1500tps左右的。

參考文獻：

https://mathpretty.com/9602.html

https://blog.csdn.net/jfkidear/article/details/81275974

Practical Byzantine Fault Tolerance

Miguel Castro and Barbara Liskov Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139 castro,liskov @lcs .mit.e

https://www.jianshu.com/p/fb5edf031afd 部分論文翻譯