什么是拜占庭将军问题？（The Byzantine Generals Problem）
拜占庭
- 拜占庭位于如今的土耳其的伊斯坦布尔,是当时东罗马帝国的首都
- 拜占庭将军问题它是由2013年图灵奖获得者计算机大神兰伯特在1982年发表的论The Byzantine Generals Problem提出。
- 拜占庭将军问题不是一个真实存在的问题，而是一个虚拟问题。
- 拜占庭将军问题本质是，在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。
由于当时拜占庭罗马帝国国土辽阔,为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序。在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成
拜占庭将军问题
- 拜占庭罗马帝国国土辽阔，为了达到防御目的，每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。
- 一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻，部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。
- 因为各位将军分处城市不同方向，他们只能通过信使互相联系。
- 在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。
- 系统的问题在于，可能将军中出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。
- 而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。
- 因此很难通过保证人员可靠性及通讯可靠性来解决问题。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，就由此形成了历史中鼎鼎有名的拜占庭将军问题。
解决方案
方案一：口头协议
- 设总人数为n, 叛徒数为m,只要满足 n＞3m, 那这个问题就是可以解决的。
- 我们可以将拜占庭将军问题简化为将军或司令和副官模型。将军是第一个提出建议的人，副官可以执行或不执行将军的命令。
- 这里需要注意的是：Lamport提出的容错的两个条件：
- IC1：即所有的忠诚的副官要遵守同一个命令，即达成一致；
- IC2：假如将军是忠诚的，那么每一个忠诚的副官都应该按照将军的意思行事。（如果将军是叛徒，所以只要满足IC1条件即可。）
情景:m=1,n=3（出错了）
- 将军G(General), 副官1和副官2
- 当叛徒数m=1,总人数=3时
- 假设将军是忠诚的，副官1是叛徒。那么就会出现一下情况：将军发起进攻命令，1和2副官收到的都是进攻命令。1是叛徒，1收到进攻，同步给2后退，此时2收到1进攻1后退,2不知道怎么办。
情景:m=1,n=4（可行）
- 将军仍然记为G,副官分别为1,2,3。
假设将军G是忠诚的，副官2是叛徒
- 将军G对1,2,3号副官发起进攻命令，那1会从2那里得到撤退命令，从3那里得到进攻命令，那1得到的命令集合就是2个进攻1个撤退命令；同样3，得到的命令集合也是2个进攻1个撤退。
假设将军G是叛徒，副官1,2,3都是忠诚的。
- 将军对1,3号副官发起进攻命令，对2副官发起撤退命令，那1会从2那里得到撤退命令，会从3那里得到进攻命令，1得到的命令集合就是2攻击1撤退，同理2,3都是2攻击1撤退。
- 1,2,3会同时进攻，满足IC1
方案二：书面协议
- 之所以会出现在口头传达中的那些错误是因为一些叛徒可以说谎，这里通过签名就是为了防止说谎。在签名算法中加了两个条件：
- （a）忠诚将军的签名是不能伪造的，内容修改可检测。（即 即使是叛徒也要原封不动的签了名将消息转发出去）
- （b）任何人都可以识别将军的签名，叛徒可以伪造叛徒司令的签名。
- 而且这里规定：每条消息只可以复制，然后加上自己的姓名再发出去。
- 下面是具体的算法：
-
- 初始化中的 Vi 类似于一个集合，表示的是第i个将军收到的命令，比如 Vi= {Attack} 之所以说是个集合是因为Vi里面不会有重复的命令出现。这在算法步骤（2）的（B) 部分描述的很清楚。
- 在算法步骤（1）中将军将签了自己姓名的消息广播发给所有副官。注意这里发的格式是 V:0，V是命令，0代表自己的身份。
-
- 算法步骤（2）（A）中，每个副官将收到的消息 V:0 把命令V放入自己的命令集合Vi（因为初始的时候他们的命令集合都是空的，所以不存在重复问题） 然后他们将命令拷贝，然后加上自己的签名 ，得到消息： V:0:i 然后再发给其他的副官。
- 在算法步骤（2）（B）中因为副官i 也会收到别的副官发来的消息v:0:1:…:jk. 此时i会判断v在不在自己的命令集合中，如果不存在的话将v加入Vi，并在k的情况下将信息签名，继续发出去。
- 在这里有几点是需要注意的。
- A） 如果将军是忠诚的话，那么因为忠诚将军的签名是不可以改的，所以所有的命令都只是V，只是消息的签名不一样罢了，那么副官将不会将重复的命令再加入Vi，所以这就是lamport在论文中提到的如果将军是忠臣的话，那么每个副官只会保存a single order 。这里之所以提到这个是后面的证明需要用到。
- B）为什么说当k的时候才会发送呢，这是因为每条信息只需要被复制m+1就可以了（这里将将军署名的时候也算是一次签名，可以发现每签名1次就是一个复制），超过m就没必要了。之所以有这样的规定会面会有证明，即只需要复制m+1此所有的忠臣就可以达成一致。还有就是这里的下标k，并不是代表一个副官的id号，而是被签名的多少次，例如 v:0:j3; 这条消息，k是等于1（因为除了将军以外只被签名了一次）的而不是3.
-
- 算法步骤（3），当一个副官不会再收到任何的消息时就会执行choice函数。这里不再收到，lamport规定是超过一个时间不再收到就认为不再收到了。这里的choice函数,lamport没做具体的实现，只是认为，当Vi中只有一个命令时就得出这个命令。当Vi和Vj是相等的时候choice执行的结果是一样的，即他们可以达成一致，这个只会在将军是叛徒的时候才会出现，这样的话就满足了IC1条件。（区块链兄弟社区，区块链技术专业问答先行者，中国区块链技术爱好者聚集地）
- 当第三步结束，就可以得出一致命令了。
证明
- 证明的总体思路是：
- 情形（一）如果将军是忠诚的话，就像我们在讨论算法的时候提到的，所有忠臣的副官只可能是收到a single order然后经过 choice函数得到的是将军的命令，所以满足IC2。
- 情形（二）这里假如将军是个叛徒。证明的总体思路是只需要证Vi，Vj是相同的集合就可以了。即只需要证明如果在step2中i将命令v放入Vi时，j也会将命令v放入Vj。
- 下面我们来证这个：
- 因为i要是想将v命令放入Vi，肯定会收到一个消息，V:0:j1:j2:…jk。那么下面就讨论： -（1）如果j属于j1~jk中的一个，那么他既然在消息上签了名，那么肯定也收到了消息v，所以在这种情况下是满足的。 -（2）如果j不属于j1~jk中的一个的话，再讨论k的范围：
- a.如果k那么i肯定会签上自己的姓名，将消息转发给所有的副官当然这里面肯定会有副官j（根据算法B中的ii），那么j要么在命令集vj中没有v的情况下将他保存，要么在已经有的情况下置之不理，但是无论是哪种情况，都会保证,Vj和Vi一致。
- b. 如果k=m.此时i不会转发此消息。但是因为只有m个叛徒，又将军是叛徒，那么这m+1个复制里面就肯定有1个是忠臣，而忠臣会不修改消息直接将叛徒将军的消息v传给所有的副官，当然包括 j， 所以在此情况下也是可以保证的。
实例证明：
- 当n=4,m=2必须要经过m+1轮复制才可以完成容错(或者说是交换)。
- 实例证明：n=4,m=2,r=m+1时（r=3 复制的轮数）可容错
- 1，当将军，L3是叛徒
step1：R1={x:0} R2={y:0} R3={0:0}
step2：k=0；1将 x:0:1 发给2,3；2将 y:0:2 发给1,3；3将 z1:0:3 发给1，将 z2:0:3 发给2。得到：
R1={x:0;y:0:2;z1:0:3} R2={y:0;x:0:1; z2:0:3} R3={0:0;x:0:1;y:0:2}
step3：k=1,k进行下一轮复制。1将 z1:0:3:1发给2,3；2将z2:0:3:2发给1,3。得到：
R1={x:0;y:0:2;z1:0:3; z2:0:3:2} R2={y:0;x:0:1; z1:0:3; z2:0:3:1} k=2算法执行choice函数。
-
书面协议的本质就是引入了签名系统，这使得所有消息都可追本溯源。这一优势，大大节省了成本，他化解了口头协议中1/3要求，只要采用了书面协议，忠诚的将军就可以达到一致（实现IC1和IC2）。这个效果是惊人的，相较之下口头协议则明显有一些缺陷。
-
书面协议的结论非常令人兴奋，这不是解决了拜占庭将军问题了吗？但请注意我们在A1~A4中实际上是添加了一些条件的，这使得拜占庭将军问题在这些假设下能够解决，但是在实际状况中却会有一些问题。观察A1~A4，我们做了一些在现实中比较难以完成的假设，比如没考虑传输信息的延迟时间，书面协议的签名体系难以实现，而且签名消息记录的保存难以摆脱一个中心化机构而独立存在。
