EOS 高吞吐量的杀手锏 BFT-DPoS共识算法

投稿

EOS 高吞吐量的杀手锏 BFT-DPoS共识算法

佚名

2018-07-14 16:10:03

当Daniel Larimer在4月5日发布了EOSIO Dawn 3.0不久后EOS价格大幅度上涨多天。该预备版本的发布代表着目标在2018年6月发布正式版EOSIO 1.0的奋斗途中一个重要里程碑，并且EOS全球开发团队为使EOSIO成为构建区块链应用最强大的平台正日以继夜地工作着。笔者发现该版本中最引人瞩目的地方要数500毫秒出块间隔和BFT-DPoS的共识算法，这无疑是EOS为达到支持百万级别用户的区块链系统中最核心的技术突破，因此本文将详细分析BFT-DPoS共识算法并解读其为何可达到远远超出其它区块链系统的500毫秒出块间隔的性能。

为使读者能顺利理解BFT-DPoS共识算法，笔者在这里首先简单介绍一下BFT 协议和DPoS算法。

一、BFT协议

BFT协议全称为拜占庭容错协议，在介绍该协议之前首先需理解何为“拜占庭问题”。该问题是由著名计算机科学家Leslie Lamport在1982年发表的论文“The Byzantine generals problem”中提出的，拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军(系统中的多个节点)需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒(系统中节点出错)，这些叛徒将努力向不同的将军发送不同的消息，试图干扰共识的达成。拜占庭问题即为：在此情况下，如何让忠诚的将军们能达成行动的一致。

该问题的提出对后来区块链的发展有着直接的影响，区块链在本质上就是在一群无相互信任的节点间(有的节点会丢弃信息，有的节点会篡改信息)，如何达成有效的共识。Lamport对该问题的研究指出“对于拜占庭问题来说，假如节点总数为N，叛变将军数为F，则当N大于或等于3F+1时，问题才有解。”也就是说当一群节点中恶意节点的数量少于总数量的三分之一时，这群节点便可通过某种协议达成对某一状态的共识，而这种协议就是BFT协议。

BFT协议简单的表述就是：首先在一群数量有限的节点中通过轮换或者随机算法选出某个节点为主节点，该节点在此时具有出块的权利。当主节点将该时段的交易打包成区块后用自己的私钥对该区块签名，并将其广播到所有节点。其它节点对该区块进行验证和确认，若某个节点确认该区块后对该区块进行签名并发送给主节点。当主节点收到至少三分之二的不同节点的签名区块后，则该区块完成了所有节点的验证成为不可逆区块串联到区块链中。

二、DPoS 算法

在比特币的共识算法中由于PoW资源消耗过大，并且算力也越来越集中，因此Dan Larimer在2014年作为比特股的首席开发者时提出了一种快速、安全且能源消耗比较小的授权股权证明(DPoS)共识机制。DPoS在最小化网络成本的同时，赋予每个持股人一定的投票权，由他们投票产生“超级节点”代表。最后由获得票数最多的一定数量的超级节点轮流平等地产生区块。在比特股中Dan Larimer选择了101个超级节点，但在EOS中选择了21个超级节点，主要有两方面原因：一是由于用户很难对较多数量的超级节点充分了解，所以过多的超级节点会降低用户投票的活跃度;二是规模为20的节点数目可以在拜占庭问题中以更低的资源成本来获得高效的共识。

这些超级节点的主要职责是：提供相关计算资源和网络资源，保证节点的正常运行;当轮到某超级节点拥有出块权时，超级节点收集该时段内的所有交易，并对交易验证后打包成区块广播至其他超级节点，其他节点验证后把区块添加到自己的数据库中。在EOS技术白皮书中，每个出块间隔定义为3秒，这主要是由于在当前的网络环境下，一个超级节点打包区块并将其广播，绝大多数其他节点收到该区块的过程耗时最多3秒。只有下一个超级节点收到了上一个超级节点广播的区块时，再进行新区块的生成才不会造成对某个超级节点产生区块的忽略。而一个区块要成为不可逆区块需要超过三分之二的超级节点进行确认，在DPoS中只有超级节点产生一个新区块，才表示它对之前收到的区块链进行了确认，所以一个区块产生后，其后续串联14个区块才表明该区块是不可逆区块，区块中的交易是不可逆交易，整个确认过程需要45秒。

DPoS共识算法也具有极强的抗分叉能力，因为区块添加到一条区块链分叉的速率与拥有该共识的超级节点比例是相关的，也就是说，具有较多超级节点的分叉会比拥有较少的那一条分叉增长速率快。任何时候一个诚实的超级节点看到一条有效的更长链时，都会从当前的分叉切换过来，又由于超级节点数量为奇数个，所以在任何时刻一定会有一条较长的链。当一个超级节点设法在两条分叉上同时生产区块时，EOS的持有者会在下一轮投票中将该超级节点删掉，并且EOS社区会给予相关恶意节点一定的惩罚。因此，在一般情况下，使用DPoS的EOS都是很难经历分叉的。

三、BFT-DPoS 共识机制

在最早的EOS技术白皮书中，EOS主要采用上述的DPoS机制每3秒来产生一个区块，而在最新版的EOS Dwan 3.0中为使区块链系统有更快的出块速度，EOS 采用了BFT-DPoS共识机制从而达到了500毫秒的出块间隔。该机制的具体过程是：EOS的持有者通过投票系统对各个超级节点竞选者进行投票，选出21个节点为超级节点。然后这21个超级节点以自身的网络资源状况商议出一个出块权拥有顺序，在每个超级节点拥有出块权时，以间隔为500毫秒(500毫秒是EOS团队通过大量实验测试得出的当前网络状态下可达到的最小的稳定状态下的出块间隔)连续产生12个新区块，然后切换到下一个超级节点连续产生之后的12个区块。

该方式可以保证一个超级节点可以连续以500毫秒的间隔产生区块，因为在同一超级节点产生新区块时不受当前网络状况的影响，但由于网络的延迟很难使得其他节点对已经产生的区块进行确认，使其成为不可逆区块。因此EOS引入了 BFT协议，当超级节点A产生第一个新区块后，A将该区块进行签名并广播给其他超级节点，其他超级节点对该区块进行验证后对其进行签名并返回给A节点，当A节点收到来自14个不同节点签名的区块后，该区块就成为不可逆区块串联到之前的区块链中(以500毫秒产生新区块的过程和对区块进行BFT协议共识的过程在超级节点中是同时进行的，即确认过程不影响超级节点产生新的区块)。EOS团队通过大量实验测试，在当前的网络状况下，一个超级节点广播一个新区块并确认的过程可在1秒的时间内完成。因此，每个新区块的产生到成为不可逆区块最多需要1.5秒的时间，这就使得跨链通信的时延大大缩小。因为一个区块链在引入另一条区块链的交易状态时必须等待其成为不可逆交易，所以两个基于EOS的区块链在3秒钟以内就可以进行一次来回的通信，而以太坊进行类似的通信需要9分钟，比特币需要3小时以上。

上述过程虽然可以保证同一超级节点产生新区块时可以达到500毫秒的间隔，但当切换超级节点产生区块时，由于网络延迟使得上一节点产生的最后几个新区块有可能被该超级节点忽略。为解决此问题，EOS选用了确定顺序的超级节点轮流出块，比如以纽约(美国东海岸)、芝加哥(美国中部)、洛杉矶(美国西海岸)、日本东京、中国上海这样的顺序，该顺序使得上一节点产生的最后区块传播到下一节点时有最小的延迟，从而避免下一个超级节点忽略上一节点产生的区块。如果是随机定义出块权的超级节点，那么在现有的网络条件下，出块间隔只有控制在3 秒时才可保证下一节点较大概率上不会忽略上一节点产生的区块。

使用上述BFT-DPoS协议就可以使得EOS的出块间隔从原来的3秒降低到500毫秒，这也使得跨链通信的时延大大缩短，单位时间内可确认的交易数量大大提升。笔者相信如果这样的机制在EOSIO1.0的正式版本中成功实现，那无疑是区块链技术向支持百万级别用户的目标迈出的巨大一步。