An overview of consensus protocols

What's up everyone. Now before the next bull run really gets going, I thought I'd slap together a post about the different consensus protocols that exists within the crypto space. You know, before everyone stops giving a shit about tech anymore. I don't know about you but when I research a coin, one of the first things I check is how the blockchain network secures itself and how it achieves global consensus. I'll first introduce some basic concepts that constitute the blockchain, followed by the most well-known consensus protocols, namely Proof of Work and Proof of Stake. Then we'll take a look at some more exotic examples and their (dis)advantages. The last part will be about Byzantine fault tolerance which is a bit more technical and not that essential to properly understand consensus protocols.

Security and consensus are inherently difficult subjects, so I purposefully leave out a lot of details for simplicity and to avoid talking about things I don't fully understand myself. Please note that I'm no expert on blockchain technology or consensus protocols. I taught myself most of these things by scrolling reddit and reading whitepapers and some articles. If you notice anything that doesn't seem right, please correct me and I'll edit the post. Also, if you know about some good links on specific subjects, feel free to leave it in a comment and if necessary I'll add it to the post as well.

So, let's get into this.

Blocks

Cryptocurrencies live on a distributed ledger in the form of a blockchain (or not, if you like IOTA). This is effectively a chain of ordered blocks, with each block containing a set of transactions or any events relevant to the network. So a block is basically nothing else than a collection of data (transaction amount, timestamp, wallet addresses, etc.) describing what happened since the last time a block was made. A very well-explained and broader introduction to blockchains can be found here.

Nodes

A node is basically one participant of the network that helps building the blockchain. Each node can put together its own block with transactions but only one of them can add it to the chain. In a centralized system, it doesn't really matter which node gets to add its block to the chain since all of them correspond to the same controlling entity anyway. In a decentralized system however, the other nodes will have to check if the proposed block is valid. In essence, they have to make sure the proposed block does not contain fraudulent or malicious transactions. For example, a node can have a transaction in its proposed block that reverses a transaction in a previous block, which could be a case of double-spending. Or the block could contain transactions that contradict each other chronologically. So the job of the validating nodes is to find out if the proposed block doesn't contradict any statements made by previous blocks. (This is very much simplified, since there exist different types of nodes like full nodes, archival nodes, validator nodes, lightweight nodes,...)

If some group wanted to hijack the network, all they would have to do is create a lot of nodes such that they have a high chance of being chosen to add the next block to the chain. To counteract this, each node has to provide some sort of unfalsifiable resource to run. It is the nature of this resource that defines how the network is secured and what is the consensus mechanism.

Proof of Work (PoW)

PoW was proposed by Satoshi Nakamoto to secure the first ever cryptocurrency blockchain: Bitcoin. But it was first described way back in 1993 as a method to combat junk mail and was properly formalized a bit later in 1999. The required resource to run a node comes in the form of computing power. A node that wants to add its block to the chain has to prove it has this computing power by solving a set of equations (called hash functions) by trial and error. The first node that finds a solution is then verified by the other nodes, which check if the proposed solution actually solves the problem. Once verified, the block gets added and the node that found the solution gets a reward in the form of the native currency. Nodes that try to add their blocks this way are called "miners" since they are basically mining new coins (usually they get paid with transaction fees as well as newly produced coins). Obviously, the more work memory you have at your disposal, the more likely it is that you find a solution before anyone else. So the more computing power you have, the more likely it is your block gets added to the chain and the more control you have over the network.

Some PoW coins are: Bitcoin (BTC), Ethereum ^(but not for long)(ETH), Dogecoin (DOGE), Litecoin (LTC)

Proof of Stake (PoS)

PoS was first introduced by the team behind Peercoin in 2012 (which was actually a PoW/PoS hybrid). In this framework, the resource provided by the nodes is the native currency of the blockchain itself. Nodes have to "stake" some of their tokens in order to be eligible for adding the next block, meaning that they provide tokens to the network in order to help securing it. The term "stake" comes from the fact that a node loses a portion or all of its staked tokens if it has been found to have malicious intents against the network. Nodes are effectively putting their tokens at stake in order to receive a reward. Again, the more coins are staked by a node, the more chance it has to be picked for adding the next block and farming the rewards. Most PoS protocols also introduce coin age as a contributing factor. A node that has been holding its coins for a longer time has more chance to add its block.

• The pros for PoS are that it consumes much less energy compared to PoW and that regulating the network requires an on-chain resource. If an entity wants control over the blockchain, it has to buy in large amounts of the currency. Not only do you risk losing all of your staked coins if you try to attack the network, you also risk devaluating the currency you are holding yourself. A currency that suffered a successful attack typically drops in value and people will not be likely to accept it as a form of payment.
• A downside of PoS is that it can encourage hoarding. People with lots of money can stake more and collect more rewards. Meanwhile, people that spend more and drive the economy are not getting any rewards for doing so -> the rich get richer.

Some PoS coins are: Ethereum 2.0 (ETH), Cardano (ADA), Polkadot (DOT), Cosmos (ATOM), Tezos (XTZ)

Some variants:

• Delegated Proof of Stake (DPoS): With DPoS, stakeholders don't directly verify the block transactions. Instead, they vote for a node that represents them, called a delegate. The delegates then carry out the block proposition and verification as usual. DPoS introduces some elements of centralization, but in a dynamic and democratic manner. Used by EOS, BitShares (BTS) and Steem (STEEM).
• Pure Proof of Stake (PPoS): This protocol was proposed by Algorand (ALGO) to solve the blockchain trilemma between security, scalability and decentralization. Every token that is held in a wallet is automatically up for stake. Each round, a number of randomly chosen tokens are selected to validate the block and get a reward.
• Proof of Activity: This is a hybrid mechanism that combines PoW with PoS. First a block is mined with PoW. The mined block only contains the miner address and a random seed. This seed is used to select a group of stakeholders that sign the block with the actual transactions in a PoS manner. Used by Decred (DCR) .
• Proof of Stake Velocity (PoSV): This mechanism was introduced by Reddcoin (RDD) to somewhat counteract the hoarding problem that affects normal PoS. Instead of the stake weight increasing linearly with coin age, the weight increases logarithmically with time. So newly staked coins gain weights quickly and the weights of older coins gradually reach a maximum. This should encourage people to more actively spend their crypto. PoSV is actually part of a larger category of consensus mechanisms that reward their validators based on how actively they use the network, called Proof of Importance (PoI). A prime example of this is NEM (XEM).

Proof of Authority (PoA)

With PoA, the resource in question is the reputation of the node, linked to an identity. The better the reputation of a node, the higher the level of authority it has within the network. Nodes have an incentive to act truthfully since they can lose their reputation, which can take a long time and a lot of secondary resources to obtain, if they are caught manipulating the network. And most importantly, the bad reputation will be linked to the identity of the person or organization behind the node. A good PoA chain should have a universal set of rules for how to obtain the right to secure the network.

The main application of PoA is traditionally for private networks, like some applications on Microsoft Azure. Examples of public cryptocurrency blockchains are POA Network (POA) and VeChain (VET) (and these are the only ones for as far as I know).

• Pros: Very fast, low-cost and economical. It is a very simple mechanism since it typically runs on a limited number of nodes with only reputation as a relevant parameter. At the same time, this also leads to the most apparent downsides of PoA.
• Cons: It more or less defeats the purpose of decentralization. All nodes receive their authoritarian status from the foundation that built the chain. Besides this, history learns us that people are often more than happy to trade in their reputation for profit.

Proof of Space (PoS*)

PoS* is similar to PoW, but instead of work memory it uses storage memory. Harddrives can be read very fast, they are relatively cheap and are broadly available, which is why it is proposed as a better alternative to PoW. A node in the network can add its block by proving that it has sufficient storage available to verify transactions. The specifics of how this happens can vary a lot so I'll list a few variants below.

• Proof of Storage/retrievability: A verifier sends a file to a prover, who then stores the file. To add the next block, the prover has to prove to the verifier that he really stored the file. Used by Permacoin, although with some alterations (Maybe it has been renamed by now or it just died somewhere in 2014).
• Proof of Capacity: This is a clever adaptation of PoW. First, nodes pre-calculate solutions to a cryptographic puzzle, which are then stored. Later on, nodes can "mine" new blocks by reading through their stored solutions and check if they solve the puzzle for the current block. The advantage is that you have to do the computation only once and the actual mining is done on the hard drive. Used by Burstcoin (BURST).
• Proof of space-time: Unfortunately, this has nothing to do with Einsteins theory of general relativity. In addition to proving that a node has a certain amount of storage available, it also has to prove that the space has remained unchanged for a certain amount of time. Used by Filecoin (FIL) and Chia (XCH).
• Proof of Acces: With this protocol, nodes have to prove that they stored a randomly selecetd block of the blockchain history on their hard drives. Then, all nodes that have the block in question on their hard drive will compete against each other with the usual PoW algorithm. This allows a very dynamic blockchain structure since each new block is linked to the previous block as well as this randomly selected "history" block, effectively creating a graph structure sometimes referred to as a "blockweave". Used by Arweave (AR).
• and many more...

Note: It seems that the terminology within this subject isn't exactly standardized so the names Proof of Space/Storage/Capacity are often used interchangeably.

• Pros: No need for power-intensive hardware like PoW has. PoS* also sets a lower entry barrier than PoS since this kind of hardware is relatively cheap as well.
• Cons: More accessible hardware also makes it easier to control 51% of the total network.

Proof of Proof (PoP)

I wanted to include this one just to illustrate how creative one can get with security protocols. With PoP, any blockchain that has insufficient active nodes to properly secure itself could inherit security from another blockchain instead. Instead of carrying out PoW or PoS themselves, miners can publish reference data from a PoP chain onto any other chain that is considered to be "more safe". In the case of an attack on the PoP chain, miners can compare the information on both chains and notice that there are inconsistencies. VeriBlock (VBK), the pioneer of PoP, has proposed to help securing Bitcoin SV (BSV) and Ethereum Classic (ETC) this way, since these chains regularly suffer from 51% attacks.

• Pros: PoP could help blockchains with lacking security infrastrucure by recycling the resources from bigger, more secure chains like Bitcoin.
• Cons: The problem is basically transferred to the miners that do the PoP verification. You would have to trust them to publish legitimate data on the bigger chain.

A variant of PoW, called Delayed Proof of Work (DPoW), is quite similar to this: A PoW blockchain profits from the additional security of a secondary chain within the same network. In order to take over the primary blockchain, both chains would have to be compromised. But unlike PoP, DPoW doesn't require a "third-party" chain to operate. Used by Komodo (KMD).

Federated Byzantine Agreement (FBA)

Byzantine failure is a key concept for any consensus protocol and is often explained with an allegory (a word that I just learned myself, basically an analogy) about generals of the Byzantine empire. The generals, who are physically separated, have two options: attack or retreat. Each of them has to cast a vote and have it sent to the other generals by a messenger. The generals are then expected to act based on which option has received the most votes. The process is complicated however, by one or more generals who are traitors to the empire and seek to disrupt the operation. As an example they can vote to attack but instead retreat, leaving the attackers at a disadvantage. Or they can send a vote to attack to some generals and a vote to retreat to the others. Another complication is that the messengers could fail to deliver the votes or even falsify them. All of these are examples of Byzantine faults: An incident where the overall state of the system does not appear to be the same for all participants. Byzantine failure occurs when the system is unable to function properly because of too much faults.

In this analogy, the generals represent the nodes in our network who also have to options: To add the proposed block to the chain or not. As you may have noticed it can be difficult to determine what is the truth in a trustless, decentralized system. Yet a proper blockchain should be resistent to Byzantine failures up to a certain level.

An FBA protocol introduces a specific set of rules that each node/general has to follow in order to mitigate the impact that a bad subset of nodes can have on the system. This can be done by having multiple voting rounds where nodes have to convince other nodes to vote for a proposed block. To come to an agreement, each node has its own quorum slice, which is basically the subset of nodes needed to convince this one particular node of a statement. With the quorum slices of different nodes overlapping, this allows for a very dynamic structure that hopefully converges to one single statement being correct. However, the increased complexity can also lead to some nodes being "stuck" without coming to a final conclusion. Even then, the system still utilizes subprotocols to guarantee it can operate despite a number of malicious, failed or stuck nodes. FBA mechanisms are typically characterized by a high level of mathematical rigor.

Within the cryptocurrency space, the FBA protocol was pioneered by Ripple (XRP) and later on adaptations were made by Stellar (XLM). The main difference between the two is that XRP uses pre-selected nodes as validators while with XLM anyone can become a validator and choose which other nodes they trust. If you are looking for a detailed explanation of FBA protocols, the Stellar whitepaper definitely has that. (I actually read through the entire 30-page thing and I must say its a good read if you're familiar with university-level mathematics and/or set theory. Otherwise I'd recommend skipping chapters 3 to 6 because it's damn heavy literature, and that's probably an understatement). Furthermore, NEO uses a Delegated Byzantine Fault Tolerance mechanism, which adds the previously mentioned concept of delegates.

• Pros: Very fast, cheap and doesn't require a lot of power usage.
• Cons: Lack of an unfalsifiable resource. You can theoretically make as many nodes as you like, which forces validators to reintroduce the concept of trust and consequentially, also some level of centralization.

End note

There are probably many more consensus mechanism than I listed here, but I think I covered most of those that have applications in the biggest cryptocurrencies. Once again, feel free to comment any suggestions. Another good source for general information about consensus protocols can be found here. If you need more info on a specific consensus algorithm, I'd suggest looking up the whitepapers of the coins I've mentioned above. I hope some people found this useful or now at least have a general idea of what some consensus protocols do. And congrats if you actually made it this far. Have a good one.

EDIT: r/ec265 linked a useful infographic that could act as a tl;dr here.