什么是拜占庭将军问题，如何理解“拜占庭容错”？

拜占庭将军问题首先是由 Leslie Lamport 等人在 1982 年提出，被称为 The Byzantine Generals Problem 或者 Byzantine Failure。

这个问题是这样描述的：

拜占庭帝国派出多支军队去围攻一个强大的敌人，每支军队有一个将军，但由于彼此距离较远，他们之间只能通过信使传递消息。

敌方很强大，必须有超过半数的拜占庭军队一同参与进攻才可能击败敌人。在此期间，将军们彼此之间需要通过信使传递消息并协商一致后，在同一时间点发动进攻。

问题难点：将军们不确定他们中是否有叛徒，叛徒可能会擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭的将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？

以上，这就是著名的拜占庭将军问题。

问题实质推演

回顾上述问题：

一群将军想要实现“一致进攻或者一致撤退”的目标，但是单独行动行不通，必须合作， 达成共识；由于叛徒的存在，将军们不知道应该如何达到一致。

注意，这里“一致性”才是拜占庭将军问题探讨的内容，如果本来叛徒数量就已经多到了问题不可解的地步，这个就是“反叛”的问题了；

同时，我们的目标是忠诚的将军能够达成一致，对于这些忠诚的将军来说，进攻或者撤退都是可以的，只要他们能够达成一致就行。

但是，光靠“一致性”不能解决问题。

如果万事俱备，客观上每个忠诚的将军只要进攻了就一定能够胜利，但是却因为叛徒的存在他们都“一致性”没有进攻；

反之，条件不利，将军们不应该进攻，但是却因为叛徒的存在所有人都“一致性”进攻了。

所以，我们还需要提出一个“正确性”要求，如何定义这个“正确性”呢？

或许可以简单地说，正确就是每个忠诚的将军都正确的表达了自己的意思，不会因为叛徒让别的将军认为忠诚的将军是叛徒而不采用他传达的消息。

最终，所有忠诚的将军都能够让别的将军接收到自己的真实意图，并最终一致行动，而形式化的要求就是：“一致性”与“正确性”。

问题的细化分析

介绍到现在，可能还是不好理解，下面以具体案例辅助解释一下：

把问题简化一下，假设只有三个拜占庭将军，分别为A、B、C，他们要决定的只有一件事情：明天是进攻还是撤退。

为此，将军们需要依据“少数服从多数”原则投票表决，只要有两个人意见达成一致就可以了。

举例来说，A 和 B 投进攻，C 投撤退：

• 那么A的信使传递给B和C的消息都是进攻；
• B的信使传递给A和C的消息都是进攻；
• 而C的信使传给A和B的消息都是撤退。

如此一来，三个将军就都知道进攻方和撤退方二者占比是 2 : 1 了。显而易见，进攻方胜出，第二天大家都要进攻，三者行动最终达成一致。

目前看来一切比较顺利，理解起来也非常简单，但是，假如三个将军中存在了一个叛徒呢？

叛徒的目的是破坏忠诚将军间一致性的达成，让拜占庭的军队遭受损失。

问题难点

假设 A 和 B 是忠诚将军，A 投进攻，B 投撤退，如果 C 是这个叛徒将军，那么 C 该做些什么，才能在第二天让两个忠诚的将军做出相反的决定呢？

目前看来，进攻方和撤退方现在是 1 : 1 ，无论 C 投哪一方，都会变成 2 : 1 ，一致性还是会达成。

但是，作为叛徒的 C 必然不会按照常规出牌，于是他让一个信使告诉 A 的内容是你“要进攻”，让另一个信使告诉 B 的则是“要撤退”。

至此，A 将军看到的投票结果是：

进攻方 ：撤退方 = 2 : 1

B 将军看到的投票结果是：

进攻方 ：撤退方 = 1 : 2

第二天，忠诚的 A 冲上了战场，却发现只有自己一支军队发起了进攻，而同样忠诚的 B，却早已撤退。最终，A 的军队败给了敌人。

截止目前，你有没有发现，明明大多数将军都是忠诚的（2/3），却被少数的叛徒（1/3）耍得团团转？

实质上，“拜占庭将军”问题的可怕之处就在于此：在一致性达成的过程中，叛徒将军（恶意节点）甚至不需要超过半数，就可以破坏占据多数的正常节点一致性的达成。

狡猾的叛徒

这时候，会存在你可能不相信甚至无法接受的一种情况：在大多数将军都是忠诚的情况下，却无法抓出这个为所欲为的叛徒。

还是上面的例子，假设 A 与 B 是忠诚的将军，C 是叛徒将军。忠诚的将军经历了上次战役的失败，就已经发觉他们中出现了叛徒，但是并不知道具体是谁。

依旧是上面投票的例子，A 投进攻，B 投撤退，C 传递给 A 和 B 两种不同的消息。

现在，我们从忠诚将军 A 的视角来看一下，他是如何做决策的。

A 现在知道另外两人中可能有一个是叛徒，他收到了 B 的撤退消息和 C 的进攻消息，他应该如何分辨呢？

A 可以问一下 B：“我从 C 那儿收到的是进攻，你从 C 那儿收到的是什么？”

因为 B 是忠诚的将军，不会伪造信息，B 会告诉 A：“收到的是撤退。”

C 发送了两条不同的消息，A 现在也发现了这个问题，但是 A 现在就可以判断 C 是叛徒了么？

可悲的事情发生了，尽管忠诚的 B 说了实话，但是 A 反而对他产生了怀疑。因为从 A 的视角来看，B 和 C 的说法不一致，他无法判断：

• 到底是第一次发送了两条不同消息的C是叛徒呢?
• 还是明明C初次告知了B的是进攻，B却和A说C告知的是撤退，B是叛徒呢?

同样的情况，也会出现在 B 身上，两个忠诚的将军无法做正确的判断，而可以任意进行信息造假的叛徒 C，此时只需要再次进行消息伪造：

和 A 说“ B 告知我的消息是进攻”，和 B 说“A 告知我的消息是撤退”，如此一来，就可以进一步把信息搞混，从而隐藏了自己是叛徒的真相。

由此我们可以得出一个结论：在拜占庭三个将军中出现一个叛徒，并且叛徒可以任意伪造消息的情况下，只要叛徒头脑清醒，他就始终无法被发现，甚至还能造成整个系统的信任危机。

根据这一结论进一步推导可以得出一个更通用的结论，如果存在 m 个叛徒将军，那么当将军总数小于或等于 3m 时（n <= 3m，m代表叛徒将军个数)，叛徒便无法被发现，整个系统的一致性也就无法达成。

叛徒是否可被抓？

从上面的结论，可以看出，忠诚将军的人数是叛徒人数 2 倍的时候，依然不能找出叛徒，那么再多一个忠诚的将军呢？

为了简化问题，接下来假设有 4 个拜占庭将军，分别是 A、B、C、D，其中有一个是叛徒。我们依然秉承找出叛徒的关键，即判断哪个将军发送了不一致的消息。

也就是说，接下来就是和其他接收到消息的将军进行信息的同步判断：是否收到的消息不一致。

现在，将问题再进一步简化，暂不需要考虑整个投票的过程，只需要考虑一个将军向其他三个将军各发送了一条命令，忠诚将军能否对这个命令达成一致的情况，

为了区分发送命令的将将军和接收消息的将军，我们将发送命令的将军称为发令将军（M），将接收命令的将军称为副官（S）。

考虑下面两个问题：

• 那么剩下的三个副官能不能通过相互间的信息同步找到叛徒？
• 或者所有忠臣间达成一致，不让叛徒的分裂想法得逞呢？

这时候就出现了两种情况：

• 发令将军是叛徒 ；
• 副官里有叛徒。

Case 1：发令将军是叛徒

假设 D 是叛徒，向 A 和 B 发送了进攻，向 C 发送了撤退。

现在切入到 A 的视角，A 问 B 和 C：“我从 D 那里收到的消息是进攻，你从D那里收到的是什么呢？”

B 说是进攻，C 说是撤退。

此时，从 A 的视角来看，C 和 D 对同一条消息的说法是不一致的，那么他们两个人中肯定有一个是叛徒，但是 A 无法判断的是：

• D给不同人发送了不一致的消息；
• 还是C伪造了D的消息。

好在，由于 A 知道最多只有一个叛徒存在，根据反证法，如果 B 也是叛徒，就有两个叛徒存在，那么 B 肯定不是叛徒。

那么 A 和 B 至少在 D 发送的是进攻这一消息上，达成了一致，两者选择都是进攻。

B 也是同样的情况，现在 A 和 B 彼此建立了信任，而同样是忠诚副官的 C，最终则和真正的叛徒 D 被一同怀疑。

Case2：副官里有叛徒

假设 C 是叛徒，D 给三个副官都发送了进攻，那么叛徒 C 应该怎样同步 D 的消息，才能分裂忠诚的发令将军和忠诚副官间的关系呢？

如果将 D 的消息原样转发出去，那么这一想法实施后也就无法再去当叛徒了。如果给 A 与 B 均发送和 D 相反的撤退消息，那么就回到了上文所讲的第一种情况，A 和 B 认为 D 发送的是进攻，发送消息的 D 也认为自己发送的消息是进攻，忠臣们行动上又一次达成了一致。

然而，为了给系统增加更多的混乱，叛徒 C 决定再次发送不一致的消息，告诉 B 自己从 D 收到的是进攻，告诉 A 自己从 D 收到的是撤退。

这种情况下，B 看到所有人都认为 D 是进攻，会傻傻地认为大家是个团结一致的集体，没有叛徒。

而 A 会发现 C 和 D 中出现了一个叛徒，不过 A 也再次可以确认 B 是自己人。此时，A 决定再和 B 同步一轮消息，看看 C 是不是说了两个不一致的消息，这种情况下，叛徒C就完全暴露了。

由此可见，在多了一个忠臣的情况下，叛徒需要处处小心，才能避免被发现。与此同时，忠臣们即便在存在混乱信息的情况下，行动上也依旧达成了一致。

根据推理，我们可以推导出一个结论：当忠臣的个数为 2m + 1 时，他们可以容忍 m 个叛徒产生的破坏。

至此，拜占庭将军问题的已经解释清楚了。

你应该已经知道了 m 个可以任意伪造消息的叛徒能够破坏规模最大为 3m 个将军的一致性。你也已经了解了叛徒是如何通过发送不一致的消息来制造混乱，以及忠诚将军又如何通过交换信息在混乱中保持一致的。

那么接下来让我们跳出拜占庭将军的比喻回到计算机的世界中，如果三个节点中有一个异常节点，那么最坏情况下两个正常节点之间是无法保证一致性的。

用算法解决难题——区块链的雏形

构造出一个完美的、可以解决问题的“拜占庭容错系统”是一个不小的挑战，而且构造出来以后，其是否真的有效，能否经得起时间的考验与各方的质疑，这些都关乎着这个系统未来的命运与其创造群体的声誉。

2008 年冬季，美国 MIT（麻省理工学院）的密码学及密码学政策战略的邮件讨论组中，一位澳大利亚的企业家 James A Donald就对一位声称构造出了一个点对点的、不需要第三方权威认证的 e-cash (电子现金)支付系统提出了质疑。而他的理由就是：对方设计的 P2P 系统不能够解决“拜占庭将军问题”。

在邮件中他挑剔地说道:

 “我们的确真的非常非常需要这个系统，但我所担忧的并不是信任的问题，而是如何获取一个全局共享的图景，借由此点而获取一致性的问题。每个人都知道 X，这并不足够。

我们需要让每个人都知道‘每个人都知道 X’。而每个人都知道‘每个人都知道X ’就是‘拜占庭将军问题’中，分布式的数据处理最难解决的问题。尤其是当X是非常庞大的数据时……”

言下之意，他并不清楚或不确信这个去中心化的系统，如何解决拜占庭将军的难题。

仅仅在一天之后，他就收到了原作者的回复，一封简洁、优雅的邮件解释了在这个系统中，破解“拜占庭将军问题”的算法。

在数学和计算机科学之中，算法为一个计算的具体步骤，常用于计算、数据处理和自动推理。

“工作量证明链”（ proof-of-work chain）正是我解决“拜占庭将军问题”的方案。

一群拜占庭将军，人手一台电脑想用字符串模式匹配的方法，暴力破解国王的 WiFi 密码，当然他们已经事先获取了组成密码的字符串的长度。

一旦他们开始模拟网络发送数据包，他们必须在一个限定的时间内完成破解工作，并清除服务器和电脑上的记录，否则他们就会被发现，那就麻烦了。

只有当绝大多数将军在同一时间发起攻击和破解，这样才能有足够的CPU(中央处理器)和计算能力在短时间内完成破解工作。

他们并不特别在乎什么时候开始攻击，只要他们全部同意就好。

一开始的时候，大家决定这样搞：任何人觉得时机到了都可以宣布一个攻击时刻。而且，不论是什么时候，只要是第一个被听到的攻击时刻，就将被确定为官方的攻击时刻。

这样的话问题又来了，因为网络传达有延迟和干扰，如果有两个将军差不多同一时间公布了两个不同的攻击时刻，那么有的人会最先听到其中一个将军发布的攻击时刻，而又有些人则会最先听到另外一个将军发布的攻击时刻。

他们使用一个“工作量证明链”来解决这个问题。

当每个将军接收到任何表达形式的第一个攻击时刻时，他都会设置他的计算机来求解一个极其困难的“工作量证明”问题，对这个问题的解答是一个哈希（Hash）散列，里面也将包含着这次的攻击时刻。

由于这个“工作量证明”问题，非常难解，一般而言，就算所有人收到这个问题后同时求解，也至少需要10分钟才能产生解答。

一旦一个将军解出了“工作量证明”，他将会把这个算出来的“工作量证明”向整个网络进行传播，每一个接收到的人，将在他们当前正在做的“工作量证明”计算的散列中附加上刚刚被求解出来的那个工作量证明。

如果任何人正在计算他收到的其他的一个不同的攻击时刻，他们将会转向新的更新后的“工作量证明”计算当中，因为他现在的“工作量证明链”更长了。

两个小时后，将有一个攻击时刻被散列在一个有 12 个“工作量证明”的链中。每个将军只要通过验证（这条工作链的）计算难度，就能估算出平均每小时有多少 CPU 算力耗费在这上面，也就会知道：

这一定是在分配的时间段内，绝大多数将军的计算机共同协作才能生成的结果。

如果“工作量证明链”中展示出来的算力足够强大，可以破解国王的 WiFi 密码，那么他们就可以在一致同意的时间内安全地展开攻击。

同步、分布式数据库和一个一致的、全局性的视野的问题如何解决？“工作量证明链”就是答案。

“拜占庭容错”方案如何实现？

在模块化的区块链底层框架（KET）中，我们使用公私钥加密和路由策略的机制实现拜占庭容错，这个是怎么实现的呢？

EKT 主链上每个公式机制节点的公钥都是公开的，具体路由策略为：

1. 区块广播

当一个节点完成打包之后，会对区块进行签名。签名完以后节点会把区块和签名广播给网络中的其他节点。

当另外一个节点收到区块和签名之后会对签名信息进行校验，以此来确认这个区块是从打包节点广播出去的。

其他节点确认完成后，会判断自己节点与打包节点在当前轮的距离，如果满足条件 (currentIndex – miningIndex + len(DPoSNodes)) % len(DPoSNodes) <len(DPoSNodes) / 2，则将自己收到的区块和签名继续广播给其他节点。

当一个节点收到两个不同的打包节点的区块和签名之后，会将两个不同的区块和签名发送给所有其他节点。而所有节点则放弃当前区块，进入下一个区块的打包并对当前打包节点的作恶行为进行记录。

2. 区块的校验与投票

在每个区块头上，都会有区块 body 的 Hash 校验值。

节点可以向其他节点获取区块 body，对 body 进行处理之后，对当前打包的区块进行投票，所有节点都会把区块的校验结果进行签名，发送给满足 (currentIndex – miningIndex + len(DPoSNodes)) % len(DPoSNodes) <len(DPoSNodes) / 2条件的节点进行唱票。

当任何一个节点收到超过半数对同一个区块的投票之后即可认为当前的区块可写入区块链中，并将区块和投票结果发送给所有的节点，所有节点对区块进行记录。

如果投票的数量不足半数则在一定时间内停止唱票，节点将自己的唱票结果发送给其他节点，所有节点在收到其他节点的投票结果之后对结果进行合并，判断最后的投票结果并执行响应的操作。

3. 节点宕机

当一个节点超过一定时间没有出块，当前轮的下一个节点会在 3*interval/2 的时间点开始打包下一个区块，进入下一个区块的打包流程。

同理，如果节点连续宕机，判断当前节点是否需要打包的条件是 currentTime – lastBlockTime > (2*(currentIndex -LastIndex)+1)*interval/2，一旦满足当前条件，则当前节点开始打包。

如果是最后 n 个区块连续宕机，则按照当前轮的最后一个区块的 hash 值判断下一轮的顺序，按照递增每个区块加一个出块 interval 的算法进行计算，判断当前打包的节点并进行打包。

当超过 n/2 的节点宕机的时候，所有节点会自动停止出块，直到超过 1/2 的节点存活。

这种方案的复杂度在最好情况下是：消息复杂度O(n^2), 时间复杂度O(1)。

在最差情况也可以达到：消息复杂度O(n^2), 时间复杂度O(n)。

基于这种路由策略的拜占庭容错机制，系统可以保证在少于n/2的节点宕机或者叛变的情况下，系统不会出现分叉，是一种用计算资源换容错性的方案。

“拜占庭问题”的影响

尽管拜占庭的“幽灵”很恐怖，但在我们实际工作中，却并不需要过分去考虑它。

因为对于大多数系统来说，内部环境里，硬件故障导致消息错误的概率本身就很低，还要按照拜占庭叛徒的策略来处理故障就更困难了。

对于黑客来说，最主要的目的是攻克系统拿到数据，而不是读懂系统间交互的协议，而自己实现一套交互把自己作为一个叛徒来的事情给系统制造混乱，这对他们来说成本太高且受益太低。