Shulou(Shulou.com)06/01 Report--

How to carry out PBFT consensus algorithm analysis and Java implementation? in view of this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

Detailed Analysis of PBFT consensus algorithm and Java implementation Why to write this

Recently, we have studied some things related to the blockchain, in fact, there are only three blocks:

Distributed storage (de-centralization)

Consensus mechanism

Secure encrypted distributed storage is a distributed database in which each node keeps a copy. Through asymmetric secret key, hash and other technologies, the operation data is signed, the abstract is verified, traceable, stored in chain structure, and the data is verified by hash summary to prevent tampering. The Byzantine fault-tolerant consensus algorithm is used to solve the communication between nodes and reach an agreement.

Brief introduction of Block chain Protocol

Distributed consensus algorithm is the core of distributed system, such as Paxos, pbft, bft, raft, pow and so on. The common ones in blockchain are POW, POS, DPOS, pbft and so on. Where:

POW, POS and DPOS are open consensus protocols.

PBFT is a semi-open consensus protocol.

Paxos, raft, etc. are closed consensus protocols.

Difference:

Open, it is impossible to know exactly how many nodes and connection status, each node may be malicious, but most of them are non-malicious

Semi-open, can determine the number of nodes and connection status, each node may be malicious, but there are non-malicious nodes that meet certain conditions

Closed, where each node is non-malicious, but may be disconnected or crash.

Performance: higher and higher from top to bottom

Summary:

Private chain is a closed ecological storage system, and Paxos and raft are the best.

The federation chain is semi-open and semi-open, so the Byzantine fault-tolerant PBFT algorithm is more suitable.

As far as public chain is concerned, POW, POS and DPOS are suitable high security protocols.

So, what we want to talk about is the consensus protocol of the nature of alliance chain: PBFT algorithm protocol. It has been a long time since the birth of the agreement, and there are a lot of articles on the Internet, but they are basically translated original papers, with a little personal reading experience, detailed analysis is still relatively few, some key connecting points are not clearly stated, and they seem to understand at a rough glance. But if you really want to achieve it, there are still more holes. So I use the way of demo, multi-thread simulation of multi-node, to achieve a complete PBFT algorithm, in which there are some problems, recorded for your reference, discussion.

Brief introduction of PBFT algorithm simple steps of PBFT protocol:

There are three main stages: preparation (pre-prepare), preparation (prepare), and confirmation (commit)

A master node (Leader) is selected from the nodes of the whole network, and the new block is generated by the master node.

The client of one of the nodes initiates a request to the primary node.

Pre-Prepare: the primary node assigns a sequence number n to the received request (guarantee of order! ) and broadcast to the whole network.

Prepare: after receiving the transaction request, each node simulates the execution of these transactions to verify the correctness of the transaction message. After the verification is passed, it is stored in the preparatory list and broadcast to the whole network.

Commit: if a node receives 2f (f is the tolerable number of Byzantine nodes), the PREPARE message digest sent by other nodes is equal to itself, and a commit message is broadcast to the whole network.

Reply: if a node receives a 2f+1 commit message, it can submit the new chunk and its transaction to the local blockchain and status database (operation confirmation is complete).

Analysis of problems

The whole agreement is relatively simple to understand, but there are many problems that need to be analyzed one by one.

How is the master node generated?

What if the master node fails?

What if the master node is faked?

How to retransmit the data?

Generation of master node

Because the operation of the node needs to go through the master node, the first thing after each node starts, find the master node. The primary node is calculated by the formula p = v mod | R |, where v is the view number, p is the copy number, and | R | is the number of copies set. So actually finding the master node is initializing the view view.

Webcast View acquisition Protocol:

Public static final int VIEW =-1

The view replied by the node that exceeds the 2f+1 serves as the initialized view (Q1: what if it cannot be satisfied?)

If (this.viewOk) return;long count = vnumAggreCount.incrementAndGet (msg.getVnum ()); if (count > = 2*maxf+1) {vnumAggreCount.clear (); this.view = msg.getVnum (); viewOk = true; System.out.println ("View initialization completed [" + index+ "]:" + view);} the primary node fails (here failure means that the application hangs up or is controlled by others to do evil)

Who first found that the master node failed, of course, it cannot be seen through the disconnection here, because even if the tcp connection is normal, the business processing may not be normal. The answer is timeout control. When the node initiating the request does not complete the operation confirmation within the timeout period, it can be suspected that the primary node is invalid, so:

Since the client broadcasts timeout request messages across the network, why not use a special packet to initiate an invalidation proposal? The main purpose is to prevent the node that initiates the request from doing evil, such as looping the proposal. It leads to continuous proposal testing, leading to network congestion.

The replica node checks that if it has been dealt with (indicating that it may be a network problem), the processing result can be returned again. If it is not handled, the primary node may be down, the request will be reforwarded to the primary node, and the timeout check will be added. At this point, if the primary node is normal, then the normal process will be followed and the operation request will eventually be confirmed. If there is a real problem with the primary node, the set timeout will trigger

Proposal for handover of network-wide broadcast master node after timeout

If (! this.viewOk) return; / / has started to elect the view. Do not repeatedly initiate this.viewOk = false;// as the replica node. Broadcast view change voting PbftMsg cv = new PbftMsg (CV, this.index); cv.setVnum (this.view+1); PbftMain.publish (cv)

When each node receives 2f+1 proposals for the same view, it switches to a new view. And check whether there are any requests to be sent, and everything returns to normal logic:

Long count = vnumAggreCount.incrementAndGet (msg.getVnum ()); if (count > = 2*maxf+1) {vnumAggreCount.clear (); this.view = msg.getVnum (); viewOk = true; System.out.println ("View change completed [" + index+ "]:" + view); / / you can continue to request if (curMsg! = null) {curMsg.setVnum (this.view) System.out.println ("request retransmission [" + index+ "]:" + curMsg); doSendCurMsg ();}}

When proposing, if a malicious node is initiated repeatedly, each node can only vote once if it needs to be detected.

String vkey = msg.getNode () + "@" + msg.getVnum (); if (votes_vnum.contains (vkey)) {return;} votes_vnum.add (vkey); cleanup status

When the commit is passed and the operation is confirmed, you can clean up the status related to the message:

/ / cleanup request related status private void remove (String it) {votes_pre.remove (it); votes_pare.removeIf ((vp)-> {return StringUtils.startsWith (vp, it);}) Votes_comm.removeIf ((vp)-> {return StringUtils.startsWith (vp, it);}); aggre_pare.remove (it); aggre_comm.remove (it); timeOuts.remove (it);} other key points

The DataKey of a PbftMsg message must be unique and can be defined through uuid or other means

Private int type; / / message type private int node; / / Node private int onode; / / Node private int vnum; / / View number private int no; / / Serial number private long time; / / timestamp private String data / data, the hash that represents the data, the only answer to the question on how to analyze the PBFT consensus algorithm and the implementation of Java is shared here. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel for more relevant knowledge.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.