DAG-Based BFT Consensus and Leader-Based BFT

DAG-based BFT uses every validator for parallel data dissemination, reducing leader-centered bandwidth limits while adding round and data-availability costs.

Where crash faults and Byzantine faults diverge

The first thing to settle when picking a consensus protocol is which failures it must survive. Crash fault tolerance (CFT) covers nodes that stop or fail to respond. Byzantine fault tolerance (BFT) also covers nodes that sign conflicting values with their own keys or otherwise deviate arbitrarily.

The standard authenticated BFT model assumes an adversary cannot forge an honest node's signature. CFT uses 2f+1 nodes and BFT uses 3f+1; their ratio approaches 1.5 as f grows. BFT also pays for authentication and equivocation detection.

The phrase "no leader" appears in both models but means different things. Leaderless protocols in the crash model, such as EPaxos and Accord, trust the content of a quorum of responses once those responses arrive. In the Byzantine model, the response itself may be false. The protocol must also prevent equivocation: one node sending different values to different peers. This post deals with the second case.

The throughput ceiling one leader sets

The archetype of leader-based BFT is PBFT, presented by Castro and Liskov at OSDI 1999. A primary assigns a sequence number to each request, and the replicas then run three phases: pre-prepare, prepare, and commit. The last two phases have replicas talking to each other, so normal-case message count grows as O(n²).

HotStuff (Yin et al., PODC 2019) lowered that cost. Threshold signatures compress quorum votes into a single quorum certificate. This reduces per-phase messages to O(n) and also makes leader replacement linear. The consensus layer of Diem was built on this structure.

The per-phase message count dropped, but votes still converge on the leader and the leader broadcasts the certificate. In implementations where the leader also disseminates transaction payloads, its uplink can limit throughput. Leader-based protocols with information dispersal or a separate availability layer can reduce this bottleneck, so a leader alone does not imply one fixed ceiling.

Separating dissemination from ordering with a DAG

Narwhal (Danezis et al., EuroSys 2022) attacks this bottleneck by splitting the layers. A mempool layer spreads transaction batches, and a separate consensus layer decides their order. Inside the mempool layer, every validator broadcasts its own batch at the same time. The protocol therefore uses the bandwidth of the whole network.

The structure that accumulates in the process is a directed acyclic graph (DAG). Each validator produces one vertex per round, and a vertex carries a batch hash together with references to vertices from the previous round.

vertex(v, r) = {
  hash of the transaction batch,
  2f+1 references to round r-1 vertices,
  signature of validator v
}

In this certified-DAG family, a valid proposal references n-f=2f+1 certificates from the previous round. Such a quorum contains at least f+1 honest nodes, and two quorums intersect in at least one honest node. The protocol can therefore advance without waiting for up to f slow or unresponsive nodes.

flowchart LR
  subgraph R1["Round r-1"]
    A1["Validator A<br/>vertex"]
    B1["Validator B<br/>vertex"]
    C1["Validator C<br/>vertex"]
    D1["Validator D<br/>vertex"]
  end
  subgraph R2["Round r"]
    A2["Validator A<br/>vertex"]
    B2["Validator B<br/>vertex"]
  end
  subgraph R3["Round r+1"]
    ANC["Anchor vertex"]
  end
  A1 --> A2
  B1 --> A2
  C1 --> A2
  B1 --> B2
  C1 --> B2
  D1 --> B2
  A2 --> ANC
  B2 --> ANC

Each node decides the order by reading this graph. Bullshark (Spiegelman et al., CCS 2022) picks one anchor vertex per round using a deterministic rule. Once an anchor is committed, every vertex it references directly or indirectly, meaning its entire causal history, enters the total order at once.

This computation costs no additional messages. Honest nodes eventually observe the same DAG, so running the same rule locally yields the same order on every node. Ordering turns from a communication problem into a local interpretation problem.

Mysticeti (arXiv 2310.14821, NDSS 2025) removed the certificates from this picture. It skips the step of collecting quorum signatures into a certificate for each vertex and makes its decisions directly on an uncertified DAG. Commit latency drops by the amount of certification overhead that disappears.

Measured throughput and latency

These figures support comparisons only within each paper's baselines and environment. A single-data-center CFT result from etcd cannot be compared directly with geo-distributed BFT latency to declare one protocol family dominant.

Shoal++ separates certified-DAG latency into queueing, anchoring, and anchor commit. Parallel dissemination can raise throughput, while round count and message delay still determine commit latency. The trade must therefore be measured under the same network and fault model.

The cost that shows up under failure

A single slow node does not necessarily delay the whole round. A protocol can skip up to f nodes once it has 2f+1 valid proposals or certificates out of 3f+1. Delay grows when the fastest 2f+1 cannot form a quorum or when causal history needed for commit is unavailable.

flowchart TD
    A["Collect round proposals"] --> B{"Have 2f+1 valid items?"}
    B -->|Yes| C["Advance round and evaluate commit rule"]
    B -->|No| D["Fetch missing data or wait for timeout"]
    D --> B
    C --> E{"Required causal history available?"}
    E -->|Yes| F["Finalize order locally"]
    E -->|No| D

Fetching missing vertices is a second problem. A node with a reference but without the body needed for commit must request the data. Certified DAGs can keep some synchronization off the critical path, but a missing causal history still delays commit when it is required.

Anchor selection frequency carries the same tension. Choosing anchors more often shortens commit latency. It also raises the chance that validators hold divergent DAG structures, which increases retransmission of missing vertices. Shoal++ (arXiv 2405.20488) eases this tension by pipelining anchors so that they overlap.

Shoal++ attacks the three latency components with faster anchor commit, dynamically increased anchors, and several staggered DAGs. The paper reports up to 60% lower common-case latency than Bullshark and up to 10x lower failure-case latency than Mysticeti. Both comparisons apply to the paper's own testbed.

Angelfish (arXiv 2509.15847, 2025) changes the structure itself according to load. Under low load, it uses lightweight voting over best-effort broadcast to keep latency down. Under high load, it switches to full DAG vertex broadcast to raise throughput. The design moves between leader-based and DAG-based operation as the load dictates.

What to pick and when

The first fork is the trust boundary. CFT can meet the requirement when one operator controls every node and only crash or omission faults need coverage. BFT is required when operators differ or arbitrary node behavior must also be tolerated.

If BFT is required, the next questions are the load range and dissemination path. At low or moderate load, a leader-based design can commit in fewer message delays. Once leader-centered data dissemination saturates at high load, a DAG or separate distributed availability layer can widen throughput.

A DAG decision should not come from one TPS threshold quoted from a paper. Transaction size, validator count, inter-region RTT, and packet loss must resemble the evaluation before its curve applies. Uneven bandwidth or frequent missing data reduces the gain from parallel dissemination.

If load swings widely by time of day, a hybrid direction such as Angelfish is worth watching. Most protocols in the DAG family are still at the research stage or tied to one chain implementation. Check implementation maturity separately before adoption. SoK: DAG-based Consensus Protocols (arXiv 2411.10026) is a reasonable starting point for surveying the whole family.

Summary

The trust boundary determines whether BFT is needed, while load and dissemination structure guide the choice within BFT. Leader-centered dissemination favors low latency but can saturate one uplink. A DAG uses the validators' aggregate dissemination bandwidth and adds queueing and anchor-commit delay.

Raft and DAG-BFT results from different environments do not establish a direct ranking. One slow node can be skipped while 2f+1 valid items remain available; a round slows when the quorum or required causal history is missing. Compare leader-based, DAG-based, and hybrid designs on the same network and fault model before choosing one.