共识算法解读-天下武功唯快不破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包含

1. 根据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”

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

上次我们讲到 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”