[区块链]关于DAG共识的调研

若有错误之处还请批评指正。
ps： 点击名称可直达论文或白皮书哦

前言

我之前接触过的大多是链式的结构，也就是串行化执行的区块链，链式区块链只能串行化处理交易或区块，导致现有区块链出现了一些问题，比如说效率，确定性，中心化问题，能耗问题等等,那么我们先把目光聚焦在效率问题上，最突出的表现是系统吞吐量不足。直观上看,提升区块链系统的吞吐量最简单的方法是增加区块大小或降低区块的产生间隔，但是,只通过这些参数层面的调整不能从根本上解决问题的,而且还需要进行协议架构的重新设计。

有一篇文章说公链性能瓶颈的我觉得还挺有趣的，点击here

目前提升区块链性能的主要方案有以下几类:(1) 链下支付技术;(2) Bitcoin-NG;(3) 分片技术(4) 基于有向无环图(directed acyclic graph,简称 DAG)的分布式账本技术。这次主要聚焦的是DAG技术。

why DAG ？

那么，为什么DAG技术要比串行化的区块链好一些呢？他好在哪里？我们为什么要选他作为区块链的结构

我们知道传统的串行化区块链如果同一时刻不同账本增加操作就会导致冲突，也就是分叉，以比特币为例，如果两个矿工同时提议区块,区块链就会出现短暂分叉,产生竞争.根据最长链原则,最终只有一个区块会被保留在主链上,而另一个区块被抛弃，这取决于网络中延伸哪个分叉的矿工群体最先产生下一个区块。

这种串行化带来的直接危害有 3 个方面:

(1) 每次出现冲突,必然有一个分叉最终失去竞争优势,这个区块就会成为主链外的孤块.这不仅造成产生这个区块的矿工算力上的浪费,也使得选择这个分叉的其他网络算力被浪费;

(2) 利用区块链分叉的话,理性矿工可以进行自私挖矿来产生高于自己算力占比的额外收益,着这种算力的分散显然会大幅度降低系统安全性;

(3) 为了最大程度地避免这种串行化带来的冲突,增加区块大小或减小区块产生间隔这两种直接提升区块链交易吞吐量的方法都存在限制,大区块在网络传播中会导致高时延，同样的，高区块产生率也会导致冲突概率增加.

DAG 是什么

我们来看一下DAG的定义，

图论中有向图的定义大家应该都知道，图 G 包括一个点集 V,一个边集 E.每个点集中的元素在 DAG 账本中对应一个交易或者区块,边集中的每个元素(u,v)是一个二元组,表示 u,v 两点之间的偏序关系，大多数情况下表示 u节点间接确认了 v 节点代表的内容.

DAG结构中天然形成的是一个偏序。

这就满足了有向的特性，那如何无环呢？也就是假设不存在
$$u_1,u_2,\dots \dots ,u_l,?i\in [l?1],(u_i,u_{i+1})\in E,(u_l,u_1)\in E$$
这种无环性使得 DAG 账本具有易增难删(append-only)、交易可定全序(total-orderable)的拓扑性质.当然，也可以通过一些紧致性以及其他验证方式去判断是否是DAG。

出度 out 表示该节点所做的引用数量,入度 in 表示 u 被引用的次数.如果 入度,我们称 u 为一个端节点(tip unit).

图的特性使得基于 DAG 的分布式账本规避了串行化带来的限制,无论是以区块为基本单元的 DAG 账本还是以交易为基本单元的 DAG 账本,都天然地支持并发操作，在高负载网络下,每个新加入的节点都可以同时引用相同的节点，每个新节点可以同时引用视图中多个端节点以加速 DAG 的收敛。当然，非正常情况下需要一些机制去解决冲突。

基于 DAG 的账本对可能的冲突交易采用乐观的包容策略,即对于并发产生的单元,只要其遵循基本协议规则,就可以进入账本,如果其中个别交易存在冲突,则将通过共识算法判定其合法性.这本质上是一种延后冲突解决策略,避免了区块链中网络算力资源浪费以及可扩展性限制。

tip:
DAG可以通过设计为区块排出全序，现有的DAG有些支持全序有些不支持全序。
树图结构通过引入主链和Epoch的概念，实现了对区块全序的支持，这也是Conflux有两种指针的原因。

为什么要排全序，偏序会带来什么问题？
一个区块链系统，如果只需要处理普通的转账交易，又能通过指针保证并发交易间没有因果关系，那它也许可以用偏序。
因为这种系统只需要处理加减操作，而加减操作是满足交换律和结合律的，交易的执行顺序对系统状态没有影响，系统最终的状态是一致的。
但偏序不能支持智能合约，因为智能合约是图灵完备的，它需要表达复杂的逻辑计算，它有乘法，一旦有乘法和加法就不会满足交换律了。
也就是说，两笔交易A和B，先执行A后执行B得到的状态与先执行B后执行A得到的状态是不一样的。偏序下两笔交易有可能以任意的顺序执行，那么不同的矿工就会得到不同的系统状态，就无法取得共识。
如果一条链想要支持智能合约，就要支持全序。

参考链接

常见共识机制

我会按照自己的理解比较快速的说一下如何进行共识，在这一部分我还会选择性的讲一下某些共识如何进行全序排列，以及一些简单的安全性的分析。

借鉴之前看的一篇综述的分类，将现有基于 DAG 的共识机制分为以下 3 类:

(1) 基于主干链的 DAG 共识协议,首先在 DAG 中确定主链,进而确定交易全序;

(2) 基于平行链的 DAG 共识协议,网络中各实体或实体集合分别维护一条链,链间通过相互引用构成平行链结构,实体间利用此引用关系进行共识;

(3) 基于朴素 DAG 的共识协议,除基本引用规则外无特殊限制,在 DAG 拓扑结构中利用某种投票机制进行共识。

首先可以看到主链DAG，最早的是ghost，它采用最重权重的方法来提升系统的安全性，比最长子链来说不会分散算力而导致51攻击实施难度变小，然后是Inclusive这个协议，ghost中，不是主链的部分会直接不要了，同样也会导致算力的浪费，Inclusive通过改进使所有的区块都被利用上，但是他没有给出具体的一个排序规则，Conflux就通过增加区块引用实现了全局排序，Byteball这个共识其实是借鉴了Dagcoin的思想，但是因为Dagcoin没有代码实现，在Byteball实现了之后又基于byteball做了改进。

朴素Dag这块，刚刚说Dagcoin是首个以交易为单元的DAG共识，后来IOTA因为是主要应用在物联网中的，所以把参与节点改成了物联网设备并进行相应的改进，Meshcash引入了两级共识来取消区块间的竞态条件，Avalanche是应用了随即交互式抽样来进行共识，SPECTRE他是区块为交易单元的，用投票来解决交易的冲突，但是没有办法全局定序，后来PHANTOM根据他做了改进后使得账本中得交易可以进行全局排序。

平行链DAG主要是这三个，hashgraph主要是链间随机同步，然后通过虚拟投票来进行全局的定序，Nano是链间相互引用，用投票来解决冲突，没有发现能够确定顺序的规则，dexon是改进了Algorand作为单链的共识算法，然后根据平行链之间的引用关系进行全局定序。

主链DAG共识

1. GHOST
   

首先是最早的GHOST，它针对传统区块链在高并发情况下存在的问题,利用树形 DAG 结构进行了一定的改进。之前也说过，串行区块链中，如果因为区块并发或网络同步原因导致诚实节点不能够及时收到其他节点产生的区块,而只能继续在较旧的区块上挖矿,这将导致同一区块之后出现多个诚实节点独立产生的若干个并发区块.此时,从全网的角度来看,多数诚实节点的算力被抵消或浪费(若干个并发区块中最终只有一个合法),那么在最长链原则下,恶意节点可以利用 50%以下的算力颠覆最长链,从而完成双花攻击.针对这一问题,GHOST 采用“最大权重子树”原则来选取主链,以取代比特币中的最长链原则.也就是说, GHOST 将候选区块集合及其引用关系看作一棵树，它的目标是从 T 中选择一条主链,作为最终主链.首先,对 T 中每个区块 B,记其权重为 1,最大的子树就是我选的主节点。

在这个图上，如果按最长子链的话，那么自私挖矿就攻击成功了，看其他人鹬蚌相争，渔翁得利，但是ghost下面，即使在出块速率较高的网络中,颠覆主链所需的恶意节点临界算力依旧为 50%。
but，GHOST 账本不包含主链之外区块(孤块)中的交易.这一方面造成系统算力的浪费,另一方面,系统性能也不能随着系统节点(算力)的增加而呈线性提高.为此,Inclusive 协议对其进行了改进.

2. Inclusive blockchain protocol
   

GHOST 协议下,每个区块只能引用一个父区块,账本呈树形结构,最终只有主链上的区块合法.而在Inclusive 协议中,每个区块可以同时引用若干个父区块,账本变为朴素的 DAG,并且,此 DAG 中的所有区块均被视为最终账本的一部分.而这同时带来一个问题,即并发产生的区块中可能包含重复或冲突的交易,并非所有区块中的所有交易都最终合法.对此,Inclusive协议首先在 DAG中共识主链,然后根据主链和拓扑结构对所有区块排序.区块全序确定之后,根据交易所在区块的顺序,冲突交易中优先被区块包含的被判定合法,其他视为非法,最终,所有的合法交易构成账本交易集合.但是它具体的排序算法也没有详细展开.

Inclusive 协议中,主链之外的区块也能获得挖矿及手续费奖励,这在很大程度上保护了网络中弱连接矿工的利益,避免了系统的中心化.但它同时也是一把双刃剑:即使双花攻击失败,攻击者也能获得奖励,双花攻击的代价因此减小.然后Inclusive 协议引入了奖励递减函数,非主链区块的奖励与它们被主链区块引用的速度有关,引用越“慢”,奖励越低,.另一个问题是,如果矿工在利益驱使下,均优先包含高手续费的交易,那么区块之间的交易重复率将大大增加,导致系统吞吐量并不能随着区块的增加而呈线性提高.通过博弈分析证明:矿工在产生区块时会随机选取交易进行包含,以避免因冲突而带来的交易费的损失,从而使得自己的收益最大化.

3. Conflux
   

Conflux也是继承自前两个共识，Conflux中的区块之间由多条边（Edge，连接）组成，这些边分成两类：父连接，以及引用连接。在确定主链（Pivot）的基础上，新生成的区块必须使用父连接连接到主链的最后一个区块上。除了主链外，还存在其他一些非主链的路径，新生成的区块必须使用“引用连接”连接这些非主链的最后一个区块。Conflux中组成DAG的区块会确定一条主链（Pivot Chain）。在主链确定的基础上再确定所有区块的先后顺序，Genesis是“创世纪”块，也就是第一个块。父连接用“实心”箭头表示，引用连接用“虚线”箭头表示。区块C使用“父连接”连接到A，使用“引用连接”连接到B。新生成的区块（New Block）使用“父连接”连接到H，使用“引用连接”连接到K。

要排序肯定要先选主链，它是如何选出主链的呢？

主链的选择使用“GHOST”规则，“GHOST”的基本思想是选择子节点数多的节点。确定下一个区块是根据子区块个数或者在子区块个数相等的情况下根据区块Hash。子区块个数多的，或者子区块个数相等区块Hash小的区块为主链的下一个区块。注意，子区块个数的计算不包括“引用连接”。

接下来看一下它是怎么排序的。每个主链上的区块组成一个时代（Epoch）。被该区块“连接”到的区块，且没有被之前区块“连接”的区块属于这个区块时代，Past（G，a）获取DAG图G中的主链中一个区块a之前的所有区块（包括区块a），也就是区块a之前的区块以及区块a能连接到的区块。很显然，伪代码的第5行：Past（G，a）- Past（G，a’）计算的是区块a所处时代中的所有区块，包括区块a。区块a时代的区块单独组成一个图的话，按照两个规则进行排序：
1）有没有连接关系 2）区块Hash大小。
同样以上图DAG为例，每个时代包含的区块用虚线分开。区块的排序为：Genesis，（A），（B，C），（D，F，E），（G，J，I，H），（K，New Block）。区块D只被区块E连接，所以属于区块E的时代。
排序参考链接
冲突：发生冲突的交易，第一个交易有效，后续冲突交易都无效。

4. Byteball
   
   Byteball 和其他的不一样，引入了见证人(witness)机制来实现，这里我就直接说一下它是如何选出最优父结点和稳定主链的。

首先附上一些名词解释：：

• 父单元与子单元：从单元A出发可直接到达单元B，即单元A到单元B的路径长度为1，则单元B称为单元A的父单元，单元A称为单元B的子单元。
• 直接包含：如果单元A为单位B的子单元，则单元A直接包含或者验证了单元B。（5直接验证4）
• 间接包含：如果从单元A出发到达单元B的路径长度大于1，则单元A间接包含或者验证了单元B。（5间接验证2）
• 顶端单元：不具有任何子单元的单元，也可称为无子单元或未经验证的单元。
• 创世单元：由创世交易构成的单元，不具有任何父单元。（G）

给定一条主链，与之相关的所有单元均可以在此基础上进行排序，其序号称为主链序号（MCI, Main Chain Index）。创世单元的MCI为0，依次加1直到链尾。对于不在主链上的单元，其MCI等于主链上最先包含（直接或者间接）该单元的那个单元的MCI。MCI代表了从主链视角来看单元在DAG中的总序，对于发生冲突的双花交易，MCI较小的单元为有效单元。

最优父单元的选择策略
单元级别：由当前单元出发至创世单元的最长路径长度定义为单元级别（unit level）
见证级别：从当前单元开始沿主链回溯，并对路径中不同见证人进行计数（相同见证人只计数1次），当遇到的见证人数足够多时（超过大多数的已知见证人）停止回溯；然后计算停止位置的单元级别，将其称作当前单元的见证级别（witnessed level）。

最优父单元的选择策略由以下三部分组成：
1、在选择最优父单元时，见证级别最高的父单元为最优父单元；
2、如果见证级别相同，则单元级别最低的作为最优父单元；
3、如果两者都相同，则选择单元哈希值（base64编码）更小的作为最优父单元。

并行排序时：单元级别低的优先，相同则hash小的优先

原文：Then, of the two nonserials, the one that has a lower MCI is considered to come earlier and deemed valid, while the other is invalid. If both nonserials happen to have the same MCI, there is tiebreaker rule that the unit with the lower hash value (as represented in base64 encoding) is valid.

图上加粗的是主链，其他是候选主链，圈内是主链序号，主链中节点的选择其实就是选择最优父单元的过程。最优父结点就是选路径上不重复见证节点最多的，如果见证都一样那就选单元级别低的，再一样就选区块hash小的。

关于排序，首先根据主链号，相同单元级别那就区块hash小的在前面。这个共识和前面conflux的一样，关于双花也是谁先谁有效，这里就是单元级别小的有效，也就是图上红色部分，6是有效的。

图上后面有一个主链的分叉，也就是两个候选主链，都指向了8，那么8就是稳定点，从8到初始节点的路径都是一样的。

那么8之后怎么选择主链呢？这就要用到当前见证级别了，如果某个候选主链的见证级别超过某个阈值，并且比现有的稳定点的见证级别大，那么主链会朝着这个候选主链进行扩展。

在这种结构里面会出现影子链的攻击手段，比如说这个如，下面就是别人弄出来的一个影子链，正常情况下因为影子链的见证级别比较低，肯定不会攻击成功，但是如果见证人一起合谋的话就会成功。

朴素DAG

1. Dagcoin
   

前面也说过，Dagcoin虽然先提出来，但是他先开始是没实现的，后来借鉴了Byteball的代码又改进了一下。

Dagcoin是首个以交易为基本单元的 DAG 账本,用户的交易直接进入 DAG 账本,成为其中的一个节点.DagCoin 中,用户在创建交易时需要进行一定的工作量,验证引用当前 DAG 视图中一个或多个交易,该交易发出后,经由 P2P 网络广播给其他节点,进入 DAG账本.

这里要说一下，DagCoin 中的网络节点不能直接过滤双花交易,如果双花交易之间不存在偏序,则它们就都可以被添加进 DAG 账本,之后通过共识算法判定合法性.那么,DagCoin 引入确认分数(confirmation score)机制.正常情况下,每个交易对其所直接或间接引用的交易贡献 1个单位的确认分数,但如果被引用的交易中存在冲突,则只对其中引用分数高者贡献确认分数(确认分数相同的情况下,被优先引用的交易确认分数增加).

现在图上2和3出现了交易的冲突，5这个交易就对2和3中的一个贡献确认分数，这里2和3确认分数相同，2被优先引用，那么交易5的确认分数给2，随着5后面交易越来越多，确认分数少的乙方会被确认无效，无效的乙方确认分数停止增长。

但是它也未给出交易确认所需的确认分数阈值，没有对敌手策略或安全边界进行详细分析

2. IOTA
   
   如果说byteball是从共识层面来改进Dagcoin的话，那么IOTA就是从交易确认机制方面改进的，当然，都借用了他的思想。

IOTA是一个面向物联网(IoT)的分布式账本,账本的参与节点是物联网中的设备。每笔交易只可以用引用两个。

图上绿色交易代表已经被网络以高确定性（high certainty）地确认，蓝色交易是部分确认，也就是确定性较低。灰色（以及下面的黄色）方框表示还没有任何人验证过的 tip ，就是末端这里。红色交易，表示有冲突，或无效交易.
我们可以看到新加入的交易1和2，1选择了tip w 和x，2选择了 tip z 和 y。 我们可以看到，2间接验证了黄色线的这部分，1同理。可以看到两个交易的加入不仅验证了绿色块的交易，对蓝色块的交易也有一定的验证确认。

交易 1 和 2 的验证路径有重合，我们可以看到有一些交易被确认一次，有些交易被确认两次。被当前所有 tip 验证和确认的交易就被认为是完全确认。因此，交易 n 进入 tangle 更深一层，现在变成了绿色。从现在开始，随后所有连接到 1 与/或 2 或者它的孩子，将会保持再验证和再确认的交易状态。

节点不需要看到和验证所有的交易。每个用户仅需要选择和验证两笔交易及其父交易。他们验证了 这个网络中的一部分。其他用户选择并验证不同的 tip 和路径，就是完整网络的协同验证，一旦一笔交易在比较深的位置，无论从最新的 tip 中的任意一个都会对他进行验证确认。

回到这个图上，注意交易 n 还没有被最重确认，因为现在我们的 tip 比较少

现在又加入了几个交易，现在5这个交易的验证路径没有验证n，n就会再次回到部分确认的状态。5的加入只是降低了现在区块的被确认的概率，但其实确定性概率是增加的。

假设现在有人使用了双花攻击，交易5加入进来在路径上发现了两个地方的冲突交易，为了确保它自身会是一笔有效的交易，它会重新选择 tip 直到找到不冲突的交易。可能会有更多的用户在 w 或 y 后面附加交易。在一定范围 内谁被确认的多谁就会被最重确认，另外一个会被丢弃，被丢弃的界定后面的交易会重新加入网络中。

在上面的示例中，用户可能继续与交易 5，6 和 8 相连，但是不会连接到交易 7。因此，交易 y，2，3 和 7 将永远也不会成为一个完全确认的状态。

图上的交易 y，2，3 和 7 可能被再次加入 网络。只要他们（仍然）是有效的，就会新的机会被确认。交易 2，3 和 7 可能然后被确认，但是交易 y 仍然无效。
参考链接

平行链DAG

1. Hashgraph
   

首先这里我只是简单说明一下，具体的已经有大佬写的非常清楚了，我会附上链接参考。
名词解释：

• 祖先（ancestor）：如果事件A是事件B的父亲事件，或是父亲的父亲的事件等等，又或者事件A等于事件B，那么事件A是事件B的祖先（ancestor），也就是说自己是自己的父亲事件，自己是自己的祖先事件。
• 可见：事件A可见事件B，当且仅当存在一条由A到B的路径。
• 强可见（strongly see）：事件A到事件B的所有路径经过的事件的集合S，当S中覆盖了超过2/3的共识节点，那么事件A强可见事件B。
• 见证人（witness）：每个共识节点的每一创建轮次的第一个Event。如图4中的A2、B3等。（其实叫见证人事件更好理解）。
• 创建轮次（round create）： 如果事件A强可见超过2/3的创建轮次为x的见证人,那么事件A的创建轮次为x+1，否则为事件A的祖先事件中的最大轮次。
• 著名见证人（famous witness）：通过统计投票决定，投票过程比较复杂，分为投票和统计两个过程

它通过虚拟投票的方式在基于 DAG 的账本中实现无领导拜占庭共识。Hashgraph 中,每个成员维护一条链,成员之间通过 gossip 协议进行交互.它们频繁地以随机方式从其他成员中选出一个进行信息同步,接收到同步信息的成员在本地创建一个事件（event),记录该同步历史，关于如何选取知名见证节点以及gossip具体人如何进行异步可见的过程我就不说啦。

一个 Event 的状态变迁过程是这样的：（绝对多数即2/3的节点数）

1.可见（A能回溯到先前的祖先事件B，A可见B，后续可见先前事件）
2.A强可见某祖先 Event B（当事件 A能找到事件 B 的所有路径中跨越了绝对多数的节点，那么事件 A强可见事件 B）（不同路径节点不同节点叠加）（绝对多数指2/3）
3.A强可见绝对多数节点的祖先 Events （B，C，D……）（定义轮次）
4.A轮次增加（即 Round + 1）（创建轮R，接收轮R+1）
5.大多数 R+1 轮 Witness 强可见 R 轮某个 witness（某轮创建的第一个事件为见证人），R 轮该 Witness 成为 famous witness
6.commit

一个事件Event什么时候被确认呢？当事件Event拥有共识轮次（round received）时就被确认。之前提到，Hashgraph共识的结果是事件Event的全局顺序，当Event拥有共识轮次后，使用一下排序规则进行排序：
1）共识轮次由小到大，如果相等，依次看2、3条规则。
2）共识时间戳由小到大，如果相等，看3条规则，事件x共识时间戳的计算方法：共识轮次的每一个著名见证人Y，找到一个最早的事件，此事件既是Y的祖先事件又是x的儿子事件，从这些事件集合取中位数事件的时间戳作为共识时间戳。
3）按事件签名和某随机数异或的结果由小到大排序，这个随机数通过该轮所有知名见证人的数字签名进行异或运算得到

Gossip 简单来说就是，节点随机选择一个可以连接的邻节点，向其发送一条信息（Event）。而 Gossip about Gossip 则是，收到 gossip 信息的节点，对该 gossip 信息进行签名，并且再把该签名打包进一个新的信息中，并随机发送给网络中的任一节点。这样，每个节点发出的 Gossip 信息都包含了对其收到的前一个 Gossip 信息的签名验证，实际上就是做了一个见证工作（Witnessing）。
那么虚拟投票又是怎么回事呢，实际上指的是强可见和选取知名见证人的过程。在这里就不细说了。
一旦知名见证人被确定，剩下的过程就只是各个节点把这个结果进行提交而已了。

一旦某个轮次确定了绝对多数的知名见证人，就可以为这一轮次中的其他普通事件（非 witness）确定接收轮次和共识时间戳（consensus timestamp）。

确定共识时间戳之后我们就可以进行一个全局排序了。

当然，仅有 timestamp 可能还无法确定 Event 的先后顺序，因为很有可能两个 events 会有相同的 timestamp。所以还需要一些其他条件和规则来约定顺序。

在 Hashgraph 中，是按照如下规则来排序的

• Round received
• Median timestamp
• Extended median timestamp
• whitened signature

目前,Hashgraph 的成员由全球 39 个声誉良好的组织构成,每年会有 1/3 的动态替换,但不支持节点的增删. hashgraph采用拜占庭协议，每轮的延迟为O(lnn)，这意味着它确认时间随着节点数量的增加而增加。

虚拟投票和gossip协议把通信复杂度降低到了O(n)。可以把它看成是一个支持并发出块的PBFT，同时解决了PBFT最大的痛点-通信复杂度。Hashgraph具有PBFT的100%确认的特性，POW的确认是非确定性的，即使6个块之后确认也不是100%的。Hashgraph将事件划分到不同的轮次，然后再对轮次内的事件进行排序，也就意味着事件（区块）的确认是批量的，并且需要不断得创建事件来推动确认。
Hashgraph白皮书中给出了共识算法的安全性（safety）证明，但对于活性（liveness）并没有严格的论证。Hashgraph与其他DAG共识算法都存在一个交易去重困难的问题，因为是并发出块，无法保证一笔交易只打包到一个区块中。如果认为有重复交易的区块为无效区块，那么极容易出现DDOS攻击。如果允许，把重复的后出现的交易舍弃，那么重复率没有一个去中心化的方法来保证。
参考链接

2. NANO
   
   与大多数分布式账本不同的是,Nano为每个账户维护一条链,记录该账户的所有交易历史.账户每产生一笔交易即创造一个区块,每个账户下的区块前后相继构成该账户的区块链,不同链之间通过相互引用关系构成区块点阵(block lattice).Nano 中一笔完整的转账交易由两个子交易构成——发送方产生的发送交易(send)和接收方产生的接收交易(receive).首先,发送方通过引用自己账户下最新区块创建一个发送交易,并将该区块广播.此时,相应金额已从当前账户中扣除,交易处于待接收状态.接收方收到此交易后,通过引用该发送交易以及自己账户链中的最新区块创建接收交易,此时,交易被标记为完成状态.可以看出,接收交易构成了不同账户之间的引用关系,形成 Nano的平行链 DAG 结构.

Nano 的是基于 PoS 的.用户的投票权重与其拥有的系统代币数量成正比.Nano 要求每个账户在创建之初指定自己的代表,如果系统中出现冲突,这些代表会通过基于权重的投票进行共识,每个代表的权重为选定其为代表的账户余额之和.如果某个账户的区块链出现分叉,即有两个或多个区块有相同的前驱区块,说明该用户试图双花.当检测到这种类型的双花交易后,代表们通过在自己的链中创建投票区块对双花交易进行投票,最后得票权重更高的区块被认定为合法.

由于账户余额的加法满足交换律,如果同时收到多个发送交易,接收方可以根据自己的意愿确定接收先后顺序,而无需考虑它们的竞态关系.由此,Nano 中不同链、不同用户之间可以实现独立异步更新账本而不互相干扰.但同时,这一设计也存在比较明显的缺点:由于一笔交易必须有接收交易才能完成,Nano 中需要节点在线才能完成交易的接收.

3.DEXON

DEXON 是若干条平行的区块链,每条链独立进行共识.这些平行链之间通过区块中的引用字段(ack field)进行互相确认,最终通过这些引用关系确定全局区块顺序.

DEXON 共识主要分为两个模块,一是单链共识协议,二是确定平行链间区块全序.

CRS:公共参考字串（CRS）其实是一个相比起随机预言机更为简单的假设，具体是这样的：我们假设在一个协议中，证明方与验证方都拥有一段相同的参考字串。这个字串可能是随机生成的，也可能是某个函数的输出。重要的是完成协议的两方并不知道这个字串具体是如何被生成的，就感觉像是天上掉下来的一样。在CRS假设下，一个协议的双方可以共享一段事先生成的，但是谁也不知道是怎么生成的参考字串，并且基于这个参考字串完成原本的协议。

VRF:用以完成出块节点的随机选择。

单链共识参考了algrand。但根据algrand的缺点改进了VRF。algrand的验证函数是这样的:

他的验证函数是这样的:

我们可以看到algorand的VRF是跟前一次的状态有关的，DEXON 对比algrand来说有三个好处，一个是更加公正无偏，因为它不依赖前一轮的验证；第二是验证更灵活，因为是基于马尔可夫状态的，即与前面的状态无关，任何节点只要在拿到CRS后都可以开始进行验证；第三就是空间消耗减少，未来的可能改进是在节点刚加入的时候就给定CRS，这样使得空间开销不与节点数量挂钩

每个单链有一个公证人集合，只有该集合的人能够参与拜占庭共识。还有一个单独的成员集合专门产生CRS，公证人集合有权提议一个区块和运行拜占庭共识协议选择打包哪个区块。如果公证人集合对达成的共识区块进行签名，下一个区块的提议者必须验证这个签名，并且把他们合并成一个阈值签名，这个签名存在下一个块里面，篡改区块不仅会导致hash不一样，这个签名也会改变。这两个集合的成员在每个epoch都可以重新选择，每个epoch的CRS都会重新生成，每次CRS的成员重选，就会更新CRS。他们会偏向选择计算结果小的人进行打包，如果一个节点对计算的阈值结果太大，那他在不太可能被选择的情况下就会放弃竞争，如果所有块都放弃也没关系，所有节点可以对一个空块达成一致。

针对平行链间的区块顺序,DEXON 设计了一套排序机制,能够基于平行链区块间的引用关系确定区块全序,并计算出每一个区块的无偏时间戳.

已被单链共识产生的区块分为两种状态:已排序区块和待排序区块.其中,已排序区块是指已经被排序算法输出并定序的区块,其余为待排序区块.

候选区块就是直接引用的所有区块都已被定序了.在单链情况下，被先引用的就是在这条链上优先，如果在平行链中绝大多数都认为这个候选区块优先，那他就被称为优先候选区块.

每当因接收到新区块而导致 DAG 拓扑发生变化时,如果候选区块集合满足内部稳定与外部稳定两个性质, DEXON 全局排序算法将从候选区块中输出所有优先候选区块,将这些区块根据哈希排序并输出到已排序区块队列.

这里,内部稳定性是指在候选区块集合内部,优先候选区块要“足够”优先于其他非优先候选区块;

外部稳定性是指无论后续收到任何新区块,优先候选区块的优先级也相对更高.当一个区块被确定全序之后,取每一条平行链(假设共 n 条)上排序在该区块之前的最后一个区块,以这 n 个区块时间戳的中值作为该区块的无偏时间戳.

大家还可以再去了解一下Algorand

问题与挑战

1：交易时长不可控。DAG的验证规则是后面的交易验证前面的交易，这就很容易出现最后的交易迟迟无法被验证的情况，尤其是在整个网络发展的初期节点数量比较少的情况下，造成交易时长无法预测。当然，解决方法也是有的，但是不管是见证人还是其他超级节点机制，都在一定程度上违背了去中心化。
2：不支持强一致性。DAG作为一种谣言传播算法，其异步通讯机制在提高了扩展性的同时也带来了一致性的不可控问题。区块链是同步操作的验证机制，能够保证较高的一致性。但是DAG作为异步操作，它不存在一个全局的排序机制，在运行智能合约时，这就很可能会出现节点间所存储的数据在运行一段时间以后出现偏差的情况。
3:安全性还没有得到大规模的验证。DAG技术并不新鲜，但是应用到去中心化账本领域确是近些年的事情。他没有像比特币那般经历过长达10年的安全验证。这是他目前大规模的部署DAPP的最大障碍。针对现有方案的安全性分析甚至更为通用的安全性证明框架亟待深入研究。
4：每个 DAG 账本都会对新单元设置基本准入规则,如某交易加入后账本拓扑仍需满足 DAG性质,或新单元加入后账本拓扑依然满足紧致性等。前者可以通过验证新加入单元的所有引用单元是否已经出现在 DAG 账本中来解决;但后者的判断则要困难得多,尤其是考虑到在高并发情况下需要对每个新加入的单元验证其是否满足该约束,节点的处理开销非常高,极端情况下甚至会影响系统的并发性.

参考综述