Paper 2024/142

GradedDAG: An Asynchronous DAG-based BFT Consensus with Lower Latency

Xiaohai Dai, Huazhong University of Science and Technology
Zhaonan Zhang, Huazhong University of Science and Technology
Jiang Xiao, Huazhong University of Science and Technology
Jingtao Yue, Huazhong University of Science and Technology
Xia Xie, Hainan University
Hai Jin, Huazhong University of Science and Technology

To enable parallel processing, the Directed Acyclic Graph (DAG) structure is introduced to the design of asynchronous Byzantine Fault Tolerant (BFT) consensus protocols, known as DAG-based BFT. Existing DAG-based BFT protocols operate in successive waves, with each wave containing three or four Reliable Broadcast (RBC) rounds to broadcast data, resulting in high latency due to the three communication steps required in each RBC. For instance, Tusk, a state-of-the-art DAG-based BFT protocol, has a good-case latency of 7 communication steps and an expected worst latency of 21 communication steps. To reduce latency, we propose GradedDAG, a new DAG-based BFT consensus protocol based on our adapted RBC called Graded RBC (GRBC) and the Consistent Broadcast (CBC), with each wave consisting of only one GRBC round and one CBC round. Through GRBC, a replica can deliver data with a grade of 1 or 2, and a non-faulty replica delivering the data with grade 2 can ensure that more than 2/3 of replicas have delivered the same data. Meanwhile, through CBC, data delivered by different non-faulty replicas must be identical. In each wave, a block in the GRBC round will be elected as the leader. If a leader block has been delivered with grade 2, it and all its ancestor blocks can be committed. GradedDAG offers a good-case latency of 4 communication steps and an expected worst latency of 7.5 communication steps, significantly lower than the state-of-theart. Experimental results demonstrate GradedDAG’s feasibility and efficiency.

Note: Appendix are added

Available format(s)
Publication info
Published elsewhere. Minor revision. Proceedings of the 42nd International Symposium on Reliable Distributed Systems (SRDS 2023)
Contact author(s)
xhdai @ hust edu cn
2024-04-05: revised
2024-02-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiaohai Dai and Zhaonan Zhang and Jiang Xiao and Jingtao Yue and Xia Xie and Hai Jin},
      title = {{GradedDAG}: An Asynchronous {DAG}-based {BFT} Consensus with Lower Latency},
      howpublished = {Cryptology ePrint Archive, Paper 2024/142},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.