摘要：
PBFT是Practical Byzantine Fault Tolerance的縮寫捅厂，即：實用拜占庭容錯算法穗熬。該算法是Miguel Castro（卡斯特羅）和Barbara Liskov（利斯科夫）在1999年提出來的，解決了原始拜占庭容錯算法效率不高的問題箕母，算法的時間復雜度是O(n^2)，使得在實際系統(tǒng)應(yīng)用中可以解決拜占庭容錯問題。該論文發(fā)表在1999年的操作系統(tǒng)設(shè)計與實現(xiàn)國際會議上（OSDI99）锅移。其中Barbara Liskov就是提出了著名的里氏替換原則（LSP）的人，2008年圖靈獎得主饱搏。以下拜占庭容錯問題簡稱BFT非剃。
BFT是區(qū)塊鏈共識算法中，需要解決的一個核心問題推沸，以比特幣和以太訪為代表的POW备绽，EOS為代表的DPOS券坞，以及今后以太訪逐漸替換的共識算法POS，這些都是公鏈算法疯坤，解決的是共識節(jié)點眾多情況下的BFT报慕。而PBFT是在聯(lián)盟鏈共識節(jié)點較少的情況下BFT的一種解決方案。
網(wǎng)上已經(jīng)有很多關(guān)于PBFT算法的描述压怠，但是寫的都不是很明白眠冈，本文以一種更為清晰易懂的方法，徹底講明白PBFT算法原理菌瘫。下一篇文章將會結(jié)合fabric-0.6.0-preview 中的代碼蜗顽，講解超級賬本項目是如何實現(xiàn)PBFT算法的。
本文假設(shè)讀者已經(jīng)理解什么是BFT問題雨让。
PBFT算法流程：
PBFT算法前提雇盖，采用密碼學算法保證節(jié)點之間的消息傳送是不可篡改的。
PBFT容忍無效或者惡意節(jié)點數(shù)：f栖忠，為了保障整個系統(tǒng)可以正常運轉(zhuǎn)崔挖，需要有2f+1個正常節(jié)點，系統(tǒng)的總節(jié)點數(shù)為：|R| = 3f + 1庵寞。也就是說狸相，PBFT算法可以容忍小于1/3個無效或者惡意節(jié)點，該部分的原理證明請參考PBFT論文捐川，下文有鏈接地址脓鹃。
PBFT是一種狀態(tài)機副本復制算法，所有的副本在一個視圖（view）輪換的過程中操作古沥，主節(jié)點通過視圖編號以及節(jié)點數(shù)集合來確定瘸右，即：主節(jié)點 p = v mod |R|。v：視圖編號岩齿，|R|節(jié)點個數(shù)太颤，p：主節(jié)點編號。
PBFT算法主體實現(xiàn)流程圖如下：
以下詳細說明盹沈，每個主體流程內(nèi)容：
1. REQUEST：
客戶端c向主節(jié)點p發(fā)送<REQUEST, o, t, c>請求栋齿。o: 請求的具體操作，t: 請求時客戶端追加的時間戳襟诸，c：客戶端標識瓦堵。REQUEST: 包含消息內(nèi)容m，以及消息摘要d(m)歌亲」接茫客戶端對請求進行簽名。
2. PRE-PREPARE：
主節(jié)點收到客戶端的請求陷揪，需要進行以下交驗：
a. 客戶端請求消息簽名是否正確惋鸥。
非法請求丟棄杂穷。正確請求，分配一個編號n卦绣，編號n主要用于對客戶端的請求進行排序耐量。然后廣播一條<<PRE-PREPARE, v, n, d>,? m>消息給其他副本節(jié)點。v：視圖編號滤港，d客戶端消息摘要廊蜒，m消息內(nèi)容。<PRE-PREPARE, v, n, d>進行主節(jié)點簽名溅漾。n是要在某一個范圍區(qū)間內(nèi)的[h, H]山叮，具體原因參見垃圾回收章節(jié)。
3.?PREPARE：
副本節(jié)點i收到主節(jié)點的PRE-PREPARE消息添履，需要進行以下交驗：
a. 主節(jié)點PRE-PREPARE消息簽名是否正確屁倔。
b. 當前副本節(jié)點是否已經(jīng)收到了一條在同一v下并且編號也是n，但是簽名不同的PRE-PREPARE信息暮胧。
c. d與m的摘要是否一致锐借。
d. n是否在區(qū)間[h, H]內(nèi)。
非法請求丟棄往衷。正確請求钞翔，副本節(jié)點i向其他節(jié)點包括主節(jié)點發(fā)送一條<PREPARE, v, n, d, i>消息, v, n, d, m與上述PRE-PREPARE消息內(nèi)容相同，i是當前副本節(jié)點編號炼绘。<PREPARE, v, n, d, i>進行副本節(jié)點i的簽名。記錄PRE-PREPARE和PREPARE消息到log中妄田，用于View Change過程中恢復未完成的請求操作俺亮。
4. COMMIT：
主節(jié)點和副本節(jié)點收到PREPARE消息，需要進行以下交驗：
a. 副本節(jié)點PREPARE消息簽名是否正確疟呐。
b. 當前副本節(jié)點是否已經(jīng)收到了同一視圖v下的n脚曾。
c. n是否在區(qū)間[h, H]內(nèi)。
d. d是否和當前已收到PRE-PPREPARE中的d相同
非法請求丟棄启具。如果副本節(jié)點i收到了2f+1個驗證通過的PREPARE消息本讥，則向其他節(jié)點包括主節(jié)點發(fā)送一條<COMMIT, v, n, d, i>消息，v, n, d,? i與上述PREPARE消息內(nèi)容相同鲁冯。<COMMIT, v, n, d, i>進行副本節(jié)點i的簽名拷沸。記錄COMMIT消息到日志中，用于View Change過程中恢復未完成的請求操作薯演。記錄其他副本節(jié)點發(fā)送的PREPARE消息到log中撞芍。
5. REPLY：
主節(jié)點和副本節(jié)點收到COMMIT消息，需要進行以下交驗：
a. 副本節(jié)點COMMIT消息簽名是否正確跨扮。
b. 當前副本節(jié)點是否已經(jīng)收到了同一視圖v下的n序无。
c. d與m的摘要是否一致验毡。
d. n是否在區(qū)間[h, H]內(nèi)。
非法請求丟棄帝嗡。如果副本節(jié)點i收到了2f+1個驗證通過的COMMIT消息晶通，說明當前網(wǎng)絡(luò)中的大部分節(jié)點已經(jīng)達成共識，運行客戶端的請求操作o哟玷，并返回<REPLY, v, t, c, i, r>給客戶端狮辽，r：是請求操作結(jié)果，客戶端如果收到f+1個相同的REPLY消息碗降，說明客戶端發(fā)起的請求已經(jīng)達成全網(wǎng)共識隘竭，否則客戶端需要判斷是否重新發(fā)送請求給主節(jié)點。記錄其他副本節(jié)點發(fā)送的COMMIT消息到log中讼渊。
垃圾回收：
在上述算法流程中动看，為了確保在View Change的過程中，能夠恢復先前的請求爪幻，每一個副本節(jié)點都記錄一些消息到本地的log中菱皆，當執(zhí)行請求后副本節(jié)點需要把之前該請求的記錄消息清除掉。最簡單的做法是在Reply消息后挨稿，再執(zhí)行一次當前狀態(tài)的共識同步仇轻，這樣做的成本比較高，因此可以在執(zhí)行完多條請求K（例如：100條）后執(zhí)行一次狀態(tài)同步奶甘。這個狀態(tài)同步消息就是CheckPoint消息篷店。
副本節(jié)點i發(fā)送<CheckPoint, n, d, i>給其他節(jié)點，n是當前節(jié)點所保留的最后一個視圖請求編號臭家，d是對當前狀態(tài)的一個摘要疲陕，該CheckPoint消息記錄到log中。如果副本節(jié)點i收到了2f+1個驗證過的CheckPoint消息钉赁，則清除先前日志中的消息蹄殃，并以n作為當前一個stable checkpoint。
這是理想情況你踩，實際上當副本節(jié)點i向其他節(jié)點發(fā)出CheckPoint消息后诅岩，其他節(jié)點還沒有完成K條請求，所以不會立即對i的請求作出響應(yīng)带膜，它還會按照自己的節(jié)奏吩谦，向前行進，但此時發(fā)出的CheckPoint并未形成stable膝藕，為了防止i的處理請求過快逮京，設(shè)置一個上文提到的高低水位區(qū)間[h, H]來解決這個問題。低水位h等于上一個stable checkpoint的編號束莫，高水位H = h + L懒棉，其中L是我們指定的數(shù)值草描，等于checkpoint周期處理請求數(shù)K的整數(shù)倍，可以設(shè)置為L = 2K策严。當副本節(jié)點i處理請求超過高水位H時穗慕，此時就會停止腳步，等待stable checkpoint發(fā)生變化妻导，再繼續(xù)前進逛绵。
View Change：
如果主節(jié)點作惡，它可能會給不同的請求編上相同的序號倔韭，或者不去分配序號术浪，或者讓相鄰的序號不連續(xù)。備份節(jié)點應(yīng)當有職責來主動檢查這些序號的合法性寿酌。如果主節(jié)點掉線或者作惡不廣播客戶端的請求胰苏，客戶端設(shè)置超時機制，超時的話醇疼，向所有副本節(jié)點廣播請求消息硕并。副本節(jié)點檢測出主節(jié)點作惡或者下線，發(fā)起View Change協(xié)議秧荆。
副本節(jié)點向其他節(jié)點廣播<VIEW-CHANGE, v+1, n, C, P, i>消息倔毙。n是最新的stable checkpoint的編號，C是2f+1驗證過的CheckPoint消息集合乙濒，P是當前副本節(jié)點未完成的請求的PRE-PREPARE和PREPARE消息集合陕赃。
當主節(jié)點p = v + 1 mod |R|收到2f個有效的VIEW-CHANGE消息后，向其他節(jié)點廣播<NEW-VIEW, v+1, V, O>消息颁股。V是有效的VIEW-CHANGE消息集合么库。O是主節(jié)點重新發(fā)起的未經(jīng)完成的PRE-PREPARE消息集合。PRE-PREPARE消息集合的選取規(guī)則：
1. 選取V中最小的stable checkpoint編號min-s豌蟋，選取V中prepare消息的最大編號max-s廊散。
2. 在min-s和max-s之間桑滩，如果存在P消息集合梧疲，則創(chuàng)建<<PRE-PREPARE, v+1, n, d>, m>消息。否則創(chuàng)建一個空的PRE-PREPARE消息运准，即：<<PRE-PREPARE, v+1, n, d(null)>, m(null)>, m(null)空消息幌氮，d(null)空消息摘要。
副本節(jié)點收到主節(jié)點的NEW-VIEW消息胁澳，驗證有效性该互，有效的話，進入v+1狀態(tài)韭畸，并且開始O中的PRE-PREPARE消息處理流程宇智。
總結(jié)：
PBFT算法由于每個副本節(jié)點都需要和其他節(jié)點進行P2P的共識同步蔓搞，因此隨著節(jié)點的增多，性能會下降的很快随橘，但是在較少節(jié)點的情況下可以有不錯的性能喂分，并且分叉的幾率很低。PBFT主要用于聯(lián)盟鏈机蔗，但是如果能夠結(jié)合類似DPOS這樣的節(jié)點代表選舉規(guī)則的話也可以應(yīng)用于公聯(lián)蒲祈，并且可以在一個不可信的網(wǎng)絡(luò)里解決拜占庭容錯問題，TPS應(yīng)該是遠大于POW的萝嘁。
參考：
拜占庭容錯(Byzantine Fault Tolerance) WIKI:??BFT - Wikipedia
