区块链本质上是分布式系统，其中包含不同的参与者，基于各自动机和可用信息行动。
每当一笔新交易在网络中广播出来，节点有权选择将该交易纳入其持有的账本副本之中，或者将其忽略。当网络中的大部分参与者选定某一状态之时，就能达成共识。
分布式计算和多智能体系统的一个基本问题是如何在一些错误流程存在的情况下实现总体系统的可靠性。这通常需要各个流程就计算中所需的某些数据值达成一致意见。¹
这些过程被称为共识。
- 当某个参与者决定不遵守规则并篡改其账本状态之时会发生什么状况？
- 当这些参与者构成网络中的一大部分且总数不过半之时会发生什么状况？
要创建一种安全的共识协议，必须实现容错性。
首先，我们将简要谈谈无法解决的“两军问题（Two Generals' Problem)”。之后我们会延伸至拜占庭将军问题并讨论在分布式和去中心化系统中的拜占庭容错。最后，我们会探讨上述内容与区块链领域有何关联。
两军问题
这一问题（最早于1975年提出，并于1978年得名）描述了一个两军共同抗敌的场景。将军1是领导者，而将军2是跟随者。两位将军各自的军队不足以击败敌军，因此他们需要联手同时进攻。虽然这看似是一个简单的场景，却内含警示之意：
为了双方能够交流并选定时间，将军1需要派遣一名通信兵穿越敌军阵营通知将军2进攻时间。然而，通信兵有可能被敌方捕获，致使消息传递失败。结果导致将军1在发动进攻之时将军2仍驻守原地。
即便第一次传信成功了，将军2必须承认（即ACK（acknowledge），注意这与TCP协议的“三次握手”相似）已收到消息，于是他派遣了一名通信兵回信，因此又会出现之前通信兵被捕获的情况。这就会引起无数次地重传 ACK 确认符，导致两位将军无法达成共识。
要实现这两位将军都确认对方同意作战方案的第二点要求是不可能的。两位将军总是会心存疑惑，想知道他们的最后一名通信兵是否成功穿越了敌方阵营。
-因为消息传递失败的可能性始终大于0，两位将军永远不可能在100%的信任下达成共识。-
两军问题已经被证明是无解的。
拜占庭将军问题
Lamport、Shostak和Pease在1982年发表的一篇著名文章中描述了拜占庭将军问题，它是改编后的两军问题的广义版本。该问题描述了一个相同的场景，只不过需要由两位以上共同抗敌的将军就进攻时间达成一致。其复杂性更强，因为一位或多位将军可能叛变，此即表明他（们）可能会在做出选择时撒谎（例如，他们会假意同意在9点发起攻击但并不行动）。
两军问题中描述的领导者-跟随者模式转变成了指挥官-副官模式。在拜占庭将军问题中，为了达成共识，指挥官和每位副官必须就同一决定达成一致意见（简单来说就是攻击或撤退）。
-拜占庭将军问题，第三页-
此外，上图中的条件 IC2 还可能出现一种有趣的情况，如果指挥官叛变了，依然要达成共识。结果，所有副官取得了多数票。
在这种情况下，达成共识的算法依据的是由副官观察到的大多数成员决定的值。
原理：取任意值m，如果将军人数为3m以上，叛徒的人数不超过m，算法OM(m)则达成共识。
这表明只要有 2/3 的参与者是忠诚的，该算法就能达成共识。如果叛徒的人数超过 1/3 ，则无法达成共识，同盟军无法协调进攻，敌方获胜。
- m = 0 →没有叛徒，所有副官选择一致 m > 0 →每位副官的最终选择取决于绝大多数副官的选择 -
从副官2的视角图示举例会更加直观清楚——以C代指指挥官，L{i}代指副官i：
- OM(1) :副官3是叛徒——副官2的视角-
步骤：
- 指挥官将v发送给所有副官
- L1将v发送给L2 | L3将x发送给L2
- L2计算收集到的消息可知：v是大多数，L2 ←majority(v,v,x) == v
最终决定取决于L1, L2, L3中的多数票，因此达成了共识。
要记住的重要一点是该算法旨在让多数副官选择相同的决定，而非某一决定。
让我们探究一下指挥官叛变的情况：
- OM(1) :指挥官是叛徒-
步骤：
- 指挥官分别向L1, L2, L3发送 x, y, z
- L1 向L2, L3 发送x | L2向L1, L3发送y | L3向L1, L2发送z
- L1 ← majority(x,y,z) | L2 ← majority(x,y,z) | L3 ← majority(x,y,z)
因为三位副官得到的值相同，因此达成了共识。此处请略微思考一下，即使x, y, z均不相同，对于三位副官来说majority(x, y, z)得出的值也是一样的。在这种情况下，x,y,z是完全不同的指令，我们可以假定他们采取了默认选项撤退。
如果你想了解更具体实际的方法以及7位将军两位叛徒这样更复杂的例子，我建议你阅读这篇文章。
拜占庭容错
拜占庭容错定义了一类系统的特征，即允许出现属于拜占庭将军问题的错误。拜占庭容错是最难的一类容错模式。它没有限制条件，也没有对节点可能做出的行为进行假设（例如，一个节点在充当一个诚实的参与者之时可以生成任意数据）。
拜占庭容错是最难解决的。航空发动机系统、核能工厂，以及几乎所有依靠大量传感器的结果决定行动的系统都需要拜占庭容错。甚至连 SpaceX 都认为其系统对此有着潜在需求。
上一节提到的算法是拜占庭容错以及叛徒人数不超过将军人数的 1/3 的情况。此外还存在其它能使该问题更容易解决的方案，其中包括使用数字签名或在网络中设置节点之间的交流限制。
这些都跟区块链有什么关系？
从定义上来看，区块链是不受任一中心主体控制的分布式账本。由于这些账本内蕴藏的价值，不良参与者有着极大的经济激励来试图引发错误。此即表明，区块链很需要拜占庭容错，即解决拜占庭将军问题的方案。
在没有拜占庭容错的情况下，一个节点能够发送并发布错误交易，极大地破坏区块链可靠性。更糟糕的是，没有中心主体能够掌握控制权并且修复损伤。
正如中本聪在这封邮件中深入描述的那样，比特币的问世带来了一项重大突破，即使用工作量证明作为拜占庭将军问题的概率解决方案。
结论
在本文中，我们讨论了分布式系统共识的几个基本概念。
在下一篇文章中，我们将讨论和比较一些用于区块链、实现拜占庭容错的算法。
原文链接: https://medium.com/loom-network/understanding-blockchain-fundamentals-part-1-byzantine-fault-tolerance-245f46fe8419
作者: Georgios Konstantopoulos