拜占庭将军问题

拜占庭将军问题（Byzantine Generals Problem），是由莱斯利·兰波特在其同名论文^[1]中提出的分布式对等网络通信容错問題。

在分佈式計算中，不同的計算機通过通讯交换信息达成共识而按照同一套协作策略行动。但有時候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论^[2]，从而破坏系统一致性^[3]。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

问题描述

莱斯利·兰波特在其论文^[1]中描述了如下问题：

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

系统的问题在于，可能将军中出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。

假使那些忠誠（或是沒有出錯）的將軍仍然能通過多數決定來決定他們的戰略，便稱達到了拜占庭容错。在此，票都會有一個預設值，若訊息（票）沒有被收到，則使用此預設值來投票。

上述的故事對映到計算機系統裡，將軍便成了計算機，而信差就是通訊系統。雖然上述的問題涉及了電子化的決策支援與資訊安全，卻沒辦法單純的用密碼學與數位簽章來解決。因為电路错误仍可能影響整個加密過程，這不是密碼學與數位簽章演算法在解決的問題。因此計算機就有可能將錯誤的結果送出去，亦可能導致錯誤的決策。

早期的解決方案

在1982年的論文^[1]中提過幾個解決方案。方案中把問題往下拆解，認為在「拜占庭将军」的問題可以在「軍官與士官的問題」裡解決，以降低将军問題的發生。而所謂的「軍官與士官的問題」，就是探討軍官與他的士官是否能忠實實行命令。

• 其中一個解決方案認為即使出現了偽造或錯誤的訊息。只要有問題的將軍的數量不到三分之一，仍可以達到「拜占庭容错」。原因是把同樣的標準下放到「軍官與士官的問題」時，在背叛的軍士官不足三分之一的情況下，有問題的軍士官可以很容易的被糾出來。比如有軍官A，士官B與士官C。當A要求B進攻，卻要求C撤退時。就算B與C交換所收到的命令，B與C仍不能確定是否A有問題，因為B或C可能將竄改了的訊息傳給對方。以函式來表示，將軍的總數為n，n裡面背叛者的數量為t，則只要n > 3t就可以容錯。^[4]
• 另一個解決方案需要有無法消去的簽名。在現今許多高度資安要求的關鍵系統裡，數位簽章就經常被用來實作拜占庭容错，找出有問題的將軍。然而，在生命攸關系統裡，使用錯誤偵測碼就可以大幅降低問題的發生。無論系統是否存在拜占庭将军問題。所以需要做密碼運算的數位簽章也不一定適合這類系統。^[5][2][3]
• 假如上述兩個解決方案裡，將軍們無法直接通訊時，該論文亦有進一步的解決方案。

此外，1980年代還有其他用來達到拜占庭容错的架構被提出，如：FTMP^[6]、MMFCS^[7] 與 SIFT。^[8]

實用拜占庭容錯

1999年，卡斯托（Miguel Castro）與利斯科夫（Barbara Liskov）提出了實用拜占庭容錯（PBFT）演算法^[9]。該演算法能提供高效能的運算，使得系統可以每秒處理成千的請求，比起舊式系統快了一些。

而在PBFT之後，許多用於拜占庭容錯（BFT）的通訊協議也被提出來改善其通訊的強健性與效率。比如Q/U^[10]、HQ^[11]、Zyzzyva^[12]與ABsTRACTs^[13] ...，用來提升效率。而Aardvark^[14]與RBFT^[15]是用來加強強健性。另外，Adapt^[16]則使用原有的BFT協議做調適，以強化其效率與強健性。BFT協議更可以藉由加入可任務的單元，以減少發出副本的次數。比如：A2M-PBFT-EA^[17]與MinBFT。^[18]

计算机系统

在分布式对等网络中需要按照共同一致策略协作的成员计算机即为问题中的将军，而各成员计算机赖以进行通讯的网络链路即为信使。拜占庭将军问题描述的就是某些成员计算机或网络链路出现错误、甚至被蓄意破坏者控制的情况。

實務應用

在對等式數位貨幣系統比特幣裡，比特幣網路的運作是平行的（parallel）。各節點與終端都運算著區塊鏈來達成工作量證明（PoW）。工作量證明的連結是解決比特幣系統中拜占庭問題的關鍵，避免有問題的節點（即前文提到的「反叛的將軍」）破壞數位貨幣系統裡交易帳的正確性，是對整個系統的運行狀態有著重要的意義。

在一些飛行器（如波音777）的系統中^[19][20][21]也有使用拜占庭容錯。而且由於是即時系統，容錯的功能也要能儘快回覆，比如即使系統中有錯誤發生，容錯系統也只能做出一微秒以內的延遲。

一些太空梭的飛行系統^[22]甚至將容錯功能放到整個系統的設計之中。

拜占庭容錯機制是將收到的訊息（或是收到的訊息的簽章）轉交到其他的接收者。這類機制都假設它們轉交的訊息都可能含有拜占庭問題。在高度安全要求的系統中，這些假設甚至要求證明錯誤能在一個合理的等級下被排除。當然，要證明這點，首先遇到的問題就是如何有效的找出所有可能的、應能被容錯的錯誤^[23]。這時候會試著在系統中加入錯誤插入器^[24][25]。

参考资料

1. Lamport, L.; Shostak, R.; Pease, M. (PDF). ACM Transactions on Programming Languages and Systems. 1982, 4 (3): 382–401. doi:10.1145/357172.357176. （原始内容 (PDF)存档于7 February 2017）. 
2. Driscoll, K.; Hall, B.; Paulitsch, M.; Zumsteg, P.; Sivencrona, H. The Real Byzantine Generals: 6.D.4–61–11. 2004. doi:10.1109/DASC.2004.1390734. 
3. Driscoll, Kevin; Hall, Brendan; Sivencrona, Håkan; Zumsteg, Phil. Byzantine Fault Tolerance, from Theory to Reality 2788: 235–248. 2003. ISSN 0302-9743. doi:10.1007/978-3-540-39878-3_19. 
4. Feldman, P.; Micali, S. An optimal probabilistic protocol for synchronous Byzantine agreement (PDF). SIAM J. Comput. 1997, 26 (4): 873–933 [2017-11-29]. doi:10.1137/s0097539790187084. （原始内容 (PDF)于2016-03-05）. 
5. Paulitsch, M.; Morris, J.; Hall, B.; Driscoll, K.; Latronico, E.; Koopman, P. Coverage and the Use of Cyclic Redundancy Codes in Ultra-Dependable Systems: 346–355. 2005. doi:10.1109/DSN.2005.31. 
6. Hopkins, Albert L.; Lala, Jaynarayan H.; Smith, T. Basil. The Evolution of Fault Tolerant Computing at the Charles Stark Draper Laboratory, 1955–85 1: 121–140. 1987. ISSN 0932-5581. doi:10.1007/978-3-7091-8871-2_6. 
7. Driscoll, Kevin; Papadopoulos, Gregory; Nelson, Scott; Hartmann, Gary; Ramohalli, Gautham, Multi-Microprocessor Flight Control System (Technical Report), Wright-Patterson Air Force Base, OH 45433, USA: AFWAL/FIGL U.S. Air Force Systems Command, 1984, AFWAL-TR-84-3076 
8. SIFT: design and analysis of a fault-tolerant computer for aircraft control. Microelectronics Reliability. 1979, 19 (3): 190. ISSN 0026-2714. doi:10.1016/0026-2714(79)90211-7. 
9. Castro, M.; Liskov, B. Practical Byzantine Fault Tolerance and Proactive Recovery. ACM Transactions on Computer Systems (Association for Computing Machinery). 2002, 20 (4): 398–461. doi:10.1145/571637.571640. 
10. Abd-El-Malek, M.; Ganger, G.; Goodson, G.; Reiter, M.; Wylie, J. Fault-scalable Byzantine Fault-Tolerant Services. Association for Computing Machinery. 2005. doi:10.1145/1095809.1095817.  |conference=被忽略 (帮助)
11. Cowling, James; Myers, Daniel; Liskov, Barbara; Rodrigues, Rodrigo; Shrira, Liuba. HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance. Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation: 177–190. 2006. ISBN 1-931971-47-1. 
12. Kotla, Ramakrishna; Alvisi, Lorenzo; Dahlin, Mike; Clement, Allen; Wong, Edmund. Zyzzyva: Speculative Byzantine Fault Tolerance. ACM Transactions on Computer Systems (Association for Computing Machinery). December 2009, 27 (4). doi:10.1145/1658357.1658358. 
13. Guerraoui, Rachid; Kneževic, Nikola; Vukolic, Marko; Quéma, Vivien. The Next 700 BFT Protocols. Proceedings of the 5th European conference on Computer systems. EuroSys. 2010 [2017-11-29]. （原始内容于2011-10-02）. 
14. Clement, A.; Wong, E.; Alvisi, L.; Dahlin, M.; Marchetti, M. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults (PDF). Symposium on Networked Systems Design and Implementation. USENIX. April 22–24, 2009 [2017-11-29]. （原始内容 (PDF)于2010-12-25）. 
15. Aublin, P.-L.; Ben Mokhtar, S.; Quéma, V. . 33rd IEEE International Conference on Distributed Computing Systems. International Conference on Distributed Computing Systems. July 8–11, 2013. （原始内容存档于August 5, 2013）. 
16. Bahsoun, J. P.; Guerraoui, R.; Shoker, A. Making BFT Protocols Really Adaptive. Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International. 2015-05-01: 904–913 [2017-11-29]. doi:10.1109/IPDPS.2015.21. （原始内容于2018-06-20）. 
17. Chun, Byung-Gon; Maniatis, Petros; Shenker, Scott; Kubiatowicz, John. Attested Append-only Memory: Making Adversaries Stick to Their Word. Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles. SOSP '07 (New York, NY, USA: ACM). 2007-01-01: 189–204 [2017-11-29]. ISBN 9781595935915. doi:10.1145/1294261.1294280. （原始内容于2020-01-29）. 
18. Veronese, G. S.; Correia, M.; Bessani, A. N.; Lung, L. C.; Verissimo, P. Efficient Byzantine Fault-Tolerance. IEEE Transactions on Computers. 2013-01-01, 62 (1): 16–30 [2017-11-29]. ISSN 0018-9340. doi:10.1109/TC.2011.221. （原始内容于2017-12-01）. 
19. M., Paulitsch; Driscoll, K. Chapter 48:SAFEbus. Zurawski, Richard (编). Industrial Communication Technology Handbook, Second Edition. CRC Press. 9 January 2015: 48–1–48–26 [2017-11-29]. ISBN 978-1-4822-0733-0. （原始内容于2020-06-26）. 
20. Thomas A. Henzinger; Christoph M. Kirsch. Embedded Software: First International Workshop, EMSOFT 2001, Tahoe City, CA, USA, October 8-10, 2001. Proceedings (PDF). Springer Science & Business Media. 26 September 2001: 307– [2017-11-29]. ISBN 978-3-540-42673-8. （原始内容 (PDF)于2017-08-09）. 
21. Yeh, Y.C. Safety critical avionics for the 777 primary flight controls system 1: 1C2/1–1C2/11. 2001. doi:10.1109/DASC.2001.963311. 
22. （[//web.archive.org/web/20160805064218/https://lwn.net/Articles/540368/ 页面存档备份，存于互联网档案馆） ELC: SpaceX lessons learned [LWN.net]]
23. Nanya, T.; Goosen, H.A. The Byzantine hardware fault model. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1989, 8 (11): 1226–1231. ISSN 0278-0070. doi:10.1109/43.41508. 
24. Martins, Rolando; Gandhi, Rajeev; Narasimhan, Priya; Pertet, Soila; Casimiro, António; Kreutz, Diego; Veríssimo, Paulo. Experiences with Fault-Injection in a Byzantine Fault-Tolerant Protocol 8275: 41–61. 2013. ISSN 0302-9743. doi:10.1007/978-3-642-45065-5_3. 
25. US patent 7475318,Kevin R. Driscoll,「Method for testing the sensitive input range of Byzantine filters」,发行于2009-01-06,指定于Honeywell International Inc. 

外部連結