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
BibTex
@INPROCEEDINGS{avarikioti2023fnf-bft,
isbn = {978-3-031-32732-2},
abbrev_source_title = {LNCS},
doi = {10.1007/978-3-031-32733-9_9},
year = {2023},
booktitle = {Structural Information and Communication Complexity},
volume = {13892},
type = {Conference Paper},
editor = {Rajsbaum, Sergio and Balliu, Alkida and Daymude, Joshua J. and Olivetti, Dennis},
journal = {Lecture Notes in Computer Science},
author = {Avarikioti, Zeta and Heimbach, Lioba and Schmid, Roland and Vanbever, Laurent and Wattenhofer, Roger and Wintermeyer, Patrick},
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.},
issn = {0302-9743},
keywords = {BFT; SMR; Parallel leaders; Byzantine-resilient performance},
language = {en},
address = {Cham},
publisher = {Springer},
title = {FnF-BFT: A BFT protocol with provable performance under attack},
PAGES = {165 - 198},
Note = {30th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2023); Conference Location: Alcalá de Henares, Spain; Conference Date: June 6-9, 2023; Conference lecture on June 8, 2023.}
}Research Collection: 20.500.11850/612866