Basic Consensus Algorithms, Explained (2024)

Byzantine Fault
3m + 1 Processor Algorithm
Proof of Work
Finality Problem
Casper FFG

Consensus is a process for all the nodes in a distributed system to agree on a single state or to make same decision. Consensus algorithm is a set of protocols or rules for the process.

Consensus is complex because it is basically many body problem, and even far more complex when various constraints are included. One of the most difficult constraints is Byzantine fault.

Byzantine fault says that there could be abnormal or malicious nodes which don’t follow rules or even violate intentionally to prevent consensus. Those nodes might do so because they are broken or occupied by a hacker. Although the problem can seem to be very old problem from the title of ‘Byzantine’ which is the name of an ancient Greek city or Roman province, it was not until 80’s that people had started to study Byzantine fault.

The early paper¹ published in 1982, Byzantine fault was described like the following picture.

Several divisions of Byzantine army setup camps surrounding enemy. Each general of division has to make decision to attack or retreat. They want to reach same decision to avoid troublesome case where some divisions attack but others retreat. To align the decision, Byzantine general can send messengers carrying his intention to the other generals. But the problem is that there can be traitors among generals. These traitors will disturb the message exchange to prevent all the normal generals reaching a same conclusion. For example, if the general ⑥ is traitor, he may send attack intention to general ① but retreat intention to general ② and general ⑤ to prevent consensus.

If there is no traitor, a simple majority rule can always lead the generals to consensus. In other words, each general collects all the other generals’ intentions and concludes following the intention more than half of the generals including himself made. If all the generals are split exactly in half, the default action can be applied.
But with a possibility of traitor(s), the problem become complex. If there is only one traitor among 6 generals, can this majority rule also make the other 5 generals reach consensus all the time? Or, is there any other rule that guarantee consensus? How about 2 traitors among 6 generals?

Under the circ*mstances like above, if a consensus algorithm can make all loyal(non-traitor) generals to arrive at the same decision, this algorithm is said to be Byzantine fault tolerant. And feature or requirement for an algorithm to be Byzantine fault tolerant is Byzantine fault tolerance or BFT in short.

Let’s move on to more detailed explanation with a simplest case for more clear understanding.

Suppose there are 3 generals in all and only one of them is traitor. Of course nobody knows who is traitor. Consensus algorithm is a simple majority rule.

The traitor always send opposite intentions to the other 2 generals to hinder the consensus. As you can see case (1) and case (2) in the above picture, if the 2 loyal generals have a same intention, they will build a same conclusion regardless of the traitor’s disturbance. But like case (3), if the 2 loyal generals have different intentions, one of them will attack and the other retreat at the end. The consensus will be broken in case (3), so the majority rule is not Byzantine fault tolerant for these 2 loyal generals and 1 traitor. Then, what is the Byzantine fault tolerant consensus algorithm for this situation?

Theoretically, it is proved that there is no Byzantine fault tolerant algorithm for 3 generals with 1 traitor, if message signing is not utilized¹.

There are various constraints other than Byzantine fault, in the consensus. The most usual constraints are whether message delivery is guaranteed or not, whether message is signed or not, and whether network is fully connected or not.
A network is said to be synchronous(sync.) if the delivery is guaranteed within a certain delay limit, or asynchronous(async.) if a message can be lost due to communication failure or overload. Surely it is far more difficult to make asynchronous networks Byzantine fault tolerant than synchronous networks.
If message signing² is applied, a malicious node can not alter messages when relaying messages from other nodes, although its own message can be still manipulated. So, with message signing, it is possible to design Byzantine fault tolerant algorithm more easily. But, building reliable message signing system also requires considerable cost and effort.

[1] L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem”, 1982
[2] Digital signature

The first achievement on general algorithm guaranteeing Byzantine fault tolerance is “3m + 1 processor algorithm” appeared in 1980.

The paper¹ proves first that for a synchronous network with m faulty nodes, there is no Byzantine fault tolerant consensus algorithm, if the network has equal or less than 3m nodes in all. In other words, it is prerequisite to have equal or more than 3m + 1 nodes.

For example, if there is 1 faulty node among 3 nodes, no Byzantine fault tolerant algorithm can exist. When 1 faulty node is expected, the network should has at least 4 (3m + 1, m = 1) nodes like the 2nd from the left in above picture. If the node is more fragile and 2 faulty nodes can exist at the same time, the network should has at least 7 (3m + 1, m = 2) nodes for Byzantine fault tolerance like the last in above picture.

Then, what is the Byzantine fault tolerant algorithm, when 3m + 1 constraint is guaranteed. Before we go into detail, we look into a simple notation for message delivery.

The above picture shows message delivery for a simple 4-nodes network. There can be at most 5 different paths to deliver a message from node ① to node ④ including relays. But duplicate relays where a message would visit intermediate nodes more than 2 times are excluded.
5 paths include 1 path for direct delivery, 2 paths for indirect deliveries with 1 relay, and 2 paths with 2 relays.
These cases are denoted like the followings

v:1:4 : direct delivery from 
v:1:2:4 : relayed by node 2
v:1:3:4 : relayed by node 3
v:1:2:3:4 : relayed by node 2 and 3 in turn
v:1:3:2:4 : relayed by node 3 and 2 in turn

For example, v:1:3:2:4 means the message is sent by node ① to node ③, relayed by node ③ to node ②, relayed again by node ②, and finally arrived at node ④.

The above statements are the consensus algorithm called 3m + 1 processor algorithm. The algorithm enforces enough relays for Byzantine fault tolerance.
More exactly, for a network which may at most m faulty nodes and so contains at least 3m + 1 nodes, should relay each message m times. And each node has to decide other node’s intention on behalf of majority rule considering m-times relayed ones.

If the network has 4 nodes (m = 1) to cover at most 1 faulty node, each node has to make decision after gathering direct messages(OM(1)) from the other 3 nodes and 1-time relayed messages(OM(0)). For m = 1, 2 times relay is also possible, but 1 time relay is enough according to the algorithm.
For m = 2, where the network has 7 nodes to overcome 2 faulty nodes, each node should gather direct messages(OM(2)), 1-time relayed messages(OM(1)) and 2 times relayed messages(OM(0)). With 7 nodes, 5 times relay is possible at most, but 2 times relay is enough.
So, when generalized with m faulty nodes, each normal node among at least 3m + 1 nodes has to collect messages directly delivered(OM(m)), 1 time relayed(OM(m-1)), 2 times relayed(OM(m-2)), and so on up to those m times relayed(OM(0)).

You may notice that when relaying message, the message wouldn’t be sent again to nodes already passed before. For example, in the 7-nodes network, the message of node ① which and arrives at node ③ after relayed by node ② will not be sent to node ② or node ① again. This message will be sent to other nodes from ④ to ⑦.

Simplest Case

To understand how relays can contribute Byzantine fault tolerance a bit more, let’s discuss the simplest case (where m = 1 ) in more detail.

The below picture shows how each of node ①, ③, and ④ collects the message originated by node ② according to the 3m + 1 processor algorithm

If node ② is traitor, there are 6 different cases where node ② sends its intentions to other nodes to disturb the consensus. You can see those cases from v:2:1, v:2:3, and v:2:4 columns in the following table. In these 6 cases, node ② sends different intentions to other nodes. Cases where node ② sends same intentions are excluded because those cases will not disturb consensus.

If node ①, ③, and ④ receive only direct messages from node ②, they will conclude different intentions (Attack or Retreat) for each case. You can see it in the light orange background columns of above table.
But surprisingly, if one time relayed messages are collected, things change.
See the light green columns in the above table. For case 1). Although node ② sends ‘Attack’ to node ① and ③, but ‘Retreat’ to node ④, each node can gather all these ‘Attack’, ‘Attack’ and ‘Retreat’. In other words, all of node ①, ③, and ④ collect same values from node ② (2A + R, 2 ‘Attack’s and 1 ‘Retreat’), so they will have same conclusion on node ②.
For other cases — case 2) case 6), things are same. Even though the gathered values can vary from case to case — 2A + R or A + 2R. the values are same for all nodes in a single case.
Among 6 cases only one case occurs. So, node ①, ③, and ④ will have same conclusion on node ② in any case.

To review above more generally, by virtue of relay, each normal node (①, ③, or ④) can collect all the messages sent to other nodes (③ and ④for ①, ④ and ① for ③, ① and ③ for ④) from the sender (②). In other words, each node will see the same set of messages, and so have same conclusion.

# When node 2 is traitorv:2:3:1 = v:2:3
v:2:4:1 = v:2:4
v:2:::1 = v:2:1 + v:2:3:1 + v:2:4:1 = v:2:1 + v:2:3 + v:2:4v:2:1:3 = v:2:1
v:2:4:3 = v:2:4
v:2:::3 = v:2:3 + v:2:1:3 + v:2:4:3 = v:2:3 + v:2:1 + v:2:4v:2:1:4 = v:2:1
v:2:3:4 = v:2:3
v:2:::4 = v:2:4 + v:2:1:4 + v:2:3:4 = v:2:4 + v:2:1 + v:2:3v:2:::1 = v:2:::3 = v:2:::4

The same principal based on relay applies even when there are more nodes. After enough relays, each node can collect all the messages sent to other nodes from a node and so make same decision.

3m + 1 processor algorithm may look perfectly useful with its simple recursive rules. But actually the algorithm has a fatal weakness in scalability due to its complexity. As can be seen in table below, the number of message increases radically as relays are repeated. The complexity against m (the number of faulty nodes) is O(nᵐ). So the algorithm is only useful with small networks. With large networks, we need other algorithms.

[1] M. Pease, R. Shostak, and L. Lamport, “Reaching Agreement in the Presence

In 3m + 1 processor algorithm or pBFT explained above, nodes collaborate to overcome the Byzantine fault. To collaborate over the disturbance of broken or hacked nodes, algorithms have a constraint on the number of node and require enough communications, which restricts the scalability.
3m + 1 processor algorithm has complexity of O(nᵐ) and pBFT has complexity of O(n²).

Proof of Work¹ (PoW) algorithm takes totally different approach. In PoW network, every node competes rather than collaborate. The node which succeeds to solve a mathematical puzzle that is extremely difficult to solve but very easy to verify will make a decision for the whole network at that time. Right after a puzzle is solved and the solution is propagated throughout the network, the competition for the next puzzle starts.
There are a few types of such puzzles including hash computation and prime factorization² of huge integer. There are no special formulas or techniques to solve these kind of puzzle more quickly. Only simple repeated trial and error³ is valid strategy.
So, the chance for a node to solve the puzzle is completely probabilistic. The probability is solely dependent on the computing power of the node. If the computing power is decentralized enough among nodes, it is actually impossible for particular node or nodes to reign the PoW network.

Public blockchain network such as Bitcoin and Ethereum, as the network is open for anyone to join as a peer with his or her own node, computing power concentration is largely suppressed.

For Bitcoin and Ethereum, the puzzle is finding a nonce that satisfies very specific condition on the hash of block header combined with the nonce.
As a simple (not real) example for understanding, the condition says the hash should start with 4 leading zeros. The following sentence express the condition or puzzle more concisely and clearly — SHA-256 is one of popular hash functions and data means block header

Find nonce for SHA-256(data + nonce) to Start with '0000'

Hash function⁴ is a function that convert arbitrary-size data into fixed-size data of totally different and unpredictable values.
Hash function has some important and unique features. The first and foremost one is the the function is irreversible. More formally, there is no inverse function for a hash function.
For example, it is simple and straightforward the SHA-256⁵ hash value of “Hello, world!” is “0x315f5bdb76d0…”, but it is impossible to calculate the inverse SHA-256 for the hash value of “0x315f5bdb76d0…” is “Hello, world!” using any formula or special technique.

SHA-256("Hello, world!") = "0x315f5bdb76d0…" # easy
SHA-256⁻¹("0x315f5bdb76d0…") = "Hello, world!" # no formula

The second feature is that the hash function changes the output(hash value) a lot even for a very small change of input. In other words, hash function diffuses input very dynamically.
You can see this in the below table. In the table, the input values are different a little from “Hello, world!” to “Hello, world!0”, “Hello, world!1”, “Hello, world!2”, and so on. But the hash values of those are totally different. You can never guess or calculate the hash of “Hello, world!1” from the hash of “Hello, world!0”, “Hello, world!2”, or other similar input.

If you need to find a nonce which would produce hash value starting with 4 leading zeros (“0x0000”) when appended after “Hello, world!” — like the “Hello, world!4250” at the last row of the above table, there’s no special way or method more effective than simple sequential trials from “Hello, world!0” to “Hello, world!4250”.

The concrete PoW algorithm being used by Ethereum is Ethash⁶. Ethash uses Keccak-256 as a hash function. The puzzle of Ethash is to find a nonce which makes the Keccak-256 hash of the block header and that nonce less than the specified value.

The above mine is Python function described in Ethash specification⁶. In Bitcoin or Ethereum, finding the nonce that meets the condition and solving the puzzle is called mining.
The node which succeeded finding the nonce will be given reward. So solving the puzzle is like mining gold.

In the while clause of the above function, the trials are repeated changing nonce by one until the hash value (hashimoto_full) become equal or less than a certain target. The target is a value given by dividing 2²⁵⁶ by the specified difficulty. The hash value of SHA-256 is 64-digit hexadecimal and the largest value is 2²⁵⁶. The target is smaller than 2²⁵⁶, so when expressed in 64-digit hexadecimal, the value has leading 0(zero)s. For example, target value 2²²⁷ has 7 leading 0s and target value 2²⁰⁵ has 12 leading 0s.

The product of target and difficulty is constant 2²⁵⁶. Raising difficulty will lowering target so that more leading 0s necessary.
The number of all hash values of SHA-256 is 2²⁵⁶ and at a given difficulty the number of hash values of successful mining is target. So, target/2²⁵⁶ is the possibility of successful mining in a single trial. This is same with the inverse of difficulty(1/difficulty).

The table below shows the real difficultys and targets of a few blocks in Ethereum mainnet. If difficulty is managed to be constant, the block creation interval will be affected by the number of node or the total computing power they are consuming. To prevent fluctuation of block creation interval and keep block creation timing uniform and predictable, Ethereum continuously reconcile the difficulty for the new block based on recent block times.

In Bitcoin or Ethereum, every transaction is digitally signed so that faulty or traitor node can not manipulate transactions. Block is quite easy to verify although extremely hard to mine so that malicious node can not spread invalid blocks. Like this way, using both PoW and digital signing, Bitcoin and Ethereum can achieve Byzantine fault tolerance.

Because PoW is working based on competition not corporation, the complexity is irrelevant to the number of nodes. The complexity largely depends on the difficulty of the puzzle. So, for large network containing hundreds or thousands of nodes, PoW seems to be much favorable than corporation based consensus algorithms such as pBFT. But PoW also has fatal problems. The best well-known one is enormous energy waste due to heavy competition and another important one is finality problem explained in detail below.

Finality Problem

To recap, the successful puzzle solving is called mining in PoW network. Mining means a new block is created and the miner is rewarded. Large number of nodes compete intensively to get the reward.
Looking into details of mining rule, the hash calculation includes the hash value of last block in addition to the transactions to add and nonce. It is for maintaining the blockchain linear or 1-dimensional. This makes it more difficult to compromise the integrity of blockchain and prevents the conflicting states in blockchain.
In most of the cases, minings occur with intervals enough to keep the blockchain linear. But almost simultaneous minings can occur no matter how much the difficulty is increased, because mining is probabilistic by nature.
Although the verification is much simple, it takes time to propagate a mined block to all nodes across the world. So simultaneous minings make the whole network a little non-uniform.

Like the following example. if two distant nodes P and Q succeed to mine a block — block B(m) and block B(n) in each — almost at the same time, within time not enough to propagate B(m) and B(n) across the whole network, nodes around P will have B(m) as a last block and nodes around Q will have B(m) as a last block. Nodes at similar distance from both P and Q can not distinguish which block actually mined first.

Both B(m) and B(n) are based on the same previous block. In other word, they contain the same hash of previous block header. So, the previous block is called parent block.

Nodes continuously try to mine next blocks to acquire rewards. Some nodes which received B(m) first would challenge next block based on B(m), but other nodes which received B(n) right before would challenge next block based on B(n). Although successful minings occur with enough time intervals due to the difficulty in most cases, it is possible with very low probability that the right next mining also occurs almost simultaneously. In these case, mined blocks can have different parent blocks. For example one of the 2nd simultaneous blocks is base on B(m) and the other is base on B(n) like the following example image.

You can see that the entire chain is not liner any more, although there was no violation against PoW rules before. This is called fork, and each linear (connected linearly) part from the fork point is called branch. In the above example, there are 2 branches. One branch is B(m) followed by B(m2) and the other is B(n) followed by B(n2).

With high competition for mining and non-uniformity in the network, the previous abnormal (but not illegal) situation can continue further. In other words, 2 branches grow more like B(m)-B(m2)-B(m3)-B(m4) and B(n)-B(n2)-B(n3)-B(n4). Or even another branch may appear.
But, eventually only one branch will survive because mining is really difficult and all of these are probabilistic. There is also another mechanism called longest chain rule which enforces to select the longest branch under a fork situation. The longest rule would accelerate only one branch to survive once one of the simultaneous branches starts to grow quickly.

Although the chain remains linear in the long term, there could be a serious trouble called finality problem in the meanwhile. Finality problem is a situation where successfully mined transactions or blocks become invalid or canceled later due to a fork explained above. It is not caused by a violation of PoW. It is an intrinsic aspect of PoW.
The picture below describes a typical process of finality problem. It shows growth of a blockchain as time goes by. At ②, block B(n) containing tx(b) was mined successfully. But almost simultaneously another block B(m) which is not child of B(n) also was mined making a fork(③). Although two branches had kept growing together, after all a branch stemmed from B(m) survived invalidating the block B(n) and the transaction tx(b), like ⑥. This implies that a transaction completely committed once can be roll-backed later. It is a significant drawback from the data persistence system’s point of view.

To workaround the finality problem, we should wait and watch for a while a block including our transaction to grow further even after mining. Usually, 6 more blocks is thought to be necessary for Bitcoin and 12 blocks for Ethereum. Of course, these numbers doesn’t guarantee prefect finality.
Currently block time of Ethereum is about 13 seconds. But finality problem makes the actual time to confirm a transaction 2.6 minutes instead of 13 seconds.

Finality problem can be exploited by a huge miner to compromise integrity and trust of a Blockchain. If he or she has more than 50% of entire mining capabilities, he or she could invalidate very important or expensive transactions to earn a profit or to achieve evil purpose. This is called “51% attack”.
Even though it may considered almost impossible to occupy more than 50% mining power among hundreds of independent and active miners, there are actual thread of 51% attack⁷. Ethereum Class(ETC) was attacked⁸ at Jan. 2019 and Bitcoin Gold(BTG) at Jan. 2020⁹.

To solve finality problem, Ethereum has developed a new consensus algorithm called Casper FFG and it is among key features of Ethereum 2.0.

[1] Proof of Work
[2] Prime Factorization
[3] Trial and error
[4] Hash function
[5] SHA-256
[6] Ethash Specification
[7] What Is a 51% Attack?
[8] ETC 51 % attack — what happened and how it was stopped (14 Jan ‘19)
[9] Bitcoin Gold Blockchain Hit by 51% Attack Leading to $70K Double Spend (Jan 27, ‘20)

Casper FFG is a type of PoS(Proof-of-Stake) consensus algorithm and has a few unique features that is expected to solve or improve dramatically the finality problem. It was first proposed by Vitalik Buterin and Virgil Griffith in 2017¹.

First, Casper FFG is a partial consensus algorithm which undertakes only finality agreement. Casper FFG doesn’t include any rule to make or confirm blocks. It defines a protocol to more quickly determine a real final block among several branches under fork situation. It can be applied over other consensus algorithm such as PoW. So, Casper FFG is classified as an overlay algorithm.

Second, Casper FFG itself is a type of PoS(Proof-of-Stake) algorithm which would expect selected nodes to run. Unlike PoW network where any node can take part in mining, in PoS network, only some special nodes who has some stake can join the consensus to determine something like block. In Casper FFG, these nodes are called validators.

Third, Casper FFG defines both incentive rules and penalty rules. Other PoS algorithms including pBFT usually don’t have penalty rules. So even if some malicious nodes try to disturb consensus, there’s no efficient way to prevent them. “Nothing at stake”² is one of the most well-known problems for PoS algorithms. But, in case of Casper FFG, validators to exploit nothing at stake will be punished and lose all their stakes.

Like pBFT or usual PoS algorithms, Casper FFG runs rounds in a fixed time schedule. In each round, all validators should vote in each round following 2 strict rules. If a validator violates a rule even once, it will lose its stake and be evicted from validators. So, these rules are called slash conditions.

If a block receives votes from more than 2/3 validators in a round, the block is said to be justified. Justified blocks still can be forked, so are not finalized. But if two sequential blocks are justified, the parent block of the two becomes ultimately finalized.
To add some details, because slash conditions prohibit a spanning vote, after two adjacent blocks win votes, at most 1/3 validators can vote any block below the parent block following the rules in later rounds. So, unless another 1/3 validators violate the slash conditions losing all their stakes, the parent block would be an ancestor of all the later justified votes.

Due to a penalty rules (slash conditions), Casper FFG is expected to promote more tight cooperation and lead to far more fast and effective finalization than longest chain rule.

Casper FFG is a governing algorithm of Beacon chain which is the topmost feature of Ethereum 2.0³ phase 0⁴.

For more concrete understanding, my presentation⁵ at SlideShare may be helpful if read with the latest paper.

[1] Vitalik Buterin and Virgil Griffith, “Casper the Friendly Finality Gadget”, 2017
[2] Nothing At Stake Problem — A Forkin’ Mess!
[3] Ethereum 2.0 Info
[4] Validated: Staking on eth2 #0
[5] Casper FFG Explained
[6] Vitalik Buterin and Virgil Griffith, “Casper the Friendly Finality Gadget, Ver. 4”, 2019

Join Coinmonks Telegram Channel and learn about crypto trading and investing

Also Read