Directed Acyclic Graph, DAG

分享者：彦丞

DAG概念

DAG：Directed Acyclic Graph，中文意为「有向无环图」。

如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图。link to WIKI

注意：

DAG不一定能转化为树，但是树一定是一个DAG
DAG可以执行拓扑排序

简单原理

”教授为了偷懒，让学生互评作业

规则是每个学生交作业前，要去批2份已经上交的作业，之后自己的作业才可以提交。”

Why not blockchain？

效率问题：TPS
确定性问题：51%算力攻击，量子计算机
中心化问题：中心化共识
能耗问题：比特币的挖矿能耗已经与阿根廷全国耗电量持平

详细说明

理想化的DAG大概是这么个图（没有所谓的主链）

在区块链的应用上，DAG图的每个顶点代表在某一个时间新挖出的区块。DAG允许不同节点按自己的节奏生成区块。

每一笔交易就是一个区块，没有容量限制，每个区块有多指向，拓展性强。

参与者越多，系统越安全，交易也越快。

DAG实现方法

DAG系当前的代表项目，最知名的无疑是DAG三架马车—- IOTA、Byteball、Nano（原来的Raiblocks）

IOTA实现

iota用的tangle结构，就是有个交易确认度的概念
不过由于其共识机制还在发展中，网络不够完善
所以提出了一个coordinator的机制，目前应该也还是中心化的

IOTA在防止双花上采取了不同的策略。IOTA将主链的概念普遍化为扭结（tangle），实际上代表厚度任意的主链。

在新顶点产生的时候，每个新顶点会选择2个旧顶点作为父顶点，并进行PoW挖矿。

IOTA在确定扭结时，按照所有的父顶点关系进行权重计算，给予较多子顶点支持的父顶点更多的权重。

NANO实现

另外提一下nano，以前叫railblocks 采用点阵结构 nano我记得是一个中国人做的，非常独特和优美

Nano采取的DAG架构是给每个账户安排一条单独的链，这些链只有每当有发送或者接受转账时会更新相关交易的信息，这样每条链都只处理跟自己账户有关的交易，大大减少了需要处理的交易总量。

与比特币不同，由于Nano每个账户有单独的链，对未来的交易可以提前进行PoW挖矿。Nano白皮书对于事先提前挖矿的攻击并没有防御措施。

Byteball实现

byteball本身指定了12个见证人节点，由见证人来确定主链选择。

Byteball要求从创始块开始确定一条所有参与者公认的主链，而将其它的顶点看作是附属在这条主链上。
每一条主链对应着一种不同的主观上的时间顺序，从而对应着不同的双花交易的确认。

另外为了防止影子链嫁接在主链上，Byteball提出见证人（Witness）制度。系统自动选择被见证次数最多的顶点作主链。

其他实现

一些已经上市，但是实际上还没推出主网的项目，比如vite，CyberVein，Ambr等等

由于在tps上已经没法再吹牛，新的dag项目主要是宣传安全性，提出新的共识算法，支持智能合约等等

技术架构

不同共识概略

DAG的共识算法方面实际上基本都是DAGLabs推出的
早期的比如Inclusive，Spectre
今年出现的Phantom和Avalanche

Spectre是支持pow的

另外Avalanche应该已经有个项目再发车了，team rocket

Snowflake to avalanche，白皮书写的非常棒

Phantom是通过对交易进行排序，实现DAG对智能合约高并发的支持方案

Avalanche是提出了一套bft+DAG的方案

挖矿

区块链中添加下一个区块需要多方进行竞争，并获取区块奖励或交易手续费。

正因如此，共识和交易生成是分离开的，并且由网络的一小部分人来完成，通常会设置较高门槛（就像比特币一样），这样会导致进一步的中心化（算力垄断）。

在DAG系统中，交易者本身就是矿工，网络中的每位参与者都能进行交易并且积极参与共识。通过这种方式，验证就能同步进行，网络能够保持完全去中心化，不需要矿工传递信任，也不需要支付交易手续费。

（笔者按：交易者不参与自己的交易的共识，那么交易者做PoW验证的其实是其他节点的交易。算力超过51%的话，大矿池可以做到侧链权重>主链。然而DAG比Bitcoin更安全实际原因在于，由于每层有多个区块，即使矿工发生分叉，后续节点看到分叉矿工的tangle结构，以及the fact that侧链每层只有一个区块，会自动更加信任主链）

攻击

DAG允许多重并行交易的特征，导致攻击者可能暗中生成一条影子链，并且时不时地将影子链跟主链进行对接以逃避检测算法。

极端情况下，这条影子链有可能代替主链成为全网的共识。

智能合约

一个是Constellation，已经上线测试，应该是使用的交易序列，来支持智能合约的实现，同时其智能合约用的是scala语言。
另外hashgraph还有其他几个用的实际上是offchain的智能合约实现形式，用docker，microservice之类，结合DAG

Vite比较特别的是采用了分组，分级的DAG结构，有所谓共识组，快照组
快照组进行全网的维护和确认，具体的大家可以看vite白皮书

总结

所以可以看出来DAG的一个主要尝试方向就是把见证人模式优化成分组分层的结构，通过权重来区别节点以及交易

总的来说DAG结构目前只适合特定方向的应用场景，自身也有非常多的问题需要解决，共识机制也才刚刚开始完善，广阔天地大有可为

Q & A

IOTA如何防止垃圾交易拥堵网络？

Gossip protocol，降低带宽

又比如hashgraph的gossip of gossip，基本上把带宽降到非常低

那么千万级别TPS的区块链是如何实现的

比如EOS，一条主链3000 TPS，我来300个侧链，差不多就百万级。

然后每条链上我还能做multi thread，千万级不在话下

IOTA和Nano的容错率是多少？

比如iota，根据交易被确认的次数，来确定交易的确认完成度
如果定义为100次，基本上在数学上就是完全可信的了

nano本身不够完善，之前都是一个人在做的

iota就不说了，他的coordinator实际上还是中心化的
只适合iot场景（量大，低价值，高吞吐，对时延精度要求不高）

为什么说IOTA是中心化的？

由于IOTA是为了规模应用而建立的，因此出于安全原因，采用了一种临时性的共识机制：协调器。每隔两分钟，IOTA基金会创建一笔里程碑（milestone）交易，所有经它确认的交易立即被认为具有100％的确认置信度。

使用协调器，Alice的第二笔交易就永远不会得到确认。协调器在IOTA网络早期发展阶段充当了一种保护机制。

（笔者按：这个调节器实际上是在共识不稳定时期做一个防止回滚的功能）