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

VK前几天在个人网站上介绍了一个99%容错共识算法:https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html。本文介绍V神的文章以及对99%容错共识算法的理解。

1)共识算法的思考

文章开头描述了目前共识算法的总结,分为两类:同步共识算法和异步共识算法。同步共识算法(比如POW)存在一种同步机制,在一定的时间范围内收集共识消息。同步共识相对来说简单,只要有超过50%的诚实节点,在足够长的时间范围内,肯定能达成共识(也就是大多数的诚实节点,记账一致)。同步共识节点确定也比较明显,时间长,分叉概率大。异步共识算法(比如PBFT,Casper FFG等等),不需要明确的时间同步,只要在收集到超过2/3以上的共识确认消息,就能完成共识。异步共识算法,共识速度快,且不存在分叉,但异步共识算法只能容忍不超过1/3的坏节点。

VK在这两种算法的基础上(异步共识算法的容错率是1/3,增加同步条件,同步共识算法的容错率达到50%)提出疑问,能否增加其他更多限制(如果节点不参与共识,但是能全程观察整个共识过程),获取更大的容错率,甚至达到99%的容错率呢?VK给出的答案:YES。

2)BFT算法中的签名消息算法

VK接着介绍,他的思路来自,1982年的BFT算法的论文:https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf。这篇论文讲述的是拜占庭将军问题,如何保证诚实的将军得到统一的命令(即使指挥官不诚实的情况下)。BFT的论文主要讲述了三部分的内容:1)如果将军之间只能通过口头消息的情况下,如何保证诚实将军统一作战(进攻,或者后退) 2)如果将军之间能通过签名的消息沟通的情况下,如何保证诚实将军统一作战 3)将军和将军之间的路径有何要求?有关BFT算法的论文,会在以后的文章详细介绍。

VK利用的是其中的第2部分的算法。BFT算法论文中有关签名消息的算法如下:

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

因为是使用签名的消息,非诚实的将军的作恶手段非常少(最多就是不广播或者延迟广播命令)。如果使用“口头”消息,非诚实的将军,可能对不同的将军传达不同的命令,其他将军也无法识别。而使用签名消息,这种方式很容易被诚实节点识别出,不同的命令来自统一签名的将军,从而忽略该将军的所有命令。简而言之,SM算法保证了无论诚实将军的个数,诚实将军数据一致,并且因为数据都是可靠数据,诚实将军可以推算出正确的命令。

3)VK的容错算法

在BFT的签名消息算法的基础上,VK提出了一个简化算法。假设条件有两个:

1)N个节点,并且节点间网络传输的时延(包括时钟的偏移)为D

2)假设节点中最少有一个诚实节点

简化算法如下:

假设节点i接收到消息v : i[1] : ... : i[k](消息v被k个节点签名)

1)如果接收该消息在T + k * D之前(T是整个算法开始的时间点)

2)如果节点i还不知道消息v的话,对该消息签名,v : i[1] : ... : i[k] : i,并发送给其他节点

在T + (N-1) * D时间后,也就是广播最多N-1次后,各个节点不再接收消息,使用Choice函数,对接收到的若干消息处理,获取最终的消息。

很容易看出,VK的容错算法对BFT的SM算法增加了两个假设条件:1)节点间消息传输的时延 2)最少有1个诚实节点(经过N-1次的广播,诚实节点间的数据肯定一致)。

VK给出了简化算法的示意图:

节点从左到右,编号为0,1,2,其中节点1为粉红色,坏节点。开始时,节点0发送y:0给节点1,2,节点2发送x:2给节点0,1。坏节点1,并不及时发送消息,在T+D时间快到的时候,发送w:1给节点0。在T+D的时间,节点0获得消息,但是节点2获得消息为。节点0,节点2,两个诚实节点在T+D的时间并不一致,没关系。在T+D的时候,节点0会广播x:2:0以及w:1:0给节点1,节点2,也就是说在T+2D的时间,节点0,节点2,消息一致,都是。

VK同时给出了简化算法的证明,保证诚实节点接收到的消息一致。

假设诚实节点x在时间T + k * D之前接收到消息v : i[1] : ... : i[k],则需要证明其他诚实也会获得消息v。证明分两种情况讨论:

1)如果x在i[1] : ... : i[k],假设x = i[j]的话,则说明节点x在T + (j-1) * D时间前接收到了消息v,并且接着广播出去。也就是说,其他诚实节点在T + j * D时间前都应该接收到消息v。

2)如果x不在i[1] : ... : i[k],节点x需要对该消息签名,广播i[1] : ... : i[k]:x。也就是说其他诚实节点在T + (k+1) * D时间前都应该接收到消息v。

4)引入Observer(观察者)

Observer是整个99%容错共识算法中的重要角色。Observer是能连接到共识节点的,相互之间可能不连接的节点。你可以理解成Observer是需要访问共识账本,提供服务的节点,但是,Observer本身并不参与共识。

引入Observer后,如果Observer能全程观察共识过程,并且和诚实节点数据一致的话,Observer就能“帮助”诚实节点行程共识。在足够多的Observer的帮助下,即使参与共识的诚实节点只有一个,也能在Observer和共识节点形成共识。

VK在原有的简化算法上发现一个问题:如果只有一个诚实节点的情况下,Observer和诚实节点的数据可能不一致。

“Colluding nodes”代表坏节点的集合,其中有k个节点。因为只有一个诚实节点,也就是总共是k+1个节点。在最后快到T+k*D的时候,作恶节点可能发送消息v给Observer1。在T+k*D时间后,Observer2和诚实节点接收到消息v,但是被忽略。从而,Observer1和其他Observer2以及诚实节点的数据不一致。

为了解决该边际情况,VK调整了一下算法:

将原来算法假设的网络延迟时间D扩大为原来的两倍,并且,Observer只有在T+(k-0.5)*D之前接收到的消息才有效。这样的话,Observer在接收到消息后,有足够的时间0.5D广播给诚实节点,再由诚实节点广播消息给其他节点或者Observer。示意图如下:

总而言之,诚实节点和Observer之间的数据保持一致,并且这些数据可靠,能推算出正确的结果。

至此,可以看出99%的共识算法的整体思想了,在Observer的帮助下,而且,Observer的数量肯定远大于共识节点的个数。只要在参与该共识算法的节点中有一个诚实节点,该共识算法就有效。这样的话,如果参与共识算法的节点够多的情况,共识算法的容错率可以无限接近100%。

5)其他

VK最后认为,该共识算法独立就能稍稍改成POS或者POW算法。也可以将该共识算法和其他算法结合。其他算法(PBFT, Casper FFG, chain-based PoS等等),给予了一个新的分类:阀值依赖类型。这些算法的观察者不需要实时全程在线,只需要偶尔和共识节点同步。而VK提出的共识算法,需要观察者实时观察整个共识过程,给予了另外一个分类:延迟依赖类型。

在其他共识算法的基础上,每隔一段时间,可以使用该算法进行同步。

6)算法的缺点

个人理解,VK提出的容错99%的共识算法,确实是个脑洞大开的想法。但是,该共识算法需要极强的同步性,并且算法极其耗时。举个例子,如果512个节点参与共识,网络延时是8秒的话,共识需要(512-1)*8 = 4088秒,1.13小时。

总结:VK在1982年的BFT论文的签名消息算法的基础上提出了简化算法,保证诚实节点数据可靠且一致。在Observer全程实时参与共识的情况下,只要共识节点中超过一个诚实节点,Observer和共识节点就能形成共识。如果参与共识算法的节点够多的情况,共识算法的容错率可以达到99%,甚至无限接近100%。但是,该共识算法需要极强的同步性,而且在共识节点多的情况下,耗时非常长。

题外:VK最近还在更新这篇文章,每次更新都尽量更准确表达他的想法。

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

扫码关注云+社区

领取腾讯云代金券