区块链学习笔记(二)【拜占庭将军问题】

笔者能力有限,如有谬误,请及时指出,十分感谢!


拜占庭将军问题实际上是一个共识问题,经典的问题描述我这里就不过多叙述了,映射到计算机上就是一群节点,在不知道是否存在恶意节点的情况下,如何保证正常节点的共识。要解决这个问题,需要满足两个特性,一致性和正确性,即所有正常节点的结果一致以及如果发送任务的节点正常,则其他正常节点必须与这个节点保持一致。在经典模式的情境下,有两种解决方案,口头协议和书面协议。(PS:以下两种方案都是在确保了通信正常的前提下讨论的,并没有考虑延时,不回应等问题,如果要讨论可以参考两军问题)
一、口头协议
经典问题的结论是,当所有节点数n和恶意节点m满足n>=3m+1时,问题有解。
当n=3,m=1时假设有ABC三个节点。
如果节点A是正常发送节点,节点C是恶意节点,当节点A同时给B、C发送1指令时,节点B由于不信任A,询问节点C节点A发送的命令是什么,可能得到节点C恶意的回复0,那么节点B无法判断A和C那个才是恶意节点,因此无法执行指令1或0,而选择静默,此时问题无解。
如果A是恶意节点,那么可能给BC发送的不同的命令1,0,同样不能达成共识。


当n=4,m=1时假设有ABCD四个节点。
如果节点A是正常发送节点,D是恶意节点,并且给BCD同时发送命令1,指令B收到A指令后同样怀疑,并询问节点CD节点A发送给他们的命令是什么,节点C是正常节点所以返回1,节点D是恶意节点,返回未知X,那么节点B综合ACD节点返回结果,会执行命令1,节点C同理,这样正常节点BC达成一致,并且都执行节点A的正常命令1。
如果节点A是恶意节点,那么首先不需要满足正确性,只需要满足一致性即可。假设节点A分别发送给BCD的命令是x,y,z,由于BCD都是正常节点,因此,他们都会如实广播自己收到的命令,他们三个节点都会是x,y,z三个命令,因此结果保持一致。


当n=7,m=2时,假设有ABCDEFG7个节点。
如果节点A是正常发送节点,FG是恶意节点,并且同时向其他节点发送命令1,节点B在不确定节点A是否为恶意节点的情况下,询问其他所有节点,并且询问每一个节点给其他节点的回复(这里是两层循环,需要特别注意)。B询问C节点提供给其他节点的命令是什么并进行统计,得到结果是1,1,x1,x2(x1,x2为恶意节点随意提供),加上C本身提供给B的1,因此,B认为C节点得到的A的命令是1。同理,去验证其他节点,会得到的结果是1,1,1,x,y(x,y为恶意节点捣乱得出的随机值),加上自身得到的命令1,所以,节点B会执行命令1。节点CDE同理。因此BCDE都会遵循节点A的命令并且达成一致。
如果节点AG是恶意节点。首先不需要满足正确性,只需要满足一致性即可。假设A给其他节点发送了x1,x2,x3,x4,x5,x6命令,那么根据上面的分析节点B会验证节点CDEFG收到的命令,得到结果CDEFG的命令分别是x2,x3,x4,x5以及Y,虽然不知道Y具体是什么,但是是一个固定的命令,再加上已经确定的x1,x2,x3,x4,x5一定是可以得到一个固定的命令,CDEF同理也会得到这个命令。因此,节点BCDEF保持了一致性。


从上面的具体例子中,我们可能发现,如果再多出现一个恶意节点,那么就会导致结果不确定增加,从而难以维持一致性,具体的数学归纳,等笔者在研究下再添加。
#################################################
数学归纳法证明留白
#################################################
二、书面协议
通过口头协议我们不能溯源,不能防止恶意节点说谎,因此,书面协议添加了签名来防止这种情况。
在口头协议中n=3,m=1的情况是没有解的,但是在书面协议中,如果节点A是正常的,他会发送给BC的命令是1:A,而BC发送给对方的命令分别是1:A:B和1:A:C,那么此时执行的命令一定是1,问题的关键在于恶意节点C无法修改A签名产生的命令1,只能添加自己的签名进行转发,此时满足一致性和正确性。如果A是恶意节点,那么可能分别发送1:A和0:A,那么BC获取的命令集合一定都是{1,0},此时通过choice(取集合中位数的函数)也可以获取一个确定的命令,此时满足一致性,问题得到解决。


【区块链学习笔记(二)【拜占庭将军问题】】同理,对于任意nm,只要发送节点正常,那么其他正常节点一定可以满足一致性和正确性。当发送节点是恶意节点时,由于签名的原因,所有正常节点收到的都是统一的命令集合,那么通过choice函数得到的结果也是一定的,一致性因此得到了保证。

    推荐阅读