An efficient sharding consensus algorithm for consortium chains

System flow of KBFT algorithm

The KBFT algorithm first initializes the system, resets the trust value of the node to 0, and then uses the K-prototype clustering algorithm to segment the node. Secondly, the nodes in the shard perform consensus processing on the transaction initiated by the client. If the node reaches a consensus on the transaction, the client will feed back the consensus information to the supervisory node. If the consensus in the shard fails, the shard will start the view switching protocol in the shard to re-consensus process the transaction. Then, the shard proxy node sends the local block to the global proxy node. If the global proxy receives a legal number of blocks within the specified time, it will package all the blocks into a global block and send it to all proxy nodes. At the same time, the supervisory node will score all the nodes according to the information fed back by the client. If the global proxy node does not receive a legal number of blocks within the specified time, the system will start the global view switching protocol. The system flow of KBFT algorithm is shown in Fig. 4.

System flow chart of KBFT algorithm.

Sharding of nodes

The KBFT algorithm first uses the K-prototype clustering algorithm to classify nodes according to their numerical attributes and categorical attributes. The numerical attributes include the node’s ID, credit value, etc., while the categorical attributes include the company to which the node belongs, the node’s IP address, and geographic location.

We let the node dataset be X = {X₁,X₂, X₃, …, X_n}, where n is the number of node objects in the dataset X, and each node data in the node dataset has m attributes (i.e., X_i = {X_i1, X_i2, X_i3, …, X_ip, X_i(p+1), X_{i(p + 2)}, X_im}, where there are p numerical attributes in the front and m-p categorical attributes in the back). Given a positive integer g, we divide the node dataset X into g shards. The sharding steps are as follows:

• We randomly select g nodes as the initial prototype (center point) and specify the initial prototype and the size of g according to the real application requirements in practical applications.

• The node objects are allocated to the nearest cluster according to the degree of dissimilarity, and the prototype of the cluster is updated after the allocation. The dissimilarity formula is as follows:

  $$d(x,y) = \sum\limits_{j = 1}^{p} {(x_{j} – y_{j} )^{{^{2} }} } + \gamma \sum\limits_{j = p + 1}^{m} {\delta (x_{j} ,y_{j} )}$$

  (1)

where \(\delta (x_{j} ,y_{j} ) = \left\{ {_{{1,(x_{j} \ne y_{j} )}}^{{0,(x_{j} = y_{j} )}} } \right.\) . The first term of Formula (1) is the Euclidean squared distance of the numerical attribute, and the second term is the simple matching dissimilarity on the categorical attribute.

• After the classification of the node is completed, the prototype of the category is redetermined, the mean value of the variable samples of the numerical type is considered to be the feature value of the new prototype, and the mode of the value of the variable samples of the categorical type is considered to be the new prototype feature value.

• We repeat steps (2) and (3) until no node samples change the category, and return the final sharding result.

KBFT algorithm consistency protocol process

The KBFT algorithm includes a consensus process for each shard to process corresponding transactions and a process for merging and distributing block data. The consensus process occurs first, followed by the merge and distribution process. The basic flow of the algorithm is shown in Fig. 5.

KBFT algorithm consensus protocol interaction process.

The specific algorithm steps are as follows:

• Request phase The client sends the request message to the proxy node of the shard where it is located, and the consensus on the request will be performed within the shard.

• Pre-prepare phase A proxy node within a shard constructs a new block and broadcasts the block to the rest of the consensus nodes within the shard.

• Prepare1 phase The node verifies the block, and if the verification is valid, the BLS multisignature algorithm is used to sign, and the signature is fed back to the proxy node.

• Prepare2 phase The proxy node waits and collects valid signatures from other consensus nodes. After receiving at least 2f + 1 identically signed messages (including itself), the proxy node aggregates all the individual signatures into a BLS multisignature and then broadcasts this multisignature to all nodes. At this point, the PREPARE phase ends.

• Commit1 phase The node will verify that the received multisignature contains at least 2f + 1 signers and verify the transactions in the block broadcast by the proxy node during the pre-preparation phase. The node then signs the message received in the Prepare2 phase and sends it to the proxy node.

• Commit2 phase The proxy node waits and collects at least 2f + 1 valid signatures, aggregates these signatures together to form a BLS multisignature, and submits a new block with this aggregated signature. The new block is then broadcast to all nodes to verify the commit. At this point, the COMMIT phase ends.

• Reply phase When the node submits, the node sends a reply message to the client. When the client receives at least f + 1 identical confirmation messages from different nodes, the current request has reached the final consensus.

• Feedback phase When the client receives the reply messages in the shard, the client feeds back all the reply messages to the supervisory node. The supervisory node scores the behavior of all nodes according to the feedback results of the client. The supervisory node will analyze and compare the messages sent by the client. If it is found that the message sent by a certain node is different from that sent by other nodes, or if the message sent by a certain node is not received, it can be determined that the node has malicious behavior. Thereafter the supervisory node will score the nodes based on their behavior.

• Merge-Distribute phase The proxy nodes of each shard broadcast the formed local block to the global proxy nodes. The global proxy node merges all the blocks that it receives into a global block and distributes it to each shard proxy node. The proxy node that receives the global block will send the global block to all nodes in the shard. At this point, the consistency protocol process ends.

Credit mechanism and supervision mechanism

The credit mechanism designed by the KBFT algorithm has three functions. First, the credit score adds an attribute to each node that can be used when sharding using the K-prototype clustering algorithm. Second, the credit value of each node will be changed after each consensus and will be kept by the supervisory node. When resharding, the system can quickly select the proxy nodes in the shard and the global proxy nodes according to the credit value. Finally, setting a credit mechanism can ensure that nodes work better and more honestly, thereby reducing the possibility of malicious nodes performing malicious acts. To improve the efficiency of the system, the credit mechanism designed by the KBFT algorithm is simple and efficient, and the node behavior can be quickly scored according to the node behavior without the need for a complicated score calculation process, and the supervisory node directly increases or decreases the credit value according to the behavior of the node. The credit value of honest nodes increases by 1 after each consensus, and the credit value of the nodes that do not participate in the consensus decreases by 1. The credit value of nodes with malicious behaviors will be reduced to 0 and will no longer participate in the relevant consensus before the global sharding. When a node has performed malicious acts multiple times, the node will be removed from the network and banned from joining the network. The calculation formula of the credit value is as follows.

Dynamic resharding mechanism

The KBFT algorithm uses the mechanism of dynamic resharding to manage attacks against static sharding proposed in the threat model. After the time interval set by the network ends, the system uses the K-prototype clustering algorithm to reshape all nodes in the network. After each cycle, the number of nodes in the network and the numerical and categorical attributes contained in the same node are different from those contained before. This process ensures that after node sharding with the K-prototype clustering algorithm, the sharding result is different from the previous result, thereby preventing the system from being attacked by static sharding by resharding. At the same time, in order to comply with the original intention of blockchain decentralization, the trust value of each node will be set to 0 after each dynamic resharding. Because if the trust value remains unchanged, the node with a high trust value will continue to act as a sharding proxy node or a global proxy node after sharding, which does not conform to the characteristics of blockchain decentralization. At the same time, once the proxy node fails or is attacked, it will affect the security and efficiency of the network.

Selection of shard proxy nodes and global proxy nodes

When the network is initialized, the system will randomly select or designate g nodes as the proxy nodes of each shard according to the real application. After the set period ends, the system will reshard all nodes in the network according to the information in the node information list stored by the supervisory node, and the selection of proxy nodes will no longer be random but will be based on the level of trust within the shard. Nodes with high trust degrees act as proxy nodes, which will make the system more secure and the consensus process more robust. The mechanism of selecting the global proxy nodes is similar to that of selecting the proxy nodes in the shard; thus, after selecting the proxy nodes in each shard, it will select the node with the highest credit in the selected proxy committee or select the global proxy node according to the real application.

Joining of new nodes and exiting of nodes

While performing dynamic sharding, the number of nodes in the network can be increased or decreased. New nodes can join the network, or nodes can opt out of the network at this point. The addition of new nodes will improve the scalability of the network, and an increase in the number of nodes in the network will enhance the robustness of the network. Node exit includes the active exit of a node or its removal from the network as a penalty due to malicious behavior in a previous consensus. If malicious nodes always exist in the network without processing, then malicious nodes may gradually erode other good nodes, thus affecting the security of the network.

View change

The normal operation of the KBFT algorithm is described above. However, some faults may occur during the operation of the network. For the faults in the partition, we primarily consider the behavior of the proxy nodes. Because the consensus in the partition is based on the PBFT algorithm, the algorithm can tolerate no more than one-third of the nodes doing evil concurrently. Therefore, it is more important to consider the behavior of the proxy nodes. The malfunction or mischief may be as follows:

• The proxy nodes in the shard did not broadcast the block information of the new transaction to other consensus nodes within the set time.

• After the consensus within the shard is completed, the proxy node does not send the block to the global proxy node, resulting in the global proxy node not receiving blocks with legal blocks within the set time.

• The global proxy node did not complete the work of receiving and merging and distributing the blocks of the entire network within the set time.

In response to these possible situations, the proposed algorithm sets up corresponding countermeasures to manage these situations reasonably to ensure the security and vitality of the system.

If a proxy node in a shard fails, the remaining correct nodes in the shard will choose a new proxy node by running a local view change, and then, the nodes continue to work towards reaching consensus. If the number of blocks received by the global proxy node within the specified time is less than the minimum threshold set by the network, then the system will perform an emergency resharding mechanism.

View change within a shard: The view change protocol in KBFT is not as complex as that in PBFT. When the consensus in the shard is not completed within a specified time or the replica node does not receive the message sent by the proxy node, the shard will trigger the view change protocol in the shard. The specific process is that the replica node in the shard must only send a message requesting view change to N_supervise. If N_supervise receives the same view change message sent by more than half of the nodes in the shard, N_supervise broadcasts the node with the highest trust value in the shard to the nodes and clients in the shard, and the shard consensus will restart. The flow chart of view switching within a shard is shown in Fig. 6.

Intrashard view change flowchart.

Global view change: The global view change is also called the emergency resharding mechanism, which is different from resharding after the end of the cycle set by the network. The primary difference between the two is that the trigger timing is different. Emergency resharding is triggered when the number of blocks received by the global proxy node within the specified time is less than the minimum threshold set by the network or the global proxy node does not distribute the merged blocks. Both are performed by the K-prototype clustering algorithm. However, in the emergency resharding mechanism, if the global proxy node selected after resharding is still the same as the last time, the proxy node with the second highest trust value in the proxy node set will serve as the global proxy node.