Patent ID: 12261967

DETAILED DESCRIPTION

The following clearly and completely describes the technical solutions in the embodiments of the present disclosure with reference to the accompanying drawings in the embodiments of the present disclosure. Apparently, the described embodiments are merely a part rather than all of the embodiments of the present disclosure. All other embodiments obtained by a person of ordinary skill in the art based on the embodiments of the present disclosure without creative efforts shall fall within the protection scope of the present disclosure.

It should be noted that all the directional indications (such as upper, lower, left, right, front, and back) in the embodiments of the present disclosure are merely used to explain a relative position relationship, motion situations, and the like of the components in a specific gesture (as shown in the figures). If the specific gesture changes, the directional indication also changes accordingly.

Moreover, the terms such as “first” and “second” used herein are only for the purpose of description and are not intended to indicate or imply relative importance, or implicitly indicate the quantity of the indicated technical features. Thus, features limited by “first” and “second” may expressly or implicitly include at least one of that feature. Further, the technical solutions of the embodiments may be combined with each other on the basis that the combination is implementable by those of ordinary skill in the art. In case a combination of the technical solutions is contradictory or infeasible, such a combination is deemed inexistent and not falling within the protection scope of the present disclosure.

The present disclosure provides a blockchain sharding method combining spectral clustering and a reputation value mechanism. As shown inFIG.1, the blockchain sharding method includes the following steps:Step100: Obtain, every other account grouping cycle Ta, account transaction data recorded during operation of a blockchain to generate an account transaction graph.Step200: Obtain an adjacency similarity matrix W and a degree matrix D based on the account transaction graph.Step300: Generate a Normalized Laplace matrix L based on the adjacency similarity matrix W and the degree matrix D, perform dimension reduction on L to obtain a feature matrix F, and then cluster the feature matrix F with a clustering dimension of k by row through a K-means clustering method.Step400: Divide blockchain accounts into k groups based on an obtained clustering result, and allocate accounts in the k groups to k blockchain shards.

The present disclosure obtains, every other account grouping cycle Ta, the account transaction data recorded during operation of the blockchain to generate the account transaction graph; and obtains the adjacency similarity matrix W and the degree matrix D based on the account transaction diagram. In this way, a correlation between accounts can be calculated, and whether there are lots of transactions between accounts can be evaluated. Then, the blockchain accounts are clustered by a spectral clustering algorithm, and accounts with lots of transactions with each other are allocated to a same group. The blockchain accounts are divided into the k groups based on the clustering result, and the accounts in the k groups are allocated to the k blockchain shards. The present disclosure can reduce a probability of a CST between shards, thereby reducing a loss caused by the CST and improving transaction processing efficiency of a blockchain network.

Preferably, the obtaining an adjacency similarity matrix W and a degree matrix D based on the account transaction graph in step200includes the following substeps:Step210: Set each account in the account transaction graph as a vertex V.Step220: Measure a relation degree of any pair of vertices Viand Vjbased on a similarity coefficient according to the following formula:

wij=E⁡(i)⋂E⁡(j)E⁡(i)⋃E⁡(j),
wherei and j are different, i,j=1, 2, . . . , n, E(i) and E(j) represent edge sets of vertex Viand vertex Vjrespectively, E(i)∩E(j) represents an intersection of edges of vertex Viand vertex Vj, namely, an edge between vertex Viand vertex Vj, and E(i)∪E(j) represents a union of the edges of vertex Viand vertex Vj.Step230: Form the adjacency similarity matrix W based on the relation degree wijbetween every two vertices in the account transaction graph, where W=(wij)i,j=1,2, . . . , n,Step240: Define dias a degree of vertex Viaccording to a formula di=Σj=1nwij.Step250: Define degrees of all vertices in the account transaction graph as the degree matrix D, where D=(dij)i,j=1,2, . . . , n.

Preferably, the generating a Normalized Laplace matrix L based on the adjacency similarity matrix W and the degree matrix D, performing dimension reduction on L to obtain a feature matrix F, and then clustering the feature matrix F with a clustering dimension of k by row through a clustering method in step300specifically includes the following substeps:Step310: Calculate the Normalized Laplace matrix L, where L=I−D−1W, and I represents an identity matrix.Step320: Calculate eigenvectors f corresponding to k1minimum eigenvalues of the obtained Laplace matrix L, and normalize a matrix constituted by the eigenvectors f to form the n×k1feature matrix F.Step330: Cluster the feature matrix F with the clustering dimension of k by row through the K-means clustering method, where each row in F is used as a k1-dimensional sample, and there are a total of n samples.

Preferably, after the dividing blockchain accounts into k groups based on an obtained clustering result, and allocating accounts in the k groups to k blockchain shards in step400, the blockchain sharding method further includes the following steps:Step500: Rate reputations of all nodes in the blockchain based on a reputation value corresponding to each node.Step510: Evenly allocate all the nodes in the blockchain to each shard every other node sharding cycle Tsbased on a reputation rating of each node.Step520: Select a notarization node of a CST based on the reputation rating of each node.Steps500to520are content of a dynamic reputation value mechanism. The dynamic reputation value mechanism is constituted by a node division mechanism, a node state transition mechanism, and a notarization window sliding mechanism.

Based on the dynamic reputation value mechanism, a reputation of each node in the blockchain is dynamically rated based on a transaction processing speed and a behavior honesty degree of the node, and a reputation rating of the node is taken as a standard to select the best among all nodes as the notarization node of the CST and evenly allocate all the nodes in the blockchain network to each shard based on the reputation rating of each node. This ensures security of transaction processing of each blockchain shard, guarantees a performance balance among blockchain shards, and improves overall performance of the network.

Preferably, step500specifically includes the following substeps:Step501: After p rounds of blockchain transaction processing, rate the reputation of each node in the blockchain based on the reputation value corresponding to the node, rate a node whose reputation value rank in all the nodes in the blockchain is greater than a first preset value as A, rate a node whose reputation value rank in all the nodes in the blockchain is less than a second preset value and greater than a third preset value as B, and rate a node whose reputation value rank in all the nodes in the blockchain is less than a fourth preset value and greater than a fifth preset value as C.Step502: Determine a remaining unrated node in the blockchain as an ordinary node, and rate the ordinary node as D.

Preferably, step520specifically includes:selecting all nodes whose reputation ratings are A as notarization execution nodes, all nodes whose reputation ratings are B as notarization inspection nodes, and all nodes whose reputation ratings are C as candidate nodes, where there are two types of notarization nodes: the notarization execution node and the notarization inspection node, which form a notarization window, and one notarization execution node and one notarization inspection node form a notarization node pair.

Specifically, as shown inFIG.2, the nodes are divided after p rounds of random blockchain transaction processing (a value of P is dynamically set based on security needs). For the nodes in the blockchain network, the reputation of each node is rated based on a latest reputation value of the node. Among all nodes ranked in descending order based on reputation values, the top %5 of the nodes are rated as A, nodes with reputation value rankings less than those of the top 5% of the nodes and greater than those of the top 10% of the nodes are rated as B, nodes with reputation value rankings less than those of the top 10% of the nodes and greater than those of the top 20% of the nodes are rated as C, and remaining nodes are ordinary nodes whose reputation ratings are D. All the nodes whose reputation ratings are A are selected as the notarization execution nodes, all the nodes whose reputation ratings are B are selected as the notarization inspection nodes, and all the nodes whose reputation ratings are C are selected as candidate nodes. All the notarization inspection nodes and notarization execution nodes are collectively referred to as notarization nodes and form the notarization window. The content executed in the above steps500and520is the node division mechanism.

Preferably, the reputation value is γ, and includes an efficiency score h of the node and an honesty degree score t of the node, where γ can be obtained according to a formula

γ=2·h·th+t.

Before step500, the blockchain sharding method further includes the following steps:Step401: For each node in the blockchain, give a processing speed score h′newof the node for a current round of transaction processing based on time consumed by the node to complete the current round of transaction processing, and calculate an updated node efficiency score

hn⁢e⁢w=hbf+hn⁢e⁢w′2
based on a previous-round efficiency score hbfof the node and the processing speed score h′newof the node for the current round of transaction processing.Step402: For each node in the blockchain, if the node correctly completes the current round of transaction processing, increase the honesty degree score of the node by a score q; or if the node performs a malicious operation in the current round of transaction processing, decrease the honesty degree score of the node by a score r.Step403: Calculate an updated honesty degree score tnew=tbf+q−r of the node based on a previous-round honesty degree score tbfof the node, as well as the score q and the score r in the current round of transaction processing, where when each node joins the blockchain network, the node is assigned with a basic efficiency score h0and a basic honesty degree score t0, and when the node is a newly added node, the previous-round efficiency score hbfof the node is h0, and the previous-round honesty degree score tbfof the node is t0.

Specifically, the node is assigned the basic efficiency score h0and the basic honesty degree score t0when joining the blockchain network. It is assumed that an efficiency score and a honesty degree score of a node before each round of transaction processing are hbfand tbfrespectively. When the node is a newly added node, a previous-round efficiency score hbfof the node is h0, and previous-round honesty degree score tbfof the node is t0. After each round of blockchain transaction processing, the efficiency score and the honesty degree score of each node are updated to hnewand tnewrespectively. Therefore, after a round of blockchain processing, methods for updating the efficiency score and the honesty degree score of each node are as follows:

Updating of the efficiency score of the node: The processing speed score h′newof the node for the current round of transaction processing is given based on the time consumed by the node to complete the current round of transaction processing. Therefore, based on processing speeds of the node for a previous round of transaction processing and the current round of transaction processing, the efficiency score of the node is updated according to a formula

hn⁢e⁢w=hbf+hn⁢e⁢w′2.

Updating of the honesty degree score of the node: If the node correctly completes the current round of transaction processing, the honesty degree score of the node is increased by the score q; or if the node performs a malicious operation in the current round of transaction processing, the honesty degree score of the node is decreased by the score r. Therefore, the honesty degree score of the node is updated according to a formula tnew=tbf+q−r.

Preferably, the node state transition mechanism is as follows:A node whose reputation rating is D is an ordinary node, and can only participate in an intra-shard transaction consensus process without other functional rights; a node whose reputation rating is C is a candidate node, and can be upgraded to a notarization inspection node; a node whose reputation rating is B is a notarization inspection node, and the notarization inspection node can check and control behavior of the notarization execution node, and can be upgraded to a notarization execution node; and a node whose reputation ranking is A can be used as a notarization execution node to process the CST.

Preferably, a role of the node is dynamically transferred, which is mainly related to behavior of the node during transaction processing. During transaction processing, if the node fails or sends a message inconsistent with messages sent by most nodes, the reputation value of the node is decreased accordingly. Therefore, after step520, the blockchain sharding method further includes the following steps:Step521: Select, every other notarization window sliding cycle Tw, half of all notarization execution nodes according to a first preset rule, and degrade all the selected notarization execution nodes to ordinary nodes, where the first preset rule is that a notarization execution node with a smaller reputation value can be selected at a greater probability.

Step522: Select a plurality of nodes from all the notarization inspection nodes according to a second preset rule to supplement the degraded notarization execution nodes in the previous process, and upgrade all the selected notarization inspection nodes to notarization execution nodes, where the second preset rule is that a notarization inspection node with a larger reputation value can be selected at a greater probability. Specifically, since reputation value rating is performed based on a ranking ratio of reputation values, the notarization inspection node selected to supplement the degraded notarization execution node whose rating is A is originally rated as B. Therefore, a reputation value of the selected notarization inspection node further needs to be increased to a lowest reputation value corresponding to the node whose rating is A (namely, a lowest score of the top 5% of reputation values of all the nodes in the blockchain).Step523: Select a plurality of nodes from all candidate nodes according to a third preset rule to supplement the upgraded notarization inspection nodes in the previous process, and upgrade all the selected candidate nodes to notarization inspection nodes, where the third preset rule is that a candidate node with a larger reputation value can be selected at a greater probability. Specifically, since reputation value rating is performed based on the ranking ratio of the reputation values, the candidate node selected to supplement the degraded notarization inspection node whose rating is B is originally rated as C. Therefore, a reputation value of the selected candidate node further needs to be increased to a lowest reputation value corresponding to the node whose rating is B (namely, a lowest score of the top 10% of the reputation values of all the nodes in the blockchain).

The content executed in the above steps521to523is the notarization window sliding mechanism.

Preferably, each node in shards receives an initiated transaction from external request source, and each node verifies and determines the above transaction. If it is determined that the transaction is a CST, the CST is submitted to the notarization window (a node in the notarization window is a public node and belongs to all shards in the network). The notarization window is constituted by a plurality of notarization nodes (the notarization nodes include the notarization execution node and the notarization inspection node). After the CST is submitted to the notarization window, a rotating notarization node pair (consisting of one notarization execution node and one notarization inspection node) in the notarization window processes the CST. Therefore, as shown inFIG.3andFIG.4, after the dividing blockchain accounts into k groups based on an obtained clustering result, and allocating accounts in the k groups to k blockchain shards in step400, the blockchain sharding method further includes:performing, by the notarization execution node in the rotating notarization node pair, the following steps:step600: decomposing content of the CST to obtain a source shard sub-transaction and a target shard sub-transaction;step610: packaging the source shard sub-transaction, submitting the packaged source shard sub-transaction to a source shard for transaction consensus processing, and completing an operation, of the CST, corresponding to a source shard ledger; andstep620: packaging the target shard sub-transaction, submitting the packaged target shard sub-transaction to a target shard for transaction consensus processing, and completing an operation, of the CST, corresponding to a target shard ledger; andperforming, by the notarization inspection node in the rotating notarization node pair, the following steps:step630: querying and verifying states of the source shard ledger and the target shard ledger based on the content of the CST; andstep640: if the states of the source shard ledger and the target shard ledger match a target state of the CST, determining that the CST is in a completed state; or if the states of the source shard ledger and the target shard ledger do not match a target state of the CST, determining that the CST is in an error state, and broadcasting a CST rollback message to the source shard and the target shard, such that the source shard and the target shard roll back the CST.

Based on a CST notarization mechanism, the notarization execution node decomposes and processes the CST, and then the notarization inspection node verifies the ledger state after the CST is completed, and performs a corresponding operation based on a verification result to ensure atomicity and security of the CST.

Preferably, after the dividing blockchain accounts into k groups based on an obtained clustering result, and allocating accounts in the k groups to k blockchain shards in step400, the blockchain sharding method further includes the following step:Step700: Before performing CST processing each time, select one notarization execution node and one notarization inspection node from the notarization window according to a fourth preset rule and the reputation value of each node in the notarization window to form the rotating notarization node pair, where the fourth preset rule is that a notarization execution node and a notarization inspection node that have a larger reputation value in the notarization window can be selected as the notarization node pair at a greater probability. The content executed in the above step700is a rotating mechanism for notarization window sliding.

The above are only specific implementations of the present disclosure, such that those skilled in the art can understand or realize the present disclosure. Various modifications to these embodiments are readily apparent to a person skilled in the art, and the generic principles defined herein may be practiced in other embodiments without departing from the spirit or scope of the present disclosure. Thus, the present disclosure is not limited to the embodiments shown herein but falls within the widest scope consistent with the principles and novel features disclosed herein.