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.