拜占庭將軍問(wèn)題是一個(gè)共識(shí)問(wèn)題:?首先由Leslie Lamport與另外兩人在1982年提出，被稱為The Byzantine Generals Problem或者Byzantine Failure。核心描述是軍中可能有叛徒，卻要保證進(jìn)攻一致，由此引申到計(jì)算領(lǐng)域，發(fā)展成了一種容錯(cuò)理論。隨著比特幣的出現(xiàn)和興起，這個(gè)著名問(wèn)題又重入大眾視野。

?關(guān)于拜占庭將軍問(wèn)題，一個(gè)簡(jiǎn)易的非正式描述如下：

拜占庭帝國(guó)想要進(jìn)攻一個(gè)強(qiáng)大的敵人，為此派出了10支軍隊(duì)去包圍這個(gè)敵人。這個(gè)敵人雖不比拜占庭帝國(guó)，但也足以抵御5支常規(guī)拜占庭軍隊(duì)的同時(shí)襲擊。基于一些原因，這10支軍隊(duì)不能集合在一起單點(diǎn)突破，必須在分開(kāi)的包圍狀態(tài)下同時(shí)攻擊。他們?nèi)我恢к婈?duì)單獨(dú)進(jìn)攻都毫無(wú)勝算，除非有至少6支軍隊(duì)同時(shí)襲擊才能攻下敵國(guó)。他們分散在敵國(guó)的四周，依靠通信兵相互通信來(lái)協(xié)商進(jìn)攻意向及進(jìn)攻時(shí)間。困擾這些將軍的問(wèn)題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進(jìn)攻意向或者進(jìn)攻時(shí)間。在這種狀態(tài)下，拜占庭將軍們能否找到一種分布式的協(xié)議來(lái)讓他們能夠遠(yuǎn)程協(xié)商，從而贏取戰(zhàn)斗？這就是著名的拜占庭將軍問(wèn)題。

應(yīng)該明確的是，拜占庭將軍問(wèn)題中并不去考慮通信兵是否會(huì)被截獲或無(wú)法傳達(dá)信息等問(wèn)題，即消息傳遞的信道絕無(wú)問(wèn)題。Lamport已經(jīng)證明了在消息可能丟失的不可靠信道上試圖通過(guò)消息傳遞的方式達(dá)到一致性是不可能的。所以，在研究拜占庭將軍問(wèn)題的時(shí)候，我們已經(jīng)假定了信道是沒(méi)有問(wèn)題的，并在這個(gè)前提下，去做一致性和容錯(cuò)性相關(guān)研究。

拜占庭容錯(cuò)算法

我們已經(jīng)了解了拜占庭將軍問(wèn)題的場(chǎng)景，并且明確了這個(gè)問(wèn)題的解決是建立在通信兵可以正確的傳達(dá)信息的基礎(chǔ)上的，即信道絕對(duì)可信。接下來(lái)，我們將探討拜占庭將軍問(wèn)題的實(shí)質(zhì)。

?拜占庭容錯(cuò)算法是解決在同步網(wǎng)絡(luò)，任意失敗模型情況下達(dá)成一致性共識(shí)。

?拜占庭將軍問(wèn)題實(shí)質(zhì)

回顧問(wèn)題，一群將軍想要實(shí)現(xiàn)某一個(gè)目標(biāo)（一致進(jìn)攻或者一致撤退），但是單獨(dú)行動(dòng)行不通，必須合作，?達(dá)成共識(shí)；由于叛徒的存在，將軍們不知道應(yīng)該如何達(dá)到一致。注意，這里“一致性”才是拜占庭將軍問(wèn)題探討的內(nèi)容，如果本來(lái)叛徒數(shù)量就已經(jīng)多到了問(wèn)題不可解的地步，這個(gè)就是“反叛”的問(wèn)題了；同時(shí)，我們的目標(biāo)是忠誠(chéng)的將軍能夠達(dá)成一致，對(duì)于這些忠誠(chéng)的將軍來(lái)說(shuō)，進(jìn)攻或者撤退都是可以的，只要他們能夠達(dá)成一致就行。

但是，光靠“一致”就可以解決問(wèn)題嗎？考慮一下，如果萬(wàn)事俱備，客觀上每個(gè)忠誠(chéng)的將軍只要進(jìn)攻了就一定能夠勝利，但是卻因?yàn)榕淹降拇嬖谒麄兌肌耙恢碌摹睕](méi)有進(jìn)攻；反之，條件不利，將軍們不應(yīng)該進(jìn)攻，但是卻因?yàn)榕淹降拇嬖谒腥硕肌耙恢碌摹边M(jìn)攻了。

可以發(fā)現(xiàn)，只有“一致性”是不足以解決拜占庭將軍問(wèn)題的，我們還需要提出一個(gè)“正確性”要求。這個(gè)要求是值得斟酌的，因?yàn)槿绻陀^來(lái)看或許會(huì)有“絕對(duì)正確的”判斷，但是針對(duì)每一個(gè)將軍，大家的判斷或許都不相同，我們?nèi)绾味x“正確”呢？我們或許可以簡(jiǎn)單地說(shuō)，正確就是每個(gè)忠誠(chéng)的將軍都正確的表達(dá)了自己的意思，不會(huì)因?yàn)榕淹阶寗e的將軍認(rèn)為忠誠(chéng)的將軍是叛徒而不采用他傳達(dá)的消息。

至此，我們將拜占庭將軍問(wèn)題簡(jiǎn)化成了，所有忠誠(chéng)的將軍都能夠讓別的將軍接收到自己的真實(shí)意圖，并最終一致行動(dòng)；而形式化的要求就是，“一致性”與“正確性”。

如果將問(wèn)題推廣開(kāi)來(lái)，可以發(fā)現(xiàn)針對(duì)一致性和正確性的算法并不要求命令必須是“進(jìn)攻/撤退”或是“1/0”，而可以是“發(fā)送消息1/發(fā)送消息2/待機(jī)”或“x/y/z/w”，這意味著拜占庭將軍問(wèn)題算法可以為多種分布式系統(tǒng)提供啟發(fā)，比如電力系統(tǒng)或網(wǎng)絡(luò)系統(tǒng)。

由此可見(jiàn)，這個(gè)問(wèn)題說(shuō)到底是一個(gè)關(guān)于一致性和正確性的算法問(wèn)題，這個(gè)算法是針對(duì)的是忠誠(chéng)的將軍，因?yàn)榕淹娇梢宰龀鋈魏纬黾s定的判斷。我們就是要在有叛徒的干擾下，找到一個(gè)抗干擾的算法。要解決這個(gè)算法問(wèn)題，我們需要將形式化要求具體化。

口頭協(xié)議推演

下面的這個(gè)截圖是從Lamport發(fā)表的論文中截取的：

對(duì)于這個(gè)算法需要說(shuō)明的是：

(1)?在第一輪?將軍會(huì)把消息發(fā)送給所有的副官，第i個(gè)副官收到的記為?Vi。如?1(這里代表的是Attack)

(2)?在第二輪里面，Li(即第i個(gè)副官)會(huì)懷疑將軍發(fā)來(lái)的消息Vi是對(duì)還是錯(cuò)，于是他會(huì)問(wèn)其余的副官。這樣他就會(huì)得到剩下的(n-2)個(gè)副官的值。?i從1到n-1，所以每個(gè)副官都會(huì)得到剩余的n-2個(gè)副官手里的Vi。在這一步驟里，忠誠(chéng)的副官j會(huì)直接將自己的?Vj發(fā)送給其它人。叛徒則會(huì)發(fā)假消息。

在n=7,m=2的時(shí)候?如果將軍是忠臣的話，那么在第二輪忠誠(chéng)的副官確實(shí)已經(jīng)可以判斷出要做的決定，因?yàn)樗麄儠?huì)收到(1 1 1 0 0 )再加上將軍發(fā)來(lái)的1就是?1 1 1 1 0 0?但是這個(gè)算法是遞歸的所有必須要到第三輪。并且如果將軍是個(gè)叛徒的話，那么第二輪有情形是做不出決定的。

這里對(duì)進(jìn)入第三輪的解釋是，如L1收到其它L2~L6發(fā)來(lái)的Vj,?但是他要懷疑準(zhǔn)確性，比如L1會(huì)想L2發(fā)給自己是否是正確的呢？那么就進(jìn)入第三輪進(jìn)行投票。

(3)在第三輪里面，接著(2)中后面的問(wèn)題。L1會(huì)依次詢問(wèn)L3,4,5,6?，問(wèn)他們上一輪L2給他們發(fā)了什么，然后L1會(huì)得到在(2)中?L2->L3, L2->L4,L2->L5, L2->L6的值?這樣再結(jié)合自己的L2->L1的值，從這5個(gè)里面用majority函數(shù)投出決定得到L2發(fā)給自己的消息值。依次再進(jìn)行L3,L4,L5,L6在第二輪中發(fā)給自己的消息的確認(rèn)。

這樣L1就完成了第二輪的確認(rèn)。之后L1再?gòu)牡谝徊街袑④姲l(fā)給自己的vi和第二輪中確定的5個(gè)值中投出自己的決定。

其余的L2，L3.等等也進(jìn)行同樣的步驟。

如果還是沒(méi)清晰的話，直接看下面的過(guò)程：

這里需要注意的是：Lamport提出的容錯(cuò)的兩個(gè)條件

IC1：即所有的忠誠(chéng)的副官要遵守同一個(gè)命令，即達(dá)成一致；

IC2：假如將軍是忠誠(chéng)的，那么每一個(gè)忠誠(chéng)的副官都應(yīng)該按照將軍的意思行事。

這里將軍是叛徒，所以只要滿足IC1條件即可。

Step1 : C給L1~L6?依次發(fā)?A R A R A X ?（A，R代表攻擊和撤退，這里因?yàn)?/span>C是叛徒，所以可以隨便發(fā)給L1-L5消息，這里只是一個(gè)例子，可以用其他的值，只要最后滿足IC1就可以）

Step2：?L1為例，L1會(huì)懷疑將軍發(fā)給自己的消息，于是會(huì)問(wèn)L2-L6

?	L2(R)	L3(A)	L4(R)	L5(A)	L6(X)	A(L1)
L2	R	R	R	R	A	R
L3	A	A	A	A	R	A
L4	R	R	R	R	A	R
L5	A	A	A	A	R	A
L6	R	A	R	A	A	A

Step3：其實(shí)在第三步中?L1會(huì)依次確認(rèn)在step2中, L2~L6發(fā)給自己的信息.?例如確認(rèn)L2時(shí)?會(huì)問(wèn)L3-L6,在Step2中L2發(fā)給你們了什么

最后得到?R, R, R,X?（因?yàn)?/span>L6這時(shí)候肯定又說(shuō)謊）?再結(jié)合自己的R , L1確定在Step2中收到L2發(fā)來(lái)的是R，之后又確認(rèn)了L3-L6。大家可以自己在草稿紙上畫(huà)出。

其實(shí)因?yàn)?/span>L1-L5都是忠誠(chéng)，他們不會(huì)在Step2中撒謊，所以只需投票L6即可?，(A R A R A )是L6發(fā)給L1-L5的信息，最后投出發(fā)的是A?，?將A修改到step2中L1-L5收到的

信息中其余的信息可以不用改。

最后得到L1-L5均是?4個(gè)A，?2個(gè)R。?以L1為例=R? A ?R ?A ?A ?A?

即L1~L5達(dá)成了一致。

http://www.blockchainbrother.com/article/7

總結(jié)

以上是生活随笔為你收集整理的【分布式共识二】拜占庭将军问题----口头协议的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。