Clownfish: Scaling DAG-based BFT Consensus via Sparse Edges
Pith reviewed 2026-06-28 04:23 UTC · model grok-4.3
The pith
Clownfish attains quadratic communication complexity in DAG-based BFT by selectively sparsifying edges per vertex.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Clownfish is a partially synchronous DAG-based BFT protocol that lowers communication complexity by selectively reducing the number of edges each vertex includes to previous rounds. When combined with a communication-optimal consistent broadcast, this yields quadratic total communication per round, an improvement over prior DAG protocols. The protocol further reduces failure-case latency by refining the round advancement rule and permits multiple leaders per round while retaining the lower complexity.
What carries the argument
Sparse edges: the selective reduction of references to previous-round vertices in each DAG vertex, combined with a communication-optimal consistent broadcast to preserve correctness.
If this is right
- Total communication per round drops to quadratic order rather than the higher costs of linear-edge DAG protocols.
- Additional latency in failure cases decreases through the optimized round advancement rule.
- Multiple leaders per round become feasible without increasing communication complexity.
- Experimental runs show measurably better scalability than existing DAG-based protocols.
Where Pith is reading between the lines
- The sparse-edge pattern could be applied to other broadcast-centric consensus constructions to reduce their bandwidth use.
- In bandwidth-constrained wide-area settings the approach might allow larger participant sets before communication saturates.
- Pairing the design with alternative consistent-broadcast primitives would be a direct next measurement to quantify further gains.
Load-bearing premise
Selectively reducing the number of edges per DAG vertex still preserves the safety and liveness guarantees of the underlying BFT protocol under partial synchrony.
What would settle it
A concrete execution trace or simulation in which the reduced-edge DAG violates agreement or fails to terminate under partial synchrony with a bounded number of Byzantine faults.
Figures
read the original abstract
Directed Acyclic Graph (DAG) based BFT protocols have demonstrated the capability to achieve significantly high throughput in practice. Recent advancements focused on minimizing the good-case latency of these protocols, approaching the theoretical lower bound. However, the high communication complexity inherent in existing DAG-based protocols limits their scalability. This primarily arises because each vertex in the DAG must include a linear number of edges (references) to vertices from previous rounds. We present Clownfish, a partially synchronous DAG-based BFT protocol designed to address the scalability bottleneck. Clownfish achieves lower communication complexity by selectively reducing the number of edges in DAG vertices. When using a communication-optimal consistent broadcast, Clownfish attains quadratic total communication complexity per round, outperforming prior DAG-based protocols. Clownfish also reduces the additional latency in failure cases by optimizing the round advancement rule. Additionally, Clownfish supports multiple leaders per round to reduce average latency while maintaining its lower communication complexity. Our experimental evaluation demonstrates that Clownfish provides significantly better scalability than existing DAG-based protocols.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents Clownfish, a partially synchronous DAG-based BFT protocol that selectively reduces the number of edges per DAG vertex to lower communication complexity. It claims quadratic total communication per round when paired with a communication-optimal consistent broadcast, reduced failure-case latency via an optimized round-advancement rule, support for multiple leaders per round, and experimental results showing improved scalability over prior DAG-based protocols.
Significance. If the sparse-edge construction preserves the required DAG connectivity, ordering, and termination properties, the result would meaningfully improve the scalability of high-throughput DAG-based BFT protocols by moving from linear to sub-linear edges per vertex while retaining the latency benefits of recent DAG designs; the inclusion of an experimental evaluation is a positive step toward practical validation.
major comments (2)
- [Protocol description (edge-selection rule)] The central claim that selectively reducing edges still guarantees that every honest vertex eventually reaches all others, that round advancement terminates, and that honest nodes agree on the total order under partial synchrony is load-bearing for the quadratic-complexity result, yet the concrete edge-selection rule and the argument establishing these invariants are not visible; without an explicit mapping or theorem, the reduction cannot be verified.
- [Communication-complexity analysis] The abstract asserts quadratic total communication complexity per round, but the derivation that the combination of sparse edges plus the communication-optimal consistent broadcast actually yields O(n^{2}) rather than a higher bound (or a fitted quantity) is not shown; this step must be made explicit to support the outperforming-prior-protocols claim.
minor comments (1)
- [Abstract] The abstract would be clearer if it briefly named the edge-selection heuristic or the round-advancement optimization rather than describing them only at a high level.
Simulated Author's Rebuttal
We thank the referee for the constructive feedback. We address each major comment below and will revise the manuscript to incorporate the requested clarifications and explicit arguments.
read point-by-point responses
-
Referee: [Protocol description (edge-selection rule)] The central claim that selectively reducing edges still guarantees that every honest vertex eventually reaches all others, that round advancement terminates, and that honest nodes agree on the total order under partial synchrony is load-bearing for the quadratic-complexity result, yet the concrete edge-selection rule and the argument establishing these invariants are not visible; without an explicit mapping or theorem, the reduction cannot be verified.
Authors: We agree that the edge-selection rule and the formal invariants were not presented with sufficient explicitness in the submitted manuscript. In the revision we will add a precise description of the edge-selection rule (including the mapping from vertices to prior-round references) in the protocol section and state a theorem with proof sketch establishing eventual connectivity, round-advancement termination, and agreement under partial synchrony. This will make the quadratic-complexity claim directly verifiable. revision: yes
-
Referee: [Communication-complexity analysis] The abstract asserts quadratic total communication complexity per round, but the derivation that the combination of sparse edges plus the communication-optimal consistent broadcast actually yields O(n^{2}) rather than a higher bound (or a fitted quantity) is not shown; this step must be made explicit to support the outperforming-prior-protocols claim.
Authors: We will expand the communication-complexity section to include an explicit derivation showing that the sparse-edge construction combined with the communication-optimal consistent broadcast yields O(n²) total communication per round. This will be supported by a formal bound and comparison to prior linear-per-vertex DAG protocols. revision: yes
Circularity Check
No circularity in protocol claims or derivation
full rationale
The manuscript describes a new partially synchronous DAG-based BFT protocol that selectively reduces edges per vertex while relying on an external communication-optimal consistent broadcast primitive. No equations, fitted parameters renamed as predictions, self-citations that bear the central safety/liveness argument, or ansatzes smuggled via prior author work appear in the abstract or described claims. The quadratic communication result follows directly from the stated edge reduction plus the broadcast primitive's properties; these are independent of the present paper's construction and remain externally falsifiable. The derivation chain is therefore self-contained.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. 2021. Good-case latency of byzantine broadcast: A complete categorization. InProceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 331–341
2021
-
[2]
Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang. 2022. Balanced byzantine reliable broadcast with near-optimal communication and improved computation. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing. 399–417
2022
-
[3]
Salem Alqahtani and Murat Demirbas. 2021. Bottlenecks in blockchain consensus protocols. In2021 IEEE International Conference on Omni-Layer Intelligent Systems (COINS). IEEE, 1–8
2021
-
[4]
Michael Anoprenko, Andrei Tonkikh, Alexander Spiegelman, and Petr Kuznetsov
- [5]
-
[6]
Aptoscan. 2026. Aptoscan: Blocks Explorer. Retrieved Accessed: 2026-01-31 from https://aptoscan.com/blocks
2026
-
[7]
Balaji Arun, Zekun Li, Florian Suri-Payer, Sourav Das, and Alexander Spiegelman
-
[8]
In 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25)
Shoal++: High Throughput {DAG} {BFT} Can Be Fast and Robust!. In 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25). 813–826
-
[9]
Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. 2025. MYS- TICETI: Reaching the Latency Limits with Uncertified DAGs. InNetwork and Distributed Systems Security Symposium (NDSS)
2025
-
[10]
Leemon Baird. 2016. The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance.Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech. Rep 34 (2016), 9–11
2016
-
[11]
Sam Blackshear, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Xun Li, Mark Logan, Ashok Menon, Todd Nowacki, Alberto Sonnino, et al. 2024. Sui lutris: A blockchain combining broadcast and consen- sus. InProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2606–2620
2024
-
[12]
Dan Boneh, Ben Lynn, and Hovav Shacham. 2004. Short signatures from the Weil pairing.Journal of cryptology17, 4 (2004), 297–319
2004
-
[13]
Gabriel Bracha. 1987. Asynchronous Byzantine agreement protocols.Information and computation75, 2 (1987), 130–143
1987
-
[14]
Manuel Bravo, Gregory Chockler, and Alexey Gotsman. 2022. Making byzantine consensus live.Distributed Computing35, 6 (2022), 503–532
2022
- [15]
-
[16]
2011.Introduction to reliable and secure distributed programming
Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. 2011.Introduction to reliable and secure distributed programming. Springer Science & Business Media
2011
-
[17]
Miguel Castro, Barbara Liskov, et al. 1999. Practical byzantine fault tolerance. In OSDI (99, 1999). 173–186
1999
-
[18]
Benjamin Y Chan and Rafael Pass. 2023. Simplex consensus: A simple and fast consensus protocol. InTheory of Cryptography Conference. Springer, 452–479
2023
-
[19]
Shir Cohen, Rati Gelashvili, Lefteris Kokoris Kogias, Zekun Li, Dahlia Malkhi, Alberto Sonnino, and Alexander Spiegelman. 2022. Be aware of your leaders. In International Conference on Financial Cryptography and Data Security. Springer, 279–295
2022
-
[20]
Xiaohai Dai, Zhaonan Zhang, Jiang Xiao, Jingtao Yue, Xia Xie, and Hai Jin. 2023. GradedDAG: An asynchronous DAG-based BFT consensus with lower latency. In2023 42nd International Symposium on Reliable Distributed Systems (SRDS). IEEE, 107–117
2023
-
[21]
George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Narwhal and tusk: a dag-based mempool and efficient bft consensus. InProceedings of the Seventeenth European Conference on Computer Systems. 34–50
2022
-
[22]
Sourav Das, Zhuolun Xiang, and Ling Ren. 2021. Asynchronous data dissemina- tion and its applications. InProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2705–2721
2021
-
[23]
Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the presence of partial synchrony.Journal of the ACM (JACM)35, 2 (1988), 288–323
1988
-
[24]
Michael J Fischer, Nancy A Lynch, and Michael S Paterson. 1985. Impossibility of distributed consensus with one faulty process.Journal of the ACM (JACM)32, 2 (1985), 374–382
1985
-
[25]
Adam Gągol, Damian Leśniak, Damian Straszak, and Michał Świętek. 2019. Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies. 214–228
2019
-
[26]
Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang
-
[27]
InProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
Dumbo-ng: Fast asynchronous bft consensus with throughput-oblivious latency. InProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 1187–1201
2022
-
[28]
Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. 2022. Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. InInternational conference on financial cryptography and data security. Springer, 296–315
2022
-
[29]
Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. 2024. Autobahn: Seamless high speed BFT. InProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles. 1–23
2024
-
[30]
Neil Giridharan, Florian Suri-Payer, Matthew Ding, Heidi Howard, Ittai Abraham, and Natacha Crooks. 2023. Beegees: stayin’alive in chained bft. InProceedings of the 2023 ACM Symposium on Principles of Distributed Computing. 233–243
2023
-
[31]
2026.Performance Dashboard Overview
Google Cloud. 2026.Performance Dashboard Overview. Retrieved March 24, 2026 from https://docs.cloud.google.com/network-intelligence-center/docs/ performance-dashboard/concepts/overview
2026
-
[32]
Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019. SBFT: A scalable and decentralized trust infrastructure. In2019 49th Annual IEEE/IFIP international conference on dependable systems and networks (DSN). IEEE, 568–580
2019
-
[33]
Suyash Gupta, Jelle Hellings, and Mohammad Sadoghi. 2021. Rcc: Resilient concurrent consensus for high-throughput secure transaction processing. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 1392– 1403
2021
-
[34]
Mohammad M Jalalzai, Jianyu Niu, Chen Feng, and Fangyu Gai. 2023. Fast- hotstuff: A fast and robust bft protocol for blockchains.IEEE Transactions on Dependable and Secure Computing21, 4 (2023), 2478–2493
2023
-
[35]
Philipp Jovanovic, Lefteris Kokoris-Kogias, Bryan Kumara, Alberto Sonnino, Pasindu Tennage, and Igor Zablotchi. 2025. Mahi-mahi: Low-latency asynchro- nous bft dag-based consensus. In2025 IEEE 45th International Conference on Distributed Computing Systems (ICDCS). IEEE, 549–559
2025
-
[36]
Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman
-
[37]
InProceedings of the 2021 ACM Symposium on Principles of Distributed Computing
All you need is dag. InProceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 165–175
2021
-
[38]
Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. 2023. Cordial Miners: Fast and Efficient Consensus for Every Eventuality. In37th International Symposium on Distributed Computing (DISC 2023). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 26–1
2023
-
[39]
Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. 2007. Zyzzyva: speculative byzantine fault tolerance. InProceedings of twenty-first ACM SIGOPS symposium on Operating systems principles. 45–58
2007
-
[40]
Hanzheng Lyu, Shaokang Xie, Jianyu Niu, Chen Feng, Yinqian Zhang, and Ivan Beschastnikh. 2025. Ladon: High-Performance Multi-BFT Consensus via Dynamic Global Ordering. InProceedings of the Twentieth European Conference on Computer Systems. 226–242
2025
-
[41]
Dahlia Malkhi and Kartik Nayak. 2023. Hotstuff-2: Optimal two-phase responsive bft.Cryptology ePrint Archive(2023)
2023
-
[42]
Dahlia Malkhi, Chrysoula Stathakopoulou, and Maofan Yin. 2024. Bbca-chain: Low latency, high throughput bft consensus on a dag. InInternational Conference on Financial Cryptography and Data Security. Springer, 51–73
2024
-
[43]
Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. 2021. Cogsworth: Byzantine view synchronization. (2021)
2021
-
[44]
Nibesh Shrestha, Rohan Shrothrium, Aniket Kate, and Kartik Nayak. 2025. Sail- fish: Towards improving the latency of dag-based bft. In2025 IEEE Symposium on Security and Privacy (SP). IEEE, 1928–1946
2025
-
[45]
Nibesh Shrestha, Qianyu Yu, Aniket Kate, Giuliano Losa, Kartik Nayak, and Xuechao Wang. 2025. Optimistic, signature-free reliable broadcast and its ap- plications. InProceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security. 3780–3794
2025
-
[46]
Alexander Spiegelman, Balaji Arun, Rati Gelashvili, and Zekun Li. 2024. Shoal: Improving dag-bft latency and robustness. InInternational Conference on Finan- cial Cryptography and Data Security. Springer, 92–109
2024
-
[47]
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
2022
- [48]
- [49]
-
[50]
Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolić. 2022. State machine replication scalability made simple. InProceedings of the Seventeenth European Conference on Computer Systems. 17–33
2022
-
[51]
SuiScan. 2026. Suiscan: Transaction Blocks Explorer. Retrieved Accessed: 2026-01-31 from https://suiscan.xyz/mainnet/txs/tx-blocks
2026
-
[52]
Giorgos Tsimos, Anastasios Kichidis, Alberto Sonnino, and Lefteris Kokoris- Kogias. 2024. Hammerhead: Leader reputation for dynamic scheduling. In2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS). IEEE, 1377–1387
2024
-
[53]
Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, and David Tse
-
[54]
In19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22)
{DispersedLedger}:{High-Throughput} byzantine consensus on variable bandwidth networks. In19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22). 493–512. Clownfish : Scaling DAG-based BFT Consensus via Sparse Edges
-
[55]
Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abra- ham. 2019. HotStuff: BFT consensus with linearity and responsiveness. InProceed- ings of the 2019 ACM symposium on principles of distributed computing. 347–356
2019
-
[56]
Qianyu Yu, Giuliano Losa, Nibesh Shrestha, and Xuechao Wang. 2025. Angelfish: Leader, DAG, or Anywhere in Between.arXiv preprint arXiv:2509.15847(2025). A Additional Illustrations Figure 7 provides an illustration of the fast-vote mechanism in Section 4.1. The left side illustrates the liveness violation. Since replica 𝑝3 skips from round 𝑟 to round 𝑟+ 2a...
work page internal anchor Pith review Pith/arXiv arXiv 2025
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.