区块链在中国（2）：PBFT算法
上一張我們從分布式系統的角度簡單敘述了一下 IBM HyperLedger fabric 的一些基本概念、架構和協議信息。其中最為核心的部分就是共識算法（consensus plugin），fabric推薦并實現的就是PBFT這一經典算法。
BFT算法
Client會發送一系列請求給各個replicas節點來執行相應的操作，BFT算法保證所有正常的replicas節點執行相同序列的操作。因為所有的replicas節點都是deterministic，而且初始狀態都相同，根據狀態機原理（state machine replication），這些replicas會產生相同的結果狀態。當Client收到f+1個replicas節點返回的結果時，如果這些結果都一樣，因為BFT算法確保了最多有f個replicas出現問題，所以至少有一個replicas是正確的，那么Client收到的這些結果都是正確的。
但是state machine replication的難點在于確保正常replicas節點都以相同的序列執行同樣的一些請求，尤其是如何來面對拜占庭故障。PBFT會融合primary-backup [Alsberg and Day 1976] 和 quorum replication
[Gifford 1979]兩種技術來序列化請求。
primary-backup
這個機制下有一個叫view的概念，在一個view里，一個replica會是主節點（primary），其余的replicas都叫備份節點（backups）。主節點負責將來自Client的請求給排好序，然后按序發送給備份節點們。但是主節點可能會是faulty的：它可能會給不同的請求編上相同的序號，或者不去分配序號，或者讓相鄰的序號不連續。備份節點應當有職責來主動檢查這些序號的合法性，并能通過timeout機制檢測到主節點是否已經宕掉。當出現這些異常情況時，這些備份節點就會觸發view change協議來選舉出新的主節點。
The algorithm ensures that request sequence numbers are dense, that is, no sequence numbers are skipped but when there are view changes some sequence numbers may be assigned to null requests whose execution is a no-op.
quorums
quorums有兩個重要的屬性：
- Intersection： 任意兩個quorums至少有一個共同的并且正確的replica
- Availability: 總是存在一個沒有faulty replicas的quorum
如果一個replica把信息寫給一個quorum，并讓該quorum來存儲信息，在收到每一個quorum中的成員的確認反饋后，那么我們可以認為該replica的信息已經被可靠的保存在了這個分布式系統中。這是強的約束，當然還有一個weak certificates：就是至少f+1個節點來共同存取信息，這樣至少有一個正確的replica存到了這份信息。
我們先來約定一些符合：
R是所有replicas的集合，每一個replica用一個整數來表示，依次為
{ 0, …, |R - 1 }
簡單起見，我們定義
|R = 3f + 1
f 是最大可容忍的faulty節點
另外我們將一個view中的primary節點定義為replica p，
p = v mod |R
v 是view的編號，從0開始一直連續下去，這樣可以理解為從replica 0 到 replica |R -1 依次當primary節點，當每一次view change發生時。
我們定義一個quorum為至少包含2f+1個replicas的集合。
The Client
一個Client會將請求
?REQUEST,o,t,c? 其中o表示具體的操作，t表示timestamp，給每一個請求加上時間戳，這樣后來的請求會有高于前面的時間戳
replicas會接收請求，如果他們驗證了條請求，就會將它寫入到自己的log中。在共識算法保證下每個replica完成對該請求的執行后直接將回復返回給client：
?REPLY,v,t,c,i,r? v是當前的view序號，t就是對應請求的時間戳，i是replica節點的編號，r是執行結果
我們上面提到過weak certificate，在這里，client也會等待這個weak certificate：即有f+1個replicas回復，并且它們的回復擁有相同的 t 和 r，由于至多有f個faulty replicas，所以確保了回復是合法的。我們叫這個weak certificate為 reply certificate。
每一個replica會與每一個處于active狀態的client共享一份秘鑰。秘鑰所占據空間較少，加上會限制active client的數量，所以不必擔心以后出現的擴展性問題。
Normal Case Operation
我們采用三階段協議來廣播請求給replicas：pre-prepare, prepare, commit。
pre-prepare階段和prepare階段用來把在同一個view里發送的請求給確定下序列，就是排好序，讓各個replicas節點都認可這個序列，照序執行，當然里面可能會有拜占庭節點惡意操作，我們接下來會舉出這種情況，以及三階段協議是如何來處理這樣的情況。
假設如圖所示，目前我們有四個節點組成的分布式網絡，replica 0擔當主節點。
我們要提前清楚，在這個網絡里，
1. 有可能四個節點都是乖節點（正確的、合法的）
2. 主節點是壞節點，其余三個備份節點是乖節點
3. 主節點是乖節點，三個備份節點里有一個是壞節點，其余是乖節點
不論上述三種情況哪一種出現，三階段協議都能保證這個分布式網絡健康、合法的運行。不會給壞節點可乘之機，從而避免破壞的出現。
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里都將被遺棄，不作數。
pre-prepare階段
主節點收到來自Client的一條請求并分配了一個編號給這個請求，然后主節點會廣播一條PRE-PREPARE信息給備份節點，這個PRE-PREPARE信息包含該請求的編號、所在的view和自身的一個digest。直到該信息送達到每一個備份節點，接下來就看收到信息的備份節點們同不同意主節點分配給該請求的這個編號n，即是否accept這條PRE-PREPARE信息，如果一個備份節點accept了這條PRE-PREPARE，它就會進入下面的prepare階段。
什么情況下備份節點會拒絕（not accept） PRE-PREPARE信息：當該備份節點之前已經接收到了一條在同一view下并且編號也是n，但是digest不同的PRE-PREPARE信息時，就會拒絕。
prepare階段
一個備份節點進入到自己的prepare階段后，開始將一條PREPARE信息廣播給主節點和其它兩個備份節點，直到PREPARE信息都抵達那三個節點。與此同時，該備份節點也會分別收到來自其它兩個備份節點的PREPARE信息。該備份節點將綜合這些PREPARE信息做出自己對編號n的最終裁決（這時進行的判斷是在防止主節點是拜占庭節點的情況）。當這個備份節點開始綜合比較來自其它兩個備份節點的PREPARE信息和自身的PREPARE信息時，如果該備份節點發現其它兩個節點都同意主節點分配的編號，又看了一下自己，自己也同意主節點的分配，a quorum certificate with the PRE-PREPARE and 2 f matching PREPARE messages for sequence number n, view v, and request m，如果一個replica達到了英文所說的條件，比如就是上面的斜體字描述的一種情況，那么我們就說該請求在這個replica上的狀態是prepared，該replica就擁有了一個證書叫prepared certificate。那我們是不是就可以說至此排序工作已經完成，全網節點都達成了一個一致的請求序列呢，每一個replica開始照著這個序列執行吧。這是有漏洞的，設想一下，在t1時刻只有replica 1把請求m（編號為n）帶到了prepared狀態，其他兩個備份節點replica 2， replica 3還沒有來得及收集完來自其它節點的PREPARE信息進行判斷，那么這時發生了view change進入到了一個新的view中，replica 1還認為給m分配的編號n已經得到了一個quorum同意，可以繼續納入序列中，或者可以執行了，但對于replica 2來說，它來到了新的view中，它失去了對請求m的判斷，甚至在上個view中它還有收集全其他節點發出的PREPARE信息，所以對于replica 2來說，給請求m分配的編號n將不作數，同理replica 3也是。那么replica 1一個人認為作數不足以讓全網都認同，所以再新的view中，請求m的編號n將作廢，需要重新發起提案。所以就有了下面的commit階段。
commit階段
緊接著prepare階段，當一個replica節點發現有一個quorum同意編號分配時，它就會廣播一條COMMIT信息給其它所有節點告訴他們它有一個prepared certificate了。與此同時它也會陸續收到來自其它節點的COMMIT信息，如果它收到了2f+1條COMMIT（包括自身的一條，這些來自不同節點的COMMIT攜帶相同的編號n和view v），我們就說該節點擁有了一個叫committed certificate的證書，請求在這個節點上達到了committed狀態。此時只通過這一個節點，我們就能斷定該請求已經在一個quorum中到達了prepared狀態，即一個quorum的節點們都同意了編號n的分配。當請求m到達commited狀態后，該請求就會被該節點執行。
三階段介紹完畢。我們想象一種情況，主節點是壞的，它在給請求編號時故意選擇了一個很大的編號，以至于超出了序號的范圍，所以我們需要設置一個低水位（low water mark）h和高水位（high water mark）H，讓主節點分配的編號在h和H之間，不能肆意分配。
Garbage Collection
分布式系統的復雜性在于要考慮到各種各樣的意外和蓄意破壞，你要制定出一套有效的法律來約束這個系統里可能發生的一切行為，并沒有完美的分布式系統存在。
當replica執行完請求時，需要把之前記錄的該請求的信息清除掉。但是不能這樣輕易的去清除，其中包含的prepared certificate可能會在后面用得上。所以要有種機智來保證何時可以清除。
其實很簡單，每執行完一條請求，該節點會再一次發出廣播，就是否可以清除信息在全網達成一致。更好的方案是，我們一連執行了K條請求，在第K條請求執行完時，向全網發起廣播，告訴大家它已經將這K條執行完畢，要是大家反饋說這K條我們也執行完畢了，那就可以刪除這K條的信息了，接下來再執行K條，完成后再發起一次廣播，即每隔K條發起一次全網共識，這個概念叫checkpoint，每隔K條去征求一下大家的意見，要是獲得了大多數的認同（a quorum certificate with 2 f + 1 CHECKPOINT messages (including its own)），就形成了一個 stable checkpoint（記錄在第K條的編號），我們也說該replica擁有了一個stable certificate就可以刪除這K條請求的信息了。
這是理想的情況，實際上當replica i向全網發出checkpoint共識后，其他節點可能并沒有那么快也執行完這K條請求，所以replica i不會立即得到響應，它還要繼續自己的步伐，那這個checkpoint在它那里就不是stable的。那這個步伐快的replica可能會越來越快，可能會把大家拉的越來越遠，這時我們來看一下上面提到的高低水位的作用。對該replica來說，它的低水位h等于它上一個stable checkpoint的編號，高水位H=h+L，L是我們指定的數值，它一般是checkpoint周期K的常數倍（這個常數是比較小的， 比如2倍），這樣即使該replica步伐很快，它處理的請求編號達到高水位H后也得停一停自己的腳步，直到它的stable checkpoint發生變化，它才能繼續向前。
View Changes
當主節點掛掉后就觸發了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中作廢這樣的請求。
fabric-master下有這樣幾個重要的子目錄：
- consensus
- controller
- executor
- helper
- noops
- obcpbft
- consensus.go
- core
- chaincode
- crypto
- db
- discovery
- ledger
- peer
- system_chaincode
- fsm.go
- events
- consumer
- producer
- membersrvc
- peer
- main.go
- core.yaml
- protos
- block.go
- chaincode.pb.go
- events.pb.go
- fabric.pb.go
- transaction.go
我們可以根據這些目錄和文件來學習PBFT或者fabric的共識算法。
總結
以上是生活随笔為你收集整理的区块链在中国（2）：PBFT算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 帮个忙！！！
- 下一篇： The Rust Programming