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

Xiaohai Dai; Zhaonan Zhang; Jiang Xiao; Jingtao Yue; Xia Xie; Hai Jin

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

Abstract

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

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Minor revision. Proceedings of the 42nd International Symposium on Reliable Distributed Systems (SRDS 2023)
Keywords: Consensus BFT Asynchronous DAG
Contact author(s): xhdai @ hust edu cn
History: 2024-04-05: revised; 2024-02-01: received; See all versions
Short URL: https://ia.cr/2024/142
License: CC BY

BibTeX

@misc{cryptoeprint:2024/142,
      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},
      url = {https://eprint.iacr.org/2024/142}
}