Blockchains are formed by the creation of a consensus. This means that nodes must eventually agree on a particular history of the blocks which are created. However, on a large blockchain network like the one running bitcoin, consensus between nodes often takes some time, since nodes don’t always have perfect knowledge of other nodes on the network. This is often explained using an anecdote, first instroduced by Leslie Lamport.

Byzantine Generals Problem

Assume that a group of generals fighting a battle have two options:

1. Advance
2. Retreat

The generals depend on messengers to communicate with each other, and these mesengers are often unreliable. Messages may either get lost or changed during a messenger’s journey. Moreover, some generals may be traitors, i.e. they want their army to lose.

In such a situation, the honest generals have a difficult job of achieving consensus among all the generals. Let’s assume that we have a group of nine generals. Four of them wish to advance towards the enemy, while another four wish to retreat. In this situation the outcome of any vote depends on the last remaining general, who may give a contradicting vote. In this situation, voting is often performed by sending messengers, which can create their own problems, but the last general can send a vote of “Advance towards the enemy.” to the first four generals, while sending “Retreat from the enemy.” to the remaining four. This may cause the army to lose the battle, and eventually the war. If we replace the generals on the battlefield with computers on a network the same problems are caused, since some computers may be faulty, or messages may not reach other nodes on time. Hence the reason for proper consensus algorithms.

In the bitcoin blockchain, the proof-of-work consensus algorithm is used. As mentioned previously, not all blockchains use the same consensus algorithms, and even if they do, there are slight differences in implementation, which makes a huge difference in block creation times. Common consensus algorithms include:

• Proof-of-Work
• Proof-of-Stake

Other than the two mentioned above, PBFT(Practical Byzantine Fault Tolerance), Proof of Activity, Proof of Service, Proof of Authority, DBFT(Delegated Byzantine Fault Tolerance) and many more do exist. The use of a particular consensus algorithm depends on the requirements for the application.

Proof of Work

Most cryptocurrencies use a variation of the Nakamoto consensus protocol, named after the inventor of blockchain. This is a consensus algorithm based on proof-of-work. It provides consensus in two places; providing a common set of rules to verify valid data and secondly, ensuring that the copy of the data is consistent among the miners.

In proof-of-work, transactions are verified by special nodes called miners, who solve a cryptographic puzzle by finding a requried hash. The computational resources spent to solve the puzzle characterise the proof-of-work, since to reverse any transaction and add it to a block, the entire puzzle must be solved again, thus wasting precious resources for the malevolent actor. The transactions are inserted into a data structure called a block, which maintains all the information required to add a new block to the chain. After the puzzle has been solved, the new block is broadcast to all the nodes in the network, so that they may add it to their local copy of the blockchain. Since multiple new blocks may be generated with the required hash at the same instance, a consensus is formed by the amount of processing power(work)that has been expended to create the block. This results in the formation of blocks known as “stale” blocks, which are detrimental to the security and performance of the blockchain, since they may trigger “forks”, wherein a blockchain splits into two valid ones.

In these types of blockchains, miners stand to gain tokens through transaction fees for including transactions in their blocks. They also obtain newly minted coins(generated by the blockchain software). This provides incentive to the miners to continue mining.

One of the problems with proof-of-work consensus is that a significant amount of computational resources must be spent to solve the cryptographic puzzle. Due to the very high energy consumption, mining may be exhorbitant in areas without cheap electricity, thus preventing many people from becoming miners or cutting into the profits of existing miners. Another problem is the usage of specialized mining hardware, called ASICs which unfairly benefit a few miners with the means to buy such devices.

Proof of Stake

This is an alternative consensus algorithm which uses the amount of coins/tokens held by nodes to effectively decide their voting powers for the addition of a new block. For example, of you own 1% of the all the tokens in the blockchain, you can mine 1% of the proof-of-stake blocks. If you stake(i.e. keep aside) all your coins for voting rights, you may earn an interest on the tokens, but you wouldn’t be able to spend them unless you remove them from the stake. Peercoin is a cryptocurrency which uses the proof-of-stake consensus. In this type of consensus algorithm, validators(special nodes) are selected to approve a new block. These validators are selected from the existing nodes based on the amount of tokens each has staked to be a validator. These validators then add create blocks containing transactions. These proposed blocks are then broadcast to the nodes for addition to the blockchain. In the process, validators often earn a return on investment(ROI) by gaining coins in the form of transaction fees. If any validator behaves in a malicious manner, their coins will be slashed(removed from their control).

A problem with this algorithm is that nodes with greater number of tokens have a higher chance of becoming validators, which destablizes the decentralized nature of the network.

Enfin

Both proof-of-stake and proof-of-work have their merits, but ultimately, the selection of a consensus algorithm depends on the application where the blockchain will be used.

Further Reading

• Proof-of-Stake
• Byzantine Generals Problem
• Other consensus algorithms
• Proof-of-Work