区块链基础:拜占庭问题

区块链基础:拜占庭问题

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

222.jpg-24.6kB

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

前提: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值集合。
233.png-33.2kB

这样网络中节点收到的请求更新一致,如果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值,不发送至其余剩余节点。

下面通过图形说明:
244.png-24.2kB

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

255.jpg-22.3kB

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

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

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

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

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

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

277.jpg-15.1kB

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

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

---本文结束感谢您的阅读---
北岸冷若冰霜 wechat
欢迎使用微信扫一扫上面的二维码,订阅我的公众号!
坚持原创分享,点击下方打赏,您的支持将鼓励我继续创作!