锐客网

  1. 首页 > it技术 > >

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

区块链

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


拜占庭将军问题实际上是一个共识问题，经典的问题描述我这里就不过多叙述了，映射到计算机上就是一群节点，在不知道是否存在恶意节点的情况下，如何保证正常节点的共识。要解决这个问题，需要满足两个特性，一致性和正确性，即所有正常节点的结果一致以及如果发送任务的节点正常，则其他正常节点必须与这个节点保持一致。在经典模式的情境下，有两种解决方案，口头协议和书面协议。（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函数得到的结果也是一定的，一致性因此得到了保证。

    推荐阅读


    上一篇：Blob分析（）

    下一篇：分布式服务框架之服务化最佳实践