In the first part, we discussed the Byzantine generals problem, how to achieve Byzantine fault tolerance, and how all of this relates to blockchain.

The algorithm in the previous article is, in fact, a solution that achieves Byzantine fault tolerance. However, that solution is not efficient enough and its variations have limitations, namely that less than a third of the network is rogue.

Running time of solving the Byzantine Generals Problem with the algorithm proposed by Lamport, Shostak and Pease (n = number of actors, m = number of traitors)

That leads us to a classic question in Computer Science:

Can we do better?

The topic of the present article will discuss alternative algorithms that achieve Byzantine fault tolerance.

Note: Please be patient with any simplifications you make. These algorithms have a lot of complex research behind them. I will provide links as we go along for the interested reader to do their own further research.

Blockchains use consensus algorithms to choose a leader who will decide the content of the next block.

That leader is also responsible for transmitting the block to the network, so that the other peers can verify the validity of its content.

Proof of Work (PoW)

This is the most popular algorithm used by currencies like Bitcoin and Ethereum, each with their own differences.

Before we continue, for non-technical readers:

A hash function is any function that can be used to map data of arbitrary size to data of fixed size¹.

If a hash function is secure, its output is indistinguishable from random.

Example:

keccak256(“hello”) = 1c8aff950685c2ed4bc3174f3472287b56d9517b9c948127319a09a7a36deac8

keccak256(“hello1”) = 57c65f1718e8297f4048beff2419e134656b7a856872b27ad77846e395f13ffe

In Proof of Work, in order for an actor to be elected as a leader and choose the next block to be added to the blockchain they have to find a solution to a particular mathematical problem.

Let that math problem be:

Given the data X, find a number n such that the hash of n added to the results of X is a number less than Y.

Example: The hash is a hypothetical hash function that has the results listed below

Y = 10 , X = ‘test’hash(X) = hash(‘test’) = 0x0f = 15 > 10

hash(X+1) = hash(‘test1’) = 0xff = 255 > 10 

hash(X+2) = hash(‘test2’) = 0x09 = 9 < 10 OK, Solved.

Since the hash function used is cryptographically secure [1,2], the only way to find a solution to that problem is by brute force (trying all possible combinations). In other words, probabilistically speaking, the actor who will solve the aforementioned problem first most of the time is the one with access to the most computing power. These actors are also called miners.

It has been very successful mainly because of its following properties:

1. It is difficult to find a solution for that problem given

2. It gives you a solution to that problem it is easy to verify that it is correct

Every time a new block is mined that miner is rewarded with some coin (block reward, transaction fees) and is therefore incentivized to keep mining. In Proof of Work, other nodes verify the validity of the block by checking that the hash of the block data is less than a preset number.

Due to the limited supply of computing power, miners also have incentives not to cheat. Attacking the network would cost a lot due to the high cost of hardware, energy, and potential lost mining profits.

The image nicely illustrates how Bitcoin, and any other currency that uses Proof of Work, discourages malicious behavior.

For readers who are interested in how string splits (also known as forks or string rearrangements in case of disagreement) work, I suggest this article.

Proof of Work provides the necessary security and has been shown to work quite well so far. However, it consumes a lot of energy:

Almost all African countries (separately) consume less electricity than the Bitcoin Mining industry

Proof of Stake (PoS)

Before I continue, let me make the analogy of the election of the leader (the actor who will select the next block) as a lottery:

In a lottery, probabilistically , if Bob has more tickets than Alice, he is more likely to win.

In a very similar way:

In Proof of Work, if Bob has more computing power and energy than Alice, and can therefore produce more work: he is more likely to win (mining the next block).

Likewise, one more time:

In proof of stake, if Bob has more stake than Alice, he is more likely to win (“mine” the next block)

Proof of Stake removes the energy and computational power requirement of PoW and replaces it with staking. Stake refers to an amount of currency that an actor is willing to lock up for a certain period of time. In return, they get a chance proportional to their stake to be the next leader and select the next block. There are several existing coins that use pure PoS, such as Nxt and Blackcoin.

The main problem with PoS is the so called nothing at stake problem. Essentially, in the event of a fork, participants are not discouraged from betting on both chains, and the danger of double-spending issues is increased. More on that here.

To avoid that, hybrid consensus algorithms appeared, such as the PoW-PoS combination used by Decred. The Ethereum Foundation is actively conducting research towards a secure and decentralized proof-of-stake protocol with Casper The Friendly Ghost and Casper The Friendly Finality Gadget.

Conclusion

In this article, we discuss Proof of Work and Proof of Stake, which are currently the consensus algorithms that achieve Byzantine fault tolerance and are practically used in today’s blockchain systems.

Other consensus algorithms exist, such as Practical Byzantine Fault Tolerance (Tendermint) or Distributed Byzantine Fault Tolerance (NEO).