欢迎来到本系列的第三篇文章，我们将探讨 Bullshark，一种拜占庭容错（BFT）共识机制。与其前辈 DAG Rider 和 Tusk 不同，Bullshark 不仅在异步环境下表现优异，同时还能充分利用同步网络的优势，实现同步与异步世界的最佳性能结合。
虽然 Tusk 在最坏情况下的异步环境中表现出色，即使在出现故障时也能提供最低延迟，但在最佳情况下的同步环境中却无法发挥其潜力，导致延迟高于现有协议。为了解决这一问题，Bullshark 提供了一条快速路径，利用常见的同步网络条件，同时在最坏情况下的异步环境中仍能表现出色。它不需要视图切换或视图同步机制。Bullshark 基于与 Tusk 相同的 DAG，因此继承了其可扩展性，能够在大规模委员会中保持高性能：在 50 个节点时实现每秒 125,000 笔交易，延迟约为 2 秒。此外，它还具备 Narwhal 的所有实用优势，如将数据传播与 DAG 构建分离，以及高效的可靠广播机制。
尽管 Tusk 提供垃圾回收功能，从而实现了有界的内存需求，但它牺牲了可量化的公平性。Bullshark 在同步阶段（即全球稳定时间 GST 之后）能够保证公平性。然而，由于在 GST 之前消息可能被无限期延迟，因此在异步阶段或 GST 之前，在有界内存需求下无法实现公平性。为此，在 GST 之前，Bullshark 采用了 Tusk 的重传策略，此时只能保证无限期执行的情况下达成协议。
Bullshark 遵循这样的趋势：一旦节点接收到至少 2f + 1 条消息，即可进入下一轮。在异步阶段，这种方式运行良好。然而，在同步阶段，恶意方可能会重新排序消息，迫使节点在收到领导者消息之前提前进入下一轮。为了解决这一问题，Bullshark 将超时嵌入 DAG，使得节点在超时发生之前会等待领导者的消息再进入下一轮。
与 DAG Rider 类似，Bullshark 的两个核心模块是：
- 可靠广播机制：提供有效性（Validity）、一致性（Agreement）和完整性（Integrity）。
- 全局完美随机数（Global Perfect Coin）：为领导者的选举提供随机性，同时保证有效性、公平性、不可预测性和终止性。
这些属性已在第一篇文章（介绍 DAG Rider 时）中定义，建议先阅读该文章后再继续。
为了在同步和异步环境中都能充分发挥性能，Bullshark 在每一波次中设置了三位潜在的领导者。一个波次由连续四轮构成：
- 第 1 轮：有两位潜在领导者，即备用领导者（Fallback Leader）和稳态领导者（Steady-State Leader）。
- 第 3 轮：设置了另一位稳态领导者，以减少同步环境下的延迟。
因此，在同步环境下，只需要两轮即可确认稳态领导者。所有节点的投票类型在每一波次中都已预先定义，这确保了同一波次中不会同时确认备用领导者和稳态领导者。
-
投票类型：
- 如果节点在上一波次中确认了备用领导者或第二位稳态领导者，其投票类型为“稳态”。
- 如果节点在上一波次中未确认任何领导者，其投票类型为“备用”。
- 借助可靠广播，即使是拜占庭节点也无法隐藏其投票类型。
-
投票轮次：
- 第 2 轮的节点只能对第 1 轮的稳态领导者投票。
- 第 4 轮的节点可根据其投票类型，对第 3 轮的第二位稳态领导者或第 1 轮的备用领导者投票。
-
异步阶段：
- 每个备用领导者被确认的概率至少为 2/3，即在异步环境中，确认备用领导者平均需要 6 轮。
-
同步阶段：
- 如果第一位领导者是诚实的，那么所有诚实节点将在第 3 轮几乎同时开始。
- 无需视图切换，因为 DAG 已编码了所有保证安全性所需的信息。任何节点都可以通过 DAG 观察到其他节点的信息并据此做出决策。
-
公平性：
- GST 之后，Bullshark 在同步阶段能保证公平性，即每个节点被选为领导者的概率相同。 投票机制详解
在 Bullshark 中，所有参与方都会维护两个列表：steadyVoters[w] 和 fallbackVoters[w]，用于记录某波次 w 中各方的投票类型。这取决于该方是否在上一波次 w-1 中确认了第二位稳态领导者、备用领导者，或者两者都未确认。
当某参与方 ) 在波次 w 的第一轮中广播一个顶点 v 时，其他参与方可以通过 v 的因果历史推断出 p 在波次 w 中的投票类型。这些因果历史包括了 v的强边所指向的顶点集，这些顶点被视为潜在的投票者。
- 确认波次 w-1 的备用领导者：潜在投票者中至少有 2f+1 个顶点需要具备到该领导者的强路径，且其投票类型为备用类型。
- 确认波次 w-1 的第二位稳态领导者：潜在投票者中至少有 2f+1 个顶点需要具备到该领导者的强路径，且其投票类型为稳态类型。
- 确认波次的第一位稳态领导者：类似的，强路径的顶点需来自波次第三轮的顶点集。
由于可靠广播的特性，即使是拜占庭节点也无法伪造其投票类型。仲裁交集（Quorum Intersection） 能够保证在同一波次中，不同类型的领导者不会同时被确认。这就是为什么 Bullshark 要求至少 2f+1 条强路径，而不像 Tusk 那样只需要 f+1 条强路径即可保证安全性。
假设 f = 1，以下是示例说明：
- S1A：波次 1 的第一位稳态领导者（第 1 轮）。
- S1B：波次 1 的第二位稳态领导者（第 3 轮）。
- F1：波次 1 的备用领导者（第 1 轮）。
所有参与方在波次 1 开始时，其投票类型均为稳态类型。
-
第 2 轮：
- P1 观察到 3 = 2f+1 条指向 S1A 的稳态投票（标记为红色），因此 P1 确认了 S1A。
- P1 在第 4 轮仅观察到 1 条指向 S1B 的投票，因此 P1 未确认 S1B。
-
波次 2 的投票类型变化：
- 由于 P1 未确认波次 1 的第二位稳态领导者 S1B，它在波次 2 中的投票类型为备用类型。
- 从 DAG 的第 5 轮观察得知，P2、P3 和 P4 也未确认 S1B，因此波次 2 中所有参与方的投票类型均为备用类型。
-
第 8 轮：
- P1 观察到 3 = 2f+1 条指向波次 2 备用领导者 F2 的备用投票（标记为蓝色），因此 P1 确认了 F2。
类似于 Tusk 和 DAG Rider，我们在 DAG 中递归地向后遍历，直到上一个已提交的领导者，目的是寻找未提交的领导者。这些领导者在本地 DAG 中未满足提交规则，但根据其他诚实节点对 DAG 的本地视图及其因果历史，可能已经被包括在内。在 Bullshark 中，这个过程比在 DAG Rider 中更复杂，因为每轮（wave）中有三个潜在的领导者，而不是一个。
根据共识交集和 DAG 的非双花（non-equivocation）特性，如果一个节点通过观察到 2𝑓+1 票提交了一个备用（fallback）或稳态（steady state）领导者，那么所有其他节点至少会看到其中的 𝑓+1 票。此外，由于同一轮中节点不能对两种类型的领导者都投票，如果某个节点 p_i 观察到备用（稳态）领导者的 𝑓+1 票，则没有节点能够提交稳态（备用）领导者，因为这种情况下稳态（备用）类型的投票最多为 2𝑓。
节点必须考虑相同的潜在投票。
- 稳态领导者 v 的潜在投票：验证者将 v 的潜在投票集合定义为其 DAG 中 v.round + 1 的所有顶点，并且这些顶点与验证者先前排序的最后一个领导者之间存在强路径。
- 备用领导者的潜在投票集合：与稳态领导者不同，备用领导者的潜在投票集合为 v.round + 3 轮中的顶点。
在计算所有潜在投票后，验证者需要检查当前轮次中的领导者是否可能被其他诚实验证者提交。以下是流程：
-
检查潜在投票类型和强路径
p_i 检查潜在投票的类型，并验证强路径是否连接到领导者，从而确定稳态和备用领导者的投票集合。- 如果当前轮次没有备用领导者，或者这一轮已经提交了稳态领导者，则备用领导者的投票集合为空。
-
判定领导者是否可以提交
p_i 检查当前轮次中的某个领导者 u 是否有至少 𝑓+1 票，而另一位领导者的票数不超过 𝑓。- 如果满足条件，则 p_i 将 u 排序，并将其推入领导者栈，同时继续遍历下一轮次以检查是否有其他领导者需要排序在 u 之前。
- 如果条件不满足，则跳过当前轮次的领导者，因为可以保证其中没有领导者能够被提交。
-
排序因果历史
完成领导者排序后，节点会以确定性的方式对这些领导者的因果历史进行排序。
原始论文还提出了一种最终同步版本的 Bullshark，这是首个不需要视图变更或视图同步机制的模型。在该模型中：
- 没有备用领导者，验证者始终尝试提交稳态领导者。
- 安全性证明：与带备用领导者的 Bullshark 模型的安全性证明类似。
- 活性保证：通过证明在全球稳定时间（GST）后，连续两个诚实的预定领导者能确保第二个领导者会被所有诚实节点提交，从而保证活性。
- 回溯确认未确认的领导者：
- P1 检查是否有未确认的领导者可以被确认。在第 4 轮，P1 仅观察到 1 条指向 S1B 的稳态投票（少于 f+1），因此 P1 不确认 S1B。因为如果 S1B 被某方确认，P1 应观察到至少 f+1 条投票。
在 Tusk 中实现的垃圾回收机制牺牲了有效性（Validity），因为在异步网络中无法区分节点是运行缓慢还是已经故障。由缓慢节点提议的区块可能在被完全排序之前就被垃圾回收掉了。而 DAG Rider 则通过弱连接（weak links）来保证有效性，但在异步条件下需要使用无限的内存空间。如前所述，Bullshark 在同步条件（即GST之后）下提供了公平性和有效性。
在 Bullshark 中，通过使用时间戳，我们实现了一种垃圾回收机制，该机制在同步条件下既允许内存使用保持有限，又能够提供公平性。
-
领导者的时间戳计算
对于一个领导者节点 v ，其时间戳是由 v 的父节点（即 v 的强边所连接的节点）的所有时间戳的中值（median）计算得出的。 -
轮次的时间戳计算
当遍历 v 的因果历史（causal history）以找到需要排序的顶点时，对每一轮次的时间戳也采用类似的计算方式，即取这一轮次中所有顶点时间戳的中值。 -
垃圾回收判定
如果某轮次的时间戳与当前轮次的时间戳差异超过 3$\Delta$ ，则该轮次会被垃圾回收。这里，$\Delta$ 表示在GST之后可靠广播一条消息所需的时间。
-
吞吐量（Throughput）：
Bullshark 的吞吐量显著高于 Hotstuff，达到 110,000 tx/sec（10个节点） 和 130,000 tx/sec（50个节点），是 Hotstuff 吞吐量的 两倍以上。
虽然看起来随着委员会规模的增加，吞吐量提升有些反直觉，但原因在于 DAG 的实现没有充分优化资源的使用（网络、磁盘、CPU）。因此，更多的节点通过提高资源的多路复用率，反而提升了性能。 -
延迟（Latency）：
尽管 Tusk 提供了更高的吞吐量，Bullshark 的卖点在于其低延迟——无论委员会规模大小，延迟都保持在 约2秒。
这与 Hotstuff 的延迟相当，主要得益于 Bullshark 能够在每 2轮 DAG 回合 中提交一个领导者，而 Tusk 则需要 4轮回合。
-
Hotstuff 的表现：
在存在 3个故障节点 时，Hotstuff 的吞吐量下降超过 10倍，而延迟则增加了 15倍。 -
Tusk 和 Bullshark 的表现：
二者在崩溃故障下仍然维持较好的吞吐量表现：- 基于底层 DAG 的架构，交易的收集和传播即使在存在故障节点时也不会受到严重影响。
- 吞吐量的下降主要归因于故障节点的容量损失，而非系统机制问题。
- 在 3个故障节点 的情况下，Tusk 和 Bullshark 的吞吐量相较于 Hotstuff 提高了 10倍，延迟减少了约 7倍。
-
Hotstuff 的局限：
Hotstuff 在 GST（全局稳定时间）之前无法提供活性保证，并且在面对各种对抗性攻击时，系统吞吐量可能降至 0。 -
Bullshark 的表现：
Bullshark 的部分同步模型可能会遇到类似的问题：- 如果领导者的消息被无限期延迟，其他节点会在听到领导者的消息之前超时。
- 为了解决这一问题，Tusk 和 DAG Rider 在 DAG 构造完成后 不可预测地选举领导者，使此类攻击变得不可能。
-
Fallback 模式：
Bullshark 的回退模式（Fallback Mode）在异步条件下提供了与 Tusk 和 DAG Rider 相同的活性保证，同时在同步条件下不影响性能。- 在回退模式下，Bullshark 放弃了相较于 Tusk 的延迟优势，以保持在异步条件下的活性。
由于基础的可靠广播机制保证了所有节点对领导者的因果历史达成一致，节点在同意排序某些领导者后，也会一致同意垃圾回收哪些轮次。
本文探讨了 Bullshark 的架构，它在基础层面上成为第一个基于 DAG 的零开销 BFT 协议，同时结合了部分同步协议和异步协议的优势。以下是 Bullshark 的核心特点和优点：
-
继承 DAG-Rider 的优点：
Bullshark 保留了 DAG-Rider 的所有理想特性，包括：- 最优的摊销复杂度：高效的资源利用。
- 异步活性（Asynchronous Liveness）：在异步条件下仍能保证系统的进展性。
- 抗量子安全性（Post-Quantum Security）：在面对量子计算威胁时仍能保持安全性。
-
快速路径（Fast Path）：
Bullshark 在同步条件下提供快速路径，显著降低延迟，保证高效的交易确认速度。 -
灵活的投票机制：
- 节点在每个波次中，如果未成功提交领导者，会切换投票类型到备用模式（Fallback）。
- 这种机制无需任何视图变更（View-Change）或视图同步（View-Synchronization）机制，因为所有必要的信息已经编码在 DAG 中。
通过结合异步协议的弹性和部分同步协议的快速路径，Bullshark 在性能和鲁棒性之间实现了卓越的平衡。它为分布式系统和区块链应用提供了一个高效且安全的解决方案，同时展示了 DAG 技术在共识协议中的巨大潜力。