Abstract:Transaction ordering attacks extract billions of dollars annually from decentralized finance users in the form of Maximal Extractable Value (MEV). Byzantine Fault-Tolerant (BFT) consensus protocols guarantee total order but place no constraint on how that order is chosen, leaving the door open for adversarial reordering. Batch-order-fairness (batch-OF) protocols close this gap, but existing designs pay a steep performance price for this guarantee. Leader-based protocols such as Themis concentrate all fairness decisions at a single replica, while recent DAG-based proposals FairDAG and DAG of DAGs (DoD) force their fairness layer into strictly serial execution despite running on multi-proposer DAGs.
We present Herring, the first $\gamma$-batch-OF DAG BFT protocol whose fairness layer parallelizes the dominant graph construction cost across committed subdags. Herring combines post-consensus graph construction with explicit missing edge resolution piggybacked on the DAG's reliable broadcast layer, a pairing that turns fair ordering from a per-round serial bottleneck into a CPU-bound task. We also uncover previously unreported liveness vulnerabilities in both FairDAG-RL and DoD that a malicious client can trigger to halt the fairness layer indefinitely, and propose patches that we integrate into our reimplementations.
We implement Herring on top of the Rust implementation of Narwhal \& Tusk and evaluate it against FairDAG-RL, DoD-W, and Themis. Herring tracks the throughput of Narwhal \& Tusk closely up to roughly $10{,}000$\,tx/s, achieves roughly $90\%$ higher saturation throughput than FairDAG-RL and $100\%$ higher than DoD-W, and substantially reduces execution latency at saturation.
| Subjects: | Distributed, Parallel, and Cluster Computing (cs.DC) |
| Cite as: | arXiv:2605.23648 [cs.DC] |
| (or arXiv:2605.23648v1 [cs.DC] for this version) | |
| https://doi.org/10.48550/arXiv.2605.23648 arXiv-issued DOI via DataCite (pending registration) |
From: Marko Putnik [view email]
[v1]
Fri, 22 May 2026 14:00:33 UTC (720 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。