【搬运】区块DAG的范式入门

概要:

与大众的普遍观点相反,将 DAG(有向无环图)用作分布式账本并不会消除工作量证明式的挖矿,也不会消除区块和交易手续费。它的目的是利用 DAG 的结构特性帮助解决区块链的孤块率问题。DAG 解决这个问题并且改进可扩展性的能力取决于为了处理交易一致性而额外实现的规则,以及其它设计上所作的选择。

Directed acyclic graphs 有向无环图

DAG 并不是一个新概念或是技术,也不是一种共识机制;它纯粹是起源于几个世纪前的一种数学结构。在技术上,DAG 是一种包含有向边但不含环(即没有一条可以从一个顶点出发然后又回到它自己的路径)的图。

字节雪球

字节雪球Byteball的DAG结构

在分布式账本的环境中,区块 DAG 一种有特殊含义的 DAG。在这种 DAG 中,顶点代表区块,边代表区块对它们父辈的引用。显然,在区块 DAG 中,区块可能有多个父辈,而不是只有一个;下文会对此进行详细描述。首先,让我们回顾一下孤块率问题。

区块链的孤块率问题

有许多因素制约着区块链的可扩展性,包括处理速度、磁盘 I/O、RAM、带宽,以及新节点的同步(即新节点刚加入网络时将整条区块链下载同步到自己本地的过程)。虽说可以通过改善硬件和技术来突破这些限制,但一个最主要的瓶颈是在协议层面:孤块率。孤块是指由于不可避免的网络延迟而在最长链以外创建的区块。

加快区块创建速度或者增大区块大小会提高孤块率,即在一个新区块传播遍网络之前,很可能会有其它新的不引用它的区块被创建出来(即广义的“分叉”)。孤块率增大会导致安全性降低,这是公认的。如果有越多的诚实区块因为自然分叉的原因导致自己不在最长链中,那么这条链就越不安全。^1 (注:这里的自然分叉是指由于协议本身的特性和网络延迟导致的分叉,而非攻击导致的分叉。在最长链规则下,分叉越多,攻击者为了使自己成为最长链而需要的算力就越小,因此最长链就越不安全。比如在有三条分叉的情况下,攻击者只需超过全网三分之一的算力即可攻占最长链。因此从协议本身的角度来讲,自然分叉越少越好。)

区块链协议一般会规定一个最大区块大小和一个常数的出块率从而应对网络延时并且将孤块的数量降到最低。这种对交易吞吐量和等待时间下限的人工限制(在比特币的情况下,这个限制是每秒3至7个交易和数十分钟的确认时间)对区块链来说是一副苦药丸——它阻止了链上扩容,但保证了自然分叉和孤块极少出现,因此主链是安全的。然而 DAG 可以通过其它方式处理孤块问题。

区块 DAG 范式

DAG 结构有机地吸收了分叉这一概念,所以有必要考虑 DAG 是否可以比链式结构的区块链做得更好。于是,以中本聪的工作量证明为基础,为了生成一个区块 DAG,我们需要对挖矿协议做出一个改变:区块可以引用多个父辈,而非一个单一的父亲。一种经典的扩展账本的方式是让区块引用图中(产生区块的挖矿者在本地能看到的)的所有末端,而非依照中本聪的原始协议只引用最长链的末端。和在区块链中一样,区块会被立即发布。

然而,和区块链不同的是,区块链在构建时会一直维护着一致性(链中的每个区块添加的交易都与链中的父辈一致),而区块 DAG 包含了来自不同“分叉”的区块,所以可能包含许多冲突交易。因此,DAG 或是区块 DAG 本身并不能被认为是一个“解决方案”或是“新方法”或是“新协议”。区块 DAG 只是一个用来设计共识协议的框架,而基于它设计的协议与链式协议相比可能(也可能不)具有同等的安全性和更高的扩容性。^2因此,我们需要一种方法来恢复一致性;换句话说,区块 DAG 系统需要用新的共识协议来取代中本聪的最长链共识。

通过排序达成共识

如果一个分布式系统对系统中所有事件的顺序达成共识,我们就可以很容易地将这个共识扩展到状态的共识——只需要简单地按照达成共识的顺序遍历所有交易,并且接受那些与已经被接受的交易一致的交易。这种方法使网络在构建区块链的过程中就一直维护着一致性。我们现在要做的就是为系统中的所有事件,也就是 DAG 中的所有区块,定义一个排序协议。所有节点都会遵从这个协议从而在区块顺序上最终达成共识。

DAG 的自然拓扑本身就已经为区块引入了偏序排序:若在 DAG 中有一条路径是区块 X引用区块 Y,即可证明区块 Y 是在区块 X 之前被创建的,因此在全局排序中应该排在 X 前面,反之亦然。因此,我们只需要为并行创建的区块(相互之间没有路径相连的区块)所组成的集定义一种顺序。这种范式起源于耶路撒冷希伯来大学开发的基于区块 DAG 的协议(InclusiveSPECTRE,和 PHANTOM);这些协议分别定义了自己的算法,每个算法都对 DAG 中的区块进行排序,并按顺序遍历 DAG,消除与已经被遍历过的交易相冲突的交易。

区块 DAG 的优势

1. 确认时间可以以秒计算,至少是在有可见的双花和冲突交易时

2. 交易吞吐量可以变得很大,只受限于网络条件和终端能力;这样衍生出的好处是手续费会降低

3. 因为每天可以创建大约 100,000 个区块,所以矿工加入矿池的动机也会变弱,这进一步促成了挖矿去中心化

4. 规避了孤块的风险,从而带来很多额外好处(比如与第二层兼容)(注:第二层是指侧链或链下的解决方案,即在主链之上,新建一层辅助的平台和协议,比如闪电网络。)

5. 通过奖励所有区块,消除链上和链下区块的差别,从而消除自私的挖矿行为

区块 DAG vs. 无区块 DAG

市场上几乎每种基于 DAG 结构的加密货币(IOTA、字节雪球、Nano等等)都偏离了中本聪的区块链范式。这种偏离不仅体现在使用 DAG 结构上,还体现在经济学层面的设计上:有的将挖矿委托给用户,有的完全去除了工作量证明挖矿,许多货币没有交易手续费,并且实际上都没有区块——它们将一个个交易直接连在一起。虽然这些设计决策可以用在 DAG 系统中,但它们的特性和 DAG 完全无关。实际上,这些项目可能只用到了 DAG 特性的很小一部分。这些 DAG 系统的兴起很大程度上影响了社区对 DAG 的看法。一方面,狂热支持派将 DAG 技术吹捧为“区块链3.0”;另一方面,怀疑论者对其不屑一顾。可是几乎所有人赞扬或批评的都是现存 DAG 协议在经济层面的设计决策,而这和 DAG 结构根本毫无关系。

比如,在最近的一个问答中,著名比特币专家 Andreas Antonopoulos 将 DAG 描述为和工作量证明相对的“另一种共识机制”。“如果你没有将工作量证明挖矿去中心化,你其实并不需要区块。” Antonopoulos 说道,“你只需要直接将交易连起来,这就是有向无环图的基础。”(点击查看 Andreas Antonopoulos 的问答视频

但是上文已经解释过,DAG 并不是要取代工作量证明或区块。DAG 只是一种数学结构。只是这种数学结构恰好被一些偏离了中本聪的工作量证明系统的项目所使用。与此相反,区块 DAG 是要将 DAG 应用在基于中本聪的系统中(并且特别要强调的是,区块 DAG 使用工作量证明),只是将数据结构和共识层重新设计了一遍。比特流(BitTorrent)和 Chia 的创始人布拉姆·科恩(Bram Cohen)在推特上发表的尖锐评论更接近本质:

有向无环图(DAG)是一种数据结构,而不是一种工作量证明。早在2005年它就被用在 Git 中。它的起源则更是久远。DAG 并不是什么新奇的、引人注目的,或是让人兴奋的东西。

——布拉姆·科恩,2018年1月31日中午12点

的确,DAG 和区块链的不同纯粹只是在结构上,并且区块链也不是什么新奇的、引人注目的,或是让人兴奋的东西。中本聪系统的新颖之处是在它的全局设计上:工作量证明挖矿、区块、交易,以及一个在缺乏信任的系统和需要依靠物质激励的参与环境中达成共识的协议。像 SPECTRE 和 PHANTOM 这样的区块 DAG 系统比中本聪的革新设计更为通用和创新的地方在于:它们独特的共识协议对 DAG 的排序是不可翻转的,因此避免了孤块带来的安全性和扩容性之间的取舍问题。

脚注:

^1 该论述的证明可参考 [a][b][c]

^2 比如,如果一个 DAG 协议对交易进行排序时将最长链里的交易全部排在其余交易的前面,那它的安全性与扩容性的折衷关系就和区块链一样。

本文搬运自DAGFans.org 如有侵权请联系:mylifeform@qq.com,我们将会在24H内删除。