Citation

Putnik, M., Decouchant, J. “Herring: Parallel Batch-Order-Fairness on DAG-based Blockchain Consensus.” arXiv:2605.23648v1 [cs.DC] (22 May 2026). Delft University of Technology.

Core Contribution

Herring is the first γ-batch-order-fairness DAG BFT protocol whose fairness layer parallelizes the dominant graph-construction cost across committed subdags, instead of running it as a per-round serial bottleneck. Order-fairness adds a safety constraint on how the total order is chosen (mitigating reordering MEV); prior designs paid heavily for it.

The Problem

  • BFT consensus guarantees total order but not which order → leaders reorder/delay for MEV.
  • Themis (leader-based) retrofits batch-OF onto HotStuff but is capped by the single-leader bottleneck (one replica collects all local orderings + computes global fair order).
  • FairDAG-RL builds the dependency graph post-consensus but processes one subdag at a time (fairness layer becomes the bottleneck even when the DAG runs fast).
  • DoD (DAG of DAGs) builds the global-order graph pre-consensus and embeds it in each vertex — an O(b²) op (b = batch size) on the DAG’s critical path, throttling round progression.

How Herring Works

  • Post-consensus graph construction (DAG runs at full speed) + explicit missing-edge resolution via FairUpdate votes that piggyback on workers’ outgoing batches and travel through Narwhal’s reliable broadcast, so each parked graph accumulates its resolutions independently and all fairness work sits off the DAG critical path → turns fair ordering from a serial bottleneck into a CPU-bound, parallelizable task.
  • Fairness-layer CPU profile (Fig.): graph weights (~194 ms) and tarjan + topo sort dominate; extract (~64 ms), update (~4.4 ms) — these are what Herring parallelizes across subdags.

Headline Results

  • Implemented on the Rust Narwhal & Tusk; evaluated vs FairDAG-RL, DoD-W, Themis.
  • Tracks Narwhal & Tusk throughput closely up to ~10,000 tx/s.
  • ~90% higher saturation throughput than FairDAG-RL; ~100% higher than DoD-W; substantially lower execution latency at saturation.
  • Identifies and patches previously unreported liveness bugs in both FairDAG-RL and DoD that a malicious client can trigger to halt the fairness layer indefinitely.
  • Adversarial eval: confines adversarial reordering to only the most fragile transaction pairs.

Connection to Wiki

See Also