Tuna: Optimal-Resilience Asynchronous DAG-Based BFT with Lower Latency

Xiaohai Dai; Jian Zhang; Jiang Xiao; Rui Hao; Xia Xie; Junhong Liu; Hai Jin

doi:10.1016/j.eng.2026.06.017

Engineering ›› :202606017 DOI: 10.1016/j.eng.2026.06.017

research-article

Tuna: Optimal-Resilience Asynchronous DAG-Based BFT with Lower Latency

Author information +

History +

PDF (1836KB)

Abstract

Recent asynchronous Byzantine fault-tolerance (BFT) protocols have introduced the directed acyclic graph (DAG) topology to improve throughput but often encounter the drawback of elevated latency. For instance, the cutting-edge protocol GradedDAG has an average latency of at least 7.5 rounds—significantly higher than the three-round best-case latency of traditional non-DAG BFT protocols such as practical Byzantine fault-tolerance (PBFT). While some works have managed to reduce latency by sacrificing resilience or strengthening network assumptions, such compromises limit their general applicability. This leads to a fundamental question: Could an asynchronous DAG-based BFT protocol achieve optimal three-round latency without compromising resilience? We propose a novel DAG-based BFT protocol named “Tuna” to provide an affirmative answer to this question. Tuna operates in an asynchronous network and achieves optimal resilience. It functions in successive rounds, where every node disseminates its block in each round using the best-effort broadcast (BEB) mechanism—a single-round broadcast protocol. Under optimistic conditions, blocks from preselected leader slots can be committed directly in just three rounds of communication. Non-leader blocks are committed indirectly after four rounds, resulting in an average latency of 4 −k/n rounds, where n denotes the total number of nodes and k represents the number of leader slots in each round. When k = n, Tuna successfully achieves three-round latency. For cases where the leader block cannot be directly committed or the leader slot cannot be directly skipped, Tuna introduces the asynchronous binary agreement (ABA) protocol to make decisions. For liveness, Tuna employs the multi-valued validated Byzantine agreement (MVBA) protocol to ensure blocks are committed even when manipulated by a malicious adversary. We formally prove Tuna’s correctness and demonstrate its superior performance through various experimental evaluations.

Keywords

Byzantine consensus / Asynchronous consensus / Byzantine fault-tolerance / Directed acyclic graph

Cite this article

Download citation ▾

Xiaohai Dai, Jian Zhang, Jiang Xiao, Rui Hao, Xia Xie, Junhong Liu, Hai Jin. Tuna: Optimal-Resilience Asynchronous DAG-Based BFT with Lower Latency. Engineering 202606017 DOI:10.1016/j.eng.2026.06.017

登录浏览全文

4963

注册一个新账户忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	Enes V, Baquero C, Rezende TF, Gotsman A, Perrin M, Sutra P . State—machine replication for planet—scale systems. In: Proceedings of the Fifteenth European Conference on Computer Systems; 2020 Apr 27—30; Heraklion, Greece. New York City: Association for Computing Machinery; 2020. p. 1-15.

[2]	Stathakopoulou C, Pavlovic M, Vukolić M . State machine replication scalability made simple. In: Proceedings of the Seventeenth European Conference on Computer Systems; 2022 Apr 5—8; Rennes, France. New York City: Association for Computing Machinery; 2022. p. 17-33.

[3]	Zhang G, Pan F, Mao Y, Tijanic S, Dang’Ana M, Motepalli S, et al. Reaching consensus in the Byzantine empire: a comprehensive review of BFT consensus algorithms. ACM Comput Surv 2024; 56:1-41.

[4]	Keidar I, Kokoris—Kogias E, Naor O, Spiegelman A . All you need is DAG. In: Proceedings of the 40th ACM Symposium on Principles of Distributed Computing; 2021 Jul 26—30; online. New York City: Association for Computing Machinery; 2021. p. 165-75.

[5]	Spiegelman A, Giridharan N, Sonnino A, Kokoris—Kogias L . Bullshark: DAG BFT protocols made practical. In: Proceedings of the 29th ACM Conference on Computer and Communications Security; 2022 Nov 7—11; Los Angeles, CA, USA. New York City: Association for Computing Machinery; 2022. p. 2705—18.

[6]	Danezis G, Kokoris—Kogias L, Sonnino A, Spiegelman A . Narwhal and Tusk: a DAG—based mempool and efficient BFT consensus. In: Proceedings of the 17th European Conference on Computer Systems; 2022 Apr 5—8; Rennes, France. New York City: Association for Computing Machinery; 2022. p. 34-50.

[7]	Arun B, Li Z, Suri—Payer F, Das S, Spiegelman A . Shoal++: high throughput DAG BFT can be fast! 2024. arXiv:2405.20488.

[8]	Lamport L, Shostak R, Pease M . The Byzantine generals problem. ACM Trans Program Lang Syst 1982; 4(3):382-401.

[9]

Abraham I, Malkhi D, Nayak K, Ren L, Yin M . Sync hotstuff: simple and practical synchronous state machine replication. In: Proceedings of the 41st IEEE Symposium on Security and Privacy; 2020 May 18—21; San Francisco, CA, USA. New York City: Institute of Electrical and Electronics Engineers;2020. p. 106-18.

[10]	Castro M, Liskov B . Practical Byzantine fault tolerance. In: Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation; 1999 Oct 25—28; New Orleans, LU, USA. Berkeley: USENIX Association; 1999. p. 173-86.

[11]	Yin M, Malkhi D, Reiter MK, Gueta GG, Abraham I . Hotstuff: BFT consensus with linearity and responsiveness. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing; 2019 Jul 29—Aug 2; Toronto, ON, Canada. New York City: Association for Computing Machinery; 2019. p. 347—56.

[12]	Miller A, Xia Y, Croman K, Shi E, Song D . The honey badger of BFT protocols. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security; 2016 Oct 24—28; Vienna, Austria. New York City: Association for Computing Machinery;2016. p. 31-42.

[13]	Duan S, Reiter MK, Zhang H . Beat: asynchronous BFT made practical. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security; 2018 Oct 15—19; Toronto, ON, Canada. New York City: Association for Computing Machinery; 2018. p. 2028-41.

[14]	Guo B, Lu Z, Tang Q, Xu J, Zhang Z . Dumbo: faster asynchronous BFT protocols. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security; 2020 Nov 9—13; online. New York City: Association for Computing Machinery; 2020. p. 803—18.

[15]

Dai X, Zhang Z, Xiao J, Yue J, Xie X, Jin H . GradedDAG: an asynchronous DAG—based BFT consensus with lower latency. In: Proceedings of the 42nd International Symposium on Reliable Distributed Systems; 2023 Sep 26—29; Porto, Portugal. New York City: Institute of Electrical and Electronics Engineers; 2023. p. 107—17.

[16]	Zhou Y, Xiao J, Dai X, Jin H . Plaindag: a low—latency asynchronous DAG BFT protocol with best—effort broadcast. IEEE Trans Inf Forensics Secur 2025; 20:9792-805.

[17]	Babel K, Chursin A, Danezis G, Kokoris—Kogias L, Sonnino A . Mysticeti: low—latency dag consensus with fast commit path. 2023. arXiv:2310.14821.

[18]	Cachin C, Guerraoui R, Rodrigues L . Introduction to reliable and secure distributed programming. Berlin: Springer Science & Business Media; 2011.

[19]	Cachin C, Shoup V . Random oracles in Constantinople: practical asynchronous Byzantine agreement using. In: Proceedings of the 19th ACM Symposium on Principles of Distributed Computing; 2000 Jul 23—26; Portland, OR, USA. New York City: Association for Computing Machinery; 2000. p. 1-26.

[20]	Friedman R, Mostefaoui A, Raynal M . Simple and efficient oracle—based consensus protocols for asynchronous Byzantine systems. IEEE Trans Depend Secure Comput 2005; 2(1):46-56.

[21]	Mostéfaoui A, Moumen H, Raynal M . Signature—free asynchronous byzantine consensus with t < n/3 and O(n²) messages. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing; 2014 Jul 15—18; Paris, France. New York City: Association for Computing Machinery; 2014. p. 2-9.

[22]	Cachin C, Kursawe K, Petzold F, Shoup V . Secure and efficient asynchronous broadcast protocols. In: Proceedings of the 2001 Annual International Cryptology Conference; 2001 Aug 19—23; Santa Barbara, CA, USA. Berlin: Springer; 2001. p. 524—41.

[23]	Abraham I, Malkhi D, Spiegelman A . Asymptotically optimal validated asynchronous byzantine agreement. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing; 2019 Jul 29—Aug 2; Toronto, ON, Canada. New York City: Association for Computing Machinery; 2019. p. 337-46.

[24]	Lu Y, Lu Z, Tang Q, Wang G . Dumbo—MVBA: optimal multivalued validated asynchronous byzantine agreement, revisited. In: Proceedings of the 39th ACM Symposium on Principles of Distributed Computing; 2020 Aug 3—7; online. New York City: Association for Computing Machinery; 2020. p. 129—38.

[25]	Guo B, Lu Y, Lu Z, Tang Q, Xu J, Zhang Z . Speeding Dumbo: pushing asynchronous BFT closer to practice. 2022. cryptoeprint:2022/027.

[26]	Jin H, Xiao J . Towards trustworthy blockchain systems in the era of “Internet of value”: development, challenges, and future trends. Sci China Inf Sci 2022; 65(5):153101.

[27]	Spiegelman A, Arun B, Gelashvili R, Li Z . Shoal: improving DAG—BFT latency and robustness. 2023. arXiv:2306.03058.

[28]	Malkhi D, Stathakopoulou C, Yin M . BBCA—CHAIN: one—message, low latency BFT consensus on a DAG. 2023. arXiv:2310.06335.

[29]	Shrestha N, Shrothrium R, Kate A, Nayak K . Sailfish: towards improving latency of DAG—based BFT. 2024. cryptoeprint:2024/472.

[30]	Dolev D, Strong HR . Authenticated algorithms for Byzantine agreement. SIAM J Comput 1983; 12(4):656-66.

[31]

Abraham I, Devadas S, Dolev D, Nayak K, Ren L . Synchronous Byzantine agreement with expected o(1) rounds, expected O(n²) communication, and optimal resilience. In: Proceedings of the 23rd International Conference on Financial Cryptography and Data Security; 2019 Feb 18—22; Frigate Bay, The Federation of Kitts and Nevis. Cham: Springer Cham; 2019. p. 320-34.

[32]	Kotla R, Alvisi L, Dahlin M, Clement A, Wong E . Zyzzyva: speculative Byzantine fault tolerance. In: Proceedings of 21st ACM SIGOPS Symposium on Operating Systems Principles; 2007 Oct 14—17; Washington, DC, USA. New York City: Association for Computing Machinery; 2007. p. 45-58.

[33]

Gueta GG, Abraham I, Grossman S, Malkhi D, Pinkas B, Reiter M, et al. SBFT: a scalable and decentralized trust infrastructure. In: Proceedings of the 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks; 2019 Jun 24—27; Portland, OR, USA. New York City: Institute of Electrical and Electronics Engineers; 2019. p. 568-80.

[34]	Chan BY, Shi E . Streamlet: textbook streamlined blockchains. In: Proceedings of the 2nd ACM Conference on Advances in Financial Technologies; 2020 Oct 21—23; online. New York City: Association for Computing Machinery; 2020. p. 1-11.

[35]	Behl J, Distler T, Kapitza R . Hybrids on steroids: SGX—based high performance BFT. In: Proceedings of the 12th European Conference on Computer Systems; 2017 Apr 23—26; Belgrade, Serbia. New York City: Association for Computing Machinery; 2017. p. 227-37.

[36]	Kapitza R, Behl J, Cachin C, Distler T, Kuhnle S, Mohammadi SV, et al. CheapBFT: resource—efficient Byzantine fault tolerance. In: Proceedings of the 7th European Conference on Computer Systems; 2012 Apr 10—13; Bern, Switzerland. New York City: Association for Computing Machinery;2012. p. 295-308.

[37]	Wang R, Ma F, Tang S, Zhang H, He J, Su Z, et al. Parallel Byzantine fault tolerance consensus based on trusted execution environments. Peer—to—Peer Netw Appl 2025; 18(1):31.

[38]

Gao Y, Lu Y, Lu Z, Tang Q, Xu J, Zhang Z . Dumbo—NG: fast asynchronous BFT consensus with throughput—oblivious latency. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security; 2022 Nov 7—11; Los Angeles, CA, USA. New York City: Association for Computing Machinery; 2022. p. 1187-201.

[39]

Gelashvili R, Kokoris—Kogias L, Sonnino A, Spiegelman A, Xiang Z . Jolteon and Ditto: network—adaptive efficient consensus with asynchronous fallback. In: Proceedings of the 2022 International Conference on Financial Cryptography and Data Security; 2022 May 2—6; Grenoble, France. Berlin: Springer; 2022. p. 296-315.

[40]	Lu Y, Lu Z, Tang Q . Bolt—Dumbo transformer: asynchronous consensus as fast as the pipelined BFT. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security; 2022 Nov 7—11; Los Angeles, CA, USA. New York City: Association for Computing Machinery; 2022. p. 2159-73.

[41]

Blum E, Katz J, Loss J, Nayak K, Ochsenreither S . Abraxas: throughput—efficient hybrid asynchronous consensus. In: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security; 2023 Nov 26—30; Copenhagen, Denmark. New York City: Association for Computing Machinery; 2023. p. 519-33.

[42]

Dai X, Zhang B, Jin H, Ren L . ParBFT: faster asynchronous BFT consensus with a parallel optimistic path. In: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security; 2023 Nov 26—30; Copenhagen, Denmark. New York City: Association for Computing Machinery; 2023. p. 504-18.