I often like to say that if cryptocurrencies was a religion, then the consensus algorithm is its god. A cryptocurrency's consensus algorithm is core to its functionality. The consensus algorithm makes it work and because a cryptocurrency works, the network effect that builds around it gives it its value. Here's a categorization of the different consensus algorithms used by popular cryptocurrencies today.

Proof of Work/Proof of Stake

Proof of Work (PoW) is the very first cryptocurrency consensus algorithm. PoW was a breakthrough in many ways. The algorithm allowed anyone to join and leave the consensus process. There was no restriction on the number participants in the system and no restriction on the participants's identities. This enabled a high degree of flexibility and decentralization, perfect for a cryptocurrency like Bitcoin that was supposed to be owned and controlled by its users.

PoW also decentralized trust. Participants in the algorithm didn't need to trust that others would cooperate. Instead, Bitcoin baked in an incentive mechanism (block rewards) to simply build on the longest chain. You didn't need to trust that other nodes are not malicious, you just needed to trust that the longest chain must be the one that the majority accepted, because if it wasn't, then it wouldn't be the longest chain!

Participants in PoW needed to solve a mathematical problem in order to generate a block accepted by majority. The first one to solve the problem mines a block, adds to the longest chain, and earns a mining reward. Because it's a computational competition, PoW requires a tremendous amount of energy to run. And the more participants that are trying to mine a block, the more energy the whole system requires.

Proof of Stake (PoS) is similar to PoW except for the fact that participants "stake" their holdings in order to get a chance to mine a block. In PoS, participants still require computational power to participate, but the computational power is much less. Instead of using it to solve mathematical problems, participants only need to use computational power to prove how much they have at stake and a well designed random number generator will choose the winning participant.

At a high level, PoS seems to be way better than PoW since the economics of mining is internalized within the blockchain and isn't affected by outside factors like the availability and advancement of ASIC technology. It is also way more expensive to perform a 51% attack on a PoS system. In a PoW system, a 51% attack would require a large amount of CPU power, but once you execute the attack, you still have the CPU power. In a PoS system, a 51% attack would require purchasing a large amount of the network asset. Once you execute the attack, the value of that asset diminishes tremendously. However, it's not all sunshine and rainbows for PoS. There are many challenges to implementing a correct PoS algorithm since it's very easy to construct an algorithm that's susceptible to problems like the nothing at stake problem and long range attacks.

Delegated Proof of Stake

Delegated PoS (dPoS) has a high barrier of entry for consensus participants. Unlike PoS or PoW, not everyone can easily jump in and out of the consensus process. With dPoS, you need a large amount of staked assets to be able to act as a validator. Other, less wealthy users can still participate in the consensus process, but in an indirect manner by delegating their assets to dPoS participants that they trust.

The idea behind dPoS is that users with a large amount at stake are much less likely to attack the system given that they'd lose a large portion of their wealth if they did. As such, it's fair to allocate a disproportionately higher amount of trust to them in the consensus process. With less participants and more trust required, systems using dPoS can often be much faster than systems using PoW or PoS.

Byzantine Fault Tolerance

Byzantine Fault Tolerance (BFT) algorithms work through cooperation instead of competition. Instead of the scenario where participants work independently, racing to create blocks, participants in BFT algorithms work together to reach consensus on what the next block would look like. If the majority of participants agree on a block, then the block is added to the blockchain.

As such, these algorithms require participants to have a high degree of trust with their immediate peers. Malicious entities can break the consensus process by not agreeing to any new blocks, and if there are enough malicious entities, the consensus process breaks down and the blockchain would then be controlled by these entities. As such, participants in BFT algorithms assign trust to other nodes in the system, with each node keeping a list of highly trusted peers to work with.

The idea is that if there are any malicious entities, they'd quickly be blacklisted by the good participants in the system. This high trust requirement makes it very hard for most users to participate in the consensus process. Little information is known about any new validators and so the logical thing for existing participants to do is to ignore them.

Just like in dPoS, systems using BFT tend to have less consensus participants and a high trust requirement. As such, these systems are incredibly performant compared to PoW or PoS.

DAG

Directed Acyclic Graph or DAG algorithms is a nascent class of consensus algorithms that often boast of infinite scalability and free transactions. The algorithm uses a Directed Acyclic Graph (DAG) data structure instead of the single-threaded blockchain data structure that the other algorithms use.

It's much faster to append to DAGs than single-threaded blockchains since DAGs technically have infinite threads and there are no resource contention issues that arise in single-threaded, multi-participant systems. The big caveat is that DAG systems are very expensive to maintain since its much much harder to efficiently maintain and validate a DAG data structure than a single-threaded blockchain. This isn't surprising given how much more complex DAGs are.

As such, DAG systems tend to be quite centralized. Consensus participants need incredibly beefy machines that can maintain the DAG. There are also few incentives to run these beefy machines even though the cost is quite high as DAGs aren't really well suited to the traditional mining rewards paradigm.

Many DAG systems also tend to be similar to BFT systems where consensus participants are not competing with others to maintain consensus but are really just coordinating with others. This leaves the system vulnerable to malicious nodes unless there are adequate mechanisms put in place to defend against them. Nano, for example, utilizes a dPoS like voting mechanism where participants with a higher amount of XRB have more power in the consensus process and other non-consensus participants can delegate their XRB to consensus participants they trust.

Summary

PoS is probably the most trustless and decentralized consensus algorithm out there. However, there is always a performance trade-off the more trustless decentralization there is. This is why PoS systems are usually less performant than BFT/dPoS/DAG systems.

Cryptocurrencies achieve higher performance by sacrificing on trustless decentralization and users should always be aware of the tradeoffs inherent to the systems they are using.

More reading

• A Hitchhiker’s Guide to Consensus Algorithms
• What is NEO?