参考链接：https://zhuanlan.zhihu.com/p/44106775

1.拜占庭问题（ [Byzantine] The byzantine generals problem. Lamport L, Shostak R, Pease M. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 382-401.）

写作特点：

喜欢以演进的方式一步一步的解析并推导出问题的约束条件和目标； 根据自己的逐步加约束条件来给出自己的算法。

背景知识：

拜占庭容错（BFT）是容错计算机系统，特别是分布式计算系统的可靠性问题，其中组件可能发生故障并且关于组件是否发生故障的信息不完整。在“拜占庭式故障”中，诸如服务器之类的组件对故障检测系统可能不一致地出现故障和起作用两种情况，向不同的观察者呈现不同的状况。

其他组件很难将其声明失败并将其关闭，因为他们需要首先就哪个组件失败达成共识。所以的组件必须就协同战略达成一致，以避免灾难性的系统失败，但有些组件不可靠。拜占庭容错也被称为交互一致性或源一致性、错误雪崩、拜占庭协议问题、拜占庭将军问题和拜占庭失败。

所以，听起来神秘高大上的拜占庭问题，也就是在分布式系统中的一个共识问题。用计算机的术语来说，就是一个多主机的系统如何处理一个或者多个组件失效的问题。这个有10台主机的系统，需要有所有的主机互相通信，必须要一半以上的主机就一个问题达成一致。但是有的主机坏掉了，以至于向其他主机发送信息时出现错误。那共识问题时，当有主机失效时，其他的主机能达成一致吗？

当前研究的结论是：如果叛徒的数量大于或等于1/3，拜占庭问题不可解。

下面看论文：

摘要：为了解决存在故障节点的可靠分布式计算机系统达成一致性的问题，作者形象地将此问题类比为存在叛徒的拜占庭军队就作战计划达成一致的问题，这个问题就是区块链中有名的拜占庭问题。

正文：

将军们必须拥有一个算法可以保证：

A.所有忠诚的将军都决定同一个行动计划。

忠诚的将军们都会按照算法的要求去做，但是叛徒们可以为所欲为。不管叛徒做什么，算法都必须保证条件A。

B.少数叛徒不能使忠诚的将军采取坏的计划。（这一条件主要针对在进攻和撤退两种决策可能性几乎相等的情况下，少数叛徒才能影响这一决定，在这种情况下，两种决定都不能说是坏的。）

这里假设第i个将军发送的值为v(i),为了满足条件A，每个忠诚的将军必须获得v(1)，..., v(i)相同的信息，如果第(i)个忠诚的将军发送的信息为v(i),其他将军必须使用v(i)。

使用n=3,一个将军两个中尉来假设问题，当将军是叛徒时，分别给两个中尉发送攻击和撤退不同的指令，这时两个中尉无法判断到底是攻击还是撤退。证明必须至少有3m+1个将军才能解决m个将军是叛徒的问题。

接着假设传递的信息是作战时间。

3.先对口头消息进行证明

证明在n=3m+1的情况下，采用大多数值的策略，可以得到正确结果。采用的主要是数学归纳法，证明算法在故障节点数目=0以及m-1的情况下成立，推理出m的情况下也成立。

有三个假设：

A1.发送的每个消息都被正确传递。

A2.消息的接收者知道是谁发的。

A3.可以检测到没有消息。

4.接着，讨论带有签名消息的解决方案，不可篡改。增加一个假设

A4（a）忠诚将军的签名不能伪造，并且可以检测到他签名的信息内容的任何更改。

（b） 任何人都可以核实将军签名的真实性。

注意，我们对叛徒将军的签名没有任何假设。特别是，我们允许另一个叛徒伪造他的签名，从而允许叛徒相互勾结。

5.缺少通信路径(图的强连通性被破坏）

也证明在N>=3m时可以解决拜占庭问题

6.可靠的系统

除了使用本质可靠的电路元件外，我们所知道的实现可靠计算机系统的唯一方法是使用几个不同的“处理器”计算相同的结果，然后对其输出进行多数表决以获得单个值。（表决可以在系统内部进行，也可以由输出的用户在外部进行。）无论是使用冗余电路实现可靠的计算机以防止单个芯片的故障，还是使用冗余计算站点实现发射防御系统以防单个站点被核攻击破坏，这都是可行的。唯一的区别是复制的“处理器”的大小。

然而，任何单一的输入数据都来自单一的物理组件——例如，来自可靠计算机中的某个其他电路，或者来自导弹防御系统中的某个雷达站——一个故障组件可以为不同的处理器提供不同的值。此外，如果不同的处理器在值发生变化时读取该值，则即使是从非故障输入单元也可以获得不同的值。例如，如果两个处理器在时钟前进时读取它，那么一个可能得到旧时间，另一个得到新时间。这只能通过同步读取时钟的前进来防止。

为了使多数表决产生可靠的系统，应满足以下两个条件：

1.所有非故障处理器必须使用相同的输入值（因此它们产生相同的输出）。

2.如果输入单元是非故障的，那么所有非故障处理器都使用它提供的值作为输入（因此它们产生正确的输出）。

这些只是我们的交互一致性条件IC1和IC2，其中“指挥官”是生成输入的单元，“中尉”是处理器，“忠诚”是非故障的。

试图用“硬件”解决方案来规避这个问题是很有诱惑力的。例如，可以尝试通过让所有处理器从同一条线路读取输入值来确保所有处理器获得相同的输入值。然而，有故障的输入单元可能会沿着线路发送一个边缘信号——这个信号可以被一些处理器解释为0，也可以被其他处理器解释为1。无法保证不同的处理器从可能有故障的输入设备获得相同的值，除非让处理器彼此通信以解决拜占庭将军的问题。

当然，有故障的输入设备可能会提供无意义的输入值。拜占庭将军的解决方案所能做的就是保证所有处理器使用相同的输入值。如果输入是重要的，那么应该有几个单独的输入设备提供冗余值。例如，导弹防御系统中应该有冗余的雷达和冗余的处理点。然而，冗余输入无法实现可靠性；仍然需要确保非故障处理器使用冗余数据来产生相同的输出。

如果输入设备是非故障的，但由于在其值变化时读取它而给出不同的值，我们仍然希望非故障处理器获得合理的输入值。结果表明，如果将函数majority和choice作为中值函数，则我们的算法具有非故障处理器获得的值在输入单元提供的值范围内的特性。因此，只要输入单元产生一个合理的值范围，非故障处理器将获得一个合理的值。

我们已经给出了几种解决方案，但它们都是用拜占庭将军而不是计算系统来表述的。我们现在研究如何将这些解决方案应用于可靠的计算系统。当然，用处理器实现“通用”算法是没有问题的。问题在于实现满足假设A1-A3（算法SM（m）的假设A1-A4）的消息传递系统。我们现在按顺序考虑这些假设。

A1.  假设A1声明由非故障处理器发送的每一条消息都被正确地传递。在实际系统中，通信线路可能发生故障。对于口头消息算法OM（m）和OM（m，p），连接两个处理器的通信线路的故障与其中一个处理器的故障是不可区分的。因此，我们只能保证这些算法将在多达m个故障的情况下工作，无论是处理器故障还是通信线路故障。（当然，连接到同一处理器的多条通信线路的故障等同于单个处理器的故障。）如果我们假设一条故障的通信线路不会导致一条签名消息的伪造，那么我们将在下面看到一个非常合理的假设，然后我们的签名消息算法SM（m）对通信线路故障不敏感。更准确地说，定理4即使在通信线路故障的情况下仍然有效。失败的通信线路与简单地删除通信线路具有相同的效果——它降低了处理器图的连接性。

A2. 假设A2规定，处理器可以确定它接收到的任何消息的发起人。实际需要的是，有故障的处理器不能模拟非故障处理器。实际上，这意味着进程间通信是通过固定线路进行的，而不是通过某种消息交换网络进行的。（如果使用交换网络，则必须考虑故障网络节点，并且拜占庭将军问题再次出现。）请注意，如果假设A4并且所有消息都已签名，则不需要假设A2，因为模拟另一个处理器将意味着伪造其消息。

A3.  假设A3要求能够检测到消息的缺失。消息的缺失只能通过在某个固定时间段内未能到达来检测，换句话说，通过使用某种超时约定。使用超时来满足A3要求需要两个假设：

1. 消息的生成和传输需要固定的最大时间。

2. 发送器和接收器具有在一定的最大误差内同步的时钟。

第一个假设的必要性是相当明显的，因为接收者必须知道他需要等待消息到达多长时间。（生成时间是处理器在接收到生成消息所需的所有输入后发送消息所需的时间。）第二种假设的必要性不太明显。然而，可以证明，这个假设或一个等价的假设对于解决拜占庭将军问题是必要的。更准确地说，假设我们允许将军们仅在以下情况下采取行动的算法：

1. 在某个固定的初始时间（对所有将军都一样）。

2. 收到消息后。

3. 当随机选择的时间长度过去时。（即，将军可以将定时器设置为随机值，并在定时器关闭时动作。）

A4.  假设A4要求处理器能够以这样一种方式对其消息进行签名，即非故障处理器的签名不能被伪造。

7.结论

在各种假设下，我们提出了拜占庭将军问题的几种解决方案，并展示了它们如何用于实现可靠的计算机系统。这些解决方案在所需的时间和消息数量上都很昂贵。算法OM（m）和SM（m）都要求消息路径的长度达到m+1。换言之，每个中尉可能必须等待发自指挥官的消息，然后通过其他中尉转发。菲舍尔和林奇已经表明，对于任何能够对付m叛徒的解决方案，这都必须是正确的，因此我们的解决方案在这方面是最优的。对于一个不完全连通的图，我们的算法要求消息路径的长度达到m+d，其中d是忠诚将军子图的直径。我们怀疑这也是最优的。

算法OM（m）和SM（m）涉及发送多达（n-1）（n-2）。。。（n-m-1）消息。可以通过组合消息来减少所需的单独消息的数量。也可以减少传输的信息量，但尚未对此进行详细研究。但是，我们希望仍然需要大量的消息。

在任意故障情况下实现可靠性是一个困难的问题，而且它的解决方案似乎天生就很昂贵。降低成本的唯一方法是对可能发生的故障类型进行假设。例如，通常假设计算机可能无法响应，但永远不会错误响应。然而，当需要极高的可靠性时，这种假设是不可能的，并且需要拜占庭将军解决方案的全部费用。

总结：拜占庭问题，本质上，它是分布式系统的一致性问题。区块链最重要的特点就是分布式系统，去中心化，那么在这个系统中同样地存在一致性问题。