DAG-Based BFT Consensus and Leader-Based BFT

In a Byzantine setting, the throughput ceiling is set by the uplink of one leader machine, not by the consensus algorithm.

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 only nodes that stop or fail to respond. Byzantine fault tolerance (BFT) also covers nodes that forge signatures or send a different value to each peer.

The difference shows immediately in quorum size. CFT needs 2f+1 nodes to tolerate f failures, while BFT needs 3f+1. That is 1.5 times the machines for the same fault tolerance, plus the cost of verifying a signature on every message.

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 a lie, and the protocol must also prevent equivocation, where one node sends a different value 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 the votes of a quorum into a single quorum certificate, which brings per-phase messages down to O(n) and makes leader replacement linear as well. The consensus layer of Diem was built on this structure.

The message count dropped, but the shape of the communication did not. Every message still travels through the leader in a star pattern, and the leader also pushes transaction payloads out to the remaining replicas. Cluster throughput therefore stops at the uplink bandwidth of one machine, while the uplinks of the other nodes sit mostly idle.

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, so the protocol uses the bandwidth of the whole network rather than one link.

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
}

A validator advances to the next round only after gathering 2f+1 references. That number is the minimum that guarantees a majority of honest nodes have already seen the referenced vertices. The f slowest nodes are skipped rather than waited for.

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

The experimental setups differ across these papers, so the table should be read as an order-of-magnitude comparison rather than a direct one. The Raft row is a CFT number that assumes no Byzantine behavior at all.

Going from 10 to 50 replicas splits the two DAG protocols in opposite directions. Bullshark holds its throughput, while Mysticeti falls from roughly 300K tps to roughly 100K tps. The benefit of dropping certificates shrinks as the validator set grows.

On the latency axis, the CFT side dominates. Raft in etcd reports a p50 near 5 ms where the DAG protocols sit in the hundreds of milliseconds. A DAG advances in rounds and waits several rounds for an anchor to commit, so commit latency accumulates as a multiple of the round time.

Placing both axes side by side, a DAG trades latency away to buy throughput. For any workload that does not need to push hundreds of thousands of transactions per second, that trade is a loss.

The cost that shows up under failure

The round structure of a DAG is strong in the normal case and weak under failure. When a single node slows down or stops, the next round of vertices waits on references to that node, and the entire round slips by that amount. The 2f+1 reference rule lets the protocol skip up to f nodes, but progress stalls once more than that becomes unstable.

Fetching missing vertices is a second problem. A node that received a reference but not the vertex body has to request it separately, and that round trip lands on the critical path. Network reliability and the degree of synchronization between nodes end up governing performance more than the protocol itself does.

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++ reports improvements along two axes. It cuts common-case latency by up to 60% against Bullshark. It also adds an optimistic fast path that routes around slow nodes on a timeout, which cuts failure-case latency by up to 10x against Mysticeti. The larger gap on the failure case shows where the DAG family was weakest.

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, and 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. On in-house infrastructure or a single cloud account where every node is operated by one party, BFT is unnecessary. A CFT store such as etcd or ZooKeeper is the better choice, and it saves the cost of 3f+1 nodes and signature verification.

If BFT is required, the next question is target throughput. With a validator set in the tens and a load below tens of thousands of transactions per second, leader-based BFT in the HotStuff family is easier to implement and operate. There is only one state machine to reason about and debug, and commit latency is shorter than in the DAG family.

DAG-based BFT becomes the realistic choice above hundreds of thousands of transactions per second, or when validators are spread across regions. Here, the infrastructure needs checking before the algorithm does. Uneven bandwidth between validators or frequent packet loss makes missing-vertex requests common, and the advantage of the DAG disappears with them.

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, so the maturity of the implementation needs a separate check before adoption. SoK: DAG-based Consensus Protocols (arXiv 2411.10026) is a reasonable starting point for surveying the whole family.

Summary

The trust boundary decides whether to use BFT, and target throughput decides which BFT to use. HotStuff brought the message complexity of leader-based BFT down to O(n). Transaction payloads still flow through the leader, so the leader uplink remains the throughput ceiling. DAG-based BFT removes that ceiling by separating dissemination from ordering, and it derives the order through local computation instead of extra communication.

The price is latency. Where Raft reports a p50 near 5 ms, DAG protocols spend hundreds of milliseconds, and one slow node delays an entire round. Shoal++ and Angelfish are two attempts to reduce that price, and whichever one is chosen, the network quality between validators decides whether the published numbers reproduce.