Previously on Episode 4 of “The Magic Behind Blockchain”…

• we updated our blockchain framework / mind map; explaining the CAP Theorem and the Blockchain Trilemma
• we introduced the Durability rule (making it a Quadrilemma)

Today’s episode is quite interesting because we will complete the beginner section (basics) of this series. The entire focus of this episode is Consensus algorithms and Categorisations.

After taking a detailed look at about 80 consensus algorithms / protocols, it turns out they can all be simplified / decomposed into 4 main categories.

This is what we are calling Consensus Categorisations.

RECAP — VERSION 2 OF THE MIND MAP

Fortunately, it is quite easy to recap the first 4 episodes just by looking at the above picture. For those who have gone through Episodes 1 to 4, this picture is almost intuitive at this point.

Now that you are all caught up, you know exactly where Consensus Categorisations fits in the bigger picture / puzzle. Let’s dive in …

TRANSACTION FLOW

In order to look at the various consensus protocols, let’s visualise the transaction flow in most blockchain networks:

1. The issuer of a transaction creates a transaction according to the blockchain specification at the Content Layer. Thus, making sure to use the right format, signatures, etc.
2. The issuer broadcasts the transaction to its neighbouring nodes. Let’s say there are N nodes. This is very crucial. Assuming each node has 30 neighbours, it only takes 3 hops to reach 27,000 nodes (30 x 30 x 30). This gossip method is called a flood fill in Bitcoin.
3. Each node that receives this transaction performs basic correctness checks on the transaction and then keeps it in its own local storage called Mempool. Here, the transaction waits for a consensus protocol to be applied.
4. Each node also keeps a history of previous transactions in their local storage whether fully or just the headers.
5. A validator node eventually gets a hold of this transaction in addition to other transactions, bundles them and runs the consensus protocol. Once successful the result of the protocol is also broadcast throughout the network via the same means. Each node updates its local history of transactions.

THE GROUND RULES OF CONSENSUS

Any person trying to achieve consensus in a Blockchain-type setup will usually aim for two outcomes (What to agree on and When to do / use the agreed-on thing):

1. DATA / ACTION AGREEMENT (WHAT ARE WE AGREEING ON?)
   This is essentially what the blockchain participants have decided to agree on. In almost all cases, it is data. From this data, an action can be taken. In the Cake & Bread protocol, the data / action was “the share of the cake each sibling should receive”. In the Byzantine Generals’ Problem, the data / action was “attack or retreat or undetermined”.

In fact, we can go one step further and call whatever is agreed on at any point in time a State; mathematically called S. The State can only change if there is agreement from all / most participants.

In the diagram above, participants issue transactions (like “I want A’ to happen”) in attempt to change to a new State that is individually beneficial for them. But since we know NOT all participants are Honest, consensus algorithms are just a smooth and secure way to get to the next state that is collectively beneficial for all participants. In the diagram above, the consensus algorithm determines that transitioning from current state S = (A,B,X,Y,Z) to S’ = (A’,B’,X,Y’,Z’) is the best approach for all parties involved.

Why didn’t X change to X’ ? The consensus protocol determined that Participant 4 was Dishonest so it maintained the previous X in the new state S’.

To summarise, we can mathematically think of consensus algorithms and states like this :

APPLY(S, TX) → S’ or error.

The consensus algorithm applies a list of transactions TX = {t₁,t₂,t₃,…,tₙ} to the current state S and you either get a new state S’ or an error if you are unable to reach a new state.

• In the Cake & bread algorithm, the current State (S) was “Each sibling having 0 share of the cake”. After applying the consensus algorithm, the new State (S’) is for example: (Sibling A has 33% of the cake, Sibling B has 33% of the cake, and sibling C has 33.1% of the cake). Otherwise, there is an error and we are unable to share the cake. Transactions are the individual wishes of the siblings (e.g. I want to have 40% of the cake).
• In the Byzantine Generals’ Problem, the current State (S) was “undetermined”. After applying the consensus algorithm, the new State (S’) should either be “attack” or “retreat”. The transactions are the individual wishes of each General whether Honest, Semi-Honest or Dishonest.
• In Bitcoin, the current State (S) is “the ownership status of all existing Bitcoins” a.k.a UTXO (Unspent Transaction Outputs). The new State (S’) is “the ownership status of all existing Bitcoins after a set of Bitcoin transactions in a new block have been applied.
• In Ethereum, the current State (S) is “the collection of all Ethereum accounts (both human and smart contract accounts)”. An account is made of nonce, ether, contract code if present and account storage. The new State (S’) is “the collection of all accounts with new Ethereum transactions applied (both regular transactions and contract-triggered transactions)”.

You can turn any blockchain consensus protocol into a State Transitioning System. This is a very efficient way of analysing or looking at it.

TIP: Most blockchains have to start from an initial state before you can start using the state transitioning system and change from state to state. This initial state is usually called a genesis block / state.

2. TIME AGREEMENT (WHEN ARE WE DOING / USING THE AGREED THING?): Just to explain how important this is, imagine that you suddenly won the lottery and came into some cash (say 1 million euros). You decided to use 10% to buy some bitcoin (so 100,000euros worth Bitcoin). But since you didn’t want to go through a regular exchange, your friend recommended a trusted person to you for a peer-to-peer transaction exchange.

Basically you meet up with this person, they transfer 100,000euros worth of Bitcoin to you (at today’s rate about 5 bitcoins), and then you give them raw cash after verifying in their app that they sent the transaction.

All goes well. You give the 100,000euros and you watch them issue the transaction into the Bitcoin main network. Once you part ways, say 30minutes later, this person sends another transaction into the Bitcoin network, sending the same 100,000euros to another wallet they own (this time with a very high transaction fee so that miners will choose this transaction first). Essentially, revoking the transaction.

Now here you are at home, constantly refreshing your mobile app waiting for your 5 bitcoins to appear. It’s only after 24hours that you come to this painful realisation. You have just been scammed.

You see… the Bitcoin network has no concept of universal time. Specifically, which transaction came before the other. Even if it tried, every computer issuing a transaction into the network has its own local time (time-zone). How do you synchronise this and determine what came first in terms of universal time? The answer is: Bitcoin doesn’t. Miners mostly pick transactions with the highest transaction fees first. So what you should have done here was to wait for 5 hours after the person made the bitcoin transaction before giving out the cash. This would have allowed the transaction to be more permanent, thus, giving a more secure sequence of events.

The concept of timing is a very crucial ground rule to consider when looking at consensus protocols. After you have agreed on some data / action / decision; When exactly should this take place? Always have an answer for this. Because if you use an “agreed time” as input to any crucial decision (e.g. accepting or rejecting a transaction, it may fail due to the absence of consensus on time (no universal way of keeping time. So you need a trusted source of time.

BLOCKCHAIN CONSENSUS CATEGORIES

Now that we understood the general flow of transactions and the 2 consensus ground rules, let’s look at some consensus categories.

Although you will not find this in any books or papers, after looking at about 80 consensus protocols, it became abundantly clear that consensus protocols can be generally distilled into two types (participant-initiated and gossip-initiated) and 4 main categories: Economic Cost-Based , Capacity Consuming, Gossip-based and Hybrid protocols.

Before we go into these 4 categories

Take 5 minutes to think of a solution to the Byzantine Generals’ Problem. These Generals need to agree on whether to attack or retreat and they need to do it via messengers. Write down whatever solution you thought about, because chances are that you will find it in the following section in some shape or form.

Consensus protocols are not exactly found in nature. They are all made up! So think of one yourself too and analyse it. You will understand things much better.

NAIVE SOLUTIONS

The most common solutions most people think about are:

1. Before going to the gates of Byzantium, one General could be elected as Lead General. That General can then announce ATTACK or RETREAT. And all Generals will just follow suit. This approach relies on the authority of the Lead General and most importantly on the guarantee that other generals can verify that the message (attack or retreat) came from the Lead General. Maybe the lead general has a particular stamp, signature or code for this. In the Cake & Bread Algorithm, this is similar to saying the eldest sibling should always share the cake. Let’s call this type of solution Proof of Authority.
2. In the heat of the Battle, one General can rise up and do the hard research on all the defences of Byzantium. They also train their physical battle skills and then broadcast ATTACK or RETREAT. Once the other Generals hear the wisdom in the plan and see the muscles and skill of this General, it is clear that they have put in a lot of work. The plan and the muscles are literal proof that they worked hard. So the other generals fall in line with this plan. Let’s call this type of solution Proof of Work.
3. One general can rise up and say. “Everyone should attack. I have signed a bond. Whoever follows my plan will be guaranteed 5000 pieces of gold win or lose.” Here, this general has put his / her own resources on the line. Therefore, he has a stake in it; and other generals are inclined to follow this General’s leadership because they can clearly see thathe has a huge incentive to wage ware for a successful outcome. Let’s call this type of solution Proof of Stake.
4. Finally, all Generals can engage in some rounds of sending messages that ends up with a common agreed value. For example they could all end up jointly deciding that, if it rains, ATTACK else RETREAT. The initial condition of whether it rains or not takes some time to agree on but once done it can be used as a true / false type condition to jointly take other future decisions. This is more like Byzantine Fault Tolerance (BFT)

So in summary, there are only 2 ways: either a participant (General, sibling, miner, validator, etc.) initiates the consensus protocol (participant-initiated) or the protocol is initiated by some kind of gossip (gossip-initiated).

According to game theory, building a consensus protocol is as easy as listing all actions by participants that are good for the protocol on one hand (e.g. correct validation of transactions) and listing all actions that are bad for the protocol (e.g. submitting fraudulent transactions) on the other hand. Reward the good (e.g. with coins) and punish the bad (loss of resources). This is what provides the economic incentive for the protocol to run securely.

ECONOMIC COST-BASED CONSENSUS PROTOCOLS

This covers essentially ALL consensus protocols that rely on a blockchain participant / group of participants (validators) leveraging some economic resources they own in exchange for trust from other participants. Here, we call it economic cost-based because, there is always a subtle threat that: if this temporarily trust person does something dishonest, they will lose ALL /a significant part of the resources that they have leveraged. So there is a clear economic cost as punishment for dishonesty. And there is a clear economic incentive for honesty!

There are 5 sub-categories of economic cost-based protocols. See below

PROS VS CONS: Economic Cost-Based Protocols are generally great at determining agreed state especially PoW. Proof of Stake protocols are good at selecting a participant (leader, validator, etc.) The Shared cost models are also very fast meaning high TPS. However, protocols like PoW can also be wasteful in resources like electricity, money, etc. They also have the single point of failure downside. For a brief moment, whoever is in charge has a lot of power. Hence they must be chosen as randomly as possible and especially in Proof of Stake variations, ensure that the amount at stake is more or equal to the amount the participant (validator) stands to gain if they act maliciously

For those who want to get their hands dirty, let’s take a quick look at the Proof of Work Algorithm in Bitcoin. In PoW, the participant performing the consensus operation is called a miner.

1. Miner collects a list of valid list of transactions from Mempool say TX, validates them and bundles them into a block.
2. Miner references valid previous block (a block is just a list of transactions and some header information like block ID, timestamp, etc.)
3. Miner makes sure referenced block has timestamp greater than that of the previous block and less than 2 hours into the future.
4. Calculate nonce for all data within the block such that the leading characters of the resulting hash match difficulty

The nonce is calculated using a simple code like below:

So basically we are hashing all the data + nonce, successively increasing nonce and counting the leading zeros to make sure it matches a set difficulty.

Cryptographically we choose the leading 0s rather than the ending 0s because those are the most significant bits. They are less likely to repeat.You can also use any secure hash Algorithm. Technically Bitcoin uses 2 rounds of SHA256 just to compensate for possible flaws in the Merkle-Damgard construction. Ethereum uses Keccak-256 which is a sponge function so better than the Merkle-Damgard construction.

You get results like when you set difficulty 2, 5 and 7 respectively

You can see that as the difficulty increases, the work required to get a valid nonce also increases. More and more processing power needed. The current Bitcoin difficulty “has” about 19 leading zeros!

TIP: The work done in Proof of Work is actually meaningless. Cranking through hashes has no value other than making sure that you stay honest and that semi-random people are able to calculate the right nonce. If you crank through millions of hashes to get to the right Nonce for Bitcoin, you better make sure all the transactions are valid. Otherwise you wasted all that electricity for nothing! Variations like Meaningful Proof of Work tweak this algorithm in order to use the processing power for something more meaningful such as medical and chemical research. You can also use this algorithm in regular applications for rate-limiting.

CAPACITY-CONSUMING PROTOCOLS

These are protocols focused on consuming relatively inexpensive resources such as memory(RAM), disk-space or other storage, time, etc. The key differentiator here is that whatever is consumed does not leverage any cost on the participant (miner, validator, etc.). For example in Proof of Capacity, mining / validating here typically requires reading through a cache of disk space. Miners / Validator nodes pre-generate chunks of data (sometimes called plots), containing all the computations necessary to forge blocks. The mining software automatically reads through the chunks of data in attempts to forge a new block. Rewards are assigned to pool which finds a block.

One of the most interesting protocols to look at here is Proof of History. It uses sequential hashes as a clock counter to keep track of time and hence securely determine the order of events. It’s a very nifty tool to use in combination with other consensus algorithms like Proof of Stake or Proof of Work.

PROS VS CONS: The main economic incentive here is the reward. It also conserves a lot of resources (electricity), etc. It is not very expensive as space requirements are relatively cheaper as compared to storage requirements. The downside here is that there is nothing really at stake. No real punishment for malicious actors.

GOSSIP-BASED CONSENSUS PROTOCOLS

These are consensus protocols that are achieved mostly via gossip. Thus, the responsibility of consensus is share amongst ALL (or most) participants rather than a randomly chosen node (miner, validator, etc.). Unlike the Shared-Cost model of the Economic cost-based Protocols, nodes here don’t directly validate blocks. They engage in rounds of communication which usually arrives at some sort of agreement vector. This vector acts as a shared secret between all participants. All honest nodes using this shared secret in any function will come to an agreed result.

PROS VS CONS: It gives very strong consistency (interactive consistency). Once there is an agreement, either ALL nodes agree or None will agree. This prevents forks and rollbacks as seen in Bitcoin. On the other hand typical Gossip-based protocols are complex to design and usually DO not scale well in terms of space, bandwidth and node count.

HYBRID CONSENSUS PROTOCOLS

This refers to consensus protocols that are a permutation / combination of any of the first 3 other consensus protocols. Usually a combination is done to suppress the weakness in one protocol and / or to enhance the strengths of one protocol. For example: Proof of Activity is a combination of Proof of Work and Proof of Stake.

PROS VS CONS: These protocols provide a lot of flexibility for different use cases. They also are a good way to have the best of both worlds if one sees some specific strengths in specific protocols. On the other hand, they are quite complex to analyse and security is a big issue to consider here.

CONCLUSION

Finally, we have come to the end of the beginner / basic section of this series. If you were here from Episode 1 to Episode 5, you already have a strong foundation to delve deeper in to more interesting / complex topics.

In Episode 6 we will zone in on Byzantine Fault Tolerance (BFT) simply because it provides some rather promising opportunities to develop scalable, efficient and secure consensus protocols. We will also delve more into the security and mathematical aspects.

Catch you in the next episode!

‍