Practical Asynchronous BFT from Local Coinst

Asynchronous Byzantine fault-tolerant (BFT) protocols assuming no timing assumptions are inherently more robust than their partially synchronous counterparts, but typically have much weaker security guarantees. We design new and efficient asynchronous BFT protocols matching all security guarantees of partially synchronous protocols. To achieve the goal, we have developed the local coin based BFT approach-one long deemed as being inefficient-and designed more efficient asynchronous binary agreement (ABA) protocols and their reproposable ABA (RABA) versions from local coins. Notably, our techniques on ABA and RABA allow us to build more efficient ABA protocols from common coins. We implemented four BFT protocols in a new Golang library, including BEAT, two WaterBear protocols, and FlatWorm. The WaterBear protocols use the conventional BFT workflow, while FlatWorm leverages the framework separating message transmission from consensus and significantly improves the system throughput. Via extensive evaluation, we show that our WaterBear protocols and FlatWorm are efficient under both failure-free and failure scenarios. Notably, WaterBear-QS consistently outperforms BEAT across all metrics and FlatWorm significantly outpaces WaterBear-QS. For example, with 16 replicas, FlatWorm achieves a throughput of 213.04ktx/sec - 5.63× that of BEAT and 3.43× that of WaterBear-QS.