科普 | 区块链技术六大核心算法之拜占庭协定

在加密货币经历“混乱时期”后，区块链再次火爆起来，受到了各方的极大关注与重视，成为资本市场和各领域关注的焦点，就连朋友圈中的探讨和分享也让人目不暇接。

区块链核心算法一：拜占庭协定

超级账本PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。该论文发表在1999年的操作系统设计与实现国际会议上（OSDI99）。没错，这个Loskov就是提出著名的里氏替换原则（LSP）的人，2008年图灵奖得主。

拜占庭的故事大概是这么说的：拜占庭帝国拥有巨大的财富，周围10个邻邦垂诞已久，但拜占庭高墙耸立，固若金汤，没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败，同时也有可能自身被其他9个邻邦入侵。拜占庭帝国防御能力如此之强，至少要有十个邻邦中的一半以上同时进攻，才有可能攻破。然而，如果其中的一个或者几个邻邦本身答应好一起进攻，但实际过程出现背叛，那么入侵者可能都会被歼灭。于是每一方都小心行事，不敢轻易相信邻国。这就是拜占庭将军问题。

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

“拜占庭将军问题”模型中，对于将军们（节点）有两个默认的假设： 

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

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

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

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

在这个分布式网络里：每个将军都有一份实时与其他将军同步的消息账本。账本里有每个将军的签名都是可以验证身份的。如果有哪些消息不一致，可以知道消息不一致的是哪些将军。尽管有消息不一致的，只要超过半数同意进攻，少数服从多数，共识达成。

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

拜占庭帝国的几支军队攻打到了敌人的城市外面，然后分开驻扎。每一支军队由一位拜占庭将军(Byzantine general)率领。为了制定出一个统一的作战计划，每一位将军需要通过信差(messenger)与其它将军互通消息。但是，在拜占庭将军之间可能出现了叛徒(traitor)。这些叛徒将军的目的是阻挠其他忠诚的将军(loyal generals)达成一致的作战计划。为了这一目的，他们可能做任何事，比如串通起来，故意传出虚假消息，或者不传出任何消息。

我们考虑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个将军一起发起攻击，敌人被歼灭了。不管怎样，按照这种方式执行，结果是没问题的。

由此，在一个分布式的系统中，尽管有坏人，坏人可以做任意事情（不受protocol限制），比如不响应、发送错误信息、对不同节点发送不同决定、不同错误节点联合起来干坏事等等。但是，只要大多数人是好人，就完全有可能去中心化地实现共识。

内容由区块链安全公司WF曲速未来(WarpFuture.com)  编译，转载请注明来自WF曲速区。本文仅代表作者观点，不代表链得得官方立场。