Consensus algorithm is actually a set of rules, setting a set of conditions and screening representative nodes. In the blockchain system, there are many such screening schemes, such as POW, Pos, DPOS and so on. In the public chain, but in the franchise chain or private chain that does not need monetary system, the public chain consensus algorithm can not provide absolutely reliable nodes and efficient requirements. For such a blockchain, traditional consistency algorithms have become the first choice, such as PBFT, PAXOS, RAFT and so on.
catalogue
BFT (Byzantine fault-tolerant technology)
Second, PBFT (practical Byzantine fault-tolerant algorithm)
Third, PAXOS.
Fourth, the raft
Verb (abbreviation of verb) power (proof of workload)
Six, POS (proof of rights and interests)
Seven. DPOS (Certificate of Employment Interests)
Eight, ripples
Byzantine error correction technology is a fault-tolerant technology in the field of distributed computing. Byzantine hypothesis is that the behavior of computers and networks is unpredictable due to hardware errors, network congestion or interruption and malicious attacks. Byzantine fault tolerance is used to deal with this abnormal behavior and meet the specifications of the problems to be solved.
Byzantine fault-tolerant system is a system with n nodes. For each request, the whole system meets the following conditions:
1) All non-Byzantine nodes use the same input information and produce the same result;
2) If the input information is correct, all non-Byzantine nodes must receive this information and calculate the corresponding results.
Common assumptions in Byzantine system include:
1) Byzantine nodes can behave arbitrarily, and Byzantine nodes can collude with each other;
2) The errors between nodes are uncorrelated;
3) When nodes are connected through asynchronous network, messages in the network may be lost, out of order and delayed, but most protocols assume that messages can reach their destinations in a limited time;
4) The information transmitted between servers can be sniffed by a third party, but it cannot be tampered with or forged, and the integrity of the information can be verified.
Byzantine fault tolerance is feasible in theory, but not practical in practice, and it needs the support of additional clock synchronization mechanism. The complexity of the algorithm also increases exponentially with the increase of nodes.
Practical Byzantine fault tolerance reduces the computational complexity of Byzantine protocol from exponential level to polynomial level.
PBFT is a state machine replication algorithm, that is, the service is modeled as a state machine, and the state machine replicates at different nodes of the distributed system. PBFT teaches to jointly safeguard a country. Three basic protocols need to be run, including consistency protocol, checkpoint protocol and view replacement protocol.
Consistency protocol. A consistency agreement includes at least several stages: request, preparation and reply, and may also include mutual preparation, submission and other stages.
In PBFT communication mode, each customer's request needs to go through five stages. Because the client can't get any information about the running state of the server from the server, whether the master node of PBFT has an error can only be monitored by the server. If the server fails to complete the client's request within a period of time, it will trigger the view replacement protocol.
The basic process of the whole agreement is as follows:
1) The client sends a request to activate the service operation of the master node.
2) When the master node receives the request, it starts the three-level protocol to broadcast the request to the slave node.
[2. 1] In the sequence number allocation stage, the master node allocates a sequence number n to the request, broadcasts the sequence number allocation message and the request message m of the client, and constructs a PRE-PREPARE message for each slave node;
[2.2] In the interactive stage, receive the pre-preparation message from the node and broadcast the pre-preparation message to other service nodes;
[2.3] In the serial number confirmation stage, after verifying the request and sequence in the view, each node broadcasts a submit message, executes the received request from the client and responds to the client.
3) The client waits for responses from different nodes. If there are m+ 1 identical responses, the response is the result of the operation.
PBFT is generally suitable for private chains and alliance chains that require strong consistency. For example, in the blockchain super ledger project led by IBM, PBFT is an optional consensus agreement. In the Fabric project of Hyperledger, the consensus module is designed as a pluggable module, which supports consensus algorithms such as PBFT and Raft.
In some distributed scenarios, it is assumed that Byzantine faults do not need to be considered, and only general crash faults are handled. In this case, it will be more efficient to adopt protocols such as Paxos. . PAXOS is a consistency algorithm based on message passing, which has high fault tolerance.
PAXOS has three roles: proposer, receiver and learner, and the main interaction process is between proposer and receiver. The algorithm flow is divided into two stages:
Stage 1
A) The proposer sends a preparation message to more than half of the recipients in the network.
B) The recipient usually replies to the commitment message.
Second phase
A) When enough recipients reply to the acceptance message, the proposer sends an acceptance message.
B) Under normal circumstances, the recipient replies to the accepted message.
The flow chart is as shown in the figure:
Wechat PAXOSStore uses Paxos protocol, and the process of calling Paxos protocol every minute is billions of times.
Paxos is a protocol designed by Lamport to maintain the consistency of distributed systems. However, Paxos is very complex and difficult to understand, so there are various implementations and variants later. Raft is an easier-to-understand consistency algorithm proposed by Stanford, which is intended to replace Paxos algorithm which is widely used at present.
Raft was originally a consensus algorithm for managing replication logs, and it is a strong consensus protocol for reaching consensus under non-Byzantine failures. The process for Raft to reach a consensus is: first, select a leader, and the leader receives the accounting request from the client, completes the accounting operation, generates blocks, and copies them to other accounting nodes. Leaders have complete management and bookkeeping rights. For example, the leader can decide whether to accept new transaction records without considering other accounting nodes, and the leader may become invalid or lose contact with other nodes. At this time, the new leader was re-elected.
In Raft, each node will be in one of the following three states:
(1)follower: All nodes start with the follower status. If no leader message is received, it will become a candidate state;
(2) Candidate: It will "pull votes" from other nodes, and if it gets the most votes, it will become the leader. This process is called leader election;
(3) Leadership: All modifications to the system must go through leadership first. Each modification will write a log entry. The process after the leader receives the modification request is as follows: This process is called log copying.
1) copies the log to all follower nodes.
2) Most nodes only submit logs when responding.
3) Notify all followers of node logs that they have been submitted.
4) All followers also submit logs.
5) Now the whole system is in a consistent state.
The raft stage is mainly divided into two stages, the first is the leader election process, and then the normal operations, such as log copying and bookkeeping, are carried out on the basis of the elected leader.
(1) leader election
When followers don't hear from the leader during the election time, they will be converted to candidate status. In the raft system:
1) Any server can be a candidate server as long as it sends a request to other server followers to elect itself.
2) If other servers agree, issue OK. If a follower falls down in the process and does not receive a request for election, the candidate can choose by himself at this time. As long as the majority of votes of N/2+ 1 is reached, the candidate can still become the leader.
3) In this way, the candidate becomes a leader, who can give instructions to voters, that is, followers, such as keeping accounts.
4) Notify bookkeeping by heartbeat message in the future.
5) Once the leader collapses, one of his followers becomes a candidate and sends an invitation to vote.
6) With the consent of his followers, he became a leader and continued to be responsible for bookkeeping and other guidance.
(2) Log replication
Bookkeeping steps are as follows:
1) Assuming that the leader has been selected, the client sends a request to add a log;
2) The leader asks his followers to follow his instructions and attach this new content to their respective logs;
3) After most follower servers write the transaction records into the account book, they confirm the success of adding and send out a confirmation message;
4) In the next heartbeat message, the leader will inform all followers to update the confirmed items.
Repeat the above process for each new transaction.
In this process, if there is a network communication failure, so that the leader can't access most followers, then the leader can only update the follower servers that he can access normally. Because most server followers have no leaders, they will re-elect a candidate as a leader, and then the leader will deal with the outside world as a representative. If the outside world asks them to add a new transaction record, the new leader will inform most followers according to the above steps. When the network communication is restored, the original leader will become a follower. In the phase of losing contact, any update of this old leader can't be considered as confirmation, and all must be rolled back to receive the new update of the new leader.
In the decentralized ledger system, each node that joins the system must keep a complete ledger, but each node can't keep a ledger at the same time, because the nodes receive different information in different environments. If they keep accounts at the same time, it will inevitably lead to inconsistency in the general ledger. Therefore, at the same time, which node has the accounting right is determined.
In the Bitcoin system, a power contest is held every 10 minutes, and the winner of the contest gets the right to keep the account once, and adds account book information to other nodes simultaneously.
The main feature of power system is the asymmetry of calculation. The work end has to do some difficult work to get a result, but the verifier can easily check whether the work end has done the corresponding work through the result. The requirement of this workload is to concatenate an integer value string named nonce after a string, and perform SHA256 hash operation on the concatenated string. If the hash result (expressed in hexadecimal form) starts with several 0s, the verification is passed.
If any node in the bitcoin network wants to generate a new block and write it into the blockchain, it must solve the PoW problem in the bitcoin network. The three key elements are workload proof function, block and difficulty value. The workload proof function is the calculation method of this problem, the block determines the input data of this problem, and the difficulty value determines the calculation amount needed for this problem.
(1) The workload proof function is
A block of bitcoin consists of a block header and a transaction list contained in the block. A block header with a fixed length of 80 bytes is an input string used to prove the workload of Bitcoin.
(2) The adjustment of difficulty occurs independently and automatically in each complete node. Every 20 16 blocks, all nodes will automatically adjust the difficulty according to a unified formula. The block generation rate is faster than 10 minute, which increases the difficulty, but slower than 10 minute, which reduces the difficulty.
The formula can be summarized as: new difficulty value = old difficulty value × (the time spent in the past 20 16 blocks /20 160 minutes).
Workload certification requires a target value. The formula for calculating the target value of bitcoin workload proof is: target value = maximum target value/difficulty value.
Where the maximum target value is a constant value:
0x 000000000 fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
The target value is inversely proportional to the difficulty value. The result of bitcoin workload proof is that the block hash value calculated by miners must be less than the target value.
(3) 3) Can POW solve the problem of Byzantine generals?
The power consensus algorithm of Bitcoin is a probabilistic Byzantine protocol.
When the dishonest computing power is less than 50% of the final capacity of the network and it is difficult to mine at the same time (about 10 minute for a block), the concept of achieving consistency in the bitcoin network will increase exponentially with the increase of the number of confirmed blocks. However, when the dishonest computing power has a certain scale, even if it is not close to 50%, the consensus algorithm of Bitcoin cannot guarantee the correctness, that is, it cannot guarantee that most blocks are provided by honest nodes.
Bitcoin consensus algorithm is not suitable for private chain and alliance chain. The first reason is that it is a final consensus algorithm, not a strong consensus algorithm. The second reason is that its consensus efficiency is low.
Expanding knowledge: consistency
Only under the ideal condition that there is no fault in the system and the communication between all nodes does not need any time can strict consistency be achieved. At this time, the whole system is equivalent to a machine. It is impossible to realize in reality.
Strong consistency, when the update operation in the distributed system is completed, any multiple processes or threads will get the latest values when accessing the system.
Weak consistency means that the system does not guarantee that the access of subsequent processes or threads will return the latest updated values. After the data is successfully written, the system does not promise to read the latest written value immediately, nor does it specifically promise how often to read it. But after a certain time level (level 2), it will be guaranteed as much as possible. Can make the data reach a consistent state.
Final consistency is a concrete form of weak consistency. The system guarantees that the system will eventually return the value of the last update operation without any subsequent update. In other words, if you need to access updated data after a period of time, this is the ultimate consistency.
In the stock certificate PoS model, there is a term called currency age, and each currency generates 1 currency age every day. For example, if you hold 65,438+000 coins for a total of 30 days, then your coin age is 3000. At this time, if you find a PoS block, your currency age will be cleared to 0. Every time you empty 365 coins, you will get interest of 0.05 coins from the block (assuming that interest can be understood as 5% annual interest rate), so in this case, interest = 3000 * 5%/365 = 0.4 1 coin, which is very interesting. Holding money has interest.
Peercoin is the first currency to adopt proof of equity. The rights and interests proof mechanism of counting coins combines the concepts of randomization and currency age, and coins that have not been used for at least 30 days can compete for the next piece. The longer the coin set, the bigger the possibility of signing a piece. Once you sign a block with the rights of money, the age of money will be cleared, so you have to wait at least 30 days before signing another block.
Although the PoS mechanism takes into account the shortcomings of PoW, choosing according to the equity balance will lead to the richest account having greater power and may dominate the bookkeeping right. The emergence of authorized interest certificate is based on solving the shortcomings of PoW mechanism and PoS mechanism.
Bitshare is a cryptocurrency using DPoS mechanism. Its principle is to let everyone who holds shares vote, so as to produce 10 1 representatives, which can be understood as 10 1 super nodes or mineral pools, and these1kloc-0/super nodes have completely equal rights with each other. If delegates can't perform their duties (they can't generate blocks when it's their turn), they will be removed from the list and the network will choose a new super node to replace them.
Bitshares introduces the concept of witness, who can generate blocks, and everyone who holds Bitshares can vote for the witness. The first n (n is usually defined as 10 1) candidates who get the unanimous vote can be elected as witnesses, and the number of witnesses (n) should meet the following requirements: at least half of the voters think that n has been completely decentralized.
The witness candidate list is updated once every maintenance period (1 day). Then randomly arrange witnesses, and each witness has 2 seconds to generate building blocks in sequence. If the witness server cannot generate blocks in a given time slice, the block generation permission will be granted to the corresponding witness server in the next time slice.
Bite shares also designed another kind of sports, representing sports. Elected representatives have the right to propose to modify network parameters, including transaction cost, block size, witness fee and block interval. If the majority of the delegates agree to the proposed change, shareholders have a two-week review period, during which they can recall the delegates and abolish the proposed change. This design ensures that the representative has no technical right to directly modify the parameters, and all changes of network parameters need the consent of shareholders.
Ripple (Ripple) is an open source payment protocol based on Internet. In Ripple's network, transactions are initiated by clients (applications) and broadcast to the whole network through tracking nodes or verification nodes.
The main function of the tracking node is to publish transaction information and respond to customer account book requests. The verification node not only contains all the functions of the tracking node, but also can add new account book instance data in the account book by consensus.
Ripple's consensus is reached among verification nodes, and each verification node is pre-configured with a trusted node list called UNL(Unique Node List). Nodes in the list can vote on transactions. Every few seconds, Ripple network goes through the following consensus process:
1) Each verification node will continuously receive transactions sent by the network. After verification with local ledger data, illegal transactions will be directly discarded, while legal transactions will be summarized into a candidate set. The transaction candidate set also includes the transactions left over from the previous consensus process.
2) Each verification node sends its own transaction candidate set as a suggestion to other verification nodes.
3) After receiving suggestions from other nodes, if the suggestions are not from the nodes on UNL, the verification node ignores the suggestions; If it is from a node on UNL, the transaction in the proposal will be compared with the local transaction candidate set, and if there is the same transaction, the transaction will get one vote. In a certain period of time, when the transaction gets more than 50% of the votes, the transaction enters the next round. No more than 50% of the transactions will be confirmed in the next consensus process.
4) The verification node sends the transaction with more than 50% votes as a proposal to other nodes, and at the same time, it raises the threshold of required votes to 60%, and repeats steps 3) and 4) until the threshold reaches 80%.
5) The verification node formally writes the transactions confirmed by 80%UNL nodes into the local general ledger data, which is called the last closed general ledger, that is, the last (latest) status of the general ledger.
In Ripple consensus algorithm, the identity of the voting node is known in advance. This consistency algorithm is only applicable to the case of license chain. The Byzantine Fault Tolerance (BFT) ability of Ripple consistency algorithm is (n- 1)/5, which means that 20% nodes in the whole network can tolerate Byzantine errors without affecting the correct consistency.
In the blockchain network, due to different application scenarios and different design goals, different blockchain systems adopt different consistency algorithms. Generally speaking, in the case of private chain and alliance chain, there is a strong requirement for consistency and correctness. Generally speaking, consensus algorithm with strong consistency should be adopted. However, in the case of public chain, it is usually impossible to achieve the consistency and correctness of 100%, and the consensus algorithm of ultimate consistency is usually adopted.
The choice of consensus algorithm is highly related to the application scenario. Paxos or raft can be used in trusted environment, pbft can be used in authorized alliance, pow, pos and ripple consensus can be used in unauthorized chain. The consensus mechanism can be freely selected according to the trust of the opponent.