区块链-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最近还在更新这篇文章，每次更新都尽量更准确表达他的想法。