Bingyong Guo (Institute of Software, Chinese Academy of Sciences), Yuan Lu (Institute of Software Chinese Academy of Sciences), Zhenliang Lu (The University of Sydney), Qiang Tang (The University of Sydney), jing xu (Institute of Software, Chinese Academy of Sciences), Zhenfeng Zhang (Institute of Software, Chinese Academy of Sciences)

Asynchronous BFT consensus can implement robust mission-critical decentralized services network without relying on any form of timing assumption. Starting from the work of HoneyBadgerBFT (CCS 2016), several studies tried to push asynchronous BFT towards practice. In a recent work of Dumbo (CCS 2020), they redesigned the protocol backbone and used one multi-valued validated Byzantine agreement (MVBA) to replace $n$ concurrent asynchronous binary agreement (ABA) protocols and dramatically improved the performance. Despite those efforts, asynchronous BFT protocols remain to be slow, and in particular, the latency is still quite large. There are two reasons contributing to the inferior performance: (1) the reliable broadcast (RBC) protocols still incur substantial costs; (2) the MVBA protocols are quite complicated and heavy, and all existing constructions need dozens of rounds and take the majority of the overall latency.

We first present a new construction of asynchronous BFT that replaces RBC instance with a cheaper broadcast component. It not only reduces the $mathcal{O}(n^3)$ message complexity incurred by $n$ RBCs to $mathcal{O}(n^2)$, but also saves up to 67% communications (in the presence of a fair network scheduler). Moreover, our technical core is a new MVBA protocol, Speeding MVBA, which is concretely more efficient than all existing MVBAs. It requires only 6 rounds in the best case and expected 12 rounds in the worst case (by contrast, several dozens of rounds in the MVBA from Cachin et al. [12] and the recent Dumbo-MVBA [33], and around 20 rounds in the MVBA from Abraham et al. [4]). Our new technique of the construction might be of independent interests.

We implemented Speeding Dumbo and did extensive tests among up to 150 EC2 t2.medium instances evenly allocated in 15 AWS regions across the globe. The experimental results show that Speeding Dumbo reduces the latency to about a half of Dumbo's, and also doubles the throughput of Dumbo, through all system scales from 4 nodes to 150 nodes. We also did tests to benchmark individual components such as the broadcasts and the MVBA protocols, which may be of interests for future improvements.

View More Papers

EqualNet: A Secure and Practical Defense for Long-term Network...

Jinwoo Kim (KAIST), Eduard Marin (Telefonica Research (Spain)), Mauro Conti (University of Padua), Seungwon Shin (KAIST)

Read More

Context-Sensitive and Directional Concurrency Fuzzing for Data-Race Detection

Zu-Ming Jiang (Tsinghua University), Jia-Ju Bai (Tsinghua University), Kangjie Lu (University of Minnesota), Shi-Min Hu (Tsinghua University)

Read More

What the Fork? Finding and Analyzing Malware in GitHub...

Alan Cao (New York University) and Brendan Dolan-Gavitt (New York University)

Read More

MobFuzz: Adaptive Multi-objective Optimization in Gray-box Fuzzing

Gen Zhang (National University of Defense Technology), Pengfei Wang (National University of Defense Technology), Tai Yue (National University of Defense Technology), Xiangdong Kong (National University of Defense Technology), Shan Huang (National University of Defense Technology), Xu Zhou (National University of Defense Technology), Kai Lu (National University of Defense Technology)

Read More