共识算法解读-天下武功唯快不破Conflux共识算法

Conflux团队注意到不论是中本聪共识还是GHOST共识,他们都是只维护一条主链,非主链的区块则被抛弃了,因此也就导致了这些被丢弃的块不能为整个区块链系统提供安全性,并且也降低了吞吐量(因为这些快被抛弃了,实际上也就是说系统的带宽被浪费了,因此他们就不能为系统贡献吞吐量)

串行交易引发的吞吐量瓶颈

上次我们讲到GHOST算法,它在中本聪共识的基础上提出的确定主链的算法,在保障了在高吞吐量的同时还保障了安全性(即不容易分叉,依然保证51%攻击)。但是GHOST算法的吞吐量是否还有进一步的提升空间呢?

答案是肯定的!Conflux团队注意到不论是中本聪共识还是GHOST共识,他们都是只维护一条主链,非主链的区块则被抛弃了,因此也就导致了这些被丢弃的块不能为整个区块链系统提供安全性,并且也降低了吞吐量(因为这些快被抛弃了,实际上也就是说系统的带宽被浪费了,因此他们就不能为系统贡献吞吐量)。

并且注意到,比特币的吞吐量很低的原因是它是串行执行交易的,也就是说交易必须先排好序才能够执行,这产生了很多不必要的依赖,也是导致分叉的根源。于是Conflux就采用延迟排序交易的方式,先乐观地并行执行交易(不论是否有依赖或者冲突)和出块(不论是否会产生分叉),然后经过一段时间再全局地对所有的交易排序,并删除哪些冲突的交易。

顺着这个思路,我们发现最核心的问题就是如何解决并行出块的时候,还能对区块的全局序达成一致,从而保证账本的不可篡改。那么Conflux是如何做到的呢?

父边/引用边与DAG排序

为了并行出块,就需要把所有的块纳入到整个区块链之中。Conflux采用采用了两种关系来定义区块之间的关系:父边(parent edge)和引用边(reference edge),参考下图:

  • 父边:新出的块指向祖先块,类似于比特币那样
  • 引用边:节点新出的块发现整个区块链中目前没有指向他的块,并建立一条指向他的边

图片

全局区块排序就顺利成章了:

  1. 先按照GHOST规则排序只包含父边的块,形成一个枢轴链(pivot chain),它类似于比特币的主链,不一样之处在于它还会引用比特币系统中丢弃的块
  2. 根据枢轴链对区块分成各个纪元(epoch),然后对每个epoch里面的区块拓扑排序。确定epoch包含的区块的划分原则是需要同时满足以下两个条件:
    • 该区块可以通过枢轴链的父边或者引用边遍历到
    • 该区块没有被之前的epoch包含
  3. 根据happens-before原则(就是谁在谁前面)对不同epoch之间的块进行排序

上述内容,可能涉及到一些专业术语 不好理解,举个排序例子(参考下图):

图片

先根据最终子树GHOST原则确定枢轴链为G->A->C->E->H->NewBlock,然后由于C引用了B,所以拍B->C;那么D和F如何排序呢?D的父亲是A,F的父亲是B,A的epoch大于B,所以D在F前面。按照这样的顺序排完就是:

G->A->B->C->D->F->E->G->J->I->H->K->New Block

当然还有一些细节,比如两个区块在同一个epoch内,并且父边也在一个epoch里,那么就根据区块的hash值id的绝对大小排序,比如假设区块DD的id是011,FF的是111,011<111,所以DD在FF前面

具体的算法如下,图中相关名词对应的解释参考其论文《Scaling nakamoto consensus to thousands of transactions per second》

图片

交易的排序

区块排好序之后,在每个区块内,按照交易的出现顺序排序,如果有冲突交易,那么只保留最先出现的那个,丢弃所有冲突的交易。

看起来很厉害是吧,那么实际实验结果如何呢?

性能

吞吐量

限制带宽20M,在4M/5s的出块速度下,每秒能处理比特币网络中3200笔交易!

这个还是非常恐怖的数字,要知道以太坊现在每秒才30~40Tps,Visa才6000多Tps。

确认时间

因为交易的序受枢轴链影响很大,而枢轴链的序是按照GHOST规则来定的,可以证明,Conflux的安全性与GHOST一致。那么按照攻击者有20%全网算力,并且只有0.01%的概率(由GHOST安全性计算规则算出)篡改交易的假设,得到的数据是:4M的区块,5秒出一个块的话,在保证安全性的同时确认时间也只有10分钟。

图片

可拓展性

带宽

带宽20M时3200Tps,近11分钟确认时间;

带宽提升到40M,交易处理速度几乎线性上升到6400Tps,确认时间也只有5.68分钟。

节点数目

如下图,可以看出,随着节点数据增多,确认延迟几乎只是随之线性增长(不像BFT算法那样指数增长,受节点数据拓展影响很大)。

图片

因此可见,Conflux提出的共识算法已经不在是PoW公链性能上的共识瓶颈

未来

如何处理带宽限制,高吞吐量带来的存储问题(20M带宽就消耗2.88G/h)和交易验证速度等问题,都是继续需要解决的问题。

如何应对存活性攻击等安全性问题,也就是说恶意网络阻塞,也是很值得研究的问题,可参考详解自适应权重 “GHAST”

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-05-30 12:10
  • 阅读 ( 959 )
  • 学分 ( 67 )
  • 分类:入门/理论

0 条评论

请先 登录 后评论
Johnathan
Johnathan

PHD

10 篇文章, 1310 学分