Three Futures for Uncertified DAGs

In blockchain consensus, one of the most important technical lines to watch over the past three years has been the evolution of DAG-based BFT. It does not have the flashy mathematical surface of ZK, nor the capital-market narrative of restaking, but it directly determines how long a transaction takes to become final. Mysticeti is a watershed on that line. The interesting part is that after Mysticeti, the path split in two.

This note answers three questions: what makes Mysticeti v1 elegant, where it falls short, and how Sui's Mysticeti v2 and IOTA's Starfish repair it in different directions. To understand that fork, we first need to understand the thing both paths gave up, and then tried to recover in different ways: certification.

Chapter 01Back to the starting point: certified DAG cost structure

To understand Mysticeti's trick, first look at what it replaced.

The previous generation of DAG-based consensus was represented by Narwhal + Bullshark. Its DAG is a certified DAG: every block first collects 2f+1 signatures and forms a quorum certificate before blocks in the next round can reference it. In other words, in the graph the consensus protocol actually runs on, every vertex is already a certificate.

This design gives two useful properties almost "for free." The first is equivocation-freedom: a Byzantine validator cannot get two conflicting blocks certified at the same time, because honest nodes will not sign both conflicting versions. The second is block availability: a certificate proves that 2f+1 validators hold the block, so at least f+1 honest validators have it and can serve the data back to anyone who needs it.

But those supposedly free properties are expensive. Each certification is itself a reliable broadcast that costs a full round trip, and each block requires O(n) signature-generation and verification work. Bullshark can commit a leader every two rounds, but once certification is included, the end-to-end latency of a leader block reaches about six message delays. For a chain that wants real-time user experience, that is a heavy tax.

Chapter 02Mysticeti v1's bet and three elegant ideas

After certification is removed, the DAG structure itself becomes the certificate.

Mysticeti's core decision is to run on an uncertified DAG. A block is signed once by its proposer and then broadcast directly. The DAG advances by receiving n−f blocks, not by certifying n−f signatures. That one-word difference removes the whole round trip and O(n) signature overhead of a certified DAG.

Once certificates disappear, equivocation-freedom and availability are no longer free. Mysticeti has to recover safety with something else. Its answer is to let the DAG structure itself act as a virtual certificate.

Idea 1A reference is a vote

In Mysticeti, when you propose your next-round block, you list all previous-round blocks you have seen as parents. That parent link is not just a record saying "I saw you." It is also a vote. You do not send a separate vote message; voting is woven into the DAG edges. This is the key intuition behind the communication savings: voting becomes a byproduct of the DAG.

Idea 2The direct decision rule

Without certificates, how do we decide whether a block should commit? Mysticeti's direct decision rule turns the question into finding a particular two-layer shape in the DAG:

In plain English: "I see a quorum of witnesses claiming they saw this block, and I see another quorum of confirmations proving those witness claims are stable." This is PBFT's classic prepare / commit intuition, except every vote is a DAG edge and no extra vote message is sent.

Idea 3Multi-proposer pipelining and crash-fault masking

Bullshark has only one proposer slot every two rounds, which naturally raises latency. Mysticeti turns every (validator, round) into a potential proposer slot, and every block is first-class: it can be proposed directly and decided directly by the decision rule. Commits happen every round, not once per wave.

Pipelining has a weak point: it only stays smooth when every proposer slot commits on time. If a slot's leader crashes, a naive protocol stalls and later blocks wait behind it. Mysticeti addresses this with a skip rule: if 2f+1 blocks at round R+1 do not reference B, B is marked to-skip. If neither direct commit nor skip can decide, an indirect rule lets B inherit the decision of a later anchor that has already been directly decided.

Taken together, these ideas gave Mysticeti v1 a strong production result: compared with Bullshark, Sui mainnet latency dropped by about 80% (roughly 1900ms → 400ms), consensus CPU cost fell by about 40%, and 3δ good-case latency was achieved in 99% of cases. Mysticeti really did "reach the latency limits."

Chapter 03What was missing: the thing that got traded away

Removing certification traded away more than one thing.

This is the key section of the analysis. The weakness of an elegant protocol is often not what it got wrong, but what it quietly gave up to obtain its main advantage. What Mysticeti v1 gave up is exactly what v2 and Starfish later try to repair.

Gap 1No strict liveness proof — and a real attack exists

The original Mysticeti paper rigorously proves safety, even under asynchrony, but its liveness argument is weaker. It only guarantees liveness for one primary block per round after GST, and it requires validators to wait for a timeout. Later research gives a concrete counterexample: a desynchronization attack can make honest nodes permanently lose synchronization and stop committing, even after the network has recovered after GST.

The root cause is subtle. Mysticeti's round advancement lets honest nodes move forward without producing their own block for that round. This leaves holes in the DAG. Too many holes, and the protocol can no longer form the 2f+1 witness / confirmation pattern needed to commit a leader. The independent Yale FLINT Group also points out that Mysticeti's round-jumping behavior is under-specified and must be carefully restricted to preserve liveness.

Gap 2Block availability sits on the critical path

In a certified DAG, the certificate itself is an availability proof. In an uncertified DAG, there is no such proof. When a validator references a block it has seen but others have not, the validators missing it have to fetch it. Mysticeti uses pull synchronization: if a parent is missing, request it. Under load, pull synchronization self-amplifies. Slow validators send more requests, fast validators burn more bandwidth answering them, and the network is busiest exactly when the protocol most needs to recover.

Gap 3Metadata explosion and full storage at scale

The Starfish paper quantifies this brutally: with 120 validators running a Mysticeti DAG at 20 rounds per second, uncompressed metadata can grow to about 1 TB in 24 hours, and worst-case metadata bandwidth can reach about 10 Gbps. Add the fact that every validator stores the full transaction payload of every block, with no erasure coding, and you get a real scaling wall.

Gap 4The Sui integration gap

There is also a gap outside the protocol itself, in how the protocol is used. Even if Mysticeti reaches optimal latency in the consensus layer, Sui transaction processing has a separate pre-consensus step: validators first vote on whether a transaction is eligible to enter consensus. This step requires each transaction to collect a quorum of BLS signatures. It is CPU-expensive, because 2f+1 stake worth of validators must sign every transaction, and it raises latency for non-fastpath transactions. Mysticeti's theoretical optimum is therefore not fully realized in production.

Chapter 04The fork: one protocol, two directions

Before Starfish, IOTA was also running Mysticeti.

Before comparing the two paths, one easily missed fact matters: this is not a competition between two unrelated protocols. Before Starfish, IOTA's production environment was already running Mysticeti-C, the single-leader-per-round version. In IOTA's official IIP-2 proposal, Starfish is described as an enhanced DAG-based consensus protocol based on Mysticeti.

So the more accurate picture is this: Sui and IOTA start from the same base protocol and evolve along two orthogonal axes. Mysticeti v1's single trade-off — giving up certification for latency — opened the gaps above. Group those gaps and you get two directions: Sui repairs the integration-redundancy gap; IOTA repairs the robustness gaps around liveness, dissemination, and metadata.

Chapter 05The Sui path: Mysticeti v2

The consensus core is near-optimal; the waste sits in the surrounding layer.

Mysticeti v2's core claim is simple: the consensus engine itself is fine; the layer to cut is Sui's pre-consensus transaction-validation layer. v2 moves transaction validation directly into the consensus flow.

Mechanically, this is an elegant reuse of the same shape. The Mysticeti commit rule originally applied to blocks: commit or skip a proposer slot. v2 conceptually extends the same idea so it can be applied in parallel to every transaction. Each transaction is finalized or rejected independently on the same DAG, while block commit / skip proceeds in parallel.

On the client side, v2 replaces the old Quorum Driver with the Transaction Driver. The old Quorum Driver broadcasts each transaction to all validators, collects BLS signatures, broadcasts the certified transaction again, and then collects results from all nodes. The new Transaction Driver sends the transaction to one selected validator, obtains its consensus position, and retrieves complete effects from a quorum. Validators batch validity signatures into consensus-block signatures instead of signing transaction by transaction.

The reported effect is about a 35% full-node latency drop in Asia (1.00s → 0.65s) and about 25% in Europe (0.55s → 0.40s). Starting with Sui node v1.60, v2 and the Transaction Driver are the default. The important caveat is that v2 does not treat liveness / desync as the headline problem. Its main axis is "remove a layer, chase product latency."

Chapter 06The IOTA path: Starfish

Agreement itself is fine; dissemination and liveness underneath it are the fragile pieces.

Starfish takes the opposite angle. The agreement problem itself is not the weak point. The fragile layer is the one underneath it, often treated as plumbing even though it shapes the whole protocol: dissemination. Starfish also directly targets the missing strict liveness proof. It responds with four design moves.

Move 1Separate metadata from payload

Starfish splits a block into a small header and a heavy payload. The header contains references, votes, acknowledgments, and commitments — the things consensus needs immediately. The payload contains the transaction data itself. Headers can be pushed aggressively; payloads do not have to be fully pushed everywhere. The consensus critical path becomes lighter.

Move 2Reed-Solomon erasure coding

A block's transaction data is encoded with Reed-Solomon code into n fragments, one per validator, with enough redundancy that any f+1 valid fragments can reconstruct the full payload. Each validator broadcasts the full payload for its own block, but for other validators' blocks it shares only one encoded shard. IOTA calls this Encoded Cordial Dissemination.

The threshold is easy to mix up: the reconstruction threshold is f+1 fragments, not 2f+1. The 2f+1 threshold appears at the availability-certificate layer. If 2f+1 validators acknowledge availability, then even if f are Byzantine, at least f+1 honest validators still hold valid fragments — exactly enough to reconstruct the payload.

Move 3Data Availability Certificates grow on the DAG

This is the most elegant part of the design. A validator acknowledges in its own header that it has verified the payload of an earlier block. Once such acknowledgments accumulate to 2f+1, and all of them are reachable in the causal history of a later committed block, that later block itself becomes the earlier payload's Data Availability Certificate (DAC). No extra availability round is bolted on; availability accumulates naturally as the DAG grows.

Move 4Push pacemaker

For the liveness gap, Starfish uses a Push pacemaker. The intuition fits in one sentence: you cannot move forward empty-handed. A validator must first produce its own block for the current round before advancing to the next. A lagging validator must first see a quorum of current-round blocks before catching up. This closes the hole where honest nodes advance rounds without producing blocks and leave gaps in the DAG. With this, Starfish provides the first strict liveness proof for uncertified DAGs.

One detail matters: the Starfish that IOTA took to mainnet is only one of three protocols in the paper. The paper proposes Starfish, Starfish-L, and Mysticeti-L. Starfish provides the first strict liveness proof for uncertified DAGs and achieves order-optimal linear payload communication; Starfish-L and Mysticeti-L further reduce metadata communication in the happy case.

Chapter 07Synthesis: three Pareto points

The same design space, shaped by different business theses.

Put the three together, and the sharpest observation is this:

The certificate Starfish brings back is not the certified-DAG style certificate that is synchronous and per block. It is a Data Availability Certificate lazily accumulated on the DAG. Starfish is therefore a synthesis: it recovers the safety / availability properties of certified DAGs without paying the per-block round-trip cost of certified DAGs. "Uncertified" was never a binary switch. It is a spectrum, and Starfish finds a new point on that spectrum: safer than Mysticeti, cheaper than Bullshark.

Mysticeti v2 goes in the opposite direction. It doubles down on being uncertified and does not touch the dissemination philosophy inside the consensus core. Instead, it targets costs outside consensus: Sui's pre-consensus transaction-validation layer.

The final judgment should not be "who wins." They were never playing the same game. Sui is a consumer, DeFi, high-TPS chain; latency and throughput are its product, and Mysticeti v2 is faithful to that positioning. IOTA is betting on enterprise, regulated, trade-and-logistics infrastructure; predictability and formal guarantees under degraded conditions are its product, and Starfish accepts a latency tax for robustness. Protocols fork because business theses fork first.