Paper 2026/898 Original: eprint.iacr.org/2026/898 ↗

Bluestreak: Uncertified DAG BFT with Sparse Metadata

Abstract

DAG-based Byzantine fault-tolerant (BFT) consensus lets all validators propose concurrently, and uncertified designs such as Mysticeti skip per-block certification to achieve low latency. In existing partially synchronous round-based DAGs that use only hashing and standard signatures, however, every block references a quorum of previous-round blocks, so block metadata grows linearly with the committee size and, even in the happy case, the metadata communicated per round grows cubically. We present Bluestreak, a partially synchronous uncertified DAG BFT protocol that sparsifies block metadata using only hashing and standard signatures. A non-leader block carries at most two references, to its author's previous block and, optionally, to the previous leader; the leader reference is a vote. It may also name the leader of two rounds earlier as certified, a claim that its author has seen $2f+1$ votes for it. Only the single leader block per round references the latest block it knows from each validator, so committing it orders their chains. Because a sparse ancestry cannot justify the claims it carries, a node references a block only after verifying every claim in the block's history, and a pull-based pacemaker fetches the blocks and votes it is missing. We prove safety and liveness under partial synchrony and show that, in the happy case, block metadata amortized over a round is constant, per-round metadata communication is quadratic in the committee size, and, under idealized timing, the average end-to-end latency equals Mysticeti's: 4.5 message delays. In experiments with emulated ten-region wide-area delays, Bluestreak cuts average block metadata from Mysticeti's 13 KB to about 320 bytes at 400 validators, and matches or beats its median end-to-end latency at every committee size from 10 to 400.