The Bullshark Protocol

The Bullshark paper (opens in a new tab) introduces two versions of the protocol: an asynchronous protocol with a 2-round fast path during synchrony, and a partially synchronous 2-round protocol. Let's focus on the partially synchronous version.

In traditional BFT leader based consensus protocols, the complexity often lies in the view-change and view-synchronization mechanisms. Many protocols, such as Hotstuff and Raft, simplify their presentation by omitting synchronization details. For instance, Hotstuff was chosen for the Diem project due to its perceived simplicity. However, the engineering team later discovered that the Pacemaker component, assumed to handle view synchronization seamlessly, was complex and challenging to implement, becoming a significant bottleneck under fault conditions.

Bullshark eliminates the need for view-change and view-synchronization mechanisms!

With Bullshark, the DAG encodes complete information, eliminating the need to "agree" on skipping or discarding slow or faulty leaders via timeout complaints. Once a validator commits an anchor (leader) vertex v on the DAG, it traverses back through v’s causal history, ordering anchors it previously skipped but could have been committed by other validators. The round-based DAG’s all-to-all communication inherently handles synchronization.

Additionally, the DAG construction in Bullshark is leaderless, ensuring perfect symmetry and load balancing among validators. DAG vertices are totally ordered without any extra communication among validators. Instead, each validator independently interprets its view of the DAG structure. Below is an illustration of the Bullshark protocol with n=4 and f=1.

In each odd round of the DAG, there is a predefined anchor vertex (highlighted in solid green above). The primary objective is to determine which anchors to commit first. To achieve a total ordering of all vertices in the DAG, a validator sequentially processes all committed anchors, ordering their causal histories according to a deterministic rule. In the illustration above, the causal history of anchor A2 is marked by green vertices.

In each even round, vertices can cast a vote for the anchor of the preceding round. Specifically, a vertex in round r votes for the anchor of round r−1 if there is an edge connecting them. The commit rule is straightforward: an anchor is committed if it receives at least f+1 votes. In the figure above, Anchor A2 is committed with 3 votes, whereas Anchor A1 only has 1 vote and remains uncommitted.

Due to the asynchronous nature of the network, validators may have different local views of the DAG. Some vertices may be delivered and added to the local DAG view of some validators but not yet to others. Consequently, while some validators may not have committed A1, others might have.

In the example provided, Validator 2 commits anchor A1 after seeing two (f+1) votes for it, even though Validator 1 has not yet committed it. To ensure total order (safety), Validator 1 must order anchor A1 before anchor A2. Bullshark achieves this through quorum intersection.

The commit rule requires f+1 votes, and each vertex in the DAG has at least n-f edges to vertices from the previous round. This guarantees that if any validator commits an anchor A, all future anchors will have a path to at least one vertex that voted for A, and consequently, to A itself.

This leads to the following corollary:

Safe to skip: If there is no path from a future anchor to an anchor A, it is guaranteed that no validator committed A, making it safe to skip A.

The anchor ordering mechanism operates as follows: when an anchor i is committed, the validator checks for a path from anchor i to anchor i−1. If such a path exists, anchor i−1 is ordered before anchor i, and the process is recursively applied starting from i−1. If no path exists, anchor i−1 is skipped, and the validator checks for a path from i to i−2. This process continues, ordering anchors if paths exist and skipping them otherwise, until an anchor that was previously committed is reached, ensuring that all preceding anchors are already ordered.

In the figure above, anchors A1 and A2 do not receive enough votes to be committed. When the validator commits A3, it must determine whether to order A1 and A2. Since there is no path from A3 to A2, according to the "safe to skip" corollary, A2 can be skipped. However, there is a path from A3 to A1, so A1 must be ordered before A3 (it is possible that some validators committed A1).

The validator then checks for a path from A1 to A0 (not shown in the figure) to decide whether A0 should be ordered before A1.

For further details on the specific DAG construction, refer to the Bullshark paper, which provides formal pseudocode and rigorous proofs of Safety and Liveness.