arXiv CSopen access

Multi-Round Visibility: A Post-Consensus Ordering Layer for DAG-Based BFT

arXiv:2605.23432v1 [cs.DC] 22 May 2026

Multi-Round Visibility: A Post-Consensus Ordering Layer for DAG-Based BFT Pengkun Ren

Hai Dong

RMIT University Melbourne, VIC, Australia [email protected]

RMIT University Melbourne, VIC, Australia [email protected]

Zahir Tari

Nasrin Sohrabi

RMIT University Melbourne, VIC, Australia [email protected]

Deakin University Melbourne, VIC, Australia [email protected]

Abstract

1

Directed acyclic graph (DAG)-based Byzantine Fault-Tolerant (BFT) protocols achieve high throughput by decoupling dissemination from agreement and allowing many vertices to be committed concurrently. This same concurrency, however, weakens the ordering evidence available at the execution boundary: once units are committed as part of a shared DAG frontier, their final linearization is driven by traversal or deterministic tie-breaking rather than verifiable structural precedence evidence. Prior fair-ordering designs address ordering ambiguity by collecting, validating, or reconstructing stronger transaction-level ordering evidence within the consensus or transaction-processing workflow. While effective for their target semantics, this couples ordering with agreement and places ordering logic on the protocol path. This paper presents Multi-Round Visibility (MRV), a post-consensus structural ordering layer for DAG-based BFT. MRV reinterprets the committed DAG as an ordering evidence substrate. The key observation is that committed vertices already carry authenticated creator, round, and ancestry metadata, allowing replicas to compute multi-round structural visibility without adding consensus-path messages. MRV accumulates this visibility within a bounded evidence horizon, compares concurrently committed atomic units of fairness (AUFs) only after they coexist in the committed DAG, and derives precedence constraints from one-sided Byzantine-robust visibility advantages. When the committed DAG does not support such a constraint, MRV exposes the remaining ambiguity and resolves it through deterministic graph completion rather than hiding it inside traversal rules. We implement MRV on a Narwhal/Tusk-based prototype and evaluate it across deployment scales, workloads, and fault settings. Across 5–50 replicas, MRV preserves the high-throughput regime of the underlying DAG-BFT stack, reaching up to 210K TPS with bounded evidence collection and limited throughput impact. These results show that MRV can be integrated as a postconsensus ordering layer while keeping structural-ordering logic off the latency-sensitive consensus path.

BFT consensus gives replicated systems a consistent committed history even in the presence of malicious actors [29]. DAG-based BFT protocols change how that history is assembled and later linearized [26]. Instead of a single sequential proposal stream, they construct a causally referenced partial order of concurrently produced units, later deriving a deterministic execution order by locally interpreting the resulting DAG. Recent architectures such as Narwhal and Tusk [7] maximize throughput by decoupling dissemination from agreement, allowing large sets of concurrently produced vertices to be proposed and committed concurrently. This architectural gain, however, comes with an ordering cost. While the system must inevitably extend the committed partial order into a deterministic execution sequence, the concurrent nature of the DAG inherently blurs the original propagation history through asynchronous dissemination, cross-round aggregation, and wave-based commitment [19]. The challenge, therefore, is not whether such linearization is needed, but what evidence should constrain it once commitment no longer preserves those temporal semantics directly. This structural ambiguity matters in applications where execution order affects economic or security outcomes. In decentralized exchanges and lending smart contracts [6, 8, 23, 31], for example, two concurrent operations may be individually valid yet economically non-equivalent depending on which executes first. Such ordering sensitivity is one reason why Maximal Extractable Value (MEV) and transactionordering manipulation have become central concerns in blockchain systems [1, 10, 12, 20]. For replicated execution, this creates a design requirement: final order should be constrained by verifiable evidence whenever available, rather than by proposer discretion, traversal conventions, or arbitrary deterministic tie-breaking alone. A growing body of order-fairness work formalizes this requirement by deriving ordering constraints from collective observations of the network [3, 5, 14, 17, 18, 30]. Existing approaches largely realize fairness by moving ordering logic deeply into the protocol workflow itself. In 1

Introduction

Ren et al.

Post-consensus structural interpretation. MRV treats structural ordering as a deterministic interpretation layer over committed DAG outputs, rather than as part of the consensus path. This placement leaves dissemination, voting, and commit rules unchanged, allowing MRV to build on the safety and liveness guarantees of the base DAG-BFT stack. AUF-level visibility evidence after coexistence. MRV operates on AUFs rather than individual transactions because AUFs are the committed objects that carry authenticated creator, round, and ancestry metadata. It compares AUF pairs only after both coexist in the committed DAG, so precedence evidence is derived from post-coexistence structural visibility rather than from globally comparable transaction-arrival times. Bounded evidence certification. MRV accumulates creatorlevel structural visibility within a bounded post-commit horizon. It introduces a precedence constraint only when the committed DAG exhibits a one-sided Byzantine-robust visibility advantage; otherwise, it abstains and leaves the pair as residual ambiguity for deterministic completion. Thus, deterministic completion produces an executable order without creating additional evidence-backed precedence claims. The contributions of this paper are summarized as follows:

leader-based systems, Themis [15] has the leader collect local transaction orderings, construct a fair proposal, and require replicas to validate that proposal. Pushing this into the DAG setting, DoD [22] embeds fairness computation directly into the transaction-processing pipeline through explicit local-order, global-order, and order-finalization stages; it also requires clients to broadcast transactions to designated workers at every party so that the proposed order can be locally validated. These designs establish important baselines, but they also expose a recurring systems tension: fair-ordering is often incorporated into the protocol path, while making such ordering claims verifiable commonly relies on broad client dissemination assumptions. Strong transaction-level receive-order fairness is not generally achievable in Byzantine settings without stronger synchrony assumptions [15]. This motivates a DAG-specific question: once a common execution slice has been committed, can the system still derive a principled deterministic order from the authenticated structural evidence that remains in the committed DAG? At that stage, the natural comparison objects are the committed DAG units themselves, since they carry authenticated creator, round, and ancestry information. We refer to these units as atomic units of fairness (AUFs). In Narwhal/Tusk-style systems [7], an AUF corresponds naturally to a committed primary block or certified DAG vertex. When competing transactions reside in different AUFs, constraining the order of those AUFs becomes the post-commit lever for reducing arbitrary execution-order choices. Our key architectural insight is that, in DAG-BFT systems, this ordering problem can be addressed at the post-commit DAG interpretation layer rather than inside the protocol workflow. Once a sub-DAG is committed, it already contains authenticated causal structure and cross-creator visibility signals that can be reused to constrain ordering. Because visibility is counted at creator granularity, repeated DAG paths do not amplify evidence, and a strong visibility imbalance must be reflected across distinct creators rather than along a single chain. This makes committed-DAG visibility a useful structural signal for post-commit linearization, though not a substitute for global arrival-time observations. We instantiate this design in MRV, a pluggable ordering layer for DAG-based blockchains that runs after consensus. MRV uses structural evidence from the committed DAG to derive AUF ordering constraints local to each slice, while preserving the underlying consensus protocol and message semantics. It operationalizes this signal conservatively: precedence is introduced only when the committed DAG shows a one-sided visibility advantage after the compared AUFs coexist, while residual ambiguity remains explicit and is resolved deterministically. This placement exposes a favorable systems trade-off: MRV strengthens execution-ordering discipline while preserving the high-throughput consensus path and avoiding separate transaction-level dependency graphs. MRV realizes this design through three core mechanisms.

• A new architectural design point is identified in which fairness-aware ordering is decoupled from consensus and realized as a pluggable post-consensus interpretation layer over committed DAG structures, preserving the original consensus workflow and its baseline safety and liveness properties. • An AUF-level structural evidence model is introduced to extract creator-level visibility evidence directly from the committed DAG, enabling ordering decisions to be based on authenticated structural asymmetry after coexistence rather than on external timing signals. • A conservative ordering mechanism is developed for MRV, where precedence constraints are added only under sufficient committed-DAG support through bounded evidence horizons, maturity thresholds, and explicit abstention in ambiguous cases. • An implementation of MRV over a Narwhal/Tusk prototype and systems evaluation across node scales, batch sizes, fault settings, and geo-distributed environments show that MRV adds bounded post-commit evidence collection with limited throughput overhead.

2

Background

In BFT consensus, the objective is not merely to agree on a single value, but to establish a consistent execution history for a deterministic state machine replicated across mutually untrusting nodes [24, 27, 29]. Classic protocols realize this through State Machine Replication (SMR) [2]: all correct replicas execute the same valid requests in the same order. From PBFT [4] to modern partially synchronous frameworks 2

Multi-Round Visibility: A Post-Consensus Ordering Layer for DAG-Based BFT

such as HotStuff [28], this process has typically been modeled as a leader extending a sequential log. Consequently, traditional BFT systems couple consensus and ordering tightly: the direct protocol output is already a totally ordered history of executable requests. 2.1

region in Figure 1, the protocol periodically commits a leader vertex; this also commits its causal history, the sub-DAG of previously uncommitted vertices referenced by the leader. We call the newly delivered vertices from one such commit step a committed execution slice. This architectural shift changes the interface between consensus and execution. In a linear-log BFT protocol, the consensus output already resembles the execution order. In a DAG-BFT protocol, the natural output of a commit decision is instead a jointly authenticated committed sub-DAG: a set of concurrently produced vertices together with their causal dependencies. The protocol agrees on which vertices enter the shared history, but it does not natively provide a total order over the concurrently committed units. That order must be derived after commitment through traversal rules, deterministic tie-breaking, or an additional ordering layer. This is the concurrency cost of DAG-based BFT. High-throughput dissemination flattens fine-grained arrival signals at the execution boundary, while wave-based commitment exposes slices whose internal precedence is only partially constrained by causality. Deterministic traversal is sufficient for replica agreement, but it provides little explicit evidence for why one causally concurrent committed unit should precede another.

DAG-based BFT and the Concurrency Cost

While the single-leader architecture provides a natural foundation for sequential execution, its tight coupling of dissemination and agreement can become a scalability bottleneck [26]. A leader must both disseminate transaction payloads and drive the cryptographic agreement phases, so throughput is often constrained by the leader’s network bandwidth. DAG-based BFT protocols address this bottleneck by moving toward high-concurrency agreement. Recent designs decouple dissemination and availability from the agreement path, building on a broader line of asynchronous BFT work [9, 11]. Replicas continuously disseminate transaction batches and broadcast availability-certified vertices attesting that the underlying data are available to a quorum. The consensus layer then orders these lightweight metadata vertices rather than raw transaction payloads. This design pattern appears across DAG-based protocols, from fully asynchronous constructions such as DAG-Rider [13] to high-throughput Narwhal-style architectures [7]. The dissemination layer also imposes the structure shown in Figure 1. To create a valid vertex at a given round, a replica includes parent references to a quorum of vertices from the preceding round. These mandatory references weave the vertices into a DAG and encode authenticated causal history: if 𝐵 ∈ Anc(𝐴), then the creator of 𝐴 incorporated 𝐵 into the ancestry of 𝐴 before broadcasting it. Round 1

Round 2

Round 3

Round 4

Replica 1

V1(1)

V1(2)

V1(3)

V1(1)

Replica 2

V2(1)

V2(2)

V2(3)

V2(1)

Replica 3

V3(1)

V3(2)

V3(3)

V3(1)

2.2

Order-Fairness

This ambiguity in the execution order is not merely a theoretical artifact. In execution-sensitive applications, such as decentralized exchanges and lending protocols, underconstrained ordering can affect economic outcomes and create opportunities for MEV. A robust line of work has therefore sought to establish order-fairness by shifting ordering authority from a single leader or traversal rule to evidence derived from the collective observations of the network. Because network-wide pairwise receive-order observations may form Condorcet-style cycles, practical systems often weaken exact global ordering goals into graph-based batch-order fairness. The graph used in these schemes is not the underlying consensus structure itself. Instead, systems construct an auxiliary dependency graph in which transactions are vertices and directed edges represent supermajority observations of relative arrival. The practical realization of this model reveals a clear architectural evolution. Aequitas [16] pioneered this graphbased foundation, circumventing Condorcet cycles by grouping strongly connected components (SCCs) into unordered batches, though it suffered from weak liveness because cyclic dependencies could indefinitely delay finalization. Themis [15] addressed this liveness limitation through deferred ordering and liveness anchors, resulting in a monolithic architecture that constructs O (|𝐵| 2 ) transaction dependency graphs within the consensus path. SpeedyFair [21] later introduced a decoupled architecture, moving fair-ordering into an optimistic parallel pipeline to hide ordering latency from

Figure 1. DAG-BFT architecture and committed execution slice. Replicas broadcast availability-certified vertices (circles) that reference a quorum of prior-round vertices (arrows), forming an authenticated causal DAG. Committing a leader vertex (orange) finalizes its previously uncommitted causal history, which forms the committed execution slice linearized by MRV (blue shaded region). Consensus protocols built atop this DAG, such as Tusk [7] and Bullshark [25], operate over this topology rather than a sequential proposal stream. As shown by the shaded 3

Ren et al.

the core BFT agreement. Across these designs, fairness evidence is still collected and maintained as a transaction-level ordering structure distinct from the base protocol output. When the traditional order-fairness paradigm intersects with modern DAG-BFT architectures, a recurring systems tension emerges. DAG-BFT protocols achieve high throughput precisely by decoupling transaction dissemination from the agreement path. Pushing transaction-level fair ordering into this setting, as in DoD [22], preserves the graph-based formulation but introduces explicit local-order, global-order, and finalization stages into the transaction-processing workflow. In addition to this computational mismatch, making transaction-level fairness claims checkable often relies on broad client dissemination [15, 22], so that fairness-relevant inputs are consistently observed across parties. This assumption creates tension with the core DAG-BFT design goal: it introduces a system-wide dissemination burden alongside the communication efficiency originally gained by decoupling dissemination from agreement. These computational and communication costs expose a linearization gap. A DAG-BFT protocol already outputs a jointly authenticated committed sub-DAG: its vertices carry round numbers, creator identities, and authenticated ancestor relations, recording cross-creator structural visibility among committed units. This raises a systems opportunity: instead of carrying a separate ordering-evidence structure through dissemination, can the execution layer reuse the committed DAG itself as ordering evidence? MRV builds on this opportunity by interpreting committed-DAG visibility as a post-consensus signal for constructing a slice-local execution order without changing the underlying protocol.

3

eventually exposes a common sequence of finalized committed outputs to all correct replicas, under the synchrony and liveness assumptions of that base protocol instance. MRV itself introduces no additional synchrony requirement. 3.2

We inherit the standard authenticated Byzantine fault model used by DAG-based BFT protocols such as Narwhal/Tusk, DAG-Rider, and Bullshark [7, 13, 25]. Among the 𝑛 replicas, at most 𝑓 are Byzantine, with 𝑛 ≥ 3𝑓 + 1. The adversary is computationally bounded but may coordinate faulty replicas and schedule messages within the communication assumptions of the base protocol. Byzantine replicas may deviate during DAG construction by omitting vertices, delaying or withholding their own messages, choosing parent references strategically, or attempting equivocation. MRV operates only on the canonical committed DAG exported by the base stack. We assume the base protocol exports certified vertices whose creator identities and parent references are authenticated, together with the same committed DAG prefix G𝑅𝑐 and the same ordered slice sequence (𝑆 1, 𝑆 2, . . .) to all correct replicas. As part of this exporter contract, for each creator-round pair (𝑐, 𝑡), the exporter exposes at most one canonical committed AUF 𝑌𝑐,𝑡 ; non-canonical equivocation attempts are not part of MRV’s input and are excluded from creator-level visibility counts. This matches the standard interface of quorum-certified DAG-BFT stacks, where equivocation handling and canonicalization belong to the base protocol’s validity, certification, and delivery rules rather than MRV’s post-consensus interpretation layer. At the MRV layer, Byzantine replicas and adversarial scheduling can affect the structural evidence that appears in G𝑅𝑐 , including visibility trajectories, maturity outcomes, and conflicting directional signals induced by strategic parent selection or message scheduling. MRV treats this committed structure as its evidence surface: evidence-backed precedence is derived only from the structural visibility predicate in Section 3.5, while pairs not supported by that predicate remain residual ambiguity for deterministic completion.

System Model and Problem Statement

We model MRV as a post-consensus interpretation layer over a DAG-based BFT stack. MRV does not modify the underlying consensus message flow, voting rules, or commit conditions. Instead, it acts as a deterministic bridge between consensus and execution: it operates on the growing committed DAG structure and the ordered committed execution slices exported by the base stack, and for each slice outputs a deterministic, slice-local order over its AUFs. The following subsections formalize these exported objects and the assumptions MRV makes about them. 3.1

Threat Model

3.3

Committed DAG and Execution Slices

The base DAG-BFT protocol outputs a monotonically growing committed DAG view. Let 𝑅 denote the current committed frontier (e.g., the highest committed round). We define G𝑅𝑐 = (𝑉𝑅𝑐 , 𝐸𝑅𝑐 ) as the common committed DAG view available at frontier 𝑅. All correct replicas eventually agree on the identical G𝑅𝑐 for any given 𝑅. For any committed vertex 𝑋 ∈ 𝑉𝑅𝑐 , the DAG provides authenticated structural metadata, including its creator cr(𝑋 ) ∈ R, strictly increasing round number 𝑟 (𝑋 ), parent references Par(𝑋 ), and reflexive ancestor closure Anc(𝑋 ) (by convention, 𝑋 ∈ Anc(𝑋 )). We abstract the base DAG-BFT stack as exposing an agreed, ordered sequence of committed execution slices 𝑆 1, 𝑆 2, . . . .

System Setting and Trust Assumptions

We consider a system of 𝑛 replicas, denoted by R = {1, . . . , 𝑛}, which also serve as the creators of DAG vertices. The base protocol authenticates creator identities and parent references through its certification and signature machinery, making committed DAG metadata publicly verifiable by all correct replicas. MRV is defined over an abstract committedDAG exporter interface: it assumes only that the base stack 4

Multi-Round Visibility: A Post-Consensus Ordering Layer for DAG-Based BFT

All correct replicas observe the same slice sequence in the same order. Each slice consists of the newly delivered AUFs associated with one commit decision. MRV does not require the base protocol to natively name such slices; it only requires an adapter that exposes the newly delivered AUFs for each commit decision before execution-layer traversal is applied. In a Narwhal/Tusk-style instantiation, this corresponds to the committed leader’s causal history after removing AUFs that have already appeared in earlier slices. Because slices contain only newly delivered AUFs, they are mutually disjoint, so that each AUF belongs to exactly one slice. After removing previously delivered AUFs, a slice need not be causally closed by itself; MRV treats the slice strictly as the output domain, while the committed DAG prefix remains available as the evidence domain. MRV is invoked independently on each slice 𝑆 ⊆ 𝑉𝑅𝑐 . To derive the order for a given slice 𝑆, MRV need not wait for the full future committed DAG; it only consults the committed prefix available up to the frontier required by its bounded observation horizon.

precedence relation only when the committed DAG satisfies the structural visibility predicate, and abstains otherwise. For two AUFs 𝐴, 𝐵 ∈ 𝑆, define their visibility delta at round 𝑡 as Δ(𝐴, 𝐵, 𝑡) = 𝐶𝐴 (𝑡) − 𝐶𝐵 (𝑡). The post-coexistence observation window for (𝐴, 𝐵) is W (𝐴, 𝐵) = {𝑠 (𝐴, 𝐵) + 1, . . . , 𝐻 (𝐴, 𝐵)}. If 𝐻 (𝐴, 𝐵) ≤ 𝑠 (𝐴, 𝐵), this window is empty and no post-coexistence structural precedence is inferred.

3.4 Atomic Units of Fairness and Structural Evidence

Definition 2 (Conditional AUF-Level Structural Fairness). An output order for a committed slice satisfies conditional AUF-level structural fairness if it preserves every evidencebacked structural visibility precedence relation that remains compatible with the slice’s hard causal order and the graphlevel conflict resolution defined by MRV. Pairwise relations without mature, one-sided, non-conflicting structural visibility evidence remain residual ordering ambiguity and are completed deterministically without being counted as evidencebacked precedence.

Definition 1 (Structural Visibility Precedence). For a pair (𝐴, 𝐵) in the same committed execution slice 𝑆, we say 𝐴 has structural visibility precedence over 𝐵, denoted 𝐴⊲SVP 𝐵, if (1) both 𝐴 and 𝐵 are mature; (2) there exists a round 𝑡 ∈ W (𝐴, 𝐵) such that Δ(𝐴, 𝐵, 𝑡) ≥ 𝑓 + 1; and (3) there does not exist a round 𝑡 ∈ W (𝐴, 𝐵) such that Δ(𝐵, 𝐴, 𝑡) ≥ 𝑓 + 1. This predicate is MRV’s evidence-backed precedence relation. Threshold 𝑓 + 1 is applied to creator-level visibility deltas, so a positive signal must be reflected across distinct creators rather than amplified by repeated paths through the DAG.

MRV orders AUFs within a single committed execution slice. We abstract an AUF as the committed DAG vertex that carries the creator, round, and ancestry metadata used by MRV; in Narwhal/Tusk-style architectures, this naturally maps to a committed primary vertex. The order of transactions within an AUF and the order among committed slices are inherited from the underlying batching and consensus layers. Structural metadata are therefore attached to AUFs rather than to individual transactions. Let 𝑋, 𝐴, 𝐵 ∈ 𝑆 denote AUFs within the same slice. To evaluate structural precedence, MRV extracts crosscreator visibility from G𝑅𝑐 . Let 𝑌𝑐,𝑡 denote the canonical committed AUF exposed by the exporter for creator 𝑐 at round 𝑡 ≤ 𝑅, if it exists. The structural visibility count of 𝑋 at round 𝑡 ≥ 𝑟 (𝑋 ) is defined as: 𝐶𝑋 (𝑡) = #{𝑐 ∈ R | 𝑌𝑐,𝑡 exists and 𝑋 ∈ Anc(𝑌𝑐,𝑡 )}. MRV limits post-commit evidence collection with a system-wide observation cap 𝑊max . For each AUF 𝑋 , its stopping time ℎ𝑋 is defined as: ℎ
𝑋 := min {𝑡 ≥ 𝑟 (𝑋 ) | 𝐶𝑋 (𝑡) ≥ 2𝑓 + 1} ∪ {𝑟 (𝑋 ) + 𝑊max } . The maturity indicator records whether 𝑋 reached quorum visibility within this cap: mature(𝑋 ) = true ⇐⇒ 𝐶𝑋 (ℎ𝑋 ) ≥ 2𝑓 + 1. For pairwise alignment, MRV delays the evaluation of pair (𝐴, 𝐵) until both AUFs have reached their stopping times. We define the coexistence-alignment round 𝑠 (𝐴, 𝐵) = max(𝑟 (𝐴), 𝑟 (𝐵)), and the pair horizon 𝐻 (𝐴, 𝐵) = max(ℎ𝐴 , ℎ𝐵 ). A slice 𝑆 reaches its final slice sealing time at𝑇 (𝑆) = max𝑋 ∈𝑆 ℎ𝑋 . 3.5

Fairness Target: Structural Visibility Precedence

MRV defines an AUF-level structural ordering target over committed DAG outputs. Its evidence source is authenticated creator, round, and ancestry metadata in the committed DAG, not replica-local transaction arrival time. Accordingly, MRV provides a structural guarantee: it certifies an AUF-level 5

Section 4 defines enforceability via the MRV precedence graph, where causal and SVP edges are assembled and only SVP constraints that survive SCC condensation are preserved as structural precedence claims. This target follows the systems principle behind orderfairness: execution order should be constrained by verifiable evidence rather than proposer discretion or arbitrary tie-breaking. MRV applies this principle to a DAG-native evidence substrate, using committed creator-level visibility to constrain slice-local AUF linearization. 3.6

Problem Statement

For each committed execution slice 𝑆, MRV derives a deterministic slice-local total order ≺𝑆 over the AUFs in 𝑆. Its fairness target is the conditional AUF-level structural fairness defined in Section 3.5: when the committed DAG provides mature, one-sided structural visibility evidence for a same-slice AUF pair, MRV should preserve the corresponding enforceable precedence relation in the final slice order. Pairs without such support remain residual ordering ambiguity; MRV completes them deterministically while keeping the resulting order separate from evidence-backed precedence. Slice Boundary. MRV operates within the linearization boundary of a committed execution slice. Cross-slice reactive

Ren et al.

INPUT

MRV CORE Evidence Extractor

1

Creator-level structural visiblility

Commited slice S

AUF from creator a

B

AUF from creator b

Creator c

c1

... ...

c3

...

...

AUF from other creators

A

rk

c2

cn A

Pair-local, one-shot, frozen verdict

Commited rounds

r1 r2 r3

A B

2 Pairwise Comparator

OUTPUT Graph Assembler / Linearizer Causal + SVP constraints, SCC condensation

3

B

SVP test over post-coexistence window

A≺B

B≺A

Abstain

A

A

A

B

B

B

C

C

D

D

E

E

D

C

... Strong signal for B over A

Sees A only Sees B only

Strong signal for A over B

Sees A and B

No one-sided signal / conflict

Sees Neither

Slice-local deterministic execution order

E Precedence graph Gs

Condensation DAG

Figure 2. Execution pipeline of MRV. Operating post-consensus, MRV takes a committed execution slice 𝑆 as read-only input and derives a deterministic slice-local order through three local stages. (1) The Evidence Extractor accumulates creator-level structural visibility for each AUF over bounded committed rounds until a quorum threshold or observation cap is reached. (2) The Pairwise Comparator evaluates mature AUF pairs over a post-coexistence window and freezes a verdict only when the committed DAG provides unconflicted, one-sided strong evidence. (3) The Graph Assembler builds the precedence graph 𝐺𝑆 from hard causal constraints and evidence-backed verdicts, then condenses SCCs, topologically orders the DAG, and completes residual ties deterministically. input the monotonically growing committed DAG view G𝑅𝑐 , the current committed execution slice 𝑆, and the systemwide observation cap 𝑊max , and produces a deterministic, slice-local total order ≺𝑆 over the AUFs in 𝑆. An overview of the MRV architecture is shown in Fig. 2. MRV separates the ordering domain from the evidence domain. The ordering domain is restricted to the AUFs contained in the current slice 𝑆. The evidence domain may extend beyond 𝑆: MRV may consult committed descendants outside 𝑆 from later rounds to extract structural visibility evidence, provided that they lie within the bounded observation horizon. MRV is invoked independently for each committed execution slice; cross-slice delivery order remains the order exported by the base consensus layer. MRV realizes the ordering of each slice through five logical stages. As the committed frontier advances, these stages are incrementally interleaved in an online manner: 1. Structural Visibility Accumulation: As new vertices are committed, MRV incrementally tracks the creator-level visibility of each AUF 𝑋 ∈ 𝑆 across subsequent rounds. 2. AUF Stopping Times: Each AUF reaches a stopping time ℎ𝑋 either by achieving quorum-grade visibility or by hitting the common observation cap 𝑊max . 3. Pair Horizons and Frozen Verdicts: For each pair (𝐴, 𝐵) ∈ 𝑆, MRV waits until the pair horizon 𝐻 (𝐴, 𝐵) is reached, extracts pairwise precedence evidence from post-coexistence rounds, and freezes the resulting verdict. 4. Slice Sealing and Precedence Graph Construction: Once the committed frontier reaches 𝑇 (𝑆), all AUFs in 𝑆 have reached their stopping times. MRV then constructs a

strategies, such as placing a transaction in 𝑆𝑖+1 in response to one committed in 𝑆𝑖 , exercise a different control point: transaction admission, mempool scheduling, or the base commit sequence. MRV is complementary to these mechanisms and targets the intra-slice ordering ambiguity exposed by concurrent DAG commitment. Given a monotonically growing committed DAG view G𝑅𝑐 , a committed execution slice 𝑆, and a common observation cap 𝑊max , MRV produces a slice-local total order satisfying: (1) Deterministic Agreement: All correct replicas derive the same ≺𝑆 from the same committed inputs. (2) Causal Consistency: ≺𝑆 extends the committed DAG’s causal partial order within 𝑆. (3) Slice Locality: MRV orders only AUFs in 𝑆, while its evidence may use committed descendants outside 𝑆 within the bounded observation horizon. (4) Evidence Conservatism: MRV certifies an evidencebacked precedence constraint only from mature, one-sided, non-conflicting structural visibility evidence. (5) Conditional Structural Fairness: Every enforceable SVP relation from Section 3.5 is preserved in ≺𝑆 . (6) Bounded Completion: ≺𝑆 is sealed once the committed frontier reaches 𝑇 (𝑆) = max𝑋 ∈𝑆 ℎ𝑋 , so post-commit evidence collection is bounded by 𝑊max .

4

MRV Design and Workflow

4.1

Overview and Execution Pipeline

MRV is a deterministic post-consensus interpretation pipeline executed independently by all correct replicas. It takes as 6

Multi-Round Visibility: A Post-Consensus Ordering Layer for DAG-Based BFT

slice-local precedence graph from hard causal constraints and evidence-backed pairwise verdicts. 5. Graph Linearization and Deterministic Completion: MRV compresses cycles through SCC condensation, topologically orders the condensation DAG, and applies the deterministic completion key 𝜅 only to residual ambiguity not fixed by causal or enforceable evidence-backed constraints. MRV first determines which AUFs have accumulated structural evidence, then identifies which AUF pairs admit evidencebacked precedence, and finally turns the resulting constrained partial order into an executable total order. Deterministic completion is used only for residual ambiguity; it does not create additional structural precedence claims. 4.2

before reaching this threshold is immature. Only mature AUFs are eligible to induce positive precedence claims in pairwise comparison. Immature AUFs still appear in the final total order, but they induce no evidence-backed precedence constraints. Committed evidence rounds

r2

r3

rk ...

A

... ...

B

... ...

Structural Visibility, Observation Horizon, and AUF Maturity

CA (t) Visibility count

r1

2f+1

CB (t)

hA Commited round t

hB =cap

Figure 3. Structural visibility accumulation and AUF stopping times. Matrix cells indicate whether creator-round AUFs see 𝐴, 𝐵, both, or neither. MRV counts distinct creators that see each target AUF and fixes ℎ𝑋 at the 2𝑓 + 1 maturity threshold or the observation cap 𝑟 (𝑋 ) + 𝑊max .

Building on the structural visibility count 𝐶𝑋 (𝑡) defined in Section 3, MRV uses committed descendants to incrementally accumulate ordering evidence for each AUF over rounds. Creator-Level Visibility Extraction. For an AUF 𝑋 ∈ 𝑆 and round 𝑡 ≥ 𝑟 (𝑋 ), visibility is measured by 𝐶𝑋 (𝑡) = #{𝑐 ∈ R | 𝑌𝑐,𝑡 exists and 𝑋 ∈ Anc(𝑌𝑐,𝑡 )}. This quantity counts the number of distinct creators whose canonical committed AUFs include 𝑋 in their ancestor closure. Because the metric is creator-level and ancestry-based, it does not depend on replica-local receive order. Observation Cap and Stopping Time. MRV treats an AUF as having accumulated quorum-grade structural visibility once 𝐶𝑋 (𝑡) ≥ 2𝑓 + 1. Since at most 𝑓 creators are Byzantine, this means that the AUF appears in the authenticated ancestry of at least 𝑓 + 1 correct creators at round 𝑡; this is a structural visibility witness, not a claim about transaction-level arrival order. To avoid waiting indefinitely for delayed AUFs, MRV bounds evidence accumulation by the observation cap 𝑊max . The cap is a protocol configuration parameter that controls the trade-off between evidence coverage and post-commit ordering delay. A larger 𝑊max gives MRV more committed rounds from which to observe structural visibility, while a smaller 𝑊max closes evidence windows earlier and may increase immature AUFs, abstentions, and deterministic completion. In our prototype, this cap is instantiated using the configured committed-history retention window passed to the MRV executor. Using the stopping time already defined in Section 3,
ℎ𝑋 := min {𝑡 ≥ 𝑟 (𝑋 ) | 𝐶𝑋 (𝑡) ≥ 2𝑓 + 1} ∪ {𝑟 (𝑋 ) + 𝑊max } ,

4.3

Pairwise Verdicts from Post-Coexistence Evidence

Given the stopping time ℎ𝑋 and maturity indicator mature(𝑋 ) of each AUF, MRV converts per-AUF visibility trajectories into pairwise precedence verdicts. Each pair is frozen once its pair horizon is reached, so later committed rounds cannot rewrite an already-issued pairwise claim. This pairwise comparator is the only stage at which MRV introduces explicit precedence claims; all later stages merely assemble or complete those claims deterministically. Mature-Pair Gate. For any pair (𝐴, 𝐵) ∈ 𝑆, if either mature(𝐴) or mature(𝐵) evaluates to false, MRV abstains. Immature AUFs provide truncated evidence trajectories and therefore do not support explicit positive precedence claims. Post-Coexistence Alignment. For mature pairs, MRV compares visibility only after both AUFs coexist in the committed history. With coexistence-alignment round 𝑠 (𝐴, 𝐵) = max(𝑟 (𝐴), 𝑟 (𝐵)), MRV evaluates the visibility delta over the strictly post-coexistence window 𝑡 ∈ {𝑠 (𝐴, 𝐵)+1, . . . , 𝐻 (𝐴, 𝐵)} as Δ(𝐴, 𝐵, 𝑡) = 𝐶𝐴 (𝑡) − 𝐶𝐵 (𝑡). This alignment excludes precoexistence lead from being interpreted as structural precedence evidence. The window starts at 𝑠 (𝐴, 𝐵) + 1 because 𝑠 (𝐴, 𝐵) is the later creation round of the pair; only subsequent committed rounds can provide creator-level visibility observations that may reflect both AUFs. One-Sided Strong Signal Rule. MRV implements the SVP predicate from Section 3.5 using a visibility-delta threshold of 𝑓 + 1. Since at most 𝑓 creators are Byzantine and each creator contributes at most one visibility count per round, a visibility advantage of 𝑓 + 1 cannot be generated solely by Byzantine creators. This does not imply transaction-level arrival priority; it identifies a Byzantine-robust structural

MRV replaces an unbounded hindsight window with a bounded online stopping rule driven entirely by committed-DAG structure. As illustrated in Figure 3, for each AUF in the active slice, the evidence window closes deterministically at the first committed round where the AUF either reaches the quorum visibility threshold or reaches the observation cap. Maturity Semantics. Based on ℎ𝑋 , the maturity indicator mature(𝑋 ) is true iff 𝐶𝑋 (ℎ𝑋 ) ≥ 2𝑓 + 1. An AUF capped 7

Ren et al.

Algorithm 1 MRV Pairwise Verdict for (𝐴, 𝐵)

signal in the committed DAG. Let 𝑝𝑜𝑠 (𝐴, 𝐵) and 𝑛𝑒𝑔(𝐴, 𝐵) indicate whether the post-coexistence window contains a positive or negative strong signal, respectively. MRV returns Edge(𝐴 → 𝐵) iff 𝑝𝑜𝑠 (𝐴, 𝐵) is true and 𝑛𝑒𝑔(𝐴, 𝐵) is false. If both signals appear, the DAG exhibits conflicting evidence and MRV abstains; if neither appears, MRV abstains for lack of signal. MRV relies on the existence of an unopposed strong signal rather than an accumulated score, preventing later descendants from disproportionately amplifying an early advantage. Figure 4 illustrates this rule over the post-coexistence visibility-delta trajectory. Verdict Taxonomy. Based on these rules, Algorithm 1 evaluates each pair exactly once at 𝑅 ≥ 𝐻 (𝐴, 𝐵), yielding one of four verdict categories (where Edge may be instantiated as either Edge(𝐴 → 𝐵) or Edge(𝐵 → 𝐴)): Edge, if a one-sided strong signal is observed; Abstain-Truncated, if at least one AUF fails to mature; Abstain-Conflict, if both positive and negative strong signals are observed; and AbstainNoSignal, if no strong directional signal is observed. Abstention is MRV’s certification boundary. An abstained pair is left outside the evidence-backed precedence relation and remains residual ordering ambiguity in 𝐺𝑆 ; deterministic completion resolves this ambiguity only to obtain an executable total order. This separation lets MRV distinguish precedence supported by committed-DAG evidence from ordering choices made solely for deterministic executability. As a result, abstention reduces evidence coverage rather than evidence soundness: it may increase the portion of the final order determined by completion, but it does not turn unsupported evidence into a structural precedence claim. A

mature pair

(𝐴, 𝐵) ∈ 𝑆×𝑆. Therefore, once the committed frontier reaches 𝑅 ≥ 𝑇 (𝑆), every AUF in 𝑆 has reached its stopping time and every pairwise verdict is frozen. Precedence Graph Construction. At this sealing horizon, MRV constructs the slice-local precedence graph 𝐺𝑆 = (𝑆, 𝐸𝑆 ) with two classes of edges. The first class consists of hard causal constraints: 𝐸𝑆causal = {(𝐵, 𝐴) | 𝐴, 𝐵 ∈ 𝑆 ∧ 𝐵 ∈ Anc(𝐴)}. These edges require the final slice order to extend the committed DAG’s causal partial order. The second class consists of evidence-backed structural precedence edges: svp 𝐸𝑆 = {(𝐴, 𝐵) | the comparator returns Edge(𝐴 → 𝐵)}. svp MRV sets 𝐸𝑆 = 𝐸𝑆causal ∪ 𝐸𝑆 . Any abstention yields no svp evidence-backed edge in 𝐸𝑆 . Graph Linearization and Deterministic Completion. Because pairwise constraints are derived independently from local structural visibility, they need not be perfectly transitive. Independently justified edges may therefore form precedence cycles, making a graph-level assembly phase necessary. MRV identifies SCCs in 𝐺𝑆 and condenses them into a Directed Acyclic Graph (DAG) of SCCs, which is then linearized by deterministic topological ordering. Causal constraints represent the committed DAG’s partial order and are not treated as fairness claims. MRV’s structural fairness claims are derived solely from evidence-backed comsvp parator edges in 𝐸𝑆 . If evidence-backed edges create cycles, MRV treats the affected evidence as graph-level ambiguity: only constraints that survive SCC condensation are claimed as enforceable structural precedence. Causal constraints remain hard execution constraints throughout linearization. Within each SCC, MRV topologically orders the subgraph

B

A-over-B signal

f+1

A≻B B≻A

Δ(A,B)

B-over-A signal Round s(A,B)

Require: Pair (𝐴, 𝐵), stopping times, maturity flags, and visibility values up to 𝐻 (𝐴, 𝐵) 1: if ¬mature(𝐴) ∨ ¬mature(𝐵) then 2: return Abstain-Truncated 3: end if 4: 𝑠 ← max(𝑟 (𝐴), 𝑟 (𝐵)), 𝐻 ← max(ℎ𝐴 , ℎ 𝐵 ) 5: 𝑝𝑜𝑠 ← false, 𝑛𝑒𝑔 ← false 6: for 𝑡 = 𝑠 + 1 to 𝐻 do 7: Δ ← 𝐶𝐴 (𝑡) − 𝐶𝐵 (𝑡) 8: 𝑝𝑜𝑠 ← 𝑝𝑜𝑠 ∨ (Δ ≥ 𝑓 + 1) 9: 𝑛𝑒𝑔 ← 𝑛𝑒𝑔 ∨ (Δ ≤ −(𝑓 + 1)) 10: end for 11: if 𝑝𝑜𝑠 ∧ ¬𝑛𝑒𝑔 then 12: return Edge(𝐴 → 𝐵) 13: else if 𝑛𝑒𝑔 ∧ ¬𝑝𝑜𝑠 then 14: return Edge(𝐵 → 𝐴) 15: else if 𝑝𝑜𝑠 ∧ 𝑛𝑒𝑔 then 16: return Abstain-Conflict 17: else 18: return Abstain-NoSignal 19: end if

Post-coexistence window

-(f+1)

Abstain

H(A,B) pair horizon

Figure 4. Pairwise comparison and verdict extraction. For a mature pair (𝐴, 𝐵), MRV evaluates visibility deltas only after both AUFs coexist. An unopposed 𝑓 + 1 crossing yields 𝐴 → 𝐵; conflict or no strong signal yields abstention.

4.4

Slice Sealing, Precedence Graph Construction, and Linearization

While Algorithm 1 establishes pairwise constraints, MRV assembles these local verdicts into an executable total order. Slice Sealing. MRV defines the slice sealing time for a slice 𝑆 as 𝑇 (𝑆) = max𝑋 ∈𝑆 ℎ𝑋 . Since the pair horizon is 𝐻 (𝐴, 𝐵) = max(ℎ𝐴 , ℎ𝐵 ), it follows that 𝐻 (𝐴, 𝐵) ≤ 𝑇 (𝑆) for every pair 8

Multi-Round Visibility: A Post-Consensus Ordering Layer for DAG-Based BFT

induced by 𝐸𝑆causal and applies the deterministic key 𝜅 only among causally incomparable AUFs. Therefore, deterministic completion never violates causality or turns residual ordering choices into structural fairness claims. To make completion replica-consistent, MRV introduces an abstract deterministic key 𝜅 (𝑋 ) that induces the same total order over AUFs at all correct replicas. The key is used in two places. First, for an SCC 𝐶, MRV lifts the key as 𝜅 (𝐶) = min𝑋 ∈𝐶 𝜅 (𝑋 ) and uses it to break ties among simultaneously eligible SCCs in the condensation DAG. Second, within an SCC, 𝜅 (𝑋 ) is used only after the causal subgraph is enforced, as described above. In our prototype, 𝜅 (𝑋 ) is the lexicographic tuple (𝑟 (𝑋 ), cr(𝑋 ), dig(𝑋 )), where dig(𝑋 ) denotes the canonical digest of 𝑋 . After SCC condensation, topological ordering, and deterministic completion, the final sequence ≺𝑆 is delivered to the execution engine.

until every pair involving 𝑋 has frozen, because pairwise comparison may extend to a later horizon 𝐻 (𝐴, 𝐵). Once both ℎ𝐴 and ℎ𝐵 are known, the pair horizon 𝐻 (𝐴, 𝐵) becomes known as well. Whenever the frontier satisfies 𝑅 ≥ 𝐻 (𝐴, 𝐵), the pair (𝐴, 𝐵) is evaluated exactly once using Algorithm 1, and its verdict is frozen permanently. Finally, when 𝑅 ≥ 𝑇 (𝑆) for active slice 𝑆, every AUF in 𝑆 has reached its stopping time and every pairwise verdict is frozen. MRV then constructs the precedence graph 𝐺𝑆 , performs SCC condensation and deterministic topological linearization, applies the completion key 𝜅 to resolve residual ambiguity, outputs the final order ≺𝑆 , and releases all state for 𝑆. Because evidence accumulation is bounded by 𝑊max and each pair is frozen at most once, the online procedure maintains bounded active state and avoids unbounded retrospective dependence on the committed DAG. Algorithm 2 MRV Processing at Committed Frontier 𝑅

4.5 Online Replica Procedure and State Management

Require: New committed frontier round 𝑅, canonical AUFs {𝑌𝑐,𝑅 }, active slices, and MRV state 1: Initialize 𝐶𝑋 (𝑅) ← 0 for each active AUF 𝑋 2: for each canonical AUF 𝑌𝑐,𝑅 do 3: for each active AUF 𝑋 ∈ Anc(𝑌𝑐,𝑅 ) reached by bounded traversal do 4: 𝐶𝑋 (𝑅) ← 𝐶𝑋 (𝑅) + 1 5: end for 6: end for 7: for each active AUF 𝑋 with ℎ𝑋 undefined do 8: if 𝐶𝑋 (𝑅) ≥ 2𝑓 + 1 then 9: ℎ𝑋 ← 𝑅; mature(𝑋 ) ← true 10: else if 𝑅 ≥ 𝑟 (𝑋 ) + 𝑊max then 11: ℎ𝑋 ← 𝑟 (𝑋 ) + 𝑊max ; mature(𝑋 ) ← false 12: end if 13: end for 14: for each unfrozen pair (𝐴, 𝐵) with ℎ𝐴 , ℎ 𝐵 defined and 𝑅 ≥ 𝐻 (𝐴, 𝐵) do 15: Freeze verdict(𝐴, 𝐵) ← PairwiseVerdict(𝐴, 𝐵) 16: end for 17: for each active slice 𝑆 with all ℎ𝑋 defined and 𝑅 ≥ 𝑇 (𝑆) do 18: Build 𝐺𝑆 from causal edges and frozen Edge verdicts 19: Condense SCCs and topologically order the SCCDAG using 𝜅 (𝐶) 20: Order each SCC by causal constraints, then 𝜅 (𝑋 ) 21: Output ≺𝑆 and release state for 𝑆 22: end for

MRV is implemented as an incremental online procedure driven by the advancing committed frontier. This procedure demonstrates that MRV avoids offline hindsight reconstruction; instead, it updates ordering evidence incrementally as the base protocol advances the committed frontier. Rather than deferring all computation until a slice seals, each replica maintains bounded active state for every unsealed slice and updates that state whenever a new committed round becomes available. For each active AUF 𝑋 , MRV stores (i) the per-round structural visibility profile {𝐶𝑋 (𝑡)} over the rounds observed so far within the relevant horizon, (ii) the stopping time ℎ𝑋 if already determined, and (iii) the maturity flag mature(𝑋 ). For each active pair (𝐴, 𝐵), MRV stores whether the pairwise verdict has already been frozen and, if so, the frozen outcome returned by Algorithm 1. For each active slice 𝑆, MRV stores the member AUFs together with the intermediate data needed to construct 𝐺𝑆 once the slice seals. When a new committed frontier round 𝑅 is delivered, the replica first materializes the canonical committed AUFs {𝑌𝑐,𝑅 }𝑐 , if any. For every active AUF 𝑋 , MRV initializes the current-round visibility count 𝐶𝑋 (𝑅) to zero. It then performs a bounded backward traversal from each canonical AUF 𝑌𝑐,𝑅 through its committed ancestors and increments 𝐶𝑋 (𝑅) for every active AUF 𝑋 encountered. This traversal is restricted to active AUFs within the relevant bounded horizon, rather than the entire historical DAG. This yields the creator-level structural visibility counts for round 𝑅 without relying on local receive order or external timing signals. These round-𝑅 counts are then used to settle AUF stopping times. If ℎ𝑋 is still undefined and 𝐶𝑋 (𝑅) ≥ 2𝑓 + 1, MRV fixes ℎ𝑋 := 𝑅 and marks 𝑋 as mature. If ℎ𝑋 remains undefined and 𝑅 ≥ 𝑟 (𝑋 ) +𝑊max , MRV caps 𝑋 at ℎ𝑋 := 𝑟 (𝑋 ) +𝑊max and marks it as immature. Fixing ℎ𝑋 does not terminate visibility tracking for 𝑋 : MRV continues to record later 𝐶𝑋 (𝑡) values

4.6

Adversarial Influence and Conservative Failure Mode

MRV treats Byzantine behavior as part of the committedDAG evidence surface. Faulty creators may influence structural visibility through their own parent choices, omissions, 9

Ren et al.

the same completion key 𝜅, then they output the same total order ≺𝑆 .

equivocations handled by the base exporter, or message scheduling effects permitted by the base protocol. However, MRV counts visibility at creator granularity, and each creator contributes at most one canonical visibility observation per round. Therefore, Byzantine-only contributions can account for at most 𝑓 units of a directional visibility margin in any round; an 𝑓 + 1 margin necessarily extends beyond Byzantine creator contributions. The effect of adversarial behavior is captured by MRV’s verdict taxonomy. Suppressed or delayed visibility may prevent maturity and lead to Abstain-Truncated; opposing strong visibility patterns lead to Abstain-Conflict; weak or insufficient directional evidence leads to Abstain-NoSignal. In each case, the svp pair remains outside 𝐸𝑆 and is resolved only as residual ambiguity during deterministic completion. Thus, adversarial influence can reduce MRV’s evidence coverage, but it does not change the rule by which MRV certifies structural precedence edges. 4.7

Proof sketch. Visibility counts, stopping times, maturity flags, pair horizons, frozen verdicts, and graph edges are deterministic functions of the common committed prefix. SCC condensation, topological ordering, and completion by 𝜅 are deterministic, so replicas output the same ≺𝑆 . Theorem 4 (Bounded Completion). For any committed execution slice 𝑆, if the base stack eventually exports a committed frontier 𝑅 ≥ 𝑇 (𝑆), then MRV eventually seals ≺𝑆 . Moreover, for every 𝑋 ∈ 𝑆, ℎ𝑋 ≤ 𝑟 (𝑋 ) + 𝑊max,

𝑋 ∈𝑆

Proof sketch. The cap round 𝑟 (𝑋 ) + 𝑊max is always included in the definition of ℎ𝑋 , so every stopping time is bounded. Once 𝑅 ≥ 𝑇 (𝑆), all pair horizons are covered and MRV performs only finite local graph construction and deterministic completion.

Complexity, State Bound, and Practical Cost Drivers

Theorem 5 (Slice Locality and Causal Consistency). MRV outputs a total order only over AUFs in 𝑆. If 𝐴, 𝐵 ∈ 𝑆 and 𝐵 ∈ Anc(𝐴), then 𝐵 ≺𝑆 𝐴.

Algorithm 2 adds bounded local overhead above the base DAG-BFT stack. MRV introduces no consensus-path messages and no extra cryptographic verification; its cost comes from bounded backward traversal for visibility updates, pairwise verdict evaluation over AUFs in a slice, and SCC condensation/topological linearization once the slice seals. For a slice of size |𝑆 |, a direct implementation performs 𝑂 (|𝑆 | 2𝑊max ) pairwise verdict work and 𝑂 (|𝑆 | 2 ) slice-local graph assembly in the worst case. The quadratic factor is over AUFs, not individual transactions; transaction ordering inherits the AUF order through containment. Active perslice state is bounded by visibility profiles over at most 𝑊max rounds together with 𝑂 (|𝑆 | 2 ) pair verdict state, and all state for 𝑆 is released once 𝑅 ≥ 𝑇 (𝑆). Thus, MRV bounds the additional committed-round evidence horizon by 𝑊max ; progress of the committed frontier remains the responsibility of the base protocol. A fuller cost breakdown is provided in the supplementary material. 4.8

𝑇 (𝑆) ≤ max (𝑟 (𝑋 ) + 𝑊max ).

Proof sketch. The precedence graph has vertex set 𝑆; descendants outside 𝑆 are used only as evidence. MRV inserts hard causal edges for same-slice ancestry and preserves them either in the condensation-DAG order or inside SCCs before applying 𝜅. Theorem 6 (Soundness of Evidence-Backed Edges). Every svp evidence-backed edge Edge(𝐴 → 𝐵) inserted into 𝐸𝑆 by MRV corresponds to 𝐴 ⊲SVP 𝐵 in the committed DAG. Proof sketch. The comparator emits Edge(𝐴 → 𝐵) only when both AUFs are mature, the post-coexistence window contains a positive 𝑓 + 1 visibility margin, and it contains no opposing strong signal. These are exactly the SVP conditions. Theorem 7 (Completeness for Structural Visibility Precedence). For any pair (𝐴, 𝐵) in 𝑆, if 𝐴 ⊲SVP 𝐵, then MRV freezes svp Edge(𝐴 → 𝐵) once 𝑅 ≥ 𝐻 (𝐴, 𝐵) and includes (𝐴, 𝐵) in 𝐸𝑆 when 𝑆 is sealed.

Analysis and Guarantees

Proof sketch. At 𝑅 ≥ 𝐻 (𝐴, 𝐵), all rounds in the post-coexistence window are fixed. Since SVP is exactly the mature, one-sided, non-conflicting strong-signal condition tested by the comparator, MRV freezes the edge verdict and later inserts it into the sealed precedence graph. A certified SVP edge is enforceable if its endpoints lie in distinct SCCs of the sealed precedence graph and therefore induce a constraint in the condensation DAG.

We analyze MRV as a deterministic post-consensus interpretation layer over the exporter interface in Section 3. The base DAG-BFT stack provides a common committed DAG prefix and a common ordered sequence of committed execution slices; MRV deterministically maps these exported objects to slice-local execution orders. We summarize the main guarantees below and provide full proofs in the supplementary material.

Theorem 8 (Conditional AUF-Level Structural Fairness). For any committed execution slice 𝑆, MRV’s final order ≺𝑆 preserves every enforceable certified SVP relation. Deterministic completion introduces no structural precedence claims.

Theorem 3 (Deterministic Agreement). For any committed execution slice 𝑆, if two correct replicas observe the same exported committed prefix up to 𝑅 ≥ 𝑇 (𝑆), the same 𝑊max , and 10

Multi-Round Visibility: A Post-Consensus Ordering Layer for DAG-Based BFT

Proof sketch. Any enforceable certified SVP edge appears as an edge in the condensation DAG, so every topological order places its source SCC before its destination SCC. Edges absorbed into SCCs are treated as graph-level ambiguity; completion by 𝜅 resolves only residual choices and is not svp inserted into 𝐸𝑆 .

5

voting logic, or the consensus commit rule; its additional work is local post-consensus processing over committed metadata. We also implement a DoD-style graph-ordering reference following DoD [22]. We include DoD because it is the closest order-fairness design built for a DAG-BFT setting, incorporating explicit graph-based ordering evidence into the system pipeline. Built on the same Narwhal/Tusk codebase, it changes the path before consensus delivery: workers disseminate local-order graphs through Narwhal’s mempool, derive global-order graphs locally, and process those graphs in the role normally played by Tusk batches. We report throughput as ordered transactions per second (TPS), measured after the corresponding ordering pipeline produces its output. We report end-to-end latency as the time from client submission until the transaction is output by the evaluated pipeline. For native Narwhal/Tusk, this is the latency reported by the original implementation; for MRV and the DoD-style baseline, it includes the additional ordering work performed by the corresponding layer. Unless otherwise specified, each experiment follows the Narwhal/Tusk configuration: one worker per validator, colocated benchmark clients, 512B transactions, 500KB batches, 1KB headers, a 200ms maximum batch delay, a 200ms maximum header delay, and a 50-round garbage-collection depth. Individual experiments vary the offered load, batch size, or configured fault setting from this baseline as described below.

Evaluation

We evaluate MRV as a post-consensus structural ordering layer for a Narwhal/Tusk-style DAG-BFT stack. The evaluation asks whether MRV preserves the throughput-oriented design point of DAG-based BFT while adding limited postcommit ordering delay and local computation. We compare three configurations: native Narwhal/Tusk, Narwhal/Tusk with MRV enabled, and a DoD-style graph-ordering reference implemented in the same experimental harness. These configurations separate three design points: fairness-agnostic deterministic traversal, MRV’s post-consensus interpretation of committed DAG evidence, and explicit graph-based ordering incorporated into the system pipeline. Our experiments vary in offered load, fault setting, and batch size. The offered-load experiment measures whether MRV sustains the native throughput/latency curve as clients increase pressure on the system. The fault-setting experiment evaluates how MRV behaves as quorum and visibility thresholds change. The batch-size experiment studies how MRV interacts with the payload granularity of DAG vertices, which affects both base dissemination and post-consensus ordering work.

Latency （ ms）

5.1

15000

Experimental Setup

Deployment. To match the wide-area setting targeted by DAG-based BFT protocols, we follow the geo-distributed methodology used by Narwhal/Tusk. We deploy validators on Amazon Web Services using m5.xlarge instances across five regions: N. Virginia (us-east-1), N. California (us-west1), Sydney (ap-southeast-2), Stockholm (eu-north-1), and Tokyo (ap-northeast-1). Each instance hosts one validator. Benchmark clients submit transactions at controlled offered loads for a fixed experiment duration. Implementation. Our implementation starts from the open-source Narwhal/Tusk codebase 1 . In the native baseline, committed DAG outputs are delivered using the protocol’s standard deterministic traversal. MRV is added as a separate ordering layer between consensus delivery and execution. Concretely, after Tusk commits a leader and exports the corresponding committed DAG output, MRV constructs the committed execution slice by selecting newly delivered AUFs, maintains the active per-slice visibility state, freezes pairwise verdicts once their horizons are reached, assembles the precedence graph, and outputs a slice-local execution order. MRV does not change Narwhal’s worker dissemination, Tusk’s

MRV n=5 MRV n=10 MRV n=20 MRV n=50

10000

Narwhal/Tusk n=5 Narwhal/Tusk n=10 Narwhal/Tusk n=20 Narwhal/Tusk n=50

DoD n=5 DoD n=10 DoD n=20

5000

0 0

50000

100000

150000

200000

Throughput (tx/s)

Figure 5. Comparative throughput-latency performance for MRV, Narwhal/Tusk and DoD.

5.2

Throughput and Latency under Offered Load

We first measure the throughput-latency envelope under increasing offered load. Figure 5 reports achieved TPS and end-to-end ordering latency for native Narwhal/Tusk, Narwhal/Tusk with MRV, and the DoD-style graph-ordering reference in the same geo-distributed harness. Across committee sizes, Narwhal/Tusk and MRV exhibit the expected saturation pattern. Throughput initially increases with offered load while latency remains relatively stable; after the knee point, additional load no longer improves throughput, and latency grows rapidly. MRV follows the same overall envelope as the native pipeline. With 5

1 https://github.com/asonnino/narwhal

11

Ren et al.

validators, MRV reaches 144K TPS, matching the native configuration. With 10 validators, MRV reaches 210K TPS, comparable to the native peak. With 20 validators, both systems remain in the 200K TPS regime. In the 50-validator geodistributed deployment, MRV still sustains more than 140K TPS, showing that the post-consensus ordering layer remains compatible with high-throughput DAG-BFT execution at a larger scale. The primary cost of MRV appears in latency rather than peak throughput. Before saturation, MRV adds a moderate end-to-end delay relative to native Narwhal/Tusk, reflecting bounded visibility accumulation and slice-local graph completion after commitment. This behavior is consistent with MRV’s placement: ordering work is kept outside the consensus message path, but it still contributes to the final output latency observed by clients. The DoD-style reference occupies a lower-throughput, higher-latency region in this geo-distributed harness, consistent with the cost of constructing and disseminating explicit ordering graphs through the system pipeline. MRV instead reuses committed DAG structure after consensus, so its overhead appears primarily as bounded post-commit ordering delay rather than reduced peak throughput.

upward because stronger visibility thresholds require additional committed-DAG evidence before AUFs and pairwise verdicts can seal. The native curves provide a baseline for the underlying DAG-BFT pipeline; the additional upward shift of MRV reflects post-consensus evidence collection rather than extra consensus-path communication. Overall, in this configuration and offered-load range, changing 𝑓 is most visible in MRV’s ordering latency. This matches MRV’s design: larger 𝑓 raises the local evidence thresholds used for maturity and pairwise precedence, while MRV itself does not add consensus-path messages.

Latency (ms)

8000

MRV (100k)

Narwhal/Tusk (500k)

DoD (100k)

MRV (300k)

Narwhal/Tusk (300k)

DoD (100k)

MRV (500k)

Narwhal/Tusk (100k)

DoD (500k)

6000

4000

2000

0 0

50000

100000

150000

200000

Throughput (tx/s)

Latency (ms)

10000

MRV (f=1)

Narwhal/Tusk (f=1)

MRV (f=3)

Narwhal/Tusk (f=3)

Figure 7. Throughput-latency under different batch sizes. 5.4

We study the effect of batch size on MRV. This experiment fixes the committee size at 10 validators and varies the batch size while measuring TPS and end-to-end ordering latency. We use this setting to isolate payload granularity: batch size changes the amount of transaction data carried by each DAG unit, while MRV’s ordering work is primarily over committed AUFs and their visibility relations. Figure 7 shows that MRV and native Narwhal/Tusk are insensitive to the tested batch sizes. Across 100KB, 300KB, and 500KB batches, MRV remains in the same high-throughput regime and follows the saturation pattern observed in the offered-load experiment. This suggests that MRV’s postconsensus ordering cost is driven mainly by the number of committed AUFs and pairwise visibility processing, rather than by transaction payload size. The DoD-style reference remains in a lower-throughput region in the geo-distributed deployment. In this setting, wide-area dissemination and graph-processing overhead dominate the batch-size effect. The supplementary material discusses deployment differences and the role of data-dependent workload structure in interpreting our DoD-style measurements relative to DoD’s published evaluation.

0 0

50000

100000

150000

200000

Throughput (tx/s)

Figure 6. Throughput-latency under different configured fault-tolerance parameters.

5.3

Impact of Batch Size

5000

Impact of Fault Setting

We next vary the configured fault-tolerance parameter while fixing the committee size at 10 validators. This experiment compares native Narwhal/Tusk and Narwhal/Tusk with MRV under 𝑓 = 1 and 𝑓 = 3. The parameter directly affects MRV’s evidence thresholds: AUF maturity uses the 2𝑓 + 1 visibility threshold, while pairwise structural precedence uses an 𝑓 + 1 one-sided visibility margin. Figure 6 shows that changing the configured 𝑓 has limited effect on achieved throughput in this deployment: both native Narwhal/Tusk and MRV remain near the same highthroughput region before saturation. The main effect appears in latency. Under 𝑓 = 1, MRV adds a moderate latency gap relative to native Narwhal/Tusk while maintaining a similar saturation point. Under 𝑓 = 3, the MRV curve shifts

6

Conclusion

MRV is a post-consensus ordering layer that reuses committed DAG structure as execution-ordering evidence. By 12

Multi-Round Visibility: A Post-Consensus Ordering Layer for DAG-Based BFT

and communications security. [16] Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. 2020. Order-fairness for byzantine consensus. In Annual International Cryptology Conference. [17] 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. 25–36. [18] Zhuolun Li and Evangelos Pournaras. 2024. SoK: Consensus for Fair Message Ordering. arXiv preprint arXiv:2411.09981 (2024). [19] Erwan Mahe and Sara Tucci-Piergiovanni. 2025. Order Fairness Evaluation of DAG-based ledgers. In 2025 7th International Conference on Blockchain Computing and Applications (BCCA). 106–114. [20] Dahlia Malkhi and Pawel Szalachowski. 2022. Maximal extractable value (mev) protection on a dag. arXiv preprint arXiv:2208.00940 (2022). [21] Ke Mu, Bo Yin, Alia Asheralieva, and Xuetao Wei. [n. d.]. Separation is good: A faster order-fairness Byzantine consensus. ([n. d.]). [22] Heena Nagda, Sidharth Sankhe, Sakshi Sinha, Keon Attarha, Mohammad Javad Amiri, and Boon Thau Loo. 2025. Dag of dags: Orderfairness made practical. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–27. [23] Kaihua Qin, Liyi Zhou, and Arthur Gervais. 2022. Quantifying blockchain extractable value: How dark is the forest?. In 2022 IEEE Symposium on Security and Privacy (SP). [24] Fred B Schneider. 1990. Implementing fault-tolerant services using the state machine approach: A tutorial. Acm Computing Surveys (CSUR) (1990). [25] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. 2022. Bullshark: Dag bft protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2705–2718. [26] Qin Wang, Jiangshan Yu, Shiping Chen, and Yang Xiang. 2023. SoK: DAG-based blockchain systems. Comput. Surveys 55, 12 (2023), 1–38. [27] Jie Xu, Cong Wang, and Xiaohua Jia. 2023. A survey of blockchain consensus protocols. Comput. Surveys (2023). [28] 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. [29] Gengrui Zhang, Fei Pan, Yunhao Mao, Sofia Tijanic, Michael Dang’Ana, Shashank Motepalli, Shiquan Zhang, and Hans-Arno Jacobsen. 2024. Reaching consensus in the byzantine empire: A comprehensive review of bft consensus algorithms. Comput. Surveys (2024). [30] Yunhao Zhang, Srinath 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 20). 633–649. [31] Liyi Zhou, Kaihua Qin, Christof Ferreira Torres, Duc V Le, and Arthur Gervais. 2021. High-frequency trading on decentralized on-chain exchanges. In 2021 IEEE Symposium on Security and Privacy (SP).

extracting creator-level visibility from authenticated round and ancestry metadata, MRV adds conservative AUF-level precedence constraints while bounding evidence collection and preserving causal consistency. Our prototype shows that this design preserves the high-throughput regime of the base DAG-BFT stack with limited overhead, offering a practical control point for structural ordering without moving ordering logic onto the consensus path.

References [1] Carsten Baum, James Hsin-yu Chiang, Bernardo David, Tore Kasper Frederiksen, and Lorenzo Gentile. 2022. Sok: Mitigation of frontrunning in decentralized finance. In International Conference on Financial Cryptography and Data Security. [2] Alysson Bessani, João Sousa, and Eduardo EP Alchieri. 2014. State machine replication for the masses with BFT-SMART. In 2014 44th Annual IEEE/IFIP international conference on dependable systems and networks. 355–362. [3] Christian Cachin, Jovana Mićić, Nathalie Steinhauer, and Luca Zanolini. 2022. Quick order fairness. In International Conference on Financial Cryptography and Data Security. 316–333. [4] Miguel Castro, Barbara Liskov, et al. 1999. Practical byzantine fault tolerance. In OsDI. [5] 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. [6] Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. 2020. Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In 2020 IEEE symposium on security and privacy (SP). [7] 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. 34–50. [8] Shayan Eskandari, Seyedehmahsa Moosavi, and Jeremy Clark. 2019. Sok: Transparent dishonesty: front-running attacks on blockchain. In International Conference on Financial Cryptography and Data Security. [9] Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. 2022. Dumbo-ng: Fast asynchronous bft consensus with throughput-oblivious latency. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. [10] Vincent Gramlich, Dennis Jelito, and Johannes Sedlmeir. 2024. Maximal extractable value: Current understanding, categorization, and open research questions. Electronic Markets 34, 1 (2024), 49. [11] Bingyong Guo, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. 2020. Dumbo: Faster asynchronous bft protocols. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. [12] Lioba Heimbach and Roger Wattenhofer. 2022. Eliminating sandwich attacks with the help of game theory. In Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security. [13] 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. 165–175. [14] Mahimna Kelkar, Soubhik Deb, and Sreeram Kannan. 2022. Order-fair consensus in the permissionless setting. In Proceedings of the 9th ACM on ASIA Public-Key Cryptography Workshop. 3–14. [15] 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 13