DAG区块链综述

问题现状

区块链面临的问题

区块链作为现在一个热门技术，越来越多的人涌入其中。传统的区块链由于其单链结构和共识算法的限制，存在[!!!]等问题。 之前有研究工作提出，一个区块链中区块链的去中心化，安全，和规模三个特新不能共存。

解决方案

• 分片技术: 将一个交易分片来并行处理，但是很难达成共识，跨链技术通过在不同分片之间建立通道来解决这个问题。
• Layer2 Protocl:参与者能够通过私有通信而不是广播到整个网络来执行脱（主）链交易挑战是如何正确有效地保证链下和链上交易的有效性和一致性。
• 辅助链技术: 通过增加辅助链来让更多的交易参与。
• 混合结构
• 混合共识算法
• 修改硬解码参数

这些方案都受限于区块链的线性结构，因此结构上的改变成为一个新兴方案。

DAG区块链的提出

单链结构使得同一时间多个节点竞争一个可用位置，这导致了认证缓慢，交易竞争和算力浪费。 为了能在同一时间提交更多交易，提出了基于DAG的区块链。

概览

DAG 是指有向无环图，通常被当作一种基础数据结构应用于导航寻址，数据压缩等算法场景。 这个概念首次被Sompolinksky在GHOST中引入区块链，用来解决并发问题。改进版本被作为核心共识算法应用于以太坊中。之后，Lerner在DAGCoin中将粒度从块提升到交易，抛弃了打包和计算步骤大大提高了效率。IOTA和ByteBall 应用了无块的概念，发布了开源实现，至今引领市场。随后，一些工作又在DAG的基础上进行了改进。如Spectre,Hashgraph,Nano等。

基于DAG的系统主要有利于需要高性能低消耗的分布式应用(DAPP)。直接应用底层的区块链可以享受到更好的特性，但是需要专业的开发技巧和昂贵的硬件设备。使用一些官方的组件是一种可替代的方案，如IOTA,MAM,Qubic。目前可以考虑应用的领域有: 物联网，数据管理，车载应用，智能家具等。

建模

一个有环无向图由点集和边集组成。点集的每个元素可以是一个交易，一个块，或者协议中的一个事件。边集的元素是一个元组，代表两点之间的关系。

关键参数 因为现在模型缺乏具体的实现，使用定性的参数来描述系统的基本技术。

• 出度入度: 描述每个单元连接数目。 出度是指从节点指出的边，即节点的前任。入度是指指向节点的边，即节点的继承者。
• 交易模型：描述如何完成一笔交易。UXTO 代表一种无损耗的输出，交易时原子的，不可分割。每个操作必须通过这些交易完成。Account model 维持一种平衡状态。
• 可信度: 一个累加的数字展示一个单元被子块直接或者间接认证的程度。也反映下一轮被选择的概率。
• 认证: 一些独特的参数被用于在网络中认证单元。

分类

节点表现形式

这个间接显示一个系统结构，是交易，事件或者区块。我们定义两种类型: $1^{od}$ 和 $2^{od} $。 前者表示请求到达时会被即刻处理，不需要等待来自节点的更多请求。这种形式包括区块和触发事件。 后者表示请求需要更多操作，多数情况下这个请求需要被预先计算或打包，然后被散播。这种形式包括区块和事件。

节点形式表示系统结构，同时也决定账本模型，表示交易如何在DAG中生成。有两种交易模型: UXTO-based model 和 account-based model。第一个意味着所有操作都必须通过原子事务来实现。用户可以通过跟踪以前的交易历史来计算余额。对于第二个，每个用户都拥有一个帐户，并且交易被配置为其结构中的字段之一。用户直接在他们的账户中计算余额。

网络技术

分为三种 发散,并行,收敛。发散表示单元在不确定的方向稀疏的传播。并行表示在多个链的单元被一组节点维护。收敛表示单元按照一个确定的趋势收敛到一个确定的序列。

按照上述标准分类如下:

共识算法

这里讨论共识算法的几个方面。

开放程度: 表明一个任意节点是否无限制运行共识算法。

成员选择: 选择节点成为出块节点的规则。

单元分配: 共识算法的准备。

单元定位: 确定一个单元在网络中的位置。

扩展规则: 如何扩展图或者链和解除联系。

冲突解决: 表示一系列可以确定冲突单元优先级的参数。

特别技术: 与其他系统不同的技术。

第一类

blockless ane natural expanding graph

IOTA

无限制网络，使用UTXO数据模型，通过交易建立系统。IOTA把节点的事务称为tangle。一个待确认的tip需要先确认前面的两个tip，参与者也共同维护系统安全。但是如果恶意tips被持续生成，可能造成整个图向多个方向发散。所以tip选择算法是必不可少的，有三种机制提供: 一致随机，未加权随机和加权随机移动。最先进的是加权随机移动算法，是马尔可夫链蒙特卡罗 (MCMC) 算法的应用。有一些修改tip选择算法的变体，如GIOTA,EIOTA。

Graphchain:

无限制网络。

IOAT去除了激励机制，而Graphchain又重新引入。每个交易必须认证足够多的节点来获得激励。

Avalancheq

一个无限制,新共识机制的网络。

共识机制不同于拜占庭和中本聪共识。是一种叫做Slush的协议，从gossip算法和流行病网络中获得灵感的CFT容忍协议。

第二类

based on blocks,natural expanding graph

Spectre

一种无限制网络。关键技术是基于块的优先级的递归加权投票算法，

Phantom

总结

从上面提到的区块链系统提取出常用的技术:

1. Cross-referencing(交叉引用)。一个块可以引用多个区块，也可以被多个区块引用。交叉引用可以提高吞吐量，扩大规模，降低认证时间。
2. Trusted authority。一个权威中心来做最后的决定，可以减少确认时间，但是会减弱去中心化特性。
3. Pairwise vote(成对投票)。2 对 1 的投票选择，而不是正常投票算法中的 n 对 1。
4. Transaction sharding(事务分片)。将交易分配到不同的链来阻止排序过程中可能的复制和冲突。
5. PoW 机制。用作一个反恶意节点的工具，对于子序列的PoW是预先计算的，可以保证交易瞬间完成。

对常用的共识机制分析:

1. Tip selection algorithm。一个新的交易如何选择之前的交易进行确认。增加了吞吐量和规模，一定程度上降低了安全性和一致性。
2. Recursive algorithm。递归调用一个函数直到得到一个稳定值。这个算法被共识机制采用来使得无序的块聚合成一个有序的链，使系统可以在一个确定的方向扩展。
3. BFT-style consensus。分为三种
   • 传统BFT。需要根据资源确定(PoW，PoS)一个commitee,commitee成员来执行共识操作。
   • async-BA/leaderless BFT: 每个链都可以广播块和投票，当一个块得到足够的票数就可以提交，但是由于这个提交和确认是异步的，所以一个全局的线性排序很难达到。
   • 前面两种的整合。经典的拜占庭容错协议首先应用于各个独立的区域，上层协议采用async-BA实现跨区域的最终共识。
4. Nakamoto consensus and its variants （中本聪共识和它的变体）。现存最流行的方法。传统的NC选择最长的链，变体NC选择权重最大的链，多用于形成主链。
5. Sorting algorithm。按照总体的线性顺序来排序，对于确保全局一致性是必不可少的。根据一些参数来确定优先级。

特性分析

BA和NC特性

拜占庭共识和中本聪共识是最流行的两种共识协议。

拜占庭共识

在存在恶意节点的情况下可以达成的共识。有三个特性:

• argeement:
• validity:
• termination:

中本聪共识

允许所有节点可以参与共识通过PoW,PoS等方式。有两个关键特性:

• persistence:
• liveness:

安全分析

Parasite Chain Attack

尝试用预先准备好的子链来替换正确的子链。

首先攻击者参照主链来构造一个有很高可信度的子链。然后分别发送一对冲突的交易到主链和构造的私链，接下来要确保子链得到有竞争力的可信度。这时，这个冲突交易可能已经在主链上确认，攻击者再发布他的子链，这样很可能使正确的主链无效然后一个coin可能被使用两次。

这种攻击需要攻击者有充足的算力来生成区块，以没有强力领导者的协议为目标。

Balance attack / liveness attack

保持多个子图平衡增长来获取收益，攻击者在一个子图发布交易后，又在另一个子图发布交易，动态维持几个子图的平衡来获取收益。

需要一个很大算力，主要攻击基于POW的协议。

Splitting attack

类似平衡攻击，攻击者找到两个相近的分支或者子图来发送冲突交易获取利润。

攻击者需要有强大的算力，主要攻击没有强力中心的系统。

Large Weight Attack

Censorship Attack

Replay Attack

Sybi Attack