Cryptology ePrint Archive: Report 2020/841

Dumbo: Faster Asynchronous BFT Protocols

Bingyong Guo and Zhenliang Lu and Qiang Tang and Jing Xu and Zhenfeng Zhang

Abstract: HoneyBadgerBFT, proposed by Miller et al. [32] as the first practical asynchronous atomic broadcast protocol, demonstrated impressive performance. The core of HoneyBadgerBFT (HB-BFT) is to achieve batching consensus using asynchronous common subset protocol (ACS) of Ben-Or et al., constituted with $n$ reliable broadcast protocol (RBC) to have each node propose its input, followed by $n$ asynchronous binary agreement protocol (ABA) to make a decision for each proposed value ($n$ is the total number of nodes).

In this paper, we propose two new atomic broadcast protocols (called Dumbo1, Dumbo2) both of which have asymptotically and practically better efficiency. In particular, the ACS of Dumbo1 only runs a small $k$ (independent of $n$) instances of ABA, while that of Dumbo2 further reduces it to constant! At the core of our techniques are two major observations: (1) reducing the number of ABA instances significantly improves efficiency; and (2) using multi-valued validated Byzantine agreement (MVBA) which was considered sub-optimal for ACS in [32] in a more careful way could actually lead to a much more efficient ACS.

We implement both Dumbo1, Dumbo2 and deploy them as well as HB-BFT on 100 Amazon EC2 t2.medium instances uniformly distributed throughout 10 different regions across the globe, and run extensive experiments in the same environments. The experimental results show that our protocols achieve multi-fold improvements over HoneyBadgerBFT on both latency and throughput, especially when the system scale becomes moderately large.

Category / Keywords: cryptographic protocols / Dumbo, atomic broadcast, asynchronous, protocol

Original Publication (with minor differences): will appear at ACM CCS 2020

Date: received 7 Jul 2020, last revised 12 Jul 2020

Contact author: guobingyong at tca iscas ac cn,zl425@njit edu,qiang@njit edu,xujing@tca iscas ac cn,zfzhang@tca iscas ac cn

Available format(s): PDF | BibTeX Citation

Version: 20200712:144344 (All versions of this report)

Short URL: ia.cr/2020/841


[ Cryptology ePrint archive ]