MiB: Asynchronous BFT With More Replicas

State-of-the-art asynchronous Byzantine fault-tolerant (BFT) protocols, such as HoneyBadgerBFT, BEAT, and Dumbo, have shown performance comparable to partially synchronous BFT protocols. This paper studies two practical directions in asynchronous BFT. First, while all these asynchronous BFT protocols assume optimal resilience with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$3f+1$</tex-math></inline-formula> replicas (where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f$</tex-math></inline-formula> is an upper bound on the number of Byzantine replicas), it is interesting to ask whether more efficient protocols are possible upon changing the resilience level. Second, these recent BFT protocols evaluate their performance under failure-free scenarios. It is unclear if these protocols indeed perform well during failures and attacks. This work first studies asynchronous BFT with suboptimal resilience using <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$5f+1$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$7f+1$</tex-math></inline-formula> replicas. We present MiB, a novel and efficient asynchronous BFT framework using new distributed system constructions as building blocks. MiB consists of two main BFT instances and five more variants. As another contribution, we systematically design experiments for asynchronous BFT protocols with failures and evaluate their performance in various failure scenarios. We report interesting findings, showing that asynchronous BFT performs consistently well during different failure scenarios. In particular, via a five-continent deployment on Amazon EC2 using 140 replicas, we show that the MiB instances have lower latency and much higher throughput than their asynchronous BFT counterparts.