区块链基础：拜占庭问题

区块链技术中很重要的一个部分就是共识机制，在了解共识机制的过程中，拜占庭将军问题就会时常看到，拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利（来自百度百科）。

这里不讨论军事问题，把拜占庭将军问题引入到计算机领域，在分布式系统中，网络中各节点由于硬件设备故障、网络延时或故障、恶意攻击导致整个系统中出现不可预知的错误。把拜占庭将军问题嵌入到分布式系统中说明：

前提：1.网络中各节点信道可靠。2.网络中节点数可知为n。

分布式网络中的众多节点，同时更新或者删除数据，必须达到共识的状态，但是有些节点会出现不确定故障或者恶意篡改，导致分布式节点数据不一致，这个问题现实中是不可避免的。那么要求系统能正常运行，这里引入一个容错的概念，可以在不完全一致的状态下，系统仍然可以正常运行。所谓的正常运行有两种概念，1.数据的正常更新后提供服务。2.由于故障节点过多数据不更新提供服务，再发起一次共识。

如何来定义这个正常运行，这个需要有一个取舍，因为结合实际应用很多因素需要考虑，理论的严谨和工程的取舍这个一般都会有权衡。下面说明通过容错达成的正常运行。

设置一个变量x，节点数为n,假设其中一个节点为i。通过各种条件设置应用场景：

1.节点i发布请求x，诚实节点收到的是（x1、x2…xi…xn）集合，这些集合内x值一致，那么从i的诚实性考虑，有可能i是诚实节点、也有可能i本身就还是恶意节点。

2.i节点是诚实节点，那么其他诚实节点也同样发送x值。

3.结合1.2，我们不管i节点的诚实性，所有诚实节点都收到一样的x值集合。

这样网络中节点收到的请求更新一致，如果i是诚实节点，那么保证了正常运行。这种情况将1.2结合系统达到了一致性和正常运行的两个要求。

但是这是理想化的状态在现实网络节点中刚才的假设都是理想化的。通过执行流程来看下：

再假设三个前提：1.x发送都可正确传达到其余节点中。2.接收节点知道发送节点。3.节点知道x消息完整。

那么网络中n个节点，恶意节点为m个，那么n>3m+1。

1.i发送x给每一个节点，每个节点收到x则更新、未收到默认就为不操作。

2.每个节点收到i发送x更新后，恶意节点m发送y其余节点，发送是一个递归过程。

3.每个节点收集i发送x信息，恶意节点m接收x值，不发送至其余剩余节点。

下面通过图形说明：

这里n=3，m=1，那么节点i和节点B是诚实节点，但是B节点不知道应该是x还是y是更新。再引入一个节点：

这种情况下i、b、c节点是诚实节点，x值在b、c集合中出现2次，y出现一次，故达到了共识。这个前提是i是诚实节点，如果i本身就不是诚实节点，i发送不同三个值，那整个系统无法共识。

n >3m+1 m=2 n=7

这个过程就会比较复杂了，假设a和d是恶意节点，那么每个诚实节点通过递归方式去接受其余节点的信息，然后收集的到信息集合中通过多数原则来确定。

b 、c、e、f为诚实节点加上i，系统达成共识。当然i如果是恶意节点，发送不同消息给下面节点，那么共识将无法成立，但是如果i发送是有一半是x值一半是不同值，可以推理下。以上推理过程在拜占庭将军问题中称为口头协议。追溯我们之前写的三个假设中，如果接收者知道发送者，那么就有书面协议。下面对书面协议再作说明：

所谓书面协议，就是网络节点在传输过程中添加一个签名，任何节点可以验证签名可靠性。

还是用节点收到的数据集合v，i节点发送x值给各个节点，节点收到v（x），然后发送v（x）：i给其余节点，如果收到的一串值中没有v（x），那么就把这个值添加到自己的v集合中。每个节点收到值后，通过choice函数判断。在口头协议中三个节点当i节点发送不同值的时候无法一致，那么这里加上签名后可以看下，以图说明：

这种情况下最后a、b节点接收信息后都是x、y那么在系统中两个节点信息一致。这就解决了3节点口头协议不能完成一致的问题。如果n=4，m=2有兴趣可以再推理一次，结果也是一致的。

综上所述，在拜占庭问题中n>3m+1能得到保证，拜占庭将军问题比较考验整个推理，笔者也是根据自己理解写了点介绍，有不对的请及时指正。