拜占庭是古代東羅馬帝國的首都，它曾經(jīng)是世界上最強大、最富有的城市之一。但是，由于地域廣闊，拜占庭經(jīng)常遭受外敵侵略和內(nèi)部叛亂。為了保衛(wèi)邊境，拜占庭派出了多支軍隊，由不同的將軍指揮。將軍之間如何達成信息一致性成了最大問題。

而區(qū)塊鏈與拜占庭將軍問題有著密切的聯(lián)系。區(qū)塊鏈網(wǎng)絡(luò)是一種分布式網(wǎng)絡(luò)，其節(jié)點就像拜占庭將軍一樣，需要在不可靠的網(wǎng)絡(luò)環(huán)境中達成交易和數(shù)據(jù)的共識。

兩軍問題

兩軍問題是拜占庭問題的一個特例。

兩軍問題及其無解性證明最早是由E.A. Akkoyunlu、K.Ekanadham和R.V.Huber于1975年在聯(lián)合發(fā)表的論文《網(wǎng)絡(luò)通信設(shè)計的約束與權(quán)衡》(Some Constraints and Trade-offs In The Design of Network Communications)中首次提出。

1978年，JimGray在《數(shù)據(jù)庫操作系統(tǒng)筆記》書中將這個問題正式命名為“兩軍問題” (Two General’s Problem)。原本是用來分析在一個不可靠的通信鏈路上試圖通過通信以達成一致是存在問題的，后來常被用于闡述分布式系統(tǒng)的一致性和共識問題。

問題定義

A國的兩支軍隊，分別由兩個將軍領(lǐng)導(dǎo)，正在準備攻擊B國的一支軍隊。B國的這支軍隊被包圍在一個山谷里，A國的兩只軍隊A1和A2分別駐扎在山谷兩邊的山頭上，但從A1駐扎地到A2駐扎地，只有唯一的一條山道，且必須經(jīng)過山谷。同時，B軍的數(shù)量和作戰(zhàn)能力比A1軍和A2軍的任意一支都要強(A軍知道，B軍不知道)，A國的任意一支軍隊單獨去進攻B軍，都會被B軍擊敗，從而讓B軍逃掉，但只要A1軍與A2軍聯(lián)合攻擊，就可以戰(zhàn)勝B軍。

問題：是否可以想出一種能讓A國的兩支軍隊的將軍達成同時攻擊約定的算法，該算法可包含發(fā)送和接收處理消息?

說答案：經(jīng)典的兩軍問題是無解的，不存在一個能確保A國·軍隊成功協(xié)商一致攻擊B國的協(xié)議。但在一定的容忍條件下，可以通過一種相對可靠的方式解決大多數(shù)問題，例如TCP協(xié)議中建立連接的“三次握手”機制。

拜占庭將軍問題

拜占庭將軍問題是由2013年度圖靈獎得主萊斯利·蘭波特(Leslie Lamport)在1982年發(fā)表的論文《拜占庭將軍問題》(The Byzantine Generals Problem)中首次提出。拜占庭將軍問題描述了如何在存在惡意行為(如消息被篡改)的情況下實現(xiàn)分布式系統(tǒng)的一致性。

拜占庭帝國的幾支軍隊將敵城包圍，每支軍隊都由一名將軍指揮。拜占庭的軍隊之間只能通過通信兵相互傳達消息。在觀察敵情之后后，根據(jù)敵城的軍事力量，拜占庭將軍們都得出相同的結(jié)論，只有超過半數(shù)的拜占庭軍隊共同發(fā)起進攻，才能攻破城池，取得勝利。

因此，所有的拜占庭軍隊必須制定一個聯(lián)合行動計劃，要么共同進攻，要么共同撤退。

但是，情報部門已經(jīng)知道這些拜占庭軍隊的將軍中存在叛徒，將試圖破壞忠誠的將軍們達成一致的聯(lián)合行動計劃。同時，雖然拜占庭軍隊的通信兵一定能不被敵方截獲且確保送達消息，但是通信兵中也可能存在叛徒，可能在傳信過程中篡改或偽造消息，也可能丟失消息。

問題求解

如果將拜占庭問題中的攻城軍隊的將軍數(shù)量對應(yīng)為分布式系統(tǒng)的節(jié)點數(shù)量，可以將符合拜占庭問題條件的分布式系統(tǒng)稱為”拜占庭系統(tǒng)”，

在拜占庭系統(tǒng)中任意兩個節(jié)點之間的通信是保證可達的，可以得出以下結(jié)論：

對于一個拜占庭系統(tǒng)，如果系統(tǒng)總節(jié)點數(shù)為Z，表示叛變將軍的不可靠節(jié)點數(shù)為X，只有當(dāng)Z≥3X+1時，可由基于拜占庭客容錯(BFT)類算法的協(xié)議保證系統(tǒng)的一致性。

在實際的系統(tǒng)中，一般把由于系統(tǒng)故障導(dǎo)致節(jié)點不響應(yīng)的情兄歸類為“非拜占庭錯誤(Crash Fault)”，把節(jié)點偽造或篡改信息進行惡意響應(yīng)的情況歸類為“拜占庭錯誤(Byzantine Fault)”。

共識算法分類

區(qū)塊鏈系統(tǒng)是一種分布式系統(tǒng)，特別是像比特幣、以太坊等公有鏈系統(tǒng)，由大量高度分散且彼此不信任的網(wǎng)絡(luò)節(jié)點構(gòu)成，區(qū)塊鏈共識機制就是以共識算法為核心，確保區(qū)塊鏈系統(tǒng)就某個事物始終能達成數(shù)據(jù)一致且不產(chǎn)生分叉。

目前，根據(jù)共識算法容錯類型的不同，可以將共識算法分為非拜占庭容錯類(CFT，Crash Fault Tolerance)算法和拜占庭容錯類(BFT，ByzantineFault Tolerance)算法。

非拜占庭容錯類共識算法

對于分布式系統(tǒng)，非拜占庭容錯類共識算法能在節(jié)點發(fā)生系統(tǒng)故障或非計劃停機等非拜占庭錯誤時，確保整個分布式系統(tǒng)的可靠性;但是，當(dāng)系統(tǒng)中存在惡意節(jié)點偽造或篡改數(shù)據(jù)等行為時，非拜占庭容錯算法無法保證系統(tǒng)的可靠性。

因此，非拜占庭容錯類共識算法主要用于實現(xiàn)封閉的、系統(tǒng)節(jié)點都受控的企業(yè)吸分布式系統(tǒng)，如某企業(yè)構(gòu)建的內(nèi)部分布式應(yīng)用集群系統(tǒng)或分布式存儲系統(tǒng)。非拜占庭容錯類共識算法中最有代表性的包括PaxoS算法與Raft算法。

拜占庭容錯類共識算法

拜占庭容錯類共識算法能允許分布式系統(tǒng)節(jié)點發(fā)生任何類型的錯誤但錯誤節(jié)點數(shù)量不超過一定比例時，確保整個分布式系統(tǒng)的可靠性。簡單的說，只要分布式系統(tǒng)的故障 (由于非拜占庭錯誤或拜占庭錯誤導(dǎo)致)節(jié)點數(shù)與系統(tǒng)總節(jié)點數(shù)相比，小于一定比例，拜占庭容錯類共識算法就能保證分布式系統(tǒng)的可靠性。

由于像比特幣、以太坊等區(qū)塊鏈系統(tǒng)中，存在大量彼此不信任的網(wǎng)絡(luò)節(jié)點，不排除有惡意節(jié)點企圖偽造或篡改系統(tǒng)數(shù)據(jù)，因此，拜占庭容錯類共識算法是區(qū)塊鏈共識機制主要采用的共識算法。拜占庭容錯類共識算法中最有代表性的包括PBFT實用拜占庭容錯算法、PoW工作量證明算法、PoS權(quán)益證明算法等。

以上就是區(qū)塊鏈技術(shù)科普：什么是拜占庭將軍問題？的詳細內(nèi)容，更多關(guān)于拜占庭將軍問題的資料請關(guān)注腳本之家其它相關(guān)文章！