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
- Since the Queen of Hamburg, PricewaterhouseCoopers Luxembourg accepts bitcoin payments
- Add or send? TEDA's Ethereum USDT additional issuance strategy and flow analysis in August
- Exclusive | Central bank officials first started the app to explain Libra and central bank digital currency
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
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
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.
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.
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
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."
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.
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”
〉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
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.
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.
We will continue to update Blocking; if you have any questions or suggestions, please contact us!
Was this article helpful?
93 out of 132 found this helpful
Related articles
- Technical Guide | Python Smart Contract Development? It’s enough to read this one.
- 5G Chain Network – New Era Spark Program (Funding) Rural Revitalization Closed Meeting is about to be held
- Data observation: Ethereum DApp ecology begins to recover
- Bitcoin rose $1,000 in two days, which may be the three reasons
- A-share blockchain concept stocks "interim examination" handed over: some profits of several hundred million yuan, and some received a million subsidies
- The volume of trading has not been significantly enlarged, and the rebound is suspected to be more attractive.
- After the Bell chain crashes, it is suspected that the new disk will be restarted.
