拜占庭將軍問題

拜占庭將軍問題是一個共識問題: 首先由LeslieLamport與另外兩人在1982年提出，被稱為The Byzantine Generals Problem或者Byzantine Failure。核心描述是軍中可能有叛徒，卻要保證進(jìn)攻一致，由此引申到計算領(lǐng)域，發(fā)展成了一種容錯理論。

一個非正式的問題描述

拜占庭帝國想要進(jìn)攻一個強(qiáng)大的敵人，為此派出了10支軍隊去包圍這個敵人。這個敵人雖不比拜占庭帝國，但也足以抵御5支常規(guī)拜占庭軍隊的同時襲擊?；谝恍┰颍@10支軍隊不能集合在一起單點突破，必須在分開的包圍狀態(tài)下同時攻擊。他們?nèi)我恢к婈爢为氝M(jìn)攻都毫無勝算，除非有至少6支軍隊同時襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵相互通信來協(xié)商進(jìn)攻意向及進(jìn)攻時間。困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進(jìn)攻意向或者進(jìn)攻時間。在這種狀態(tài)下，拜占庭將軍們能否找到一種分布式的協(xié)議來讓他們能夠遠(yuǎn)程協(xié)商，從而贏取戰(zhàn)斗？這就是著名的拜占庭將軍問題。（其中不會去考慮通信兵是否會被截獲或者無法傳達(dá)信息等問題，即信道沒有問題。有一個相似問題叫兩軍問題）

口頭版算法（口頭協(xié)議）

image.png

假設(shè)在一個有n個將軍和m個叛徒的團(tuán)隊中，只要滿足n>=3m+1,此問題在口頭協(xié)議算法下有解。

其中：

1. 下文采用將軍——副官模型（Lamport原文也是采用該模型）會將團(tuán)隊的n個人分為1個將軍和n-1個副官進(jìn)行說明。實際上只需把將軍——副官模型遍歷至所有的將軍即可；

2. m個叛徒中可以包含1個將軍和m-1個副官，也可以是m個副官；

①OM（0）算法：

• 將軍把他的命令發(fā)給每個副官；

• 每個副官執(zhí)行將軍的命令，若未收到命令，則執(zhí)行默認(rèn)命令；

②OM（m）算法：

• 將軍把他的命令發(fā)給每個副官；

• 對于任意i<=n，Vi是副官i從將軍處收到的命令，副官i在OM（m-1）中作為將軍把Vi發(fā)送給除 將軍和副官i以外的n-2個副官；

• 對于任意j≠i，Vj是副官i在第2步中從副官j用OM（m-1）算法時收到的命令，最終副官i使用majority（V1，V2……Vn-1）算出副官i最終執(zhí)行的命令。

其中majority（V1，V2……Vn-1）= Vk ，其中Vk的值的出現(xiàn)次數(shù)最多，即副官執(zhí)行大多數(shù)人會執(zhí)行的命令，否則執(zhí)行默認(rèn)命令。注意Vk的值具有唯一性。比如V1至Vn-1中出現(xiàn)了5個A和4個R，其余值出現(xiàn)次數(shù)均小于5，則majority（V1,，V2……Vn-1）=A。但若出現(xiàn)了5個A和5個R，其余值出現(xiàn)次數(shù)均小于5，則majority（V1,，V2……Vn-1）=O，其中O則為默認(rèn)命令。

算法采用了遞歸思想。然而不得不承認(rèn)，老師在講遞歸時，我是睡過去的…因為完全無法理解…下面將舉一個例子來說明這個算法：假設(shè)n=7，m=2。即團(tuán)隊中有1個將軍（記為X），6個副官（記為A~F），其中有2個叛徒。（其中假設(shè)副官A是忠誠的）根據(jù)算法進(jìn)行演繹：

1.X向A~F發(fā)送指令，假設(shè)A收到的指令值為V1，B收到的為V2……F收到的指令為V6，其中V1到V6的值可以完全相同（將軍是忠誠的），也可以不全相同（將軍是叛徒）；

2.副官A向副官B_{F發(fā)送指令V1，副官B}F同時也會向除X和自身以外的其他5個人發(fā)送自己從將軍處收到的指令；

3.根據(jù)第2步，A會從B_{F處各收到一條指令，分別記為a2}a6。由于B_{F中有1到2個叛徒，A不能將a2}a6分別視作V2_{V6，而應(yīng)該分別確認(rèn)a2}a6的真實性。以從B收到的a2為例，A應(yīng)當(dāng)向C_{F發(fā)送a2信息，并且應(yīng)當(dāng)從C}F收到B在第2步中發(fā)給他們的信息，假設(shè)為b3~b6；

4.A可以使用majority函數(shù)算出V2=majority（a2，b3，b4，b5，b6）。副官A對于V3_{V6同理進(jìn)行操作。（按照算法說明，對于V3}V6的信息收集應(yīng)該在第3步就完成了，第4步應(yīng)該只用majority函數(shù)即可）；

5.A再使用一次majority函數(shù)算出自己應(yīng)當(dāng)執(zhí)行的命令，即為majority（V1，V2……V6）。其中V1為第1步中X發(fā)給A的指令，V2~V6是A在第4步中通過majority函數(shù)算出來的指令；

副官B~F和A同時按照上述1至5步進(jìn)行操作。一次將軍——副官模型的OM（2）計算就完成了。

問題：為什么A收到a2和a6后不能直接視作V2和V6？答：因為在有2個叛徒的情形下，V1，a2~a6的值肯定不會完全相同?？赡艽嬖赩1=V2=V3=V4≠V5≠V6。情形1：將軍是忠誠的，副官E、F是叛徒；情形2：將軍和副官E（或F）是叛徒:；上述兩種情形均會導(dǎo)致V1=V2=V3=V4≠V5≠V6。而根據(jù)拜占庭將軍問題描述：一致性：所有忠誠的副官必須遵守同一命令；正確性：如果將軍是忠誠的，則每個忠誠的副官必須遵守將軍的命令；換而言之，如果將軍是不忠誠的時候，則忠誠的副官只要遵守同一命令（即滿足正確性），而不需遵守將軍的命令（也無法遵守將軍的命令）；于是副官A不知道將軍是否忠誠，因此就不知道是否需要遵守將軍的命令。

總結(jié)：

1.在將軍——副官模型中，有1個將軍，超過3m個副官和m個叛徒的情況下，每個副官均應(yīng)使用m層majority函數(shù)，而對于任意k<=m時，該副官在第k層應(yīng)使用P（m-k,n-2）次majority函數(shù)，因此對于一次將軍——副官模型中，該副官總共要用

image.png

次majority函數(shù)；2.該算法是一個關(guān)于m的XX算法（階乘和指數(shù)的算法…），使用該算法的前提是知道m(xù)的值，并且要求n>=3m+1,即要求四模冗余。

口頭版算法證明

命題：證明OM(m)算法在n>3m（等價于n>=3m+1）時成立。

回顧口頭算法中的兩個約束條件：

IC1：所有忠誠的副官都要遵守同一個命令，即一致性；

IC2：如果將軍是忠誠的，則每一個忠誠的副官都應(yīng)該遵守將軍的命令；

在此先引入一個引理LEMMA1：對于任意非負(fù)整數(shù)m和k，當(dāng)n>2k+m且最多有k個叛徒，那么算法OM（m）滿足IC2。該引理數(shù)學(xué)證明如下：

（1）當(dāng)k=0時，若將軍是忠誠的，根據(jù)算法OM（0）可知忠臣會直接遵守將軍發(fā)來的命令，而根據(jù)IC2的假設(shè)，將軍是忠誠的，因此所有忠臣接收到的命令都是同一個值。因此當(dāng)k=0時可以O(shè)M（k）算法可以滿足IC2；

（2）當(dāng)k>=1時，由于n>2k+m，在OM（k）到OM（k-1）時，由于減少的是忠誠的將軍，因此整個算法總?cè)藬?shù)為n-1，而叛徒數(shù)仍然為k。由于n>2k+m，故n-1>2k+m-1>=2k，即n-1>2k。即在OM（m-1）算法中，忠臣的個數(shù)（n-1-k）是大于叛徒的個數(shù)（k）。由于OM（k-1）成立，因此根據(jù)majority函數(shù)投票，在將軍是忠誠的情況下，如果忠臣的個數(shù)大于叛徒的個數(shù)時，所有忠臣均會執(zhí)行將軍的指令（如果不理解的話可以令k=1，m=1推演一遍）

接著證明原命題OM（m）算法在n>3m時成立：

（1）首先假設(shè)將軍是忠誠的，那么將LEMMA1中的k換成m，則OM（m）滿足IC2，由于將軍是忠誠的，所有忠誠的副官都會執(zhí)行將軍的命令，自然也就滿足IC1；

（2）如果將軍是叛徒，則不用考慮IC2是否滿足，只需證明IC1即可。

參考LEMMA1的證明，若將軍是叛徒，則從OM（m）到OM（m-1）時，由于減少的將軍是叛徒，因此整個算法的總?cè)藬?shù)為n-1，且叛徒個數(shù)也為m-1，忠臣的個數(shù)n-m+1，由于n>3m，因此忠臣個數(shù)n-m+1>2m+1>m-1，即到OM（m-1）時忠臣是能夠達(dá)成一致的。而在OM（m-1）到OM（m-2）的情況下，除了要發(fā)送指令的將軍'，即上述案例中所述的副官A以外，還有超過3m-1個，而3m-1>3（m-1），因此在OM（m-1）的情況下，也能夠滿足原命題條件。

簽名算法（SM，書面協(xié)議）

初始化，Vi=空集

1. 發(fā)令者簽名，然后將他的消息發(fā)送給每個下屬

2. 對于任意的i：

3. 1. 如果下屬i從發(fā)令者處收到了一個形如v:0的消息，同時目前為止他還未收到任何其他命令，那么：

4. 1. 下屬i讓Vi={v}.

5. 下屬i向其他下屬發(fā)送消息v:0:i.

6. 如果下屬i收到過形如v:0:j1:…:jk的消息，同時v還未出現(xiàn)在集合Vi中，那么：

7. 1. 將v添加到Vi

8. 如果k<m,那么他就向除j1:…:jk之外的其他下屬發(fā)送消息v:0:j1:…:jk:i

9. 對于任意的i：當(dāng)下屬i不再收到任何消息時，他選擇choice(Vi)的值作為命令

image

上圖代表了當(dāng)有三個將軍且發(fā)令者是叛徒的時候，算法SM(1)的執(zhí)行情況。發(fā)令者給其中一個下屬發(fā)送進(jìn)攻命令，給另一個發(fā)送撤退命令。在步驟(2)，兩個下屬都收到了這兩個命令，因此步驟(2)之后，V1=V2={attack,retreat}，這樣他們會得到相同的choice({attack,retreat})值。并且他們都猜到發(fā)令者是叛徒。

工作量證明Pow實現(xiàn)拜占庭共識

現(xiàn)在我們看一下比特幣的工作量證明是如何解決計算機(jī)網(wǎng)絡(luò)中的拜占庭將軍問題的。比特幣網(wǎng)絡(luò)是就交易的順序，沒有中心化機(jī)構(gòu)的情況下達(dá)成共識的，同樣拜占庭將軍也是做得同樣的事情。拜占庭將軍需要攻擊城堡，所有將軍需要對任何將軍可能提出的攻擊時間達(dá)成共識。

方案一：被所有將軍都接受到的攻擊計劃，被認(rèn)為是正式的攻擊計劃。問題是：兩個或多個將軍有可能同時發(fā)出不同的攻擊計劃。

這個問題模型被工作量證明簡化了，比特幣工作量證明系統(tǒng)中，不會追蹤交易順序，取而代之是在將軍之間達(dá)成共識。每個將軍基于工作量證明，解決一個難度適當(dāng)?shù)腍ash難題，每個難題有足夠的難度，僅當(dāng)在所有的將軍同時工作時，平均10Mins會找到一個難題的答案（solution）。當(dāng)一個將軍找到問題的答案，它會把這個答案連同攻擊計劃在網(wǎng)絡(luò)中廣播。一旦收到Solution，每個將軍調(diào)整難題為在廣播中收到的攻擊時間，攻擊計劃。然后將軍繼續(xù)解決下一個工作量證明。這樣接下來每個solution會依次在第一個solution后串聯(lián)成鏈。如果有將軍還在繼續(xù)在對另一個不同的攻擊方案進(jìn)行工作量證明計算，它會切換到這個最長的鏈上。這個最長鏈上積累了最多的CPU算力。

平均一個小時后，這個鏈上會有六個區(qū)塊。每個將軍可以判斷是否有足夠多的將軍工作在含有相同初始攻擊計劃的最長鏈上。鏈會在一小時累積到六個區(qū)塊，說明大多數(shù)將軍對相同的攻擊計劃進(jìn)行工作量證明計算（CPU投票）。因此將軍對攻擊時間達(dá)成共識。

喜歡本文的朋友歡迎點贊分享~

image

唯識相鏈啟用微信交流群（Go與區(qū)塊鏈技術(shù)）

歡迎加微信：ywj2271840211