了解区块链的基础知识：拜占庭将军的挑战。 第一部分

本文的翻译是专门为本月开始的“ High Load Architect”课程的学生准备的。

---

区块链是一个分散的系统，由各种实体组成，这些实体根据其动机和所拥有的信息进行运作。

每当通过网络广播新交易时，节点都可以将此交易包括在其分类帐的副本中或忽略它。 当大多数网络参与者决定接受某个状态时，就可以达成共识。

分布式计算和多主体系统中的一个基本问题是在存在许多无效过程的情况下实现总体系统可靠性。 通常，这需要过程之间相互协调一些在计算过程中将需要的值。

这些过程被描述为共识。

• 当参与者决定不遵守规则并干预其账本状态时会发生什么？
• 当网络中有很多这样的参与者而不是大多数时，会发生什么？

为了确保共识协议的安全，它必须是容错的。

首先，我们将简要讨论两位将军的不可解决的问题。 然后，考虑拜占庭将军问题并讨论分布式和分散系统中的拜占庭容错能力。 最后，让我们谈谈这一切与区块链技术之间的关系。

两位将军的任务

该任务于1975年首次发布 ，并于1978年命名，描述了两个将军攻击一个共同敌人的情况。 第一位将军被认为是领导者，第二位是跟随者。 仅每个将军的军队还不足以击败敌军，因此他们需要同时进行合作和进攻。 这种情况看起来很简单，但是有一个警告：

为了使他们能够就某个时间进行沟通并达成共识，第一将军必须通过敌人的营地派遣使者，在进攻开始时必须向第二将军传达信息。 但是，信使可能会被对手捕获，并且消息不会传递。 这将导致第一个将军的军队继续进攻，而第二个将军仍留在原地。

即使传递了第一个消息，第二个将军也必须确认（他的确认（ACK），注意与TCP中的三向握手类似），因此他将信使发送回去，从而重现了可以捕获该信使的先前场景。 。 这流入无尽的ACK，因此，将军们无法达成协议。

没有办法保证第二个条件，也就是说，每个将军都完全确信对方同意进攻计划。 两位将军将永远不知道使者是否已到达战友。



事实证明 ，两位将军的任务是无法解决的。

拜占庭将军的任务

Lamport，Shostak和Piz在1982年描述了该问题，此问题的版本成为了一个亮点。 她描述了相同的情况，在该情况下，应由更多的将军代替两名将军在进攻时间达成一致。 另一个麻烦是，一个或多个将军可能是叛徒，也就是说，他们可以为自己的意图撒谎（例如，将军说他同意在09:00进攻，但不会）。

在两位将军的任务中描述的领导者跟随者的范式被转变成指挥官-下属的设施。 为了在这里达成共识，指挥官和每个下属必须就同一解决方案达成共识（进攻或撤退）。

图片翻译：

拜占庭将军的任务。 总司令必须向其n-1个下属发送命令，以便：

• 所有忠实的下属将领都遵守一个命令。
• 如果司令员是忠实的，那么他所有忠实的下属都会服从命令。

除了第二点，还必须指出一个有趣的事实：如果指挥官是叛徒，那么仍然必须达成共识。 结果，所有中尉都拥有多数票。

在这种情况下，共识算法基于下属看到的大多数决策的含义。

定理：对于任何m ， OM（m）算法均与超过3m个将军和最多m个叛徒达成共识。

这意味着当2/3的参与者诚实时，该算法可以达成共识。 如果叛徒超过1/3，则达不到共识，军队无法协调进攻，敌人获胜。

OM算法（0）

1. 指挥官将他的值发送给每个下属。
2. 每个下属都使用他从指挥官那里获得的值，或者如果他没有收到任何值，则使用值DELAY。

OM算法（m），m> 0

1. 指挥官将他的重要性发送给每个下属。
2. 对于每个i，令vi为第i个下属从指挥官接收的值，如果下属未接收到任何值，则将使用RESET值。 第i个下属在OM算法（m-1）中充当命令者，并将值发送给其余的n-2个下属。
3. 对于每个i，假设ji，令vj为在步骤（2）中从第j个下属收到的第i个下属的值（使用OM算法（m-1）），或者在以下情况下使用值DISCONNECT没有任何意义。 第i个从站使用多数值（v1，...，vn-1）。

当m = 0时，没有叛徒，每个下属都遵循该顺序。 对于m> 0，对下属的每个最终选择都是从选举所有下属的主要部分开始的。
如果从第二个下属的角度来看情况，将会更加清楚-令C为司令，L {i}为第i个下属。



OM（1）：下属3是叛徒。 从下属的角度来看情况。

步骤：

1. 指挥官将v发送给所有下属。
2. L1向L2发送v的值，或者L3向L2发送x的值。
3. L2←多数（v，v，x）== v

最后的决定是由L1，L2和L3的大多数票决定的，因此达成了共识。

重要的是要记住，目标是大多数下属选择相同的解决方案，而不是特定的解决方案。

让我们看一下指挥官是叛徒的情况。



OM（1）：指挥官是叛徒。

步骤：

1. 指挥官分别向L1，L2，L3发送x，y，z的值；
2. L1将x的值发送到从站L2，L3 | L2向L1，L3发送y |的值。 L3向L1，L2发送z的值；
3. L1←多数（x，y，z）| L2←最（x，y，z）| L3←多数（x，y，z）

它们都具有相同的价值，因此可以达成共识。 请注意，即使x，y，z的值都不同，所有三个下属的多数值（x，y，z）也相同。 如果x，y，z的阶数完全不同，我们可以假定它们将按照默认计划RESET起作用。

要查看一个实用的方法来处理具有7个将军和3个叛徒的更复杂示例，建议您阅读本文 。

拜占庭容错

拜占庭的容错能力是一种特征，它定义了一个系统，该系统允许属于拜占庭将军任务的一类故障。 拜占庭式故障是最复杂的故障类型 。 它并不意味着任何限制，也不假设节点可以具有哪种行为（例如，一个节点可以生成任何真实的数据，冒充诚实的参与者）。

拜占庭式错误最难解决。 飞机发动机系统，核电站以及几乎任何其动作取决于大量传感器结果的系统中，都需要拜占庭容错。 甚至SpaceX都将其视为其系统的潜在需求 。

上一节中提到的算法对应于拜占庭的容错能力，直到叛徒的人数超过所有将军的三分之一。 还有其他选项可以简化此任务，包括使用数字签名或引入对等方之间的通信限制。

这一切与区块链有何关系？

区块链是去中心化的分类账，根据定义，它们不受中央机构的控制。 由于存储在其中的价值，攻击者有良好的经济动力去尝试犯错。 然而，拜占庭的容错性以及因此解决区块链的拜占庭一般性问题是非常必要的。

在没有拜占庭容错的情况下，对等方可以传输和发布虚假交易，从而完全抵消了区块链的可靠性。 更糟的是，没有中央机构可以承担责任并修复损害。

当比特币被发明时，一个重大突破是使用了拜占庭将军问题概率解决方案的证据。 中本聪（Satoshi Nakamoto）在此电子邮件中已对其进行了详细描述。

结论

在本文中，我们研究了分布式系统中共识的一些基本概念。