Conflux伍鸣:用DAG结构提升中本聪共识的吞吐率

fengzi 2019-06-30

12月25日圣诞夜,Conflux CTO伍鸣博士做客「火星财经创始学习群」,分享了“Conflux: 使用 DAG 结构提升中本聪共识的吞吐率”。

嘉宾简介:

Conflux伍鸣:用DAG结构提升中本聪共识的吞吐率
Conflux CTO:伍鸣博士
本科毕业于中国科技大学,中科院计算机系统结构博士,曾为微软亚洲研究院(MSRA)系统研究组的高级研究员,研究方向包括分布式事务处理系统、图计算引擎和人工智能平台。近年来在多个系统领域的顶级会议(如 SOSP、OSDI、NSDI、ATC等)中发表论文,并担任过 OSDI、ASPLOS、HotDep等会议的程序委员会委员。

要点速览:

1.基于中本聪共识的思想,使用 DAG 技术改造,可以在不牺牲去中心化和安全性的前提下,大幅提高吞吐效率。
2.为什么传统的基于PoW的中本聪共识机制的吞吐率非常低下?总结来说,为了安全,不得不如此。
3.保证安全性是公链系统最核心的要求,PoS虽减少了PoW中挖矿所需要消耗的资源,但同时引入了很多新的攻击情形和安全性威胁,目前没有很完美的解决方案。

伍鸣博士坦言,目前存在的一些基于PoW的区块链系统所能提供的交易吞吐率都非常低,由此带来很多问题,包含用户体验糟糕、交易费用高昂,并进一步限制了在区块链系统上开发更有意义的应用的能力。

在此背景下,Conflux通过有向无环图技术(DAG)与中本聪共识(比特币的共识机制)的结合,在不牺牲去中心化和安全性的前提下,提高基于工作量证明(PoW)的区块链系统的吞吐率。

以下为伍鸣博士直播的详细内容(由Conflux和火星财经整理)

第一部分:行业背景

众所周知,当前区块链领域面临的最大的一个问题之一,就是效率的问题。业界已经存在的一些基于PoW的区块链系统(例如比特币、以太坊)所能提供的交易吞吐率都非常的低。比特币的极限速度是平均每秒处理大概7个交易,以太坊是每秒30个交易,远远低于像Visa这样的中心化的交易服务可以支持每秒上千个交易的吞吐率。

效率低会带来很多问题:

首先,效率低使得现有的区块链的用户体验很糟糕,比如交易被加入区块需要等很长时间。

其次,吞吐率有限使得交易费用高昂。

更进一步,交易费用高昂限制了在区块链系统上开发更有意义的应用的能力。

为了提高效率,大体有以下这么几个思路:

1.依然采用中本聪共识,但调整协议参数。

通过调整出块时间和区块大小来提高效率。如莱特币(2.5 min/1MB block), BCH (10min/32MB block)。但有研究表明,无论这两个参数如何调整,提高吞吐率必然以降低安全性为代价,在第二部分,我将为大家分析这其中的原因。

2.基于中本聪共识的思想,使用 DAG 技术改造。

这可以在不牺牲去中心化和安全性的前提下,大幅提高吞吐效率。

3.使用 PoS 或 dPoS 机制。

dPoS算法如 EOS 很大程度上牺牲了去中心化,有不小的争议。而 PoS 算法也存在股权集中、难以应对长程攻击(Long Range Attack)等去中心化或安全性问题。

4.使用分片 (Sharding), 状态通道 (State Channel) 等侧链或链下解决方案。

其中一部分被有些人称为 Layer 2。 这些方案与 Conflux 目前的解决方案是正交的,它们在尝试从另一个角度解决吞吐率问题,对吞吐率的提高是可以效果叠加或优势互补的。例如,提升全节点的吞吐率的技术可以帮助使用分片技术的系统减少跨链交易所造成的性能瓶颈,也可以完成更多的状态通道结算交易。

第二部分:中本聪共识机制为何吞吐率低下

为什么传统的基于PoW的中本聪共识机制的吞吐率非常的低下?总结来说,为了安全,不得不如此。

在公有链中,为了能让参与网络协议的机器节点对交易的执行达成共识,矿工挖出区块以后需要在P2P网络中进行广播,以便让所有的机器获得一致的账本结构。每个矿工会根据最长链规则,选择将新挖出的区块接在它所看到的最长链的末尾。也就是所有诚实的节点,会共同延长这个最长的主链。这样,如果恶意的节点没有>50%的算力就不可能逆转主链。

然而,如果网络延迟比较大,使得一个新块在产生以后还来不及传播到全网就会有其他的节点产生另外的新块,就会在区块链上产生了大量分叉。

下面让我们用一个图片,来展示了发生分叉后区块链账本的样子。

Conflux伍鸣:用DAG结构提升中本聪共识的吞吐率

这些分叉带来两个问题。第一,分叉的区块最终被丢弃,这浪费了网络和计算资源。第二,分叉同时也危害了安全性,如果大量诚实节点生成的区块因为分叉被丢弃,攻击者只需要少于50%的算力就可以产生出恶意的最长链了。

因此,在比特币或以太坊中,为了保证安全性,它们需要保持一个很长的出块时间(即很低的出块速率),或者维持很小区块大小以减小区块在网络中广播的延迟,以此来减少分叉出现的频率,但同时也因此大大降低了系统的吞吐率。

提高吞吐率会引发分叉,而不同分叉上的两个区块是竞争关系。它们争夺后续挖出的确认区块,来让自己所在的分支成为最长链,失败者则被丢弃。诚实节点挖出来的区块之间这种无意义的竞争,为攻击者带来了可乘之机。为了提高安全性,比特币选择了降低出块速度,尽量避免这种情况出现。

那么,如果我们选择了另一个思路,即通过允许每个区块选择多个区块作为自己的父亲或祖先,哪怕在出块速度很快的时候,也可以避免诚实区块之间无意义的竞争。这样,就绕开了中本聪共识中安全与效率两难的困境。

在这种思路下,整个网络将构成有向无环图结构(DAG)。下一步要考虑的是,不同的区块中的交易,应该以什么顺序执行?这时,我们通过设计一个安全的有向无环图拓扑排序算法,每个节点只需要在自己本地的 DAG 上执行一遍这个算法,就可以获得一个区块的执行顺序,这个算法应该保证:

·每个挖矿的机器节点排出来的序应当是一致的。
·即使在遭遇双花攻击时,这个顺序也不可被更改。

稍后,我将以 Conflux 为例,来看一下怎么样设计这个安全的拓扑排序算法。

DAG 技术有很多了,比如说 Spectre和 Phantom 算法,这是设计思路与我们最接近的算法,都是采用 DAG 角度优化 PoW 链的效率。但遗憾的是,Spectre 无法对所有区块排一个序出来,这导致它上面无法跑智能合约。而Phantom 被我们发现有漏洞。

同时,还有一些基于 DAG 的算法,与今天讲的内容相比,形似但非神似,比如说雪崩共识,Hashgraph. 这些算法本质上都是联盟链的算法。与通过“股权质押”的方式,将联盟链算法转换成PoS 公链算法。但联盟链转换成PoS公链算法的过程存在安全性问题。比较为人熟知的一些针对PoS的攻击有,无利害攻击(Nothing-at-Stake Attack)和长程攻击(Long-Range Attack)。

第三部分:使用PoW+DAG提高区块链吞吐量实例分析-Conflux 的机制设计

接下来我们以Conflux为例,具体从技术细节的角度看一下,利用DAG提高吞吐量的思路是怎么实现的。

在Conflux中,每个区块包含两种边,父边和引用边。父边和引用边共同构成一个有向无环图。去掉引用边,所有父边又构成了一棵树。在挖矿环节,矿工要监听 P2P 网络中广播的区块,并在本地维护一个有向无环图结构的区块账本。矿工在挖矿时,新区块父边和引用边的选择,需要遵循以下的规则:

Conflux伍鸣:用DAG结构提升中本聪共识的吞吐率

1.在父边构成的树中,依据 Ghost 规则选择一条主链。具体来说,从创世块开始,迭代地去从孩子区块中选择下一个在主链上的区块。选择的规则是挑选拥有最大子树的孩子区块。新区块的父边,应当指向主链中最后一个区块。

2.此外,对于那些既没有父边,也没有引用边指向的区块,我们称为“叶子区块”,新区块的引用边要指向所有剩下的叶子区块。

有了这些边的定义,这个账本结构就定下来了,区块被广播后,所有的节点最终都会得到一个结构一致的有向无环图,即一个一致的账本。

那么有了一致的账本以后,所有的节点如何去决定一个安全的、一致的区块排序呢?我们的核心想法是,首先,这些节点先在DAG中决定一个一致的主链,然后,再根据这个主链来决定一个一致的区块的排序。

下面,让我们用一个例子来看下如何决定一个一致的区块排序。

Conflux伍鸣:用DAG结构提升中本聪共识的吞吐率

主链的选取同样遵循 Ghost 规则,刚刚在选父边的时候我提到过这个规则。我们根据这一规则,我们将区块C,E,H,都选进了主链。

根据我们刚刚讲的选边规则。新区块的父边应当指向 H, 同时 K 是叶子区块。所以新区块的引用边应当指向 K.(注意:H 的引用边指向了 G, 所以 G 不是叶子区块)。

现在我们有了让所有节点对主链产生共识的机制。那接下来,这些节点如何对区块的全序达成共识呢?为了做到这一点,我们引入一个Epoch的概念。在主链上的每一个区块就确定了一个Epoch。在分叉上的区块属于哪个Epoch,是由第一个产生在它之后的主链区块所在的Epoch决定的。比如,区块D属于Epoch E,因为D最先被E引用,所以产生在E之前,但是D并不产生在C之前。按照这个规则,我们可以得到一个一致的排序,如下图所示。

Conflux伍鸣:用DAG结构提升中本聪共识的吞吐率

所以,在Conflux中,我们首先按照Epoch的顺序来给区块排个序。然后在每一个Epoch内部,我们再按照拓扑排序来确定区块的顺序。如果出现平局的情况,我们再根据区块的哈希值来打破平局。所以这个图中的区块排好序以后就是这样的。接下来我们要为交易排序,Conflux首先按照区块的顺序去给交易排序。然后在每个区块内部,我们就按照交易在区块里所在的位置来排就可以了。

最后,我们来看一下,交易如果发生重复或冲突怎么解决。我们再用一个例子来解释一下:

Conflux伍鸣:用DAG结构提升中本聪共识的吞吐率

这个例子里面的交易2和交易3发生了冲突。因为交易2执行过以后,账户X里面就没有足够的余额来完成交易3了,因为在这个交易的全序里面,交易3是发生在交易2之后的,所以我们会让交易3变为无效。另一种情况是,相同的交易有可能被不同的节点打包到不同的并发区块里,比如交易4。在这种情况下,Conflux只会接受在全序中出现的第一个这样的交易,而把后面的重复交易无效掉。

问答环节:

Q1:Conflux 如何与PoS 公链项目对比?

A1:我们都知道,保证安全性是公链系统最核心的要求,因为公链本身就是在构建一个可信的系统。PoS虽然减少了PoW中挖矿所需要消耗的资源,但同时它也引入了很多新的攻击情形和安全性威胁,而且目前没有很完美的解决方案。比较为人熟知的一些针对PoS的攻击有,无利害攻击(Nothing-at-Stake Attack)和长程攻击(Long-Range Attack)。出于这个原因,Conflux坚持采用基于POW的共识机制,通过引入DAG的技术来打破共识机制的性能瓶颈。这是我们原型测试系统实际跑出来的结果。

Q2: Conflux 一笔交易能多久确认?

A2: 在没有坏人攻击的情况下,5s 一个 4MB 大小的区块,确认时间约 8 分钟。在有 30% 算力攻击的情况下,确认时间约 16 分钟。

Q3:Conflux的TPS能跑到多少 ?

A3:在谈论和对比 TPS 的时候,我们需要注意区分测试 TPS 的实验设定。例如在比特币中,每一个区块都需要广播给所有矿工,每一笔交易都被所有人验证过,我们称之为一个交易得到的“全节点验证”。在一些 Sharding方案的实验中,所有的交易被分成 30 份, 每个节点可能只验证其中一份。这样的交易称为“部分节点验证”。很显然,“部分节点验证”交易的总 TPS 是可以成倍于 “全节点验证” 的。

Conflux 在共识层面可以做到 4000-6000 TPS 的“全节点验证”, 如果考虑合约执行、状态读写等因素,实际部署可能会低一些。Sharding 技术是共识层技术一个很好的补充,Conflux 有计划在未来实现 Sharding, 提供更高的 “部分节点验证” TPS, 为用户提供多种选择。

Q4: Conflux的roadmap和相关时间计划是怎样的?

A4: 我们计划在春节后测试网上线,预计明年Q3主网上线。

Q5:Conflux会有代币发行吗?还是挖矿?

A5:Conflux没有ERC20,主网上线之后会有挖矿。

Q6: 那这里会不会涉及到PoW,或者挖矿的算力? 另外这里的主要难点是什么?面临的主要技术问题是什么?

A6: Conflux 是基于中本聪共识做的改进,是一个PoW 共识机制,当然会有挖矿。

这里主要的难点是为DAG的账本设计高效的一致的排序算法。这个算法要能保证好人之间达成一致,还能够抵抗各种复杂的攻击情形。

Q7: Conflux是如何预防双花攻击的?

A7: 这个问题回答起来比较复杂,先来看一个图

Conflux伍鸣:用DAG结构提升中本聪共识的吞吐率

在这个图中,我们首先来看一下一个攻击者如何能够逆转在账本中的一个交易,比如交易4。为了做到这一点,一个攻击者需要产生一个交易4的双花交易,打包到一个区块里面,并且将这个区块在区块的全序中插入到区块B的前面。

但攻击者很难做到这一点,主要有两个原因。第一个就是除非攻击者能够改变主链,不然他不能够逆转交易,因为交易的顺序是由主链来决定的。比如一个攻击者想把一个块插在靠前的位置,他能做就是在一个很早的Epoch里面的区块后面接着产生新块。但是只要这个块不在主链上,它就最终还是会属于一个很晚的Epoch。因为当一个诚实的新块产生以后,它会通过引用边把这个攻击者的区块给拉到新的Epoch里面。

第二个原因就是,如果攻击者没有超过50%的算力,他就没有办法改变主链。

Q8: Conflux的CTPS有测试数据吗?

A8: CTPS是指确认交易的TPS。我们实验中测出来的TPS实际上就是确认交易的TPS。大概在4000~6000。

Q9: 挖矿的话,对于挖矿设备具体有什么要求呢?

A9: 我们会选择GPU友好的POW算法,所以使用GPU设备就可以了。

Conflux伍鸣:用DAG结构提升中本聪共识的吞吐率

相关推荐