摘要
我们将介绍DAG Rider，这是第一个实现最佳弹性、最佳分摊通信复杂度和最佳时间复杂度的异步拜占庭原子广播协议
(译者注: 在分布式容错计算中，拥有两种广播协议：
- 一种是顺序广播，顺序广播指的是所有的进程按照相同的顺序，处理接受相同的消息集。
- 一种是原子广播，原子广播指的是要么所有参与参与者都正确执行，否者失败。
在区块链领域中，这往往代表着两种区块链架构： - 一种btc,eth 作为代表的以块作为单位的传统的区块链。
- 另外一种，代表着以aptos,sui 为代表的，不要求使用块的dag结构区块链)。
DAG Rider是后量子安全的，并确保所有由正确流程提出的值最终得到交付。
我们构建的DAG Rider用两层结构：
- 在第一层结构中，节点进程可靠地广播他们的提议，并构建一个结构化的有向非循环图（DAG）之间的通信。
- 在第二层，节点进程在宿主机观察其DAG，并对所有提案进行排序，这一步发生在运行进程的宿主机，不需要对外额外的通信。
1 简介
对可扩展的地理复制(译者注：地理复制指的是在不同的位置运行的多个副本)拜占庭容错可靠性系统的放大需求激发了巨大的需求拜占庭状态机复制 (SMR) 问题的研究 [17, 31].近年来[28, 32, 43]，该问题的许多变体被定义来满足区块链系统的需求。为了解决在组织间部署中自然产生的公平性问题，我们专注于经典的长效拜占庭原子广播（BAB）问题[12，19]，除了总排序和进程外，还保证所有正确进程的提议最终被包括在内。直到最近，拜占庭共识问题的异步协议[12, 16, 26]被认为成本太高或太复杂，无法用于实际的SMR解决方案。
然而，最近的两篇单次拜占庭共识论文，VABA[1]和后来的Dumbo[35]，提出了异步解决方案，具有
- 1，最佳弹性，
- 2，预期恒定时间复杂性，
- 3，最佳二次通信和最佳摊销线性通信复杂性（）。
对于最佳二次通信和最佳摊销线性通信复杂性，在本文中，我们遵循这一最新的工作思路，
提出了DAG-Rider：第一个具有最优弹性、最优轮复杂度和最优分摊通信复杂度的异步 BAB 协议。
此外，给定一个完美的共享币抽象，我们的协议不使用签名，也不依赖于非对称加密的假设。
因此，当使用具有信息理论一致性保证的确定性基于阈值的硬币实现 [13, 34] 时，我们的 BAB 协议的安全特性是后量子安全的。
简单说。我们分两层构建DAG-Rider：一个通信层和一个零开销的排序层。在通信层，节点进程可靠地广播他们的提按，并提 一些元数据，帮助他们形成他们所传递的消息的有向无环图（DAG)。也就是说，DAG由几轮组成，每个进程节点在每轮中最多广播一条信息，每条信息都有𝑂(𝑛)对以前几轮信息的引用，其中 𝑛是进程的总数量。排序层不需要任何额外的通信。相反，进程观察他们的本地DAG，并在少量随机化的帮助下（每𝑂(𝑛)投掷一枚硬币 每𝑂(𝑛)掷硬币决定不同进程提出的数值) 在他们的本地 DAG 中对所有传递的消息进行本地排序。
DAG-Rider一个很好的特点是，提按操作只是一个简单的可靠广播。可靠广播的协议属性保证了所有正确的节点进程最终会看到同一个DAG。此外，可靠广播的有效性属性保证了所有正确节点进程的广播信息最终都包含在DAG中。因此，与 VABA 和 Dumbo 协议相比，DAG-Rider 没有浪费任何信息，所有正确进程的提按值最终都是有序的（即，不需要重新提按），而 VABA 和 Dumbo 协议则追溯性地忽略了一半的协议信息，在𝑂(𝑛)提按中提交一个值。
复杂度。我们用不同的正确的节点进程提出的𝑂(𝑛)值所需的异步时间[16]来衡量时间复杂度。我们用节点进程为承诺一个值所发送的比特数来衡量通信复杂度。为了将DAG-Rider与最先进的异步拜占庭协议进行比较，我们考虑了SMR的实现，即运行VABA或Dumbo协议的无界序列来独立达成每个槽的协议。为了在我们的时间复杂度定义方面进行比较，我们允许基于VABA和Dumbo的SMRs并发运行多达𝑛个槽。然而，请注意，对于执行过程来说，必须按顺序输出槽位决定（没有空隙）。因此，根据[6]中的证明，基于VABA和Dumbo的SMR的时间复杂度为𝑂(log(𝑛))。表 1 将 DAG-Rider 与基于 VABA 和 Dumbo 的 SMR 进行了比较。
由于我们的协议使用可靠的广播抽象作为基本构建块，不同的实例化会产生不同的复杂性。例如，如果我们使用经典的Bracha广播[11]，在每个消息中提出一个单一的值，我们得到每个决策的通信复杂度为𝑂（𝑛3）。这是因为Bracha广播的复杂度是𝑂(𝑛2)，而为了形成DAG，每个消息都必须包括对先前消息的𝑂(𝑛)引用。如果我们愿意允许有概率𝜖违反进度，那么我们可以使用Guerraoui等人的广播协议[25]，将每个决策的复杂度降低到𝑂（𝑛2log(𝑛)。
现在，正如 Dumbo 通过使用批处理和添加擦除编码(纠删码)阶段以更经济地分配数据将 VABA 的通信复杂性从二次方摊销到线性一样，我们也可以将我们的通信复杂性摊销为每个决策的线性。 首先，因为无论如何我们在每个广播中都包含了一个 𝑂(𝑛) 引用向量，所以在每条消息中批处理 𝑂(𝑛) 提议可以减少整个通信复杂度的一个因素，即使使用 Bracha 广播也是如此。 为了达到最佳线性复杂度，我们可以用 Cachin 和 Tessaro [14] 的异步可验证信息传播来代替可靠广播。 该协议的通信复杂度为𝑂(𝑛2log(𝑛) + 𝑛|𝑉 |)，其中|𝑉 | 是消息大小，它允许我们批处理 𝑂(𝑛log(𝑛)) 提案，以实现最佳的摊销通信复杂度。
本文的其余部分结构如下： 第二节描述了用于 DAG-Rider 的模型和构建块； 第三节正式定义了 BAB 问题； 第四节描述了 DAG 构造层； 第五节指定 DAG 层之上的 DAG-Rider 协议； 第六节证明协议的正确性并分析其性能； 第七节描述相关工作； 最后，第 8 节结束了本文。
2 模型和构件
该系统由一组Π = {𝑝1, . . . , 𝑝𝑛}的𝑛节点进程，其中𝑓 < 𝑛/3，可以任意行动，即拜占庭。为简单起见，我们考虑总共有𝑛=3𝑓+1个节点进程。每两个正确接待你进程之间的联系 每两个正确进程之间的联系是可靠的。也就是说，当一个正确的节点进程向另一个正确的节点进程发送消息时，消息最终会到达，并且接收者可以验证发送者的身份。通信是异步的，也就是说，对信息传递时间没有约束。我们考虑一个自适应的对手，在运行期间可以动态地破坏多达𝑓个节点进程。一旦对手破坏了一个节点进程，它就可以丢弃之前从该进程发给其他人的未交付的消息。对手控制着消息的到达时间。作为构造的一部分，我们使用了两个构件：一个可靠的广播层和一个延迟的全局完美硬币，我们接下来描述一下。
该系统由一组Π = {𝑝1, . . . , 𝑝𝑛}的𝑛节点进程，其中𝑓 < 𝑛/3，可以任意行动，即拜占庭。为简单起见，我们考虑总共有𝑛=3𝑓+1个节点进程。每两个正确接待你进程之间的联系 每两个正确进程之间的联系是可靠的。也就是说，当一个正确的节点进程向另一个正确的节点进程发送消息时，消息最终会到达，并且接收者可以验证发送者的身份。通信是异步的，也就是说，对信息传递时间没有约束。我们考虑一个自适应的对手，在运行期间可以动态地破坏多达𝑓个节点进程。一旦对手破坏了一个节点进程，它就可以丢弃之前从该进程发给其他人的未交付的消息。对手控制着消息的到达时间。作为构造的一部分，我们使用了两个构件：一个可靠的广播层和一个延迟的全局完美硬币，我们接下来描述一下。
可靠的广播。有一些已知的算法，如Bracha广播[11]来实现异步网络模型中的可靠广播抽象。还有一些高效的gossip协议[9, 10, 25, 27]，以进程数的次生通信成本提供可靠的广播whp，以及异步可验证的消息广播协议[14, 35]，使用擦除码来有效地批处理广播值。
由于我们对构建一个满足概率为1的异步原子广播感兴趣，我们相应地定义了可靠的重播抽象，以允许使用高效的gossip协议。形式上，每个发送方进程𝑝𝑘可以通过调用r_bcast𝑘（𝑚，𝑟）发送消息，其中𝑚是一个消息，𝑟∈N是一个整数。每个进程𝑝𝑖都有一个输出r_deliver𝑖 (𝑚, 𝑟, 𝑝𝑘)，其中𝑚是一个消息，𝑟是一个轮数，而𝑝𝑘是调用相应r_bcast𝑘 (𝑚, 𝑟) 的进程。可靠的广播抽象保证了以下属性。
协议 如果正确处理𝑝𝑖 输出
r_deliver𝑖(𝑚, 𝑟, 𝑝𝑘)，然后每个其他正确的过程𝑝𝑗最终输出 r_deliver𝑗 (𝑚, 𝑟, 𝑝𝑘) 概率为 1。
完整性 对于每一轮 𝑟 ∈ N 和进程 𝑝𝑘 ∈ Π，正确的过程 𝑝𝑖输出 r_deliver𝑖(𝑚, 𝑟, 𝑝𝑘） 最多一次，不管𝑚。
有效性 如果一个正确的进程𝑝𝑘调用r_bcast𝑘(𝑚,𝑟)，那么每个正确的进程𝑝𝑖最终输出r_deliver 𝑖 (𝑚, 𝑟, 𝑘)，概率为 1。
全球完美硬币。我们使用全局完美的硬币，对手无法预测。进程 𝑝𝑖 ∈ Π 通过调用 choose_leader𝑖(𝑤) 调用硬币的实例 𝑤，𝑤 ∈ N。这个调用返回一个进程𝑝𝑗∈Π，它是例如𝑤所选择的领导者。设𝑋𝑤为随机变量，表示硬币返回过程𝑝𝑗作为调用choose_leader𝑖(𝑤)。全局完美硬币币有以下保证：
协议 如果两个正确的进程调用choose_leader𝑖(𝑤)和 choose_leader𝑗(𝑤)的返回值分别为 𝑝1 和 𝑝2，则 𝑝1 = 𝑝2。
终止 如果至少有 𝑓 + 1 个进程调用 choose_leader(w)，那么每个 choose_leader(w) 调用最终都会返回。
不可预测性 只要少于𝑓+1个进程调用select_leader(𝑤)，返回值就与随机值无法区分，除非有可忽略的概率𝜖。也就是说，对手能猜到调用select_leader(𝑤)返回的进程𝑝𝑗的概率𝑝𝑟 ≤ Pr[𝑋𝑤 = 𝑝𝑗]+ 𝜖。
公平性 硬币是公平的，即∀𝑤∈N，∀𝑝𝑗∈Π。Pr[𝑋𝑤= 𝑝𝑗] = 1/𝑛.
这种硬币被用作以前拜占庭协议的一部分，如[1, 7, 13, 35]。实施例子可以在[13, 34]中找到。实现全局完美硬币的一种方法是使用PKI和阈值签名方案[8, 33, 42]，阈值为（𝑓+1）-of-𝑛。当一个进程调用硬币的一个实例𝑤时，它用自己的私钥签署𝑤，并将该份额发送给所有进程。一旦一个进程收到𝑓+1的份额，它就可以把它们结合起来，得到阈值签名，并对其进行散列，得到一个随机进程。由于阈值签名值是由实例名称𝑤确定的，这样任何𝑓+1个份额都会揭示它（例如，[42]中的模式是基于Shamir的秘密共享[41]），该硬币是完美的（所有进程都同意领导者），其协议属性有信息理论保证。然而，为了确保不可预测性，PKI必须是可信的，以确保对手不能在一个正确的进程产生之前产生足够的份额来揭示随机性。通常，人们假设用一个受信任的经销商来为所有进程设置随机密钥。然而，这个假设可以通过执行𝑂(𝑛4)消息复杂性的异步分布式密钥生成协议[30]来放松。无论哪种方式，只有在对手的计算能力有限的情况下，这个方案才是不可预测的。然而，由于DAGRider仅仅依靠硬币的不可预测特性来实现 灵活性，其安全属性是后量子安全的。
3 问题定义
我们解决的问题是拜占庭原子广播（BAB）。它允许进程商定一个消息序列，以满足 状态机复制（SMR）。由于FLP(不可能原理)的结果[23]，BAB 不能在异步设置中得到确定的解决。因此，我们使用全局完美硬币来提供随机性 以确保概率为1的有效性。为避免与底层可靠广播抽象的事件相混淆，我们 将BAB的广播和传递事件命名为a_bcast(𝑚, 𝑟)和 a_deliver(𝑚, 𝑟, 𝑘)，其中𝑚是一个消息，𝑟∈N是一个序列号。是一个序列号，𝑝𝑘∈ Π是一个进程。序列号的目的是 序列号的目的是为了区分由 同一个过程。为了简单起见，我们假设 每个进程都广播了无限多的具有连续的 序列号。
定义 3.1（拜占庭原子广播）。 每个正确的过程𝑝𝑖 ∈ Π 可以调用 a_bcast𝑖(𝑚, 𝑟) 并输出 a_deliver𝑖(𝑚, 𝑟, 𝑘), 𝑝𝑘 ∈ Π。拜占庭原子广播协议满足可靠广播（协议、完整性和有效性）以及：
总的顺序 如果一个正确的过程𝑝𝑖输出𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑖(𝑚, 𝑟, 𝑘)在𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑖(𝑚′, 𝑟′ , 𝑘′ )，则没有正确的过程𝑝𝑗输出𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑗(𝑚′, 𝑟′, 𝑘′)，而不需要先输出 𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑗（𝑚，𝑟，𝑘）。
在拜占庭SMR（如区块链）的背景下，BAB抽象支持交易排序和执行之间的分离，正如[2]中所做的那样。BAB提供了一种机制来提出交易，并对其进行完全排序，而执行引擎必须在将交易应用到SMR之前对其进行验证。
此外，请注意，我们的BAB定义比大多数拜占庭SMR系统中实现的排序协议提供了更强的保证。我们的有效性属性要求所有由正确进程广播的消息最终被排序（概率为1），而大多数拜占庭SMR协议（即[17，37，43]要求在无限的运行中，做出无限多的决定，但一些由正确进程提出的建议可以被忽略。此外，需要注意的是，我们的BAB协议满足链式质量。也就是说，对于每一个大小为(2𝑓+1)𝑟的有序消息前缀，𝑟∈N，至少有(𝑓+1)𝑟被正确进程广播。
通信测量。 为了分析摊销后的通信复杂度，我们假设每个消息包含一个交易块，我们说，当所有诚实的各方𝑎_𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑚时，消息中的交易𝑚被订购。我们将通信复杂度衡量为诚实进程为订购一个交易所发送的比特总数。为了能够测量异步运行时间，我们遵循[16]，为每个执行𝑟定义一个时间单位，即𝑟中正确进程之间所有消息的最大时间延迟。我们将时间复杂度衡量为一个正确方从执行中的任何一点开始传递不同正确进程提出的𝑂(𝑛)值所需的预期时间单位。