Paper 2022/020

PACE: Fully Parallelizable BFT from Reproposable Byzantine Agreement

Sisi Duan and Haibin Zhang

Abstract

Reaching consensus is the single most crucial problem in fault-tolerant distributed computing. This paper studies asynchronous consensus with Byzantine failures commonly known as asynchronous binary Byzantine agreement (ABA). ABA is a key component as well as a bottleneck for (almost) all known asynchronous Byzantine fault-tolerant (BFT) protocols and asynchronous multi-party computation (MPC) with guaranteed output. This paper addresses two significant problems in ABA: we propose the first common-coin based ABA with 2 steps only in a round and the first practical solution on running ABA in a fully parallelizable manner. We first present Pillar, a new round-based ABA protocol using common coins, having 2 steps in a round. Pillar can be directly used to improve all practical asynchronous BFT protocols implemented and MPC protocols achieving guaranteed output. To demonstrate the performance of Pillar, we use it in the BEAT protocol based on the classic framework of Ben-Or, Kemler, and Rabin and HoneyBadgerBFT, and implement a new BFT protocol, called ACE, providing up to 2x the throughput of BEAT. We go on to suggest reproposable ABA (RABA), a generalized ABA primitive that allows a replica to change its mind and vote twice. In contrast to conventional ABA, RABA requires the protocol to be biased towards 1, but does not require external validity (via, e.g., expensive threshold signatures). We use Pillar to build Pisa, a signature-free RABA protocol that is as efficient as Pillar. We also show how to turn some other ABA protocols (including the one by Cachin, Kursawe, and Shoup) to RABA. We then propose a novel asynchronous BFT framework built on reliable broadcast (RBC) and RABA. This leads to the first fully parallelizable asynchronous BFT protocol, allowing all ABA instances to run in a strictly concurrent manner. Our concrete instantiation, called PACE, consistently and significantly outperforms existing asynchronous BFT protocols in terms of all metrics, having much fewer steps than all asynchronous BFT implemented for all practically large systems. PACE provides 6x the throughput of BEAT when there are 91 replicas. Such a solution can be directly used as a solution to run ABA in parallel, a procedure needed not just in BFT but in interactive consistency and MPC with guaranteed output. Our result, therefore, identifies RABA as a first-class primitive in distributed computing. Also, the PACE framework lays the foundation on information-theoretic asynchronous BFT and asynchronous BFT without public-key cryptography.