Cryptology ePrint Archive: Report 2022/020

PACE: Fully Parallelizable BFT from Reproposable Byzantine Agreement

Sisi Duan and Haibin Zhang

Abstract: The classic asynchronous Byzantine fault tolerance (BFT) framework of Ben-Or, Kemler, and Rabin (BKR) and its descendants rely on reliable broadcast (RBC) and asynchronous binary agreement (ABA). However, BKR does not allow all ABA instances to run in parallel, a well-known performance bottleneck. We propose PACE, a generic framework that removes the bottleneck, allowing fully parallelizable ABA instances. PACE is built on RBC and reproposable ABA (RABA). Different from the conventional ABA, RABA allows a replica to change its mind and vote twice. We show how to efficiently build RABA protocols from existing ABA protocols and a new ABA protocol that we introduce.

We implement six new BFT protocols: three in the BKR framework, and three in the PACE framework. Via a deployment using 91 replicas on Amazon EC2 across five continents, we show that all PACE instantiations, in both failure-free and failure scenarios, significantly outperform their BKR counterparts, and prior BFT protocols such as BEAT and Dumbo, in terms of latency, throughput, latency vs. throughput, and scalability.

Category / Keywords: asynchronous BFT, binary consensus, blockchain, fault tolerance

Date: received 6 Jan 2022, last revised 23 Apr 2022

Contact author: duansisi at mail tsinghua edu cn, haibin at bit edu cn

Available format(s): PDF | BibTeX Citation

Version: 20220423:140733 (All versions of this report)

Short URL: ia.cr/2022/020