区块链|易理解的拜占庭将军问题——深入剖析论文精读|车联网

1.背景 1.1 场景描述

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题。

注意：拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问。

其最终目的就是：能够各方达到某一个命令的一致，这里的各方指的是忠诚的一方，那些叛军是不需要算在一起的。

1.2 与两军问题的区别 1.2.1 两军问题的定义
拜占庭将军问题和两军问题实质是不一样的，不能混为一谈。其中两军问题如下图所示：

文章图片

两军问题描述：

白军驻扎在沟渠里，蓝军则分散在沟渠两边。白军比任何一支蓝军都更为强大，但是蓝军若能同时合力进攻则能够打败白军。他们不能够远程的沟通，只能派遣通信兵穿过沟渠去通知对方蓝军协商进攻时间。是否存在一个能使蓝军必胜的通信协议，这就是两军问题

1.2.2 区别
和拜占庭将军问题有一定的相似性也有不同之处，所以我们必须注意的是：

通信兵得经过敌人的沟渠，在这过程中他可能被捕，也就是说，两军问题中信道是不可靠的，并且其中没有叛徒之说（这里有没有并不是关键问题，根本性问题是信道的不可靠，同时也是它和拜占庭将军问题的根本区别）；

由此可见，大量混淆了拜占庭将军问题和两军问题的文章并没有充分理解两者。

两军问题的根本问题在于信道的不可靠，也就是信号做不到真正的同步，那么想要做到真正的同步唯一的办法就是量子通信——毕竟遇事不决量子搞定

不过其实也是有一定的理论基础的：
1. 处于量子纠缠态的两个粒子，无论相隔多远都能够彼此同步，光是直观的来看，这个效应可以用来实现保密通讯；
2. 由于测不准原理，一测量粒子状态就会改变其状态，所以通讯时还必须通过这个信道发送另一条信息，从而使这个不可靠信道变为可靠信道。

1.3 问题的本质到底是一个关于一致性和正确性的算法问题。针对的是忠诚的将军，因为叛徒可以做出任何超出约定的判断。我们就是要在有叛徒的干扰下，找到一个抗干扰的算法。

一致性（IC1）
每一个忠诚的将军必须得到相同的( v 1 , v 2 , . . . , v n v_1,v_2,...,v_n v1?,v2?,...,vn?)指令向量或者指令集合。
正确性（IC2）
若 i i i将军是忠诚的，其他忠诚的将军必须以他送出的值作为 v i v_i vi?

1.4 现有解决方案思路类似TCP/IP的三次握手，我们也同样的是采用容错机制，通过限制一部分条件最后使得在有叛徒的情况下依然能够得到信息的真实性。
2.方案说明 2.1 方案相关背景说明失效说明：

所谓拜占庭失效指一方向另一方发送消息，另一方没有收到，或者收到了错误的信息的情形。将其统一的进行分类（同时也是满足分布式系统的失效分类，因为拜占庭将军问题其实也是属于分布式的一种情况）：

1.进行算法的另一步时失效，即崩溃失效；
2.无法正确执行算法的一个步骤；
3.执行了任意一个非算法指定的步骤。

2.2 方案1——口头协议（OM(m)算法） 2.2.1 协议内容
要求不可靠节点小于1/3,不然就可以达到欺骗的情况
满足以下三个条件的方式称为口头协议：

A1：每个被发送的消息都能够被正确的投递
A2：信息接收者知道是谁发送的消息
A3：能够知道缺少的消息

注意：口头协议并不会告知消息的上一个来源是谁,也就是没有经过签名

2.2.2 算法实现过程
1.算法描述：对于正整数 m m m和 p p p，当图 G G G是 p p p-正则的是，定义算法OM(m, p)：

算法： OM(m, p)
(0) 选取司令的一个正则邻居集 N N N，其中 N N N包含 p p p个副官；
(1) 司令发送他的值给 N N N中的每个副官；
(2) 对于 N N N中的每个 i i i，令 v i v_i vi?为副官 i i i从司令接收到的值；如果没有从司令收到指令，默认选择RETREAT。副官 i i i发送 v i v_i vi?给每个其他的副官 k k k，如下：

(A) 如果 m = 1 m=1 m=1，按照路径 r i , k r_{i, k} ri,k?发送值。其中，路径的存在由定义1的(a)(ii)部分保证。
(B) 如果 m > 1 m>1 m>1，副官 i i i当作司令，再除去已经检测出来叛乱者图中运行 O M ( m ? 1 , p ? 1 ) OM(m-1, p-1) OM(m?1,p?1)算法。——副将得到信息一致就说明司令没有叛乱，否则已经叛乱，这时候都可以去除已经叛乱的，递归一次

(3) 对于每个 k k k和 N N N中的每个 i i i，且 i ≠ k i\neq k i?=k，令 v i v_i vi?为副官 k k k在第(2)步中从副官 i i i处收到的值；如果没收到值，则为RETREAT。副官 k k k使用 m a j o r i t y ( v i 1 , . . . , v i p ) majority(v_{i_1}, ..., v_{i_p}) majority(vi1??,...,vip??)作为他的值，其中 N = i 1 , . . . , i p N={i_1, ..., i_p} N=i1?,...,ip?。

2.算法图示过程

无法判断的情况

m=1，n=3中司令忠诚而副官2是叛徒的情形：

文章图片
可以进行判断的情况
1. m=1，n=4中司令忠诚而副官3是叛徒的情形:
文章图片
1. m=2，n=7中司令忠诚而副官5和副官6是叛徒的情形:
文章图片
- 以下图表示司令忠诚时副官1在OM(1)中得到的信息
  因为A2收到司令1的信肯定不会听信一面之词，他需要看别人收到的是否一致
  
  文章图片

2.3 方案2——书面协议（SM(m)算法）

同样需要满足一致性IC1和正确性IC2。
和口头协议主要区别在于将军发令时会对信息进行签名

2.3.1 协议内容
在算法中，司令官发送一个签名的命令给他的每个副官。然后，每个副官添加他的签名到命令上，并发送给其他副官，收到命令的副官再添加他的签名发送给其他副官…
算法还假定了一个choice函数，作用在一个命令的集合上来获得一个单独的命令。choice函数需要满足：

如果命令集合 V V V只包含一个元素 v v v，那么 c h o i n c e ( V ) = v choince(V)=v choince(V)=v.

如果命令集是 ? \emptyset ?，那么 c h o i n c e ( ? ) = R E T R E A T choince(\emptyset)=RETREAT choince(?)=RETREAT.

例如，choince函数可以是取有序集合 V V V的中位数。
2.3.2 算法实现
1.算法描述令 x : i x:i x:i指由将军 i i i签名的命令值 x x x， v : j : i v:j:i v:j:i指命令指 v v v由将军 j j j签名后再由将军 i i i签名。令将军 0 0 0为司令官，每个副官 i i i维护一个命令集 V i V_i Vi?，包含他收到的被正确签名的命令值。(如果司令官是忠诚的，这个值集的元素不会超过一个)。

Algorithm SM(m)
初始化V i = ? V_i = \emptyset Vi?=?
(1) 司令官签名并发送他的命令给每个副官；
(2) 对于每个 i i i:

(A) 如果副官 i i i从司令官接收到一个 v : 0 v:0 v:0形式的消息，并且他还没有接收到过任何命令，那么：

(i) 令 V i = v V_i={v} Vi?=v;
(ii) 发送 v : 0 : i v:0:i v:0:i给每个其他的副官。

(B) 如果副官 i i i接收到形如 v : 0 : j 1 : . . . : j k v:0:j_1:...:j_k v:0:j1?:...:jk?的消息，且 v v v不在 V i V_i Vi?中，那么:

【区块链|易理解的拜占庭将军问题——深入剖析】(i) 他将 v v v添加到 V i V_i Vi?中;
(ii) 如果 k < m k

(3) 对于每个副官 i i i: 当副官 i i i不再接收到消息，他将遵从 c h o i c e ( V i ) choice(V_i) choice(Vi?)行动。

2.算法图示过程

口头协议解决不了通过书面协议去解决的两个图示：

n=3，m=1，其中司令是叛徒：

如果是口头协议的话肯定就行不通，因为司令和副官都可以进行篡改——没有签名机制在里面；

有了签名机制在里面，仅仅只能是司令进行篡改，因为副官是没法篡改司令签名过的信息；

文章图片

m=2，n=4中司令和副官3是叛徒：

文章图片

只要经过忠诚的副将转手之后便经过了签名就不可更改，所以当两个或者两个以上是忠诚的时候，那么这两个肯定统一

在第二步的时候，节点接收到信息并不是马上就相信他这个糟老头子说传的话，而是会询问其他节点他传的信息是什么，是否是一致，通过统计那种信息最多就相信谁，所以经过忠诚的传递之后的是不能篡改的，那么忠诚的信息一定是统一的

3. 结论

口头协议：将军总数为n，叛徒数量为m，OM(m)可以实现，在n>3m（至少3m+1）的情况下；
书面协议：对于任意m，最多只有m个背叛者情况下，算法SM(m)能解决拜占庭将军问题；
使用了签名的情况下，只要知道了叛徒数量，我们就可以利用SM(m)算法解决拜占庭将军问题，同理口头协议也是需要知道叛徒数量的。

书面协议的结论非常令人兴奋，这不是解决了拜占庭将军问题了吗？但请注意我们在A1~A4中实际上是添加了一些条件的，这使得拜占庭将军问题在这些假设下能够解决，但是在实际状况中却会有一些问题。观察A1-A4，我们做了一些在现实中比较难以完成的假设，比如：