區塊鏈之PBFT算法區塊鏈
使用拜占庭容錯算法不需要發行加密貨幣，但是只能用于私有鏈或者聯盟鏈，需要對節點的加入進行權限控制；不能用于公有鏈，因為公有鏈中所有節點都可以隨意加入退出，無法抵擋女巫攻擊（sybilattack）。下面主要介紹Fabric的PBFT算法。
在公有鏈中用的最多的是pow算法和pos算法，這些算法都是參與者的利益直接相關，通過利益來制約節點誠實的工作，解決分布式系統中的拜占庭問題。拜占庭容錯算法是一種狀態機副本復制算法，通過節點間的多輪消息傳遞，網絡內的所有誠實節點就可以達成一致的共識。使用拜占庭容錯算法不需要發行加密貨幣，但是只能用于私有鏈或者聯盟鏈，需要對節點的加入進行權限控制；不能用于公有鏈，因為公有鏈中所有節點都可以隨意加入退出，無法抵擋女巫攻擊（sybil attack）。下面主要介紹Fabric的PBFT算法。
01系統模型
該系統要達成的目的是：讓所有正常的replicas節點執行相同的序列操作。
1、系統假設是異步分布式的，通過網絡傳播的消息可能丟失、延遲、重復或亂序，節點可能失效但節點失效是相互獨立的。傳遞的消息都是通過簽名的，惡意節點可以控制失效節點，但是不能夠篡改正常節點的簽名信息。
2、安全性：在R>=3f 1的前提下，系統能保持安全性和活性。R為總結點數，f為錯誤節點數。
3、角色分工：
replica（副本）所有參與的節點，總數為R
primary（主節點）：負責將來自client的請求排好序，然后發給所有的備份節點。
backup（備份節點）：接收并檢查主節點的排序信息，如果主節點作惡可以進行換選。
其中主節點的選舉方法是：p = v mod R ，其中v是系統的view編號，每次換選時發生view change，view編號 1。
4、quorums
quorums有兩個重要的屬性：
1)Intersection： 任意兩個quorums至少有一個共同的并且正確的replica
2)Availability: 總是存在一個沒有faulty replicas的quorum
如果一個replica把信息寫給一個quorum，并讓該quorum來存儲信息，在收到每一個quorum中的成員的確認反饋后，那么我們可以認為該replica的信息已經被可靠的保存在了這個分布式系統中。這是強的約束，當然還有一個weak certificates：就是至少f 1個節點來共同存取信息，這樣至少有一個正確的replica存到了這份信息。
02算法流程
PBFT算法通過三階段廣播協議來使所有正常節點按相同的順序執行請求，三階段分別為pre-prepare、prepare和commit。執行流程如圖所示。
prepare階段和commit階段用來確保那些已經達到commit狀態的請求即使在發生view change后在新的view里依然保持原有的序列不變，比如一開始在view 0中，共有req 0， req 1， req2三個請求依次進入了commit階段，假設沒有壞節點，那么這四個replicas即將要依次執行者三條請求并返回給Client。但這時主節點問題導致view change的發生，view 0 變成 view 1，在新的view里，原本的req 0， req1， req2三條請求的序列被保留，作數。那些處于pre-prepare和prepare階段的請求在view change發生后，在新的view里都將被遺棄，不作數。
假設replica 0為主節點，下面詳細介紹三階段：
pre-prepare階段
主節點收到client發送的一條請求，給這條請求編號為n，然后想所有的備份節點發送pre-prepare消息，消息的格式為<<pre-prepare, v, n, d>, m>，其中v是視圖view編號，m是請求的消息，d是請求消息的摘要。當滿足一下條件時，備份節點會接受這條pre-prepare消息，進入prepare階段。
1、請求和預準備消息的簽名正確，并且d與m的摘要一致。
2、當前視圖編號是v。
3、該備份節點從未在視圖v中接受過序號為n但是摘要d不同的消息m。
4、預準備消息的序號n必須在水線（watermark）上下限h和H之間。
prepare階段
備份節點i進入prepare階段后，發送一條prepare消息給所有的副本節點，消息格式為<prepare, v, n, d, i>，同時接收其他節點發送的prepare消息。
所有副本節點在收到準備消息之后，對消息的簽名是否正確，視圖編號是否一致，以及消息序號是否滿足水線限制這三個條件進行驗證，如果都正確則接受。（這個階段是防止主節點作惡）如果從2f個不同的副本收到的prepare消息與pre-prepare消息一致，即連同自己一共2f 1個確認，那么這個節點就處于prepared狀態，同時擁有一個prepared certificate證書。然后進入commit階段。
預準備階段和準備階段確保所有正常節點對同一個視圖中的請求序號達成一致。
commit階段
進入commit階段的節點i會廣播一條commit消息給其他所有節點，消息格式為<commit, v, n, D(m), i>,同時接收其他節點發送的commit消息，每個副本接受確認消息的條件是：
1）簽名正確；
2）消息的視圖編號與節點的當前視圖編號一致；
3）消息的序號n滿足水線條件，在h和H之間。
如果滿足以上條件，則接受消息。如果從不同的節點收到2f 1（包括自己）條commit消息且都正確，那么這個節點進入committed狀態，并擁有一個committd certificate。然后向客戶端返回請求。
其中watermark的作用是：
我們想象一種情況，主節點是壞的，它在給請求編號時故意選擇了一個很大的編號，以至于超出了序號的范圍，所以我們需要設置一個低水位（low water mark）h和高水位（high water mark）H，讓主節點分配的編號在h和H之間，不能肆意分配。
三階段到此結束，客戶端等待f 1個相同的副本結果作為最后結果。
03垃圾回收
節點在一次三階段協議中收到的pre-prepre,prepare,commit等消息是非常多的,這小消息都要記錄在本地的日志中，為了節省存儲空間,可以把已經確認無誤的消息給清除掉。只有當至少f 1個節點執行了請求的消息的時候，才能將相應的日志刪除。
于是，當一個節點執行完某條請求后，可以廣播一條消息，當全網有2f 1個節點都執行完這條請求后就可以刪除它的日志了。但是每條消息都進行廣播來確認是否刪除是低效的，所以可以k條消息放一起確認，每當k條請求執行完后，就廣播一條消息，當2f 1個節點都執行完這個請求后，就可以將這k條請求的日志刪除了。
這就是建立檢查點checkpoint，當節點i執行完k條請求后，就生成一個checkpoint，并廣播checkpoint消息：<CHECKPOINT, n, d, i>，n是最近一個影響狀態的請求序號，d是狀態的摘要。當有2f 1個檢查點消息時，就證明這個檢查點是正確的，形成一個stable checkpoint。具有這個stable checkpoint的節點就可以將所有序號小于等于n的pre-prepare,prepare,commit消息，以及之前的檢查點和檢查點消息刪除。
但是由于節點的執行速度不同，要使不同的節點的檢查點維持在一個范圍內，最快的幾點與最慢的節點之間最多差L個檢查點。這里又用到了水線watermark，用檢查點協議來更新水線的高低值（h和H），這兩個高低值限定了可以被接受的消息。水線的低值h與最近穩定檢查點的序列號相同，而水線的高值H=h L，L需要足夠大才能使副本不至于為了等待穩定檢查點而停頓。
04視圖變更
當主節點掛掉后就觸發了view change協議。我們需要確保在新的view中如何來延續上一個view最終的狀態，比如給這時來的新請求的編號，還有如何處理上一個view還沒來得及完全處理好的請求。
Data Structures
所以我們需要記錄上一個view里發生什么。
有兩個集合P和Q，replica i 的P存著 i 在上一 view 中達到prepared狀態的請求的一些信息，有了P，在新的view中，replica i就會明白接下來處于prepared狀態的請求不能與上一個view中處于prepared狀態的請求的編號相同。Q是記錄在上一個view里到達pre-prepared狀態的請求的一些信息。
View-Change Messages
我們來看一下Fig 2， 當備份節點 i 懷疑 view v中的主節點出問題（比如是壞節點）后，它會進入 view v 1，并廣播一條VIEW-CHANGE信息給所有的replicas，其中包含該replica i最新的stable checkpoint的編號，還有 replica i上存的每一個checkpoint的編號和digest的集合，還有上面所說的該replica的P和Q兩個集合。
View-Change-Ack Messages
replicas 會收集VIEW-CHANGE信息并發送ACK確認給 view v 1 中的主節點。
新的主節點收集了VIEW-CHANGE和VIEW-CHANGE-ACK（包含自己的信息），它會將VIEW-CHANGE存在一個集合S中。主節點需要選出一個checkpoint作為新view處理請求的起始狀態。它會從checkpoint的集合中選出編號最大（假設編號為h）的checkpoint。接下來，主節點會從h開始依次選取h到h L（L就是normal case階段我們提到的設置值）之間的編號n對應的請求在新的view中進行pre-prepare，如果一條請求在上一個view中到達了committed狀態，主節點就選取這個請求開始在新的view中進行三階段。
之所以選取committed的請求，是因為上面我們提到增加COMMIT階段為了across view來考慮的，處于committed狀態的請求的編號在新的view中是有效的，可以繼續使用。但是如果選取的請求在上一view中并沒有被一個quorum給prepare，那它的編號n有可能是不被一個quorum給同意的，我們選擇在新的view中作廢這樣的請求。
參考文章：
https://blog.csdn.net/bluecloudmatrix/article/details/51898105?utm_source=tuicool&utm_medium=referral#commentBox
https://www.jianshu.com/p/fb5edf031afd
1.TMT觀察網遵循行業規范，任何轉載的稿件都會明確標注作者和來源；
2.TMT觀察網的原創文章，請轉載時務必注明文章作者和"來源：TMT觀察網"，不尊重原創的行為TMT觀察網或將追究責任；
3.作者投稿可能會經TMT觀察網編輯修改或補充。
