Chapter 1 The Concept and Role of Consensus Mechanisms

1.1 Concept: The Core Rules for the Normal Operation of Distributed Ledgers

Since most cryptocurrencies adopt a decentralized blockchain design, with nodes being dispersed and parallel, it is necessary to design a system to maintain the order and fairness of the system's operation, unify the version of the blockchain, reward users who provide resources to maintain the blockchain, and punish malicious actors. Such a system must rely on some method to prove who has obtained the right to package a blockchain (or bookkeeping rights) and can receive rewards for packaging that block; or who intends to cause harm and will receive certain penalties. This is the consensus mechanism.

1.2 Role: Solving Trust Issues, Determining the Generation and Maintenance of New Blocks

The reason the consensus mechanism occupies a core position in blockchain technology is that it establishes a set of rules from the perspective of cryptographic technologies such as asymmetric encryption and timestamps. All participants and their modes of participation must adhere to these rules, which are transparent and cannot be arbitrarily modified. Therefore, without the endorsement of a third-party authority, it can mobilize all nodes in the network to jointly supervise and record all transaction situations, publishing them in the form of code, effectively achieving the transfer of value information. It solves, or more accurately, greatly improves the trust issue between two unrelated, mutually distrustful strangers. After all, trusting an objective technology is less risky than trusting a subjective person.

On the other hand, in blockchain systems, due to the high network latency in peer-to-peer networks, there may be differences in the order of transactions observed by different nodes. Therefore, the consensus mechanism can reach a consensus on the order of transactions that occurred within a short period, determining who is responsible for generating new blocks and maintaining the effective unity of the blockchain.

1.3 Mainstream Models of Consensus Algorithms

Blockchain systems are built on P2P networks, and the entire set of nodes can be denoted as PP, generally divided into ordinary nodes that produce data or transactions, and a set of "miner" nodes (denoted as M) responsible for verifying, packaging, and updating the data or transactions generated by ordinary nodes. These two types of nodes may overlap; miner nodes usually participate in the consensus competition process as a whole. In specific algorithms, certain representative nodes may also be elected to participate in the consensus process and compete for bookkeeping rights on their behalf. The set of these representative nodes is denoted as D; the bookkeeping nodes selected through the consensus process are denoted as A. The consensus process is executed repeatedly in rounds, with each round generally reselecting the bookkeeping nodes for that round. The core of the consensus process consists of two parts: "leader election" and "bookkeeping." In the specific operational process, each round can be divided into four stages: leader election, block generation, data validation, and chain updating (i.e., bookkeeping). As shown in Figure 1, the input of the consensus process is the transactions or data generated and verified by data nodes, while the output is the packaged data block and the updated blockchain. These four stages are executed in a cyclical manner, with a new block generated in each round.

Figure 1 Basic Model of Blockchain Consensus Process

Source: Yuan Yong, Ni Xiaochun, Zeng Shuai, Wang Feiyue, "Current Status and Prospects of Blockchain Consensus Algorithm Development"

>Stage 1: Leader Election

Leader election is the core of the consensus process, which is the process of selecting bookkeeping nodes AA from the entire set of miner nodes MM: we can represent the leader election process using the formula f(M)→f(M)→ AA, where the function f represents the specific implementation of the consensus algorithm. Generally speaking, |A|=1, meaning that a unique miner node is ultimately chosen for bookkeeping.

>Stage 2: Block Generation

The bookkeeping node selected in the first stage packages the transactions or data generated by all nodes PP during the current time period into a block according to specific strategies and broadcasts the newly generated block to all miner nodes MM or their representative nodes D. These transactions or data are usually sorted based on various factors such as block capacity, transaction fees, and transaction waiting times before being sequentially packaged into the new block. The block generation strategy is a key factor in the performance of the blockchain system and is also a concentrated reflection of miners' strategic behaviors such as greedy transaction packaging and selfish mining.

>Stage 3: Validation

After receiving the broadcast of the new block, miner nodes MM or representative nodes DD will verify the correctness and rationality of the transactions or data encapsulated in the block. If the new block is recognized by the majority of validating/representative nodes, it will be updated as the next block in the blockchain.

>Stage 4: Chain Updating

The bookkeeping node adds the new block to the main chain, forming a complete and longer chain from the genesis block to the latest block. If there are multiple forked chains in the main chain, one appropriate branch must be selected as the main chain according to the main chain identification criteria specified by the consensus algorithm.

Chapter 2 The Origin of Consensus Mechanisms

2.1 The Two Generals Problem and the Byzantine Generals Problem

2.1.1 The Two Generals Problem

Figure 2 Illustration of the Two Generals Problem

Selected from Yuan Yong, Ni Xiaochun, Zeng Shuai, Wang Feiyue, "Current Status and Prospects of Blockchain Consensus Algorithm Development," Acta Automatica Sinica, 2018, 44(11): 2011-2022

As shown in the figure, the blue army branches 1 and 2 are stationed on either side of a slope and cannot communicate remotely, while the white army is stationed on the only path between the two armies. Suppose the white army is stronger than either of the blue army branches but not as strong as the two blue armies combined. If the blue armies need to coordinate a simultaneous attack, they must communicate with each other, but the white army, being in the middle, cannot confirm whether the blue army's messenger has genuinely delivered the attack signal to the other side, and we will not consider the possibility of information being tampered with for now. In this case, due to the inability to achieve complete confirmation among each other, they ultimately cannot reach effective consensus, forming the "Two Generals Paradox."

2.1.2 The Byzantine Generals Problem

Figure 3 Illustration of the Byzantine Generals Problem

Due to the vast territory of the Byzantine Roman Empire at that time, in order to achieve better defense, armies were stationed around the empire, with each army being far apart and relying on messengers to convey messages. During wartime, all generals must reach a consensus or decide by majority whether to attack the enemy camp. However, since it relies entirely on humans, if there are generals who rebel or messengers who convey incorrect information, how can we ensure that loyal generals reach a consensus without being influenced by traitors? Thus, the Byzantine problem arose.

Both the Two Generals Problem and the Byzantine Generals Problem illustrate a common issue: achieving consensus and coordinating actions is very difficult in the face of unreliable information exchange. The Byzantine Generals Problem is more like a generalization of the "Two Generals Paradox."

From the perspective of computer networks, both the Two Generals Problem and the Byzantine Problem are common topics in computer networking courses: there is a possibility of failure in direct communication between two nodes on the network, so the TCP protocol cannot guarantee that two terminal networks will maintain a 100% consistent state throughout. However, the consensus mechanism can use economic incentives and other methods to reduce this uncertainty to a level acceptable to most people.

It is precisely because of problems like the Two Generals Problem and the Byzantine Problem that the necessity for the development of consensus mechanisms began to emerge.

2.2 The Development History of Consensus Mechanisms

2.2.1 Classification of Consensus Mechanisms

Due to the different requirements for information recording and block generation across various blockchain project types, and with the continuous improvement of consensus mechanisms as blockchain technology evolves, there are currently over 30 types of consensus mechanisms. These consensus mechanisms can be primarily divided into two categories based on their Byzantine fault tolerance capabilities: Byzantine fault-tolerant and non-Byzantine fault-tolerant systems.

Table 1 Classification of Consensus Mechanisms

Source: Yuan Yong, Ni Xiaochun, Zeng Shuai, Wang Feiyue, "Current Status and Prospects of Blockchain Consensus Algorithm Development"

2.2.2 Evolution of Consensus Mechanisms

> The Development of Consensus Algorithms

Based on the timeline of the introduction of consensus algorithms, we can see a relatively clear development of consensus algorithms.

Figure 4 Evolution of Consensus Algorithms

Source: Compiled from online resources

Figure 5 Historical Evolution of Blockchain Consensus Algorithms

Consensus algorithms lay the foundation for the consensus mechanisms of blockchain. Initially, the research on consensus algorithms was mainly conducted by computer scientists and professors to address spam issues or for academic discussions.

For example, in 1993, American computer scientist and Harvard professor Cynthia Dwork first proposed the idea of proof of work to solve the spam problem; in 1997, British cryptographer Adam Back independently proposed and formally published the proof of work mechanism for hash cash in 2002 to address spam issues; in 1999, Markus Jakobsson formally proposed the concept of "proof of work," laying the groundwork for Satoshi Nakamoto's design of the Bitcoin consensus mechanism.

Chapter 3 Common Consensus Mechanisms

Figure 6 Summary of Relatively Mainstream Consensus Mechanisms

Source: Hasib Anwar, "Consensus Algorithms: The Root of Blockchain Technology"

The above figure summarizes 14 relatively mainstream consensus mechanisms, including PoW (Proof of Work), PoS (Proof of Stake), DPoS (Delegated Proof of Stake), LPoS (Leased Proof of Stake), PoET (Proof of Elapsed Time), PBFT (Practical Byzantine Fault Tolerance), SBFT (Simple Byzantine Fault Tolerance), DBFT (Delegated Byzantine Fault Tolerance), DAG (Directed Acyclic Graph), Proof-of-Activity, Proof-of-Importance, Proof-of-Capacity, Proof-of-Burn, and Proof-of-Weight.

Next, we will mainly introduce and analyze the ten most mainstream consensus mechanisms currently in blockchain.

> POW

• Concept:

Proof of Work mechanism. It means proving the amount of work done by consuming a certain amount of computer time to confirm the work completed.

• Implementation Principle:

Figure 7 Principle of PoW Proof of Work

The PoW used by Bitcoin is based on the SHA-256 algorithm function, which is a hash algorithm in the family of cryptographic hash functions that outputs 256 bits:

Proof of Work output = SHA256(SHA256(block header));

if (Proof of Work output < target value), proof of work is completed;

if (Proof of Work output >= target value), change the random number, recursively adjust the logic of i, and continue to compare with the target value.

New difficulty value = old difficulty value * (time taken for the past 2016 blocks / 20160 minutes)

Target value = maximum target value / difficulty value

The maximum target value is a fixed number. If the time taken for the past 2016 blocks is less than 20160 minutes, this coefficient will be small, and the target value will be adjusted upward; conversely, the target value will be adjusted downward. Therefore, the difficulty of Bitcoin and block generation speed will be inversely proportional, adjusting the block generation speed appropriately.

• Representative Application: BTC, etc.

>POS

• Concept:

Proof of Stake. It is a mechanism for reaching consensus based on the stake held by individuals, where the more coins held and the longer they are held, the greater the probability of receiving rewards.

• Implementation Principle:

PoS implementation algorithm formula: hash(block_header) <= target * coinage

Coinage calculation formula: coinage = number of coins * remaining usage time of coins

Here, coinage represents the age of the coins, which means that the older the coinage, the easier it is to obtain the answer. The calculation of coinage is obtained by multiplying the number of coins owned by the remaining usage time of each coin, which also means that the more coins owned, the easier it is to obtain the answer. In this way, PoS solves the resource wastage problem in PoW, and since miners cannot own 51% of the entire network's coins, it also addresses the 51% attack issue.

• Representative Application: ETH, etc.

>DPoS

• Concept:

Delegated Proof of Stake. Investors holding coins elect super nodes through voting to operate the entire network, similar to a people's congress system.

• Implementation Principle:

The DPOS algorithm is divided into two parts: electing a group of block producers and scheduling production.

Election: Only permanent nodes with voting rights can be elected, and ultimately only the top N witnesses can be elected. These N individuals must receive more than 50% of the votes to be successfully elected; otherwise, this list will be re-elected at fixed time intervals.

Scheduling Production: Under normal circumstances, block producers take turns producing a block every 3 seconds. Assuming no producer misses their turn, the chain they produce will inevitably be the longest chain. When witnesses produce blocks, they need to produce a block every 2 seconds; if they exceed the specified time, the current witness will lose their production rights and pass them to the next person. Therefore, witnesses not only do not receive rewards but may also lose their witness status.

• Representative Application: EOS, etc.

>DPoW

• Concept:

Delayed Proof of Work. A new generation of consensus mechanism built on the foundations of PoB and DPoS. Miners use their computing power to prove their work through hash algorithms and obtain corresponding wood, which cannot be traded. Once a certain amount of wood is accumulated, they can go to a burning site to burn the wood. This balances computing power and mining rights.

• Implementation Principle:

In a DPoW-based blockchain, the rewards obtained by miners are no longer tokens but "wood" that can be burned. Miners use their computing power to prove their work through hash algorithms and obtain corresponding wood, which cannot be traded. Once a certain amount of wood is accumulated, they can go to a burning site to burn the wood. Through a set of algorithms, those who burn more wood or BP or a group of BPs can obtain the rights to produce blocks in the next event segment, and after successfully producing a block, they receive rewards (tokens). Since multiple people may burn wood within a time period, the probability of producing a block in the next time period is determined by the amount of wood burned. The more wood burned, the higher the probability of obtaining block production rights in the next time period.

Two Types of Nodes: Notary Nodes and Normal Nodes.

64 notary nodes are elected by the stakeholders of the dPoW blockchain and can add notarized blocks from the dPoW blockchain to the attached PoW blockchain. Once a block is added, its hash will be included in a Bitcoin transaction signed by 33 notary nodes, creating a dPow block record hashed to the Bitcoin blockchain. This record has been notarized by the majority of notary nodes in the network. To avoid conflicts among notary nodes in mining, which would reduce network efficiency, Komodo designed a mining method using a polling mechanism that operates in two modes. In the "No Notary" mode, all network nodes are allowed to participate in mining, similar to traditional PoW consensus mechanisms. In the "Notaries Active" mode, network notaries mine at a significantly reduced network difficulty rate. In "Notaries Active" mode, each notary is allowed to mine a block at their current difficulty, while other notary nodes must mine at 10 times the difficulty, and all normal nodes mine at 100 times the difficulty of notary nodes.

Figure 8 DPoW Workflow Without Notary Nodes

• Representative Application: Komodo, etc.

>PBFT

• Concept:

Practical Byzantine Fault Tolerance Algorithm. It reduces the algorithm's complexity from exponential to polynomial, making Byzantine fault tolerance algorithms feasible in practical system applications.

• Implementation Principle:

Figure 9 Principle of PBFT Algorithm

First, the client sends a request to the primary node to invoke a service operation, and then the primary node broadcasts the request to other replicas. All replicas execute the request and send the results back to the client. The client needs to wait for f+1 different replica nodes to return the same result as the final result of the entire operation.

Two conditions must be met: 1. All nodes must be deterministic, meaning that the result of the operation must be the same under the same state and parameters. 2. All nodes must start executing from the same state. Under these two conditions, even if there are faulty replica nodes, the PBFT algorithm achieves a consensus on the total order of requests executed by all non-faulty replica nodes, ensuring safety.

• Representative Application: Tendermint Consensus, etc.

>DBFT

• Concept:

Delegated Byzantine Fault Tolerance. An improved Byzantine fault tolerance algorithm that can be applied to blockchain systems. This system consists of nodes, delegates (who can approve blocks), and speakers (who propose the next block). It is a consensus algorithm implemented within the NEO blockchain that guarantees fault tolerance.

• Implementation Principle:

In this mechanism, there are two participants: "bookkeeping nodes" that specialize in bookkeeping and ordinary users in the system.

Ordinary users vote to decide bookkeeping nodes based on the proportion of their holdings. When consensus is needed, a speaker is randomly selected from these bookkeeping nodes to propose a plan, and then other bookkeeping nodes express their opinions based on the Byzantine fault tolerance algorithm, following the principle of majority rule. If more than 66% of the nodes agree with the speaker's proposal, consensus is reached; otherwise, a new speaker is selected, and the voting process is repeated.

• Representative Application: Neo, etc.

>PoA

• Concept:

Proof of Authority. It is certified by some recognized accounts, which are called "validators." Validators run software that supports placing transactions in blocks.

• Implementation Principle:

Three Conditions:

1. Identity must be formally verified on-chain, and information can be cross-verified in publicly available domains;

2. Their qualifications must be difficult to obtain, making the rights to the validated blocks sufficiently precious; 3. The establishment of authoritative checks and procedures must be completely unified.

Using PoA, every individual has the right to become a validator, so there is an incentive to maintain the validator position once obtained. By attaching a reputation to identity, validators are encouraged to maintain the transaction process. Validators do not want to gain a negative reputation, as this would cause them to lose their hard-won validator status.

• Representative Application: VeChain, etc.

>DAG

• Concept:

Directed Acyclic Graph. In a DAG, each new unit added not only joins the long chain of blocks but also connects to all previous blocks, verifying each new unit and confirming its parent unit and the parent unit's parent unit, gradually reaching the genesis unit and including the hash of its parent unit in its own unit. Over time, all transaction blocks connect to form a graph structure.

• Implementation Principle:

In a DAG network, each node can be both a trader and a validator, as the transaction processing in DAG is completed by the transaction nodes themselves. Taking IOTA as an example, IOTA's Tangle ledger ensures high-speed transaction processing without requiring transaction fees. However, this does not mean that transactions are free; in this ledger, initiating each transaction requires first validating two random transactions and pointing the initiated transaction to these two transactions. Thus, the responsibilities that miners bear on the blockchain are distributed among all traders. This method of processing transactions in DAG can be referred to as asynchronous processing mode.

Figure 10 Differences Between Traditional Blockchain Structure and DAG Structure

• Representative Application: IOTA, etc.

> PoET

• Concept:

Proof of Elapsed Time. Typically used in permissioned blockchain networks, it determines the mining rights of those who obtain blocks in the network. Permissioned blockchain networks require any expected participants to verify their identity before joining. According to the principles of a fair lottery system, each node has an equal chance of becoming the winner.

• Implementation Principle:

Each participating node in the network must wait for a randomly selected period; the first node to complete the set waiting time will obtain a new block. Each node in the blockchain network generates a random waiting time and sleeps for a set time. The first node to wake up, i.e., the one with the shortest waiting time, wakes up and submits a new block to the blockchain, then broadcasts the necessary information to the entire peer network. This process will repeat to discover the next block.

Two Factors:

1. Participating nodes naturally select a random time rather than deliberately choosing one;

2. The winner has indeed completed the waiting time.

• Representative Application: HyperLedger Sawtooth, etc.

>PoSV

• Concept:

Proof of Stake Velocity. Proposed by Reddcoin, it draws on the economic concept of "velocity of money" and primarily allocates bookkeeping rights based on the coin age of nodes participating in the competition.

• Implementation Principle:

PoSV also allocates bookkeeping rights based on the coin age of nodes participating in the competition, but modifies the coin age calculation formula to an exponentially decaying function. Taking Reddcoin as an example, Reddcoin sets the half-life of coin age growth rate to one month. Assuming a unit token can accumulate 1 CoinDay of coin age on the first day, it can only accumulate 0.5 CoinDay of coin age on the 31st day, and 0.25 CoinDay of coin age on the 61st day, and so on. This approach encourages nodes to use their tokens for a transaction after holding them for a period, thus recalculating coin age and increasing the circulation speed of tokens in the network.

• Representative Application: Reddcoin, etc.

Table 2 Comparison of Advantages and Disadvantages of Current Mainstream Consensus Mechanisms

Source: Compiled from online resources

Chapter 4 Selection of Consensus Mechanisms and Summary of Current Status

4.1 How to Choose a Suitable Consensus Mechanism

Step 1: Determine the Importance of the Final Result

For some applications, the final result is very important. If you are building a new system that supports very small payments, changes in transaction results may be acceptable. Similarly, if you are building a distributed social network, it is not particularly necessary to guarantee that the status updates immediately 100%. In contrast, if you are building a distributed protocol, the final result is crucial for user experience. For example, Bitcoin has an approximate final confirmation time of 1 hour, Ethereum has about 6 minutes, while Tendermint Core has only 1 second.

Step 2: Determine How Fast the Application Process Needs to Be

If you are building a game, is it reasonable to wait 15 seconds before each action? Due to the low block processing time of Ethereum, games built on it may lead to poor user experience because of Ethereum's throughput. However, applications for transferring property rights can run perfectly well on Ethereum. Using the Cosmos SDK to build an application that allows developers to use Tendermint Core out of the box, it has a short block processing time and high throughput, capable of processing 10,000 transactions per second. You can reduce the required communication overhead and speed up the application by setting a maximum number of validators for the application.

Step 3: Determine the Degree of Decentralization Required by the Application

Some applications, such as games, may not require very high scrutiny resistance as a byproduct of decentralization. Theoretically, is it really important for validators to create cartels in games and reverse transaction results for profit? If not, blockchains like EOS may better suit your needs because they offer fast transaction speeds without fees. However, applications like autonomous banks become more decentralized as they grow stronger. Although Ethereum is considered decentralized, some supporters claim that Ethereum's mining pools are a significant point of centralization for the platform, even though there are only 11 validators (mining pools). One major advantage of building your own blockchain instead of constructing it on a smart contract platform is that you can customize how the application completes validation. However, building your own blockchain is challenging, so the Cosmos SDK is very useful for easily constructing your own blockchain and customizing the required degree of decentralization.

Step 4: Determine Whether the System Can Be Terminated

If you are building an application similar to a distributed ride-sharing service, ensuring 24/7 service must be a top priority, even if there are occasional accounting errors similar to transaction errors. One of the properties of Tendermint Core is that if there is a disagreement among network validators, the network will pause operations rather than execute erroneous transactions. Applications like decentralized exchanges require correctness at all costs—if issues arise, pausing trading in a decentralized exchange is far better than potentially encountering transaction problems.

Summary: Choosing a Suitable Consensus Algorithm After Weighing Pros and Cons

In summary, there is no single best consensus algorithm; each consensus algorithm has its own significance and advantages, and you need to make your own judgments and trade-offs. However, by understanding the relevant processes of consensus mechanisms, including proposals and protocols, and establishing a framework to consider the types of consensus algorithms your application may need, you should be able to make more informed decisions.

4.2 Future Development of Consensus Mechanisms

Consensus algorithms are one of the core elements of blockchain. Although this article lists over 30 consensus mechanisms, many niche consensus mechanisms may not have been discussed. As blockchain technology gradually becomes known and accepted by the public, it is likely that more and better consensus algorithms will emerge in the future, possibly new consensus algorithms or more likely improvements and optimizations of existing consensus algorithms.

After experiencing a flourishing period in 2016 and 2017, there is currently no universally recognized evaluation standard for consensus algorithms; they generally lean more towards fairness and the degree of decentralization, as well as some technical issues such as energy consumption, scalability, fault tolerance, and security. However, blockchain technology must be grounded in demand and application scenarios, and the consensus mechanism algorithms are closely related to incentive mechanisms. How to customize a suitable consensus mechanism for the characteristics of your project and optimize the current consensus mechanisms will become the future direction of research on consensus mechanisms.