区块链研习 | 看懂“拜占庭容错”，也就看懂了区块链的核心技术

2017 年 9 月 14 日 AI金融评论 敖萌

雷锋网AI金融评论按：“区块链研习”是雷锋网推出的区块链技术研习系列，本系列将收罗学界与业界大咖技术研究与应用实践中的真知灼见，以飨读者。本文作者为中国信息通信研究院（工信部电信研究院）专家敖萌博士，雷锋网独家特约文章，雷锋网与信通院联合首发。未来，敖萌博士原创的区块链系列文章还将继续刊出，雷锋网与信通院相关平台同步更新，敬请关注！

上一篇我们简单提到了拜占庭将军问题：拜占庭的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也能做出同样的判断。因此这次进攻时间的协商是无效的。

采用了这种办法以后，另一种情况又会怎样？当B是背叛者，A将军派出了3个传令兵，分别告诉B、C、D将军，下午1点准时发起进攻。B告诉C说B收到的命令是下午2点，B告诉D说收到的命令是下午2点，C和D分别告诉另外2个将军，A告诉他们的命令是下午1点。

于是，C、D收到的消息都是两个1点，一个2点。对于C、D而言，不需要判断是A和B谁是背叛者——他们只需要执行收到多的那个命令就可以了。

如果A是忠诚的，那么B是背叛的，这种情况下对于A来说，他知道自己是忠诚的，他发出的命令，至少有2个将军会执行，所以下午1点，A、C、D三个将军一起去进攻，有3个将军一起发起攻击，敌人被歼灭了。如果B是忠诚的，那么B会收到两个1点一个2点，B也会执行收到多的命令，于是B、C、D三个将军一起去进攻，有3个将军一起发起攻击，敌人被歼灭了。不管怎样，按照这种方式执行，结果是没问题的。

采用PBFT方法，本质上就是利用通信次数换取信用。每个命令的执行都需要节点间两两交互去核验消息，通信代价是非常高的。通常采用PBFT算法，节点间的通信复杂度是节点数的平方级的。

注意，上面所讨论的所有情况里，还有一个假设：所有传递的消息都是口头消息。意思就是，A告诉B下午1点进攻，B可能告诉C说“A命令我下午2点进攻”。如果采用了书写的消息，那么情况是不一样的。A派传令兵给B一张纸，A将军用自己独特的笔迹写的“下午1点进攻”，然后要求B把这张纸传给C，B在纸上用自己独特的笔迹签名表示同意，然后B传给C，C也签名表示同意，然后D也同意，最后签过所有名的纸再给每个人看一眼，就可以让所有节点一致了。这种采用书面签名消息的情况，对算法要求简单得多。但是，采用书面消息的前提是：每个将军都知道其他将军的笔迹是什么样的，并且无法模仿其他将军的笔迹。

在PBFT的基础上，又出现了很多变种算法，这些算法往往都带有一些额外的假设。例如：认为发起请求的客户端一定是忠诚的，由客户端去验证节点是否忠诚；认为绝大部分时候将军都是忠诚的，所以降低两两交互核验消息的次数；通过对节点进行分工，来提高整个系统的处理速度；等。这些变种算法由于增加了额外的假设，导致了整个系统的去中心化程度的降低（关于区块链系统去中心化程度的理解，可以参见本系列的第6篇文章）。

但是，对于不同类型的应用场景，有些假设是合理的，有些假设则是不合理的。例如，在类似比特币的代币转账系统中，不能认为客户端是忠诚的，因为客户端很可能会发起双花交易。因此，当企业希望使用区块链技术改进自己的业务或者开展新业务的时候，一定要选择适合自己业务的区块链技术和系统。