Paper 2025/567

Making Uncertified DAG BFT Provably Live with Linear Payload and Quadratic Metadata Communication

Abstract

Uncertified DAG-based BFT protocols, such as Mysticeti and Cordial Miners, achieve state-of-the-art latency by eliminating per-block quorum certificates. However, they have lacked rigorous liveness proofs, and recent work has demonstrated explicit desynchronization attacks where honest parties fail to commit leaders after Global Stabilization Time (GST). We present Starfish, an uncertified DAG-based BFT protocol that closes this gap with a new Push pacemaker. This mechanism ensures party synchronization after GST by requiring parties to create their own blocks before advancing rounds and introducing a safe “catch-up” condition for slow parties. To address scalability, Starfish decouples payload from metadata: block headers carry only commitments to Reed-Solomon-encoded fragments, and data availability is certified directly on the DAG via Data Availability Certificates (DACs). This achieves order-optimal worst-case linear payload communication while increasing sequencing latency by only one round. We further propose Starfish-L, combining multi-signatures with a Lazy-Push pacemaker to reduce metadata communication from quartic to cubic in the worst case and quadratic in the happy case. Applying these techniques to Mysticeti yields Mysticeti-L, which matches Mysticeti's low latency while achieving quadratic metadata and linear payload communication costs in the happy case. Finally, we provide full safety and liveness proofs and derive latency bounds in terms of the actual message delay.

Note: -Increased a timeout in the lazy push pacemaker -Loosen the assumption of threshold signatures to multi-signatures