Paper 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.

Note: Major revision; title changed from "Bluestreak: Scaling DAG BFT by Sparsifying Metadata". Reformatted in LNCS with appendices. Rewritten introduction and abstract; revised presentation of the sparse block format, the commit rule, and the pull-based pacemaker. Safety and liveness theorems are now stated in the body, and the liveness proof gains a round-progress lemma. New comparison table of certified and uncertified DAG protocols (Bullshark, Sailfish++, Clownfish, Autobahn, Mysticeti, Mysticeti-L) with happy-case and crash-fault latency, per-round metadata communication, and required signatures. The evaluation adds Autobahn to the committee-scaling experiment and a per-block metadata breakdown; throughput, crash-fault, and stability results and the related work moved to the appendix. New appendix measuring the metadata share on Sui Mainnet.