Paper 2022/021

WaterBear: Information-Theoretic Asynchronous BFT Made Practical

Sisi Duan and Haibin Zhang and Boxin Zhao

Abstract

This paper refutes the conventional wisdom that information-theoretic BFT is impractical. We design and implement WaterBear, the first practical information-theoretic asynchronous Byzantine fault-tolerant (BFT) protocol. We also present a more efficient, quantum-secure asynchronous BFT protocol, WaterBear-QS, which, compared to WaterBear, additionally uses a collision-resistant hash function. We show that WaterBear and WaterBear-QS are efficient under both failure-free and failure scenarios, achieving comparable performance to the state-of-the-art asynchronous BFT protocols. In particular, our failure case evaluation is thus far the most comprehensive evaluation for asynchronous BFT settings.