Implementation of pbft algorithm in Fabic

At present, * * * recognition algorithms can be divided into three categories: public chain, alliance chain and private chain.

Private chain, all nodes are trusted.

Alliance chain, there are point-to-point untrusted nodes.

Private chain: the * * * identification algorithm of private chain is the * * identification algorithm in traditional distributed systems before the popularization of blockchain concept, such as zab protocol of zookeeper, which is one of paxos-like algorithms. The applicable environment of private chain generally does not consider the existence of evil nodes in the cluster, but only considers the failed nodes caused by system or network reasons.

Alliance chain: In the alliance chain, the classic representative project is the Fabric project organized by Hyperledger, and the 0.6 version of Fabric uses pbft algorithm. The applicable environment of alliance chain needs to consider not only the existence of failed nodes in the cluster, but also the existence of evil nodes in the cluster. For the alliance chain, each newly added node needs to be verified and audited.

Public chain: The public chain should consider not only the faulty nodes in the network, but also the bad nodes, similar to the alliance chain. The biggest difference from the alliance chain is that the nodes in the public chain can join or quit freely without strict verification and audit.

Pow algorithm and pos algorithm are commonly used in public chain. These algorithms are directly related to the interests of participants, and solve the Byzantine problem in distributed systems through the honest work of interest-constrained nodes. Byzantine fault-tolerant algorithm is a state machine replication algorithm. Through multiple rounds of message transmission between nodes, all honest nodes in the network can reach a consistent understanding.

Byzantine fault-tolerant algorithm does not need to issue cryptocurrency, but it can only be used in private chain or alliance chain, and it needs to control the access of nodes. Can't be used on the public chain, because all nodes on the public chain can join and quit at will, and can't resist the witch attack.

Raft algorithm includes three roles: follower, candidate and leader. A node in a cluster can only be one of these three states at a certain moment, and these three roles can change with the change of time and conditions.

Raft algorithm mainly has two processes: one is leader election, and the other is log copying, in which the log copying process will be divided into two stages: recording logs and submitting data. The maximum number of fault-tolerant nodes supported by raft algorithm is (N- 1)/2, where n is the total number of nodes in the cluster.

There is an animation abroad that introduces the raft algorithm thoroughly. The link address is: /raft/. This animation mainly includes three parts. The first part introduces the simple version of the process of leader election and log replication, the second part introduces the detailed version of the process of leader election and log replication, and the third part introduces how raft algorithm restores network consistency when it encounters network partition (brain crack).

Pbft algorithm is mainly used to solve Byzantine problems.

To solve this problem, there is a very important premise that the channel must be reliable. If the channel cannot be guaranteed to be reliable, then there is no solution to the Byzantine problem. Regarding the reliability of the channel, it will lead to problems between the two armies. The conclusion of the problem between the two armies is that it is basically impossible or very difficult to try to reach an agreement through communication on an unreliable communication link.

The problem of Byzantine generals was first put forward by leslie lamport and two others in the paper The Problem of Byzantine Generals published in 1982. He proved that when the total number of generals is more than 3f and the number of traitors is F or less, loyal generals can agree on orders, that is, 3F+ 1

First, let's think about a problem. Why is the maximum number of fault-tolerant nodes in pbft algorithm (n- 1)/3, and that in raft algorithm (n- 1)/2?

For raft algorithm, the fault tolerance of raft algorithm only supports fault-tolerant nodes, not fault-tolerant evil nodes. What is a failed node? Refers to the failure of a node due to other abnormal conditions such as busy system, downtime or network problems. What is the evil node? In addition to deliberately not responding to the requests of other nodes in the cluster, evil nodes can also deliberately send wrong data, or send different data to different other nodes, so that the nodes in the whole cluster can not reach the * * * knowledge eventually. This kind of node is an evil node.

Raft algorithm only supports fault-tolerant nodes. Assuming that the total number of nodes in the cluster is n and the number of failed nodes is f, according to the principle that decimals are subordinate to the majority, normal nodes in the cluster only need one more node than F, that is, f+ 1 node, and the number of correct nodes will be more than the number of failed nodes, then the cluster can achieve * * * knowledge. Therefore, the maximum number of fault-tolerant nodes supported by raft algorithm is (n- 1)/2.

For pbft algorithm, because pbft algorithm needs to support both fault-tolerant nodes and fault-tolerant evil nodes. Suppose the number of nodes in the cluster is n, and the problematic node is F. Among the problematic nodes, it can be either a faulty node or a bad node, or just a faulty node or just a bad node. Then there will be the following two extreme situations:

In the first case, F problematic nodes are both faulty nodes and bad nodes, so according to the principle that decimals are subordinate to the majority, the normal nodes in the cluster only need one more node than F nodes, that is, f+ 1 node, and the number of confirmed nodes will be more than the number of faulty nodes, so that the cluster can achieve * * * knowledge. In other words, the maximum number of fault-tolerant nodes supported in this case is (n- 1)/2.

In the second case, the failed node and the evil node are different nodes. Then there will be f problem nodes and f failed nodes. When nodes are found to be problem nodes, they will be excluded from the cluster, leaving F failed nodes. Then, according to the principle that the decimal is subordinate to the majority, the normal node in the cluster only needs one more node than the F node, that is, f+ 1 node, and the number of confirmed nodes will be more than the number of failed nodes, so that the cluster can know. Therefore, the number of all types of nodes adds up to f+ 1 correct nodes, f failed nodes and f problem nodes, that is, 3f+1= n.

Combining the above two situations, the maximum number of fault-tolerant nodes supported by pbft algorithm is (n- 1)/3.

The basic flow of pbft algorithm mainly includes the following four steps:

The client sends a request to the master node.

The master node broadcasts the request to other nodes, and the nodes perform the three-stage identification process of pbft algorithm.

After processing the three-stage process, the node returns the message to the client.

After the client receives the same message from the f+ 1 node, it indicates that the * * * recognition has been completed correctly.

Why do you receive the same message from the f+ 1 node, indicating that * * * knowledge has been completed correctly? From the deduction in the previous section, it can be seen that in the best case or the worst case, if the client receives the same message from f+ 1 nodes, it means that enough correct nodes have all reached the * * * knowledge and have been processed.

3. The core three-stage process of the algorithm

The core three stages of the algorithm are pre-preparation, preparation and submission.

Compared with the process, for the leader election, the essence of raft algorithm is who chooses quickly, while pbft algorithm takes turns to be the main node according to the number of people. For * * * knowledge process and leader re-election mechanism, in order to describe these two algorithms more vividly, we compare the * * * knowledge process of raft and pbft to the process of how a team executes orders, and understand the difference between raft and pbft from this perspective.

A team must have a boss and ordinary members. For raft algorithm, the process of knowledge is: as long as the boss is still alive, we (ordinary members of the team) will do what the boss says and resolutely implement it. So when will you be the boss again? Only when the boss is dead will the boss be re-elected, otherwise the boss will die.

For pbft algorithm, the process of knowledge is: when the boss gives me an order, when I think there is something wrong with the boss's order, I will refuse to carry it out. Even if I think the boss's order is right, I will ask other members of the team if the boss's order is right. Only when most people (2f+ 1) think that the boss's order is right will I carry out it. When will the boss be reelected? Of course, if the boss dies, we must re-elect. If most people think that the boss is incompetent or has problems, we will re-elect the boss.

Four. conclusion

Raft algorithm and pbft algorithm are classical algorithms in private chain and alliance chain. This paper mainly introduces the process and differences between raft algorithm and pbft algorithm. Raft and pbft algorithms have two basic differences:

Raft algorithm slave nodes will not reject the request of the master node, while pbft algorithm slave nodes will reject the request of the master node in some cases;

Raft algorithm can only tolerate fault nodes, and the maximum number of fault-tolerant nodes is (n- 1)/2, while pbft algorithm can tolerate fault nodes and evil nodes, and the maximum number of fault-tolerant nodes is (n- 1)/3.

Pbft algorithm realizes * * * knowledge by voting, which can solve problems including bifurcation and improve efficiency. However, it is only applicable to the private chain of the alliance chain, because the traffic between two nodes is O (n 2) (which can be reduced by optimization), and generally it is not applicable to nodes above 100.

The premise of pbft solution is that the channel must be reliable, but the problem is poor scalability.

Part from:/kojhliang/article/details/80270223.

Blockchain is designed for BFT.