区块链-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个非诚实将军,拜占庭将军问题都能解决。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180820G1X2DH00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券