Herring: Parallel Batch-Order-Fairness on DAG-based Blockchain Consensus Marko Putnik
Jérémie Decouchant
Delft University of Technology, The Netherlands [email protected]
Delft University of Technology, The Netherlands [email protected]
arXiv:2605.23648v1 [cs.DC] 22 May 2026
Abstract
To close this gap, a recent line of work [20, 19, 41, 6, 21, 9] has introduced the notion of order-fairness (OF) as an additional safety property for BFT consensus, proposing several definitions that differ in strength and tractability. Among these, 𝛾-batch-order-fairness (batch-OF) [20] has emerged as the most practical yet meaningful choice, and it guarantees that whenever a fraction 𝛾 of the replicas locally receive a transaction tx before another transaction tx ′ , then all honest replicas must deliver tx no later than tx ′ . The Themis leader-based protocol [19] demonstrated that batch-OF can be retrofitted onto HotStuff [38] with standard liveness. However, leader-based OF protocols remain fundamentally capped by the single-leader bottleneck of their underlying consensus engine, where one replica must collect all local orderings, compute the expensive global fair ordering, and drive consensus. DAG BFT protocols [10, 17, 33, 32, 2, 3, 13] eliminate this bottleneck by allowing replicas to propose vertices concurrently, achieving substantially higher throughput. Beyond throughput, DAG BFT protocols also tolerate faulty leaders gracefully, as the DAG continues to grow at full rate even with faulty replicas, with only the commitment being temporarily delayed. Two recent proposals have brought batch-OF to DAG-based BFT. FairDAG-RL [14] constructs global dependency graphs after each subdag is committed (postconsensus) and resolves missing edges implicitly, using ordering indicators deposited in later committed subdags. DoD [26] takes the opposite approach, constructing the global dependency graph before consensus and embedding it in the payload of each DAG vertex. While both protocols improve upon Themis in raw throughput by leveraging the multi-proposer DAG design, each of them serializes sub-DAG execution that prevents them from approaching the throughput of their underlying DAG consensus. Problem. Although FairDAG-RL and DoD differ in where graph construction occurs, both protocols force their fairness layers into strictly serial, round-by-round execution, just at different points in the pipeline. In DoD, the global-order graph is constructed as part of the DAG vertex creation process. This is an 𝑂 (𝐵 2 ) operation (where 𝐵 is the batch size) that sits on the critical path of every DAG round. The DAG cannot advance to the next round until the fairness computation completes, directly throttling the DAG’s otherwise fast round progression. In effect, DoD inherits the high-throughput potential of DAG-based consensus only to immediately surrender it by embedding the most expensive fairness operation on the DAG’s critical path. In FairDAG-RL, graph construction happens after consensus, so the underlying DAG runs at full speed. However, the fairness layer still processes one subdag at a time, leaving the rest of the validator’s CPU idle and forcing fair ordering to become the system bottleneck even when the DAG runs comfortably. Where the fairness layer actually spends its time. The fairness layer in both FairDAG-RL and DoD inherits the same high
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. Batchorder-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 𝛾-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. Our adversarial evaluation shows that Herring confines adversarial reordering to only the most fragile transaction pairs, a robustness that stems from the combination of its batch-OF guarantees and the underlying DAG’s dissemination layer.
1
Introduction
Decentralized Finance (DeFi) has grown into a multi-billion-dollar ecosystem built on top of permissionless blockchains, where the order in which transactions are committed often determines who profits and who pays. Transaction ordering attacks such as frontrunning, back-running, and sandwich attacks have stolen billions of dollars from ordinary users in the form of Maximal Extractable Value (MEV) [5, 8]. Byzantine Fault-Tolerant (BFT) consensus protocols [7, 38, 10] guarantee that all honest replicas agree on a single total order of transactions, but place no constraint on how that order is chosen relative to the order in which transactions arrived at the network. This gap has been extensively exploited. In leader-based protocols such as HotStuff [38], a leader can unilaterally reorder or delay transactions within its block without violating any consensus property. 1
Marko Putnik and Jérémie Decouchant
so that all fairness work sits off the DAG’s critical path. Inspired by Themis [19], Herring resolves missing edges explicitly 1 via FairUpdate votes that piggyback on workers’ outgoing batches and travel through Narwhal’s reliable broadcast, so that each parked graph accumulates its resolutions independently. Table 1 summarizes the key design differences between Herring, FairDAG-RL and DoD. Overview and Contributions. As a summary, this paper makes the following contributions: • We present Herring, the first batch-OF DAG BFT protocol that parallelizes global graph construction across committed subdags, by combining post-consensus graph construction with explicit missing edge resolution that piggybacks on Narwhal’s existing batch dissemination. • We identify and analyze previously unreported liveness bugs in the fairness layers of both FairDAG-RL [14] and DoD [26]. For each bug we give a concrete trigger scenario, propose a patch, and integrate the patch into our reimplementations so that both baselines actually run to completion in our evaluation (Appendix B). • We prove that Herring satisfies 𝛾-batch-OF, together with the standard safety and liveness properties of its underlying DAG BFT consensus. • We implement Herring on top of the Rust implementation of Narwhal & Tusk [10] and evaluate it against FairDAG-RL, DoD-W, and Themis across a range of workloads, network sizes, and fairness parameters. Herring tracks the throughput of its underlying DAG consensus closely up to 10,000 tx/s, sustains roughly 90% higher saturation throughput than FairDAG-RL and 100% higher than DoD-W, and achieves up to 75% lower execution latency than both DAG-based baselines. • We demonstrate Herring’s structural resistance to Byzantine collusion by comparing it against Themis under the reversing order adversarial strategy of Kelkar et al. [19], showing that Herring confines adversarial reordering to only the most fragile transaction pairs.
Average CPU time (ms)
193.9
200
150
100 63.9
50 21.9 4.4
0
weights tarjan + topo sort extract
update
Task
Figure 1: Average CPU time per phase of FairDAG-RL’s fairness layer, broken down by the four FairPropose phases of extract local orderings, pairwise weight matrix computation, Tarjan plus topological sort, and result update. The pairwise weight phase dominates total cost.
level structure as the Themis FairPropose algorithm. Each committed subdag goes through four phases on the fairness processor: (i) extracting the per replica local orderings from the subdag’s certificates, (ii) building the pairwise weight matrix that records how many replicas place each pair of transactions in each direction, (iii) running Tarjan and topological sort on the resulting dependency graph, and (iv) applying the result back to cumulative state. To understand what makes serial execution so costly in practice, we measured per task CPU time across these four phases in FairDAGRL and Figure 1 shows the result. The pairwise weight matrix alone per committed subdag consumes more than three times the cost of Tarjan plus topological sort and almost an order of magnitude more than the extraction and result handling steps combined. The weight phase is also the only phase whose cost scales quadratically with the size of the active vertex set, which itself grows with throughput. A serial fairness layer that finalizes one subdag at a time therefore spends most of its wall clock time on the expensive weight matrix calculation and leaves the other CPU cores idle. This observation, that the dominant cost is exactly the part of the algorithm that has no cross subdag data dependency, is what motivates Herring’s central design choice. Solution. In this paper we present Herring, a batch-OF DAG BFT protocol built on top of Narwhal & Tusk [10], whose central design insight is that the dominant per-subdag graph construction cost can be made parallel across committed subdags, with the remaining cross subdag work confined to a small number of synchronization points. Herring exploits this insight by running graph construction tasks for multiple committed subdags concurrently on a thread pool, turning OF from a per-round serial bottleneck into a CPUbound task that scales with the number of available validator cores. Two supporting design choices keep this parallelism sound. Like FairDAG-RL, Herring builds its dependency graphs post-consensus,
2
Background
This section introduces the two foundations Herring builds on: 𝛾batch-OF, the fairness property Herring guarantees, and Narwhal & Tusk, its underlying DAG BFT consensus.
2.1 𝛾-Batch-Order-Fairness Traditional BFT consensus protocols guarantee safety and liveness but place no constraint on the relationship between the order in which transactions are received by replicas and the order in which they appear in the total order. Order-fairness protocols aim to enforce such a relationship. The strongest intuitive notion is receive-order-fairness [20], which requires that if a 𝛾 fraction of replicas receive tx before tx ′ , then all honest replicas must output tx strictly before tx ′ . However, Kelkar et al. [20] showed that receive-order-fairness is impossible in general, even when all replicas are honest, due to the Condorcet paradox. 1 An implicit resolution scheme as in FairDAG-RL is in principle compatible with
parallel construction, but it forces every parked graph to wait for evidence to trickle in through later committed subdags, with every subdag task needing to read and mutate the weights of earlier parked graphs, thus making concurrency complex to manage. Explicit missing edge resolution decouples each parked graph from the others and lets all of them accumulate votes concurrently through Narwhal’s reliable broadcast. 2
Herring: Parallel Batch-Order-Fairness on DAG-based Blockchain Consensus
Table 1: Design comparison of the leading batch-OF DAG BFT protocols. An entry in green indicates the best design choice, and an entry in ::: red indicates a shortcoming. Liveness attacks† were identified and patched in this work (Appendix B). The Corruption column reports the fault tolerance threshold at 𝛾 = 1. FairDAG-RL achieves 𝑛 ≥ 3𝑓 +1 because it assumes a DAG with weak edges∗ , whereas Herring and DoD operate on DAG without weak edges and require 𝑛 ≥ 4𝑓 +1.
FairDAG-RL [14]
Graph Construction
Missing Edge Resolution
Performance Bottleneck
Liveness Attacks
Corruption (𝛾 = 1)
Post-consensus
::::::
Implicit
Fairness layer ::::::::::
† Yes :::
𝑛 ≥ 3𝑓 +1∗ 𝑛 ≥ 4𝑓 +1 𝑛 ≥ 4𝑓 +1
DoD [26]
Pre-consensus ::::::::::
::::::
Implicit
::::::::::
DAG pipeline
Yes†
Herring (this work)
Post-consensus
Explicit
None
No
:::
Parallel Graph Construction No
::
No
::
Yes
∗ Weak edges are block references to the left-behind not-directly-referenced blocks, e.g., references to slow but honest nodes’ blocks. With weak edges every honest node’s local
ordering is present upon subdag commit. Without weak edges this is not the case, thus the threshold becomes 𝑛 ≥ 4𝑓 +1. Note that Narwhal [10] by design removes weak edges specifically to enable garbage collection, which is infeasible when weak edges are present.
2.2
As a simple example, consider three replicas receiving transactions in the orders [𝑎, 𝑏, 𝑐], [𝑏, 𝑐, 𝑎], and [𝑐, 𝑎, 𝑏]. A majority prefers 𝑎 before 𝑏, 𝑏 before 𝑐, and 𝑐 before 𝑎, forming a cycle that cannot be linearized without violating at least one majority preference. To circumvent this impossibility, Kelkar et al. [20] introduced the relaxed notion of 𝛾-batch-OF (see Definition 2.1), which groups cyclically dependent transactions into batches and only enforces ordering constraints across batches. Transactions belonging to the same batch are output at the ’same time’. Further, within a batch, any total ordering is allowed, as the fairness guarantee only constrains relative ordering across batches.
Narwhal & Tusk
Narwhal & Tusk [10] is the asynchronous DAG BFT protocol Herring builds on. It decouples transaction dissemination from ordering, eliminating the leader bandwidth bottleneck of traditional BFT protocols. Each replica (called a validator) runs a primary process and one or more worker processes. Workers receive client transactions, assemble them into batches, and reliably broadcast those batches to workers with the same identifier on other validators. The primary manages only lightweight metadata and the DAG structure, referencing worker batches by their cryptographic digests. This separation allows throughput to scale horizontally by adding more workers per validator. DAG construction. The protocol proceeds in rounds. In each round 𝑟 , every validator proposes a single DAG vertex through its primary, containing references (strong edges) to at least 𝑛−𝑓 vertices from round 𝑟 −1. Before a vertex can be proposed, the primary must collect 𝑛−𝑓 certificates of availability from the previous round, where each certificate attests that at least 𝑓 +1 honest validators have stored the corresponding vertex’s data. This reliable broadcast mechanism ensures that any certified vertex is retrievable even if its original proposer fails. Unlike DAG-Rider [17], Narwhal & Tusk does not use weak edges (i.e., references to vertices emitted before round 𝑟 −1), which allows replicas to garbage collect older uncommitted (orphaned) DAG vertices, thus making the protocol practical for deployment. Consensus and total ordering. Tusk operates on top of the Narwhal DAG without additional communication. It groups rounds into waves of fixed length, at the end of which a leader vertex 𝐿𝑟 is elected through a shared coin. If 𝐿𝑟 receives at least 𝑓 +1 references in the following round, it is committed. Upon commitment, all vertices in the causal history of 𝐿𝑟 not already committed under an earlier leader form the subdag 𝐴𝑟 . The DAG is thereby partitioned into non-overlapping subdags (𝐴𝑟 1 , 𝐴𝑟 2 , . . .). Vertices of each subgraph 𝐴𝑟 are deterministically ordered by topological sort. Key properties. Narwhal & Tusk guarantees the following properties: • Agreement. If a correct replica commits a vertex 𝑣, then all correct replicas eventually commit 𝑣. • Total order. If a correct replica commits 𝑣 before 𝑣 ′ , then every correct replica commits 𝑣 before 𝑣 ′ .
Definition 2.1 (𝛾-Batch-Order-Fairness [20]). For any two transactions tx and tx ′ received by all replicas, if 𝛾𝑛 replicas receive tx before tx ′ , then all honest replicas output tx no later than tx ′ , where 12 < 𝛾 ≤ 1. Aequitas [20] first realized batch-OF only guarantees weak liveness, because Condorcet cycles can chain together and grow to arbitrary length. Themis [19] solved this through batch unspooling, which allows transactions within a cycle to be output incrementally without waiting for the cycle to fully form, while still ensuring that all transactions in the same batch appear contiguously in the output. Herring adopts the same unspooling approach. Dependency graphs. Both Themis and the batch-OF DAG BFT protocols that followed construct a dependency graph to capture pairwise ordering preferences. Given 𝑛−𝑓 replica orderings, a directed edge from tx to tx ′ is added when the number of replicas that received tx before tx ′ exceeds a threshold of 𝑛(1−𝛾) + 𝑓 + 1. Transactions are classified by the number of ordering reports they have accumulated: (i) Solid, if the transaction appears in at least 𝑛−2𝑓 orderings; (ii) Shaded, if it appears in at least 𝑛(1−𝛾) + 𝑓 + 1 orderings but in fewer than 𝑛−2𝑓 ; and (iii) Blank, otherwise. Only non-blank transactions are inserted into the dependency graph. The ordering is finalized once the graph becomes a tournament, i.e., when every pair of non-blank vertices is connected by exactly one directed edge. Pairs that have not yet accumulated enough evidence to determine a direction are called missing and their edges must be resolved before finalization. 3
Marko Putnik and Jérémie Decouchant
• Validity. If a correct replica broadcasts a vertex 𝑣, then all correct replicas eventually commit 𝑣.2
Protocols built on DAGs with weak edges, such as FairDAG-RL, can achieve a weaker threshold of 𝑛 ≥ 3𝑓 +1 for 𝛾 = 1 because weak edges add 𝑓 extra honest contributions per subdag. However, weak edges come at a significant practical cost. As noted by Danezis et al. [10], the original Narwhal & Tusk paper explicitly removes weak edges precisely because they make garbage collection infeasible, since any block received may eventually be referenced by a future weak edge and must therefore be stored indefinitely. Herring inherits Narwhal & Tusk’s garbage collection and operates within a fixed memory footprint, at the cost of the stronger 𝑛 ≥ 4𝑓 +1 threshold. Following the analysis of Ladelsky et al. [23], accommodating this stronger threshold requires adjusting the underlying Narwhal protocol so that rounds consist of at least (𝑘−1)𝑓 + 1 vertices and each vertex references (𝑘−1)𝑓 + 1 vertices from the previous round, where 𝑘 = 2𝛾4−1 for Byzantine faults (reducing to 𝑘 ≥ 3 for crash faults only).
Self-referencing rule. In addition to the standard vertex validity rules, Herring requires that each correct replica includes a reference to its own previous round certificate when proposing a new vertex. Without this rule, a correct replica’s earlier vertex can be orphaned while a later vertex is committed, causing ordering evidence to arrive out of order across subdags. The self-referencing chain prevents this by guaranteeing that if a replica’s round 𝑟 vertex is committed, all of its earlier vertices are in the causal history and therefore committed in the same or an earlier subdag. Combined with the worker’s monotonic local ordering indicator (LOI) assignment, this ensures that each correct replica’s cumulative ordering across committed subdags is non-decreasing in LOI. FairDAG [14] adopts the same rule.
3
System Model
Cryptography. We assume a public-key infrastructure (PKI) where each replica holds a unique private key and all public keys are known. Digital signatures allow any replica to verify the origin and integrity of a message. We further assume a collision-resistant hash function 𝐻 that maps arbitrary-length inputs to fixed-length digests, used throughout the protocol to identify transactions and batches [15].
This section describes the system and threat model under which Herring operates. Herring inherits the asynchronous network and Byzantine fault assumptions of its underlying DAG BFT protocol, Narwhal & Tusk [10], and strengthens only the fault-tolerance threshold to match the requirement of 𝛾-batch-OF. System and threat model. We consider a system of 𝑛 known replicas communicating via message passing over an asynchronous network where messages between correct replicas are eventually delivered but with no bound on delay. A computationally bounded adversary can corrupt up to 𝑓 replicas during execution. Corrupted replicas are Byzantine and may behave arbitrarily, e.g., they can reorder or withhold messages, and report false local orderings. The remaining 𝑛−𝑓 replicas follow the protocol faithfully. Replicas are connected by pairwise authenticated channels. Clients submit transactions to all replicas and wait for finalization. Following the standard assumption in OF protocols [20, 19, 14], the external network between clients and replicas is non-adversarial, as an adversary controlling transaction delivery could manipulate input orderings directly and render any OF guarantee vacuous. Fault-tolerance threshold. Narwhal & Tusk requires 𝑛 ≥ 3𝑓 +1 for consensus safety and liveness. Herring strengthens this to the 4𝑓 threshold required by 𝛾-batch-OF, i.e., 𝑛 > 2𝛾 −1 , where 12 < 𝛾 ≤ 1, reducing to 𝑛 ≥ 4𝑓 +1 for 𝛾 = 1 (𝑛 ≥ 3𝑓 +1 if only crash faults are present). This threshold is a direct consequence of building on top of Narwhal & Tusk, whose DAG does not contain weak edges. Narwhal achieves its validity property through reinjection of orphaned vertices into later rounds, which eventually commits every correct replica’s transactions but provides no bound on how many rounds this takes. For fair ordering, waiting for reinjection is not an option, since the dependency graph for a subdag must be built from the orderings actually present in that committed subdag. A committed subdag contains at most 𝑛−𝑓 orderings, of which up to 𝑓 may be Byzantine, leaving 𝑛−2𝑓 honest contributions. The 4𝑓 Themis threshold of 𝑛 > 2𝛾 −1 is what makes this honest majority strict for every transaction pair, even after Byzantine influence.
4
Herring: Parallel Batch-OF on DAG BFT
This section describes the design of Herring. We first give an architectural overview, then describe how workers assign local ordering indicators (LOIs) and cast FairUpdate votes, and finally present the per-subdag graph construction and order finalization.
4.1
Overview
Herring preserves the architecture of Narwhal & Tusk and adds a per replica fairness processor that builds a global dependency graph and emits a fair transaction order upon every committed subdag. The starting point of Herring’s design is the observation from the introduction that the dominant cost in any Themis-style fairness layer is the pairwise weight matrix computation (phase 1 of FairPropose), and that this cost has no cross subdag data dependency. Herring exploits this by running phase 1 of multiple committed subdags concurrently on a thread pool, and serializing only the parts that actually need cross subdag agreement. Three design choices make per subdag processing safely parallel. First, dependency graphs are constructed post-consensus, so the fairness processor runs only after Tusk commits a subdag, keeping all fairness work off the DAG’s critical path. Second, missing edges are resolved explicitly via FairUpdate votes that piggyback on workers’ outgoing batches and travel through Narwhal’s reliable broadcast. Each subdag’s graph receives its resolutions directly rather than waiting for implicit evidence from later subdags. Third, support counts and pairwise weights are cumulative across committed subdags, with two complementary mechanisms ensuring that each transaction enters at most one graph despite parallel processing. A solid claim recorded synchronously at dispatch time excludes solid transactions of any in flight subdag from later snapshots, and a cumulative chain forwarded along the parallel task pipeline excludes shaded transactions of any in flight subdag from later active sets.
2 As Narwhal’s garbage collection might orphan vertices that never commit, it is
then necessary to re-inject the transactions of orphaned vertices into later vertices, which together with the 1/2-Chain Quality property of the DAG ensures eventual commitment within a constant number of rounds in expectation. 4
Herring: Parallel Batch-Order-Fairness on DAG-based Blockchain Consensus
(c) Per-subdag graph and order resolution. From the 𝑛−𝑓 local orderings, the task builds 𝐺𝑟 , decomposes it into SCCs, identifies the anchor, and linearizes each SCC up to the anchor. Transactions forming a Condorcet cycle ({tx 2 , tx 3 , tx 4 , tx 5 }) are output ‘at the same time’ as part of the same batch.
(a) DAG BFT consensus layer. An unmodified Narwhal & Tusk DAG with five validators across six rounds, with committed leaders 𝐿1 , 𝐿2 , 𝐿3 producing subdags 𝐴1 , 𝐴2 , 𝐴3 .
(b) Herring per-subdag parallel pipeline. After a synchronous extract + solid-claim step on the main thread, each subdag’s task runs four phases on a thread pool. Phase 1 (pairwise weight matrix, the dominant cost) is fully parallel across in flight subdags. The only cross subdag synchronization is the cumulative-𝐾 chain forwarded early by Phase 3, which the next subdag’s Phase 2 awaits before filtering its active set. Phase 4 either finalizes or parks the graph, where parked subdags accumulate 𝑛−𝑓 FairUpdate votes over Narwhal’s reliable broadcast and then run ApplyFairUpdate. The Emit serialization point drains ready buffers in subdag commit order. Dashed wait segments on 𝐴2 , 𝐴3 visualize the passing of the cumulative chain, i.e., 𝐴2 ’s Phase 2 cannot begin until 𝐾1 arrives from 𝐴1 ’s Phase 3, and 𝐴3 ’s until 𝐾1 ∪ 𝐾2 arrives from 𝐴2 ’s.
Figure 2: Herring system overview.
Figure 2 illustrates the high level architecture across three subfigures. Sub-figure 2a shows the unmodified DAG BFT layer that commits subdags 𝐴1, 𝐴2, 𝐴3, . . . . Sub-figure 2b shows the Herring per subdag pipeline that runs after each commit. Sub-figure 2c shows the per subdag graph 𝐺𝑟 that the pipeline produces and from which the per subdag transaction order is extracted. Workers assign each transaction a monotonically increasing LOI on first observation and broadcast batches containing transactions, LOIs, and any pending FairUpdate votes. Primaries assemble the DAG and Tusk commits subdags exactly as in vanilla Narwhal & Tusk. Each committed subdag is then handed to the fairness processor, which performs lightweight synchronous bookkeeping on the main thread before dispatching a four phase task onto a thread pool (Sub-figure 2b). Phase 1 computes the support counts and pairwise weight matrix. It is the dominant cost (Figure 1) and runs fully in parallel across in flight subdags. Phase 2 awaits the cumulative 𝐾 chain from the prior subdag and uses it as an active set filter before building 𝐺𝑟 . Phase 3 runs Tarjan SCC decomposition and anchor truncation, then forwards the extended chain to the next subdag’s task before doing any missing edge work, so that 𝐴𝑟 +1 ’s Phase 2 can begin while 𝐴𝑟 is still in Phase 4. Phase 4 either returns a finalized
order or parks the graph and triggers a FairUpdate vote exchange. Three synchronization points discipline this design. First, a solid claim recorded synchronously before dispatch excludes solid transactions of any in flight subdag from later snapshots. Second, the cumulative 𝐾 chain handoff between consecutive subdags excludes shaded transactions of any in flight subdag from later active sets. Third, the Emit point drains ready buffers in subdag commit order, so that the transaction order of 𝐴𝑟 −1 is always emitted before that of 𝐴𝑟 , ensuring all correct replicas produce the same total order.
4.2
Worker Batch Construction and FairUpdate Voting
Each Narwhal worker maintains a LOI tracker that assigns a monotonically increasing counter value to every transaction upon first observation, regardless of whether the transaction arrives directly from a client or inside a remote worker’s batch. 3 Subsequent observations of the same transaction return the previously assigned LOI. 3 Our implementation runs the LOI tracker inside a single worker per validator, which
keeps the local receive order centralized and avoids cross worker LOI reconciliation. A natural extension is to dedicate one worker per validator as the OF worker that exclusively handles LOI assignment and FairUpdate voting, while other workers retain their normal Narwhal duties. The OF worker then serves as the validator’s authoritative 5
Marko Putnik and Jérémie Decouchant
This guarantees that each (replica, transaction) pair has a stable LOI reflecting the true first observation time, independent of the ingress path.
by enough replicas to cross the solid threshold 𝜏𝑠 only when their committing vertices are spread across several committed subdags.
Algorithm 1 FairUpdate voting at the worker 1: State: LOI tracker 𝑇 , unresolved edges 𝑃 [𝑟 ], resolved votes 𝑉 [𝑟 ]
Single graph mechanism: solid claim plus cumulative chain. The single graph property, that each transaction enters at most one 𝐺𝑟 , is the safety invariant that makes parallel execution sound. Maintaining it across in flight tasks is the central challenge of the design, because the synchronous main thread cannot wait for any task to finish before extracting the next subdag’s snapshot. Herring uses two complementary mechanisms to handle this. The first is a solid claim recorded synchronously on the main thread before 𝐴𝑟 ’s task is dispatched. The claim is the set of solid transactions in 𝐴𝑟 ’s snapshot, and subsequent subdags exclude this set from their snapshots at extract time. Solid transactions are the right thing to claim eagerly because they are guaranteed to enter 𝐺𝑟 by the anchor rule of Themis’ FairPropose algorithm [19]. They have support at least 𝜏𝑠 , so they are necessarily in some SCC at or before the anchor in topological order, regardless of the rest of the graph structure. The claim is dropped when 𝐴𝑟 ’s task returns to the main thread, and any transaction that actually entered 𝐺𝑟 is then promoted to permanent excluded state. The second mechanism is a cumulative chain that handles shaded transactions. Shaded transactions are not claimed because, unlike solids, they are not guaranteed to end up in 𝐺𝑟 . A shaded transaction can have a path to a solid in 𝐺𝑟 and be retained, or it can be truncated past the anchor and need to reappear in a later subdag’s snapshot. Claiming shaded transactions eagerly would either be wrong, since the truncated ones have to come back, or it would force every later subdag to wait for 𝐴𝑟 ’s task to finish, which would defeat the parallelism. Instead, each subdag’s task forwards along the cumulative set 𝐾1 ∪ 𝐾2 ∪ · · · ∪ 𝐾𝑟 of vertices retained in earlier graphs, and the next subdag’s task uses this set as an active set filter inside its own post weight computation phase, i.e., shaded transactions of an in flight subdag 𝐴𝑟 therefore stay visible to phase 1 of 𝐴𝑟 +1, 𝐴𝑟 +2, . . . during weight matrix construction, but they are excluded from the active set before Tarjan runs, so they never enter a second graph.
2: upon FairPropose (𝑟, 𝑀𝑟 ) from fairness processor do 3: for each (𝑢, 𝑣) ∈ 𝑀𝑟 do 4: if 𝑇 knows loi(𝑢 ) and loi(𝑣) then 5: record directed vote (min → max) by LOI in 𝑉 [𝑟 ] 6: else 7: 𝑃 [𝑟 ] ← 𝑃 [𝑟 ] ∪ { (𝑢, 𝑣) } 8: end if 9: end for 10: upon new transaction tx observed do 11: 𝑇 .Record(tx ) 12: for each 𝑟 and each (𝑢, 𝑣) ∈ 𝑃 [𝑟 ] with tx ∈ {𝑢, 𝑣 } do 13: if 𝑇 knows loi(𝑢 ) and loi(𝑣) then 14: record directed vote in 𝑉 [𝑟 ], remove (𝑢, 𝑣) from 𝑃 [𝑟 ] 15: end if 16: end for 17: upon 𝑃 [𝑟 ] = ∅ for some 𝑟 do 18: queue 𝑉 [𝑟 ] into next outgoing batch, clear 𝑉 [𝑟 ]
A batch carries three kinds of payload alongside its raw transactions. Direct entries pair each newly received client transaction with its LOI. Indirect entries pair each transaction digest learned from a remote batch with its local LOI and are propagated exactly one hop. FairUpdate votes contain directed edge resolutions for previously parked subdags. When the fairness processor parks a subdag 𝑟 with unresolved missing edges 𝑀𝑟 , it sends a FairPropose(𝑟, 𝑀𝑟 ) message to the local worker. Algorithm 1 describes how the worker resolves each missing edge by comparing the LOIs of its two endpoints. If both LOIs are known, the worker records a directed vote. Otherwise, it defers the edge until the missing endpoint arrives via a future client submission or remote batch. Once all edges in 𝑀𝑟 have been resolved, the worker queues the complete set of directed votes for subdag 𝑟 into the next outgoing batch, so that edge resolutions travel through Narwhal’s existing reliable broadcast without additional communication rounds.
4.3
Why this split. Splitting the single graph mechanism into a solid claim plus a cumulative chain is what lets Herring keep the weight phase fully parallel while still serializing only what has to be serialized. Solid transactions account for the bulk of throughput at steady state, and excluding them at extract time means later subdags do not have to compute weights involving solids of in flight subdags at all. Shaded transactions are visible to the weight phase of later subdags because their resolution depends on cross subdag evidence anyway, but the cumulative chain filter ensures they are dropped before Tarjan runs. The result is that the most expensive operation, which Figure 1 identifies as the pairwise weight matrix, runs concurrently across in flight subdags, and the only synchronization point is the cumulative chain handoff that adds a single set union per subdag.
Per-Subdag Graph Construction
When Tusk commits a subdag 𝐴𝑟 , the fairness processor first runs a short synchronous step on the main thread that maintains cumulative per replica orderings of all pending (not yet proposed) transactions, ingests 𝐴𝑟 ’s new contributions into them, and builds a snapshot {𝐿𝑖 } for the parallel graph construction task. Cumulative state is necessary because a naive per subdag scheme, where support counts are computed only from orderings within the current 𝐴𝑟 , would fail to leverage the evidence that builds up across subdags. Under realistic asynchrony, a transaction can be reported local receive order and feeds LOIs to the rest of the system over a side channel. We leave this engineering split to future work. 6
Herring: Parallel Batch-Order-Fairness on DAG-based Blockchain Consensus
Algorithm 2 Per-subdag graph construction (parallel task)
topological order containing at least one solid vertex. Only SCCs up to and including the anchor are retained, and 𝐾𝑟 is the set of retained vertices. Forwarding the extended chain at this point, before missing edge handling in phase 4, is what preserves parallelism. The next subdag’s phase 2 can begin as soon as 𝐾𝑟 is known, without waiting for 𝐴𝑟 ’s graph to finalize or park. On result arrival, the main thread runs a synchronous step that promotes the vertices entering 𝐺𝑟 to proposed_txs, removes them from pending state, and drops the solid claim recorded for 𝐴𝑟 .
1: Input: subdag id 𝑟 , snapshot orderings {𝐿𝑖 }, oneshot receiver
prior_cumulative_rx, oneshot sender cumulative_tx 2: Output: finalized order or parked graph with missing edges 𝑀𝑟 3: Thresholds: 𝜏 = 𝑛 (1−𝛾 ) + 𝑓 + 1, 𝜏𝑠 = 𝑛 − 2𝑓 4: // Phase 1: support classification and pairwise weight matrix. 5: for each tx appearing in any 𝐿𝑖 do 6: 𝑐 (tx ) ← | {𝑖 : tx ∈ 𝐿𝑖 } | 7: end for 8: 𝑉𝑟 ← {tx : 𝑐 (tx ) ≥ 𝜏 }, 𝑆𝑟 ← {tx : 𝑐 (tx ) ≥ 𝜏𝑠 } 9: for each unordered pair {𝑢, 𝑣 } ⊆ 𝑉𝑟 do 10: 𝑤𝑢𝑣 ← | {𝑖 : 𝑢 ≺ 𝑣 in 𝐿𝑖 } |, 𝑤𝑣𝑢 ← | {𝑖 : 𝑣 ≺ 𝑢 in 𝐿𝑖 } | 11: end for
4.4
FairUpdate and Order Finalization
The fairness processor extracts FairUpdate votes from every committed subdag and routes them to the parked graph for the target subdag they reference. Once a parked graph for subdag 𝑟 has accumulated votes from 𝑛−𝑓 distinct replicas, a finalization task is spawned on the thread pool.
12: // Phase 2: cumulative chain barrier, then build 𝐺𝑟 . 13: prior_cumulative ← await prior_cumulative_rx 14: 𝑉𝑟 ← 𝑉𝑟 \ prior_cumulative 15: 𝐺𝑟 ← (𝑉𝑟 , ∅ ), 𝑀𝑟 ← ∅ 16: for each unordered pair {𝑢, 𝑣 } ⊆ 𝑉𝑟 do ⊲ using cached 𝑤 from Phase 1 17: if max(𝑤𝑢𝑣 , 𝑤𝑣𝑢 ) ≥ 𝜏 then 18: add edge (𝑢, 𝑣) if 𝑤𝑢𝑣 ≥ 𝑤𝑣𝑢 , else (𝑣, 𝑢 ) 19: else 𝑀𝑟 ← 𝑀𝑟 ∪ { (𝑢, 𝑣) } 20: end if 21: end for
Algorithm 3 FairUpdate resolution and order finalization 1: Per-replica state: 2: parked [𝑟 ]: parked graph (𝐺𝑟 , 𝑀𝑟 , 𝑎) for subdag 𝑟 3: votes[𝑟 ]: accumulated votes, author → directed edges 4: ready [𝑟 ]: completed order for subdag 𝑟 5: next: next subdag id to emit
22: // Phase 3: SCC decomposition, anchor truncation, chain forward. 23: [𝐶 1 , . . . , 𝐶𝑠 ] ← TopoSort(TarjanSCC(𝐺𝑟 ) ) 24: 𝑎 ← max{ 𝑗 : 𝐶 𝑗 ∩ 𝑆𝑟 ≠ ∅ } 25: truncate 𝐺𝑟 and 𝑀𝑟 to vertices in 𝐶 1 ∪ · · · ∪ 𝐶𝑎 26: 𝐾𝑟 ← vertices retained in 𝐺𝑟 after truncation 27: send prior_cumulative ∪ 𝐾𝑟 on cumulative_tx
6: upon committed subdag contains FairUpdate votes do 7: route each vote to votes[𝑟 ′ ] by target subdag 𝑟 ′ 8: for each 𝑟 ′ with |votes[𝑟 ′ ] | ≥ 𝑛−𝑓 do 9: spawn ApplyFairUpdate(𝑟 ′ ) on thread pool 10: function ApplyFairUpdate(𝑟 ) 11: (𝐺𝑟 , 𝑀𝑟 , 𝑎) ← parked [𝑟 ] 12: for each (𝑢, 𝑣) ∈ 𝑀𝑟 do 13: 𝑤𝑢𝑣 ← | {𝑎 : (𝑢 → 𝑣) ∈ votes[𝑟 ] [𝑎] } | 14: 𝑤𝑣𝑢 ← | {𝑎 : (𝑣 →𝑢 ) ∈ votes[𝑟 ] [𝑎] } | 15: if max(𝑤𝑢𝑣 , 𝑤𝑣𝑢 ) ≥ 𝜏 then 16: add edge (𝑢, 𝑣) if 𝑤𝑢𝑣 ≥ 𝑤𝑣𝑢 , else (𝑣, 𝑢 ) 17: end if 18: end for 19: ready [𝑟 ] ← Finalize(𝐺𝑟 , 𝑎) 20: Emit() 21: end function
28: // Phase 4: finalize or park. 29: if 𝑀𝑟 = ∅ then 30: return Finalize(𝐺𝑟 , 𝑎) ⊲ Alg. 3 31: else 32: park (𝐺𝑟 , 𝑀𝑟 , 𝑎) and send FairPropose (𝑟, 𝑀𝑟 ) to local worker 33: end if
When 𝐴𝑟 ’s task completes, transactions that entered 𝐺𝑟 are made permanent and removed from pending state, while transactions that were in 𝐴𝑟 ’s snapshot but did not enter 𝐺𝑟 stay in pending state and are eligible for the next subdag’s snapshot.
22: function Finalize(𝐺, 𝑎) 23: [𝐶 1 , . . . , 𝐶𝑠 ] ← TopoSort(TarjanSCC(𝐺 ) ) 24: order ← [ ] 25: for 𝑗 = 1 to 𝑎 do 26: append LinearOrder(𝐶 𝑗 ) to order 27: end for 28: return order 29: end function
Per subdag task. Algorithm 2 gives the parallel graph construction in full. The four phases were introduced in §4.1 and are visualized in Sub-figure 2b. In phase 1, the task classifies each transaction by its support count 𝑐 (tx), the number of distinct 𝐿𝑖 in which it appears. Only transactions with 𝑐 ≥ 𝜏 are admitted to 𝑉𝑟 . A transaction with 𝑐 ≥ 𝜏𝑠 is additionally marked as solid. For each pair of admitted vertices, the task counts how many snapshot orderings place one before the other. These pairwise counts are cached for use in phase 2. In phase 2, after the cumulative chain barrier, the task adds a directed edge between two admitted vertices if the larger of the two cached counts reaches the shaded threshold 𝜏, and records the pair as a missing edge otherwise. In phase 3, the task computes the strongly connected components (SCCs) of 𝐺𝑟 via Tarjan’s algorithm, topologically sorts them, and identifies the anchor as the last SCC in
30: function Emit 31: while ready [next ] exists do 32: output ready [next ] to application log 33: next ← next + 1 34: end while 35: end function
⊲ serialization point
Algorithm 3 describes vote application and order finalization. ApplyFairUpdate tallies, for each missing edge, the number of 7
Marko Putnik and Jérémie Decouchant
distinct replicas that voted in each direction and adds the majority supported edge whenever the larger tally reaches the shaded threshold 𝜏. Because votes ride on the same reliable broadcast that carries Narwhal’s transaction batches, every vote cast by a correct replica is eventually delivered to every other correct replica. Therefore, every parked graph eventually accumulates the 𝑛−𝑓 votes needed to trigger finalization. Finalize recomputes the SCCs of the augmented graph, topologically sorts them, and linearizes each SCC up to and including the anchor. Transactions forming a Condorcet cycle are output contiguously, while inter SCC ordering follows the topological sort, following the condensation plus unspooling approach of Themis [19]. The intra SCC linearization can be instantiated either as a Hamiltonian path through the tournament induced by the SCC or deterministically by sorting on transaction digests. Both choices preserve 𝛾-batch-OF since the fairness guarantee only constrains the ordering across SCCs. Emit is the serialization point where ready buffers are drained in subdag commit order, emitting the order of 𝐴𝑟 only after every earlier subdag has been emitted. This is necessary because Tusk commits 𝐴𝑟 −1 before 𝐴𝑟 , and the total transaction order must respect this commitment sequence across all correct replicas. Graph construction (Algorithm 2) and vote application remain fully parallel.
5
The fairness argument is borrowed from Themis [19] with the substitution of the leader’s collected list 𝐿 by the per-subdag snapshot {𝐿𝑖𝑟 } and of the leader proposal by subdag 𝐴𝑟 ’s dependency graph 𝐺𝑟 . Directional safety rules out wrong-direction edges in any 𝐺𝑟 and in any ApplyFairUpdate resolution. The non-trivial case is when tx and tx ′ finalize in different subdags, where we show they belong to the same Condorcet cycle. LOI monotonicity is the one place where the Themis argument needs adaptation, and it rests on the self-referencing rule and the worker’s monotonic LOI assignment. Liveness follows from Narwhal’s validity together with the fact that every parked graph eventually accumulates 𝑛 − 𝑓 FairUpdate votes, since votes ride on the same reliable broadcast that carries transaction data.
6
Experimental Evaluation
We evaluate Herring by comparing its performance to FairDAGRL [14] and DoD-W [26], two leading batch-OF DAG BFT protocols. In addition, we also evaluate the overhead of fair ordering of Herring relative to Narwhal & Tusk [10], its underlying DAG consensus protocol. We also benchmark against Themis [19], the leading batchOF protocol built on top of the leader-based consensus protocol of HotStuff [38]. We implemented Herring from the Rust research implementation of Narwhal 4 by modifying the batch structure of each Narwhal worker to allow fair transaction ordering. This included keeping track of a node’s local receive order together with appending a node’s local receive order position with each transaction within the batch. To allow for parallel CPU-bound global graph construction, we have utilized the thread pool implementation provided with the Tokio 5 Rust library. For comparing against DoD, we utilize its released code6 with modifications. Upon running the code, we noticed that it differs from the protocol specification of its accepted conference paper. For this reason, the code was adjusted to conform to the protocol description pseudo-code. However, by doing so we spotted a liveness bug within the protocol description itself concerning the implicit edge update mechanism (Appendix B). Furthermore, due to the architectural design of DoD, there is a probability that implicitly added edges might need to be discarded after consensus. This makes the implicit missing edge resolution fix non-intuitive. For this reason, we have chosen to extend the implementation with explicit edge resolving, similar to how Themis [19] and Herring handle missing edges. DoD builds on Rashnu’s [27] data-dependent order-fairness notion, which enforces fair ordering only between transactions that access overlapping data objects, with the original DoD evaluation reporting on two variants, DoD-R (read heavy) and DoD-W (write heavy). The latter behaves similarly to Themis, i.e., assumes dependency between each transaction. Herring, FairDAG-RL, and Themis do not implement data-dependent fairness and order all transactions through the fairness layer regardless of data dependency. Therefore, in our evaluation we use DoD-W, which is the
Correctness
This section gives an insight into the correctness of the protocol with full proofs deferred to Appendix A. Herring’s fairness processor runs after consensus and does not modify round progression, vertex creation, or leader election. The only change to the underlying DAG is the self-referencing rule of Section 2.2, which strengthens validity without weakening safety or liveness. Herring inherits the agreement, total order, and validity properties of Narwhal & Tusk directly, and adds three fairness-layer guarantees on top. Theorem 5.1 (Agreement on fair order). All correct replicas emit the same total transaction order. Theorem 5.2 (𝛾-batch-order-fairness). For any two transactions tx and tx ′ received by all replicas, if 𝛾𝑛 replicas receive tx before tx ′ , all correct replicas output tx no later than tx ′ . Theorem 5.3 (Liveness). Every transaction submitted by a correct client is eventually output by every correct replica. The central technical step is a reduction. Herring’s parallel execution emits the same total order as a serial reference in which each subdag’s graph construction task, including any subsequent ApplyFairUpdate resolution, runs to completion before the next begins. The three synchronization points of Section 4.1, namely the synchronous solid claim at dispatch, the cumulative 𝐾 chain handoff between consecutive subdags, and the Emit serialization point, together suffice to enforce this equivalence. Once the reduction is in place, agreement collapses to determinism of the serial reference, which is a deterministic function of the committed subdag sequence and the observed FairUpdate vote set.
4 https://github.com/asonnino/narwhal 5 https://tokio.rs 6 https://github.com/HeenaNagda/DoD
8
Herring: Parallel Batch-Order-Fairness on DAG-based Blockchain Consensus
configuration that actually exercises DoD’s fairness layer on every transaction. We note that data-dependent fairness is an orthogonal optimization that could be layered onto any of the four protocols. As such we do not explore this direction in this paper and leave it for future work. The released implementation of FairDAG-RL [14] is built on top of ResilientDB [12], a framework that differs to runtimes of both Herring and DoD-W, which makes the apples to apples comparison between protocols non-trivial. Instead, we have implemented a prototype of the FairDAG-RL protocol starting from the pseudocode description7 . The main difference lies in the underlying DAG structure. The original FairDAG-RL protocol assumes a DAG with weak edges, which lets it count 𝑓 additional contributions per subdag and in turn reach the weaker fault tolerance threshold of 𝑛 ≥ 3𝑓 +1 for 𝛾 = 1. Since Herring, DoD-W, and Narwhal & Tusk all operate on the weak-edge free Narwhal, running the original FairDAGRL directly would compare protocols across two different DAG structures at once, which would conflate the effect of the DAG with the effect of the fairness layer. We therefore ported FairDAG-RL to run on plain Narwhal, dropping the extra 𝑓 contributions that weak edges would provide and raising its threshold to match the other protocols (𝑛 ≥ 4𝑓 +1 for 𝛾 = 1). This gives a fair comparison of fairness layers on the same DAG substrate. We note that this comes at a cost for FairDAG-RL, since its original design targets a weaker threshold. On the other hand, running on plain Narwhal also removes the latency penalty that weak edges impose by waiting for slow replicas, so the performance numbers we report for FairDAGRL in this paper can be read as an upper bound on what its fairness layer can achieve. Interestingly, by implementing FairDAG-RL from scratch given its protocol description, we have noticed a liveness bug which can be turned into a liveness attack as discussed in Appendix B. When it comes to the Themis [19] protocol, we have utilized the baseline implementation from the authors of Rashnu [27] 8 , as the original released Themis source code is not complete. We have further adjusted the codebase by allowing for transaction size parameter control and have changed client broadcast to mimic the Narwhal client broadcast approach.
6.1
transactions per batch) and 512 bytes for the block header size (around 16 batches per block). We spawn 𝑁 clients, where 𝑁 is the number of nodes and each client connects to every node. Thus, every replica receives transactions from multiple clients in parallel, ensuring a saturated and uniformly distributed input load across the system. Each client submits transactions in bursts with a precision of 20, meaning the target send rate is divided into 20 equally-spaced bursts per second (one burst every 50 ms). To avoid duplicate transactions across clients, each client initializes its transaction counter to a random 64-bit value and shuffles the order of its outgoing connections on every burst, so that no two clients submit overlapping transaction identifiers and no replica is favored. We assign a separate compute node per each group of four clients and the same client setup is used across all evaluated protocols to ensure a fair comparison.
6.2
Different Batch Sizes
We first evaluate the impact of the batch size parameter on the performance of Themis, DoD-W, FairDAG-RL and Herring. The number of replicas is set to 𝑁 = 13, the batch-OF parameter 𝛾 is set to 𝛾 = 1.0 and the input rate is set to 7,000 tx/s. We set the number of faulty replicas 𝑓 to the maximum allowed given the constraints, thus we have 𝑓 = 3 replicas that silently crash. Similarly to previous batch-OF protocols, we compare the protocols across the following batch sizes: {25, 50, 100, 200, 400}. The batch size value represents the number of transaction orderings present within a single block. In leader-based protocols such as Themis, consensus occurs immediately after receiving the first block from each of the 𝑁 − 𝑓 replicas, meaning the computational complexity of global graph construction is directly tied to the batch size value, i.e., a batch size of 𝐵 yields a global graph built from exactly (𝑁 − 𝑓 ) · 𝐵 transaction orderings per consensus. In contrast, in DAG-based protocols such as DoD-W, FairDAG-RL and Herring, a single consensus instance can commit multiple blocks per replica at once and thus the effective number of transaction orderings fed into global graph construction is in addition bounded by the depth of the committed sub-DAG. As a result, for the same batch size value, DAG-based protocols generally process a larger number of transaction orderings per consensus instance than leader-based ones, which needs to be kept in mind when interpreting the results. Figure 3 shows that Herring consistently achieves the highest execution throughput across all evaluated batch sizes, sustaining close to the offered load of 7,000 tx/s for 𝐵 ≤ 50 and degrading gracefully as 𝐵 grows. FairDAG-RL peaks at the smallest batch size with roughly 4,500 tx/s and degrades monotonically thereafter, while DoD-W exhibits a markedly different, non-monotonic profile, rising from about 1,500 tx/s at 𝐵 = 25 up to a peak of roughly 4,400 tx/s at 𝐵 = 100 before collapsing at larger batch sizes. This behavior stems from the DoD-W architecture, where a global order graph is constructed prior to consensus at every DAG round, effectively adding an extra global-ordering step on top of the underlying DAG BFT protocol, i.e., at small 𝐵 the fixed per-round cost of this step dominates and caps throughput, while at 𝐵 = 100 it is better amortized across more transaction orderings, yielding the observed peak. Themis is effectively off-scale in comparison, sustaining only around 8–30 tx/s across the entire range (see inset), which reflects
Setup
We run our experiments on the DAS5 [4] academic cluster where each cluster node consists of two 8-core processors clocked at 2.4 GHz and 64 GB of RAM DDR3 memory. Nodes are interconnected via InfiniBand (IB) and Gigabit Ethernet (GbE). Each experiment run lasted for 60 seconds with each reported result being the average of at least 5 runs. Experiments mainly measure end-to-end (execution) throughput and latency of the system. Each Narwhal node consists of one primary process together with one worker process and each Narwhal node was assigned a separate machine, i.e., primary and worker processes of the same node were collocated on the same machine. When it comes to the main Narwhal parameters, we have chosen a fixed size of 128 bytes for each transaction, 4000 bytes for each batch (around 32
7 https://github.com/randomUserGithub123/narwhal/tree/fairdag 8 https://github.com/HeenaNagda/Themis_tx
9
Herring FairDAG‑RL DoD‑W Themis Themis (zoom)
6000 30 20 10
4000
25
50
100
200
Herring FairDAG‑RL DoD‑W Themis
40000
Execution Latency (ms)
8000
tx/s
Execution Throughput (tx/s)
Marko Putnik and Jérémie Decouchant
400
2000
30000
20000
10000
0
0 25
50
100
200
400
25
50
Batch Size (B)
100
200
400
Batch Size (B)
Figure 3: Impact of the batch size (𝐵) parameter on performance of Herring, FairDAG-RL, DoD-W and Themis at an input rate of 7,000 tx/s with 𝑁 = 13, 𝑓 = 3 and 𝛾 = 1.0. 𝑁 increases. We make 𝑓 = 1 and we vary 𝛾 to be: 𝛾 = 1.0 (𝑁 = 5), 𝛾 = 0.9 (𝑁 = 6), 𝛾 = 0.8 (𝑁 = 7) and 𝛾 = 0.7 (𝑁 = 11). For each protocol we select the batch size yielding the best performance based on the results of the previous experiment, thereby we have 𝐵 = 25 for Herring and FairDAG-RL and 𝐵 = 100 for DoD-W. The input rate is kept at 7,000 tx/s. Figure 4 illustrates the throughput and latency across Herring, FairDAG-RL and DoD-W for different 𝛾 values. At 𝛾 ∈ {1.0, 0.9, 0.8}, Herring consistently tracks the offered load of 7,000 tx/s, sustaining roughly 6,900 tx/s across all three settings at sub-second latency (around 700–750 ms). FairDAG-RL reaches comparable throughput at 𝛾 = 1.0 and 𝛾 = 0.8 (around 6,800 tx/s), but with significantly higher variance and a latency spike to roughly 4.2 s at 𝛾 = 0.9. DoD-W remains close to the offered load at 𝛾 = 1.0 but begins to fall behind at 𝛾 = 0.8, dropping to 5,000 tx/s. The gap opens clearly at 𝛾 = 0.7 (𝑁 = 11), where Herring sustains around 6,200 tx/s at 2.3 s of execution latency, while FairDAG-RL drops to 3,800 tx/s at 8.0 s and DoD-W drops to 3,000 tx/s at 2.0 s. This corresponds to a 64% throughput improvement over FairDAGRL and a 108% improvement over DoD-W, together with 71% lower
the fundamental throughput gap between leader-based and DAGbased batch-OF designs. The latency results show that Herring and DoD-W achieve the lowest execution latencies at small batch sizes (both around 2 s at 𝐵 = 25), whereas both FairDAG-RL and Themis already incur close to 10 s at the same batch size point. As 𝐵 grows, all protocols see their latency increase substantially which is consistent with our earlier observation that batch-OF protocols feed a larger number of transaction orderings into global graph construction per consensus instance as 𝐵 grows, thus increasing computation time. Overall, these results indicate that Herring offers the best throughput-latency trade-off in the small-to-moderate batch size regime (𝐵 < 100).
6.3
Varying the Batch-Order-Fairness Parameter
8000
Herring FairDAG‑RL DoD‑W
7000
Execution Latency (ms)
Execution Throughput (tx/s)
In this experiment, we analyze the impact of the batch-OF parameter 𝛾 on performance of the fairness DAG BFT protocols. The network size 𝑁 and the batch-OF parameter 𝛾 are correlated with the fol4𝑓 lowing formula: 𝑁 > 2𝛾 −1 , thus by decreasing 𝛾 the network size
6000 5000 4000 3000 2000 1000 0
7000
Herring FairDAG‑RL DoD‑W
6000 5000 4000 3000 2000 1000
γ=1.0 N=5
γ=0.9 N=6
γ=0.8 N=7
0
γ=0.7 N=11
Batch-OF Parameter (γ)
γ=1.0 N=5
γ=0.9 N=6
γ=0.8 N=7
γ=0.7 N=11
Batch-OF Parameter (γ)
Figure 4: Impact of the batch-OF parameter 𝛾 on performance of Herring, FairDAG-RL and DoD-W at an input rate of 7,000 tx/s with 𝑓 = 1. 10
Herring: Parallel Batch-Order-Fairness on DAG-based Blockchain Consensus
latency than FairDAG-RL. DoD-W attains comparable latency to Herring at 𝛾 = 0.7, but only at roughly half the throughput. This widening gap at stricter fairness settings highlights the scalability advantage of Herring’s design, which absorbs the growth of 𝑁 substantially better than both baselines due to its intrinsic parallelism.
6.4
and more than an order of magnitude higher throughput than Themis, while simultaneously sustaining the lowest execution latency among all fairness protocols across the entire evaluated range. These results confirm that Herring is the only evaluated fair ordering protocol that is able to keep up with the performance of its underlying DAG consensus protocol, making fair ordering essentially a near-free property in its design.
Increasing Input Rates 6.5
Herring FairDAG-RL DoD-W Narwhal&Tusk Themis
12000 10000
Different Network Sizes
In this set of experiments we measure the performance of the DAG BFT protocols by varying the network size, i.e., we keep the input rate fixed at 7,000 tx/s and vary the number of nodes from 5 until 23, thereby also adjusting the fault threshold 𝑓 from 1 to 5. Faulty nodes are silently crashing. We keep the batch-OF parameter 𝛾 as 𝛾 = 1.0 and again use the optimal batch size per each protocol. We exclude Themis from this set of experiments as its performance compared to DAG BFT protocols has been evaluated sufficiently, i.e., it is expected that it performs much worse than other protocols. Figure 6 shows how the throughput and latency of fairness DAG BFT protocols degrade with the increase in the number of nodes, in contrast to the underlying DAG BFT protocol of Narwhal & Tusk, which sustains a flat throughput and latency. This is expected due to the increase in communication overhead and computational costs, as each global graph construction computational cost is correlated with the amount of local receive orderings (𝑁 − 𝑓 factor). Most notably, Herring closely matches the throughput of Narwhal & Tusk up to 𝑁 = 18, sustaining close to the offered 7,000 tx/s, and only starts to visibly degrade beyond 𝑁 = 18, eventually settling at around 3,500 tx/s for 𝑁 = 23. Its latency remains within a few seconds across the entire evaluated range, peaking at around 4 s at 𝑁 = 20 before dropping back. In contrast, both FairDAG-RL and DoD-W degrade from the start, with FairDAG-RL dropping from around 5,900 tx/s at 𝑁 = 5 to roughly 3,000 tx/s at 𝑁 = 23, while DoD-W degrades even more aggressively, falling from 6,500 tx/s down to around 1,300 tx/s over the same range. Their latencies grow correspondingly, reaching 15 s and 16 s respectively at 𝑁 = 23, i.e., roughly an order of magnitude higher than Herring at the same Herring FairDAG-RL DoD-W Narwhal&Tusk Themis
30000
Execution Latency (ms)
Execution Throughput (tx/s)
This experiment measures the performance of the protocols by increasing the transaction input rate into the system. The intention behind the experiment is to determine the saturation points for each protocol, i.e., points with maximum achievable input rate after which the protocol stagnates in processing transactions and latency starts to sharply increase. We choose 𝑁 = 13, 𝛾 = 1.0 and set 𝑓 = 3 replicas to silently crash. In addition to the comparison between fairness DAG BFT protocols, we include the underlying DAG consensus protocol of Narwhal & Tusk, together with the state-of-the-art batch-OF leader-based Themis protocol. Similarly to the previous experiment, per protocol we select the batch size yielding best performance. Figure 5 illustrates the throughput and latency of all five protocols as the input rate is increased from 500 tx/s up to 13,000 tx/s. Most notably, Herring tracks the throughput curve of the underlying Narwhal & Tusk protocol up to roughly 10,000 tx/s, at which point it peaks at around 9,600 tx/s before entering a noisy regime with a gradual decline. This demonstrates that the parallel design nature of the fair ordering layer of Herring introduces minimal overhead on top of its underlying DAG consensus. In contrast, both FairDAG-RL and DoD-W saturate much earlier, at around 5,000 tx/s and 4,500 tx/s respectively, after which their throughput flattens and their execution latency climbs sharply, reaching close to 18–20 s for FairDAG-RL and 13 s for DoD-W at the highest offered rates. Themis saturates the earliest, already around 1,500 tx/s, after which its throughput collapses to effectively zero and its latency starts increasing, confirming the fundamental scalability gap between leader-based and DAG-based batch-OF designs. When looking at saturation points, Herring achieves roughly 90% higher throughput than FairDAG-RL, roughly 100% higher throughput than DoD-W,
8000 6000 4000 2000
25000 20000 15000 10000 5000 0
0 0
2000
4000
6000
8000
10000
0
12000
2000
4000
6000
8000
10000
12000
Input Rate (tx/s)
Input Rate (tx/s)
Figure 5: Impact of the client input rate on performance of Herring, FairDAG-RL, DoD-W, Narwhal&Tusk and Themis at with 𝑁 = 13, 𝑓 = 3 and 𝛾 = 1.0. 11
7000
Herring DoD-W Narwhal&Tusk FairDAG-RL
20000
Execution Latency (ms)
Execution Throughput (tx/s)
Marko Putnik and Jérémie Decouchant
6000 5000 4000 3000 Herring DoD-W Narwhal&Tusk FairDAG-RL
2000 1000 5
6
7
8
9
15000
10000
5000
0
10 11 12 13 14 15 16 17 18 19 20 21 22 23
5
Number of Nodes
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23
Number of Nodes
Figure 6: Impact of the network size 𝑁 on performance of Herring, FairDAG-RL, DoD-W and Narwhal&Tusk at an input rate of 7,000 tx/s with 𝛾 = 1.0. network size. At 𝑁 = 18, Herring achieves around 70% higher throughput than FairDAG-RL and over 175% higher throughput than DoD-W, while sustaining roughly 85% lower latency than both. These results confirm that Herring scales substantially better with network size than the existing fairness DAG BFT protocols.
6.6
Figure 7 shows the throughput and latency of all four protocols under varying Byzantine ratios. Overall, all protocols remain relatively stable across the evaluated range, with only minor fluctuations in both metrics, which confirms that the attack primarily affects the ordering of transactions rather than raw performance. Herring and FairDAG-RL deliver the highest throughput, both sustaining close to 1,750 tx/s across all ratios, followed by DoD-W at around 1,300–1,450 tx/s, while Themis remains effectively saturated at around 200 tx/s. Among the DAG-based protocols, Herring exhibits the smallest throughput reduction as the Byzantine ratio grows, dropping by less than 1% between 0% and 23.08%, compared to roughly 9% for FairDAG-RL and 8% for DoD-W. Interestingly, FairDAG-RL achieves a slightly lower execution latency than Herring at this operating point. This is because at 2,000 tx/s neither protocol is close to its saturation point, and FairDAG-RL’s implicit edge update mechanism avoids the extra communication overhead that Herring’s explicit edge resolution incurs, while Herring’s parallel graph construction advantage only materializes at higher input
Different Ratios of Byzantine Nodes
This experiment measures the performance of all fairness DAG BFT protocols together with the leader-based protocol of Themis under different ratios of Byzantine nodes. Byzantine nodes perform a simple yet effective attack where they reverse the local ordering of transactions. We fix the network size at 𝑁 = 13, keep the batch-OF parameter 𝛾 at 𝛾 = 1.0 and use the optimal batch size per protocol. We set the unique transaction input rate to the system to be 2,000 tx/s, as this is the point before the saturation of Themis, which thus allows us to fairly compare all protocols. We vary the ratio of Byzantine nodes as 𝑓 = 0 (0%), 𝑓 = 1 (7.69%), 𝑓 = 2 (15.38%) and 𝑓 = 3 (23.08%).
6000
1750
Execution Latency (ms)
Execution Throughput (tx/s)
2000
1500 1250
Herring FairDAG-RL DoD-W Themis
1000 750 500
5000
4000
3000
2000 Herring FairDAG-RL DoD-W Themis
1000
250 0
0 0.00%
7.69%
15.38%
23.08%
0.00%
Byzantine Node Ratio
7.69%
15.38%
23.08%
Byzantine Node Ratio
Figure 7: Impact of different ratios of Byzantine nodes on performance of Herring, FairDAG-RL, DoD-W and Themis at an input rate of 2,000 tx/s with 𝑁 = 13 and 𝛾 = 1.0. 12
Herring: Parallel Batch-Order-Fairness on DAG-based Blockchain Consensus
7
rates, as shown in previous experiments. Themis is an outlier in terms of latency, sustaining around 300 ms as it operates below its saturation point at the fixed input rate, but at the cost of an order of magnitude lower throughput than the DAG-based protocols. These results confirm that Herring remains robust under Byzantine behavior, with its throughput essentially unaffected.
6.7
Reversing Order Attack Resistance
Fraction of tx pairs (tx, tx0) reversed
In this experiment, we evaluate the robustness of Herring against adversarial reordering compared to Themis, following the methodology of Kelkar et al. [19]. We choose Themis as the comparison baseline, as it is the state-of-the-art leader-based batch-OF protocol, and our goal here is to highlight the robustness advantage of DAG-based batch-OF protocols due to their underlying data dissemination design. Each Byzantine replica reverses its local ordering before reporting it. As a closeness measure between two transactions we use Dist(tx, tx′ ) = |#(tx ≺ tx′ ) − #(tx′ ≺ tx)|, where small Dist indicates a fragile pair. Concretely, Dist ranges from 𝑁 mod 2 up to 𝑁 in steps of 2, where Dist = 𝑁 means that all nodes agree on the receive order of the pair, and for each Dist bucket the y-axis reports the fraction of transaction pairs whose final total ordering disagrees with the honest majority receive order. We fix 𝑁 = 21, 𝑓 = 5 and vary 𝑓actual ∈ {0, 2, 5}. 0.8 Herring, f_actual=0 Herring, f_actual=2 Herring, f_actual=5
0.7
Themis, f_actual=0 Themis, f_actual=2 Themis, f_actual=5
0.6 0.5 0.4 0.3 0.2 0.1 0.0 1
3
5
7
9
11
13
15
17
19
Related Work
Order-fairness protocols. The notion of 𝛾-batch-order-fairness was introduced by Kelkar et al. [20] with Aequitas, which however only provides weak-liveness due to arbitrarily chained Condorcet cycles. Themis [19] restored standard liveness through batch unspooling and deferred ordering and serves as the direct ancestor of the leader-based fair-ordering line, which subsequently evolved along axes of data-dependent fairness [27], pipelining with consensus [25], weight-based sorting [9], position fairness [36], crossround graph maintenance [31], bounded unfairness [21], and minimal batch variants [30]. Such work is orthogonal to Herring and we leave its evaluation as future work. Some approaches replace local orderings with median or inferred timestamps [41, 22, 39], hide transaction contents until commit [34, 24], or randomly permute committed sets [37, 1, 16]. Attacks on batch-OF. The Condorcet [35] and Ambush [28] attacks exploit client-induced information asymmetry across nodes to force Condorcet cycles that capture honest transactions, and both works independently propose internal transaction gossiping among nodes as the mitigation. This mitigation is provided natively by Narwhal’s dissemination layer, where every worker batch is consistently broadcast to the corresponding workers on all other nodes, and thus transfers to Herring without additional machinery. Figure 8 possibly hints at DAG BFT protocols being resistant by design to such batch-OF attacks. DAG BFT consensus. A parallel line of work has re-architected BFT consensus around DAGs in order to remove the single-leader bottleneck. Certified designs enforce non-equivocation at the dissemination layer through reliable broadcast [17, 10, 33, 32, 2]. Uncertified designs relax this to best-effort broadcast in exchange for lower commit latency and handle equivocation at the ordering layer [18, 3, 13, 29]. Hybrid designs use the DAG only as a dissemination layer and defer ordering to a leader-based finalization protocol [11]. None of these protocols enforce any OF property. As Herring works post-consensus and requires minimal changes in the underlying DAG (addition of LOIs and the self-referencing rule), we believe Herring’s design can be easily applied to any such DAG BFT in order to enable the OF property. We leave this as future work. Fair ordering on DAG BFT. Only FairDAG-RL [14] and DoD [26] realize batch-OF on top of DAG BFT, and both are dissected in detail against Herring in Section 4, Appendix B, and the experimental evaluation. On the consensus-layer side, Zhang et al. [40] demonstrate inter-block frontrunning attacks targeting the DR-first ordering rule of Tusk and Bullshark, which are orthogonal to the batch-OF layer and apply to Herring only to the extent that they apply to its underlying DAG BFT consensus. Upon playing with the released code of Zhang et al. [40] we noticed that the attack activation code does not reflect the theoretical definition given in the paper, and thus we defer the proper evaluation as future work. Liveness of prior batch-OF DAG BFT protocols. While reimplementing FairDAG-RL [14] and DoD [26] from their pseudocode descriptions as baselines, we identified previously unreported liveness bugs in the fairness layer of each protocol. In FairDAG-RL, the weight-update loop of the graph construction algorithm only considers ordering indicators that arrive in the current subdag,
21
Dist(tx, tx0)
Figure 8: Robustness against the reversing order adversarial attack for Herring and Themis with 𝑁 = 21, 𝑓 = 5, and varying the actual number of Byzantine replicas 𝑓actual ∈ {0, 2, 5}.
Figure 8 shows that Herring consistently outperforms Themis in resilience across all settings. At Dist = 1, Herring reverses only ∼ 11%–16% of pairs across all 𝑓actual values, whereas Themis reverses ∼ 35%–44%. More importantly, the fraction of reversed pairs in Herring drops to effectively zero already at Dist = 5 regardless of 𝑓actual , while Themis only converges to zero at Dist ≥ 15 and exhibits a long tail in between. The gap between the three 𝑓actual curves is also markedly smaller for Herring, indicating that the additional leverage an adversary gains from controlling more replicas is much more limited. Similar to FairDAG [14] results, the results substantiate the claim that DAG-based batch-OF protocols structurally mitigate adversarial ordering manipulation due to their inherent reliable dissemination layer. 13
Marko Putnik and Jérémie Decouchant
silently discarding indicators deposited while the transaction was still blank. A concrete input sequence can make the dependency graph permanently fail to become a tournament, stalling all future finalization. In DoD, three independent issues interact to prevent the missing edge weight store from ever reaching the edge threshold for a common class of transaction pairs, stalling the execution queue. We describe the bugs, concrete triggering scenarios, and the patches we integrated into our reimplementations in Appendix B.
8
[10]
[11]
[12] [13]
Conclusion
We presented Herring, the first batch-OF DAG BFT protocol whose dominant fairness layer cost runs embarrassingly parallel across committed subdags. The design starts from the observation that the dominant cost in any Themis-style fairness layer, the pairwise weight matrix, has no cross subdag data dependency, and exploits this by running multiple subdags’ graph construction tasks concurrently on a thread pool. Two supporting design choices keep this parallelism sound: post-consensus graph construction (shared with FairDAG-RL) that keeps all fairness work off the DAG’s critical path, and explicit FairUpdate vote resolution (inspired by Themis) that piggybacks on Narwhal’s batch dissemination and lets each parked graph accumulate its resolutions independently. Along the way, we identified and patched previously unreported liveness bugs in both FairDAG-RL and DoD. Our evaluation shows that Herring tracks the throughput of Narwhal & Tusk closely up to roughly 10,000 tx/s, sustains up to 100% higher throughput and 75% lower latency than the two DAG-based baselines, and remains essentially unaffected by colluding Byzantine nodes.
[14] [15]
[16]
[17]
[18]
[19]
[20]
[21]
References [1]
[2]
[3]
[4]
[5]
[6]
[7]
[8] [9]
Orestis Alpos, Ignacio Amores-Sesar, Christian Cachin, and Michelle Yeo. 2023. Eating sandwiches: modular and lightweight elimination of transaction reordering attacks. In 27th International Conference on Principles of Distributed Systems, OPODIS 2023, Tokyo, Japan, December 6-8, 2023. Balaji Arun, Zekun Li, Florian Suri-Payer, Sourav Das, and Alexander Spiegelman. 2025. Shoal++: high throughput DAG BFT can be fast and robust! In 22nd USENIX Symposium on Networked Systems Design and Implementation, NSDI 2025. https://www.usenix.org/conference/nsdi25/presentation/arun. Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. 2025. Mysticeti: reaching the latency limits with uncertified dags. In 32nd Annual Network and Distributed System Security Symposium, NDSS 2025, San Diego, California, USA, February 24-28, 2025. Henri Bal, Dick Epema, Cees de Laat, Rob van Nieuwpoort, John Romein, Frank Seinstra, Cees Snoek, and Harry Wijshoff. 2016. A Medium-Scale Distributed System for Computer Science Research: Infrastructure for the Long Term. Computer. Massimo Bartoletti and Roberto Zunino. 2025. A theoretical basis for MEV. In Financial Cryptography and Data Security - 29th International Conference, FC 2025, Miyakojima, Japan, April 14-18, 2025, Revised Selected Papers, Part II (Lecture Notes in Computer Science). Christina Garman and Pedro MorenoSanchez, (Eds.) Springer, 225–242. doi:10.1007/978-3-032-07035-7\_14. Christian Cachin and Jovana Micic. 2024. Quick order fairness: implementation and evaluation. In IEEE International Conference on Blockchain and Cryptocurrency, ICBC 2024, Dublin, Ireland, May 27-31, 2024. Miguel Castro and Barbara Liskov. 1999. Practical byzantine fault tolerance. In Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, Louisiana, USA, February 22-25, 1999. Margo I. Seltzer and Paul J. Leach, (Eds.) USENIX Association, 173–186. https: //dl.acm.org/citation.cfm?id=296824. Chainlink. 2023. What Is Maximal Extractable Value (MEV)? https://chain.link /education-hub/maximal-extractable-value-mev. (2023). Wuhui Chen, Yikai Feng, Jianting Zhang, Zhongteng Cai, Hong-Ning Dai, and Zibin Zheng. 2024. Auncel: fair byzantine consensus protocol with high performance. In IEEE INFOCOM 2024 - IEEE Conference on Computer Communications.
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
14
George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Narwhal and tusk: a dag-based mempool and efficient bft consensus. In Proceedings of the Seventeenth European Conference on Computer Systems. Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. 2024. Autobahn: seamless high speed BFT. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, SOSP 2024, Austin, TX, USA, November 4-6, 2024. Suyash Gupta, Sajjad Rahnama, Jelle Hellings, and Mohammad Sadoghi. 2020. Resilientdb: global scale resilient blockchain fabric. Proc. VLDB Endow. Philipp Jovanovic, Lefteris Kokoris-Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. 2025. Mahi-mahi: low-latency asynchronous BFT dag-based consensus. In 45th IEEE International Conference on Distributed Computing Systems, ICDCS 2025, Glasgow, United Kingdom, July 21-23, 2025. Dakai Kang, Junchao Chen, Anh Dinh, and Mohammad Sadoghi. 2025. Fairdag: consensus fairness over multi-proposer causal design. Proc. VLDB Endow. Jonathan Katz and Yehuda Lindell. 2014. Introduction to Modern Cryptography, Second Edition. CRC Press. isbn: 9781466570269. https://www.crcpress.com/Int roduction-to-Modern-Cryptography-Second-Edition/Katz-Lindell/p/book/9 781466570269. Alireza Kavousi, Duc Viet Le, Philipp Jovanovic, and George Danezis. 2025. Blindperm: efficient MEV mitigation with an encrypted mempool and permutation. In 29th International Conference on Principles of Distributed Systems, OPODIS 2025. doi:10.4230/LIPICS.OPODIS.2025.36. Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021. All you need is dag. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. 2023. Cordial miners: fast and efficient consensus for every eventuality. In 37th International Symposium on Distributed Computing, DISC 2023, October 10-12, 2023, L’Aquila, Italy. Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and Sreeram Kannan. 2023. Themis: fast, strong order-fairness in byzantine consensus. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. 2020. Orderfairness for byzantine consensus. In Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part III. Aggelos Kiayias, Nikos Leonardos, and Yu Shen. 2024. Ordering transactions with bounded unfairness: definitions, complexity and constructions. In Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques (Lecture Notes in Computer Science). Springer, 34–63. doi:10.1007/978-3-031-58734-4\_2. Klaus Kursawe. 2020. Wendy, the good little fairness widget: achieving order fairness for blockchains. In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies, AFT 2020, New York, NY, USA, October 21-23, 2020. Razya Ladelsky and Roy Friedman. 2025. On quorum sizes in dag-based bft protocols. In 2025 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). Dahlia Malkhi and Pawel Szalachowski. 2022. Maximal extractable value (MEV) protection on a DAG. In 4th International Conference on Blockchain Economics, Security and Protocols, Tokenomics 2022. doi:10.4230/OASICS.TOKENOMICS.20 22.6. Ke Mu, Bo Yin, Alia Asheralieva, and Xuetao Wei. 2024. Separation is good: A faster order-fairness byzantine consensus. In 31st Annual Network and Distributed System Security Symposium, NDSS 2024, San Diego, California, USA, February 26 - March 1, 2024. Heena Nagda, Sidharth Sankhe, Sakshi Sinha, Keon Attarha, Mohammad Javad Amiri, and Boon Thau Loo. 2025. DAG of dags: order-fairness made practical. Proc. ACM Manag. Data, 3, 6, 1–27. doi:10.1145/3769777. Heena Nagda, Shubhendra Pal Singhal, Mohammad Javad Amiri, and Boon Thau Loo. 2024. Rashnu: data-dependent order-fairness. Proc. VLDB Endow., 17, 9, 2335–2348. doi:10.14778/3665844.3665861. Eunchan Park, Taeung Yoon, Hocheol Nam, Deepak Maram, and Min Suk Kang. 2025. On frontrunning risks in batch-order fair systems for blockchains (extended version). IACR Cryptol. ePrint Arch. Nikita Polyanskii, Sebastian Mueller, and Ilya Vorobyev. 2025. Starfish: a high throughput BFT protocol on uncertified DAG with linear amortized communication complexity. Cryptology ePrint Archive, Paper 2025/567. (2025). https://e print.iacr.org/2025/567. Geoffrey Ramseyer and Ashish Goel. 2024. Fair ordering in replicated systems via streaming social choice. (2024). https://arxiv.org/abs/2304.02730 arXiv: 2304.02730 [cs.CR]. Pengkun Ren, Hai Dong, Nasrin Sohrabi, Zahir Tari, and Pengcheng Zhang. 2025. Proof-carrying fair ordering: asymmetric verification for BFT via incremental graphs. CoRR. arXiv: 2510.14186. doi:10.48550/ARXIV.2510.14186.
Herring: Parallel Batch-Order-Fairness on DAG-based Blockchain Consensus
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]
[41]
9
assigned an LOI to, which we refer to as 𝑖’s graphed contributions up to 𝐴𝑟 . {𝐿𝑖𝑟 } is the snapshot extracted at 𝐴𝑟 , where each 𝐿𝑖𝑟 is the LOI ordered prefix of Π𝑟𝑖 consisting of 𝑖’s contributions that have been sealed into DAG vertices committed by the time 𝐴𝑟 is processed. 𝐾𝑟 is the set of vertices retained in 𝐺𝑟 after anchor truncation. The proof structure mirrors Themis [19]. The first lemma shows that Herring’s parallel execution is observationally equivalent to a serial reference in which each subdag’s task runs to completion before the next begins. After establishing this equivalence, we argue about 𝐺𝑟 in isolation, exactly as Themis argues about a single leader proposal. The remaining safety and fairness lemmas lift from Themis with the substitution of the leader’s collected list 𝐿 by the snapshot {𝐿𝑖𝑟 } and of the leader proposal by 𝐴𝑟 ’s dependency graph 𝐺𝑟 .
Alexander Spiegelman, Balaji Arun, Rati Gelashvili, and Zekun Li. 2024. Shoal: improving DAG-BFT latency and robustness. In Financial Cryptography and Data Security - 28th International Conference, FC 2024, Willemstad, Curaçao, March 4-8, 2024, Revised Selected. Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris KokorisKogias. 2022. Bullshark: DAG BFT protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022. ACM. doi:10.1145/3548606.3559361. Chrysoula Stathakopoulou, Signe Rüsch, Marcus Brandenburger, and Marko Vukolic. 2021. Adding fairness to order: preventing front-running attacks in BFT protocols using tees. In 40th International Symposium on Reliable Distributed Systems, SRDS 2021, Chicago, IL, USA, September 20-23, 2021. Mohammad Amin Vafadar and Majid Khabbazian. 2023. Condorcet attack against fair transaction ordering. In 5th Conference on Advances in Financial Technologies, AFT 2023. Joseph Bonneau and S. Matthew Weinberg, (Eds.), 15:1– 15:21. doi:10.4230/LIPICS.AFT.2023.15. Yang Wang, Xiaofei Xing, Guojun Wang, Yuheng Zhang, and Peiqiang Li. 2025. Dikaios: position-anchored group ordering with reputation for fair and efficient byzantine consensus. Comput. Netw. David Yakira, Avi Asayag, Gad Cohen, Ido Grayevsky, Maya Leshkowitz, Ori Rottenstreich, and Ronen Tamari. 2021. Helix: A fair blockchain consensus protocol resistant to ordering manipulation. IEEE Trans. Netw. Serv. Manag. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. 2019. Hotstuff: BFT consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. Peter Robinson and Faith Ellen, (Eds.) ACM, 347–356. doi:10.1145/3293611.3331591. Pouriya Zarbafian and Vincent Gramoli. 2023. Lyra: fast and scalable resilience to reordering attacks in blockchains. In IEEE International Parallel and Distributed Processing Symposium, IPDPS 2023, St. Petersburg, FL, USA, May 15-19, 2023. Jianting Zhang and Aniket Kate. 2025. No fish is too big for flash boys! frontrunning on dag-based blockchains. In IEEE Annual Computer Security Applications Conference, ACSAC. Yunhao Zhang, Srinath T. V. Setty, Qi Chen, Lidong Zhou, and Lorenzo Alvisi. 2020. Byzantine ordered consensus without byzantine oligarchy. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2020, Virtual Event, November 4-6, 2020.
Lemma A.1 (Reduction to serial execution). Define the serial reference of Herring as the variant in which each 𝐴𝑟 ’s graph construction task runs to completion, including any subsequent ApplyFairUpdate resolution, before 𝐴𝑟 +1 ’s task begins. For every committed sequence of subdags 𝐴1, 𝐴2, . . . , Herring’s parallel execution and the serial reference emit the same total transaction order. Proof. By induction on 𝑟 , both 𝐺𝑟 and the set of FairUpdate edges admitted into 𝐺𝑟 agree in the parallel and serial executions. For the base case, 𝐴1 ’s task receives the empty cumulative chain in both executions and its snapshot {𝐿𝑖1 } is the same in both, since no prior exclusions exist. The four phases are deterministic functions of the snapshot, so 𝐺 1 and 𝐾1 agree. For the inductive step, assume the claim holds for all 𝑟 ′ < 𝑟 . The Ð cumulative chain 𝑟 ′ <𝑟 𝐾𝑟 ′ is then identical in both executions. In the parallel execution, 𝐴𝑟 ’s snapshot at the synchronous extract step may additionally contain shaded vertices belonging to in flight predecessors, since those tasks have not yet returned their results to the main thread. The cumulative chain filter in Phase 2 removes exactly those vertices from the active set before edge construction. For every pair (𝑢, 𝑣) with both endpoints in the post filter active set, the orderings that contain both 𝑢 and 𝑣 are the same in the two executions, because the snapshots agree on every replica’s contribution involving such pairs. The cached weights between active pairs therefore agree, and Phase 3 produces the same 𝐺𝑟 and 𝐾𝑟 . FairUpdate votes ride on Narwhal’s reliable broadcast and are observed by both executions as part of the same committed vertex sequence. ApplyFairUpdate is a deterministic function of (𝐺𝑟 , votes), so the admitted FairUpdate edges agree. Emit drains finalized orders in subdag commit order in both executions. Since the per subdag orders agree and the commit order is identical, the emitted total order agrees. □
Open Science
This paper presents Herring, a DAG-based consensus protocol that is designed to ensure batch-order fairness without sacrificing high performance. To support reproducibility and independent verification, we have open-sourced the complete implementation of Herring, alongside our implementations of the FairDAG-RL and DoD-W baselines, at https://github.com/randomUserGithub123/narwhal.
10
Ethical Considerations
This work raises no ethical concerns. All data, source code, and measurement results used in this paper are publicly available and contain no personally identifiable information. No human or animal subjects were involved in any part of the experimental procedure, and the work does not raise concerns related to health care, environmental impact, or military applications.
A
Full Correctness Proofs for Herring
Throughout this appendix, 𝜏 = 𝑛(1 − 𝛾) + 𝑓 + 1 and 𝜏𝑠 = 𝑛 − 2𝑓 , with 𝑛 > 4𝑓 /(2𝛾 − 1) and 12 < 𝛾 ≤ 1. We use the cumulative state notation of Section 4.3, with an explicit round superscript where the proofs require it. Π𝑟𝑖 is replica 𝑖’s LOI ordered pending list at the moment 𝐴𝑟 ’s snapshot is extracted, i.e., the transactions that replica 𝑖 has locally observed and not yet contributed to any earlier 𝐺𝑟 ′ . We treat Π𝑟𝑖 as a sequence when LOI order matters and as a set otherwise, and we drop the superscript and write Π𝑖 whenever the round is clear from context. 𝑃 𝑟 is the set of transactions that have entered some 𝐺𝑟 ′ with 𝑟 ′ < 𝑟 , and 𝑃𝑖𝑟 is the subset that 𝑖 has locally
A direct consequence is the single graph property, which Themis obtains for free from serial proposal construction. Corollary A.2 (Single graph). Each transaction enters at most one 𝐺𝑟 . Proof. In the serial reference each transaction is either retained in some 𝐾𝑟 , and thereafter excluded from all snapshots 𝑟 ′ > 𝑟 via the cumulative chain, or returned to pending state and eligible 15
Marko Putnik and Jérémie Decouchant
for the next snapshot. Lemma A.1 transfers this to the parallel execution. □
snapshot. For such a correct replica 𝑖, either 𝑖 has not yet observed tx ′ , in which case 𝑖 trivially received tx first, or 𝑖 has observed tx ′ but with an LOI past the prefix it contributed to 𝐴𝑟 , so tx ′ ∈ Π𝑟𝑖 . In the latter case Lemma A.3 gives LOI𝑖 (tx) < LOI𝑖 (tx ′ ), since tx lies in 𝑖’s committed prefix 𝐿𝑖𝑟 and tx ′ in its pending suffix Π𝑟𝑖 , and the worker’s monotonic LOI assignment forces 𝑖 to have received tx first. Under 𝑛 > 4𝑓 /(2𝛾 −1), 𝛾𝑛−4𝑓 ≥ 𝑛(1−𝛾) +1 by integrality. □
By Lemma A.1, the parallel execution and the serial reference emit identical total orders on every committed sequence, so a property of the emitted order holds in one if and only if it holds in the other. For the remainder of the appendix we argue about the serial reference, and every conclusion applies to the parallel execution by equivalence.
Lemma A.6 (Contiguous cycles). Suppose tx finalizes in 𝐺𝑠 and tx ′ in 𝐺𝑟 with 𝑠 > 𝑟 , and 𝛾𝑛 replicas received tx before tx ′ . Then tx and tx ′ belong to the same Condorcet cycle.
Lemma A.3 (LOI monotonicity). For each correct replica 𝑖 and each committed subdag 𝐴𝑟 , the concatenation of 𝑖’s graphed contributions 𝑃𝑖𝑟 and its pending list Π𝑟𝑖 , taken in LOI order, is non decreasing in LOI.
Proof. The argument is the Themis Lemma B.3 [19] case analysis applied to the serial reference. By Lemma A.4(3) the edge (tx ′, tx) is never added. If tx has support at least 𝜏 in 𝐴𝑟 ’s snapshot, then tx ∈ 𝑉𝑟 . At least 𝛾𝑛 − 𝑓 ≥ 𝜏 orderings place tx before tx ′ , so (tx, tx ′ ) ∈ 𝐺𝑟 . In the condensation, [tx] either coincides with [tx ′ ] or precedes it topologically, and since tx ′ ∈ 𝐾𝑟 both cases give tx ∈ 𝐾𝑟 , contradicting 𝑠 > 𝑟 by Corollary A.2. If tx has support strictly less than 𝜏 in 𝐴𝑟 ’s snapshot, then since tx ′ ∈ 𝐾𝑟 the anchor SCC of 𝐺𝑟 contains some solid 𝑍 . By Lemma A.4(2) exactly one of (tx ′, 𝑍 ) and (𝑍, tx ′ ) is in the finalized 𝐺𝑟 , so there is a path tx ′ = 𝑢 0 → 𝑢 1 → · · · → 𝑢𝑙 = 𝑍 in 𝐺𝑟 . Each edge on the path corresponds to at least 𝑛(1 − 𝛾) + 1 correct replicas agreeing on direction. Combined with Lemma A.5 applied to 𝑍 and tx, and with the hypothesis on tx and tx ′ , the sequence [tx ′, 𝑢 1, . . . , 𝑢𝑙 −1, 𝑍, tx, tx ′ ] forms a Condorcet cycle. □
Proof. The self referencing rule of Section 2.2 forces each round 𝑟 vertex of correct replica 𝑖 to reference 𝑖’s round 𝑟 −1 certificate. By induction on round, if 𝑖’s round 𝑟 vertex commits in 𝐴𝑘 then every earlier vertex of 𝑖 commits in some 𝐴 𝑗 with 𝑗 ≤ 𝑘. Workers assign LOIs strictly monotonically on first observation and seal batches in LOI order, so transactions in 𝑖’s round 𝑟 vertex have LOIs above those in any earlier vertex of 𝑖, and walking through 𝑖’s committed vertices in subdag commit order therefore yields 𝑃𝑖𝑟 in LOI order. The Ingest step appends to Π𝑟𝑖 in LOI order, and removing the prefix retained in some earlier 𝐺𝑟 ′ preserves monotonicity of the remainder. Finally, every transaction in 𝑃𝑖𝑟 was assigned its LOI by 𝑖 in a round strictly earlier than any transaction still pending at 𝐴𝑟 , so its LOI is below every entry of Π𝑟𝑖 . □ Lemma A.4 (Graph structure and directional safety). The output of Algorithm 2, together with any subsequent ApplyFairUpdate resolution, satisfies the following. (1) Every solid transaction in 𝑉𝑟 lies in 𝐾𝑟 . (2) For every solid tx and non-blank tx ′ in 𝑉𝑟 , exactly one of (tx, tx ′ ) and (tx ′, tx) is present in the finalized 𝐺𝑟 . (3) If 𝛾𝑛 replicas received tx before tx ′ , the edge (tx ′, tx) is never added to any 𝐺𝑟 nor installed by ApplyFairUpdate.
Lemma A.7 (FairUpdate votes arrive). Every parked subdag eventually accumulates votes from at least 𝑛 − 𝑓 distinct replicas.
Proof. On parking 𝐴𝑟 with missing edges 𝑀𝑟 , the fairness processor sends FairPropose(𝑟, 𝑀𝑟 ) to its local worker. The LOI tracker is persistent, so for each (𝑢, 𝑣) ∈ 𝑀𝑟 the worker records a directed vote as soon as both endpoints are observed. Clients broadcast to all replicas and indirect entries propagate transaction observations Proof. Parts (1) and (2) follow the argument of Themis Lemma B.1 [19] through Narwhal’s reliable broadcast, so every correct replica evenwith 𝐿 replaced by {𝐿𝑖𝑟 } and the leader proposal replaced by 𝐺𝑟 . The tually observes both endpoints. Votes queue into the next outgoing threshold condition 𝑛 > 4𝑓 /(2𝛾 − 1) ensures the larger direction batch and reach all correct replicas by Narwhal’s validity. Within reaches 𝜏 between any solid and non-blank pair, possibly through finitely many rounds, 𝐴𝑟 ’s parked graph accumulates votes from at ApplyFairUpdate when 𝐺𝑟 is parked. Missing edges between two least 𝑛 − 𝑓 replicas. □ shaded vertices are resolved by ApplyFairUpdate using the same thresholds applied to the FairUpdate vote tallies. For part (3), at least Main Theorems 𝛾𝑛 − 𝑓 correct replicas received tx before tx ′ , so the wrong direction Proof of Theorem 5.1. By Lemma A.1, the emitted sequence count in any snapshot or FairUpdate tally is at most 𝑛(1 − 𝛾) + 𝑓 , of every correct replica matches that of the serial reference. The which is strictly less than 𝜏, and the threshold is never crossed in serial reference is a deterministic function of the committed subdag the wrong direction. □ sequence and the observed FairUpdate vote set, both of which Lemma A.5 (Solid precedes unobserved). Suppose tx is solid in 𝐴𝑟 ’s snapshot and tx ′ has support strictly less than 𝜏 in 𝐴𝑟 ’s snapshot. Then at least 𝑛(1 − 𝛾) + 1 correct replicas received tx before tx ′ in receive order.
are identical across replicas by Tusk’s agreement and total order properties. □ Proof of Theorem 5.2. Let tx finalize in 𝐺𝑠 and tx ′ in 𝐺𝑟 , and suppose 𝛾𝑛 replicas received tx before tx ′ . The case analysis follows Themis Theorem 4.1 [19]. If 𝑟 = 𝑠, Lemma A.4(3) rules out the wrong direction edge. Either (tx, tx ′ ) ∈ 𝐺𝑟 , in which case tx either topologically precedes tx ′ in the condensation or shares an SCC with it and is emitted contiguously under the intra SCC linearization, or the pair is missing and
Proof. The argument follows Themis Lemma B.2 [19]. Since tx is solid and tx ′ has support below 𝜏, the number of snapshot orderings 𝐿𝑖𝑟 that contain tx but not tx ′ is at least 𝛾𝑛 − 3𝑓 . At most 𝑓 of these come from Byzantine replicas, leaving at least 𝛾𝑛 − 4𝑓 correct replicas with tx ∈ 𝐿𝑖𝑟 and tx ′ ∉ 𝐿𝑖𝑟 at the moment of 𝐴𝑟 ’s 16
Herring: Parallel Batch-Order-Fairness on DAG-based Blockchain Consensus
resolved by ApplyFairUpdate in the correct direction. In every case tx is emitted no later than tx ′ . If 𝑠 < 𝑟 , Emit drains in subdag commit order, so tx is output before tx ′ . If 𝑠 > 𝑟 , Lemma A.6 places tx and tx ′ in the same Condorcet cycle, so they share a batch in the maximal cyclic batch partition of the output, and tx is emitted no later than tx ′ . □
This creates a gap where a certain replica 𝑅𝑘 may report transactions 𝑑 1 and 𝑑 2 in an earlier subdag 𝐴𝑟 ′ , at which point both are still blank and belong to no graph, so the comparison is silently skipped. When a later subdag 𝐴𝑟 finally promotes 𝑑 1 and 𝑑 2 into a graph, 𝑅𝑘 ’s vertex in 𝐴𝑟 may carry unrelated transactions and thus never re-trigger the comparison. The ordering indicators from 𝑅𝑘 remain stored in 𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑_𝑜𝑖𝑠 but are permanently excluded from the weight computation. If 𝑅𝑘 ’s vote is the decisive one needed to push either direction of the pair (𝑑 1, 𝑑 2 ) past the non-blank threshold, no edge is ever added between them, thus the dependency graph never becomes a tournament, and the fairness layer stalls indefinitely.
Proof of Theorem 5.3. Let tx be submitted by a correct client. Each correct replica eventually includes tx in a worker batch, and by Narwhal’s validity the batch eventually commits. The support of tx reaches 𝜏𝑠 in some snapshot, and by Lemma A.4(1), tx ∈ 𝐾𝑟 for that subdag. If 𝐺𝑟 has no missing edges it finalizes immediately. Otherwise Lemma A.7 delivers 𝑛 − 𝑓 votes, and Lemma A.4(3) forces every missing pair to resolve in the correct direction. By the anchor rule, 𝐺𝑟 ’s finalization depends only on its own vertices, so Condorcet cycles cannot stall it. By induction on commit order every earlier subdag finalizes, and Emit eventually outputs 𝐴𝑟 ’s order. □
B
Concrete Attack.We use 𝑁 = 4, 𝑓 = 1. Replica 𝑅4 crashes silently, leaving three honest replicas 𝑅1, 𝑅2, 𝑅3 . The quorum threshold for adding an edge is ⌈3/2⌉ = 2 and the threshold for promoting a node to solid is 3. A malicious client triggers the liveness attack by crafting two transactions 𝑎 and 𝑏. Subdag 𝐴1 . The client submits 𝑎 and 𝑏 exclusively to 𝑅3 , and unrelated filler transactions to 𝑅1 and 𝑅2 : 𝑅1 : {(𝑥, 1)},
𝑅3 : {(𝑎, 1), (𝑏, 2)}
Only one replica (𝑅3 ) has seen 𝑎 and 𝑏, which is below the non-blank threshold, so both remain blank and enter no graph. However, 𝑅3 ’s ordering (𝑎 before 𝑏) is recorded in 𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑_𝑜𝑖𝑠. The weightupdate loop skips the pair because neither node belongs to a graph yet.
Liveness Attacks on Fairness DAG BFT Protocols
While implementing FairDAG-RL [14] and DoD [26] from their pseudocode descriptions, we identified liveness bugs in both protocols’ fairness layers. In this section we describe each bug, give a concrete attack or failure scenario, and state the fix.
B.1
𝑅2 : {(𝑥, 1)},
Subdag 𝐴2 . The client submits 𝑎 and 𝑏 to 𝑅1 and 𝑅2 in opposite orders, and keeps 𝑅3 busy with a filler transaction 𝑦: 𝑅1 : {(𝑎, 1), (𝑏, 2)},
Liveness Attack on FairDAG-RL
In FairDAG-RL, each replica assigns monotonically increasing ordering indicators to transactions as they arrive and broadcasts them as DAG vertices. The underlying DAG consensus periodically commits a leader vertex 𝐿𝑟 whose causal history defines a subdag 𝐴𝑟 (the set of newly committed vertices not included in any earlier leader’s causal history). The fairness layer receives 𝐴𝑟 and processes it as follows. First, for each transaction digest 𝑑 appearing in 𝐴𝑟 , the layer records the ordering indicator from the proposing replica into a global vector 𝑛𝑜𝑑𝑒 (𝑑).𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑_𝑜𝑖𝑠. Second, the layer checks whether 𝑑 has accumulated enough ordering indicators to be promoted: a node with 𝑎𝑝 (𝑑, 𝑟 ) ≥ 𝑁 − 𝑓 indicators becomes solid, one with 𝑎𝑝 (𝑑, 𝑟 ) ≥ ⌈(𝑁 −𝑓 )/2⌉ becomes shaded, and otherwise it remains blank, where non-blank nodes are inserted into a dependency graph 𝐺𝑟 . Third, the layer updates pairwise edge weights in 𝐺𝑟 and adds a directed edge between two nodes once the number of replicas preferring one direction reaches the non-blank threshold of ⌈(𝑁 −𝑓 )/2⌉. The fairness layer finalizes a transaction ordering once 𝐺𝑟 becomes a tournament, i.e., every pair of nodes is connected by exactly one directed edge.
𝑅2 : {(𝑏, 1), (𝑎, 2)},
𝑅3 : {(𝑦, 1)}
Now 𝑎𝑝 (𝑑, 𝑟 = 2) = 3, i.e., three replicas have seen both 𝑎 and 𝑏, so both are promoted to solid and inserted into a new dependency graph 𝐺 2 . The weight update loop processes 𝐴2 ’s vertices where 𝑅1 votes 𝑎 ≺ 𝑏, 𝑅2 votes 𝑏 ≺ 𝑎, and now 𝑅3 contributes nothing to the transaction pair (it has done so in previous subdag commit). The resulting weights are 𝐺 2 .𝑤𝑒𝑖𝑔ℎ𝑡 [(𝑎, 𝑏)] = 1 and 𝐺 2 .𝑤𝑒𝑖𝑔ℎ𝑡 [(𝑏, 𝑎)] = 1, both below the non-blank threshold of 2, so no edge is added. The dependency graph is not a tournament and the fairness layer stalls permanently, blocking all future rounds. Had 𝑅3 ’s earlier vote (𝑎 ≺ 𝑏 from 𝐴1 ) been counted, the weight 𝐺 2 .𝑤𝑒𝑖𝑔ℎ𝑡 [(𝑎, 𝑏)] would reach 2, an edge would be added, and the graph would finalize normally. Patch. The root cause is that the weight-update loop (Figure 8, lines 19–32 of [14]) only considers ordering indicators that arrive in the current subdag, missing any that were deposited while the transaction was still blank. The fix is to add a catch-up pass immediately after lines 11–18 (the node classification step), i.e., whenever a node 𝑑 is newly promoted into a graph 𝐺𝑟 , compute its pairwise weights against every other node already in 𝐺𝑟 by scanning the full 𝑐𝑜𝑚𝑚𝑖𝑡𝑡𝑒𝑑_𝑜𝑖𝑠 vectors of both nodes across all 𝑁 replicas, rather than relying on the current subdag’s vertices as triggers. This is both necessary and sufficient as every ordering indicator that was recorded while 𝑑 was blank is now accounted for exactly once, and the incremental loop at lines 19–32 continues to handle any future indicators arriving in later subdags. We have integrated this patch in our implementation of FairDAG-RL and verified that it restores finalization liveness.
Root Cause. The weight update step (Figure 8, lines 19–32 of [14]) iterates over every vertex 𝑣 ∈ 𝐴𝑟 and every transaction 𝑑 listed in 𝑣. For each such 𝑑, it looks up the dependency graph 𝐺 ′ to which 𝑑 belongs and compares 𝑑’s ordering indicator from the proposing replica against those of all other nodes in 𝐺 ′ . Crucially, this comparison fires only when 𝑑 appears in a vertex of the current subdag 𝐴𝑟 and 𝑑 already belongs to some graph 𝐺 ′ at the time of processing. 17
Marko Putnik and Jérémie Decouchant
B.2
Liveness Attack on DoD
two data-dependent transactions 𝑎 and 𝑏 to all four honest replicas, but due to network asynchrony the transactions arrive in different local-order rounds:
In DoD, each replica independently constructs a global dependency graph from 𝑁 −𝑓 collected local-order messages before consensus. For each pair of data-dependent transactions 𝑡 and 𝑡 ′ , the replica counts how many local orders place 𝑡 before 𝑡 ′ (denoted 𝑤 (𝑡, 𝑡 ′ )) and vice versa. If the larger count meets or exceeds the edge threshold 𝑛(1−𝛾) + 𝑓 + 1 and is greater than its counterpart, a directed edge is added. Otherwise, the pair is recorded as a missing edge in a set 𝑀, that is then broadcast alongside the global-order graph. Each replica locally maintains a missing edge store 𝑀𝑤 that tracks accumulated weights. A committed global-order graph can only be executed once all its missing edges are resolved in the executing replica’s 𝑀𝑤 , otherwise the execution queue stalls (Algorithm 3, line 18 of [26]). Bug 1: Weights diverge across replicas. Algorithm 2, line 32 of [26] broadcasts missing pairs without their weights. Since each replica constructs its global graph from a potentially different quorum of 𝑁 −𝑓 local orders, the computed weight for the same pair can differ. For instance, one replica may compute 𝑤 (𝑎, 𝑏) = 2 and store this in its 𝑀𝑤 , but broadcasts only the bare pair (𝑎, 𝑏) without the weight. Another replica that independently computed 𝑤 (𝑎, 𝑏) = 1 from a different quorum stores its own value of 1. Per the protocol description, a replica increments the weight by 1 upon receiving a missing pair, but even with this update applied, the two replicas’ weights remain permanently diverged. Bug 2: Weights are inflated by repeated broadcasts. The same mechanism also leads to double-counting. Algorithm 2, lines 39–40 of [26] increment the scalar weight in 𝑀𝑤 by 1 for each received copy of a missing pair, with no deduplication of the originating evidence. Consider the case where all 𝑓 replicas crash silently: the only available quorum is the 𝑁 −𝑓 honest replicas, so every honest replica collects the same set of local orders, constructs an identical global-order graph, and broadcasts the same missing pair to all others. Upon receiving these 𝑁 −𝑓 identical broadcasts, each replica increments the weight 𝑁 −𝑓 times despite the underlying evidence originating from the same set of local orders. The weight thus becomes inflated and may spuriously cross the edge threshold in a direction that no quorum of local orders genuinely supports. Bug 3: Weights are frozen against past-round evidence. The protocol provides two mechanisms to accumulate directional weight for a missing pair (𝑡, 𝑡 ′ ) in 𝑀𝑤 . The first (Algorithm 1, lines 7–8 of [26]) increments 𝑤 (𝑡 ′, 𝑡) when transaction 𝑡 physically arrives at a replica that already tracks the pair. The second (Algorithm 2, lines 11–12 of [26]) boosts the weight when both 𝑡 and 𝑡 ′ appear as vertices in a future round’s global dependency graph. Both are ineffective for a common class of pairs. The first requires 𝑡 to arrive after the pair is added to 𝑀𝑤 , but missing pairs are created during global ordering, which runs after both transactions have already been received. Since client transactions are submitted only once, neither will arrive again. The second requires both transactions to appear as vertices in a future round’s global dependency graph, but each transaction is included in exactly one round’s local-order graph and will not appear in any subsequent round. Concrete scenario. We use 𝑁 = 5, 𝑓 = 1, 𝛾 = 1, with 𝑅5 that immediately silently crashes. The non-blank threshold is 𝑛(1−𝛾) + 𝑓 + 1 = 2 and the solid threshold is 𝑛 − 2𝑓 = 3. A client submits
Replica 𝑅1 𝑅2 𝑅3 𝑅4
Round of 𝑎
Round of 𝑏
𝑟 𝑟 −1 𝑟 𝑟
𝑟 𝑟 𝑟 −1 𝑟
In round 𝑟 ’s global ordering, every honest replica collects the same quorum of 𝑁 −𝑓 = 4 local orders from {𝑅1, 𝑅2, 𝑅3, 𝑅4 }. Both 𝑎 and 𝑏 appear in three round-𝑟 local orders (𝑎 in 𝑅1, 𝑅3, 𝑅4 ; 𝑏 in 𝑅1, 𝑅2, 𝑅4 ) and are classified as fixed. However, only 𝑅1 and 𝑅4 include both transactions in their round-𝑟 local order; 𝑅2 includes only 𝑏 (it placed 𝑎 in round 𝑟 −1) and 𝑅3 includes only 𝑎. Suppose 𝑅1 received 𝑎 before 𝑏 and 𝑅4 received 𝑏 before 𝑎. Then 𝑤 (𝑎, 𝑏) = 1 and 𝑤 (𝑏, 𝑎) = 1. Neither reaches the edge threshold of 2, so (𝑎, 𝑏) is recorded as a missing edge. Although 𝑅2 and 𝑅3 both have evidence of the pair from round 𝑟 −1, this information was captured in a prior round’s local-order graph and is never contributed to the pair’s resolution. Neither weight accumulation mechanism ever fires, as neither transaction will arrive again nor reappear in a future round’s dependency graph. The weights remain stuck at 1 permanently, and the execution queue stalls on the first global-order graph containing this pair, blocking all subsequent committed graphs. Patch. A similar implicit edge update approach of FairDAG-RL could be applied, but is non-trivial in DoD because global graphs are constructed before consensus. Implicitly resolved edges may be based on local orders from up to 𝑓 replicas whose vertices are ultimately not committed, as the DAG structure of DoD does not include weak edges. This means implicitly added edges could need to be reverted after consensus, making the fix non-intuitive. For this reason, we have chosen to implement explicit edge resolution, where a replica that resolves a missing edge broadcasts the resolved direction to all other replicas, as done in Themis [19] and Herring.
18