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.

People

Dr. Roland Schmid

PhD student

2020—2025

Prof. Laurent Vanbever

Group Leader

BibTex

@inproceedings{avarikioti2023fnf-bft,
  author    = {Avarikioti, Zeta and Heimbach, Lioba and Schmid, Roland and Vanbever, Laurent and Wattenhofer, Roger and Wintermeyer, Patrick},
  title     = {{FnF-BFT: A BFT protocol with provable performance under attack}},
  booktitle = {Lecture Notes in Computer Science},
  volume    = 13892,
  address   = {Alcal{\'{a}} de Henares, Spain},
  year      = 2023,
  month     = jun,
  publisher = {Springer},
  doi       = {10.1007/978-3-031-32733-9_9},
  url       = {https://doi.org/10.1007/978-3-031-32733-9_9}
}

Research Collection: 20.500.11850/612866