The Origins of Consensus
In the first part of this series, we looked at how Satoshi Nakamoto published the blockchain data-structure and the way to ensure block integrity was invented 17 years before Bitcoin’s visionary paper in 2008. In a similar vein, consensus protocols have been around for much longer than what is generally thought of as a blockchain technology. It is fair to say that even the most modern blockchain systems employ relatively old algorithms, providing new use cases and renewed interest in a classic branch of distributed computing.
The role of a consensus protocol is to get some participants in a network with equal status to agree on the acceptance and order of messages in the system. This is a classic problem in computer science and has been worked on for a long time.
It is difficult to put an exact date on the first consensus research, but in 1982 Leslie Lamport, Robert Shostak, and Marshall Pease published a research paper called “The Byzantine Generals Problem,” which laid down the groundwork for modern blockchain consensus.
The paper uses a metaphor of generals in the Byzantine army that need to agree on an attack plan, but do not trust each other. The metaphor models a situation in a computer network in which participants need to reach consensus, but individual nodes may misbehave. In fact, the term Byzantine fault-tolerance has come to describe a failure model in which nodes are assumed to fail in any conceivable way, including malicious behavior. The paper also describes several solutions to the problem, including a solution making heavy use of public-key cryptography.
However, it was not until 1999 that a paper written by Miguel Castro and Barbara Liskov described the “Practical Byzantine Fault Tolerance” (PBFT) algorithm. PBFT is an efficient consensus algorithm that solves the Byzantine Generals Problem using a state machine approach, which provides high transaction throughput.
Today, PBFT is used in many state-of-the-art blockchain platforms, in particular in enterprise blockchains and high-performance blockchains that focus on scalability by using a small set of delegate validators.
While Bitcoin uses a different approach, based on proof of work, variations of PBFT form the basis for the consensus algorithms in Hyperledger Fabric, EOS, Tendermint, Zilliqa and many other less know platforms. There are also several implementations of Ethereum, based on the algorithm.
PBFT is the consensus protocol of choice for many of these systems for two main reasons. Firstly, the protocol is very efficient and can achieve high transaction throughputs. Secondly, the protocol provides transaction finality, meaning that once a transaction is included, it is confirmed. Ever heard, of the recommendation to wait for six block confirmations before considering a Bitcoin transaction confirmed? That’s because Bitcoin provides finality in a probabilistic sense only. With each block added on top of the block including a transaction, the probability that the transaction is undone is reduced.
PBFT’s biggest disadvantage is the fact the bandwidth required by the protocol scales quadratically with the number of nodes involved. The protocol is, therefore, usually used between a small number of validator nodes, either in a consortium chain or in delegated proof of stake model.
One can only speculate, but this may have been the main reason for Satoshi Nakamoto not mentioning PBFT and similar work in the Bitcoin paper and using proof of work instead. However, the fact remains, that one of the most popular algorithms in blockchain technology has been around for many years.