The great guide to consensus algorithms

Consensus algorithms in decentralized networks are not limited to the choice between Proof of work and Proof of stake. We will first look at the most common varieties of Proof of work and Proof of stake, and then we will delve further into the subject. Consensus algorithms are such a deep topic, like the rabbit hole in the Alice fairy tale. So we will only look at them in general terms.

Consensus algorithms make sure that all participants in the decentralized network see and interpret the same transactions in the same way. In addition, consensus algorithms protect the system from malicious actions, verify the data entered and help avoid double-spending. Simply put, they are responsible for making sure that the decentralized network operates error-free.

## Where it all started: the Proof of work algorithm

The Proof of work algorithm was the first among consensus algorithms. The algorithm’s name reveals its essence, as to validate transactions, a system participant solves a mathematical puzzle to calculate a hash, and then publicly demonstrates the proof of work done. The first miner to discover the solution to the mathematical puzzle is entitled to enter the transactions into the block and affix their signature to the block. Such a signature entitles them to receive a reward in cryptocurrencies from the network’s algorithm. In general terms, this is how all Proof of work algorithms work, starting with Bitcoin (BTC).

As the mathematical puzzle is continually becoming more complex according to a given algorithm, miners who use Proof of work need to continually build up their overall processing power. The mathematical problem becomes too complex to be solved by a single miner. Therefore, miners join together to form pools. The pool divides the problem among all participants, accepting partial solutions from them and paying a proportional share of the reward for the solved block signature in return.

## More modern modifications of Proof of work

The Proof of work algorithm is not limited to the mechanism described above.

There are more modern variations of Proof of work. For example, X11, which is used by the Dash cryptocurrency. X11 is so called because it consists of 11 hashing algorithms at once:

• Blake.
• Blue Midnight Wish (BMW).
• GrÃ¸stl.
• JH.
• Keccak.
• Skein.
• Luffa.
• CubeHash.
• SHAvite-3.
• SIMD.
• ECHO.

This is the main difference between Dash cryptocurrency and Litecoin cryptocurrency, which uses one encryption algorithm, Scrypt, as well as Bitcoin, which uses one encryption algorithm, SHA-256. The X13 and X17 algorithms use a similar principle. They use, respectively, 13 and 17 hashing algorithms. Also some modern modifications of Proof of work use the Dagger Hashimoto cryptographic algorithm. Its main feature is high memory requirements. This allows to make the network more decentralized, because mining becomes possible only on PCs, not on ASICs.

## The Proof of capacity algorithm

The Proof of capacity algorithm is much like the Proof of work algorithm.

The same way a mathematical puzzle is solved, connected with the search of hash function values. Proof of capacity means that the space on the hard disk or other storage medium is used to search the values. Therefore, this consensus algorithm is also called Proof-of-space (PoSpace). It is used by poorly distributed cryptocurrencies Burstcoin, Chia and SpaceMint. It should be considered only as a mathematical curiosity. There are also algorithms with important applied value, the main one being Proof of stake and its variants.

## The main characteristics of the Proof of stake algorithm

Proof of stake uses coins that are already stored in users’ wallets to validate transactions. As with Proof of work, transactions are bundled into blocks that are sealed with a final signature. Network members can also earn rewards from the network algorithm for confirming transactions. In some cases, the Proof of stake algorithm rewards network participants with transaction fees; they go to those who validate the block.

In the simplest version of Proof of stake, the chance of confirming a block depends on the percentage of coins in the user’s wallet to the total number of issues. More common now are Proof of stake variants, in which validators (network members with block validation rights) are chosen at random among the top users with the most coins in their wallets. Such PoS variants allow to exclude malicious collusion of network participants.

## Delegated Proof-of-Stake algorithm

Cosmos, Tron, EOS and a number of other cryptocurrencies use the Delegated Proof-of-Stake algorithm. It is a variation of Proof-of-Stake that uses voting and delegation mechanisms to select network validators. Recall that validators are nodes that have the authority to validate transactions. The validators then agree among themselves on which transactions to discard and which to include in the block. To eliminate the possibility of malicious behavior by validators, they bail them out in network coins. If a validator violates the rules of the network, the network confiscates the coins it has pledged. To do this, some Delegated Proof-of-Stake algorithms rely on “witnesses,” or “fishermen,” to check validators.

## Differences of the DAG algorithm

DAG is short for Directed Acyclic Graph. Strictly speaking, it is not a blockchain consensus algorithm, but another distributed ledger. The best known cryptocurrency that uses this algorithm to validate transactions is called Iota.

Each DAG transaction communicates directly with other transactions without combining them into blocks. Each node that creates a new transaction creates a connection to the two nodes that initiated the transactions before it.  If all is well, the new transaction validates the two old transactions. After that, the new transaction becomes the old transaction and queues itself for transaction confirmation. Nodes are not allowed to validate their own transactions. Each user wishing to make a transaction confirms two of someone else’s transactions and thus the entire transaction history. Both without having to mine and without having to pay transaction fees. No time is wasted creating blocks, and as the number of network participants grows, the network bandwidth does not fall, but rather grows – as does the speed of transaction confirmation.

Directed means that the algorithm is unidirectional. The process always moves from old to new transactions. Acyclic – means the old transaction never comes back to verify new transactions, in other words it does not create loops. The last letter (G) is the “graph”, of transactions, payments, and connections, that is drawn when checking transactions in networks based on the DAG consensus algorithm.

## RPCA algorithm

The best known cryptocurrency using this algorithm is called Ripple. RPCA stands for Ripple Protocol Consensus Algorithm. All nodes constantly poll each other and vote after a certain interval to see which copy of the base is correct. With a sufficiently developed network of nodes, it is impossible to get a majority when voting because the attacker needs to gain a majority in the limited time between polls of the network. This eliminates the possibility that the attacker will be able to do a fork of the base in a limited amount of time. If the attacker clogs the network with garbage transactions, the RPCA algorithm will raise the fees for him in such a way that the rest of the network will not notice.

## The BFT algorithm

BFT (short for Byzantine Fault Tolerance) deserves attention if only because this consensus algorithm is used by such a new and promising cryptocurrency as TON coin. Transactions in this network are currently some of the fastest and cheapest. A more modern modification of this algorithm, Practical Byzantine Fault Tolerance (PBFT) allows consensus even if some nodes in the network do not respond or give wrong information. The nodes in the PBFT model are ordered and synchronized with each other. This mechanism helps each node maintain a view of the current state of the network among the nodes. Cross Fault Tolerance (XFT – simplified PBFT) finds application in small private networks. But Paxos and Raft cryptocurrencies use a modification of BFT called Crash Fault Tolerant (CFT). It is especially resistant to system failures.

## When DAG met BFT: the Aptos and Sui algorithm

New Cryptocurrencies: Aptos and Sui use an algorithm that combines DAG and BFT consensus algorithms. The infinite growth theorem of DAG is solved mathematically, with transaction verification relying on validators. This assumes that some of the validators do not work correctly or maliciously. Therefore, the validators pass transactions over several rounds, where valid transactions “make it to the final” and invalid ones are discarded. This process engages the BFT algorithm. In doing so, even the odds are leveled for even the slowest but most honest validators. Thus, DAG turns from chaos into a slender and symmetric structure with vertices, which are fixed, true transactions.

Theoretically, such an algorithm would achieve a network throughput that exceeds 100,000 transactions per second.

## What other consensus algorithms there are

We haven’t yet looked at the following algorithms, as they are used by little-known cryptocurrencies:

• Proof of Weight.
• Proof of Activity.
• Proof of Importance.
• Leased Proof of Stake.
• Proof of Burn.
• Proof of Participation.
• Proof of History.

However, they may be of considerable interest to those who are professionally engaged in cryptography.