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

Vehicle Lateral Motion Stability Under Wheel Lockup Attacks

Alireza Mohammadi (University of Michigan-Dearborn) and Hafiz Malik (University of Michigan-Dearborn)

Read More

ScriptChecker: To Tame Third-party Script Execution With Task Capabilities

Wu Luo (Peking University), Xuhua Ding (Singapore Management University), Pengfei Wu (School of Computing, National University of Singapore), Xiaolei Zhang (Peking University), Qingni Shen (Peking University), Zhonghai Wu (Peking University)

Read More

Repttack: Exploiting Cloud Schedulers to Guide Co-Location Attacks

Chongzhou Fang (University of California, Davis), Han Wang (University of California, Davis), Najmeh Nazari (University of California, Davis), Behnam Omidi (George Mason University), Avesta Sasan (University of California, Davis), Khaled N. Khasawneh (George Mason University), Setareh Rafatirad (University of California, Davis), Houman Homayoun (University of California, Davis)

Read More