How various protocols tackle the Byzantine Generals Problem

What is the Byzantine Generals Problem?

The Byzantine Generals Problem is a thought experiment applied to electronic distributed networks. It seeks a way to synchronise independent participants.

The set-up:

«Armies of several generals (network nodes) are besieging a city. They can communicate only by sending messengers (transactions). The key task is to agree on a common plan to attack or retreat (consensus). Some generals are traitors and will try in every way to thwart the agreement».

The first academic paper on the topic in 1982 was published by Leslie Lamport, Robert Shostak and Marshall Pease. The problem applies only to distributed systems without a central node trusted by the rest of the network. In the real world such a node could be, for example, a country’s central bank, which issues fiat currency and allocates it to commercial banks’ accounts.

Because cryptocurrencies are built on decentralised principles without a single governing authority, solving this problem became foundational to the design of blockchain-based networks.

How did Satoshi Nakamoto solve the Byzantine Generals Problem?

In 2008 the creator of Bitcoin, Satoshi Nakamoto, proposed a practical solution to the Byzantine Generals Problem. He devised the Bitcoin protocol and implemented the Proof-of-Work (PoW) consensus algorithm. This removed the need for trust by setting clear rules for achieving consensus (agreement) among Bitcoin’s distributed nodes (the generals).

The PoW algorithm allows each node to verify that others have done the work correctly and are abiding by the agreement. This is achieved through the blockchain, cryptography and economic incentives for miners, which protect consensus from malicious behaviour.

If a node decides to perform the “wrong work”, other participants will see it and will not allow the unwanted activity to proceed.

Which consensus algorithms do cryptocurrencies use?

Beyond Proof-of-Work, the most common and reliable solutions to the Byzantine Generals Problem are Proof of Stake (PoS) and Byzantine Fault Tolerance (BFT).

Proof of Stake (PoS) is the most popular version in the crypto market. Instead of miners, as in PoW, control of the network is given to holders of the native coin. The main advantage is far lower energy consumption compared with PoW.

Byzantine Fault Tolerance (BFT) is designed to scale PoS blockchain networks. Unlike the previous approach, BFT relies on collective decision-making in reaching consensus. Nodes send transactions to one another until two-thirds of all nodes arrive at the same result.

There are many modifications and hybrid algorithms. One is Tendermint, which underpins the Cosmos blockchain, where Delegated Proof-of-Stake (DPoS) and BFT are used together. For example, Solana uses DPoS and a BFT implementation—Practical Byzantine Fault Tolerance (pBFT).

Beyond these algorithms, cryptocurrencies use more than a dozen other consensus variants. Some include:

• Leased Proof of Stake (LPoS) — another PoS variant in which users can participate in block generation by leasing tokens to “main” nodes. This consensus is used in the Waves blockchain;
• Proof of Elapsed Time (PoET) — a modification of PoW that uses CPU resources. It builds on a fair-lottery algorithm in which a validator is chosen at random in proportion to resources committed. Used in Hyperledger solutions;
• Delegated Byzantine Fault Tolerance (DBFT) — a modification of two algorithms at once: PBFT and DPoS. This consensus variant is used in the NEO blockchain;
• Directed Acyclic Graphs (DAG) — not a consensus mechanism but an alternative to blockchains. A DAG consists of circles and lines rather than blocks and looks like a graph. Consensus algorithms in such networks can be the familiar ones, but the way information is recorded is fundamentally different. One such hybrid is Hashgraph;
• Proof of Activity (POA) — a hybrid mechanism based on PoW and PoS. The best-known example is Decred;
• Proof of Importance (Pol) — built on the principles of a ratings system. The higher a validator’s notional rating, the greater the chance of finding blocks. This type of consensus was popularised by the NEM network;
• Proof of Capacity (PoC) — uses disk space instead of computing resources. The consensus is used in the Chia and BitTorrent networks;
• Proof-of-Personhood (PoP) — proof of personhood. It uses mechanisms to confirm “humanness”, ensuring that each participant receives an equal vote and share of rewards. The flagship is the Worldcoin cryptocurrency.