看懂“拜占庭容错”,也就看懂了区块链的核心技术  cebnet.com.cn

2018-09-11 09:43:38 区块链Bobo

拜占庭将军问题:拜占庭的n个将军围攻一个敌人,n个将军包围着这个敌人,所以他们是在不同的地方。忠诚的将军希望通过某种协议达成某个命令的一致(比如约定某个时间一起进攻)。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。如果同时发起进攻的将军数量少于m个,那么不足以歼灭敌人反而容易被敌人全部歼灭。怎样做才能保证有多于m个将军在同一时间一起发起进攻?

  “拜占庭将军问题”模型中,对于将军们(节点)有两个默认的假设:

  所有忠诚的将军收到相同的命令后,执行这条命令得到的结果一定是相同的;

  如果命令是正确的,那么所有忠诚的将军必须执行这条命令。

  假设1的含义是:所有节点对命令的解析和执行是一样的,这个命令必须是一个确定性的命令,不能存在随机性,也不能依赖节点自身的状态。(这个命令不能是心情好就攻击敌人,心情不好就原地休息。)

  假设2的含义是:忠诚的将军需要判断接收到的命令是不是正确的。这个判断命令的方法是整个拜占庭容错技术的核心。

  对于将军们的通信过程,在“拜占庭将军问题”中也是有默认假设的:点对点通信是没问题的。也就是说,在这里,我们假设A将军要给B将军一条命令X,那么派出去的传令兵一定会准确的把命令X传递给B将军。

  有了上述假设,我们来看看将军们面临的核心问题是什么。

  我们考虑4个将军的情况,同时假设4个将军中最多只有1个背叛者。当4个将军A、B、C、D把敌人包围了之后,必须协商一个统一的时间去发起进攻。这时,A将军派出了3个传令兵,分别告诉B、C、D将军,下午1点准时发起进攻。到了下午1点,A、C、D三个将军发起了进攻,歼灭了敌人,同时他们三个发现B是背叛的。虽然B背叛了,但是对最终任务没有影响。

  但如果A是背叛的,会发生什么情况?A派出3个传令兵,分别告诉B、C、D将军在下午1点、2点、3点发起进攻。于是,到了下午1点,B将军去攻击敌人,由于寡不敌众,全军覆没;2点,C将军全军覆没;3点,D将军全军覆没。

  因为对于忠诚的将军来说,他不知道谁是背叛者,所以,他不能完全相信接收到的命令,他必须对命令做出判断。在1999年,著名的PBFT算法出现了。这个算法说起来也不难理解,他的核心思想是:对于每一个收到命令的将军,都要去询问其他人,他们收到的命令是什么。

  回到刚才的第二种情况(A是背叛者),A派出3个传令兵,分别告诉B、C、D将军在下午1点、2点、3点发起进攻。B将军派出传令兵去告诉C和D两位将军,B收到的命令是下午1点进攻。C也同样派出了传令兵分别告诉B和D两位将军,C收到的命令是下午2点进攻。D也同样告诉B和C两位将军,D收到的命令是下午3点进攻。于是,B得到了3条指令:A命令B下午1点进攻,A命令C下午2点进攻,A命令D下午3点进攻。B很容易判断出来,A是背叛者(因为B知道最多只有一个背叛者)。C和D也能做出同样的判断。因此这次进攻时间的协商是无效的。

阅读原文
标签:将军 命令 进攻 下午 敌人 收到