这是即将推出的系列文章中的第一篇，旨在解释 Aptos Labs 开发的基于 DAG 的共识算法。从第一篇开始——DAG Rider，它由 Idit Keidar、Eleftherios Kokoris-Kogias、Oded Naor 和 Alexander Spiegelman 于 2021 年提出。
DAG Rider 基于拜占庭原子广播问题，使用异步通信模型。它受到当时最新的异步协议 VABA 和 DUMBO 的启发，这些协议展示了以下特性：最优的容错能力、期望线性时间复杂度，以及最优的摊销线性通信复杂度（对于 Dumbo 来说，这是通过批处理技术将 VABA 的二次通信复杂度转化为线性通信复杂度实现的，而这种方法我们也将在 DAG Rider 中看到）。
在深入探讨协议的设计和运行机制之前，让我们先讨论一下其结构的一些关键特性：
- 无签名
- 无需非对称加密假设
- 抗量子安全
通过使用基于阈值的确定性币实现，并结合信息理论协议保证，我们实现了上述特性。
DAG Rider 由两层构成：通信层和零开销排序层。在通信层，节点可靠地广播它们的提议，并根据这些传递的消息形成一个DAG。DAG 以轮次传播，使得每个节点在每轮最多可以提议一个区块，并且每个区块引用了上一轮中 2f+1 个节点的提议。节点只有在看到至少 2f+1 个其他节点的提议后，才能进入下一轮。排序层不需要额外的交互或通信，因为提议者可以确定性地排序它们的本地DAG，并且最终会收敛到相同的DAG。
注意：这里的 f 表示协议可以处理的最大拜占庭节点数，而 n 是总节点数，且 n = 3f+1。
DAG Rider 使用了 Cachin 和 Tessaro 的异步可验证信息分发可靠广播协议，从而实现了摊销通信复杂度为 O(n)，并且期望的时间复杂度为常数，即 O(1)。为了实现最优的线性摊销通信复杂度，我们将 nlog(n) 条消息批量处理在一起。附图提供了不同可靠广播和批处理情况下的通信复杂度比较。
DAG Rider 常因其优雅性而受到赞扬，正如原始论文中所强调的——通信层和排序层之间有清晰的模块化分离，通过不同的可靠广播抽象实例化提供了具有不同权衡的协议，并且排序逻辑简单而复杂，整个排序逻辑的伪代码少于 30 行。
接下来，让我们深入探讨协议的两个构建模块：
我们利用了高效的 gossip 协议，这些协议以概率 1 满足活跃性要求。可靠广播满足以下几个属性：
a. 一致性（Agreement）——如果一个诚实节点传递了一个广播消息，那么其他所有诚实节点也会以概率 1 接收到该消息。
b. 完整性（Integrity）——对于任何轮次 r，一个诚实节点 p 至多只会传递来自节点 k 的广播消息一次，无论消息内容如何。
c. 有效性（Validity）——如果一个诚实节点 p 广播了消息 m，那么每个诚实节点最终都会以概率 1 接收到该消息 m。
以上三个属性将在文章中多次提到。
全局完美随机数抽象允许我们选择一个领导者，同时保证对手无法提前得知领导者的身份。这是通过以下方法实现的：
在实现 PKI（公钥基础设施）的基础上，结合门限签名方案，门限值设为 (f+1) -of- n，其中 n = 3f+1。门限签名方案确保领导者在至少 f+1 个节点调用了函数 choose_leader(w) 之前不会被揭示，这里的 w 表示函数的第 w 次实例化，我们将在后文看到，(w) 代表波次编号。
a. 一致性（Agreement）
如果两个诚实节点分别独立地对同一实例调用 choose_leader(w)，并分别返回 (p_1) 和 (p_2)，则 (p_1 = p_2)。
b. 终止性（Termination）
如果至少有 (f+1) 个节点调用了 choose_leader(w) 函数，则该函数最终必须返回一个值，即当达到门限时，必须选择一个有效的节点作为领导者。
c. 不可预测性（Unpredictability）
在门限签名完成之前，choose_leader(w) 的返回值必须与随机值无法区分，即除了以可忽略的概率外，对手无法在门限达到之前预测领导者的身份。
d. 公平性（Fairness）
随机数是公平的，即每个节点被选为领导者的概率相等（等可能性）。
全序性（Total Order）
全序性意味着所有诚实节点必须对所有提议的消息具有相同的顺序。
DAG Rider 还满足链质量（Chain Quality）属性：
即，对于所有已排序消息前缀的大小为 (2𝑓+1)𝑟(𝑟 ∈ ℕ），至少有 (𝑓+1)𝑟 的消息是由诚实节点广播的。
让我们按照论文的内容进行，定义一个抽象的DAG结构，并通过一些改变将其转化为我们的DAG Rider。这一抽象DAG构成了我们的通信层。提议的消息表示为DAG的顶点，而指向上一轮消息的引用则作为DAG的边。对于不同的节点来说，DAG可能看起来不同，但由于可靠广播机制，我们能够防止节点之间的分歧，保证它们的视图最终会收敛。对于节点 p ，其DAG表示为一个数组 DAG_p[]，其中 DAG_p[r]，r
让我们分析一下出边，也就是指向上一轮提议的引用。出边分为两种：强边和弱边。强边指向的是上一轮的顶点，即轮次 r-1 中的顶点，而弱边则指向的是轮次 r' < r-1 中的顶点，且这些顶点之间没有其他路径。强边提供了一致性保证，而弱边提供了有效性，并确保最终所有的顶点都能包含在全序中。
当可靠广播传递提议消息时，其他节点可以验证以下内容：
- 消息的轮次 r，
- 消息的来源节点，
- 消息是否具有指向上一轮 r-1 中 2f+1 个顶点的强边。
如果所有验证都通过，该提议将被添加到一个缓冲区中。每个节点会不断检查其缓冲区，看看是否有可以添加到其本地DAG[]的顶点。只有在该顶点的所有强边（指向 DAG[r-1] 的顶点）或弱边（没有直接路径且是在轮次 r' < r-1 中提议的顶点）所指向的顶点已添加到 DAG}[] 后，才能将该顶点添加到 DAG[] 中。
注意：即使节点已经进入了更晚的轮次，仍然可以将顶点添加到 DAG[]中，但对此类顶点只能形成弱边。
DAG Rider 以“波次”传播。每个波次由 4 个轮次组成，第 w 波次的第 1 轮领导者通过该波次第 4 轮中的全局完美随机数选出。这个领导者是随机选择的，并作为第 w 波次的领导者。
一旦领导者的序列确定后，对于每个节点都是一致的（无分歧，全局完美随机数是确定性的）。通过这些领导者的因果历史，我们可以确定性地为所有顶点排序。
由于节点在观察到 2f+1 个提议后（总共有 3f+1 个提议）才进入下一轮，因此它们可能会在完成该波次后才观察到领导者。在这种情况下，该节点不会为该波次提交任何领导者，只是直接进入下一波次。但某些其他诚实节点可能会观察到领导者并将其提交到本地的 DAG 中。为了确保一致性，我们必须保证所有诚实节点最终都会提交该顶点。
为此，我们利用强边的特性：如果在后续轮次中，当节点 p 提交顶点 v 作为波次 w 的领导者，并观察到从 v 到 v' 存在一条强边，而 v' 是某个波次 w' ( w' < w ）的未提交领导者，则节点 p 会将 v' 提交到其本地 DAG 中，并将其排序在 v 之前。
因此，通过这一提交规则确保了一致性：如果一个诚实节点在某个波次中提交了领导者 v，那么由于从后续波次的领导者到 v 存在强路径，所有诚实节点最终都会提交 v。
提交规则（Commit Rule）：
为了一个领导者能够被提交，必须至少有 2f+1 个节点在该波次的第四轮中为其形成强路径。如果没有达到这一条件，该领导者在该波次中无法被提交，必须等待后续波次中有领导者被提交，并且从后续波次的领导者到该领导者存在强路径。
这一规则通过下图进行了说明：
在这里， v2 和 v3 分别是波次 2 和波次 3 的随机选择领导者。由于 v2 没有来自波次 2 第 4 轮至少 2f+1 个顶点的强路径（这里至少需要 3 个），它无法被提交，必须等待领导者顶点 v3 来观察从 v3 到 v2 的强路径。
该协议保证，对于每个波次，每个诚实节点提交波次领导者的概率至少为 2/3。这是使用公共核心抽象（common-core abstraction）的结果，该抽象保证在三轮全节点间通信并收集累积的值集合之后，所有正确的节点至少有 2f+1 个公共值。这些公共值的集合称为公共核心（common core）。因此，期望中，每个诚实节点每隔 2/3 个波次提交一次领导者。
全序性通过递归搜索从最近完成的波次 w 到最后提交的波次 w' 的强路径来实现，主要检查是否存在未提交的波次（即领导者未提交的波次）。例如：
- 首先检查是否存在从 w 到 w-1 的强路径。
- 如果不存在强路径，则说明没有诚实节点会提交 w-1 ，然后继续检查 w-2 到 w 的强路径。
- 如果存在从 w-1 到 w 的强路径，则先提交 w-1 ，然后开始检查 w-1 到 w-2 的强路径。
- 按照这种方式不断向前推进，直到到达波次 w' 。
通过上述机制，协议确保了所有消息的全序性，同时维护了一致性和高效性。
协议中包括慢节点以及有效性属性的满足，得益于使用弱边。由于某些提议和区块可能会延迟，而节点已经进入下一轮，可能没有强边连接这些区块，因此我们可以在稍后观察到这些区块并将其正确排序时形成弱边。
完整性（Integrity） 由以下事实保证：所有顶点都被可靠地广播，因此通过可靠广播的完整性，确保同一轮中的两个顶点不会共享相同的来源节点，即一个节点在每轮最多只能提出一个区块。
因此，当前的协议是一个有效的 BAB（Byzantine Atomic Broadcast）协议，满足 有效性、一致性、完整性 和 全序性，并具有 最优时间复杂度 O(1) 和 最优摊销通信复杂度 O(n)。通过依赖可靠广播，排除了拜占庭式分歧，确保所有诚实节点最终看到相同的 DAG，而无需依赖签名或非对称加密假设，使得该协议具备后量子安全性。最后，协议的优雅设计成为未来基于DAG的共识协议的构建模块，正如我们在 Aptos 生态系统中所见。
敬请关注下一篇文章，我们将对 Narwhal 和 Tusk 进行类似的分析。