涨知识 | 正热门的新一代分布式账本结构 DAG 到底是什么？

链闻ChainNews
公众号ID：chainnewscom

关注

在大洋彼岸的加密世界里，上周最热门的初创公司要数 Hedera 了。这家公司宣布获得 1800 万美元融资，由 Digital Currency Group 领投，计划在下半年推出新的虚拟货币平台 Hedera Hashgraph，实现每秒钟处理数十万笔交易的能力。

Hedera Hashgraph 平台并不使用传统的「链式」区块链技术，而是使用一种新的数学模式 DAG directed acyclic graph，在中文世界，通常被译为「有向无环图」。DAG 技术或结构其实并不是新鲜事物，Byteball 和 IOTA 也都采用这种模式，也引发过不少争议和讨论。

DAG 或「有向无环图」究竟是什么？链闻 ChainNews 特别选择了一篇由硅谷创业公司 NAD Grid 技术合伙人老钱撰写的一篇文章，通过介绍 IOTA 及其背后的机制和争议，让读者更清晰地了解这种热门的新一代分布式账本技术。

老钱毕业于伊利诺伊大学厄巴纳-香槟分校，师承著名密码学者 Andrew Miller，目前正忙碌于创业项目 NAD Grid，通过区块链技术实现更高效的电力传输和分配。他之前曾为链闻 ChainNews 读者奉上过关于零知识证明的专栏《一个数独引发的惨案：零知识证明》。

如果你关注区块链和加密货币，相信你已经听说了 IOTA 这个异军突起的加密货币。作为一个加密货币，IOTA 的成绩单是非常漂亮的。但是你知道他背后的技术是怎么样的嘛？你知道 IOTA 在社区里的争议性不亚于 BCH 嘛？你了解 IOTA 团队的前世今生嘛？今天老钱来给大家聊聊 IOTA。

IOTA 是什么…

IOTA的初衷是一个给 IoT 设计的加密货币，这个目的反映在了这个货币的名字里。在 IOTA 对物联网的世界观展望里，智能硬件终端之间将会根据用户设定的规则进行大量频繁的小额交易。想象有这么一天，你把你的智能汽车停在路边走进一家咖啡店，路边的智能咪表每分钟自动向你智能汽车里的钱包扣停车费，咖啡店的屋顶装着光伏板，太阳能发电供给这家咖啡店的所有电力设施，发电的盈余将会输给同区域的另外几家住户，这些住户家里的智能电表自动通过计算来买咖啡店的太阳能发电盈余。这些都是IoT终端之间交易的例子。

IOTA 核心团队成员有 David Snsteb、Sergey Ivancheglo、Serguei Popov 和 Dominik Schiener，这个团队之前的产品是 NXT，最早的一个基于 PoS 的虚拟货币。

IOTA 背后的分布式账本结构并不是传统区块链中「链式」的结构，而是一个有向无环图（DAG），IOTA 称之为 Tangle，中文翻译为「缠结」。在这个 Tangle 中，每一个节点代表的是一个交易。IOTA 里没有区块的概念，也没有挖矿和矿工的概念。这可能是 IOTA 的最吸引人的亮点了，没有挖矿和矿工就代表没有交易费，币量也是恒定的，而且整个网络的吞吐量 Throughput 也能很高。听起来是不是一个很理想的系统？接下来我们就来深入了解一下 IOTA 的技术细节，一起看看哪些已经是现实，哪些东西社区还在探索和研究。

IOTA 技术细节

在 Tangle 这个由交易组成的有向无环图里，一个网络节点要发起一笔新的交易时，需要在 Tangle 中找 2 笔其他交易去验证，并且将自己新发起的交易指向这两笔交易，整个 Tangle 就是这样一点一点扩大出去的。正因为这样的设计，整个网络中验证交易的责任从传统的矿工转移到了每个网络的使用者身上——你想要发起一笔交易，就必须帮着一起验证网络中的其他交易。

上图这个例子是截取了 Tangle 中的一部分（Tangle 扩展的方向是从左到右，越往右的交易越新），交易 A 指向交易 B 和 D，那么 A 就是直接验证了 B 和 D（A directly verified B and D）；A 虽然没有直接指向 F，但是 A 到 F 之间有一条通路 path，那么我们可以说 A 间接验证了 F（A indirectly verified F）。上图中 A 和 C 称为 2 个 tip，tip 是指还没有任何其他交易直接或者间接指向他们。

一个网络节点发起一笔新的交易时，除了需要找 Tangle 里 2 笔其他交易去验证之外，还需要做一个 PoW 计算。这个 PoW 计算比比特币的 PoW 计算要简单很多，一台普通电脑可能只需要 5-10 分钟就能完成计算。IOTA 设计 PoW 这一步是为了防止有人恶意发很多 transaction 从而阻塞整个网络，或者更进一步通过更改整个 DAG 的形状而达成一些攻击。上图中，每个表示交易的小方块里右下角的数字被称为权重 weight，这个 weight 是和 PoW 所付出的计算量相关的，举个例子，假如有2笔交易，他们通过 PoW 算出来的二进制值分别为 x 和 y，x 的开头是 2 个 0，y 的开头是 4 个 0，那得到 y 所需要的计算量一定是大于x的，所以交易 y 的 weight 会比交易 x 的 weight 大。在 IOTA 里，weight 的取值范围是 3^n，也就是weight的取值只可能是 1，3，9，27…

方块里左上角的数字被称为累积权重 cumulative weight，这个 cumulative weight 等于这个交易自己的 weight 加上所有直接或间接指向它的交易的 weight 的总和。比如交易F，直接或间接指向 F 的有 A，B，C，E，所以 F 的 Cumulative Weight ＝ 1+3+1+1+3＝9。

除了 weight 和 cumulative weight，每个交易还有一个分数 score，这个 score 等于这个交易自己的 weight 加上所有这个交易直接或者间接验证了的交易的 weight 的总和，举个例子，假如只看上图的话，E 直接或间接的指向了除了 A，B，C，D 之外的所有交易，所以 E 的 score＝1+3+1+1+1＝7。

这里可以看出 cumulative weight 是一个可变值，从发出交易之后这个值会一直增加，score 是一个不可变的值，交易发出之后，它的 score 就定了。这个 cumulative weight 和 score 能用来干什么呢？且看下面继续分析。

假如我要发起一个交易，我要怎么选 2 个交易去验证呢？理论上你可以随便选。你可以随机选择网络中的 2 个交易，或者你也可以永远只选几个很老的交易（在 Tangle 中处于很左边的位置的交易）。但是一个健康的 Tangle 应该是不断有人发起新的交易形成新的 tips，这些 tips 也应该尽快被之后来的交易所验证。所以选择 2 个交易时，我们更应该倾向选择 tips。

IOTA 官方推荐用一种马尔可夫蒙特卡洛 MCMC 随机游走的方法去选择 2 个 tips，这样能保证整个 Tangle 良好的发展。这个 MCMC 的过程是这样的：

挑选一个 cumulative weight 区间，比如 270-300 之间。
挑选 Tangle 中 N 个 cumulative weight 在这个区间内的交易节点 particles。这些 cumulative weight 落在区间内的节点在有向无环图里可以想象成纵向上的一条 slice，你可以想象这些 particles 都处于一个差不多的垂直面上，理论上他们距离整个 Tangle 最右边边缘的距离也差不多相当。
这 N 个节点往右随机游走，两个相邻节点 A 和 B 之间的 cumulative weight 相差越小，那么 A 游走到 B 的机率也越大。
这 N 个 particles 中最先完成游走并到达的 2 个 tips，这 2 个 tips 就是你的交易需要去验证的 2 个交易。

但是这只是推荐的做法，怎么防止有人只验证一些很老的交易呢？这里就要用到前面说的 score 了。IOTA 客户端在发起交易时，只会选择那些 score 大于某个特定值的交易去验证。这个特定值与当前 tips 的数量正相关。也就是说如果一个交易指向的是 2 个非常老的交易，那么它的 score 就很可能不满足这个特定值的条件，这样他们被新的交易选到的可能性就很小。

那一笔交易要怎么才能算成功确认呢？这里要介绍一个非常重要的概念，叫做 Finality（最终确认性）。如果我们说某一个交易或者转账在某一个分布式的账本上被「最终确认」，那么这个交易无论发生什么，也无法被回滚和撤销。

大家可能觉得，不对啊，区块链的一个基本特性不就是「历史不可更改」么？

这里要指出一个认知上普遍的误解，大部分区块链中的交易不存在「最终确认」这种说法。拿比特币来说，你的交易打包进区块，并得到 6 个确认之后，并不是指这笔交易 100% 确认了，如果有人发起了 51% 攻击，你的交易在攻击之后的最长链里就不一定是被确认的状态。但是如果我们假设比特币不会出现 51% 攻击，那么随着区块链的增长，你的交易被逆转的可能性是越来越低。你对这个交易被确认的「信心」也越来越高。

IOTA 里呢，这个「信心」是可能变高也可能变低的。IOTA 里交易的确认是这样一个「信心值」，这个信心值＝当前所有 tips 中，有多少 tips 存在一条能连通到你的交易的路径，或者换句话说，当前有多少 tips 间接确认了你的交易。假设当前一共有 100 个 tips，其中有 90 个 tips 间接确认了你的交易，那你的这条交易就是 90% 确认。如果我能造出 100 个新的 tips 使得这 100 个 tips 都不间接确认你的交易，那么现在你的交易就变成只有 45% 确认了。

相信你看到这儿不难看出，一个交易要想得到一个足够高的确认信心，那需要等待的时间也不短。如果每个交易都想要超过 50% 的确认信心的话，那网络中交易的吞吐量并没有实质性比比特币这些传统的区块链提高到哪里去。IOTA 更灵活的地方是体现在交易的延迟上，因为如果你选择只要 10% 的确认信心的话，一笔交易被对方接受的速度会快很多。

争议

中心化？

交易确认的信心值居然可以那么简单就改变，这种情况很恐怖吧？IOTA 现在是怎么处理这个问题的呢？很简单，他们在客户端里写死了一个网络节点的地址，这个节点叫 coordinator，coordinator 是 IOTA 团队维护的一个闭源的 component，coordinator 每分钟会发一条交易，为了区别这个特殊交易和别的交易，coordinator 发出的交易称为 milestone。IOTA 现在默认所有被 milestone 间接确认的交易都是 100% 确认的状态。因为没有人可以伪造 coordinator 的交易，所以这个办法是最直接，最简单的解决办法。那么问题来了，这样整个 IOTA 网络不就成了 coordinator一个人说的算了吗？是的…很多币圈大佬和学者都有指出过这个问题，称 IOTA 完全就是一个中心化的系统。IOTA团队也反击称 coordinator 只是在 IOTA 还没有被大规模应用前的一个临时方案。他只是初期出来带一下节奏，等 IOTA 整体网络的负载上去之后，会移除 coordinator。但关键的问题在于，如何移除 coordinator？或者如何建立一个具有良性激励机制的「coordinator 集团」，IOTA 团队并没有给出完美的答案，社区的一种观点是，IOTA 用复杂的参数和 ledger 维护的方法，包裹了从根本上没有解决的类似「权益证明」PoS 的问题。

IOTA 对于上面的观点也做出了一些反驳，他们认为 IOTA 因为没有矿工和区块的概念，所以整个网络的算力可以大致等同于整个网络的交易吞吐量 Throughput，理想状态下，如果吞吐量大了，上面说的那种把交易确认信心值降低的攻击方式不会很简单，因为如果大部分交易流量都是来自诚实的好节点，都跟着规则走，那么一个 attacker 通过添加没用的 tips 来降低一个交易的确认信心会变得杯水车薪。IOTA 的白皮书里提到，只要 attacker 不掌握 1/3 以上的算力，那么 attack 成功的概率会很低。我们来计算一下，现在 IOTA 整个网络的交易吞吐量还很低，大约每小时 1500 个交易。attacker 如果能发每小时 500 个交易就足以可以改变 Tangle 的形状，attacker 如果能每小时发 750 个交易（每 5 秒一个交易），那么基本上整个网络他一个人就能说的算了。5 秒一个交易并不是很难达到的一个目标，所以现在 IOTA 放了 coordinator 这么一个网络秩序的维护者在里面。

Curl 哈希函数与三进制

年中的时候，MIT 的密码学教授 Neha Narula 发表了一篇报告，称 IOTA 内部自己实现的 Curl 哈希函数有严重的漏洞。Narula 教授称 Curl 哈希函数有碰撞漏洞，她的团队用普通计算机几分钟内就能找出哈希碰撞，attacker 可以利用这个漏洞来伪造别的用户的签名，从根本上瓦解 IOTA 的安全性。Narula 教授将这个发现告诉了 IOTA 团队，IOTA 团队很快就把这个漏洞修复了。但是对外呢，IOTA 声称这个漏洞是他们故意放在那里的，因为这样如果有人把 IOTA 开源的代码复制出去做了一个新的Tangle，他们就有办法去整这些抄袭的人……我听到这句话的时候，内心是崩溃的。这可能是我听到过的最荒唐的狡辩了。

密码学界有一句话：「永远不要自己写加密函数（never roll your own crypto）」但我认为 IOTA 自己写哈希函数还是有他的原因的，IOTA 里对数据的编码采用了一种特殊的三进制编码，主要原因是 IOTA 的团队相信三进制CPU理论上具有比二进制 CPU 更好的能效。IOTA 团队在创造 IOTA 之前，自己也在研发一款叫JINN的三进制 CPU，他们的理想中，JINN 如果成功普及开，IOTA 的三进制模式就非常适合在 JINN 上跑了。这个想法是挺超前的，但是，目前三进制CPU仅仅是在科研阶段。JINN 后续也没有什么进展。我猜 IOTA 自己写哈希函数一开始也是为了适配内部三进制的编码不得已为之的。IOTA 目前所谓的三进制其实也只是一个模拟，IOTA 的代码全都是二进制形式，在程序里需要将三进制转化成二进制，处理完后再转回三进制。

改进方案

IOTA 白皮书里提到了几种可能发生的 attack，这里我就不一一描述了。综合看来，白皮书里提到的attack的方式归根结底都是 attacker 能够改变整个 DAG 的形状而造成的。那么如果我们设计一种机制让 attacker 没那么容易自由的改变 DAG 的形状，是不是就可以防止很多 attack，或者大大降低这些 attack 的成功机率了呢？换句话说，如果发起交易选择 tip 不是一个不确定性 undeterministic 的过程，而是一个确定性 deterministic 的过程呢？这样你的交易指向哪两个 tips 就不是任你选择的，而是能预先判断出来的。比如你发起的交易所需要指向的 2 个 tips 是确定的，而不是通过 MCMC 这种随机游走的方式得到的，会怎么样？我还没有想好这么一个 deterministic tip selection 的方法，但是我有几个 idea。比如挑选的tips是通过交易的 hash 值来决定的，这样是不是确定性就会比 MCMC 要高。这样要想改变整个 DAG 的形状，是不是难度就变得更大了？欢迎大家留言一起讨论这种 deterministic tip selection 的可行性以及对安全性的帮助。

作者：
老钱（BS'14, MS'18）, UIUC 计算机科学系硕士，师承 Zcash Andrew Miller。三年互联网工作经验。目前担任 NAD Grid https://nadgrid.com 技术合伙人。NAD Grid互联能源世界。

该文获得 NAD Grid 老钱授权，并发表于「链闻 ChainNews.com」。
任何中文媒体的转载请与「链闻」联系。

「链闻社」活动预告

「链闻社」第四期嘉宾访谈
3 月 23 日 21:00-22:00

可能你还想看这些

《2018 年不得不面对的 13 个区块链问题》

《型男不适合投资区块链？》
《站在加密风暴中心，操纵千亿美元市值涨跌是种怎样的体验？》
《福布斯加密富豪榜，排名前 19 位赢家全曝光》
《以太坊与区块链 3.0 相比，社区开发者多出 30 倍？！》
《一文彻底读懂 Tether，究竟是神、是妖、还是魔？》

《送你一份「去中心化交易平台」清单，完全收藏版！》
《从美国到波多黎各，一群加密富豪正在搬家！》
《要改 Bitcoin 白皮书、工作量证明的 Cobra 究竟是谁？》
《链闻社 | 嘉宾访谈 ArcBlock 老冒【全程音频+文字整理】》
《区块链商业模式解密｜BAIC 谈毅访谈实录【全程音频+文字整理】》
《区块链项目如何建好开发者社区｜SegmentFault 高阳访谈实录【全程音频+文字整理】》

ChainNews 招聘专场

点击图片查看详细信息

链闻 ChainNews
Buy on the rumor, sell on the news.
有谣言买入，有新闻卖出。

网站改版上线

涨知识 | 正热门的新一代分布式账本结构 DAG 到底是什么？

浏览过的版块