What is Byzantine Fault Tolerance?

Byzantine Fault Tolerance (BFT) is the means by which a distributed system, such as a blockchain network, screens out bad, outdated or incomplete information in order to maintain collective accuracy.

Overview

What it is: Byzantine Fault Tolerance is a protocol that addresses the challenge of validating information in a distributed network, this is also known as the Byzantine Generals Problem.

What it does: This method, when implemented in a computing network environment, provides a very high level of confidence that every node is acting on the same data at the same time.

Why it matters: Without a Byzantine Fault Tolerance solution blockchain technology couldn’t function, as decentralized consensus could never be reached in a trustless network. The more efficiently a company can achieve Byzantine Fault Tolerance, the more likely their system is going to be used and bought by other companies.

What to do about it: Companies exploring the use of Blockchain-related technologies should consider up-front how to address distributed data validation issues, using approaches such as BFT. Given how the application and data landscape is becoming increasingly fragmented due to trends such as microservices and IoT, these solutions and the thinking behind them may also have a broader application.

An Allegory: The Byzantine Generals Problem

This is an allegory where a Byzantine army has completely encircled an opponent’s city. Multiple generals, positioned at different locations around the city, must decide whether to attack or retreat based on the messages they receive from their commander. Somehow, each general must decide whether the messages they receive are valid. Is it actually from a loyal commander? Might the enemy have intercepted and altered the contents of the message in transit?

This problem is compounded because every general must act the same way at the same time or the entire army will face defeat.

The solution is having the generals relay the message they have received from their commander to every other general in the army. The generals compare all the messages they received from their peers. If at least two-thirds of the messages agree, the general will act. If there is not two-thirds agreement, the message fails and the generals default to a predetermined strategy.

When implemented in a computing network environment, this method delivers a very high level of confidence that every node is acting on the same data at the same time.

Potential Solutions

Early solutions include NASA and SRI International’s SIFT (Software Implemented Fault Tolerance). These required extremely redundant hardware and highly accurate software to detect Byzantine Faults and was limited to very specific use-cases in aircraft.

Later solutions, including Miguel Castro and Barbara Liskov’s “Practical Byzantine Fault Tolerance” (pBFT) algorithm, provide a high performing Byzantine machine state with sub-millisecond replicating abilities. pBFT operates by reaching consensus between nodes regarding the state of the information in question. Once consensus is reached that information is considered final since all honest nodes agree on the particular state as a result of the persistent communication between them. pBFT is the basis for modern blockchain technology solutions to the Byzantine Generals Problem.

Different solutions for incorporating Byzantine Fault Tolerance can be found in the blockchain technology ecosystem. These include Proof-of-Work (PoW) and Proof-of-Stake (PoS); other variants of the aforementioned protocols exist as well.

  • PoW: Users in a blockchain network, known as miners, compete to find a solution to a difficult asymmetrical cryptographic problem that can only be solved by guessing. Once the solution is found and verified, the miner creates a block and broadcasts it to the network to finalize all transactions within that block.
  • PoS: Users stake specified tokens in order to gain the opportunity to forge/validate a new block and be rewarded. The forger is chosen in a pseudo-random fashion, with the selection process bias being based on the size of each respective user’s stake. If the chosen forger acts maliciously in a provable fashion then they lose their stake and a new forger is chosen.

Technology Leadership and Impact

The creation of Byzantine Fault Tolerance protocols has had a massive impact on consensus algorithms. Companies invested in the success of blockchain technology are both the leaders and key researchers of this field. Current competitors leading the field are the teams behind major blockchain-based cryptocurrencies: Bitcoin Core, Ethereum, Litecoin Foundation, Ripple, and Bitcoin Cash. Other leaders in the field, with emphasis on research, include universities such as Stanford, Cornell, and the University of Guelph, Ontereo plus industry giants like IBM, Alibaba, and the People’s Bank of China.

Further Reading

“Practical Byzantine Fault Tolerance” Castro and Liskov http://pmg.csail.mit.edu/papers/osdi99.pdf