区块链-BFT算法介绍

BFT（拜占庭容错）算法由Leslie Lamport和另外两位作者在1982年的论文中提出。Leslie Lamport（莱斯利·兰伯特），2013年图灵奖获得者，美国计算机协会(ACM)院士。Lamport还是Latex的设计和开发者。

BFT的论文下载地址：

http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf。

本文详细介绍论文中设计BFT算法。

1）拜占庭将军问题

复杂的系统由多个计算机系统组成，BFT算法解决的问题是在一些计算机系统出错的情况下，如何保证系统的正确性和一致性。形象的例子，围在敌城外的一些拜占庭将军，在有些叛徒的情况下，诚实的拜占庭将军如何正确并且一致的执行指挥官的命令。这也是BFT（拜占庭容错）算法的由来。

论文首先定义了拜占庭将军问题：一个指挥官发送一个命令给n-1个将军，保证：IC1）所有诚实的将军遵守统一的命令 IC2）如果指挥官是诚实的，所有的诚实的将军必须准守指挥官的命令。论文接着指出如果将军之间通过口述消息，只有超过2/3的将军是诚实将军，拜占庭将军问题才能解决。论文给出了两个极限例子：总共三个拜占庭将军，其中一个是Commander（指挥官），拜占庭将军之能有两个选择：attack（进攻）或者retreat（撤退）。下图中显示了，只有2/3个诚实将军，无法解决拜占庭将军问题。

上图中，将军2是不诚实，发送“撤退”消息给将军1，虽然指挥官给他发送的是“进攻”消息。下图中，指挥官是不诚实，分别给将军1以及将军2发送“进攻”和“撤退”消息。在这两种情况下，将军1都接收到两个消息：一个是进攻，一个是撤退。将军1无法区分是将军2或者指挥官不诚实，按照IC2，将军1选择从指挥官发送的消息“进攻”。同理，将军2选择“撤退”。也就是将军1和将军2的结果不一致，不符合IC1条件。也就是说，在3个将军的情况下，如果其中一个将军不诚实，其他将军不能判别谁不诚实。

论文中接着论证了两个算法：1）如果拜占庭将军之间通过口述消息通讯 2）如果拜占庭将军之间通过签名消息通讯。

2）基于口述消息（Oral Message）的BFT算法

论文给出了口述消息的定义（满足三个条件）：

A1. 消息可以准确发送到指定的接收方 A2.消息接收者知道消息的发送方 A3. 可以检测消息的缺失。

基于上面的条件假设，不诚实的聪明的将军可以有如下的攻击手段（不被发现）：1）向不同的将军发送不同的消息 2）延迟消息发送。

论文提出了OM的算法：

OM(m)的算法是个递归算法，其中的m指不诚实将军的个数，如下图所示：

很明显看出，OM(m)中有n-1个OM(m-1)，对于每个OM(m-1)又有n-2个OM(m-2)。整个OM(m)的算法复杂度是O(n^m）。

举个例子，如下图，四个拜占庭将军，其中Commander是诚实的，将军3是非诚实的。

第1步，Commander发送命令v给其他三个将军。第2步，三个将军广播消息给其他两个将军（上图中只画出了将军2收到的消息），将军3非诚实，发送x给将军2。第3步，将军2收到的消息为，使用v作为命令（多数消息是v）。

论文用推演法证明了结论：超过3m的将军中，最多有m个不诚实的将军的情况下，OM(m）算法满足IC1和IC2条件。也就是说，使用OM(m)算法的容错是1/3。

3）基于签名消息（Signed Message）的BFT算法

签名消息的定义，在口述消息的定义上增加了一个条件：

诚实将军的签名无法修改，任何篡改都会发现，并且任何人可以验证签名。

论文提出了SM（Signed Message）的算法：

SM算法是针对将军间能通过签名消息沟通情况下，解决拜占庭将军问题的算法名称。v:0表示命令为v，有编号为0的将军（command）签名。v:i:j表示命令v，在i的签名的基础上，被编号j的将军接收到并且广播。这个算法的原理还是很简单的，保证每个命令v都能由最少一个诚实节点广播一次。具体看第2步骤，条件B的ii，在k

基于SM的算法假设，不诚实的聪明的将军只有如下的攻击手段（不被发现）：延迟消息发送。

举个例子，如下图：

上图中总共3个将军，Commander是不诚实的将军，分别发送“attack”和“retreat”给将军1和将军2。将军1和将军2从签名的消息发现从Commander发出了“矛盾”的命令，可以断定Commander不诚实，保持一致。SM(m）算法的复杂度是O(n*m)。

注意的是：SM(m)算法是VK提出99%容错算法的基础，详细请查看

区块链 - 99%容错共识算法理解

。

4）其他

论文还论述了OM或者SM算法中，如果将军之间通讯不是“全连接”，将军之间通讯需要满足的连接条件。感兴趣的小伙伴可以自行查阅论文。

总结：Leslie Lamport，2013年图灵奖获得者，在1982年提出了BFT算法，解决拜占庭将军问题。论文提出了两种假设下的算法：1）OM（口述消息沟通），非诚实将军可以发送不同命令给不同的将军，OM算法复杂度是O(n^m)。OM算法的容错率是1/3。2）SM（签名消息沟通），非诚实将军发送不同命令会被识别，算法复杂度是O(n*m)，同时SM(m)算法保证只要不超过m个非诚实将军，拜占庭将军问题都能解决。