众所周知，Aleo 的共识协议是借鉴或者几乎完全是参照 Sui 的共识协议 Narwhal 和 Bullshark。Narwhal 和 Bullshark - 共识可扩展性的秘诀即管理涉及自有对象的交易（例如个人付款或铸造和转移 NFT）可以独立处理，而无需严格的排序要求。相反，涉及共享对象的交易（例如去中心化交易所 (DEX) 中的流动性池或订单簿）需要特定的执行顺序，因为多个用户可以访问和操纵它们。利用这一区别以不同的方式处理自有对象和共享对象。
1. 概述
Narwhal 的核心理念是通过将内存池的数据传播职责与共识层的数据排序职责分离，从而建立高性能分布式账本。在传统的内存池中，用户向验证者提交的交易需要每个验证者将交易广播到其他验证者的内存池。然后，提议者或领导者从他们的内存池中选择交易来创建一个区块，然后在共识机制期间再次广播该区块。此过程会导致效率低下，因为交易在共识过程中被广播两次，第一次来自内存池，第二次来自区块传播。
相比之下，基于 DAG 的共识系统（如 Narwhal 和 Bullshark）允许每个验证者的内存池（使用 Narwhal）独立传播交易批次。当验证者收到交易批次时，它会将该批次作为顶点存储在其本地视图中的有向无环图 (DAG) 中。从顶点连接到前一轮顶点的边代表对该顶点的投票。通过利用共识逻辑，每个验证者都可以解释本地 DAG 结构并对其进行完全排序，而无需进行额外的消息交换。这种方法确保建立在 DAG 结构之上的共识逻辑不会增加额外的通信开销。
2. Narwhal
Narwhal 充当内存池层，用于为每个验证者构建基于轮次的 DAG。DAG 由顶点和边组成，其中每个顶点代表一批交易，连接顶点的传出边是对其上一轮父节点的引用（如图1所示）。验证者彼此交换有关这些顶点和引用的信息，以在各自的本地视图中形成 DAG。Narwhal 主要用于构建 DAG，而建立在 Narwhal 之上的共识逻辑负责对其进行解释。
图 1 显示了基于圆形的 DAG 的组件，其中包含顶点（蓝色框）和传出边（引用），以绿色箭头表示。
与往常一样，将考虑一个 n3f+1 系统，该系统旨在容忍多达三分之一的拜占庭节点。在 Narwhal 中，每个验证者由 Worker 和一个主节点组成。Worker 有两项职责：
将交易批次流式传输到相应的验证器工作器（例如，Worker1 与其他验证器 Worker1 共享批次，如图 2 所示）
将批次的摘要（哈希）发送到各自的主节点。每个验证器的主节点使用这些摘要来运行 Narwhal 内存池协议并在其自己的视图中形成本地基于回合的 DAG。
图 2 说明了每个验证器的内部工作原理，它由工作器和主验证器组成。
由于每个工作节点独立运行，因此可以通过向验证器系统添加更多工作节点来水平扩展数据传播过程。主节点仍然是瓶颈，因为每个验证器只有一个主节点负责运行内存池协议。然而，这种权衡带来了显着的好处。将数据传播与 DAG 构建分开，允许主节点独立于数据传播形成 DAG。此外，主节点利用来自工作节点的批次摘要来运行内存池协议，而不是使用整个交易批次，从而节省大量带宽。
构建 DAG
为了构建 DAG，每个验证者在第 r 轮遵循以下步骤：
1. 每个验证者的主验证者向所有其他验证者发送一条消息，包括：
a. 来自其工作者的一批交易摘要
b. 来自上一轮（r-1）的 nf 证书（引用）
2. 收到消息后，主接收者通过确保以下内容来验证消息：
a. 该消息与接收者来自同一轮。
b. 接收方在第 r 轮中第一次从发送方主节点接收到该消息。
c. 其工作人员已将与指定摘要相对应的批次存储在消息中。
3. 如果检查通过，验证者将通过发回其签名来为该消息投票。
4. 发送者汇总来自不同接收者的 nf 签名以创建证书，并将此证书发送回所有其他主节点。然后，接收者可以使用此证书以及相关的消息摘要在各自的本地 DAG 中创建顶点。
5. 一旦主要节点可以形成 nf 个顶点，每个顶点都有一个证书，它就可以进入下一轮，即 r+1。
图 3：验证者广播其顶点并将其他验证者的 DAG 添加到其本地 DAG 的流程。
图 4 显示了每个验证者的工作器和主验证者的职责
图 5：DAG 构建
3. Bullshark
一旦有了 DAG，就可以在其上使用 Bullshark 进行排序逻辑，这不会增加任何通信开销。术语“零通信开销”意味着 Bullshark 不需要验证者进行额外的通信来为他们的顶点建立总顺序。相反，每个验证者都会查看其本地 DAG，并使用 Bullshark 作为共识协议来解释顶点和边，最终确定它们的顺序。尽管由于网络不可靠或存在损坏的拜占庭节点，不同的验证者可能会看到不同的 DAG，但 Bullshark 可以确保诚实的验证者达到相同的总顺序。Bullshark 共识有两个版本：同步版本和部分同步版本。在这里重点关注后者，因为它通过垃圾收集保证了有限的内存使用，将在后面深入研究这一功能。Bullshark 通过将基于轮次的 DAG 分为奇数轮和偶数轮来解释它。为简单起见，考虑一个 n=4 和 f=1 的场景（记住 n3f+1）。在奇数轮中，引入了一个称为“锚点”的预定义顶点，在图 6 中以绿色表示。目标是确定要承诺哪些锚点，而这正是偶数轮变得至关重要的地方。
图 6：锚点及其因果历史
偶数轮中与上一奇数轮中的锚点相连的边将作为对该锚点的投票。一旦锚点在下一偶数轮中获得至少 f+1 票，它就会被提交。例如，在图 7 中，第 3 轮中的锚点 A2 被提交，因为它在第 4 轮获得了三票，超过了 f+1=2 的阈值。相反，A1 仍未提交，因为它只有一票。
图 7 说明了偶数轮中的顶点如何为上一奇数轮中的锚点投票
但是，考虑到网络的异步特性，不应忽略 A1。不同的验证器在其本地视图中可能拥有不同的 DAG。如图 8 所示，当验证器 2 试图跟上验证器 1 时，它会提交锚点 A1，即使验证器 1 没有提交。当验证器 2 赶上验证器 1 时，就会出现问题，因为验证器 2 随后会提交 A1，然后是 A2。
图 8：不同验证者对 DAG 的不同看法
为了确保验证者之间就顶点的全序达成共识，即使 DAG 视图不同，Bullshark 也提出了一个解决方案。如果存在从旧锚点到未来锚点的路径，并且未来锚点得到提交，则旧锚点也必须得到提交并排在未来锚点之前。否则，跳过旧锚点被认为是安全的。验证者递归地应用此原则，直到到达先前提交的锚点。一旦实现锚点承诺，验证者就可以使用确定性规则（例如拓扑排序或按 gas 价格排序）为所有已提交的锚点及其因果历史建立全序。在图 9 中，锚点 A3 的因果历史区块用带绿色角的白色框表示。
图 9 展示了 Bullshark 全序锚点及其因果历史
图 9 直观地展示了承诺过程和全排序。在第 6 轮中，验证器提交锚点 A3，因为它获得了三票，超过了 f 票的阈值。然后，验证器递归回顾其历史记录以提交并确定较旧锚点的顺序。由于没有从 A3 到 A2 的路径，因此跳过 A2 被认为是安全的。当验证器回到 A1 时，它会立即提交并将 A1 排序在 A3 之后，因为存在从 A3 到 A1 的路径。A3 以及锚点 A1 和 A3 的因果历史是有序的，如图 9 底部所示。此过程从第 1 轮重新开始，验证器继续回顾直到找到先前提交的锚点，这意味着其所有历史数据都已排序。
值得注意的是，如果锚点具有从已承诺的未来锚点到它们的路径，则承诺锚点被认为是安全的，该路径来自群体交集。
垃圾收集与公平性
在这个部分，深入研究了 Bullshark 如何使用垃圾收集来解决内存问题并在基于 DAG 的共识中实现公平性。公平性是区块链技术中的理想属性，确保所有节点都有权为共识协议做出贡献，即使它们的运行速度很慢。然而，旨在确保所有节点的顶点最终都被添加到其他节点的 DAG 中时，挑战就出现了。由于网络的异步性质，不确定这个过程需要多长时间。这种不确定性要求所有节点必须保留所有任意旧的顶点和证书，以便其他节点可以随时访问，从而允许较慢的节点赶上来。然而，随着 DAG 继续无限增长，过于强大的公平性会导致 DAG 构造中的内存不受限制。因此，需要一种方法来清理旧的、未使用的历史记录，而这正是垃圾收集。
垃圾收集是一种恢复未使用内存的机制，使其可供将来使用。简单来说，它涉及删除 DAG 中未使用的历史数据，从而有效地释放内存资源，进而有助于保持有限的内存使用量。然而，垃圾收集和公平性之间存在根本矛盾。当对旧的 DAG 数据进行垃圾收集时，无法保证任意历史信息可以被较慢的节点轻松访问。因此，同时实现垃圾收集和公平似乎是不可能的。Bullshark 通过放宽公平性要求以仅在同步期间确保公平性来解决这一挑战，这就是为什么 Bullshark 的部分同步版本比异步版本更受欢迎的原因。部分同步模型由两个时期组成：异步和同步时期。在异步期间，系统的行为是异步的，这意味着由于恶意行为者或互联网固有的不可靠性，消息可能会出现延迟。然而，来自恶意行为者的攻击或与互联网相关的延迟问题最终必须停止，让系统恢复并恢复正常运行。系统恢复的点称为 GST（全局稳定时间），此后系统将过渡到同步操作。
简单来说，在部分同步模型中，系统在 GST 之前保持异步，之后同步运行。垃圾收集的过程很简单。验证器在广播顶点时会为其添加时间戳。提交锚点时，会为其分配一个时间戳，该时间戳计算为其父节点（锚点具有强边指向的顶点）的中位数。现在锚点的历史记录已准备好排序，验证器会回顾锚点的历史记录，同时使用该轮顶点时间戳的中位数计算每轮的时间戳。一旦达到某个轮次的 GCround，其时间戳比锚点时间戳小超过预定义的时间，则该 GCround 和其下面的轮次都会被垃圾回收。
图 10：Bullshark 如何垃圾收集旧历史并实现公平的过程
图 10 提供了 Bullshark 垃圾收集工作原理的具体示例。在此图中，定义为 2，锚点 A（绿色）的时间戳计算为 5。因此，可以还原并发现 GCround 时间戳的阈值为 5-2，结果为 3。因此，任何时间戳在 3 和 5 之间的顶点都可以包含在 DAG 中，即使它到达的时间晚于其他顶点。如图 10 所示，来自验证器 4 的顶点（标记为时间戳 4）可以添加到 DAG 中，尽管它比其他顶点晚到达。同时，时间戳低于 3 的轮次将被垃圾收集。但是，仅添加验证器 4 的顶点并不能保证公平性，因为没有从锚点到该顶点的路径。因此，在全序过程中将忽略该顶点。为了解决公平性问题，引入了“弱链接”或“弱边”的概念。与迄今为止讨论过的边（称为强边，将第 r 轮中的顶点与紧接在前一轮（第 r-1 轮）中的顶点连接起来）不同，弱边将第 r 轮中的顶点与第 r-1 轮以下的顶点连接起来。它们在共识逻辑中不计入投票；相反，它们的目的是帮助创建通往慢速验证者顶点的路径，以确保其他诚实的验证者最终将它们添加到 DAG 中。因此，垃圾收集和弱链接的组合可确保同步期间的公平性，同时限制内存使用量。
4. 结论
在整篇文章中，深入研究了 Narwhal 和 Bullshark，这是处理共识协议中共享对象的基本思想。
Narwhal 的总体思路是将内存池功能与共识机制分离开来。通过使用 Narwhal 作为内存池，工作节点可以以网络速度传播批量交易。同时，工作节点将批量摘要转发给主要节点，以形成基于轮次的 DAG。通过这种设计，Narwhal 的结构可以通过向每个验证者添加更多工作节点来实现水平扩展。
一旦验证者使用 Narwhal 构建了 DAG，就可以在 DAG 之上构建共识逻辑。Bullshark 处理共识层中的排序逻辑，而无需在验证者之间发送额外消息。通过这种干净的分离设计，数据可以以网络速度传播，而不是排序速度。值得注意的是，Bullshark 提供了同步期间的垃圾收集和公平性解决方案，解决了许多基于 DAG 的共识所面临的内存和公平性问题。
PS：本文全部来自于网络搜集整理，如有错误请及时联系纠正，谢谢！
ZKT 纯GPU锄头，第一梯队，仅限大算力合作！
ZKT Aleo-ASIC，芯片和芯片机预售中，台积电代工！
2024年全球ZK峰会 Aleo-ASIC 最有竞争力品牌！
感兴趣的小伙伴扫码联系，仅限大客户和渠道！
全网最全Aleo中文WiKi
Aleo最新十年区块产出奖励模型推演（Testnet Beta）
Aleo主网倒计时 | Aleo最新Puzzle谜题算法深度解析！
重磅分析！以太坊真的会开倒车转回“PoW”么？还是会效仿Aleo模式？
Aleo主网倒计时 | Aleo 完成 snarkOS 和 snarkVM 的代码安全审计
Aleo主网倒计时 | Aleo Systems 公司 CEO Alex Pruden 卸任感言
重磅！Aleo初始经济模型重大更新！主网上线时间是否有变化？
ALEO 问答集锦 | 关于质押者、证明者和验证者官方最新解答
ALEO 问答集锦 | Aleo积分到底有什么用？区块奖励重大变化？
重磅分析！为什么说FPGA或者ZK通用服务器在Aleo项目上机会是零？
