1.2 问题分析与证明
描述拜占庭问题的原始论文是通过口头和书面两种消息传递方式来分析的，将军也分为发令者和副官。
1.2.1 通过口头消息
只通过口头的方式传递消息，可以达成一致的前提为：如果有m个叛国将军，则将军的总数必须为3m+1个以上。
下面是口头消息传递过程中默认的一些条件。
A1：每个被发送的消息都能够被正确地投递。
A2：信息接收者知道是谁发送的消息。
A3：能够知道缺少的消息。
A1和A2假设两个将军之间通信没有干扰，即不会有背叛者阻碍消息的发送（截断），也不会有背叛者伪造他人消息的情况，每个将军都可以无误地将自己的消息发送给其他将军。
我们定义口头消息算法OM(m)。对于所有的非负整数m，每个发令者通过OM(m)算法发送命令给其他n-1个副官。下面解释说明OM(m)算法在最多有m个背叛者且总将军数至少为3m+1的情况下，为何能解决拜占庭将军问题。
算法定义一个函数majority(com1, com2,…,comN)，表示重复次数最多的命令。
OM(0)算法描述如下（初始设置）。
（1）发令者将他的命令发送给每个副官。
（2）每个副官执行他从发令者得到的命令，如果没有收到任何命令，则默认为撤退。
OM(m)算法描述如下（中间过程）。
（1）发令者将他的命令发送给每个副官。
（2）对于每个i，vi是每个副官i从发令者收到的命令，如果没有收到命令，则为撤退命令。副官i在OM(m-1)中作为发令者将vi发送给另外n-2个副官。
（3）对于每个j，并且j≠i，vj是副官j从第（2）步中副官i发送来的命令（使用OM(m-1)算法），如果没有收到第（2）步中副官i的命令，则默认为撤退命令。最后副官j使用majority(v1,…,vN-1)得到最终指令。
可能算法在描述上比较复杂，但是结合图例大家就能很清晰明了地理解。我们来考虑一个n=4，m=1的情况。
1. 副官D是背叛者
第一步：发令者A执行算法OM(1)将自己的命令发送给3个副官B、C、D，3个副官都正确地收到了命令，如图1-1所示。
图1-1 发令者发送命令（D为背叛者）
第二步：每个收到命令的副官都作为发令者执行算法OM(1)，将自己收到的命令转发给其余副官，因为副官D是背叛者，所以他给副官B和C传递的消息可能是假消息，如图1-2所示。副官B和C分别根据majority函数决定命令。
图1-2 副官转发命令（D为背叛者）
根据判定函数，B、C最后得到的结果都是1（与发令者相同）。因此，背叛的副官D无法干扰发令者的决定。那如果发令者是背叛者呢？
2. 发令者是背叛者，其余副官是忠诚的
第一步：发令者A向副官B、C、D发送不同的命令，如图1-3所示，这在实际情况中就是一个攻击者向不同方发送了不一致的值（如0或1），企图扰乱副官做出一致决定。
图1-3 发送者发送命令（A为背叛者）
第二步：副官收到命令后，变为发令者执行OM(1)向所有的副官发送命令，如图1-4所示。通过多数表决算法，可以看到，副官最后仍可达成一致的命令。
图1-4 副官转发命令（A为背叛者）
这里没有提到多叛徒的形式，感兴趣的读者可以自己查阅原始文献。Lamport证明了在采用口头协议的情况下，将军总数大于3m、背叛者为m或者更少时，忠诚的将军可以达成命令上的一致。
1.2.2 通过书面消息
通过以上描述可以看到：口头协议这种传递方式最大的缺点是消息不能溯源。那我们是否可以加入某些规则，让信息可以追本溯源，从而改变现状？这就是书面消息引入的灵感。
我们在口头消息A1~A3这3点要求的基础上，加入新的条件A4，使之成为书面消息。
A4：① 签名不可被伪造，一旦被篡改即可发现；
② 任何人都可以验证将军签名的可靠性。
先说结论：对于任意m，最多只有m个背叛者的情况下，算法SM(m)能解决拜占庭将军问题。也就是说，SM(m)算法一定可以使忠诚的将军达成一致（但这个一致的结果并不一定正确）。
回顾下拜占庭将军问题的要求。
IC1：所有忠诚的副官都遵守一个命令，即一致性。
IC2：若发令者是忠诚的，每一个忠诚的副官遵守他发出的命令，即正确性。
我们要找到一个算法SM(m)，使不管将军总数n和叛徒数量m是多少，只要采用该算法，忠诚的将军总能达成一致甚至正确（即上面的IC1和IC2）。我们用集合Vi表示i副官收到的命令集，这是一个集合，也就满足互异性（没有重复的元素）等集合的条件。类似地，我们定义choice(V)函数来决定各个副官的选择，这个函数可以有多种形式，它只要满足以下两个条件。
（1）如果集合V只包含一个元素v，那么choice(V)=v。
（2）choice(O)=RETREAT，其中，O是空集。
任何满足这两个条件的函数都可以作为choice()，我们只需要根据具体情形定义choice()即可，函数至少要做到对于相同的输入集合V，有一致的输出choice(V)。
根据A4和choice()可得出SM(m)算法。
（1）初始化Vi=空集合。
（2）将军签署命令并发给每个副官。
（3）对于每个副官i：
① 如果副官i从发令者收到v:0的消息，且还没有收到其他命令序列，那么
• 使Vi为{v}；
• 发送v:0:i给其他所有副官；
② 如果副官i收到消息v:0:(j1:…:jk)且v不在集合Vi中，则
• 添加v到Vi；
• 如果k<m，那么发送v:0:(j1:…:jk:i)给每个不在j1,…,jk 中的副官。
（4）对于每个副官i，当不再收到消息时，则遵守命令choice(Vi)。
值得注意的是，如果将军忠诚，由于其签名不可伪造，所有忠诚的副官将得到一个单点集{v}，他们采用的命令集Vi相同，得到的choice(Vi)也为v，满足了IC1和IC2；如果将军并非忠诚，只需要满足IC1，但是算法SM(m)使所有忠诚的副官得到相同的Vi，使用choice()函数后采用的命令也就一定相同。
同样举个例子，如图1-5所示，有3个人，其中，发令者A是背叛者。由于忠诚的人数小于3m这个设定，因此这种情况在口头消息中是解决不了的。
很显然，副官1得到的L1={B,C}，副官2得到相同的L2={B,C}。他们采用choice()函数后得到的命令一定相同。
书面协议的本质是引入了签名系统，这使所有消息可追本溯源。这一优势大大节省了成本，也化解了口头协议中1/3要求，只要采用了书面协议，忠诚的将军就可以达成一致（实现IC1和IC2）。这个效果是惊人的，相较之下，口头协议则明显有一些缺陷。
图1-5 书面消息示例
书面协议的结论貌似完美，这不是解决了拜占庭将军问题吗？但请注意，我们是添加了前提条件A1~A4，使拜占庭将军问题在这些假设下能够解决。但在实际状况中会有一些问题，条件A1~A4是一些在现实中非常难以完成的假设，如没考虑传输信息的延迟时间、异步情况下节点步伐不一致、书面协议完美的签名体系难以实现等，因此这个效果几乎是无法达到的。
虽不能做到完美，但我们还是可以探索尽量完善的解决方案。区块链就很好地解决了使多个节点达成一致性且保证正确性的问题，从而保证了去中心化对等系统的自组织运行。本章只是抛砖引玉，后面我们会用一章详谈共识问题。下面，让我们走进区块链的世界。