FnF-BFT: A BFT Protocol with Provable Performance Under Attack

Abstract

We introduce FnF-BFT, the first partially synchronous BFT protocol with performance guarantees under truly byzantine attacks during stable networking conditions. At its core, FnF-BFT parallelizes the execution of requests by allowing all replicas to act as leaders independently. Leader parallelization distributes the load over all replicas. Consequently, FnF-BFT fully utilizes all correct replicas’ processing power and increases throughput by overcoming the single-leader bottleneck. We prove lower bounds on FnF-BFT ’s efficiency and performance in synchrony: the amortized communication complexity is linear in the number of replicas and thus competitive with state-of-the-art protocols; FnF-BFT ’s amortized throughput with less than $$\frac{1}{3}$$ byzantine replicas is at least $$\frac{16}{27}$$ th of its best-case throughput. We also provide a proof-of-concept implementation and preliminary evaluation of FnF-BFT.