資訊專欄INFORMATION COLUMN
摘要：在這種狀態下，拜占庭將軍們才能保證有多于支軍隊在同一時間一起發起進攻，從而贏取戰斗拜占庭將軍問題中并不去考慮通信兵是否會被截獲或無法傳達信息等問題，即消息傳遞的信道絕無問題。共識算法的核心就是解決拜占庭將軍問題分布式網絡一致性問題。
本文首發于深入淺出區塊鏈社區
原文鏈接:什么是拜占庭將軍問題原文已更新，請讀者前往原文閱讀
接觸區塊鏈的同學，多少都聽說過拜占庭將軍問題，經常看到或聽到某某區塊鏈使用某某算法解決了拜占庭將軍問題，那么究竟什么是拜占庭將軍問題呢?
什么是拜占庭將軍問題也被稱為“拜占庭容錯”、“拜占庭將軍問題”。
拜占庭將軍問題是Leslie Lamport（2013年的圖靈講得住）用來為描述分布式系統一致性問題（Distributed Consensus）在論文中抽象出來一個著名的例子。
這個例子大意是這樣的：
拜占庭帝國想要進攻一個強大的敵人，為此派出了10支軍隊去包圍這個敵人。這個敵人雖不比拜占庭帝國，但也足以抵御5支常規拜占庭軍隊的同時襲擊。這10支軍隊在分開的包圍狀態下同時攻擊。他們任一支軍隊多帶帶進攻都毫無勝算，除非有至少6支軍隊（一半以上）同時襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵騎馬相互通信來協商進攻意向及進攻時間。困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進攻意向或者進攻時間。在這種狀態下，拜占庭將軍們才能保證有多于6支軍隊在同一時間一起發起進攻，從而贏取戰斗？
拜占庭將軍問題中并不去考慮通信兵是否會被截獲或無法傳達信息等問題，即消息傳遞的信道絕無問題。Lamport已經證明了在消息可能丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的。所以，在研究拜占庭將軍問題的時候，已經假定了信道是沒有問題的.問題分析
單從上面的說明可能無法理解這個問題的復雜性，我們來簡單分析一下：
先看在沒有叛徒情況下，假如一個將軍A提一個進攻提議（如：明日下午1點進攻，你愿意加入嗎？）由通信兵通信分別告訴其他的將軍，如果幸運中的幸運，他收到了其他6位將軍以上的同意，發起進攻。如果不幸，其他的將軍也在此時發出不同的進攻提議（如：明日下午2點、3點進攻，你愿意加入嗎？），由于時間上的差異，不同的將軍收到（并認可）的進攻提議可能是不一樣的，這是可能出現A提議有3個支持者，B提議有4個支持者，C提議有2個支持者等等。
再加一點復雜性，在有叛徒情況下，一個叛徒會向不同的將軍發出不同的進攻提議（通知A明日下午1點進攻， 通知B明日下午2點進攻等等），一個叛徒也會可能同意多個進攻提議（即同意下午1點進攻又同意下午2點進攻）。
叛徒發送前后不一致的進攻提議，被稱為“拜占庭錯誤”，而能夠處理拜占庭錯誤的這種容錯性稱為「Byzantine fault tolerance」，簡稱為BFT。
相信大家已經可以明白這個問題的復雜性了。
中本聰的解決方案在出現比特幣之前，解決分布式系統一致性問題主要是Lamport提出的Paxos算法或其衍生算法。Paxos類算法僅適用于中心化的分布式系統，這樣的系統的沒有不誠實的節點（不會發送虛假錯誤消息，但允許出現網絡不通或宕機出現的消息延遲）。
中本聰在比特幣中創造性的引入了“工作量證明（POW : Proof of Work）”來解決這個問題，有興趣可進一步閱讀工作量證明。
通過工作量證明就增加了發送信息的成本，降低節點發送消息速率，這樣就以保證在一個時間只有一個節點(或是很少)在進行廣播，同時在廣播時會附上自己的簽名。
這個過程就像一位將軍A在向其他的將軍（B、C、D...）發起一個進攻提議一樣，將軍B、C、D...看到將軍A簽過名的進攻提議書，如果是誠實的將軍就會立刻同意進攻提議，而不會發起自己新的進攻提議。
以上就是比特幣網絡中是單個區塊（賬本）達成共識的方法（取得一致性）。
理解了單個區塊取得一致性的方法，那么整個區塊鏈（總賬本）如果達成一致也好理解。
我們稍微把將軍問題改一下：假設攻下一個城堡需要多次的進攻，每次進攻的提議必須基于之前最多次數的勝利進攻下提出的（只有這樣敵方已有損失最大，我方進攻勝利的可能性就更大），這樣約定之后，將軍A在收到進攻提議時，就會檢查一下這個提議是不是基于最多的勝利提出的，如果不是（基于最多的勝利）將軍A就不會同意這樣的提議，如果是的，將軍A就會把這次提議記下來。
這就是比特幣網絡最長鏈選擇。
經濟學分析工作量證明其實相當于提高了做叛徒（發布虛假區塊）的成本，在工作量證明下，只有第一個完成證明的節點才能廣播區塊，競爭難度非常大，需要很高的算力，如果不成功其算力就白白的耗費了（算力是需要成本的），如果有這樣的算力作為誠實的節點，同樣也可以獲得很大的收益（這就是礦工所作的工作），這也實際就不會有做叛徒的動機，整個系統也因此而更穩定。
很多人批評工作量證明造成巨大的電力浪費，促使人們去探索新的解決一致性（共識）問題的機制：權益證明機制（POS: Proof of Stake）是一個代表。在拜占庭將軍問題的角度來看，它同樣提高了做叛徒的成本，因為賬戶需要首先持有大量余額才能有更多的幾率廣播區塊，POS不是本文重點，以后在講。
共識算法的核心就是解決拜占庭將軍問題（分布式網絡一致性問題）。擴展閱讀
The Byzantine Generals Problem
深入淺出區塊鏈 - 系統學習區塊鏈，打造最好的區塊鏈技術博客。
如果想與我有更密切的交流可以選擇加入我的知識星球（星球成員可加入微信技術交流群）
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/23966.html
摘要：拜占庭故障是最嚴重最難處理的。在飛機發動機系統核電站和幾乎所有行為取決于大量傳感器結果的系統都需要拜占庭容錯。前面提到的算法，只要叛徒的數量不超過將軍的三分之一，就是拜占庭容錯。 showImg(https://segmentfault.com/img/bV6WtE?w=1080&h=870);區塊鏈本質上是去中心化的系統，由不同的成員計算機組成，這些成員的行為取決于它們的動機和它們可...
摘要：劉宇昆，英文名，是一名美籍華裔科幻作家。他最令國人熟知的成就，就是成功翻譯了劉慈欣的三體系列小說的英文版，讓大劉在國際科幻文學領域聲名鵲起。最近，月出版的科幻選集就收錄了他的新作，以及由他翻譯的劉慈欣作品黃金原野。 劉宇昆，英文名Ken Liu，是一名美籍華裔科幻作家。他最令國人熟知的成就，就是成功翻譯了劉慈欣的「三體」系列小說的英文版，讓大劉在國際科幻文學領域聲名鵲起。 這次他帶著新...
摘要：劉宇昆，英文名，是一名美籍華裔科幻作家。他最令國人熟知的成就，就是成功翻譯了劉慈欣的三體系列小說的英文版，讓大劉在國際科幻文學領域聲名鵲起。最近，月出版的科幻選集就收錄了他的新作，以及由他翻譯的劉慈欣作品黃金原野。 劉宇昆，英文名Ken Liu，是一名美籍華裔科幻作家。他最令國人熟知的成就，就是成功翻譯了劉慈欣的「三體」系列小說的英文版，讓大劉在國際科幻文學領域聲名鵲起。 這次他帶著新...
摘要：同時利用工作量證明等共識機制解決了雙重花費和拜占庭將軍問題。比如拜占庭將軍問題就是一個典型的協作問題。拜占庭帝國想要進攻一個強大的敵人，為此派出了支軍隊去包圍這個敵人。這個敵人雖不比拜占庭帝國，但也足以抵御支常規拜占庭軍隊的同時襲擊。 隨著比特幣的起起伏伏，區塊鏈技術也越來越受到關注，成為當下和人工智能一樣風靡的領域，也有了除了比特幣之外的應用嘗試。不過明白區塊鏈技術底層原理的同學應該...
摘要：區塊鏈系統首先是一個分布式系統，分布式系統的核心問題包括一致性共識一致性問題一致性問題是分布式領域最為基礎也是最重要的問題。算法與算法問題是指分布式系統中存在故障，但不存在惡意節點的場景即可能消息丟失或重復，但無錯誤消息下的共識達成問題。 區塊鏈系統首先是一個分布式系統，分布式系統的核心問題包括一致性、共識 一致性問題 一致性問題是分布式領域最為基礎也是最重要的問題。如果分布式系統能實...
閱讀 2241·2023-04-26 01:50
閱讀 706·2021-09-22 15:20
閱讀 2579·2019-08-30 15:53
閱讀 1585·2019-08-30 12:49
閱讀 1704·2019-08-26 14:05
閱讀 2700·2019-08-26 11:42
閱讀 2298·2019-08-26 10:40
閱讀 2587·2019-08-26 10:38
