PBFT性能会下降？各种算法的对比。

PBFT协议在超过100个节点的时候性能会下降
作者&＃xff1a;maxdeath
链接&＃xff1a;https://www.zhihu.com/question/60058591/answer/173970031

首先要搞清为什么PBFT&＃xff0c;乃至所有的BFT都没法应用于超过100个节点。原因的关键在于O(N^2)的消息复杂度。这是什么意思呢&＃xff1f;点对点的消息传输需要发一个消息就够了&＃xff0c;这是O(1)的消息复杂度&＃xff0c;要是广播一个消息&＃xff0c;需要把消息发给网络里所有人一人一份&＃xff0c;就是O(N)的消息复杂度&＃xff0c;而想要可靠地&＃xff0c;在有拜占庭节点&＃xff08;恶意节点&＃xff09;存在的网络里广播一条消息的话&＃xff0c;至少需要O(N^2)的消息复杂度&＃xff0c;也就是说&＃xff0c;如果网络有100个节点&＃xff0c;如果你想让确认网络里的其他人都确实地收到你的消息&＃xff0c;你至少要发10000条消息。这性能一看就好不了。于是才有了比特币&＃xff0c;它把可靠的那部分用奖励&＃xff0c;挖矿和最长链解决了&＃xff0c;于是再大的网络也只是O(N)的消息复杂度&＃xff0c;这就scalable了。但是另一个问题就出现了——大网络里传输效率和延迟有瓶颈&＃xff0c;而这种瓶颈会制约可靠性。也就是说你广播的东西太大的话&＃xff0c;比特币的那套奖励&＃xff0c;挖矿和最长链的东西就不是那么好使了。于是&＃xff0c;目前所有的提高scalability的方法基本上就是结合两者&＃xff0c;也就是分层。无论是叫分层也好&＃xff0c;委员会选举也好&＃xff0c;差不多想法就是我们把某一部分的可靠性用比特币的方法解决&＃xff0c;剩下的部分用BFT。这其实和代议制民主很像——所有人一起讨论事情太难了&＃xff0c;那么我们让所有人选代表&＃xff0c;然后选出来几个代表讨论事情就高效多了。但接下来的问题是这两部分怎么对接&＃xff1f;两个方法对于恶意节点的数量要求不一样&＃xff08;BFT必须严格少于1/3&＃xff0c;比特币的话是算力小于1/4&＃xff09;&＃xff0c;要不要奖励&＃xff08;自私挖矿算不算恶意呢&＃xff1f;&＃xff09;&＃xff0c;共识类型不一样&＃xff08;BFT是最终共识&＃xff0c;比特币是最长链共识&＃xff0c;也就是允许分叉&＃xff09;&＃xff0c;是许可还是非许可。这些都是处理起来很让人头疼的问题&＃xff0c;基本上&＃xff0c;所有的分层算法都得要给出这些东西。而我目前为止还没有看到一个完全找不出漏洞的算法。就拿你说的sharding的那篇文章说吧。这个Elastico&＃xff0c;或者叫SCP&＃xff0c;我很惊讶这个竟然能发表&＃xff0c;他们对于无穷小量的处理太随意了。我不是说他们结果一定不对&＃xff0c;但是他们的证明是有问题的。他们分层非常的幼稚&＃xff0c;他的方法就是简单的随机选&＃xff0c;而随机选的时候&＃xff0c;他们就是简单的说如果我们的随机方法是公平的&＃xff0c;那么当这个小组的人数很大的时候&＃xff0c;这个小组恶意节点超过1/3的可能无穷小。

异步拜占庭容错&＃xff08;aBFT&＃xff09;&＃xff0c;以加快实现不可逆转性。 aBFT算法在1秒内提供100&＃xff05;的不可逆性确认。

POW
POW机制是依赖机器算力进行数学运算来获取记账权&＃xff0c;资源消耗相比其他共识机制高、可监管性弱&＃xff0c;同时每次达成共识需要全网共同参与运算&＃xff0c;性能效率比较低&＃xff0c;容错性方面允许全网50%节点出错。POW机制最早出现在比特币中&＃xff0c;这也是区块链里出现的较早的共识机制。
缺点&＃xff1a;
浪费能源&＃xff1b;
区块的确认时间难以缩短&＃xff1b;
新的区块链必须找到一种不同的散列算法&＃xff0c;否则就会面临算力攻击&＃xff1b;
容易产生分叉&＃xff0c;需要等待多个确认&＃xff1b;
永远没有最终性&＃xff0c;需要检查点机制来弥补最终性&＃xff1b;

POS( Proof of Stake&＃xff09;权益证明

DPOS&＃xff08;Delegated Proof of Stake&＃xff09;股份授权证明机制
DPOS与POS原理相同&＃xff0c;只是选了一些“人大代表”。BTS社区最先提出了DPOS机制。最近较热的EOS也是采用了DPOS机制。
核心思想&＃xff1a;百分之五十一的矿工具有不可逆转的权利。
优点&＃xff1a;该模式可以每30秒产生一个新区块&＃xff0c;并且在正常的网络条件下区块链分叉的可能性极其小&＃xff0c;即使发生也可以在几分钟内得到解决。
缺点&＃xff1a;整个共识机制还是依赖于token&＃xff0c;很多商业应用是不需要token存在的。

POOL验证池
一句话介绍&＃xff1a;基于传统的分布式一致性技术&＃xff0c;加上数据验证机制。
优点&＃xff1a;
不需要token也可以工作&＃xff0c;在成熟的分布式一致性算法&＃xff08;Pasox、Raft&＃xff09;基础上&＃xff0c;实现秒级共识验证。
缺点&＃xff1a;
去中心化程度不如Bitcoin&＃xff1b;
更适合多方参与的多中心商业模式。

一致性算法&＃xff08;BFT-DPOS&＃xff09;
EOS.IO软件能够精确的每0.5秒生成一个块&＃xff0c;并且只有一个生产者有权在任何给定的时间点生成一个块。如果在预定时间没有生成块&＃xff0c;则跳过该时间段的块。当跳过一个或多个块时&＃xff0c;区块链中会出现0.5秒或更多秒的间隔。