在上篇文章中烛卧，對口頭消息算法OM(m)進(jìn)行了闡述肮砾，OM(m)算法能夠處理在大于3m個將軍中至多存在m個叛徒的拜占庭將軍問題涝婉。Leslie的論文^[1]中侮攀，對將軍之間發(fā)送不可篡改的簽名消息的情況進(jìn)行分析扮休，闡述書面協(xié)議算法SM(m)迎卤。

拜占庭將軍問題

假設(shè)

為了限制叛徒發(fā)送的消息，從而使拜占庭將軍問題更加簡單玷坠。一種方法是讓每位將軍發(fā)送不可偽造的簽名消息蜗搔。更準(zhǔn)確的來說，在假設(shè)A1-A3的基礎(chǔ)上添加如下假設(shè)：

A4 (a) 忠誠將軍的簽名不能被偽造八堡，并且任何針對他簽名消息的篡改都能被檢測到樟凄；
(b) 任何將軍都可以驗證將軍簽名的真實性

注意，我們并沒有對叛徒的簽名進(jìn)行限制兄渺，也就是說一個叛徒的簽名可以被其他叛徒偽造缝龄，進(jìn)而叛徒可以進(jìn)行串謀作惡。

引入了簽名消息之后挂谍，三將軍問題也就不在成立了∈迦溃現(xiàn)在給出一個算法，在任意數(shù)量將軍中有m個叛徒的情況口叙。

SM(m) 算法

在算法中炼绘，司令官發(fā)送一個簽名的命令給他的每個副官。然后妄田，每個副官添加他的簽名到命令上俺亮，并發(fā)送給其他副官，收到命令的副官再添加他的簽名發(fā)送給其他副官......

算法還假定了一個choice函數(shù)疟呐，作用在一個命令的集合上來獲得一個單獨的命令脚曾。choice函數(shù)需要滿足：

1. 如果命令集合$V$只包含一個元素$v$，那么$choince(V)=v$.
2. 如果命令集是$\emptyset$启具，那么$choince(\emptyset)=RETREAT$.

例如本讥，choince函數(shù)可以是取有序集合$V$的中位數(shù)。

在下面的算法中富纸，令$x:i$指由將軍$i$簽名的命令值$x$囤踩，$v:j:i$指命令指$v$由將軍$j$簽名后再由將軍$i$簽名。令將軍$0$為司令官晓褪，每個副官$i$維護(hù)一個命令集$V_i$堵漱，包含他收到的被正確簽名的命令值。(如果司令官是忠誠的涣仿，這個值集的元素不會超過一個)勤庐。

Algorithm SM(m)

初始化 $V_i = \emptyset$

(1) 司令官簽名并發(fā)送他的命令給每個副官示惊；
(2) 對于每個$i$:

(A) 如果副官$i$從司令官接收到一個$v:0$形式的消息，并且他還沒有接收到過任何命令愉镰，那么：

(i) 令$V_i={v}$;
(ii) 發(fā)送$v:0:i$給每個其他的副官米罚。

(B) 如果副官$i$接收到形如$v:0:j_1:...:j_k$的消息，且$v$不在$V_i$中丈探，那么:

(i) 他將$v$添加到$V_i$中;
(ii) 如果$k<m$录择，那么他發(fā)送消息$v:0:j_1:...:j_k:i$給不同于$j_1:...:j_k$的每個副官。

(3) 對于每個副官$i$: 當(dāng)副官$i$不再接收到消息碗降，他將遵從$choice(V_i)$行動隘竭。

注意，在第二步中讼渊，副官$i$將忽略任意值已經(jīng)在$V_i$出現(xiàn)的消息动看。通過對$k$的歸納，對于每個副官序列$j_1, ..., j_k$, 且$k<m$爪幻，每個副官至多收到一條$v:0:j_1:...:j_k$消息菱皆。在第(3)步中可以使用超時來判斷沒有消息再回到來。

舉例： m=1, n=3

下圖描述了當(dāng)將軍是叛徒時挨稿，發(fā)送消息的情況：

在第(1)步仇轻，司令發(fā)送發(fā)送“attack”給副官1并發(fā)送“retreat”給副官2；
在第(2)步奶甘，每個副官將收到兩個命令值拯田，即$V_1=V_2={"attack", "retreat"}$。
在第(3)步甩十，兩個忠誠的副官執(zhí)行$choice(V_i)$得到的結(jié)果也是一樣的。

因此吭产，當(dāng)司令叛徒時侣监，算法滿足條件IC1。

當(dāng)司令是忠誠的時臣淤，叛徒副官無法篡改司令的命令橄霉，因此忠誠的副官的行動值集$V_i$只有一個元素，即司令發(fā)送的命令邑蒋。

因此姓蜂，SM(m)算法滿足條件IC1和IC2。

證明

下面證明算法的正確性：

定理 2：對于任意$m$,當(dāng)將軍中至多有$m$個叛徒時医吊，算法SM(m)能解決拜占庭將軍問題钱慢。

證明： 首先證明條件IC2。如果司令是忠誠的卿堂，那么在第(1)步中束莫，他發(fā)送簽名的命令$v:0$給每個副官懒棉。在第(2)(A)步中，每個忠誠的將軍收到命令$v$览绿。而且策严，因為叛徒無法篡改將軍的命令成$v':0$，所以忠誠的副官不會在第(2)步中收到其他值因此每個忠誠的副官將按照司令的命令$v$行動饿敲。條件IC2得證妻导。

當(dāng)司令是忠誠的時，條件IC1包含在條件IC2中怀各，因此倔韭，下面僅需證明當(dāng)將軍是叛徒時，條件IC1成立渠啤。

如果兩個忠誠的副官$i$和$j$在第(2)步中收到的行動值集$V_i$和$V_j$相同狐肢，那么他們會采取相同的命令。因此沥曹，證明條件IC1份名，等于證明如果副官$i$在第(2)步中將值$v$放入其值集$V_i$中，那么妓美，副官$j$也會將$v$放入其值集$V_j$僵腺。

如果副官$i$在第(2)(A)步收到命令$v$，那么他會在第(2)(A)(ii)步將其發(fā)送出去壶栋，因此副官$j$也會受到值$v$辰如。

如果副官$i$在第(2)(B)步將一個命令$v$添加到$V_i$中，那么他肯定收到了形如$v:0:j_1:...:j_k$的消息贵试。如果$j$是$j_1:...:j_k$中的一個琉兜，那個副官$j$肯定也已經(jīng)收到命令值$v$。否則毙玻，討論兩種情況：

1. $k<m$豌蟋。在這種情況下，副官$i$會發(fā)送$v:0:j_1:...:j_k:i$消息給副官$j$桑滩，因此副官$j$會收到指令$v$梧疲；
2. $k=m$。在這種情況下运准，因為司令是叛徒幌氮，那么副官中至多有$m-1$個叛徒，因此在$j_1:...:j_m$中至少有一個副官是忠誠的胁澳，這個忠誠的副官肯定將指令$v$發(fā)給了副官$j$该互，因此，副官$j$擁有指令$v$韭畸。

結(jié)論得證慢洋。

小結(jié)

在本篇文章中塘雳，介紹了當(dāng)將軍之間傳輸不能篡改的簽名消息時，拜占庭將軍問題的算法SM(m)普筹，算法能夠處理在n個將軍中至多有m個叛徒的情況($n\geq m$)败明。

口頭協(xié)議和書面協(xié)議都假設(shè)了將軍之間是能夠直接通信的，后續(xù)的文章中將介紹不是所有將軍都能直接通信的情況下拜占庭將軍問題的解法太防。

1. Lamport L, Shostak R, Pease M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 382-401. ?