Monday, July 27, 2020

Practical Byzantine Fault Tolerance (pBFT) 實用拜占庭容錯入門

入門:拜占庭將軍問題 (Byzantine Genreals Problem)
拜占庭帝國 (Byzantine Empire) 是一個幅員很廣的古代國家,
所以,軍隊之間要一起行動,必須先遠程溝通,協商,
獲得可靠的共識,最後一致進攻,才能成事。

不過,由於不同軍隊之間距離偏遠,古代每個將軍只能用密函互傳訊息。
同時,由於敵方也知道我方軍隊的兵力相當,
所以,它們也派了一些間諜將軍,希望可以傳一些錯誤的訊息,打亂我方的陣腳。

投票
假設我方有 7 個每個將軍,每人都可以傳一封密函給其他將軍一次。
這 7 個(故意選單數,避免票數打和)將軍當中,有 1 個是間諜,6 個是誠實的。
每個人需要投票表示「進攻」和「防守」,多數服從少數。

如果誠實的將軍中,有 3 位投贊成,3 位投反對,
間諜就可以向那 3 位投進攻的將軍表示投進攻,同時向那 3 位投防守的人表示投防守。

這樣,3 個贊成進攻的將軍,就會以為自己是大多數,所以進攻。
同時,3 個贊成防守的將軍,也會因為以為自己是大多數,所以防守。
最後,由於大家沒有可靠的共識 (reliable consensus),就會有人出兵,有人留城,
整個戰爭將會慘敗。

共識
假設進攻由一個將軍決定,當將軍們都收到其他將軍的肯定,就可以進攻。
現在,假設整個帝國有 6 個將軍,但每一個將軍都只收到 3 封回音。

如果原因是因為,有 2 個將軍的飛馬傳信失敗,同時又有 2 個成功的傳信是來自間諜。
這樣,憑著收回來的 3 個訊息(2 個來自間諜,1 個來自將軍。有 2 封掉失,1 封自己),
將軍也無法肯定是否應該進攻。

科學家稱這兩種攻擊方法為「拜占庭攻擊 (Byzantine Attack)」,
而這兩種錯誤的情況,則稱之為「拜占庭錯誤 (Byzantine Fault)」。

解決方法:CFT 與 BFT
現今世界中,共識算法 (Consensus Algorithm) 正正就是解決以上問題的重要工具。
共識算法主要可分為兩種: Crash Fault Tolerance (CFT) 和 Byzantine Fault Tolerance (BFT)。

CFT 主要指將軍沒有回應,或者訊息間傳遞失敗;
而 BFT 則更進一步,既針對訊息傳遞問題,也考慮到會有間諜在其中作惡。

Practical Byzantine Fault Tolerance (pBFT) 實用拜占庭容錯
在 1999 年,Miguel Castro 及 Barbara Liskov 提出了一個針對 BFT 的解決方案,稱為 pBFT。

假設有 f 個間諜的話,pBFT 需要有 3f+1 個節點 (replica),才能要防止間諜影響共識。
換句話說,在 7 個節點的系統,如果運行 pBFT,只容許有 2 個間諜存在 (3*2+1=7)。

當中 3f+1 的證法比較複雜,詳細可參考 [2] 中的證法。有另一個證法:
假設系統中有 R 個節點,當中有 k 個忠誠節點,有 f 個非法節點。
如果目前 k 個忠誠節點中,有  f 個下了線,然後 f 個非法節點又同時發出假消息,
要阻止假消息「成真」,剩餘的 k-f 必須要比 f 大,
所以得出 k-f > f,也就是 k > 2f,
因為 R = k+f,所以也得出 R-f > 2f,也就是 R > 3f。

整個系統有五大階段:

1. Request: 
用戶 (Request Client) 發送一個 request 去主節點去寫入訊息 m。

2. Pre-Prepare: 
主節點會以 multicast 形式,發送 Pre-Prepare 指令去其他各節點。

3. Prepare: 
當每一個節點收到來自其他節點的 Pre-Prepare,並且驗證過內容為相同及正確後,
就會以 multicast 發送 Prepare 去其他節點。

4. Commit:
當各節點收到 2f+1(包括它自己)的 Prepare 訊息後,就會進入 Prepared 狀態。
然後,各節點就會發送 Commit 去其他節點。

5. Reply:
當各節點收到 2f+1(包括它自己)的 Commit 訊息後,就會進入 Committed 狀態。
然後,各節點就會傳送 Reply 給 Request Client。
當 Client 收到最少 f+1 (還是 2f+1?)個 Reply,就可以確認整個系統已經寫入共識 m。

6. Checkpoint:
系統會偶爾用 checkpoint 作為舊記錄的封存,
以防止他日重開系統,需要由頭開始計起(及驗證)共識值。


pBFT 的潛在問題
pBFT 有以下兩個主要特點:

  • pBFT 假設 malicious node 只是行為怪異,但並不考慮資料外泄問題。
    換言之,pBFT 只能在相信每一個 replica 中的資料並不私隱的情況下,才能運作。
  • pBFT 需要大量的 multicast 訊息傳播。
    當系統變得越大,訊息量將會指數性增加,令系統負擔變大。


---

參考:

[1]: Castro, Miguel, and Barbara Liskov. "Practical Byzantine fault tolerance." OSDI. Vol. 99. No. 1999. 1999. (http://pmg.csail.mit.edu/papers/osdi99.pdf)

[2]: Bracha, Gabriel, and Sam Toueg. "Asynchronous consensus and broadcast protocols." Journal of the ACM (JACM) 32.4 (1985): 824-840.(https://zoo.cs.yale.edu/classes/cs426/2012/bib/bracha85asynchronous.pdf)

[3]: https://medium.com/coinmonks/pbft-understanding-the-algorithm-b7a7869650ae

[4]: https://zhuanlan.zhihu.com/p/56780298



No comments:

Post a Comment