EKT多链技术谈 | 人们常说的“拜占庭将军”问题究竟是啥？

何谓“拜占庭将军问题”？

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

拜占庭帝国想要进攻一个强大的敌国，为此帝国派出了10支军队去包围这个帝国。这个敌人虽然不如拜占庭帝国强大，但也足以抵御5支常规拜占庭军队的同时袭击。由于某些原因，这10支军队无法聚合在一起进行攻击，必须分散然后根据统一的指令一起进攻或者撤退。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。

军中可能有叛徒，可能向其他的将军发送错误的指令。在这种情况下如何保持战争指令的统一性进而获取胜利便成为了一个问题。

进一步讲，拜占庭将军的问题可以描述为：

一个发送命令的将军要发送一个命令给其余n-1个将军，使得所有忠诚的接收命令的将军遵守相同的命令如果发送命令的将军是忠诚的，那么所有忠诚的接收命令的将军遵守所接收的命令这个问题发展到计算机领域，就是拜占庭容错问题。区块链需要解决的一个核心问题就是如何保证在分布式环境下，各个节点（即使存在恶意节点）的数据能够达成最终的一致性和正确性。

EKT的共识算法是DPoS，在DPoS的共识基础上，我们也引入了基于路由策略进行拜占庭容错的方案。

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

在EKT中，我们使用公私钥加密和路由策略的机制实现拜占庭容错。这个是怎么实现的呢？

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

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的节点宕机或者叛变的情况下，系统不会出现分叉，是一种用计算资源换容错性的方案。