Byzantine Fault Tolerance
Byzantine fault tolerance (BFT) is the property of a distributed computer system that allows it to continue operating correctly and reaching consensus even when some fraction of its participants behave arbitrarily — including sending conflicting, malicious, or nonsensical messages — named after the Byzantine Generals Problem in distributed computing theory.
The Byzantine Generals Problem, formalized by Lamport, Shostak, and Pease in a 1982 paper, describes the challenge facing a group of generals who must coordinate an attack but can only communicate by messenger, knowing that some generals may be traitors who send deliberately misleading orders. The mathematical question is: what fraction of traitors can be tolerated while still guaranteeing that loyal generals reach the same decision?
The theoretical answer is that a system can tolerate fewer than one-third of its participants being Byzantine (arbitrarily faulty or malicious). If more than one-third of participants are adversarial, it is provably impossible to guarantee agreement in an asynchronous network. This bound — often expressed as the two-thirds honest majority requirement — underpins virtually every BFT consensus algorithm used in blockchain systems.
Practical Byzantine Fault Tolerance (PBFT), designed by Castro and Liskov in 1999, was the first efficient BFT algorithm suitable for real-world distributed systems. It requires O(n^2) message complexity per round, making it impractical for very large validator sets but highly suitable for smaller permissioned networks. Tendermint (now CometBFT) adapted PBFT for blockchain use and powers the Cosmos ecosystem. HotStuff, used by Diem (Facebook's blockchain project) and adapted into many modern consensus designs, reduced the message complexity to O(n) using a linear pipeline.
Ethereum's proof of stake consensus (Gasper, combining Casper FFG and LMD-GHOST) achieves probabilistic BFT-style finality with a much larger validator set — currently over 800,000 validators — through a voting aggregation scheme that avoids the full O(n^2) message overhead of classical BFT while still providing strong finality guarantees within two epochs (approximately 12.8 minutes).
BFT is relevant beyond consensus: it describes the resilience of any distributed system component, including cross-chain oracle networks, decentralized price feeds, and threshold signature schemes. A BFT oracle network can provide tamper-resistant price data as long as fewer than one-third of its nodes are compromised.