- The Byzantine Generals’ Problem sounds like it belongs in the history books rather than in cryptocurrency whitepapers
- However, the principle behind it forms the cornerstone of blockchain technology
- What is the Byzantine Generals’ Problem, and how does it apply to crypto?
The Byzantine Generals’ Problem is something you’ll find in a number of cryptocurrency papers going back to Bitcoin, but its name alone offers nothing with regard to what it actually is or how it has any relation to the sector. In this piece we go through the why and wherefores of the Byzantine Generals’ Problem and explain how it matters and why crypto can help with it.
Not a Problem
The Byzantine Generals’ Problem is not based on an event from history, but is in fact a theoretical puzzle first posed by Leslie Lamport, Robert Shostak and Marshall Pease in ACM Transactions on Programming Languages and Systems, a scientific journal on programming languages published by the Association for Computing Machinery in 1982.
The puzzle in question is this – how can you ensure that multiple entities in different locations are able to agree on the same course of action before taking it? The question is one of consensus, which is something that blockchains know all about.
Obtaining General Agreement
Imagine a Byzantine era (395–1453) army that has an entire city encircled with its numerous divisions. The generals at the heads of these divisions must agree on a battle plan, with consensus being critical – they must agree on the next move and not deviate. However, there may be bad actors within the ranks, or the messages between the generals may get mislaid or mistranslated. This could lead to disparate action being taken, leading to potential disaster for the army.
Blockchains, of course, rely on consensus from multiple parties, so how can they protect against insider attacks, accidents, or mistakes? Lamport et al. suggest that the Byzantine army could withstand up to 1/3 of the generals being ‘traitors’ and still reach a consensus, meaning that as long as at least 2/3 of them are honest then consensus can be reached and the ‘right’ plan can be carried out.
In 1999, a paper was produced by Miguel Castro and Barbara Liskov that showed how decentralized systems could follow this principle through a Byzantine Fault Tolerance (BFT) algorithm. Systems that implemented a BFT algorithm could still function even when up to 1/3 of nodes were compromised in some way, Castro and Liskov noted, but would need some method of dissuading bad actors from attempting a coup in the first place.
Bitcoin put this BFT algorithm into practice in 2008 with its Proof-of-Work (PoW) consensus mechanism. This mechanism requires validators to put in time, effort, and money into confirming transactions, offering a practical barrier to those who might wish to undermine group consensus. While far from perfect, PoW nevertheless laid the foundations for the concept of practical interpretation of the BFT algorithm (pBFT) within blockchains.
Byzantine Generals’ Problem Will Always Exist
A number of consensus mechanisms have come and gone since Bitcoin’s emergence in 2008, with a more recent one, Icon’s LFT2, doing away with much of the communication required between the nodes and speeding it up hugely as a result without compromising on security. This is like giving our Byzantine generals smartphones with which to communicate, while Bitcoin restricts them to carrier pigeons.
No system can ever be 100% resilient against the Byzantine Generals Problem, but with the relatively few successful attacks on blockchains in the 11 years since Bitcoin was created, it’s pretty clear that the Byzantine Fault Tolerance approach is working pretty well more than 20 years on.