有向无环图DAG，图论/算法中有时也称为有向无环图DAG ( Directed Acyclic Graph)。所谓有向无环图是指：任意一条边有方向，且不存在环路的图。首先它是一个有向图，其次这个有向图的任意一个顶点出发都没有回到这个顶点的路径，是为有向无环；
 

DAG不一定能转化为树，但是树一定是一个DAG；
 

DAG可以执行拓扑排序。

生活和工程中的许多事例都能转化为DAG模型，比如：

有n个矩形，大小不同，导致有些矩形能够嵌套进另一些矩形。告诉你这些矩形的长和宽，让你找出尽可能多的矩形，使它们能依次嵌套在下一个矩形内。乍一看这个问题和DAG没有任何关系。但是仔细想想，如果一个矩形能够嵌套在另一个矩形内，那不就正好有一条[边]连接着这两个矩形（矩形看作顶点）吗？也就是一个矩形的边指向另一个矩形的边。同时一个矩形显然是无法自身嵌套自身的，所以可证明无环。因此，这是个DAG。

工程上是如何实现以DAG算法为共识的。

我们今天来看下具体的业务流程，从一笔交易的发起，到交易入块的整个逻辑。

DAG的实现

1、我们启动一个ethereum节点和一个DAG节点，它们之间是通过proxy进行连接。

2、ethereum调用proxy把交易传到DAG节点，DAG节点调用Core的AddTransctions把收到的交易加入到transactionpool里。

3、gossip心跳检测到需要发起gossip，便会创建一个新的event，把transactionpool的交易全部打包到event里，然后插入到Store里。

4、随机选取一个peer，发起gossip，从目标peer拉取自己不知道对方知道的event，并把自己知道的event传给对方。

5、拿到对方返回的event，调用Core的EventDiff来合并Event，并增加pedding区的Event，然后执行RunConsensus，来DivideRounds，调用DecideFame决定famous witnesses。

6、通过多次的gossip，famous witnesses被确定，然后调用FindOrder去决定roundReceived和consensusTimestamp，然后排序。

7、调用handleNewConsensusEvents取出新共识过的event，并把里面的交易打包到一个块里，清空pedding区。

8、把区块返回到ethereum，ethereum执行区块里的交易，并把账本状态返回到DAG，DAG把账本状态入块，然后签名，再把签名广播到其他DAG节点，其他DAG节点收到签名，验证无误，与自己的签名合并入块，再把自己的签名广播。

DAG主链（哈希图谱）逻辑

DAG共识与pow共识最大的区别在于，交易顺序的确定，以太坊中是单个矿工说了算，矿工可以根据自己的挖矿策略（交易手续费的高低）来决定一个块中包含哪些交易，然后通过哈希算力争夺记账权。而哈希图谱中，hash graph 通过gossip协议在对一个round中的交易顺序达成一致，并形成一个块，简单来说这些交易顺序是通过协商确定的，一旦确定不可更改。这样，分布式中的每一个账本根据相同的交易顺序向下演化世界状态，最终可以保持账本的一致性。

• DAG
• 矩形
• event
• 交易
• goip