go語言pbft算法實現的簡單介紹

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

對數據順序達成一致共識是很多共識算法要解決的本質問題

創新互聯提供網站建設、成都做網站、網頁設計，品牌網站制作，1元廣告等致力于企業網站建設與公司網站制作，10年的網站開發和建站經驗,助力企業信息化建設，成功案例突破近1000家,是您實現網站建設的好選擇.

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算法介紹的很透徹，鏈接地址為： 。這個動畫主要包含三部分內容，第一部分介紹簡單版的領導者選舉和日志復制的過程，第二部分內容介紹詳細版的領導者選舉和日志復制的過程，第三部分內容介紹的是如果遇到網絡分區（腦裂），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）差

部分來自：

區塊鏈在設計上就是為了BFT

區塊鏈筆記——PBFT

PBFT是實用拜占庭容錯的簡稱，是解決拜占庭將軍問題的一種方案。比起最開始的BFT算法，PBFT額外要求網絡封閉，即節點數目確定并提前互通，但將復雜度從指數級降低到多項式級，使得BFT系列算法真正具有可行性。

與POW、POS等大家耳熟能詳的共識不同，BFT系列的共識不需要“Proof”，亦即不需要節點投入算力或其他資源來確權，因此不需要代幣激勵便可完成共識。缺點是原始的BFT效率太低，只能存在于理論而無法應用。而改進的PBFT雖然效率大大提高，卻對節點數量和狀態提出了要求，導致合格的記帳節點太少，并且也只能維持在少數，過多的節點會拖慢網絡速度。因此PBFT更多是用在聯盟鏈和私鏈上。公鏈也有應用，例如NEO，便是采用了PBFT算法。

拜占庭將軍問題的實質是在惡劣的通訊環境中，如何使各參與方達成一致意見。POW和POS等共識要求參與方投入成本，爭奪唯一的發言權。在某一段時間內只有唯一的發言人，自然只會有一個意見，從而達成共識。PBFT采取不同的思路，要求各參與方相互發送及驗證彼此的信息，最終采用多數原則達成共識。

PBFT能夠以一種低成本的方式實現節點間共識，其理念其實相當貼近我們的生活習慣。例如在老師布置作業后，同學們總要互相問問確認一下，才放心地把今天的作業記到本子上。當然實現上還有很多細節，保證各節點的平等關系。在節點數目不多的時候，節點之間實現相互通信的成本并不高，節點之間可以快速發送確認。但節點數目增長卻會帶來整體性能的下降。PBFT可以容忍的壞節點數量不多于總數的三分之一，如果節點損壞率比較固定，提高總節點數量雖然能使系統獲得更好的冗余，卻會大大增加通訊量，造成效率下降。加上PBFT沒有激勵機制，其適合聯盟鏈和私鏈場景。作為公鏈不可避免地節點數量太少，分布過分集中，例如NEO只有七個節點。

PBFT要求壞節點數量f=(n-1)/3，這里n是總節點數。只要f滿足這個條件，共識總是可以達成。為什么f要滿足這個條件？簡單來說，假設網絡中存在惡意節點聯盟，其控制了數量為f的節點，這些節點可以故意發布錯誤的信息。此時網絡中正常節點數量為n-f個。將這n-f個節點分為兩部分，各自包含一部分節點。對于任一部分正常節點來說，只要惡意節點數f大于自身節點數，同時大于剩余的正常節點數，這部分正常節點便會與惡意節點聯盟達成共識。此時只要惡意節點聯盟先后向兩部分正常節點發送不同的共識信息，便可造成網絡分叉。因此要保證網絡運行，對于每一部分正常節點來說，網絡中惡意節點數量不能同時大于自身節點數和網絡剩余正常節點數。代入計算便得到f=(n-1)/3。

實用拜占庭容錯算法（PBFT）

?拜占庭帝國即東羅馬帝國，擁有巨大的財富，并對鄰邦垂誕已久，為此派出了10支軍隊去包圍這個敵人。這個敵人雖不比拜占庭帝國，但也足以抵御5支常規拜占庭軍隊的同時襲擊。基于一些原因，這10支軍隊不能集合在一起單點突破，必須在分開的包圍狀態下同時攻擊。他們任一支軍隊單獨進攻都毫無勝算，除非有至少6支軍隊同時襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵相互通信來協商進攻意向及進攻時間。困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進攻意向或者進攻時間。在這種狀態下，拜占庭將軍們能否找到一種分布式的協議來讓他們能夠遠程協商，從而贏取戰斗？這就是著名的拜占庭將軍問題【在分布式系統中指的是消息不僅可以被丟失、延遲、重放，還可以被偽造】。

? ? PBFT(Practical Byzantine Fault Tolerance)算法由Miguel Castro 和Barbara Liskov在1999年提出來的，解決了原始拜占庭容錯算法效率不高的問題，將算法復雜度由指數級降低到多項式級，使得拜占庭容錯算法在實際系統應用中變得可行。

? ? PBFT是一種狀態機副本復制算法，一般包括三種協議:一致性協議(agreement)、檢查點協議(checkpoint)和視圖更換協議(view change)。該算法要滿足以下兩個性質：? ?

? ? 安全性(safety)：safety means nothing bad happens.? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 活性(liveness)：liveness means that something good eventually happens.

? ? 在一個拜占庭系統里面，要容忍f個拜占庭節點錯誤，則replica數量至少為3f+1，這是滿足安全性的前提。因為網絡延遲或宕機，系統存在f個節點不回復響應（f個節點包括拜占庭節點和非拜占庭節點，最壞情況f個節點全是非拜占庭節點），剩下2f+1個響應中可能有f個拜占庭節點，從而得到n-2ff，即響應中非拜占庭節點數目大于拜占庭節點數目（f+1f）。

? ? 算法不依賴同步提供安全性，則必須依賴同步提供活性，否則違背FLP定理(在異步通信場景，即使只有一個進程失敗了，沒有任何算法能保證非失敗進程能夠達到一致性)。在拜占庭節點不超過f，并且delay(t)有界的情況下就能保證系統活性，delay(t)表示從消息發送到接受的時間間隔。

? ? 在一個view里面，會從replicas中選擇一個primary，其余的replicas則叫backups。如果主節點行為發生異常，則進行view change換主。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ?游戲從client向primary發送請求 開始。 狀態機操作， 時戳。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?游戲從client至少收到f+1個replicas的響應 結束。 視圖編號， 時戳， 客戶端身份， replica編號， 請求結果。【why f+1？因為在2f+1個committed中有f個拜占庭節點表面上同意請求，實際上根本不會回復請求】

3.1 重彩大戲------三階段協議

Pre-prepare:

? ? Primary為客戶端請求分配一個序列號n，向所有backups發現預準備消息 。 視圖編號， 消息 的摘要。

Prepare:

? ? 若滿足以下條件，backups接受預準備消息：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1.客戶端請求和預準備消息具有正確簽名。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2.當前視圖編號是v。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3.backups從未在當前視圖v接收過序列號為n但摘要不同的預準備請求。? ? ? ? ? ? ? ? ? ? ? ? ? 4.hnH。【防止一個拜占庭節點選擇一個大的序號來消耗序號空間】

? ? 如果上述條件滿足，backups接收預準備消息，進入prepare階段，向其他節點廣播準備消息 ，并將預準備和準備消息寫入日志。

commit:

? ?如果backups收到2f【包括自己】個與預準備消息一致的準備消息，請求消息和預準備消息具有相同的視圖v和序列號n，并且已將相關消息寫入日志，則進入commit階段，向其他節點廣播一條確認消息 。如果各節點收到2f+1條相同的commits消息，則向客戶端發送一條reply消息。

3.2 垃圾回收

? PBFT是一種狀態機副本復制算法，replicas會將執行過消息記錄在本地日志中，為了節省內存，需要一種機制來清理日志。何時來清理？在每次操作完后執行是不明智的，因為比較耗資源。可以定期清理，比如每100次清理一次。我們將請求后執行的狀態稱為檢查點checkpoint；帶證明的檢查點稱為stable certificate，當節點收到2f+1個checkpoint消息時，可證明穩定檢查點是正確的。穩定檢查點之前的日志消息均可刪除。? ? ? ? ? ? ? ? ? ? ? ?

? 當清理檢查點時replica i向其他replicas廣播一條檢查點協議 ， 是最近一次正確執行請求序號， 是其當前狀態摘要。如果每一個replica收到2f+1個具有相同序號 和摘要 的檢查點消息，這時每一個replica可以清理序列號 小于等于n的日志信息。

? ?檢查點協議也用來更新水平線。低水平線 等于最近穩定檢查點的序號，高水平線 ， 為日志大小。

3.3 視圖更改

? ? 當主節點掛掉，或者在commit階段有些節點收到2f+1個commit，有些沒有收到2f+1個commit，導致狀態不一致，這些狀況都需要更改視圖來提供系統活性和安全性。

? ? 當請求超時，備份節點進入視圖v+1，廣播視圖更改消息 。 穩定檢查點序列號， 是穩定檢查點證明， 是一個集合，包含對請求 （請求的序列號大于 ）相關消息集合 。 包含2f+1個相同的準備消息。

? ? ?當視圖v+1的主節點收到2f個相同個視圖更改消息，向其他副本廣播新視圖消息 ， 是2f+1個視圖更改消息， 的計算規則如下：? ? ? ? 1.確定序列號 和 。其中 等于 中穩定檢查點序列號, 等于 中最大prepare消息序列號。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2.主節點為 和 之間的每一個序列號n分配pre-prepare消息。如果 中包含n對應的 組合，則對應的預準備消息為 （也就是說序列號n對應的請求有2f+1個prepare消息，在新視圖中依然提交這個請求）。如果 中不包含n對應的 組合，則提交null消息為 ，即不做任何處理。

? ? 副本收到新視圖消息后，廣播一次prepare消息，進入v+1，視圖更換完成。

拜占庭共識算法

拜占庭共識算法有一個前提：

安全節點數 R(eliable) 大于不安全節點數 E(vil)。而且理想情況下R方希望投票結果是統一的。

所以結合兩個不等式

P R/2 +E

P R

得出

R R/2 + E

這就可推測出

R + R/2 R + E

(3/2) R ALL(總節點數)

辣么 R ALL(2/3)

所以當安全節點數 R(eliable) 大于總節點的(2/3)時，投出來的票才是可靠的

然后，祭出拜占庭投票的流程，以及算法模擬流程

其中D為發送請求端，R0 R1 R2 R3為服務端：

最后本來想自己寫個實現的，但是Java實現太重量級了，貼個別人用Go語言實現的吧

網頁標題：go語言pbft算法實現的簡單介紹
分享地址：http://m.kartarina.com/article28/hiiccp.html

成都網站建設公司_創新互聯，為您提供標簽優化、微信公眾號、微信小程序、營銷型網站建設、網站設計、網站導航

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯