Consensus algorithms are the bedrock upon which distributed systems, including blockchains, are built. These algorithms are protocols that every node in a blockchain network adheres to in order to achieve agreement on a shared state. This consistent agreement, otherwise referred to as State Machine Replication (SMR), guarantees a number of fundamental properties of blockchain: e.g. an assurance of eventually reaching an agreement, and ensuring that no node who follows the algorithm can diverge from the common state.

Note: Although consensus algorithms allow nodes to agree on a shared state, a more accurate representation might be that these algorithms enable nodes to agree on a common value. Starting from a series of values and an initial shared state, a new state is formed with each run of the consensus algorithm. In the realm of blockchains, the agreed value is the 'block'.

In the context of blockchains, an additional challenge emerges: maintaining consensus integrity in the face of unpredictable node behavior. This challenge gives rise to a class of consensus algorithms known as Byzantine Fault Tolerant (BFT) algorithms, a concept that recurs frequently in blockchain discussions.

The choice of a consensus algorithm has a profound impact on the characteristics of a blockchain. It influences factors such as scalability, decentralization, governance, and transaction finality. As such, consensus algorithms continue to be a hot topic in the Web3 ecosystem, even as development of new algorithms has quietened recently.

This apparent slowing in innovation can be attributed to a sense of performance saturation in existing blockchains, and a shift of focus towards Layer 2 solutions, which augment the scalability of baselayer blockchains.

Nonetheless, the security and reliability of blockchain systems remain firmly anchored in the chosen consensus algorithm. We will explore some of the widely adopted consensus algorithms in blockchain to help demystify the engines that power the platforms we regularly engage with.

Proof of Work (PoW)

At the core of the original blockchain implementation, Bitcoin, was the utilization of a consensus algorithm called Proof of Work (PoW). In essence, the idea behind PoW is that a collective group of nodes (computer systems) can agree on a common value, provided one node is randomly selected to propose this value and incentivized to ensure its correctness. This random selection process is executed in a rather unique way, by having the nodes compete to solve a mathematical challenge. This challenge is not something you can strategize or calculate an answer to, it's purely a game of chance, like rolling dice. The more attempts a node makes, the higher its odds of solving the challenge and 'winning the race'. This process of attempting to solve the challenge is referred to as 'mining'.

However, one problem that miners using PoW face is the possibility of two nodes solving the challenge simultaneously. In such a case, the system opts for a 'longest chain rule'. The nodes continue their work with the latest block they receive, and if they encounter a longer sequence of blocks, they switch to it, discarding the blocks from the shorter chain.

Because mining is computationally intensive and consumes a lot of resources, the successful node (or miner) is rewarded with cryptocurrency, as a form of compensation for their expended efforts.

Prominent examples of PoW blockchains include Bitcoin and its derivatives (Bitcoin Cash, Litecoin, etc.), Monero, and Ethereum Classic.

Security Considerations

The primary security requirement of a PoW system is that >50% of the overall computational power of the network is controlled by nodes that are following the rules. This is a critical assumption as it ensures that even if some nodes are acting maliciously, the honest ones will always eventually produce more blocks, leading to the discarding of blocks created by dishonest nodes.

However, what happens if the dishonest nodes control more than 50% of the network's power? They could potentially manipulate the blockchain by producing a sequence of blocks with certain transactions (i.e., spending some cryptocurrency), then creating a new, longer sequence of blocks without those transactions. This would effectively enable them to 'double spend' their cryptocurrency while leaving the transaction recipient empty-handed.

Another consequence of this scenario is network censorship, where the dishonest nodes, being able to produce a longer chain, control what transactions are added to the blocks and can thus arbitrarily censor transactions.

Figure 1: A second, longer chain produced to double spend the amount of cryptocurrency spent by t₁

Selfish Mining

Selfish mining represents another potential security vulnerability within proof of work blockchain networks. In this scenario, a node that successfully solves the mathematical challenge keeps the newly created block to itself, while already starting to work on the next block. This provides an advantage, as they're aware of one block more than the other nodes.

If the node manages to find subsequent blocks based on the one they have kept hidden, they can always share a longer chain segment than other nodes. Consequently, their blocks become the canonical ones. This enables the malicious miner to:

1. Gain all the mining rewards.
2. Censor any transactions they deem undesirable.

Selfish mining attacks start to become significantly probable when a node or a group of nodes control at least 28% of the network's computational power. Hence, this figure is often cited as the maximum security threshold for proof of work blockchains.

Network Partition

Another risk to blockchain systems, irrespective of the consensus algorithm utilized, is the potential for the network to be split into two or more partitions due to reachability issues. This could occur, for instance, due to technical disruptions or malicious activity.

Consensus algorithms generally operate on the implicit assumption that nodes can communicate with each other. Proof of work blockchains do not inherently have any protections against such attacks. Rather, they rely on the economic incentive of miners to quickly mine and share new blocks to obtain their associated rewards.

A network partition can result in the creation of two parallel chains, in an event known as a fork. Once the partition is resolved and the nodes are unified, one of the two chains will inevitably be discarded.

The detection of a fork is essential to prevent misplaced trust in uncertain information, and to pause activity until the problem is resolved. Although this scenario can be damaging, instigating partitions in large blockchain systems, such as Bitcoin, would require the cooperation of diverse entities, including nationwide institutions and telecom operators.

However, the inherent complexity and decentralization of the internet do provide some assurance that alternative pathways and routes can be found, mitigating the risk of a complete partition.

Figure 2: A network partitioned in two by cutting connections between the two sets of nodes.

Proof of Stake (PoS)

Proof of Stake represents another class of consensus algorithms, often associated with the second generation of blockchain networks. Unlike Proof of Work, which requires proof that computational work has been carried out to solve a mathematical challenge, Proof of Stake operates differently:

"Stake" refers to the vested interest a node (called a validator in PoS systems, rather than a miner) has in actively and correctly participating in the consensus process. This is often demonstrated by locking a specific amount of cryptocurrency, which is not used for any other purpose other than demonstrating ownership.

"Proof" signifies the evidence that the block producer is indeed holding a staked amount. Proof of Stake determines how the set of validators is defined, but the actual algorithm executed by the nodes can vary significantly across different blockchains. Nevertheless, PoS algorithms generally strive to offer the following enhancements over Proof of Work:

• Power Efficiency: The randomness involved in PoW's solution process consumes a substantial amount of energy. This isn't efficient, and Proof of Stake aims to reduce this energy consumption by replacing the PoW process with the validation of signatures by staking validators.
• General-Purpose Hardware: PoW requires dedicated, highly efficient hardware, as the probability of mining a block (and receiving the associated reward) increases with more efficient hardware. This results in a continuous race to acquire and replace hardware with the latest model, rendering general-purpose machines inefficient. PoS, on the other hand, only requires standard servers for maintaining network connections and signing data when necessary.
• Faster Finality: In PoW, a block is considered valid only after nodes produce new blocks on top of it, meaning users need to wait a considerable amount of time to confirm a transaction is definitively included in the system state. In contrast, PoS either offers immediate finality as soon as blocks are disseminated across the network or a significantly low revert probability, necessitating only slightly longer wait times for highly sensitive use cases.
• Light Clients: While PoW requires constant contact with various parts of the network to securely determine the correct chain, PoS allows for the validation of block attestations (signatures) to confirm information's authenticity. This makes light clients less network-demanding and easier to develop in any context.

These improvements certainly make Proof of Stake appealing from an operational perspective. However, it's worth noting that the concept of using cryptocurrency stakes instead of computational power as the consensus mechanism remains a topic of ongoing debate within the realm of decentralization and governance.

Proof of Stake (PoS) opens up possibilities to integrate established Byzantine Fault Tolerance (BFT) consensus algorithms, typically designed for a known set of nodes. Here are some examples:

• Tendermint: An influential consensus algorithm because of its practicality and the comprehensive Go SDK, which includes an out-of-the-box consensus solution. Each round involves a proposer (selected in a round-robin fashion) proposing a block that then goes through two voting stages. A block is finalized when the second voting phase achieves a quorum of at least 2/3 of the total staked amount. Validators can also vote to skip a round if a proposer fails to propose on time.

• Hotstuff: Hotstuff enhances performance by optimizing message complexity and creating a pipeline of consensus rounds, where payloads can contain messages from different phases of consecutive rounds. It provides a theoretical framework for analyzing the security and performance of other proposals, such as PBFT or Tendermint. Aptos blockchain utilizes Hotstuff for its BFT State Machine Replication.

Two prominent blockchain ecosystems that have implemented PoS on their main-nets are:

• Ethereum: Ethereum transitioned from Proof of Work to Proof of Stake with "The Merge", following a long-planned development process. Its massive set of validators is randomly divided into sub-committees to optimize message exchange. These committees last for a period, known as an epoch, before reshuffling. Each sub-committee is tasked with validating a series of blocks until validators representing 2/3 of the total staked ETH amount reach consensus. For an attacker to remove a block previously attested by validators holding 2/3 of the staked ETH, it would cost 1/3 of the total staked ETH.

• Polkadot: Polkadot, initiated by Ethereum co-founder Gavin Wood, has a distinctive architecture which allows different associated blockchains, or parachains, to communicate directly or through the main Polkadot chain. The main-net employs a Nominated Proof of Stake system, where validators are allotted slots to produce blocks via a lottery at the beginning of an epoch. A secondary algorithm is used to finalize all produced blocks. Account holders can delegate their cryptocurrency to validators to participate in PoS rewards.

Security Considerations

Slashing

Security considerations in Proof of Stake (PoS) consensus algorithms are intrinsically connected to the quantity of cryptocurrency staked by validators. Upon the detection of any evidence indicating misbehavior by a validator, the said evidence is employed to "slash" the stake of the validator in question. Slashing typically entails the partial or total confiscation of the validator's staked cryptocurrency, the extent of which is contingent upon the severity of the detected violation.

Ordinarily, the confiscated amount is divided into two halves: one part is allotted to the party that reported the violation, and the other part is completely burnt or destroyed. The latter action serves as a safeguard against potential abuse of the system, deterring instances where a violator and a reporter could potentially collude.

Figure 3: The stake of a malicious node is partially burnt and partially awarded to the reporter

Nothing At Stake

The "Nothing at Stake" problem arises in Proof of Stake (PoS) environments where the creation of a block candidate for the blockchain is relatively inexpensive, requiring merely the assembly of transactions and computation of a signature. Consequently, a malicious validator could potentially fabricate multiple valid blocks for an identical slot in the blockchain, thereby initiating a fork in the blockchain and facilitating the repeated expenditure of the same funds. This conundrum is typically resolved through a comprehensive slashing of the validator's entire staked amount, as this form of attack is among the most detrimental.

Figure 4: A malicious block proposer creates or votes for different block proposals in the same round trying to create different possible states in different nodes.

Security Threshold

The security threshold for Proof of Stake (PoS) consensus algorithms is rooted in the well-established guideline that a maximum of 33% of the nodes can be malicious without compromising the system. Each PoS algorithm interprets this boundary differently, depending on its specific design parameters. As such, specialized documentation is essential for understanding these variations. Furthermore, it's crucial to realize that this nominal constraint manifests in two dimensions: the number of nodes and the total amount of cryptocurrency at stake. Given that the distribution of the stake among validators is only indirectly correlated, these two aspects should be examined both separately and collectively.

Network Partition

Unlike Proof of Work (PoW) algorithms, PoS protocols might have the ability to detect network forks or partitions at the protocol level. This is because network-wide attestations are typically needed to affirm the acceptance or finality of blocks. In such situations, nodes could either halt the processing of new information or issue warnings that the network is proceeding with unconfirmed blocks. This allows users to stay informed of the ongoing situation without the need for additional countermeasures. Each algorithm employs different procedures to recover from such scenarios.

Proof of Authority

There's another category of consensus algorithms that deserves mention, which encompasses those that do not offer an economic incentive linked to the cryptocurrency issued by the blockchain. This does not mean that there are no economic incentives involved, but rather that they are not directly associated with the system's crypto-economics.

We can refer to this class of algorithms as Proof of Authority (PoA). The blocks issued under this algorithm carry proof—typically a signature—that they were issued by an authorized node. Initially, a set of authorized nodes is defined and embedded into the blockchain's initial state as the primary source of truth. Then, protocols may be implemented to allow modifications to the set of validators, such as additions, removals, or replacements. The clique algorithm integrated into the go-ethereum client is an example of a PoA mechanism with almost no Byzantine Fault Tolerance (BFT) guarantees. It has been used for some Ethereum testnets, like Rinkeby or Goerli.

We can also include in this category numerous algorithms stemming from academic research. These were developed starting in the early 1980s and focus on consensus in Byzantine scenarios, where the set of participating nodes is assumed to be fixed by design. Leslie Lamport first used the term "Byzantine" to refer to an arbitrary or potentially malicious node in his paper The Byzantine Generals Problem. In subsequent years, a significant contribution to practical and usable consensus algorithms came in the form of Practical Byzantine Fault Tolerance (PBFT). PBFT proposed a practically implementable BFT consensus algorithm and demonstrated its safety. The solution comprises two algorithms—one operating under normal conditions, involving a block proposer who lets its proposal be approved through three rounds of messages amongst all peers, and another to be used in case the block proposer behaves maliciously.

PBFT has inspired many BFT consensus algorithms, such as IBFT, a PBFT variant that incorporates a protocol for altering the validators set. It has also inspired many others suitable for Proof of Stake, such as Tendermint. Finally, PBFT serves as a reference point for comparison when discussing message complexity and the number of rounds in a single consensus instance.

Security Considerations

Malicious Leader

In consensus algorithms that utilize a leader-based mechanism, the primary security issue lies in addressing the potential presence of a malicious leader. Such a leader, during their designated term, could disseminate disparate blocks throughout the network or cease producing them altogether. While clique does not offer resilience in such situations, most other algorithms typically incorporate a voting-based protocol. This allows other nodes to bypass the malicious leader and maintain the algorithm's functionality. This concern is shared with Proof of Stake consensus algorithms, where a change in leadership is also accompanied by a penalty in the form of slashing.

Figure 5: A malicious round leader spreads different blocks relying on the trust other nodes have in it.

Other Solutions

Within the expansive Web3 ecosystem, numerous consensus proposals can be categorized under the three previously listed groups. However, certain novel or distinctive approaches merit specific mention.

Proof of History

The Solana blockchain operates on the Proof of History mechanism, where hashes of data and timestamps enable pre-ordering of messages prior to the execution of an optimized, stake-based variant of PBFT. This combination of a "pre-consensus" timestamping system, a highly parallelizable execution engine, and an efficient gossip protocol, amplifies Solana's transaction throughput to a degree that it more closely resembles a constant operation stream rather than a block-based system.

Proof of Elapsed Time

The Proof of Elapsed Time is a consensus algorithm, notably implemented by Hyperledger Sawtooth, which closely mirrors the mechanics of Proof of Work. However, the mining process is supplanted by the proof that a node waited for a specific period in a trusted execution environment, not controlled by the miner, before creating a new block. While a full BFT implementation is lacking, the primary concern centers around the trust in the security of the Trusted Execution Environments offered by major CPU vendors.

Conclusion

This article presents an overview of key consensus algorithms, concentrating on their core characteristics and underscoring the major security properties and challenges to consider in their implementation and use. Even though algorithms themselves can be deeply understood — with BFT guarantees serving as a bulwark against local faulty behaviors — implementation and design specifics can invariably present novel security challenges. Specifically, we observed how the balance among parties, such as computing power (PoW), amount of staked currency (PoS), or simply access to a consortium of members (PoA), directly impacts the security of blockchain design by shaping the assumptions on which their respective consensus algorithms are based.