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

拜占庭將軍問題

假設(shè)

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

A4 (a) 忠誠將軍的簽名不能被偽造，并且任何針對(duì)他簽名消息的篡改都能被檢測(cè)到；
(b) 任何將軍都可以驗(yàn)證將軍簽名的真實(shí)性

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

引入了簽名消息之后，三將軍問題也就不在成立了?，F(xiàn)在給出一個(gè)算法，在任意數(shù)量將軍中有m個(gè)叛徒的情況。

SM(m) 算法

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

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

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

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

在下面的算法中，令$x:i$指由將軍$i$簽名的命令值$x$，$v:j:i$指命令指$v$由將軍$j$簽名后再由將軍$i$簽名。令將軍$0$為司令官，每個(gè)副官$i$維護(hù)一個(gè)命令集$V_i$，包含他收到的被正確簽名的命令值。(如果司令官是忠誠的，這個(gè)值集的元素不會(huì)超過一個(gè))。

Algorithm SM(m)

初始化 $V_i = \emptyset$

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

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

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

(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$的每個(gè)副官。

(3) 對(duì)于每個(gè)副官$i$: 當(dāng)副官$i$不再接收到消息，他將遵從$choice(V_i)$行動(dòng)。

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

舉例： m=1, n=3

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

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

因此，當(dāng)司令叛徒時(shí)，算法滿足條件IC1。

當(dāng)司令是忠誠的時(shí)，叛徒副官無法篡改司令的命令，因此忠誠的副官的行動(dòng)值集$V_i$只有一個(gè)元素，即司令發(fā)送的命令。

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

證明

下面證明算法的正確性：

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

證明： 首先證明條件IC2。如果司令是忠誠的，那么在第(1)步中，他發(fā)送簽名的命令$v:0$給每個(gè)副官。在第(2)(A)步中，每個(gè)忠誠的將軍收到命令$v$。而且，因?yàn)榕淹綗o法篡改將軍的命令成$v':0$，所以忠誠的副官不會(huì)在第(2)步中收到其他值因此每個(gè)忠誠的副官將按照司令的命令$v$行動(dòng)。條件IC2得證。

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

如果兩個(gè)忠誠的副官$i$和$j$在第(2)步中收到的行動(dòng)值集$V_i$和$V_j$相同，那么他們會(huì)采取相同的命令。因此，證明條件IC1，等于證明如果副官$i$在第(2)步中將值$v$放入其值集$V_i$中，那么，副官$j$也會(huì)將$v$放入其值集$V_j$。

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

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

1. $k<m$。在這種情況下，副官$i$會(huì)發(fā)送$v:0:j_1:...:j_k:i$消息給副官$j$，因此副官$j$會(huì)收到指令$v$；
2. $k=m$。在這種情況下，因?yàn)樗玖钍桥淹剑敲锤惫僦兄炼嘤?m-1$個(gè)叛徒，因此在$j_1:...:j_m$中至少有一個(gè)副官是忠誠的，這個(gè)忠誠的副官肯定將指令$v$發(fā)給了副官$j$，因此，副官$j$擁有指令$v$。

結(jié)論得證。

小結(jié)

在本篇文章中，介紹了當(dāng)將軍之間傳輸不能篡改的簽名消息時(shí)，拜占庭將軍問題的算法SM(m)，算法能夠處理在n個(gè)將軍中至多有m個(gè)叛徒的情況($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. ?