CN111935207A - Block chain system consensus method based on improved C4.5 algorithm - Google Patents

Abstract

The invention discloses a consensus method for a blockchain system based on an improved C4.5 algorithm, including a first-level consensus layer consensus: a slave node in a group sends a request to a master node, and the master node packages several requests after receiving the requests for a period of time A block is then broadcast to the group to which it belongs for a PBFT consensus; the second-level consensus layer consensus: after the block passes the consensus verification process of the first-level consensus layer, a second PBFT consensus will be performed at the second-level consensus layer confirm. The K nodes in the second-level consensus layer elect a master node through the point voting mechanism, and the node will package the requests collected during this period that have passed the consensus of the first-level consensus layer into a block and broadcast it to the second-level consensus layer. All nodes of PBFT consensus.

Description

Consensus method of blockchain system based on improved C4.5 algorithm

technical field

The invention belongs to the technical field of blockchain systems, and in particular relates to a consensus method for a blockchain system based on an improved C4.5 algorithm.

Background technique

Blockchain is a decentralized distributed system with the characteristics of openness, traceability, decentralization and immutability. Consensus algorithm is the core of blockchain technology, which directly affects the scalability of the blockchain system. Blockchain can be divided into public chain, private chain and alliance chain. The consensus algorithm commonly used in alliance chain is Practical Byzantine Fault Tolerance (PBFT). PBFT is an algorithm used to solve Byzantine generals problem, which can exist in the network. In the case of malicious nodes, the consistency between each node is guaranteed. Figure 1 is a schematic flow chart of the existing PBFT algorithm. The PBFT consensus algorithm is mainly composed of a consensus protocol, a view replacement protocol and a checkpoint protocol. Consistency protocol is used to ensure the consistency of data saved by all nodes in the whole network, which is realized by mutual communication between nodes in three stages; view replacement protocol is used to replace faulty nodes to ensure the normal operation of the system; checkpoint protocol is used to periodically clean up Expired interactive data reduces the storage pressure of nodes, regularly checks whether the system is unified, and synchronizes inconsistent nodes. However, the existing Byzantine fault-tolerant algorithms either have poor scalability and low fault-tolerance rate, or the random selection of the master node will cause the view change process and affect the entire consensus process. Network congestion. How to improve the existing PBFT algorithm is the premise of large-scale blockchain application.

The present invention has been made in view of this.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to overcome the deficiencies of the prior art and provide a consensus method based on the improved C4.5 algorithm block chain system. In order to solve the above technical problems, the basic concept of the technical solution adopted in the present invention is:

Based on the improved C4.5 algorithm blockchain system consensus method, including the first-level consensus layer consensus: the slave node in the group sends the request to the master node, and after receiving the request for a period of time, the master node packages several requests into a block , and then broadcast the block to the group it belongs to for a PBFT consensus; the second-level consensus layer consensus: After the block passes the consensus verification process of the first-level consensus layer, it will be confirmed by the second-level PBFT consensus at the second-level consensus layer. The K nodes in the second-level consensus layer elect a master node through the point voting mechanism, and the node will package the requests collected during this period that have passed the consensus of the first-level consensus layer into a block and broadcast it to the second-level consensus layer. All nodes in the PBFT consensus; if there is no new request from the first-level consensus layer during this period, the node will pack an empty block and send it to the second-level consensus layer consensus chain, and then conduct the next election; submission stage: when the district After the block has passed the consensus of the secondary consensus layer, all master nodes will digitally sign the block and collect digital signatures from other master nodes, indicating that they agree with the authenticity and validity of this block; The set of digital signatures attached to the block itself is packaged into a submission message and broadcast to all slave nodes in the first-level consensus layer to which it belongs, indicating that the block can be chained. So far, the nodes of any level of consensus layer will receive the commit message of this block; in the execution stage: after receiving the commit message from the master node, the slave node verifies the set of digital signatures attached to the block, and can determine the block Whether it has passed the consensus verification of the secondary consensus layer. If the verification fails, it can be considered that the master node to which the slave node belongs has malicious behavior, and the illegal operation can be reported to achieve the role of the slave node's upward supervision; if the verification is successful, the request content of this block can be executed, and the block Block records are on the chain.

After adopting the above technical solution, the present invention has the following beneficial effects compared with the prior art.

The invention ensures the reliability of the main node to a certain extent, reduces the number of view switching, and thus achieves higher consensus efficiency. At the same time, the global decentralized consensus is improved to a hierarchical multi-centralized consensus through node grouping, which effectively alleviates the simple use of The PBFT algorithm increases the number of nodes and the communication volume is too large, which improves the honest probability of the master node, reduces the consensus time between nodes, and improves the consensus efficiency.

The specific embodiments of the present invention will be described in further detail below with reference to the accompanying drawings.

Description of drawings

The accompanying drawings are used as a part of the present application to provide a further understanding of the present invention, and the exemplary embodiments of the present invention and their descriptions are used to explain the present invention, but do not constitute an improper limitation of the present invention. Obviously, the drawings in the following description are only some embodiments, and for those of ordinary skill in the art, other drawings can also be obtained from these drawings without any creative effort. In the attached image:

Fig. 1 is the flow chart of the existing PBFT algorithm;

Figure 2 is a decision tree model diagram;

Figure 3 is a two-layer blockchain network diagram after nodes are grouped;

Figure 4 is a flowchart of the improved PBFT.

It should be noted that these drawings and written descriptions are not intended to limit the scope of the present invention in any way, but to illustrate the concept of the present invention to those skilled in the art by referring to specific embodiments.

Detailed ways

In order to make the purposes, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and the following embodiments are used to illustrate the present invention , but are not intended to limit the scope of the present invention.

Example

C4.5 decision tree is a classic decision tree algorithm. The model is shown in Figure 2. It determines the features to be classified by calculating and comparing the information gain rate of each feature. The basic process is as follows:

(1) Suppose the sample set S has s training samples, divide the sample set into m classes, the number of instances of the i-th class is S _i , S _i /s is the probability P _i , Info(S) is the class information entropy, Its calculation formula is:

(2) If feature A is selected as a splitting feature, the sample set S is divided into k subsets {S ₁ , S ₂ ,...,S _k }, and feature A has k uncorrelated values {α ₁ , _{α 2 , . _}

是S_j中第i类的样本概率。in,

is the sample probability of class i in S _j .

(3) Calculate the information gain of conditional attribute A:

Gain(A, S)=Info(S)-Info _A (S) (3)

(4) The conditional attribute A is used as the dividing standard to divide the training set S into k subsets, a _i corresponds to the number of samples in the training set S _j , and the information entropy of the attribute A in the sample S is:

(5) The information gain rate of attribute A is:

In order to make the C4.5 algorithm more suitable for the blockchain model, this embodiment improves it. The traditional C4.5 algorithm is prone to redundant rules when generating a decision tree, the size of the decision tree is too large, and the classification speed is too slow. question. Combined with the actual application scenario of the blockchain consensus mechanism, in the PBFT consensus mechanism, the data information carried by the attribute values of some existing nodes is similar. This embodiment proposes an improved C4.5 decision tree algorithm based on cosine similarity. , as in formula (6). If the difference between the information entropy of any two attribute values is within a small range, as shown in formula (7). Calculate the cosine similarity of two attribute values, and combine the attribute values whose similarity is within the threshold range, as shown in formula (8). The algorithm can effectively reduce the size of the decision tree, reduce redundant rules, and improve the classification speed.

Among them, the smaller the η, the better, generally not more than 0.1, here η = 0.1

The improved C4.5 basic process is as follows:

(1) Calculate the information entropy of each attribute value in the node attribute and the information gain rate of the attribute;

(2) According to formula (7), compare whether there is an attribute value pair whose information entropy is within the threshold range in the attribute value of each attribute, if there is, calculate (3), otherwise go to (6);

(3) Calculate the cosine similarity value of the two attribute value pairs according to formula (6). If it is greater than the threshold value of 0.9, it means that the two vectors have high similarity, then go to (4), otherwise go to (6);

(4) Combine the two attribute value vectors into a new attribute value vector according to formula (8), and the new vector represents a new subset and a new attribute value. Then delete the original attribute value in the attribute that participated in the comparison, and add a new attribute value to form a new attribute;

(5) Recalculate the information entropy and information gain rate of the attribute according to the modified attribute;

(6) Select the attribute with the largest information gain rate from the attribute set as the split attribute.

The C4.5 algorithm is combined with the PBFT consensus mechanism, and the decision tree algorithm is used to evaluate and classify the consensus nodes participating in the consensus, which are numbered as {0,1,…,M-1} according to the level of trust. On the basis of the classification of trust evaluation, sampling and grouping are carried out in proportion to K. The first K nodes in the evaluation of trust level are the main nodes of each group. The model is shown in Figure 3. Each node in the group saves a list. The address of a node in the group will appear above, and this address identifies these nodes as the same group. There is an upper limit M/K for the number of nodes in this group. When a new node a joins, it sends its own request to the network, attaches the public key P, and then enters the waiting state. After receiving the request information from the new node, the master node b in the network determines that the number of nodes in its own group has not yet arrived. The upper limit, will accept the joining information with a timestamp, and the public key S of the node, encrypt it with P, and transmit it to the secondary consensus layer in the form of a message. After receiving the confirmation message ( It may receive multiple packets at the same time, the one with the earliest timestamp is the main one), determine to join the group, and send a receipt packet, using S encryption. After receiving the message, b broadcasts it to the entire group of nodes, updates the node list, and synchronizes the latest node list to node a, and a then synchronizes all the data of the blocks in the entire network. When a node c exits, the node c needs to submit an exit application with the public key S to the master node d in the group, and the master node d accepts the exit information with the timestamp and the public key S of the node, encrypts it with P, and uses the message Submit an exit application to the secondary consensus layer in the form of an exit application. After the other master nodes agree to the consensus, they will send a receipt message and use S encryption. The master node d sends the information of node c to the group to update the node connection information in its own group. When it is confirmed that the 2f+1 nodes in the group have completed the update, node c will actually exit the blockchain network.

In the secondary consensus layer, in order to further reduce the probability of malicious nodes becoming master nodes, the selection of master nodes adopts a point voting mechanism. The voting results are calculated as:

T=Number of votes*α+Point value*β(α+β=1) (9)

Where T is the final score, α, β are different correction parameters set according to the change of the integral value of the node. 0≤α, β≤1.

1. Calculation of integral value: When the system is initialized, an integral value of 50 points will be assigned to each node. If a node successfully produces a block within a cycle and is verified to be valid, the system will reward 10 points of points; if the node fails to complete the block within the specified time, the system will deduct 10 points. The integral value will gradually accumulate with the behavior of the node. At this time, in order to avoid the excessive gap between the rich and the poor in the integral value, the integral threshold is set to 200 points. After 200 points, the system resets the integral value to 50.

2. Regarding the maintenance of the score table, select the node with the highest trust level in the alliance chain as the authoritative node to maintain the score table. When the node successfully reaches the consensus, the hash value of the successful consensus content will be used as evidence to bind the score, and the authoritative node will The hash value will be verified. If the verification is passed, the node will accumulate points. If the verification fails, the node points will be deducted according to the node address. Finally, before the next stage of consensus starts, the points in the points table will be added to all nodes. The 1-point operation completes the establishment of the point system in the maintenance process of the point table. On the one hand, from the perspective of game theory, the punishment and reward mechanism reduces the impact of malicious nodes on the consensus of the blockchain system; Further reduce the possibility of masternodes doing evil.

The flowchart of the improved PBFT consensus algorithm is shown in Figure 4. The main process stages are as follows:

(1) First-level consensus layer consensus: slave nodes in the group send requests to the master node. After receiving requests for a period of time, the master node packages several requests into a block, and then broadcasts the block to the group to which it belongs for a PBFT consensus.

(2) Second-level consensus layer consensus: After the block passes the consensus verification process of the first-level consensus layer, the second PBFT consensus confirmation will be performed at the second-level consensus layer. The K nodes in the second-level consensus layer elect a master node through the point voting mechanism, and the node will package the requests collected during this period that have passed the consensus of the first-level consensus layer into a block and broadcast it to the second-level consensus layer. All nodes in the PBFT consensus; if there is no new request from the first-level consensus layer during this period, the node will pack an empty block and send it to the second-level consensus layer consensus chain, and then conduct the next election.

(3) Submission stage: After the block has passed the consensus of the secondary consensus layer, all master nodes will digitally sign the block and collect digital signatures from other master nodes, indicating that they agree with the authenticity and validity of the block ; and then package the digital signature set of the second-level consensus layer with the block itself into a submission message and broadcast it to all slave nodes in the first-level consensus layer to which it belongs, indicating that the block can be put on the chain. So far, the nodes of any level of consensus layer will receive the commit message of this block.

(4) Execution stage: After the slave node receives the submission message from the master node, it verifies the set of digital signatures attached to the block to determine whether the block has passed the consensus verification of the secondary consensus layer. If the verification fails, it can be considered that the master node to which the slave node belongs has malicious behavior, and the illegal operation can be reported to achieve the role of the slave node's upward supervision; if the verification is successful, the request content of this block can be executed, and the block Block records are on the chain.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention in any form. Although the present invention has been disclosed above with preferred embodiments, it is not intended to limit the present invention. Within the scope of the technical solution of the present invention, personnel can make some changes or modifications to equivalent examples of equivalent changes by using the above-mentioned technical content, but any content that does not depart from the technical solution of the present invention is based on the technical solution of the present invention. Substantially any simple modifications, equivalent changes and modifications made to the above embodiments still fall within the scope of the solutions of the present invention.

Claims (1)

1. The block chain system consensus method based on the improved C4.5 algorithm is characterized by comprising a first-level consensus layer consensus: the method comprises the following steps that a slave node in a group sends a request to a master node, the master node packs a plurality of requests into a block after receiving the request for a period of time, and then broadcasts the block to a group to which the block belongs to carry out PBFT consensus for one time; and (3) second-level consensus layer consensus: after the block passes the consensus verification process of the first-level consensus layer, the second-level consensus layer is subjected to the PBFT consensus confirmation. K nodes in the secondary consensus layer elect a main node through an integral voting mechanism, and the node packs the collected requests passing through the consensus of the primary consensus layer in the period of time into a block and broadcasts the block to all nodes of the secondary consensus layer for PBFT consensus; if the primary common-identification layer has no new request in the period of time, the node packs a vacant block and sends the vacant block to the secondary common-identification layer common-identification uplink, and then the next election is carried out; a submission stage: after the block is subjected to the consensus of the secondary consensus layer, all the main nodes carry out digital signature on the block and collect digital signatures from other main nodes to represent the authenticity and the effectiveness of the block; then, the block attached to the digital signature set of the secondary common identification layer is packaged into a submit message which is broadcast to all the slave nodes in the primary common identification layer to which the submit message belongs, so that the block can be subjected to uplink operation. The node of any level of the consensus layer receives the submission message of the block; an execution stage: after receiving the submitted message from the master node, the slave node verifies the digital signature set attached to the block, and can judge whether the block is subjected to consensus verification of the secondary consensus layer. If the verification fails, the master node to which the slave node belongs can be considered to have malicious behaviors, and the illegal operation can be reported, so that the effect of upward supervision of the slave node is achieved; if the verification is successful, the requested content for the block can be executed and the block is recorded for uplink.

Images