pith. sign in

arxiv: 2605.23432 · v1 · pith:22S23HM4new · submitted 2026-05-22 · 💻 cs.DC

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

Pengkun Ren , Dong Hai , Nasrin Sohrabi , Zahir Tari This is my paper

Pith reviewed 2026-05-25 03:06 UTC · model grok-4.3

classification 💻 cs.DC
keywords multi-round visibilityDAG-based BFTpost-consensus orderingstructural orderingByzantine fault tolerancefair orderingdirected acyclic graphhigh-throughput consensus
0
0 comments X

The pith

MRV derives structural ordering for concurrent DAG commits from vertex metadata after consensus finishes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents Multi-Round Visibility as a post-consensus layer that turns the already-committed DAG into an ordering evidence substrate. It establishes that replicas can accumulate multi-round visibility from each vertex's authenticated creator, round, and ancestry data and then compare atomic units of fairness once they coexist in the graph. This separation matters because prior fair-ordering methods placed evidence collection inside the agreement workflow and slowed the critical path. If the claim holds, DAG-BFT stacks keep their concurrent-commit throughput while still producing a verifiable linearization at the execution boundary. The remaining ambiguities are resolved by explicit deterministic graph completion rather than hidden traversal rules.

Core claim

MRV reinterprets the committed DAG as an ordering evidence substrate. Committed vertices inherently carry authenticated creator, round, and ancestry metadata, enabling replicas to derive multi-round structural visibility without extra consensus-path messages. MRV accumulates this visibility within a bounded evidence horizon, compares concurrently committed atomic units of fairness after they coexist in the DAG, and derives precedence constraints from Byzantine-robust visibility advantages. When the DAG lacks such constraints, MRV exposes and resolves the remaining ambiguity through deterministic graph completion rather than hiding it inside traversal rules.

What carries the argument

Multi-Round Visibility (MRV), a post-consensus layer that accumulates visibility from committed vertices' authenticated metadata and derives precedence constraints from visibility advantages across rounds.

If this is right

  • Ordering logic runs entirely after consensus completes and therefore leaves the agreement critical path unchanged.
  • Atomic units of fairness are compared only after they have coexisted in the DAG for multiple rounds, enabling visibility-based precedence.
  • Byzantine-robust visibility advantages supply the precedence constraints used for linearization.
  • Any remaining ordering ambiguity is surfaced and resolved by deterministic graph completion.
  • Throughput stays within the high-throughput regime measured for the underlying Narwhal/Tusk stack.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same metadata-driven approach could be applied to other DAG constructions that already embed creator and round information.
  • The bounded evidence horizon size may need tuning when round duration or network diameter changes.
  • Visibility advantages might be checked against additional fairness notions such as censorship resistance in follow-on analysis.

Load-bearing premise

Committed vertices carry authenticated creator, round, and ancestry metadata sufficient for replicas to derive consistent multi-round structural visibility without extra consensus-path messages.

What would settle it

An execution trace in which two correct replicas produce inconsistent orderings from identical committed DAG frontiers under the MRV rules, or a throughput measurement showing the MRV layer reduces the baseline DAG-BFT rate under the evaluated fault settings.

Figures

Figures reproduced from arXiv: 2605.23432 by Dong Hai, Nasrin Sohrabi, Pengkun Ren, Zahir Tari.

Figure 1
Figure 1. Figure 1: DAG-BFT architecture and committed execution slice. Replicas broadcast availability-certified vertices (cir￾cles) that reference a quorum of prior-round vertices (ar￾rows), 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 at… view at source ↗
Figure 2
Figure 2. 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 … view at source ↗
Figure 3
Figure 3. Figure 3: Structural visibility accumulation and AUF stop￾ping 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. 4.3 Pairwise Verdicts from Post-Coexistence Evidence Given the stopping timeℎ𝑋 and maturity indicator mature(𝑋) of each AUF, MRV converts… view at source ↗
Figure 4
Figure 4. 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. … view at source ↗
Figure 5
Figure 5. 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 [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: Throughput-latency under different batch sizes. 5.4 Impact of Batch Size 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 … view at source ↗
Figure 6
Figure 6. Figure 6: Throughput-latency under different configured fault-tolerance parameters. 5.3 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, … view at source ↗
read the original abstract

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 ordering evidence at the execution boundary: once units are committed in a shared DAG frontier, their final linearization is driven by traversal or deterministic tie-breaking rather than verifiable structural precedence. Prior fair-ordering designs address ambiguity by collecting or reconstructing transaction-level ordering evidence within the consensus workflow. While effective, this couples ordering with agreement and places ordering logic on the critical path. This paper presents Multi-Round Visibility (MRV), a post-consensus structural ordering layer for DAG-based BFT that reinterprets the committed DAG as an ordering evidence substrate. Committed vertices inherently carry authenticated creator, round, and ancestry metadata, enabling replicas to derive multi-round structural visibility without extra consensus-path messages. MRV accumulates this visibility within a bounded evidence horizon, compares concurrently committed atomic units of fairness (AUFs) after they coexist in the DAG, and derives precedence constraints from Byzantine-robust visibility advantages. When the DAG lacks such constraints, MRV exposes and resolves the remaining ambiguity through deterministic graph completion rather than hiding it inside traversal rules. We implement MRV on a Narwhal/Tusk-based prototype. Evaluation across 5-50 replicas under various fault settings shows MRV preserves the high-throughput regime of the DAG-BFT stack, proving it provides post-consensus structural ordering without burdening the consensus-critical path.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper claims that Multi-Round Visibility (MRV) provides a post-consensus structural ordering layer for DAG-based BFT protocols. Committed vertices carry authenticated creator, round, and ancestry metadata that replicas can use to derive multi-round structural visibility within a bounded evidence horizon, compare concurrently committed atomic units of fairness (AUFs), and obtain precedence constraints from visibility advantages. When constraints are absent, deterministic graph completion resolves residual ambiguity. MRV is implemented on a Narwhal/Tusk prototype; evaluation with 5-50 replicas under various faults shows that high throughput is preserved, demonstrating that ordering can be added without burdening the consensus-critical path.

Significance. If the central claim holds, MRV would allow DAG-BFT stacks to add verifiable structural ordering after consensus without extra messages or latency on the critical path. This separation could be useful for applications that need both high throughput and fairness properties. The use of an existing prototype for evaluation is a positive aspect, as it directly tests integration overhead.

major comments (2)
  1. [MRV design description] MRV design description (abstract and design paragraphs): The claim that existing authenticated creator/round/ancestry metadata in committed vertices is sufficient to compute Byzantine-robust multi-round visibility and consistent precedence constraints lacks any formal model, invariant, or proof. No argument is supplied showing that the resulting partial order is identical at all correct replicas or that it cannot be influenced by equivocation or omission by up to f faulty nodes. The reliance on deterministic graph completion to resolve ambiguity is stated but not shown to guarantee safety.
  2. [Evaluation section] Evaluation section (abstract): Throughput preservation is asserted for the Narwhal/Tusk prototype under faults, yet no quantitative results, baselines, error bars, or latency measurements are provided. Without these data it is impossible to verify that MRV imposes no measurable burden on the consensus path or that the ordering layer scales as claimed.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful comments. We address each major point below and will revise the manuscript to strengthen the formal foundations and expand the evaluation presentation.

read point-by-point responses

  1. Referee: [MRV design description] MRV design description (abstract and design paragraphs): The claim that existing authenticated creator/round/ancestry metadata in committed vertices is sufficient to compute Byzantine-robust multi-round visibility and consistent precedence constraints lacks any formal model, invariant, or proof. No argument is supplied showing that the resulting partial order is identical at all correct replicas or that it cannot be influenced by equivocation or omission by up to f faulty nodes. The reliance on deterministic graph completion to resolve ambiguity is stated but not shown to guarantee safety.

    Authors: We acknowledge that the manuscript presents MRV at a descriptive level and does not include a dedicated formal model, invariants, or proofs of consistency and safety. The design builds on the authenticated metadata and commitment guarantees of the underlying DAG-BFT protocol, but we agree a rigorous argument is needed. We will add a new section that defines multi-round visibility formally, states invariants ensuring identical partial orders at correct replicas and resilience to equivocation/omission by f faults, and provides a proof sketch for the safety of deterministic graph completion. revision: yes

  2. Referee: [Evaluation section] Evaluation section (abstract): Throughput preservation is asserted for the Narwhal/Tusk prototype under faults, yet no quantitative results, baselines, error bars, or latency measurements are provided. Without these data it is impossible to verify that MRV imposes no measurable burden on the consensus path or that the ordering layer scales as claimed.

    Authors: The abstract summarizes the evaluation outcomes, but the full evaluation section indeed presents only high-level claims without the supporting quantitative data. We will revise the evaluation section to include the concrete results from the 5-50 replica experiments: throughput numbers under fault-free and faulty scenarios, latency measurements, baseline comparisons against the unmodified Narwhal/Tusk stack, and error bars demonstrating that MRV adds no measurable overhead to the consensus path. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation uses existing DAG metadata as independent substrate

full rationale

The paper presents MRV as reinterpreting committed DAG vertices' authenticated creator/round/ancestry fields to derive visibility and precedence post-consensus. No equations, fitted parameters, or self-citations are shown that reduce the ordering rules to quantities defined by the target result itself. The approach is described as reading pre-existing metadata without additional consensus-path messages or new fitted inputs. Evaluation is empirical on Narwhal/Tusk prototype under faults, but the core claim does not collapse to a self-definitional or self-citation chain. Absence of a formal invariant is a potential correctness gap, not evidence of circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no equations, parameters, or explicit assumptions are visible beyond the high-level claim that existing vertex metadata suffices.

pith-pipeline@v0.9.0 · 5811 in / 1179 out tokens · 22833 ms · 2026-05-25T03:06:58.911259+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Carsten Baum, James Hsin-yu Chiang, Bernardo David, Tore Kasper Frederiksen, and Lorenzo Gentile. 2022. Sok: Mitigation of front- running in decentralized finance. InInternational Conference on Finan- cial Cryptography and Data Security

    work page 2022

  2. [2]

    Alysson Bessani, João Sousa, and Eduardo EP Alchieri. 2014. State machine replication for the masses with BFT-SMART. In2014 44th Annual IEEE/IFIP international conference on dependable systems and networks. 355–362

    work page 2014

  3. [3]

    Christian Cachin, Jovana Mićić, Nathalie Steinhauer, and Luca Zano- lini. 2022. Quick order fairness. InInternational Conference on Financial Cryptography and Data Security. 316–333

    work page 2022

  4. [4]

    Miguel Castro, Barbara Liskov, et al. 1999. Practical byzantine fault tolerance. InOsDI

    work page 1999

  5. [5]

    Wuhui Chen, Yikai Feng, Jianting Zhang, Zhongteng Cai, Hong-Ning Dai, and Zibin Zheng. 2024. Auncel: Fair byzantine consensus protocol with high performance. InIEEE INFOCOM 2024-IEEE Conference on Computer Communications

    work page 2024

  6. [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. In2020 IEEE symposium on security and privacy (SP)

    work page 2020

  7. [7]

    George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexan- der Spiegelman. 2022. Narwhal and tusk: a dag-based mempool and efficient bft consensus. InProceedings of the Seventeenth European Conference on Computer Systems. 34–50

    work page 2022

  8. [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

    work page 2019

  9. [9]

    Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhen- feng Zhang. 2022. Dumbo-ng: Fast asynchronous bft consensus with throughput-oblivious latency. InProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

    work page 2022

  10. [10]

    Vincent Gramlich, Dennis Jelito, and Johannes Sedlmeir. 2024. Max- imal extractable value: Current understanding, categorization, and open research questions.Electronic Markets34, 1 (2024), 49

    work page 2024

  11. [11]

    Bingyong Guo, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. 2020. Dumbo: Faster asynchronous bft protocols. InProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security

    work page 2020

  12. [12]

    Lioba Heimbach and Roger Wattenhofer. 2022. Eliminating sandwich attacks with the help of game theory. InProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security

    work page 2022

  13. [13]

    Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021. All you need is dag. InProceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 165–175

    work page 2021

  14. [14]

    Mahimna Kelkar, Soubhik Deb, and Sreeram Kannan. 2022. Order-fair consensus in the permissionless setting. InProceedings of the 9th ACM on ASIA Public-Key Cryptography Workshop. 3–14

    work page 2022

  15. [15]

    Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and Sreeram Kannan. 2023. Themis: Fast, strong order-fairness in byzantine con- sensus. InProceedings of the 2023 acm sigsac conference on computer and communications security

    work page 2023

  16. [16]

    Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. 2020. Order-fairness for byzantine consensus. InAnnual International Cryp- tology Conference

    work page 2020

  17. [17]

    Klaus Kursawe. 2020. Wendy, the good little fairness widget: Achiev- ing order fairness for blockchains. InProceedings of the 2nd ACM Conference on Advances in Financial Technologies. 25–36

    work page 2020

  18. [18]

    Zhuolun Li and Evangelos Pournaras. 2024. SoK: Consensus for Fair Message Ordering.arXiv preprint arXiv:2411.09981(2024)

    work page arXiv 2024

  19. [19]

    Erwan Mahe and Sara Tucci-Piergiovanni. 2025. Order Fairness Eval- uation of DAG-based ledgers. In2025 7th International Conference on Blockchain Computing and Applications (BCCA). 106–114

    work page 2025

  20. [20]

    Dahlia Malkhi and Pawel Szalachowski. 2022. Maximal extractable value (mev) protection on a dag.arXiv preprint arXiv:2208.00940(2022)

    work page arXiv 2022

  21. [21]

    Ke Mu, Bo Yin, Alia Asheralieva, and Xuetao Wei. [n. d.]. Separation is good: A faster order-fairness Byzantine consensus. ([n. d.])

    work page

  22. [22]

    Heena Nagda, Sidharth Sankhe, Sakshi Sinha, Keon Attarha, Moham- mad Javad Amiri, and Boon Thau Loo. 2025. Dag of dags: Order- fairness made practical.Proceedings of the ACM on Management of Data3, 6 (2025), 1–27

    work page 2025

  23. [23]

    Kaihua Qin, Liyi Zhou, and Arthur Gervais. 2022. Quantifying blockchain extractable value: How dark is the forest?. In2022 IEEE Symposium on Security and Privacy (SP)

    work page 2022

  24. [24]

    Fred B Schneider. 1990. Implementing fault-tolerant services using the state machine approach: A tutorial.Acm Computing Surveys (CSUR) (1990)

    work page 1990

  25. [25]

    Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. 2022. Bullshark: Dag bft protocols made practical. InProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2705–2718

    work page 2022

  26. [26]

    Qin Wang, Jiangshan Yu, Shiping Chen, and Yang Xiang. 2023. SoK: DAG-based blockchain systems.Comput. Surveys55, 12 (2023), 1–38

    work page 2023

  27. [27]

    Jie Xu, Cong Wang, and Xiaohua Jia. 2023. A survey of blockchain consensus protocols.Comput. Surveys(2023)

    work page 2023

  28. [28]

    Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT consensus with linearity and re- sponsiveness. InProceedings of the 2019 ACM symposium on principles of distributed computing

    work page 2019

  29. [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)

    work page 2024

  30. [30]

    Yunhao Zhang, Srinath Setty, Qi Chen, Lidong Zhou, and Lorenzo Alvisi. 2020. Byzantine ordered consensus without byzantine oli- garchy. In14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 633–649

    work page 2020

  31. [31]

    Liyi Zhou, Kaihua Qin, Christof Ferreira Torres, Duc V Le, and Arthur Gervais. 2021. High-frequency trading on decentralized on-chain exchanges. In2021 IEEE Symposium on Security and Privacy (SP). 13

    work page 2021