『学概念找员外』有向无环图DAG的用途

发布网友 发布时间：2023-01-02 23:29

我来回答

共1个回答

热心网友 时间：2023-10-10 02:22

有向无环图（DAG, Directed Acyclic Graph）：是一个无回路的有向图。如果有一个图，从A点出发到B点，然后经过C点，最后可以顺着方向回到A，形成一个闭环，那么这个图就不是非向无环图。如果将从C到A的边方向改为从A到C，则变成有向无环图。如图1 和 图2。

看到这两幅图，应该可以明白了，当然这个图是很简单的，只有三个点，事实上可能是由百万千万或者更多个点组成的图。有向无环图就是从一个图中的任何一点出发，不管走过多少个分叉路口，都没有回到原来这个点的可能性。

拓扑排序：就是一个有向无环图的所有定点的线性序列。且这个序列必须满足这两个条件：

这个东西，是比较难理解，再上图说话吧。比如在这个有向无环图中，它用拓扑排序，该怎么进行呢？

最后，一个完整的拓扑排序就完成了，结果为：1、2、4、3、5。

大家都知道，在比特币系统中，固定约十分钟出一个块，而且一旦打包成功一个区块，这个区块的信息还必须同步到其他的所有区块上面去，这是极其耗费资源和时间的。同时一个块里面大概能容纳3000笔交易，也就意味着10分钟才能交易成功3000笔。这个交易速度实在是满足不了用户的需求，所以为了解决比特币这个问题，出现了各种分叉币，也可谓是把比特币搞的乱七八糟了。后来以太坊问世后，基于比特币的基础上，交易速度提高了不少，每秒交易可达到20笔左右，但是任然有多次的以太坊拥堵事件，证明这个交易速度还远远不够。

在比特币系统中，如果可以改变51%的节点的记录数据，那么就实现了恶意攻击。然而现在比特币的大部分算力掌握在少数几个较大的矿厂手里，虽然大家都有共识，不会发起恶意攻击，但是不代表不会有意外事件发生。

随着计算机硬件的不断迭代升级，量子计算机的问世，那么比特币的加密算法还会有用吗？会不会被破解掉？虽然比特币的哈希算法可以实时调整难度，但是到底能承受多大的考验，员外是说不清的。

比特币用于大额的跨境转账或者交易等用途，还是挺实用的，但是谁会去用比特币购买小件商品？显然是不可能的，交易手续费就会让你心疼半天，然后还得再等半天的确认时间。

在区块链的应用上使用了DAG图之后，可以使得出块速度变快，因为DAG图中的每个顶点都是一个在某一时间点打包完成的区块。与传统的公链一次性只能产出一个区块来比，DAG的不同节点都可以自己来生成区块，然后这个区块只要选择好自己的下一个或者多个区块作为自己的子区块就好了。仅仅是在这一点上，出块速度就会高出比特币多个量级，交易速度简直可以快的飞起。

基于DAG的数据结构来说的话，对于里面的每个节点来说，因为与之相连的节点很少，而且是有方向性的，只能往前不能后退，所以都不需要再等大量的其他节点达成共识后，再同时确认下一笔交易了，避免了因网络延迟和数据同步造成的大量时间浪费。所以，使用DAG记账的节点的延展性可得到大幅度提升。

从上面这张图中，可以看到DAG的每一个节点都可以向下连接任意多个新的节点，这个有什么用呢？如果在这一个区块内部交易数据或者与之相连的下一步的交易数据也是过多的话，那么就可以分成足够多个区块来共同分担区块压力，从而可以提高交易的吞吐量。相比于比特币这样的系统每次只能打包一个区块来说，简直是完胜。

没有一个东西是完美的，有优势就有缺点，所以DAG的缺点目前在安全问题上面，主要是双花和影子链攻击。这个问题员外目前还没有找到足够好的答案，只能后续再说了。

本文参加优享优质经验征集计划，经验即价值，优享为成长买单
全球首个去中心化经验价值共享平台“优享”开启今夏最强空投!注册即送UX，最高5000UX，更多价值，等你发现！注册链接