EN
原文来源：Amber Group
在过去十年中，区块链已成为分布式账本技术的一种主要形式。虽然区块链目前仍占据主导地位，但其存在固有的可扩展性问题，因此有越来越多的项目正在提出替代性解决方案。其中之一便是 DAG（有向无环图），作为比传统区块链更有效的解决方案，DAG 已被许多替代性 L1 所推崇。然而，在 web3 领域中，对于 DAG 到底是什么、以及它与现有区块链技术有什么区别，仍存在很多困惑。本研究报告旨在通过详解 DAG 的工作原理及其在加密领域的应用，向读者介绍使用 DAG 技术的替代性 L1 ，同时对 DAG 技术的不同用途进行分类，并普及 DAG 相关知识。
“DAG” 到底是什么意思 ？
“DAG” 是 “Directed Acyclic Graph （ 有向无环图 ） ” 的首字母缩写。对于不熟悉计算机科学的人来说，这可能是一个拗口的名词，因此我们对每个单词进行如下详解：
- Directed （有向）：该数据结构的数据只向一个方向传输
- Acyclic （非循环的）：在数据结构上不能从当前状态返回到之前的状态，即 “ 非循环的 ”
- Graph （图）：在数据结构可视化下，该结构显示为多个顶点之间相互关联的一组关系
DAG 结构究竟是什么样的？检查数据的排序方式是确定数据结构究竟是 DAG 还是区块链的最佳方法。这种排序方式是指如何及时地对交易进行排序。因为我们理解时间是线性的，所以我们通常会认为事件也是按照特定顺序发生的。人类认同时间这一概念，因此我们也认同事件是按顺序发生的。
上图是 “ 全序 ” 的一个例子。当确定了哪个事件先发生之后，所有事件都将有确切的顺序。在一组全序的事件中，我们会确切地知道每个事件在全序中的位置。如图使用全序时，事件 A 首先出现，然后是事件 B ，再然后是事件 C 。这就是事件在区块链中的记录方式。
然而，分布式账本的全序可能会在吞吐量和延迟方面限制可扩展性。可以通过 “ 偏序 ” 账本来解决部分问题。在偏序中，每个事件相对于所有其他事件的确切顺序是未知的。相反，只有相关事件的顺序是已知的。我们不确定所有事件的顺序，但我们可以确定相互依赖的事件之间的顺序。
例如，我们可以确定事件 B 发生在事件 C 之前。但是，在偏序系统中，我们不确定事件 A 何时发生。事件 A 可能发生在这些事件之前、或者之后、甚至之间。事件 A 与其他事件无关。
通常来讲，为什么我们想知道这些交易是如何排序的？因为我们想知道一个事件是如何导致另一个事件发生的。偏序没有时间概念，所以在不清楚每个事件发生时间的前提下，我们如何对事件进行排序呢？
“ 因果序 ” 是该问题的解决方法。因果序是一种偏序，其不考虑事件发生的时间，而只考虑事件之间的因果关系。只要我们可以确定哪些事件导致了其他事件，我们便可以对这些事件进行排序。
上图是一个因果序的例子。上图中的事件没有时间戳，所以无法确定这些事件的确切发生时间。但是，我们可以看到 A 导致 B 发生，而 B 导致 C 和 E 发生。然后可以得出 A 最终导致 D 和 F 发生。因为 C 引起了 D ， E 引起了 F ，所以我们可以确定 C 和 D 以及 E 和 F 的因果顺序。但是，我们不需要确定 C 和 E 或 C 和 F 的顺序 , 也不需要确定 E 相对于 C 或 D 的顺序。并非所有事件都是偏序并且彼此之间都有因果关系，但这并无大碍，因为不相关的事件不需要相对于彼此进行排序。
通过使用因果序，我们将不再受限于类似 “ 事件链 ” 的结构，因此将能够构建 DAG 结构。彼此无关的事件根本不需要排序。交易呈因果序的分布式账本结构为 DAG ，而全序的账本结构为区块链。由于因果序允许某些交易完全跳过排序，因此与基于区块链的账本相比，基于 DAG 的账本在吞吐量和延迟方面有可扩展性优势。
现在，许多 Layer 1 都鼓吹 DAG 技术是他们架构设计中的差异化因素之一，但并非所有人都使用 DAG 来实现因果序。遗憾的是，现在还没有一个框架能够对 DAG 架构进行分类。出于本文的研究目的，我们将找出是什么真正构成 DAG Layer 1 ，并尝试根据交易的排序方式将相关项目分为两类。首先，我们将探讨使用 DAG 来处理交易，但其账本是全序的 Layer 1 。然后，我们将探讨账本是因果序的同时，使用 DAG 结构存储事件和交易的 Layer 1 。有些协议使用基于 DAG 的账本，而有些则只在交易处理中部分使用 DAG ，区分这两类协议非常重要，因为后者可能不会像前者一样提升交易吞吐量。
使用 DAG 的区块链
全序的区块链是如何运用 DAG 的？
Fantom 是一个利用 DAG 的区块链例子， DAG 用来加速其共识协议，同时以传统的、全序的区块链结构输出结果。如果一个区块链声称自己是基于 DAG 的，那么通常情况下， Layer 1 使用的是基于 DAG 的共识机制，而非基于 DAG 的账本。
Fantom ：利用 DAG 技术并且基于 Gossip 协议的区块链
Fantom 的共识协议 Lachesis 整合在一个基于 DAG 的结构上，称为 Opera 链。 Opera 链的网络由节点组成，这些节点是运行 Fantom 软件的计算机。构建 Fantom 共识机制的块被称为 “ 事件块 ” 。 Fantom 的 “ 块 ” 与我们通常所说的 “ 区块 ” 有所不同。
在高层次上，节点创建事件块，这些事件块形成一个 DAG 。 Fantom 使用这个事件块的 DAG 并生成一条区块链（一条确认块的链）。
Fantom 将数据存储在事件块中，其中包含财务、技术和其他信息。事件块是由单个节点创建的数据结构，用于全网共享交易及用户信息。在上图中，我们看到的是一个 DAG 结构，圆形代表节点，事件块由节点生成。在上图中没有表现出来，其实每个节点都在生成事件块。每当节点交换交易信息时，都会创建一个新的共享事件块。事件块会在整个网络中共享。当一个事件块与另一个事件块通信时，被通信的事件块会存储前一个事件块的交易信息，然后创建一个新的事件块。随后将此信息传递给下一个事件块。交易信息被 hash ，每个事件块包含一个或多个先前事件块的哈希值。这会使数据不可变，因为在不更改哈希值的情况下无法修改或删除先前的事件块。
如上图， Opera 链 DAG 结构中的绿色区域是事件块，它们相互通信，直到找到一个被称作 “Clotho” 块的事件块（上图中的蓝色块）。 Clotho 块包含一个 “ 标记表 ” ，这是一种数据结构，用于保存特定事件块之间的所有连接数据。要想被认定为 Clotho 块， Clotho 必须与先前设置的事件块具有 2/3 以上的超多数连接。 Clotho 块通过标记表数据结构来与 DAG 结构中的其他 Clotho 块进行通信。
根据彼此之间的通信信息， Clotho 块之间达成共识来创建另一个事件块，称之为 “Atropos” 块（上图中的绿色块）。每个 Clotho 块在创建时都有一个特定的时间戳。如果所有节点中至少 2/3 的节点时间相同，则 Clotho 块将成为 Atropos 块。这些 Atropos 块串联在一起构成 “ 主链 ” 。主链可以看作是 DAG 结构中的区块链。每个 Atropos 块都与其他 Atropos 块相连接，共享从 Clothos 块收集来的信息，而 Clothos 块的信息又来自所有其他事件块。
该主链包含所有事件的全序。所有参与节点都有一份主链的副本，并且可以在 Lachesis 共识协议中搜索自己区块的历史位置。节点不需要存储每个事件块的所有信息，只需参考主链即可。这让系统能快速访问先前事件。
因为 智能合约 通常需要将与之交互的所有交易进行排序才能正常运行，而 DAG 不会记录准确的交易时间并且只对部分交易进行排序，所以这会使大多数 DAG 协议无法与智能合约结合，理解这一点非常重要。从 IOTA 和 Avalanche 的 X-Chain 中也能够看出这点。相比之下， Opera 链的架构允许记录交易的准确时间以及对交易进行排序。然而，虽然 Fantom 的 Opera 链与以太坊主链相比确实提升了交易吞吐量，但是却无法达到与其他因果序 DAG 同等的延迟和吞吐量。这是因为 Fantom 的 Opera 链使用的以太坊虚拟机 (EVM) 限制了其性能。 Fantom 的 Opera 链通过允许 Cosmos SDK 构建在 Lachesis 协议上而非 EVM 上，实现打破部分瓶颈。未来， Fantom 计划打造 Fantom 虚拟机 (FVM) ，这将进一步改善可扩展性。自 Fantom 崛起以来，以太坊上已经构建了一些新的 Layer 2 扩展解决方案。 Fantom 的 EVM 层在这一波新的扩展解决方案中逐渐失去了意义，因此 Fantom 在现有解决方案下通过开发 FVM 来实现超越限制是有道理的。
具有因果序输出的 DAG
大多数人说的 “DAG” 实际上指的是一个因果序分布式账本。这些 DAG 是如何工作的，它们与相对的全序有什么区别？ Avalanche 的 X-Chain 、 IOTA 和 Sui 是具有因果序分布式账本的例子。
Avalanche X-Chain ，一个基于 UTXO 的 DAG 。
比特币引入了未花费交易输出（ UTXO ）模型来记录 钱包 之间的转账状态。每个 UTXO 都是一个所有权链，所有者签署交易后便将 UTXO 所有权转移至新所有者的地址。在 UTXO 的背景下，比特币应被描述为区块链，而 Avalanche 的 X-Chain 应被描述为 DAG 。 X-Chain 使用因果序的 Avalanche 共识协议。当你向某人发送 AVAX 时，你就在使用 X-Chain 。要了解 Avalanche 的 DAG 是如何工作的，首先需要知道 Avalanche 的 DAG 结构是如何形成的。
Avalanche 共识分为四个主要阶段： Slush 、 Snowflake 、 Snowball 和 Avalanche 。最后阶段与 Avalanche 共识相对的是 Snowman 共识，我们将在后面对此进行探讨。我们先来看看 Slush 共识是如何运作的。 Avalanche 网络由许多节点组成。每个节点具有三种状态：无状态、真和假。下面我们更直观地分别用颜色来表示：无色、蓝色和红色。
每个节点一开始都是无色的，在此面临投票决定真或假（蓝色或红色）。一旦选择了一种颜色，该节点就会与网络中的众多其他节点进行通信。如果这些节点还没有颜色，它们将采用与该节点相同的颜色。如果大多数节点具有相同的颜色，则原始节点将保持该投票结果。如果大多数节点是不同的颜色，则原始节点会将其投票结果反转为该颜色。
节点之间将进行多轮通信，直到所有节点达成共识。目标是让每个节点在颜色上形成一致。当节点倾向于某个颜色时，这将加强该倾向并将正确结果导向于该颜色。这个概念是 Avalanche 的构建基础，一切都建立于此概念之上。
Avalanche 的第二个构成部分是 Snowflake 协议。在节点导入内存时，每个节点都有一个计数器。每当进行 Slush 协议通信返回相同颜色时，计数器都会加 1 。而每当节点反转结果返回不同颜色时，计数器都会重置。一旦计数器达到足够大的数字时，它将锁定其状态并防止节点改变颜色。这将有助于巩固真实的颜色。
节点在第三个阶段 Snowball 协议中将以更大的内存记录数值。 Snowball 协议在 Snowflake 协议的基础上增加了置信度。 Snowflake 协议的节点不是根据与之通信的其他节点来改变颜色的，而是通过回顾自身所有的颜色变化历史，并根据节点的置信度状态来改变颜色，置信度考量了该节点的投票变化历史数据。
以上所有阶段最终导向 Avalanche 协议。 Avalanche 是一个仅能添加（将交易添加到之前的交易上）的 DAG 结构。 Avalanche 也可以在没有 DAG 结构的情况下运行，比如 Avalanche 在合约链 (C-Chain) 和平台链 (P-Chain) 上的线性结构即是这种情况。 Avalanche 共识的开发团队 Team Rocket 认为 DAG 架构优于区块链，因为 DAG 架构每个交易的投票都联动其添加的所有交易，所以 DAG 的投票机制更有效率。
Avalanche 共识由多个 Snowball 事件组成，以此将所有已知交易构建成动态 DAG—— 每个 Snowball 事件都是图中的一个顶点。顶点类似线性区块链中的一个个区块。它包含其父代的哈希值，以及一系列交易的列表。 Avalanche 共识建立在 Snowball 的基础上，置信度的概念依然有效，只不过是应用于 DAG 的各个节点上。与之前讨论的红蓝决策不同， Avalanche 共识中的节点会判断一笔交易是否正确或是否与其他交易冲突，并彼此达成共识。每个交易都链接在一个父交易上，所有父交易都链接回一个创世顶点上。一个交易下可以有子交易，子交易与其所有的父交易相链接。因为需要一个交易作为所有其他交易的基础（ IOTA 也有一个创世顶点），所以 Avalanche 需要一个创世顶点；创世顶点很重要，因为只支持添加操作的交易都需要一个添加主体。但是，如果直接将 Snowball 应用于节点构成的 DAG 上，这会引发一个尚未解决的问题，这就是交易冲突或双花。因此 Avalanche 在 Snowball 的基础上添加了 “chit” 这一概念。当置信度达到阈值时，将一个称为 chit 的计数器添加到交易中，并赋值 “1” 。如果没有赋值，则 chit 计数器为 “0” 。该节点将计算 chit 值的总和作为额外的置信设置，类似于 Snowball 的置信度。然后节点使用 chit 的总和来确定某个交易的置信度，及其所有子交易（添加到节点上的新交易）的置信度。
Avalanche 能够整合 Slush 、 Snowflake 和 Snowball 并将它们调整为线性链。这样做是为了与 Avalanche 共识并行的 Snowman 共识，这两者完全不同。不同于 Avalanche 的 UTXO 模型， Snowman 共识是基于账户的。 Snowman 共识用于 Avalanche 网络的平台链（ P-chain ）和合约链（ C-chain ）。该协议原理与上述相同，但每个顶点只有一个父节点而不是多个父节点。因此所有顶点形成全序。这也使整体结构呈现为区块链，而不是 DAG 。这对于需要知道交易先后顺序的应用程序来说非常有用，并且 Snowman 共识还支持智能合约。
Avalanche 共识协议用在 货币 转账上表现惊人，并且还可以应用于各种其他协议。在硬 分叉 至其自有项目 Bitcoin ABC 之前， Avalanche 曾被用作比特币现金的预共识机制。 Avalanche 的 DAG 结构提升了交易速度，同时因为比特币现金不需要智能合约，所以 DAG 不兼容智能合约的缺陷对此也毫无影响。在支付领域中， Avalanche 能够忽略智能合约的需求，只强调基于 DAG 的账本如何能更有效地扩展功能。
IOTA ，使用工作量证明且基于交易的 DAG
IOTA 的因果序结构被称为 Tangle ，这是一个并行处理交易的网络。 Tangle 是 IOTA 构成 DAG 的数据结构。 IOTA 的 tangle 包含交易，其中每笔交易在图中表示为一个顶点。当一笔新交易加入 Tangle 时，它 会选取两个先前的交易来批准，并将两个新链接添加到图中。
在下图中，交易 G 批准了交易 E 和 F 。交易包含诸如 “Alice 给了 Bob 十个 IOTA 币 ” 之类的信息。未经批准的交易被称为 “tip” 。交易 G 就是一个 tip ，因为它尚未被批准。每个新加入的交易都需要链接两个待批准的 tip 。有一些策略来帮助选择 tip ，但最简单的是随机选择两个 tip 来批准。对于新交易来讲，选择 tip 来批准的过程极具可扩展性。
红色交易 I 和 G 是未经批准的 tip ，因为它们没有与任何其他交易相关联。其他所有交易都已被批准，因为每个交易都有与之相链接的其他交易。
同时， IOTA 导入了权重，这是加强 IOTA DAG 架构的重要概念。我们如何知道交易是否可信？在典型的区块链中，通常会看到区块链的确认量。 IOTA 通过查看交易权重来实现类似功能。
交易的权重代表节点为创建该 交易所 做的工作量。每笔交易都有一个初始权重，权重值可以是 1 、 3 、 9 等（ n 的三次方）。较高的权重说明节点在交易上花费了更多工作。每笔交易还有一个累积权重；这是其自身权重加上直接或间接批准它的所有交易的权重值总和。让我们深入了解一下该机制的工作原理。
每笔交易都有自己的权重，同时每当一个 tip 添加到 tangle 上时，累积权重都会增加。
上图中，我们可以看到交易 D 直接由交易 E 和 H 批准，同时也间接由 G 和 I 批准。因此 D 的累积权重为 3+1+3+1+1=9 ，即其自身权重加上 E 、 H 、 G 和 I 的权重之和。
累积权重较大的交易比累积权重较小的交易更重要。每个添加到 tangle 中的新交易都会通过自身交易的权重来增加前面交易的累积权重。随着时间的推移，较旧的交易变得越来越重要。因为我们可以认为没有实体能够在短时间内生成具有足够大权重的交易，因此使用累积权重能够避免垃圾交易攻击及其他载体的攻击。
类似于 Avalanche 的 X-Chain ，这种方法虽然具有高度可扩展性，但几乎不可能集成智能合约。因此为了与其他智能合约链竞争， IOTA 正在上线一个单独的智能合约层，称为 “Assembly” 。 Assembly 是一个全序的 Layer 2 ，旨在支持 EVM 和 WASM 智能合约。
Sui ，使用权益证明的智能合约 DAG
虽然 Sui 在本报告中被归类为因果序，但实际上 Sui 同时使用了全序和因果序。 Sui 的交易处理架构可以看成是两部分：一部分是全序的、按顺序执行的依赖交易，另一部分是因果序的、并行执行的独立交易。依赖交易使用 Sui 的 Narwhal 和 Bullshark 协议。 Narwhal 是基于 DAG 的内存池，而 Bullshark 是一个共识协议，与 Narwhal 集成以达成共识。依赖交易只需与它们所关联的其他交易按顺序执行。但是，在交易完全独立时， Sui 采用另一种方法。对于独立交易， Sui 不使用 Narwhal 和 Bullshark ，而使用一种称为拜占庭一致广播 (BCB) 的方法。该方法不需要全局共识，因此几乎可以瞬间处理交易并写入账本。
大多数分布式账本都以地址为中心，而 Sui 的账本则以 “ 对象 ” 为中心。对象可以是 NFT 、 dapp 、代币，或者基本上你可以在传统区块链上构建为智能合约的任何东西。每个对象都有一个 “ 所有者 ” 属性，该属性指定谁可以与该对象交互。一个对象可以有四种不同类型的所有权。第一种是由一个地址拥有的对象，这样用户可以在 Sui 上拥有一些东西，比如在钱包里持有代币。第二种所有权是由另一个对象拥有的对象，例如在一个多重签名智能合约（对象）内持有的代币（对象）。第三种所有权是不可变的对象，本质上没有所有者。没有人可以更改不可变对象，但任何人都可以与之交互。第四种也是最后一种所有权是共享的对象。任何人都可以读取或写入共享对象，例如 AMM 。
无论交易如何排序，所有交易都在同一个网络上并行处理。
交易只是针对某个对象的具体实例进行简单地元数据更改，交易将对象作为输入，并读取、写入或改变这些输入的对象，以生成新创建或更新的对象作为输出。每个对象都知道产出它的上一个对象的哈希值。
对象要么适合 Sui 的全序共识架构，要么适合 Sui 的因果序共识架构。共享对象的交易必须是全序的，因为任何用户的交易都会更改他们正在交互的对象，因此交易排序很重要。但是，如果一个对象由一个地址拥有，那么只有该地址才能够在交易中更改对象。因此，写入此种对象的交易是独立的，这也就意味着它可以使用拜占庭一致广播。虽然 Narwhal 和 Bullshark 的结合构建出了快速响应的共识架构，但 BCB 几乎是瞬时的。
Sui 的账本是一个 “ 对象存储库 ” 或 “ 对象池 ” ，其数据存储在 DAG 中。例如，发送 USDC 这一行为是更新一个对象的 “ 所有者 ” 属性的行为，这不会对其他对象产生影响。
Sui 的账本是一个 “ 对象存储库 ” 或 “ 对象池 ” ，其数据存储在 DAG 中。在这个 DAG 中，节点是对象，而图中的每个箭头代表一个交易，该交易更新给定对象的属性。此图中未表现出来的是创世交易，它不接受任何输入并且生成的对象处于系统初始状态。
虽然其他具有 DAG 结构的分布式账本都无法集成智能合约，但 Sui 似乎已经用一种创新的方法扫清了障碍。 Sui 的智能合约语言 Move 支持将对象进行分类以及并行执行 Sui 的交易。如果没有 Move ， Sui 的智能合约架构可能无法实现。
关键要点
就速度和吞吐量而言，交易的因果序似乎比全序更有优势。然而，当尝试创建的应用程序需要严格按时间排序时，缺乏排序的因果序就会产生问题，并且许多项目无法在其 DAG 架构上正确地运行智能合约。 Fantom 类似区块链结构的全序架构支持 EVM 和智能合约。尽管 Fantom 具有全序输出，但开发人员依然找到了方法来优化 DAG 共识机制下的 Layer 1 。 Avalanche 则选择了不同的方法，其创建了一个单独的共识机制 Snowman 来支持 EVM 和智能合约的便捷开发。 IOTA 也选择了另一种方法，其正在创建框架来实现在 IOTA 上轻松部署区块链实例，以此来支持 EVM ，从而有效地创建全序的 Layer 2 基础设施。 Sui 的独特设计很有前景，交易既可以是全序的，也可以根据需要采用因果序，兼容智能合约的同时，还能够减少延迟。
Sui 是最新基于 DAG 的 Layer 1 ，但 Sui 实现了差异化并且对先前架构的缺陷进行了改进，因此 Sui 实现了让 DAG 真正成为分布式账本的一种结构。即便因果序交易不会成为未来主流，但基于 DAG 的技术也有助于扩展现有区块链。虽然 DAG 作为一种扩展方法未必在所有应用场景下都是最佳选择，但在 Avalanche 的 X-Chain 和 IOTA 上， DAG 在延迟和吞吐量方面看起来表现出色。
然而，不支持智能合约的缺陷让 DAG 在当前的竞争中处于劣势，特别是现在市场流行 Layer 2 汇总和链下零知识扩展解决方案。虽然大多数基于 DAG 的账本的确能够在较少损失去中心化性的同时降低延迟，但作为分布式账本的区块链和 DAG 都需要网络上的每个节点参与处理每笔交易。为了实现完全可扩展性，这是所有分布式账本都需要解决的最大问题之一。 Sui 通过独特的 BCB 设计来解决这个问题，它允许交易跳过共识。但这并不是每个基于 DAG 的架构都需要解决的关键问题，也不应该以此为据宣称所有基于 DAG 的架构都优于基于区块链的架构。归根结底， DAG 只是一种数据结构，我们也只是正在看到它在分布式账本技术中的应用。 Sui 的 Mysten Labs 目前正在与 Layer 1 区块链 Celo 合作，将 Narwhal 架构应用到其内存池中。 Narwhal 是一种具有 DAG 结构的内存池协议。 Celo 作为账本具有区块链结构，但它利用 DAG 作为其后端组件来实现性能改进。通过更先进的扩展解决方案，在 DAG 与区块链之间的斟酌或将变得不再有意义。本文的目的是让读者了解现有架构。类似 DAG 在 Narwhal 上的应用将是未来 DAG 的主要应用场景。虽然我们无法预测 DAG 在分布式账本领域的应用范围，但 DAG 作为一项技术，它的影响必将日益扩大。
关于作者
本文作者 Robert McTague 在 Amber Group 生态基金担任 投资 助理，该基金是 Amber Group 的加密行业早期风险基金。他取得了电气工程学士学位，在加入 Amber 之前曾在一家 DeFi 公司工作，专注于帮助公司业务发展。在学习之余，他热衷于开发智能合约和研究 web3 整体框架。
免责声明
本文所载的资料（ “资料”）供参考之用，属摘要形式，并不完备。该等资料不是、也无意作为出售或购买任何证券或产品的要约或要约邀请。该等资料并未提供，亦不应视为提供投资建议。
该等资料并不考虑任何潜在投资者的特定投资目标、财务状况或特殊需要。对于 “资料”的公正性、正确性、准确性、合理性或完整性，不作任何明示或暗示的承诺或保证。我们不承诺更新该资料。潜在投资者不应将其视为自己判断或研究的替代品。潜在投资者应在其认为必要的范围内，咨询自己的法律、监管、税务、商业、投资、财务和会计方面的顾问，并根据自己的判断和顾问的建议做出任何投资决定。
原文链接
