Mysticeti: Latency-Optimal DAG Consensus Protocols and Sub-Second Finality

Mysticeti represents the state-of-the-art breakthrough in Byzantine Fault Tolerant (BFT) consensus algorithms for distributed state machines and blockchain systems. By organizing broadcast transaction blocks into a Directed Acyclic Graph (DAG) round structure and decoupling data dissemination from transaction ordering, Mysticeti achieves theoretical latency-optimal consensus—committing transactions in only 3 network message delays (round-trips) without requiring a designated round leader.

This article details the architectural evolution from traditional PBFT/Raft to DAG-based BFT (Narwhal/Tusk, Bullshark), the mathematical mechanics of Mysticeti's fast commit paths, and failure recovery.

1. Quick-Reference: BFT Consensus Protocol Evolution

+-----------------------------------------------------------------------------------------+
|                               BFT CONSENSUS PROTOCOL EVOLUTION                          |
+-----------------------------------------------------------------------------------------+
| Protocol           | Architecture Model   | Commit Latency (Delays) | Throughput (Txns/sec) | Leader Bottleneck |
+--------------------+----------------------+-------------------------+-----------------------+-------------------+
| Practical BFT (PBFT)| Linear Leader Round | 3 - 5 Message Delays    | < 5,000 / sec         | Severe (O(N^2))   |
| HotStuff (Diem)    | Linear Pipelined     | 7 - 8 Message Delays    | ~ 15,000 / sec        | Moderate (O(N))   |
| Narwhal & Bullshark| DAG Mempool + Leader | 5 - 6 Message Delays    | > 100,000 / sec       | Low (Decoupled)   |
| Mysticeti (Sui)    | Uncertified DAG      | 3 Message Delays (Opt)  | > 150,000 / sec       | None (Leaderless) |
+-----------------------------------------------------------------------------------------+

2. DAG-Based Consensus Foundations: Decoupling Dissemination from Ordering

Traditional consensus protocols (PBFT, Raft) force the leader to both propose the payload and coordinate consensus votes simultaneously, creating high bandwidth choke points at the leader.

DAG-based consensus decouples these responsibilities into two independent layers:

Data Dissemination Layer (DAG Mempool): All $N$ validator nodes continuously broadcast signed blocks of transactions in parallel rounds. Each block at Round $R$ cites $\ge 2f + 1$ block hashes from Round $R-1$ .
Consensus Ordering Layer (Zero Overhead): Validators locally traverse the DAG structure to deterministically linearize transactions without exchanging a single additional network consensus message!

DAG Block Hierarchy (Round R to Round R+2):
Round R+2:  [ Block A₂ ] -------- [ Block B₂ ] -------- [ Block C₂ ]
                \     \            /    |    \            /     /
                 \     \----------/-----+-----\----------/     /
Round R+1:        [ Block A₁ ]      [ Block B₁ ]      [ Block C₁ ]
                       \              /     \              /
Round R:               [ Block A₀ ]  [ Block B₀ ]  [ Block C₀ ]

3. Mysticeti's 3-Round-Trip Latency-Optimal Commit Path

In earlier DAG protocols (Narwhal/Bullshark), validators had to wait for threshold signatures ( $2f + 1$ certificates) at each round before advancing, adding 2 round-trips per DAG layer.

Mysticeti eliminates round certificates:

Validators propose blocks directly upon receiving raw blocks from $\ge 2f + 1$ peers.
A block at Round $R$ achieves commit finality as soon as it receives indirect support from a quorum of blocks at Round $R+2$ .
Total Commit Latency: Exactly 3 network message delays ( $1.5$ round-trips), which is the proven theoretical lower bound for asynchronous BFT consensus.

4. Byzantine Fault Tolerance and Safety Proofs

In a system of $N = 3f + 1$ validator nodes:

The protocol guarantees Safety (zero conflicting transaction linearizations) even if up to $f$ nodes are maliciously colluding (Byzantine).
The protocol guarantees Liveness (continuous transaction commits) under partial synchrony once the Global Stabilization Time (GST) is reached.

References

Danezis, G., et al. (2023). Mysticeti: Low-Latency DAG Consensus with Fast Path. arXiv preprint.
Danezis, G., et al. (2022). Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus. EuroSys.
Castro, M., & Liskov, B. (2002). Practical Byzantine Fault Tolerance and Proactive Recovery. ACM TOCS.