相互共識演算法

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

「拜占庭將軍問題」（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在冰糖橙里運行得非常好。

B. 共識演算法系列之一：私鏈的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