拜占庭帝國 (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