Research on Consensus Mechanism | Seeing Knowledge, Insights, and Enlightenment

Seeing the knowledge, understanding and understanding, the retrospect and prospect of the encryption economy – the consensus mechanism

Table 1 Consensus System Classification

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

Figure 4 Evolution of consensus algorithm

Source: Network data organization

Foreword

The consensus mechanism is one of the important elements of the blockchain and the core rule for the normal operation of the distributed ledger. It is mainly used to solve the trust problem between people and determine who is responsible for generating new blocks and maintaining in the blockchain system. The effective unity of the system has become a constant research hotspot in the field of blockchain.

Starting from the concept and role of the consensus mechanism, this paper first gives the reader a preliminary understanding of the consensus mechanism. Then, starting from the issues of the two armies and the Byzantine generals, the development of the consensus mechanism is introduced in accordance with the sequence of time proposed by the consensus mechanism; Then it introduces the current mainstream consensus mechanism from three aspects: concept, working principle and representative project, and compares the advantages and disadvantages of the mainstream consensus mechanism. Finally, it gives suggestions on how to choose the consensus mechanism for the blockchain project. And pointed out the possibility of future development of the consensus mechanism.

table of Contents

First, the concept and role of the consensus mechanism 1.1 Concept: the core rules of the normal operation of the distributed ledger

1.2 Role: Solving the problem of trust and determining the generation and maintenance of new blocks

1.2.1 Used to solve the problem of trust between people

1.2.2 is used to determine who is responsible for generating new blocks and maintaining effective unification in the blockchain system

1.3 Mainstream model of consensus algorithm

Second, the origin of the consensus mechanism

2.1 The issue of the two armies and the issue of the Byzantine General

2.1.1 The issue of the two armies

2.1.2 Byzantine General

2.2 History of consensus mechanism development

2.2.1 Classification of consensus mechanisms

2.2.2 Development Mechanism of Consensus Mechanism

Third, the common consensus system

Fourth, the choice of consensus mechanism and summary of the status quo

4.1 How to choose a consensus mechanism that suits you

4.1.1 Determine if the final result is important

4.1.2 How fast does it take to determine the application process?

4.1.2 Determine the degree of application decentralization needs

4.1.3 Determine if the system can be terminated

4.1.4 Choose the appropriate consensus algorithm after weighing the advantages and disadvantages

4.2 Future development of consensus mechanism

Chapter 1 Concept and Role of Consensus Mechanism

1.1 Concept: The core rules for the normal operation of distributed ledgers

Since most of the cryptocurrencies use decentralized blockchain design, nodes are scattered and parallel everywhere, so a system must be designed to maintain the order and fairness of the system, unify the version of the blockchain, and reward Resources maintain users of the blockchain and punish malicious people. Such a system must rely on some way to prove who made the right to pack a blockchain (or billing right) and get the reward for packing the block; or who is going to harm it? , will get a certain punishment, this is the consensus mechanism.

1.2 Role: Solving the problem of trust and determining the generation and maintenance of new blocks
1 .2.1 Used to solve the problem of trust between people

The reason why the consensus mechanism can be at the core of blockchain technology is that it has a set of rules from the perspective of cryptographic techniques such as asymmetric encryption and time stamping. All participants and their participation methods must abide by this. Set rules, and the rules are transparent, can not be modified at will, so without the endorsement of third-party authorities, it can also launch the nodes of the whole network to jointly supervise, record all transactions, and publish them in the form of code, effectively Realizing the transfer of value information, solving or, more precisely, greatly improving the trust between two strangers who are unrelated and distrustful of each other. After all, trusting an objective technology is more risky than trusting a subjective person. small.

1.2.2 is used to determine who is responsible for generating new blocks and maintaining effective uniformity in the blockchain system. On the other hand, in the blockchain system, due to the high network latency under the peer-to-peer network, each node observes There are certain differences in the order of transaction transactions. Therefore, the consensus mechanism can reach a consensus on the transaction transactions occurring during this period in a short period of time to determine who is responsible for generating new blocks in the blockchain system, and Maintain the effective unification of the blockchain.
1.3 The mainstream model of the consensus algorithm The blockchain system is built on the P2P network. The collection of all nodes can be recorded as PP. It is generally divided into ordinary nodes for production data or transactions, and is responsible for verifying the data or transactions generated by ordinary nodes. The "miners" node set (marked as M) for mining operations such as packing and updating the winding, the two types of nodes may have intersections; the miners usually participate in the consensus competition process, and will also elect specific in specific algorithms. Representing nodes, replacing them in the consensus process and competing for billing rights. The collection of these representative nodes is recorded as D; D; the accounting nodes selected through the consensus process are recorded as AA consensus processes, which are repeated according to the round, each round of consensus The process generally re-selects the accounting node of the round. The core of the consensus process is the two parts of "selector" and "bookkeeping". Each round can be divided into leader election and block (block) in the specific operation process. Generation), validation (Data validation) and chaining (ie, accounting) are four stages. As shown in Figure 1, the input to the consensus process is the transaction or data generated and verified by the data node. Is packaged data block and the update block chain. 4 performs the cycle phases, each one executed will generate a new tile.

Figure 1 Basic model of the blockchain consensus process

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

Phase 1: Election

The selection is the core of the consensus process, that is, the process of selecting the accounting node AA from the entire miner node set MM: we can use the formula f(M)→f(M)→AA to represent the main selection process, where the function ff represents The specific implementation of the consensus algorithm. In general, |A|=1,|A|=1, that is, the only miner node is selected to be accounted for.

Stage 2: Blocking

The accounting node selected in the first stage packs the transaction or data generated by the entire node PP in the current time period into a block according to a specific strategy, and broadcasts the generated new block to the entire miner node MM or its representative node DD. These transactions or data are usually sorted into new blocks according to various factors such as block capacity, transaction cost, and transaction waiting time. The block-making strategy is a key factor in the performance of the blockchain system, and it is also greedy transaction packaging and selfishness. 3. The concentrated expression of the strategic behavior of mining miners and other miners.

Phase 3: Verification

After the miner node MM or the representative node DD receives the broadcast new block, it will verify the correctness and rationality of the transaction or data encapsulated in the block. If the new block is approved by most of the verification/representative nodes, the block Will be updated to the blockchain as the next block.

Stage 4: Winding

The accounting node adds the new block to the main chain, forming a complete, longer chain from the creation block to the latest block. If there are multiple fork chains in the main chain, the main chain according to the consensus algorithm is required. Determine the criteria to choose one of the appropriate branches as the main chain.

The second chapter is the origin of the consensus mechanism

2.1 The issue of the two armies and the issue of the Byzantine General
2.1.1 The issue of the two armies

Figure 2 Schematic diagram of the two military issues

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

As shown in the figure, the 1st and 2nd branches of the Blue Army are stationed on both sides of the slope, and they cannot communicate remotely, and the White Army is stationed in the middle of the two armies. Suppose the White Army is stronger than any of the two Blue Army units, but not as powerful as the two Blue Army. If the two units of the Blue Army need to jointly attack at the same time, they need to communicate with each other. However, the White Army is on the way to the middle. It is impossible to confirm whether the Blue Army Messenger has actually sent the offensive signal to the opposite side, and temporarily does not consider whether the information has been The possibility of tampering. Under this circumstance, due to the inability to achieve full confirmation between each other, ultimately no effective consensus can be reached, forming a "two military paradox."

2.1.2 Byzantine General

Figure 3 Schematic diagram of the Byzantine general

Due to the vast territory of the Byzantine Roman Empire at that time, in order to better achieve the purpose of defense, the army was scattered around the empire. Each army was far apart and could only rely on the messenger to transmit news. During the war, all the generals must reach an agreement, or decide on whether to attack the enemy camp with the majority of the agreement. However, since there is a complete dependence on people, if there is a situation in which the military or the messenger sends the wrong message, how can we ensure that the loyal generals reach an agreement without being affected by the traitors? Then there was the Byzantine issue.

Both the military issue and the Byzantine general are expounding a problem: in the case of unreliable information exchange, there are great difficulties in reaching consensus and concerted action. The question of General Byzantine is more like the generalization of the "two military paradoxes."

From the perspective of computer networks, both the military and Byzantine issues are common in computer network courses: the direct communication between two nodes on the network has the possibility of failure, so the TCP protocol cannot completely guarantee the two terminal networks from beginning to end. A state of 100% consistent. However, consensus mechanisms can use other means such as economic incentives to reduce this uncertainty to a level that most people can accept.

It is precisely because of the problems of the two military issues and the Byzantine issue that the consensus mechanism has begun to show its necessity for development.

2.2 History of consensus mechanism development
2.2.1 Classification of consensus mechanisms

Since different blockchain project types have different requirements for information recording and block generation, and with the continuous improvement of the consensus mechanism with the development of blockchain technology, there are currently more than 30 consensus mechanisms. These consensus mechanisms can be divided into two main categories according to their Byzantine fault-tolerant performance: the Byzantine fault-tolerant system and the non-Byzantine fault-tolerant system.

Table 1 Classification of consensus mechanisms

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

2.2.2 Development of consensus mechanism

〉The development of consensus algorithms

According to the proposed time of the consensus algorithm, we can see the development of the consensus algorithm relatively clearly.

Figure 4 Evolution of consensus algorithm

Source: Network data organization

Figure 5 Historical evolution of the blockchain consensus algorithm

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

The consensus algorithm lays the foundation for the consensus mechanism of the blockchain. Initially, the study of consensus algorithms was mainly used by computer scientists and computer professors to improve spam issues or academic discussions.

For example, in 1993, Cynthia Dwork, a US computer scientist and professor at Harvard University, first proposed the idea of ​​proof of work in order to solve the problem of spam. In 1997, the British cryptographer Adam Back independently proposed and solved the spam problem in 2002. In 1999, Markus Jakobsson officially presented the concept of “workload proof”, which laid the foundation for the design of the Bitcoin consensus mechanism.

Chapter III Common Consensus Mechanism

Figure 6 Comparison of the mainstream mainstream consensus mechanism

Source: Hasib Anwar, “Consensus Algorithms: The Root Of The Blockchain Technology”

The above picture shows 14 of the relatively mainstream consensus mechanisms summarized by a geek Hasib Anwar, including PoW (workload proof), PoS (certificate of interest), DPoS (certificate of entrusted equity), LPoS (rental proof of entitlement), PoET ( Proof of past time), PBFT (Practical Byzantine Fault Tolerance), SBFT (Simple Byzantine Fault Tolerance), DBFT (Delegate Byzantine Fault Tolerance), DAG (Directed Acyclic Chart), Proof-of-Activity (Proof of Activity), Proof-of- Importance, Proof-of-Capacity, Proof-of-Burn, Proof-of-Weight.

Next, we mainly introduce the analysis and analysis of the top ten consensus mechanisms of the current blockchain.

POW

Concept:

Workload certification mechanism. That is to say, the proof of the workload means that a certain amount of computer time is consumed to confirm the amount of work done.

Implementation principle:

Figure 7 PoW workload proof principle

The PoW represented by Bitcoin uses the SHA-256 algorithm function, which is a hash algorithm that outputs 256 bits in the password hash function family:

The output of the proof of work = SHA256 (SHA256 (block header));

If (output of the proof of work < target value), to prove that the workload is completed;

If (output of proof of work> = target value), change the random number, the logic of recursive i, continue to compare with the target value.

New difficulty value = old difficulty value * (the length of the past 2016 blocks / 20160 minutes)

Target value = maximum target value / difficulty value

The maximum target value is a fixed number. If the time spent in 2016 is less than 20160, then the coefficient will be smaller and the target value will be increased. Otherwise, the target value will be reduced. Therefore, bitcoin The difficulty and the speed of the block will be adjusted in an inverse proportion to adjust the block speed.

Representative application: BTC, etc.

》POS

Concept:

Proof of equity. That is to say, according to the mechanism by which each person holds the currency rights to reach a consensus, the longer the currency is held, the greater the probability of obtaining the reward.

Implementation principle:

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

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

Among them, coinage indicates the age of the coin, which means that the older the coin, the easier it is to get an answer. The calculation of the age of the coin is obtained by multiplying the coin owned by the miner by the remaining time of each coin, which will mean that the more coins you have, the easier it is to get the answer. In this way, pos solves the problem of wasting resources in pow, and at the same time, the miner cannot own 51% of the entire network, so it also solves the problem of 51% attack.

Representative application: ETH, etc.

DPoS

Concept:

Entrusted equity certificate. That is, the investor holding the currency operates the entire network by voting for the super node, similar to the people's congress system.

Implementation principle:

The DPOS algorithm is divided into two parts. Elect a group of block producers and dispatch production.

Elections: Only permanent nodes with the right to be elected can be elected, and only the top N witnesses can be elected. All N people must get more than 50% of the votes to be elected. In addition, the list will be re-elected at regular intervals.

Scheduling production: Under normal circumstances, block producers produce a block every 3 seconds in turn. Assuming that no producers miss their order, the chain they produce is bound to be the longest chain. When the witness produces a block, a block needs to be generated every 2 seconds. If the time is exceeded, the current witness will lose the production right and transfer it to the next person. The witness is not only not paid, but may also lose the witness status.

Representative application: EOS, etc.

DPoW

Concept:

Proof of delayed workload. A new generation of consensus mechanisms based on PoB and DPoS. The miner uses his own calculation power, through the hash algorithm, and finally proves his workload, after obtaining the corresponding wood, wood is not tradeable. When the wood has accumulated a certain amount, you can go to the burning site to burn wood. This will balance the power of calculation and mining rights.

Implementation principle:

In the DPoW-based blockchain, miners mining is no longer a reward token, but a “wood” that can be burned, burning wood. The miner uses his own calculation power, through the hash algorithm, and finally proves his workload, after obtaining the corresponding wood, wood is not tradeable. When the wood has accumulated a certain amount, you can go to the burning site to burn wood. Through a set of algorithms, people who burn more wood or BP or a group of BP can get the right to the next event segment, and get rewards (tokens) after successful block. Since there may be more people burning wood in a period of time, the probability of a block in the next time period is determined by the amount of wood burned by itself. The more you burn, the higher the probability that you will get a block right in the next period.

Two node types: a notary node and a normal node.

The 64 notary nodes are elected by the equity holders of the dPoW blockchain, and the notarized blocks can be added from the dPoW blockchain to the attached PoW blockchain. Once a block has been added, the block's hash value will be added to the Bitcoin transaction signed by the 33 notary nodes and a dPow block record will be created that hashes to the Bitcoin blockchain. This record has been notarized by most notary nodes in the network. In order to avoid war between the notary nodes in mining, and thus reduce the efficiency of the network, Komodo designed a mining method using a polling mechanism, which has two modes of operation. In the "No Notary" mode, all network nodes are supported to participate in mining, similar to the traditional PoW consensus mechanism. In the "Notaries Active" mode, network notaries use a significantly reduced network difficulty rate to mine. In the “Notary Public Activation” mode, each notary is allowed to mine a block using its current difficulty, while other notary nodes must use 10 times difficulty mining, and all normal nodes use 100 times the difficulty of the notary node.

Figure 8 DPoW in the absence of a notary public node workflow

Representative application : Komodo et al

PBFT

Concept :

Practical Byzantine fault tolerance algorithm. The algorithm complexity is reduced from exponential to polynomial, making the Byzantine fault-tolerant algorithm feasible in practical system applications.

Implementation principle :

Figure 9 PBFT algorithm principle

First, the client sends a request to the master node to invoke the service operation, and then the master node broadcasts the other copy of the request. All copies 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 qualifications: 1. All nodes must be deterministic. That is, the results of the operation execution must be the same given the same state and parameters. 2. All nodes must be executed from the same state. Under these two qualifications, even if there is a failed replica node, the PBFT algorithm agrees on the total order of request execution of all non-failed replica nodes, thus ensuring security.

Representative application : Tendermint Consensus, etc.

DBFT

Concept:

Authorized Byzantine fault tolerance. Improved Byzantine fault tolerance algorithm to make it suitable for blockchain systems. The system consists of a node, a principal (who can approve the block), and a spokesperson (who proposes the next block). It is a consensus algorithm for guaranteeing fault tolerance implemented inside the NEO blockchain.

Implementation principle:

Within this mechanism, there are two participants: the “booking node” for professional accounting and the average user in the system.

Ordinary users vote to determine the accounting node based on the proportion of equity held. When a consensus is needed, a speaker is randomly selected from these accounting nodes to formulate a plan, and then other accounting nodes according to the Byzantine fault-tolerant algorithm. That is, the principle of obeying the majority is stated. If more than 66% of the nodes agree to the speaker's plan, the consensus is reached; otherwise, the speaker is re-elected and the voting process is repeated.

Representative application: Neo, etc.

PoA

Concept:

Proof of authority. That is, certified by some approved accounts, these recognized accounts are called "Validators". The software run by the verifier, which allows the verifier to place the transaction in the block.

Implementation principle :

Three conditions:

1. The identity must be formally verified on the chain, and the information can be cross-validated in the publicly available domain;

2, its qualifications must be difficult to obtain, so the right to obtain the verification block is precious enough; 3, the establishment of authoritative inspections and procedures must be completely unified.

With PoA, each individual has the right to become a verifier, so there is an incentive to maintain the verifier's location once acquired. By attaching a reputation to the identity, the certifier can be encouraged to maintain the transaction. Because the verifier does not want to get a negative reputation, it will make it lose the hard-won certifier status.

Representative application : VeChain, etc.

DAG

Concept :

Directed acyclic graph. Each newly added unit in the DAG not only joins the long-chain block, but joins all the previous blocks, verifies each new unit and confirms its parent unit and the parent unit of the parent unit. The unit, and the hash of its parent unit is included in its own unit. As time increases, the blockchains of all transactions are connected to each other to form a graph structure.

Implementation principle :

In the DAG network, each node can be a trader and a verifier, because the transaction processing in the DAG is done by the transaction node itself. Taking IOTA as an example, IOTA's Tangle ledger does not need to pay transaction fees while ensuring high-speed processing of transactions. However, it does not mean that the transaction is free, because in this account, each transaction needs to verify the other two random transactions first, and direct the transactions initiated by the two to the two transactions, so that the miners in the blockchain The responsibilities assumed are assigned to all traders. The way DAG handles transactions can be called asynchronous processing mode.

Figure 10 Difference between traditional blockchain structure and DAG structure

Representative application : IOTA, etc.

PoET

Concept :

Proof of the amount of elapsed time. That is, it is usually used to license the blockchain network, which determines the mining rights of the blockpers in the network. The licensed blockchain network requires any prospective participant to verify identity before joining. According to the principle of the fair lottery system, each node has the same chance of becoming the winner.

Implementation principle :

Each participating node in the network must wait for a randomly selected period, and the first node that completes the set waiting time will get a new block. Each node in the blockchain network generates a random wait time and sleeps for a set amount of time. The node that wakes up first, the node with the shortest waiting time, wakes up and submits a new block to the blockchain, and then broadcasts the necessary information to the entire peer-to-peer network. The same process will be repeated to find the next block.

Two factors:

1. The participating nodes will naturally select a random time instead of deliberately selecting;

2. The winner did complete the waiting time.

Representative application : HyperLedger Sawtooth, etc.

PoSV

Concept :

Proof of equity circulation. It is proposed by Reddcoin that the concept of “money circulation speed” in economics is mainly based on the age-based accounting rights of nodes participating in the competition.

Implementation principle :

PoSV also assigns billing rights according to the age of the nodes participating in the competition, but changes the calculation formula of the currency age to a function of the growth rate exponential decay. Taking Reddcoin as an example, Reddcoin sets the half-life of the growth rate of the currency to one month. Assume that the unit pass can accumulate 1 CoinDay currency on the first day, only 0.5 CoinDay coin age on the 31st day, 0.25 CoinDay coin age on the 61st day, and so on. In this way, the node is used to conduct a transaction after holding the pass for a period of time, thereby restarting the calculation of the currency age and increasing the circulation speed of the pass in the network.

Representative application : Reddcoin, etc.

Table 2 Comparison of the advantages and disadvantages of the current mainstream consensus mechanism

Source: Network resource organization

Chapter IV Summary of the Choice and Status Quo of Consensus Mechanism

4.1 How to choose a consensus mechanism that suits you

Step 1: Determine if the final result is important

For some applications, the end result is very important. If you are building a new one that can support a very small payment system, then the change in trading results is acceptable. Similarly, if you are building a new distributed social network, it is not particularly necessary to have a 100% guaranteed status update immediately. Conversely, if you are building a new distributed protocol, the end result is critical to the user experience. For example, Bitcoin has about one hour of final confirmation time, Ethereum has about 6 minutes of final confirmation time, and Tendermint Core has only one second of final confirmation time.

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 processing time of the Ethereum block, the game built on it will result in a poor user experience due to the throughput of Ethereum. However, the application for the transfer of property rights can be run entirely on Ethereum. Use the Cosmos SDK to build an application that allows developers to use Tendermint Core out of the box with short block processing time and high throughput to handle 10,000 transactions per second. You can reduce the communication overhead required and speed up the application by setting the maximum number of validators for your application.

Step 3: Determine the extent to which the application needs decentralization

Some applications such as games may not require very high scrutiny as a decentralized by-product. In theory, is it really important for the verifier to be able to create a cartel in the game and reverse the results of the transaction to make a profit? If it doesn't matter, a blockchain such as EOS may be better suited to your needs because the transaction is fast and there is no cost to pay. However, some of the more powerful applications such as autonomous banks will be more dispersed. Although Ethereum is considered to be decentralized, some supporters claim that the Ethereum mine is an important part of the platform's centralization, although there are actually only 11 validators (mine pools). One of the great things about building your own blockchain instead of building it on a smart contract platform is that you can customize the way your app performs validation. However, building your own blockchain is difficult, so the Cosmos SDK is very useful, making it easy to build your own blockchain and customize how much you need to decentralize.

Step 4: Determine if the system can terminate

If you are building an application that is similar to a distributed shared ride service, then ensuring 24/7 service must be a top priority, even if there are occasional transaction-like errors in accounting. One of the attributes of Tendermint Core is that if there is a disagreement between network verifiers, the network will suspend operations instead of making the wrong transactions. Applications such as decentralized exchanges require correctness at all costs – if there is a problem, decentralized exchanges are much more likely to suspend transactions than may occur.

Summary: Choose the appropriate consensus algorithm after weighing the advantages and disadvantages

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

4.2 Future development of consensus mechanism

The consensus algorithm is one of the core elements of the blockchain. Although there are more than 30 consensus mechanisms listed in the paper, there are still many niche consensus mechanisms that may not be discussed. As the blockchain technology is gradually known and accepted by the public, there may be more and more updated consensus algorithms appearing in the future, which may be a new consensus algorithm, and more should be the current consensus algorithm. Improvement and optimization.

After 16 years and 17 years of blooming, the current consensus algorithm does not have a recognized evaluation standard, but generally prefers the degree of fairness and decentralization, as well as some technical related issues, such as energy consumption and scalability. , fault tolerance and security. However, blockchain technology must be combined with requirements and application scenarios, and the consensus mechanism algorithm and incentive mechanism are inseparable. How to customize the appropriate consensus mechanism for the characteristics of their own projects and optimize the current consensus mechanism will become the development of future consensus mechanism research. direction.