1、PBFT算法Cuiting Shi, OneThing Tech LTD.Thursday, December 6, 2018 TOC o 1-5 h z HYPERLINK l bookmark13 o Current Document 背景-1 HYPERLINK l bookmark16 o Current Document PBFT算法模型3 HYPERLINK l bookmark22 o Current Document 2.1基本概念3三階段協議-4 HYPERLINK l bookmark38 o Current Document pre-prepare 階段6 HYPERLI

2、NK l bookmark46 o Current Document prepare 階段-7 HYPERLINK l bookmark53 o Current Document commit 階段8算法優化9 HYPERLINK l bookmark62 o Current Document 4.1檢查點協議9 HYPERLINK l bookmark69 o Current Document 4.2視圖變更協議11 HYPERLINK l bookmark72 o Current Document 4.2.1維持計時器11 HYPERLINK l bookmark75 o Current

3、Document 4.2.2請求視圖變更12 HYPERLINK l bookmark80 o Current Document 4.2.3切換到新視圖13 HYPERLINK l bookmark85 o Current Document PBFT算法應用15 HYPERLINK l bookmark88 o Current Document 參考161.背景通常情況下，分布式系統由很多節點組成，系統的可靠性要求系統必須具備應付異常節點發 送過來的不一致消息的能力。分布式的這個場景最早由Lamport，Shostak和Pease于 1982年形象地描述為拜占庭將軍問題(1Leslie Lam

4、port 1982)，即多個拜占庭將軍各自率 領了小分隊駐扎在敵方城市之外，他們需要對是否進攻敵軍達成統一的作戰計劃，但是這些 將軍之間存在反叛者，他們可能會篡改、延遲或者丟棄其他將軍的命令，迷惑其他可信將 軍。拜占庭將軍問題就是要找到一個算法來保證可信將軍之間能夠達成一致的作戰計劃。Lamport他們證明了對于拜占庭將軍問題，系統中如果存在f個不可信節點，那么只有總節 點數不少于3f + 1才存在一個算法解決該問題。下面我們來簡單地證明這個問題解的不可能 性，假設系統中總共有3個節點，Commander是提議者，記為C，Lieutenant 1和 Lieutenant 2是驗證節點，記為LT

5、1和LT2。這三個節點中存在一作惡節點，下面我們 證明在存在一個作惡節點的情況下，無論是提議者還是驗證節點，系統均無法達成統一的共 識。如圖1-1所示，假設C是作惡節點，另外兩個節點是可信節點。C向節點LT1和LT2發送 了相互矛盾的命令一進攻和撤退，那么LT1在接收到C發送過來的進攻命令和LT2轉發過 來的命令撤退，那么它就無法確定是要進攻還是撤退。Commander圖1-1提議者是作惡節點C said retreatretreatLieutenant2如圖1-2所示，假設LT2是作惡節點，節點C和LT1是可信節點，C要求LT1和LT2進 攻，但是LT2在轉發C的命令給LT1的時候作假，告訴

6、LT1它接收到C發過來的命令是撤 退，那么LT1在就無法判斷到底是要進攻還是撤退。圖1-2 Lieutenant 2是作惡節點從上述論證中我們可以直觀地覺察到3個節點的情況下，即使只有一個作惡節點，也無法達 成共識。但如果系統中多一個可信節點LT3，則LT1可以收到可信節點Commander發出 的和LT3轉發的進攻命令，即使LT2節點發出撤退命令，LT1也可以正確選擇跟大多數節 點一致的進攻命令，這樣系統能達成共識。我們可以將這個結論進行推廣，即對于存在f個 作惡節點的分布式系統，當節點總數不超過3f的時候，是不存在一個可以達成共識的解的， 嚴格的數學證明大家可以參考Lamport另夕卜一篇

7、關于拜占庭錯誤的論文(2M. Pease 1980)。學者們陸續提出了解決該問題的拜占庭容錯算法BFT，不是只能用于同步系統，就是性能太 差，難以在生產環境中廣泛運用。為了解決BFT的實際運用問題，MIT計算機實驗室的 Castro和Liskov于1999年在OSDI會議上提出了能夠在異步網絡環境中工作的PBFT算 法(3Miguel Castro 1999),在借鑒分布式系統的狀態機復制和quorum的基礎上設計了 三階段協議來解決一致性問題，同時引入了優化項，算法的復雜度由原來的指數級降低為多 項式級別。下面我們會講解PBFT算法的模型、算法流程、優化，其中算法流程即三階段協 議是PBFT

8、算法的核心算法流程，是我們的重點講解對象。2. PBFT算法模型PBFT算法本質上是一個狀態機復制算法，能夠用于實現帶有狀態和特定操作的任意確定性 狀態復制服務，它的目的是讓所有的可信節點執行相同的序列。此外，PBFT算法使用安全 的哈希函數對消息做摘要、使用公私鑰對消息進行簽名和驗簽、同時增加了消息驗證碼，保 證了消息的完整性和不可篡改性。在作惡節點總數不超過系統節點總數的1的情況下，PBFT3算法能夠保證系統的安全性和活性。PBFT算法主要包含三類基本協議：三階段協議：解決如何達成共識檢查點協議：類似于操作系統的還原點，主要用于垃圾回收視圖變更協議：用于解決主節點失效下不工作的情況2.1基

9、本概念首先我們了解一下PBFT算法的基本概念：主節點primary :負責對請求進行排序，發起新的請求副節點backup :負責驗證請求是否有效客戶端client :負責提出請求，要求節點執行某個操作，通常跟主節點合二為一序列號sequence number :請求的編號視圖view : 一個主節點和多個備份節點形成一個視圖檢查點checkpoint :如果某個序列號對應的請求收到了超過2的節點的確認，則稱為一個檢查點。3根據前面的討論，我們知道PBFT算法是用于解決拜占庭將軍問題的，所以系統要能夠容忍 /個作惡節點，則系統的總節點數不少于3f + 1個。假定系統中包含1個主節點和2f + 1

10、個 副節點。三階段協議三階段協議是PBFT算法的核心流程，用于解決系統的一致性問題，保證所有可信節點在給 定狀態和參數組的條件下，按照相同的順序執行完請求后能夠取得相同的狀態。三階段分別 為pre-prepare、prepare和commit階段，具體的執行流程圖如圖3-1所示，下面是正 常的流程：客戶端c在時間為t發送請求REQUEST, of t,叱給主節點，要求執行操作。Pre-prepare階段：主節點0對請求分配序列號：完成排序后將請求廣播給所有的 副節點prepare階段：副節點i驗證在接受到主節點的請求后，需要驗證請求和序列號在當 前的視圖中是否有效，將投票結果發給其他節點com

11、mit階段：每個節點在收到超過2/個副節點的投票信息之后，如果請求、序列 號和視圖均匹配，則生成一個提交信息發送給其他節點，表明接收了對應的請求。每個節點在收到超過f + 1個節點的提交信息后，將請求的發起時間仁請求的執行 結果廠和當前的視圖號v發送給客戶端c :REPLY, v, t, c,睥八。客戶端在接受執行結果r之前，需要阻塞等待/ + 1個節點白的響應，要求各個副本節 點i對于客戶端C的請求的響應中的簽名氣必須有效，同時這些響應中的各個結果 r以及請求的時間戳t需要相同。如果客戶端超時沒有收到響應，客戶端會廣播請求給系統中的所有節點。節點接收到重復的 請求的時候，如果已經處理過該請求

12、的話，那么會將響應再次發送給客戶端。同時，副本會 記錄下自己最近一次發送給客戶端的響應消息。此外，如果節點不是主節點的話，需要把請 求轉發給主節點。如果主節點不將請求廣播給副節點，當有足夠的副節點懷疑主節點是作惡 節點的時候，亦會引發視圖變更，將主節點替換掉。圖3-1 PBFT算法流程圖pre-prepare 階段主節點在收到客戶端的請求后，會基于當前的視圖u對請求分配編號n，將視圖號貝請求 序列號九、請求摘要d、簽名。封裝成pre-prepare消息PRE - PREPARE, vm,d、，記錄 到本地的消息日志中，然后將pre-prepare消息連同客戶端原始請求m發送給其他的副節 點，同

13、時追加到自己的消息日志中。注意，pre-prepare消息中，是不包含客戶端原本的請 求消息m的，而只是包含了該請求的摘要而已。pre-prepare階段主要是用來對請求進行 絕對排序，將請求傳輸和請求排序進行解耦，同時還可以證明在視圖變更協議中，主節點在 視點為u的時候把請求編號為n。. backup (PRE - PREPA RE, v,n, d舄，m)*I backupf I backup圖 3-2 pre-prepare 階段當副節點接受到主節點的pre-prepare消息的時候，在滿足如下的條件的情況下會接受該 消息。當前的視圖號也是u，即表明pre-prepare消息的發起者確實是

14、主節點客戶端請求m的摘要確實是pre-prepare消息中帶的摘要d，pre-prepare消息的簽名 是有效的。在當前視圖u中，序列號正還沒有被用過，即該節點沒有接受過編號同樣為n、但是請求 不是m的pre-prepare消息。序列號正不能過小、也不能過大，即nehtH，這個是為了防止一個主節點作惡，選擇 一個過大的序列號來惡意消耗完序列號空間。prepare 階段每個副節點在上一個階段驗證主節點的pre-prepare消息有效之后，會進入到prepare階段，生成一個prepare消息PREPARE, v,幾d,私記錄到本地，表明自己已經接受了主節點 的提議，同意在視圖u中把序列號九分配給

15、了客戶端請求m，保證自己在這個視圖中不會再將序列號分配給其他的客戶端請求，然后把prepare消息發送給其他節點。. r primary蜘叩5.5史瓜j叩I backup圖3-3準備階段對于各個節點發送過來的prepare消息PREPARE, v,幾d,凱，包括主節點在內的所有節點接受該消息的條件是：prepare消息的簽名氣正確當前節點的視圖號是/在視圖號u中，客戶端請求的編號不能過大過小，即neh,H算法的pre-prepare和prepare階段保證了系統中可信節點在視圖v中對于請求m的絕 對排序取得了共識。commit 階段當各個節點做好準備之后，即本地消息日志中記錄了摘要為d的請求m

16、、記錄了主節點對請 求血進行排序的pre-prepare消息，同時接收到了超過2f個其他節點發過來的有效的 prepare消息，各個節點會進入下一個階段，即commit階段。各個節點會生成一個視圖 為貝請求序列號為九、請求摘要為D(m)、簽名為氣的commit消息 COMMIT,v,n,D(rn)，mi追加到本地消息日志文件中，同時廣播給系統內的其他節點。圖3-4提交階段對于各個節點發送過來的commit消息，接受該消息的條件是：COMMIT消息的簽名是正確的當前節點的視圖號是v對于客戶端請求m的編號n e h, H上一個階段請求的摘要也是D(rn)，對這個請求的編號也是n提交階段保證了可信節

17、點就本地提交的客戶端請求的序列號取得了共識，即便這些客戶端請 求在每個節點是在不同的視圖號中提交的，保證了所有的可信節點按照給定的順序執行了所 有的客戶端請求，從而實現了安全性。當節點收到超過/ + 1個不同節點發送過來的 commit消息之后，會執行客戶端請求m中所要求的服務操作，同時將執行結果發送給客戶 端，這個保證了在可信節點中提交的任意一個客戶端請求，最終都會在另夕卜f + 1個節點中 被提交到本地的。算法優化4.1檢查點協議PBFT通過三階段協議來對請求達成共識，但是各個階段產生的消息如果不進行垃圾回收的 話，系統的存儲資源將會不堪重負。為此，PBFT算法設計了檢查點協議來丟棄本地的

18、消息 日志文件中的舊消息。垃圾回收的設計需要考慮何時該刪除消息，同時保證某個消息在可信 節點中都被刪除之后，某個節點在缺失這些消息的情況下在同步到最新的狀態后能夠證明這 個狀態是正確的。根據前面的三階段協議，我們可以知道客戶端收到某個請求的執行結果的時候，表明該請求 已經被至少/ + 1個節點提交過了，這個時候就可以刪除該消息了。對于第二個問題，檢查 點協議是通過提供額外的證據，checkpoint消息來證明這個狀態是正確的。但是如果每次 執行完一個客戶端請求之后都生成上述要求的證據，那么這個操作將是非常昂貴的。實際 上，PBFT的檢查點協議是周期性地生成這些證明，比如當請求的序列號整除周期T

19、的時 候。圖4-1檢查點協議如圖4-1所示，檢查點協議的的工作流程如下所示：當周期T到達的時候，各個節點會生成一個內容為最近一次執行的請求的摘要義請求編號為九、簽名為氣的checkpoint消息(CHECKPOINT, n, d, i)，追加到本地日志記錄 中，然后廣播給系統內的其他節點。氣各個節點接受到checkpoint消息后，驗證有效后會追加到本地的日志消息中。當各個節點在其消息日志中收集到了 2/ + 1個不同節點發送過來的有效的且狀態相同的 checkpoint消息的時候，那么表明這是一個穩定的檢查點stablecheckpoint，即2f + 1 個節點他們最后一次執行的請求都是一

20、樣的，而且都分配了序號隊當一個檢查點被證明是有效、穩定之后，那么節點會把本地消息日志中的消息中客戶端 請求序列號小于或者等于打的消息(pre-prepare、prepare, commit消息)都刪掉。 同時，它會刪掉舊的檢查點和checkpoint消息。檢查點協議除了用于垃圾回收外，還用于更新請求序列號的有效范圍，序列號的最低值h設 為最近一次檢查點里面的請求序列號，序列號的最高值設為H = h + K,其中k需要設置得大 點，比checkpoint的周期要大，不然節點收到序列號較大的請求之后需要阻塞等待到下 個檢查點才能處理。比如說，如果檢查周期是100個請求，那么k可以設置成200。4.

21、2視圖變更協議前面我們提到過，一些拜占庭算法不能解決主節點出故障的問題。PBFT算法是通過視圖變 更協議來允許系統在主節點出故障的情況下仍能夠正常運轉，從而保證了系統的活性。視圖 變更協議實際上是通過超時機制觸發的，通過超時機制，我們可以避免主節點不工作的情況 下，副節點無限期地等待客戶端請求被執行。假定系統當前狀態如圖4-2所示，視圖號為兀圖4-2視圖變更初始視圖v卜面我們來具體闡述一下視圖變更協議的具體工作流程。4.2.1維持計時器副節點會針對視圖能隹持一個計時器。當在收到主節點發送過來的一個有效的請求而且沒有 執行的時候，如果是針對當前視圖的計時器還沒有啟動的話，那么節點會啟動一個新的計

22、時 器。如果節點還在執行其他請求的話，那么節點會重置該請求的計時器。如果節點不再等待 執行該請求的時候，會停止視圖u的計時器。4.2.2請求視圖變更如圖4-3所示，當副節點的視圖u的計時器如果超時了，就會生成一個view-change消 息，記錄到本地日志文件中，同時廣播給其他節點，要求替換掉主節點，變更到下一個視圖 u + 1。注意，在視圖變更期間，除了 checkpoint, view-change和newview消息之外， 備份節點i是不會接受其他消息的。圖4-3視圖變更計時器超時，發起視圖變更view-change消息的具體內容為以W - CHANGE, v + 1,n, , P, i

23、)，其中最近一次的穩定 檢查點對應的請求的序列號， 是證明該檢查點穩定性的2/ + 1個 checkpoint消息的集 合，/是Pm的集合，其中血是副節點i中的序列號大于打的等待提交和執行的客戶端請求m。每個九包含了如下的信息：不包含原始請求m的pre-prepare消息，不過不包含原始的客戶端請求m ,2f個由其他副節點簽名的跟pre-prepare消息匹配的、有效的prepare消息(匹配 有效指的是prepare消息中的簽名有效，在視圖u中分配給請求的序列號一致，客戶 端請求摘要D(rn)相同)各個節點收到view-change消息后，會檢驗該消息是否有效，如果有效的話，會追加到本 地的

24、日志文件中。4.2.3切換到新視圖如圖4-4所示，當新視圖v + 1對應的新的主節點接收到2/個節點的發送過來的有效的 view-change消息之后，會向其他節點發送一個帶上自己簽名。，的new-view消息，提 議系統內所有節點切換到下一個視圖u + 1，同時接受自己成為新的主節點。這個new- view 消息的另夕卜一個作用是找到所有節點的共同的穩定檢查點，同時針對那些攜帶了尚未 提交執行的請求的prepare消息重新生成相應的pre-prepare消息，這個主要是在切換到 新視圖之后，新的主節點需要重新對這些未處理的請求分配序列號，然后對這些請求再次執 行一遍三階段協議。其中，new-

25、view消息的具體格式為NEW VIEW, v + 1,V, 0):V是主節點加本地日志中保留的所有要求由視圖U變更為視圖U + 1的有效vew- change消息的集合。0是一個沒有攜帶客戶端原始請求m的pre-prepare消息的集合，這些preprepare 消息中對應的請求都是在上一個視圖u都是有效的，但是還沒有處理完的。圖4-4視圖變更新的主節點發起新視圖副節點在收到要求將視點變更為v + 1的new-vew消息之后，在確認消息有效之后，會接 受該new-view消息，記錄到本地消息文件中，同時將視點更換到新的視點u + 1。此外， 副節點還會new-view中攜帶的由新的主節點重新生成的pre-prepare消息都追加記錄到 本地的消息日志中，并按照檢查點協議進行垃圾回收，刪除比較老的消息。然后，對于 new-vew消息中集合。中攜帶的所有由新主節點生成的新的pre-prepare消息，備份節點 都會生成相應的prepare消息，記錄到本地日志文件中，轉發給其他節點，即對這些未處 理的請求在新的視圖中重新執行一遍三階段協議，保證視圖切換過程中未處理的請求能夠重 新被處理。5. PBFT