TMT观察网_独特视角观察TMT行业

在公有鏈中用的最多的是pow算法和pos算法，這些算法都是參與者的利益直接相關(guān)，通過利益來制約節(jié)點(diǎn)誠實(shí)的工作，解決分布式系統(tǒng)中的拜占庭問題。拜占庭容錯(cuò)算法是一種狀態(tài)機(jī)副本復(fù)制算法，通過節(jié)點(diǎn)間的多輪消息傳遞，網(wǎng)絡(luò)內(nèi)的所有誠實(shí)節(jié)點(diǎn)就可以達(dá)成一致的共識(shí)。使用拜占庭容錯(cuò)算法不需要發(fā)行加密貨幣，但是只能用于私有鏈或者聯(lián)盟鏈，需要對(duì)節(jié)點(diǎn)的加入進(jìn)行權(quán)限控制；不能用于公有鏈，因?yàn)楣墟溨兴泄?jié)點(diǎn)都可以隨意加入退出，無法抵擋女巫攻擊（sybil attack）。下面主要介紹Fabric的PBFT算法。

01系統(tǒng)模型

該系統(tǒng)要達(dá)成的目的是：讓所有正常的replicas節(jié)點(diǎn)執(zhí)行相同的序列操作。

1、系統(tǒng)假設(shè)是異步分布式的，通過網(wǎng)絡(luò)傳播的消息可能丟失、延遲、重復(fù)或亂序，節(jié)點(diǎn)可能失效但節(jié)點(diǎn)失效是相互獨(dú)立的。傳遞的消息都是通過簽名的，惡意節(jié)點(diǎn)可以控制失效節(jié)點(diǎn)，但是不能夠篡改正常節(jié)點(diǎn)的簽名信息。

2、安全性：在R>=3f 1的前提下，系統(tǒng)能保持安全性和活性。R為總結(jié)點(diǎn)數(shù)，f為錯(cuò)誤節(jié)點(diǎn)數(shù)。

3、角色分工：

replica（副本）所有參與的節(jié)點(diǎn)，總數(shù)為R

primary（主節(jié)點(diǎn)）：負(fù)責(zé)將來自client的請(qǐng)求排好序，然后發(fā)給所有的備份節(jié)點(diǎn)。

backup（備份節(jié)點(diǎn)）：接收并檢查主節(jié)點(diǎn)的排序信息，如果主節(jié)點(diǎn)作惡可以進(jìn)行換選。

其中主節(jié)點(diǎn)的選舉方法是：p = v mod R ，其中v是系統(tǒng)的view編號(hào)，每次換選時(shí)發(fā)生view change，view編號(hào) 1。

4、quorums

quorums有兩個(gè)重要的屬性：

1)Intersection： 任意兩個(gè)quorums至少有一個(gè)共同的并且正確的replica

2)Availability: 總是存在一個(gè)沒有faulty replicas的quorum

如果一個(gè)replica把信息寫給一個(gè)quorum，并讓該quorum來存儲(chǔ)信息，在收到每一個(gè)quorum中的成員的確認(rèn)反饋后，那么我們可以認(rèn)為該replica的信息已經(jīng)被可靠的保存在了這個(gè)分布式系統(tǒng)中。這是強(qiáng)的約束，當(dāng)然還有一個(gè)weak certificates：就是至少f 1個(gè)節(jié)點(diǎn)來共同存取信息，這樣至少有一個(gè)正確的replica存到了這份信息。

02算法流程

PBFT算法通過三階段廣播協(xié)議來使所有正常節(jié)點(diǎn)按相同的順序執(zhí)行請(qǐng)求，三階段分別為pre-prepare、prepare和commit。執(zhí)行流程如圖所示。

prepare階段和commit階段用來確保那些已經(jīng)達(dá)到commit狀態(tài)的請(qǐng)求即使在發(fā)生view change后在新的view里依然保持原有的序列不變，比如一開始在view 0中，共有req 0， req 1， req2三個(gè)請(qǐng)求依次進(jìn)入了commit階段，假設(shè)沒有壞節(jié)點(diǎn)，那么這四個(gè)replicas即將要依次執(zhí)行者三條請(qǐng)求并返回給Client。但這時(shí)主節(jié)點(diǎn)問題導(dǎo)致view change的發(fā)生，view 0 變成 view 1，在新的view里，原本的req 0， req1， req2三條請(qǐng)求的序列被保留，作數(shù)。那些處于pre-prepare和prepare階段的請(qǐng)求在view change發(fā)生后，在新的view里都將被遺棄，不作數(shù)。

假設(shè)replica 0為主節(jié)點(diǎn)，下面詳細(xì)介紹三階段：

pre-prepare階段       

主節(jié)點(diǎn)收到client發(fā)送的一條請(qǐng)求，給這條請(qǐng)求編號(hào)為n，然后想所有的備份節(jié)點(diǎn)發(fā)送pre-prepare消息，消息的格式為<<pre-prepare, v, n, d>, m>，其中v是視圖view編號(hào)，m是請(qǐng)求的消息，d是請(qǐng)求消息的摘要。當(dāng)滿足一下條件時(shí)，備份節(jié)點(diǎn)會(huì)接受這條pre-prepare消息，進(jìn)入prepare階段。

1、請(qǐng)求和預(yù)準(zhǔn)備消息的簽名正確，并且d與m的摘要一致。

2、當(dāng)前視圖編號(hào)是v。

3、該備份節(jié)點(diǎn)從未在視圖v中接受過序號(hào)為n但是摘要d不同的消息m。

4、預(yù)準(zhǔn)備消息的序號(hào)n必須在水線（watermark）上下限h和H之間。

prepare階段      

備份節(jié)點(diǎn)i進(jìn)入prepare階段后，發(fā)送一條prepare消息給所有的副本節(jié)點(diǎn)，消息格式為<prepare, v, n, d, i>，同時(shí)接收其他節(jié)點(diǎn)發(fā)送的prepare消息。

所有副本節(jié)點(diǎn)在收到準(zhǔn)備消息之后，對(duì)消息的簽名是否正確，視圖編號(hào)是否一致，以及消息序號(hào)是否滿足水線限制這三個(gè)條件進(jìn)行驗(yàn)證，如果都正確則接受。（這個(gè)階段是防止主節(jié)點(diǎn)作惡）如果從2f個(gè)不同的副本收到的prepare消息與pre-prepare消息一致，即連同自己一共2f 1個(gè)確認(rèn)，那么這個(gè)節(jié)點(diǎn)就處于prepared狀態(tài)，同時(shí)擁有一個(gè)prepared certificate證書。然后進(jìn)入commit階段。

預(yù)準(zhǔn)備階段和準(zhǔn)備階段確保所有正常節(jié)點(diǎn)對(duì)同一個(gè)視圖中的請(qǐng)求序號(hào)達(dá)成一致。

commit階段

進(jìn)入commit階段的節(jié)點(diǎn)i會(huì)廣播一條commit消息給其他所有節(jié)點(diǎn)，消息格式為<commit, v, n, D(m), i>,同時(shí)接收其他節(jié)點(diǎn)發(fā)送的commit消息，每個(gè)副本接受確認(rèn)消息的條件是：

1）簽名正確；

2）消息的視圖編號(hào)與節(jié)點(diǎn)的當(dāng)前視圖編號(hào)一致；

3）消息的序號(hào)n滿足水線條件，在h和H之間。

如果滿足以上條件，則接受消息。如果從不同的節(jié)點(diǎn)收到2f 1（包括自己）條commit消息且都正確，那么這個(gè)節(jié)點(diǎn)進(jìn)入committed狀態(tài)，并擁有一個(gè)committd certificate。然后向客戶端返回請(qǐng)求。

其中watermark的作用是：

我們想象一種情況，主節(jié)點(diǎn)是壞的，它在給請(qǐng)求編號(hào)時(shí)故意選擇了一個(gè)很大的編號(hào)，以至于超出了序號(hào)的范圍，所以我們需要設(shè)置一個(gè)低水位（low water mark）h和高水位（high water mark）H，讓主節(jié)點(diǎn)分配的編號(hào)在h和H之間，不能肆意分配。

三階段到此結(jié)束，客戶端等待f 1個(gè)相同的副本結(jié)果作為最后結(jié)果。

03垃圾回收

節(jié)點(diǎn)在一次三階段協(xié)議中收到的pre-prepre,prepare,commit等消息是非常多的,這小消息都要記錄在本地的日志中，為了節(jié)省存儲(chǔ)空間,可以把已經(jīng)確認(rèn)無誤的消息給清除掉。只有當(dāng)至少f 1個(gè)節(jié)點(diǎn)執(zhí)行了請(qǐng)求的消息的時(shí)候，才能將相應(yīng)的日志刪除。

于是，當(dāng)一個(gè)節(jié)點(diǎn)執(zhí)行完某條請(qǐng)求后，可以廣播一條消息，當(dāng)全網(wǎng)有2f 1個(gè)節(jié)點(diǎn)都執(zhí)行完這條請(qǐng)求后就可以刪除它的日志了。但是每條消息都進(jìn)行廣播來確認(rèn)是否刪除是低效的，所以可以k條消息放一起確認(rèn)，每當(dāng)k條請(qǐng)求執(zhí)行完后，就廣播一條消息，當(dāng)2f 1個(gè)節(jié)點(diǎn)都執(zhí)行完這個(gè)請(qǐng)求后，就可以將這k條請(qǐng)求的日志刪除了。

這就是建立檢查點(diǎn)checkpoint，當(dāng)節(jié)點(diǎn)i執(zhí)行完k條請(qǐng)求后，就生成一個(gè)checkpoint，并廣播checkpoint消息：<CHECKPOINT, n, d, i>，n是最近一個(gè)影響狀態(tài)的請(qǐng)求序號(hào)，d是狀態(tài)的摘要。當(dāng)有2f 1個(gè)檢查點(diǎn)消息時(shí)，就證明這個(gè)檢查點(diǎn)是正確的，形成一個(gè)stable checkpoint。具有這個(gè)stable checkpoint的節(jié)點(diǎn)就可以將所有序號(hào)小于等于n的pre-prepare,prepare,commit消息，以及之前的檢查點(diǎn)和檢查點(diǎn)消息刪除。

但是由于節(jié)點(diǎn)的執(zhí)行速度不同，要使不同的節(jié)點(diǎn)的檢查點(diǎn)維持在一個(gè)范圍內(nèi)，最快的幾點(diǎn)與最慢的節(jié)點(diǎn)之間最多差L個(gè)檢查點(diǎn)。這里又用到了水線watermark，用檢查點(diǎn)協(xié)議來更新水線的高低值（h和H），這兩個(gè)高低值限定了可以被接受的消息。水線的低值h與最近穩(wěn)定檢查點(diǎn)的序列號(hào)相同，而水線的高值H=h L，L需要足夠大才能使副本不至于為了等待穩(wěn)定檢查點(diǎn)而停頓。

04視圖變更

當(dāng)主節(jié)點(diǎn)掛掉后就觸發(fā)了view change協(xié)議。我們需要確保在新的view中如何來延續(xù)上一個(gè)view最終的狀態(tài)，比如給這時(shí)來的新請(qǐng)求的編號(hào)，還有如何處理上一個(gè)view還沒來得及完全處理好的請(qǐng)求。

Data Structures

所以我們需要記錄上一個(gè)view里發(fā)生什么。 

有兩個(gè)集合P和Q，replica i 的P存著 i 在上一 view 中達(dá)到prepared狀態(tài)的請(qǐng)求的一些信息，有了P，在新的view中，replica i就會(huì)明白接下來處于prepared狀態(tài)的請(qǐng)求不能與上一個(gè)view中處于prepared狀態(tài)的請(qǐng)求的編號(hào)相同。Q是記錄在上一個(gè)view里到達(dá)pre-prepared狀態(tài)的請(qǐng)求的一些信息。

View-Change Messages

我們來看一下Fig 2， 當(dāng)備份節(jié)點(diǎn) i 懷疑 view v中的主節(jié)點(diǎn)出問題（比如是壞節(jié)點(diǎn)）后，它會(huì)進(jìn)入 view v 1，并廣播一條VIEW-CHANGE信息給所有的replicas，其中包含該replica i最新的stable checkpoint的編號(hào)，還有 replica i上存的每一個(gè)checkpoint的編號(hào)和digest的集合，還有上面所說的該replica的P和Q兩個(gè)集合。

View-Change-Ack Messages

replicas 會(huì)收集VIEW-CHANGE信息并發(fā)送ACK確認(rèn)給 view v 1 中的主節(jié)點(diǎn)。

新的主節(jié)點(diǎn)收集了VIEW-CHANGE和VIEW-CHANGE-ACK（包含自己的信息），它會(huì)將VIEW-CHANGE存在一個(gè)集合S中。主節(jié)點(diǎn)需要選出一個(gè)checkpoint作為新view處理請(qǐng)求的起始狀態(tài)。它會(huì)從checkpoint的集合中選出編號(hào)最大（假設(shè)編號(hào)為h）的checkpoint。接下來，主節(jié)點(diǎn)會(huì)從h開始依次選取h到h L（L就是normal case階段我們提到的設(shè)置值）之間的編號(hào)n對(duì)應(yīng)的請(qǐng)求在新的view中進(jìn)行pre-prepare，如果一條請(qǐng)求在上一個(gè)view中到達(dá)了committed狀態(tài)，主節(jié)點(diǎn)就選取這個(gè)請(qǐng)求開始在新的view中進(jìn)行三階段。

之所以選取committed的請(qǐng)求，是因?yàn)樯厦嫖覀兲岬皆黾覥OMMIT階段為了across view來考慮的，處于committed狀態(tài)的請(qǐng)求的編號(hào)在新的view中是有效的，可以繼續(xù)使用。但是如果選取的請(qǐng)求在上一view中并沒有被一個(gè)quorum給prepare，那它的編號(hào)n有可能是不被一個(gè)quorum給同意的，我們選擇在新的view中作廢這樣的請(qǐng)求。

參考文章：

https://blog.csdn.net/bluecloudmatrix/article/details/51898105?utm_source=tuicool&utm_medium=referral#commentBox

https://www.jianshu.com/p/fb5edf031afd