Comparison of nine consensus mechanisms
There are many consensus mechanisms on the blockchain, but none of them are perfect or suitable for all application scenarios.
1. Proof of Work (POW)
Proof of Work (PoW) can usually only be proved from the results, because the monitoring process is usually cumbersome and inefficient.
Bitcoin uses the PoW mechanism in the block generation process. A block hash value that meets the requirements is composed of N leading zeros, and the number of zeros depends on the difficulty value of the network. To get a reasonable block hash value requires a lot of trial calculations, and the calculation time depends on the hash operation speed of the machine. When a node provides a reasonable block hash value, it means that the node has indeed undergone a large number of attempts to calculate, but the number of calculations cannot be obtained, because finding a reasonable hash value is a probabilistic event. When a node has n% of the computing power of the entire network, the node has an n% probability of finding the block hash value.
PoW relies on machines to perform mathematical operations to obtain accounting rights. It consumes a lot of resources, has a high consensus mechanism, and is weak in supervision. At the same time, each time a consensus is reached, the entire network must participate in the calculation. The performance efficiency is relatively low, and the fault tolerance is convenient to allow 50% of the entire network. The node has an error.
Advantages of PoW: Completely decentralized, nodes are free to enter and exit.
Disadvantages of PoW: At present, Bitcoin has attracted most of the world's computing power, and other blockchain applications that use the PoW consensus mechanism are difficult to obtain the same computing power to ensure their own security; mining causes a lot of waste of resources; consensus is reached The cycle is longer.
The projects using PoW are: Bitcoin and the first three stages of Ethereum (Frontier Frontier, Homestead Homestead, Metropolis). The fourth stage of Ethereum, Serenity, will adopt a proof-of-stake mechanism (POS).
2. Proof of equity (P0S)
Proof of Stake (PoS for short) was first proposed by Quantum Mechanic at the Bitcoin Forum lecture in 2011, and then implemented by Peercoin and NXT (Future Coin) in different ways.
The main idea of PoS is that the difficulty of obtaining a node's accounting rights is inversely proportional to the equity held by the node. Compared with PoW, it reduces the resource consumption caused by mathematical operations to a certain extent, and the performance has been correspondingly improved, but it is still It is a way to compete for the right to bookkeeping based on hash calculations, and it is weakly supervisable. The fault tolerance of this consensus mechanism is the same as that of PoW. It is an upgrade of PoW. According to the proportion and time of each node's tokens, the difficulty of mining is reduced in proportion to speed up the speed of finding random numbers.
In PoW, a user may spend $1,000 to buy a computer and join the network to mine to generate new blocks, thereby being rewarded. In PoS, users can buy equivalent tokens for $1,000 and put these tokens as deposits in the PoS mechanism, so that users have the opportunity to generate new blocks and get rewards.
In general, there is a collection of token holders in this system, and they put their tokens into the PoS mechanism so that they become validators. For example, for the first block of the blockchain, the PoS algorithm randomly selects one of the validators (the weight of the validator is selected according to the amount of tokens they invest, for example, a validator with a deposit of 1W tokens is selected The probability is 10 times that of a validator investing 1K tokens), giving him the right to generate the next block. If within a certain period of time, the validator does not generate a block, the second validator is selected instead of generating a new block. Like PoW, PoS is based on the longest chain.
With the disappearance of economies of scale (referring to the phenomenon of increased economic benefits caused by the expansion of production scale), the risk of centralization has decreased. The return from tokens worth 10 million USD is not more or less, which is 10 times that of tokens worth 1 million USD. No one will not get a proportional extra return because they can afford mass production tools.
Advantages of PoS: To a certain extent, it shortens the time for reaching consensus; it no longer needs to consume a lot of energy to mine.
Disadvantages of PoS: It still requires mining, which essentially does not solve the pain points of commercial applications; all confirmations are only a probabilistic expression, not a deterministic thing. In theory, there may be other attacks, such as Ethereum. The DAO attack caused the Ethereum hard fork, and the emergence of ETC, which in fact proved the failure of the hard fork.
3. Certificate of Share Authorization (DPOS)
The BitShares community first proposed the Proof of Share Authorization (DPoS) mechanism. The main difference between it and PoS is that the node elects several agents, which are verified and booked by the agents, but its compliance supervision, performance, resource consumption and The fault tolerance is similar to PoS. Similar to board voting, coin holders vote for a certain number of nodes for proxy verification and accounting.
The working principle of DPoS is as follows: each shareholder has corresponding influence according to his shareholding ratio, the result of 51% shareholder voting will be irreversible and binding, and the challenge is to achieve “51% approval” through a timely and efficient method ；
In order to achieve this goal, each shareholder can vote for a representative. The top 100 representatives with the most votes will take turns to generate blocks according to the established schedule. Each representative is allocated a time period to produce blocks.
All representatives will receive 10% of the transaction fee equivalent to an average block as a reward. If an average block uses 100 shares as a transaction fee, a representative will receive one share as a reward.
Network delays may prevent some representatives from broadcasting their blocks in time, and this will cause the blockchain to fork. However, this is unlikely to happen because the representative who made the block can establish a direct connection with the representatives of the blocks before and after the block is made. Establishing this direct connection with the representative behind you (and perhaps the representative behind) is to ensure that you get paid.
The voting mode of DPoS can generate a new block every 30 seconds, and under normal network conditions, the possibility of blockchain bifurcation is extremely small, and even if it occurs, it can be resolved within a few minutes. The basic steps to implement this mode are as follows:
Become a representative. To become a representative, you must register your public key on the network and obtain a 32-bit unique identifier. This identifier will be referenced by the "head" of each transaction data.
Authorize voting. Each wallet has a parameter setting window, in which the user can select one or more representatives and rank them. Once set, each transaction made by the user will transfer votes from the "input representative" to the "output representative". Under normal circumstances, users will not create transactions specifically for voting purposes, because that will cost them a transaction fee. But in emergency situations, some users may feel that it is worthwhile to pay a fee to change their vote in a more positive way.
Keep the representatives loyal. Each wallet will display a status indicator to let users know how their representatives are performing. If they miss too many blocks, the system will recommend the user to change to a new representative. If any representative is found to have issued an invalid block, then all standard wallets will ask for a new representative to be elected before each wallet performs more transactions.
Resist the attack. In resisting attacks, the top 100 representatives have the same rights, that is, each representative has an equal right to vote. Therefore, it is impossible to concentrate power on a single representative by obtaining more than 1% of the votes. Since there are only 100 representatives, it is not difficult to imagine that an attacker can perform a denial of service attack on each representative whose turn to produce the block in turn. Fortunately, since each representative is identified by his public key rather than an IP address, the threat of this particular attack can be easily mitigated. This will make it more difficult to determine the target of a DDoS (distributed denial of service) attack. The potential connection between representatives will make it more difficult to prevent them from producing blocks.
The advantages of DPoS: greatly reduce the number of nodes participating in verification and accounting, and can achieve consensus verification in seconds.
Disadvantages of DPoS: The entire consensus mechanism still relies on tokens, and many commercial applications do not require tokens.
4. Betting consensus
Betting consensus is a new concept introduced by Casper, the next-generation consensus mechanism of Ethereum, and belongs to PoS. Casper's consensus is reached by block, not by chain like PoS.
In order to prevent validators from offering different bets in different worlds, we also have a simple and strict clause: if your two bet numbers are the same, or if you submit a bet that cannot be processed by Casper in accordance with the contract, you will lose All deposits. From this we can see that Casper is different from traditional PoS in that Casper has a penalty mechanism, so that illegal nodes not only get no transaction fees through malicious attacks on the network, but they also face the risk of confiscation of the deposit.
The validator under the Casper protocol needs to complete the two activities of block production and betting. details as follows:
Block generation is a process that occurs independently of all other times. The validator collects transactions. When it is their turn to generate a block, they create a block, sign it, and send it to the network. The betting process is more complicated. The current Casper default validator strategy is designed to imitate the traditional Byzantine fault-tolerant consensus: observe how other validators bet, take the value at 33%, and move further towards 0 or 1.
The process of the client confirming the current state is as follows: first download all the blocks and bets, and then use the above algorithm to form its own opinions, but do not publish the opinions; it simply proceeds in order at each height Observe that if the probability of a block is higher than 0.5, process it, otherwise skip it. After processing all the blocks, the resulting state can be displayed as the "current state" of the blockchain. The client can also give a subjective view of "final determination": if the opinion formed by each block before the height k is higher than 99.999% or lower than 0.001%, then the client can think that the first k blocks have been finalized .
5. Ripple Consensus
The Ripple consensus algorithm enables a group of nodes to form a consensus based on a list of special nodes. The initial list of special nodes is like a club. To admit a new member, 51% of the club’s members must vote. Consensus follows the "51% rights" of these core members, and outsiders have no influence. Since the club started from centralization, it will always be centralized, and if it starts to corrupt, shareholders can't do anything. Like Bitcoin and Peercoin, the Ripple system separates shareholders from their voting rights, so it is more centralized than other systems.
6. Pool verification pool
Based on the traditional distributed consistency technology and data verification mechanism, the Pool (joint venture) verification pool is currently a consensus mechanism used on a large scale in the industry. Its advantages and disadvantages are as follows:
Advantages: It can work without tokens. On the basis of mature distributed consensus algorithms (Paxos, Raft), it can achieve second-level consensus verification.
Disadvantages: The degree of decentralization is not as good as Bitcoin, which is more suitable for a multi-center business model with multiple parties.
7. Practical Byzantine fault tolerance
In distributed computing, different computers try to reach consensus through information exchange, but sometimes, the coordinating computer or member computers in the system may exchange wrong information due to system errors, which affects the final system consistency. For the Byzantine Generals problem, if you look for possible solutions based on the number of wrong computers, you can’t find an absolute answer, but can only be used to verify the effectiveness of a mechanism.
The possible solution to the Byzantine Generals problem is: in the case of N≥3F+1, consistency is possible (N is the total number of computers, F is the total number of computers in question). After the information is exchanged between the computers, each computer lists all the obtained information, and most of the results are used as solutions.
The use of Byzantine Fault Tolerance (PBFT) first proposed by Castro and Liskov in 1999 was the first Byzantine algorithm to be widely used. As long as 2/3 of the nodes in the system are working normally, consistency can be guaranteed.
The overall process of using the Byzantine fault-tolerant algorithm is as follows: the client sends a request to the master node to call the service operation, such as "<REQUEST,o,t,c>", where the client c requests to perform the operation o, and the timestamp t is used to guarantee the client The request will only be executed once. Each message sent by the replica node to the client contains the current view number, so that the client can track the view number, thereby further calculating the current master node number. The client sends a request to the master node it thinks through a point-to-point message, and then the master node automatically broadcasts the request to all backup nodes.
The view number is an integer numbered consecutively. The master node is calculated by the formula p=v mod |R|, where v is the view number, p is the replica number, and |R| is the number of replica sets.
The response of the copy to the customer order is "<REPLY,v,t,c,i,r>", v is the view number, t is the timestamp, i is the number of the copy, and r is the result of the requested execution.
The master node sends the request to other replicas through broadcasting, and then starts to perform the three-phase task.
Preparation stage. The master node assigns a sequence number n to the received request, and then sends a pre-preparation message to all backup nodes. The pre-preparation message format is "<<PRE-PREPARE, v, n, d>, m>", where v is the view Number, m is the request message sent by the client, and d is the summary of the request message m.
preparation stage. If the backup node i accepts the pre-preparation message, it enters the preparation phase. While preparing, the node sends a preparation message "<PREPARE, v, n, d, i>" to all replica nodes, and writes the preparation message and the preparation message into its own message log.
Confirmation stage. When the "(m, v, n, i)" condition is true, replica i broadcasts "<COMMIT, v, n, D(m), i>" to other replica nodes, and then enters the confirmation phase. All copies execute the request and send the result back to the client. The client needs to wait for different replica nodes to send back the same result as the final result of the entire operation.
If the client does not receive a reply within a limited time, the request will be broadcast to all replica nodes;
If the request has been processed at the replica node, the replica will resend the execution result to the client;
If the request has not been processed at the replica node, the replica node will forward the request to the master node;
If the master node does not broadcast the request, then the master node is considered invalid;
If there are enough replica nodes that the master node is invalid, it will trigger a view change.
Figure 2-85 shows the normal execution flow of the algorithm without the failure of the master node, where copy 0 is the master node, copy 3 is the failed node, and c is the client.
Use Byzantine fault tolerance
