Paper 2025/567

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

Nikita Polyanskii, IOTA Foundation
Sebastian Mueller, Aix-Marseille University
Ilya Vorobyev, IOTA Foundation
Abstract

Uncertified partially synchronous DAG BFT protocols such as Mysticeti achieve the lowest latency among DAG protocols by omitting per-block quorum certificates, but they lack rigorous liveness proofs: honest parties can desynchronize and never commit a leader again, even under synchrony. To avoid the quadratic communication cost of pushing full blocks, production implementations pull missing ancestors, which results in consensus request amplification, large tail latency, and vulnerability to Byzantine dissemination. We present Starfish, whose new Push pacemaker gives uncertified DAGs their first rigorous liveness proof, together with safety proofs and latency bounds in the actual message delay δ. Starfish makes Push practical by separating payloads from headers: parties push headers and Reed-Solomon fragments, data-availability certificates form on the DAG itself, and worst-case payload communication becomes linear, at the cost of increasing transaction latency by one round. We also show how multi-signatures and delayed history pushes can be applied to Starfish and Mysticeti, resulting in new protocols with quadratic happy-case metadata communication, the lowest among partially synchronous DAG BFTs. Without faults, at 100 validators on a synthetic WAN, Starfish sustains ≈257k tx/s at sub-second median latency against Mysticeti's ≈190k. Controlled experiments show that Byzantine selective dissemination can drive honest-transaction median latency under Pull to tens of seconds in both protocols; under Push dissemination, Starfish holds it within about two seconds across the whole fault range, at substantially lower communication cost than Push on Mysticeti. Starfish has replaced Mysticeti on a public blockchain's mainnet. An observational study comparing each validator with itself across the switch finds per-validator consensus requests down 86% and p99 consensus latency down 27%; well-connected validators pay the added round at +16% consensus latency, and bytes sent per sequenced byte rise by 133%.

Note: The protocol Starfish is deployed on IOTA Mainnet

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
DAG-based BFTpartial synchronySMRcommunication complexity
Contact author(s)
nikitapolyansky @ gmail com
sebastian muller @ univ-amu fr
ilia vorobev @ iota org
History
2026-11-03: last of 4 revisions
2025-03-28: received
See all versions
Short URL
https://ia.cr/2025/567
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/567,
      author = {Nikita Polyanskii and Sebastian Mueller and Ilya Vorobyev},
      title = {Making Uncertified {DAG} {BFT} Provably Live with Linear Payload and Quadratic Metadata Communication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/567},
      year = {2025},
      url = {https://eprint.iacr.org/2025/567}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.