CN115567542B

CN115567542B - Method and device for maintaining node set

Info

Publication number: CN115567542B
Application number: CN202211530168.4A
Authority: CN
Inventors: 焦梦洪
Original assignee: Hangzhou Ant Love Technology Co ltd
Current assignee: Hangzhou Ant Love Technology Co ltd
Priority date: 2022-12-01
Filing date: 2022-12-01
Publication date: 2023-03-10
Anticipated expiration: 2042-12-01
Also published as: CN115567542A

Abstract

A method and a device for maintaining a node set are provided. The method is applied to any block chain node, each block chain node and 2 in the block chain network constructed based on the structured P2P network ⁿ At least part of leaf nodes in the fork tree correspond to each other one by one, the XOR distance between any two block chain nodes is calculated by the node identification of the corresponding leaf node, and n is a positive integer; the node set corresponding to any preset value is used for recording the block chain node point of which the exclusive OR distance from the block chain node is any preset value; the method comprises the following steps: searching a target sub-tree corresponding to the target node set; determining a primary subtree containing leaf nodes corresponding to the candidate block chain nodes; and under the condition that any one level of subtree contains leaf nodes corresponding to the candidate block chain nodes, selecting at least one target block chain node from the corresponding candidate block chain nodes and recording the target block chain node into a target node set.

Description

Method and device for maintaining node set

Technical Field

The embodiment of the specification belongs to the technical field of block chains, and particularly relates to a method and a device for maintaining a node set.

Background

At this stage, a blockchain-based network may implement various forms of blockchain applications or blockchain services. Users can participate in related transactions for realizing a block chain through block chain nodes, for example, a plurality of block chain nodes respectively corresponding to different users in a block chain system can perform Secure Multi-Party Computation (SMPC) on private data of a certain node based on privacy technologies such as homomorphic encryption and zero knowledge proof. As another example, transfers may be effected between different user accounts based on a blockchain network; as another example, NFTs (Non-homogeneous tokens) corresponding to digital collections such as digital paintings, digital avatars, GIFs, etc. may also be issued over a blockchain network, so that ownership of the digital collections carried by the NFTs can be circulated among users of the blockchain network, thereby generating a value corresponding to the digital collections.

A blockchain network is generally constructed based on a structured P2P (Peer-to-Peer) network, and each blockchain node in the network may respectively maintain at least one node set for recording other blockchain nodes in the network, so as to perform data transmission between different blockchain nodes based on the blockchain nodes recorded in the node set. Moreover, the number of the block chain link points recorded in each node set is usually less than the number of all the block chain nodes corresponding to the corresponding sub-tree, so that selecting which block chain nodes should be recorded in the node set according to different principles brings different communication performances.

In the related art, any block link point typically adds a block chain node to any node set in the following manner: one is to add a preset number of nodes connected first to the arbitrary node set on a first-come-last basis, and to preferentially reserve blockchain nodes with longer connection time for security. The other is to add a preset number of block link points with a smaller RTT (Round Trip Time) to the any node set according to the RTT with the any node. When determining which block chain nodes should be recorded in the node set corresponding to any sub-tree in the above manner, the leaf nodes corresponding to each determined block chain link point are still randomly distributed in the sub-tree, so that for any two block chain nodes in the block chain network, the shortest path determined by the block chain link points recorded in the node set is probably not optimal, and thus, data transmission between the two block chain link points needs to be realized through more hops, which affects the communication performance of the block chain network.

Disclosure of Invention

The invention aims to provide a method and a device for maintaining a node set.

According to a first aspect of one or more embodiments of the present specification, a node set maintenance method is provided, which is applied to any blockchain node in a blockchain network that is based on a structured P2P networkConstructing each block chain link point in the block chain network and 2 ⁿ At least part of leaf nodes in the fork tree are in one-to-one correspondence, wherein the XOR distance between any two block chain nodes is calculated by the node identification of the corresponding leaf node, and 2 ⁿ The node identifiers of all leaf nodes belonging to the same subtree in the cross tree are respectively the same as the XOR distances calculated by the node identifiers of the leaf nodes corresponding to the chain link points of any block, and n is a positive integer; the node set corresponding to any preset value is used for recording the block chain node point of which the XOR distance with the node of any block chain is any preset value; the method comprises the following steps:

aiming at a target node set corresponding to any preset value, searching the node 2 ⁿ A corresponding target sub-tree in the fork tree, wherein the target sub-tree contains 2 ⁿ The root nodes of all the primary subtrees are child nodes of the root nodes of the target subtrees respectively;

determining a primary sub-tree comprising leaf nodes corresponding to candidate blockchain nodes, wherein the candidate blockchain node is a blockchain node found by any blockchain node in the blockchain network;

under the condition that any one level subtree contains leaf nodes corresponding to the candidate block chain nodes, selecting at least one target block chain node from the candidate block chain nodes corresponding to the any one level subtree and recording the selected target block chain node into the target node set, so that when the block chain message is sent to other block chain nodes by any one block chain node, routing and forwarding the block chain message through the block chain node points recorded in the target node set.

According to a second aspect of one or more embodiments of the present specification, a node set maintenance apparatus is provided, which is applied to any blockchain node in a blockchain network, where the blockchain network is constructed based on a structured P2P network, and each blockchain node and 2 link nodes in the blockchain network are provided ⁿ At least part of leaf nodes in the tree are in one-to-one correspondence, wherein any two areasThe XOR distance of the leaf nodes is calculated from the node identifiers of the corresponding leaf nodes, and 2 ⁿ The node identification of each leaf node belonging to the same subtree in the tree is respectively the same as the XOR distance calculated by the node identification of the leaf node corresponding to the chain link point of any block, and n is a positive integer; the node set corresponding to any preset value is used for recording the block chain node point of which the XOR distance with the node of any block chain is any preset value; the device comprises:

a target sub-tree searching unit, configured to search the target node set 2 corresponding to any preset value ⁿ A corresponding target sub-tree in the fork tree, wherein the target sub-tree contains 2 ⁿ The root nodes of all the primary subtrees are child nodes of the root node of the target subtree respectively;

a primary sub-tree determining unit, configured to determine a primary sub-tree including a leaf node corresponding to a candidate block chain node, where the candidate block chain node is a block chain node found in the block chain network by the any block chain node;

and the node recording unit is configured to select at least one target block chain node from candidate block chain nodes corresponding to any one of the primary subtrees and record the selected target block chain node into the target node set when any one of the primary subtrees includes a leaf node corresponding to the candidate block chain node, so that when the block chain message is sent to another block chain node by any one of the block chain nodes, the block chain message is routed and forwarded through the block chain node recorded in the target node set.

According to a third aspect of one or more embodiments of the present specification, there is provided an electronic apparatus including:

a processor;

a memory for storing processor-executable instructions;

wherein the processor implements the method of any of the first aspects by executing the executable instructions.

According to a fourth aspect of one or more embodiments of the present description, there is provided a computer-readable storage medium having stored thereon computer instructions which, when executed by a processor, implement the steps of the method according to any one of the first aspect.

Based on the foregoing embodiments of the present specification, in a block chain network constructed based on a structured P2P network, each block link node and 2 ⁿ At least part of leaf nodes in the tree are in one-to-one correspondence, wherein the XOR distance between any two block chain nodes is calculated by the node identification of the corresponding leaf node, and 2 ⁿ The node identification of each leaf node belonging to the same subtree in the cross tree is respectively the same as the XOR distance calculated by the node identification of the leaf node corresponding to any block chain link point in the network, and n is a positive integer; and the node set corresponding to any preset value is used for recording the block chain nodes with the XOR distance of any block chain node as any preset value. Aiming at a target node set corresponding to any preset value, searching the node 2 by any block chain node point ⁿ A corresponding target sub-tree in the fork tree, wherein the target sub-tree contains 2 ⁿ The root nodes of all the primary subtrees are child nodes of the root node of the target subtree respectively; then determining a primary subtree containing leaf nodes corresponding to candidate block chain nodes, wherein the candidate block chain nodes are the block chain nodes found by any block chain node in the block chain network; and further, under the condition that any one level sub-tree contains a leaf node corresponding to the candidate block chain node, selecting at least one target block chain node from the candidate block chain nodes corresponding to the any one level sub-tree to record into the target node set, so that when the block chain message is sent to other block chain nodes by any one block chain node, routing and forwarding the block chain message through the block chain node points recorded in the target node set.

By adopting two modes described in the related technology, only the record in the node set corresponding to any subtree is ensured to be the pairThe distribution rule of the leaf nodes corresponding to the leaf nodes in the subtree is not determined, but the distribution rule of the leaf nodes corresponding to the recorded block link points in the subtree is not determined: in the case that any subtree includes a plurality of level-one subtrees, and a plurality of block chain nodes are recorded in a corresponding node set, it is highly likely that leaf nodes corresponding to the recorded block chain nodes respectively belong to the same level-one subtree, or block chain nodes corresponding to leaf nodes in at least one subtree are not recorded in the node set. It can be seen that, when the block chain nodes are recorded in the node set by the method described in the related art, the leaf nodes corresponding to the block chain link points recorded in the same node set are respectively 2 ⁿ The distribution in the tree is not uniform. Since each block chain node in the block chain network records the block chain node in the manner described above, for any two block chain nodes having multiple routes in the block chain network, the shortest path determined by the node set may not be optimal, and still needs to be optimized.

However, with the foregoing embodiments of the present specification, as long as any one of the primary subtrees includes a leaf node corresponding to the candidate block chain node, at least one target block chain node is selected from the candidate block chain nodes corresponding to the subtree and recorded in the corresponding target node set, so as to ensure that, for the target node set of the any subtree, leaf nodes corresponding to each block chain node recorded in the target node set are distributed as uniformly as possible in the any subtree, that is, block chain nodes corresponding to the leaf nodes in each primary subtree are recorded in the target node set as possible. Therefore, based on the target node set maintained in the manner, the overall shortest path between any blockchain node and other blockchain nodes can be determined, so that people in the blockchain network can be found out as quickly as possible based on the path and other blockchain nodes, and the efficiency of sending blockchain messages is improved.

Drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present disclosure, the drawings needed to be used in the description of the embodiments will be briefly introduced below, and it is obvious that the drawings in the following description are only some embodiments described in the present disclosure, and it is obvious for a person skilled in the art to obtain other drawings based on these drawings without inventive labor.

Fig. 1 is a schematic structural diagram of a binary tree according to an exemplary embodiment.

Fig. 2 is a flowchart of a method for maintaining a node set according to an exemplary embodiment.

Fig. 3 is a schematic structural diagram of an apparatus according to an exemplary embodiment.

Fig. 4 is a block diagram of an apparatus for maintaining a node set according to an exemplary embodiment.

Detailed Description

In order to make those skilled in the art better understand the technical solutions in the present specification, the technical solutions in the embodiments of the present specification will be clearly and completely described below with reference to the drawings in the embodiments of the present specification, and it is obvious that the described embodiments are only a part of the embodiments of the present specification, and not all of the embodiments. All other embodiments obtained by a person of ordinary skill in the art based on the embodiments in the present specification without making any creative effort shall fall within the protection scope of the present specification.

In order to solve the foregoing problems in the related art, the present specification proposes a maintenance scheme of a node set. This scheme is described in detail below with reference to the accompanying drawings.

The maintenance method of the node set is applied to any blockchain node in a blockchain network, and a network structure is introduced firstly. The blockchain network described in this specification is constructed based on a structured P2P (Peer to Peer) network, and each blockchain link point in the blockchain network may be each node in the structured P2P network. Each block link point in the block chain network and 2 ⁿ At least some of the leaf nodes in the tree are in one-to-one correspondence, wherein an exclusive-OR distance (XOR distance) of any two blockchain nodes is marked by the node of the corresponding leaf nodeIs obtained by calculation, and 2 ⁿ The node identification of each leaf node belonging to the same subtree in the tree is respectively the same as the XOR distance calculated by the node identification of the leaf node corresponding to the chain link point of any block, and n is a positive integer; and maintaining a node set corresponding to each preset value one by one in each block chain node point, wherein the node set corresponding to any preset value is used for recording the block chain node of which the exclusive OR distance from the block chain node to any block chain node is any preset value.

The P2P network is a peer-to-peer network, and the structured P2P network described in this specification is a peer-to-peer network with a certain structure, where each node in the network is logically and fixedly distributed. The kademlia network is a typical representative of the structured P2P network and is widely applied to various public chains and alliance chains, such as EtherFang, changan chain and the like. Specifically, each node in the structured P2P network corresponds to 2 respectively ⁿ Different leaf nodes in the tree. In the block chain network constructed based on the structured P2P network, each block chain node is respectively connected with 2 ⁿ Leaf nodes in the fork tree correspond one to one. In addition, the above 2 ⁿ The fork tree is a full fork tree, 2 ⁿ The next level of any root node in the tree has 2 ⁿ And any child node can be a root node of a next-level sub-tree or a leaf node. The number of block link points in the block chain network does not normally exceed this 2 ⁿ The number of leaf nodes of the tree, i.e. the number of individual block chain nodes and 2 in the block chain network ⁿ At least part of leaf nodes in the fork tree are in one-to-one correspondence.

In the examples of this specification, 2 is stated ⁿ Each leaf node in the fork tree has a corresponding node identifier. The node identifier of any leaf node may be the same as the node identifier of the block chain node corresponding to the node, or may be obtained by calculation and conversion according to the node identifier of the block chain node. The node identifier of any blockchain node may be identity information such as a public key of the node or a digest (e.g., hash) of the public key, or may be calculated from the above information. Taking the public key as an example,for any blockchain node in the blockchain network, a hash value with a fixed length corresponding to the identity information (such as a public key) of the node can be calculated through a hash function, and the hash value is taken as the any blockchain node at 2 ⁿ And identifying the node of the corresponding leaf node in the fork tree. In this way, each block link point in the block chain network may be compared to 2 ⁿ At least part of leaf nodes in the fork tree are in one-to-one correspondence. The XOR distance between any two blockchain nodes is calculated by the node identification of the corresponding leaf node, and 2 ⁿ And the node identifiers of all leaf nodes belonging to the same subtree in the tree are respectively the same as the XOR distances calculated by the node identifiers of the leaf nodes corresponding to the chain link points of any block.

The structured P2P network described in this scheme may be a kademlia network, that is, each block link point may construct the block link network through a kademlia protocol. Any leaf node is in said 2 ⁿ The position of the node in the tree is determined by the node identification of the leaf node, and 2 is observed from the view point of each block chain node ⁿ The tree branches also differ.

Taking the binary tree when n =1 as an example, it is not assumed that node identifiers of leaf nodes corresponding to each block chain node in the block chain network are binary values of four bits, respectively, and that there are 16 block chain nodes a to P in the block chain network, and node identifiers of leaf nodes corresponding to each node one to one are 1111, 1110, 1101,. And 0000, respectively. On this basis, the binary tree as viewed from the node B perspective can be seen in fig. 1.

In fig. 1, the xor distance of each blockchain node is calculated by bit (i.e., 1bit is a calculation unit). Specifically, according to the sequence from the high level to the low level, if the values of the consecutive x bits of the node identifiers of the multiple leaf nodes are the same, and the value of the x bit is different from the value of 1110 at the corresponding position, 4-x is the exclusive or distance between the block chain link point and the node B corresponding to the multiple leaf nodes.

For example, the first three bits of 1111 (i.e., 111) are bitwise the same as the first three bits of 1110 (the last bit is different), so the sectionThe xor distance between point a and node B is 1 (i.e., 4-3= 1); as another example, the first two bits (i.e., 11) of 1100 and 1101 are each bitwise the same as the first two bits of 1110 (the last two bits are both different), so the XOR distances between nodes C and D and node B are each 2. Similarly, the xor distances between the nodes E to H and the node B may be all 3, and the xor distances between the nodes I to P and the node B may be all 4, which are not described again. Centering on the node B, the 2 can be determined based on the above-mentioned XOR distance ⁿ The tree structure comprises 4 subtrees in a cross tree, wherein leaf nodes (namely leaf nodes marked as 1111 and the same below) corresponding to a node A form a subtree, nodes C and D form a subtree (namely a subtree characterized by a root node D0.3), nodes E-H form a subtree (namely a subtree characterized by a root node D0.2), and nodes I-P form a subtree (namely a subtree characterized by a root node D0.1).

Illustratively, the structured P2P network may maintain a Distributed Hash Table (DHT), and the DHT may be implemented by a Kademlia protocol, in other words, the structured P2P network may be a Kademlia network. At this time, the nodes of the different xor distances may be represented in the concept of K-bucket (K-bucket). For node B, a subtree with k =1 (i.e. the XOR distance is 1, the same below) is the subtree with the right node A, a subtree with k =2 is the subtree with nodes C-D, a subtree with k =3 is the subtree with nodes E-H, and a subtree with k =4 is the subtree with nodes I-P. According to the structure of the binary tree, each subtree is in one-to-one correspondence with different exclusive-or distances.

Wherein any subtree comprises 2 ⁿ And (5) a primary subtree. Still taking fig. 1 as an example, since n =1, the subtrees respectively include 2 level subtrees. Take a subtree with k =4 (i.e. a subtree characterized by the root node d 0.1) as an example, the subtree includes a primary subtree1.1 characterized by the primary root node d1.1 and a primary subtree1.2 characterized by the primary root node d 1.2. Further, any one primary subtree comprises 2 secondary subtrees, for example, the primary subtree1.1 comprises a secondary subtree2.1 characterized by a secondary root node d2.1 and a secondary subtree2.2 characterized by a secondary root node d 2.2; and, the first level subtree1.2 contains the second level root node d2.3 tableA secondary subtree2.3 characterized and a secondary subtree2.4 characterized by a secondary root node d 2.4. In addition, the subtree0.2 represented by the root node D0.2 only includes two first-level subtrees, wherein any one of the first-level subtrees does not include a second-level subtree (directly includes a leaf node), and the subtree0.3 represented by the root node D0.3 directly includes leaf nodes C and D (at this time, the leaf nodes C and D may be respectively regarded as two first-level subtrees included in the subtree), which is not described again.

In addition, it should be noted that 2 is described in the embodiment of the present specification ⁿ And (4) a fork tree, wherein n can be any positive integer. For example, when n =1, said 2 ⁿ The fork tree is a binary tree; when n =2, said 2 ⁿ The fork tree is a quadtree, which is not described in detail. In the related art, the structured P2P network usually corresponds to a binary tree, and at this time, an empty bucket phenomenon often exists, that is, for an xor distance with a larger value, because the number of the block chain nodes corresponding to the corresponding primary subtree is larger, the probability that the block chain nodes therein are selected and recorded in the node set corresponding to the primary subtree is smaller, that is, the leaf nodes corresponding to the block chain nodes recorded in the K-bucket corresponding to the primary subtree are distributed too sparsely in all the leaf nodes corresponding to the primary subtree, which would result in too many path hops between any block chain node and other block chain nodes, and the communication process takes too long time. In the scheme, n can be greater than 1, such as 2, 3, 4 and the like, and in this case, 2 ⁿ The average hop count of the cross tree is reduced to 1/n of the average hop count of the binary tree, so that the hop count of multi-hop communication is reduced by times, and the PP communication performance is enhanced.

In addition, any block chain node maintains a node set corresponding to each preset value one by one, and for the 2 ⁿ And the preset value is each possible value of the corresponding exclusive-or distance. And the node set corresponding to any preset value is used for recording the block chain node of which the exclusive or distance with the block chain node is any preset value. Still taking fig. 1 as an example, the node set corresponding to the preset value 1 is used to record the blockchain node with the xor distance 1 with the node B, so that the node set is only used to record the nodeA; the node set corresponding to the preset value 2 is used for recording the block chain node with the XOR distance of 2 with the node B, so that the node set is used for recording at least one node in the nodes C and D; the node set corresponding to the preset value 3 is used for recording the block chain nodes with the XOR distance of 3 with the node B, and therefore the node set is used for recording at least one node in the nodes E-H; the node set corresponding to the preset value 4 is used to record the blockchain node with the xor distance of 4 with the node B, so that the node set is used to record at least one node in the nodes I to P, which is described below by taking the node set corresponding to k =4 as an example. In addition, for any blockchain node recorded in any node set, node information such as a node identifier of a leaf node corresponding to the node, identity information (e.g., a public key) of the node, address information (e.g., an IP address, a port number) of the node, and the like may be recorded in the set, and of course, other information may also be recorded, which is not described again. Based on the node set maintained by itself, any one of the block link points may determine a forwarding path (one hop or multiple hops) between itself and any other block link node in the block link network, that is, the node set may be used as a routing table for implementing communication according to the node information recorded therein.

It should be noted that fig. 1 only uses the node B as an example, and actually, each of the block link points in the block chain network may respectively maintain its corresponding node set. Furthermore, as can be seen from the foregoing process, the number of node sets maintained by any blockchain node is determined by the number of bits of the node identifier of the corresponding leaf node, for example, the node identifier is 160 bits (i.e., the binary length of the node identifier is 2) ¹⁶⁰ ) Then the value range of the exclusive or distance between any block chain node and other block chain nodes in the block chain network is [1,160 ]]At this time, any block link point may be maintained as 160 node sets at most. For example, when the node sets are set to record at most α block link points, if any block link node finds itself in the block link network (i.e., any block link node is found in the block link network), the upper limit of the number of block link nodes recorded in each node set maintained by the block link node may be presetPoint) distance is not less than a, selecting a block chain link points from the block chain link points and recording the selected block chain link points in a node set corresponding to the exclusive-or distance; however, when the number of the block link points that are at a certain exclusive or distance from the node itself is found to be less than α, all the block link points may be recorded in the node set corresponding to the exclusive or distance, and details thereof are not repeated.

It should be noted that the foregoing analysis is for explaining 2 corresponding to the block chain network ⁿ The structure of the tree and the case of the node set maintained locally at any one of the block nodes, and 2 ⁿ The specific structure of the cross tree, the preset value, the corresponding relation between the first-level subtree and the node set and the like are incidence relations of the logic level. In fact, any of the tile link points does not generate or locally save the 2 ⁿ The tree is crossed, and node sets corresponding to preset values one by one are maintained.

For a node set (hereinafter referred to as a target node set) corresponding to any preset value maintained by any blockchain node in the blockchain network, the any blockchain node may maintain the node set based on the following scheme. Referring to fig. 2, fig. 2 is a flowchart illustrating a method for maintaining a node set according to an exemplary embodiment. As shown in fig. 2, the method is applied to any blockchain node in a blockchain network, the blockchain network is constructed based on a structured P2P network, and each blockchain node and 2 in the blockchain network ⁿ At least part of leaf nodes in the fork tree are in one-to-one correspondence, wherein the XOR distance between any two block chain nodes is calculated by the node identification of the corresponding leaf node, and 2 ⁿ The node identification of each leaf node belonging to the same subtree in the tree is respectively the same as the XOR distance calculated by the node identification of the leaf node corresponding to the chain link point of any block, and n is a positive integer; the node set corresponding to any preset value is used for recording the block chain node point of which the XOR distance with the node of any block chain is any preset value. The method may include steps 202-206 described below.

Step 202, aiming at a target node set corresponding to any preset value, searching for the node 2 ⁿ A corresponding target sub-tree in the fork tree, wherein the target sub-tree contains 2 ⁿ And the root nodes of all the primary subtrees are child nodes of the root node of the target subtree respectively.

As mentioned above, said 2 ⁿ Any subtree in the tree contains 2 ⁿ And the root nodes of all the first-level subtrees are child nodes of the root node of the target subtree respectively. In fact, 2 ⁿ The two levels of subtrees adjacent to each other in the hierarchy of the cross tree have an inclusion relationship, namely, the upper level subtree comprises the lower level subtree, and the root node of the lower level subtree is a child node of the root node of the upper level subtree.

As shown in fig. 1, the root node d0.1 is a root node of a subtree0.1, the primary root nodes d1.1 and d1.2 are root nodes of the primary subtrees 1.1 and 1.2, respectively, and the primary root nodes d1.1 and d1.2 are child nodes of the root node d 0.1. Similarly, the root node d0.2 is a root node of the subtree0.2, the primary root nodes d1.3 and d1.4 (not shown in the figure) are root nodes of the primary subtree1.3 and subtree1.4, respectively, and the primary root nodes d1.3 and d1.4 are child nodes of the root node d 0.2. Through the above manner, the node sets corresponding to the preset values can be found for any block link point, and the scheme is explained by the updating process of the target node set corresponding to any preset value.

Step 204, determining a primary sub-tree including leaf nodes corresponding to candidate block chain nodes, where the candidate block chain node is a block chain node found by any block chain node in the block chain network.

During the operation of participating in the blockchain network, any blockchain node may find one or more other blockchain nodes in the network, and these nodes may be used as candidate blockchain nodes. In an embodiment, the any blockchain node may initiate a node discovery request to other blockchain nodes in the blockchain network, wherein the other blockchain nodes receiving the request may be neighboring nodes to which the any blockchain node has established contact. The other blockchain nodes receiving the node discovery request may return, in response to the request, blockchain node identity information recorded in the own node set to the any blockchain node, so that the any blockchain node may determine a corresponding candidate blockchain node according to the node identity information. When the received node identity information respectively returned by a plurality of other block chain nodes is repeated, any block chain node can perform deduplication processing on the node identity information, and the node respectively represented by each processed independent identity information is determined as a candidate block chain node. In addition, in case that the structured P2P network is a Kademlia network, the NODE discovery request may be a FIND _ NODE request.

In another embodiment, the any blockchain node may receive a blockchain message sent by any other blockchain node, and at this time, the any blockchain node may be determined as a candidate blockchain node. Of course, before receiving the message, the any block link point may have been recorded in the node set maintained by itself by the any other block link point; in other words, the any other block link point may have found the any block link node, but the any other block link point has not found the any other block link node. In a case that the structured P2P network is a Kademlia network, the blockchain message may be a FIND _ VALUE message for querying a certain data, or may also be a response message of the message, where the response message is used to return a query result for the data to an initiator of the FIND _ VALUE message.

Where a blockchain message as described herein may be a transaction for creating a smart contract or a response message containing transaction Receipt, such as a contract deployment result, the contract may be used to issue an NFT in a blockchain network; alternatively, the blockchain message may be a transfer transaction that may be used to purchase at least one NFT or a response message containing a transaction receipt (e.g., transfer result).

For the candidate blockchain nodes found, any blockchain node may further determine a primary subtree containing leaf nodes corresponding to the candidate blockchain nodes.

Step 206, under the condition that any one level sub-tree contains a leaf node corresponding to the candidate block chain node, selecting at least one target block chain node from candidate block chain nodes corresponding to the any one level sub-tree to record into the target node set, so that when the any one block chain node sends a block chain message to other block chain nodes, the block chain message is routed and forwarded through the block chain node recorded in the target node set.

The number of candidate blockchain nodes found may be one or more, and in case of finding multiple candidate blockchain nodes, each candidate blockchain node may belong to one or more primary subtrees. For this reason, in a case that any one of the first-level sub-trees includes a leaf node corresponding to the candidate block chain node, the any one of the block chain nodes may select at least one target block chain node from candidate block chain nodes corresponding to the first-level sub-tree, and record the target block chain node into the target node set (i.e., the node set corresponding to the any one of the first-level sub-trees). Taking subtree0.1 shown in fig. 1 as an example, if a node B determines that a first-level subtree1.1 of the node B includes leaf nodes corresponding to candidate block chain nodes, at least one target block chain node record may be selected from the candidate block chain nodes corresponding to subtree1.1 to the target node set; and/or, if the node B determines that its primary subtree1.2 includes leaf nodes corresponding to candidate block chain links, at least one target block chain node record may be selected from the candidate block chain nodes corresponding to the subtree1.2 to the target node set.

By this way, as long as any one level sub-tree includes a leaf node corresponding to the candidate block chain node, the block chain node can select at least one target block chain node record from the candidate block chain nodes corresponding to the sub-tree to the corresponding target node set, thereby ensuring that the leaf nodes corresponding to the block chain nodes recorded in the target node set of the sub-tree are distributed as uniformly as possible in the sub-tree, that is, the block chain nodes corresponding to the leaf chain nodes in the sub-tree are recorded in the target node set as possible. Based on the target node set maintained in the manner, the overall shortest path between any block chain node and other block chain nodes can be determined, and any other block chain node in the block chain network can be searched as quickly as possible according to the path, so that the efficiency of sending the block chain message is improved;

in an embodiment, the target sub-tree may further include m levels of subordinate sub-trees, where m is a positive integer; the subordinate subtrees of the ith level are i-level subtrees, root nodes of the i-level subtrees are child nodes of the root nodes of the i-1-level subtrees, i is greater than 1 and less than or equal to m, and i is a positive integer. Based on this, in case that any i-level sub-tree contains a leaf node corresponding to the candidate block link point, the any block link node may select at least one target block link node record from candidate block link nodes corresponding to the any i-level sub-tree into the target node set.

For example, two child nodes of the root node d0.1 of the subtree0.1 shown in fig. 1 are a primary root node d1.1 and a primary root node d1.2, respectively, which respectively represent the primary subtree1.1 and the subtree1.2. Wherein, any one of the first-level sub-trees comprises 1 level of lower-level sub-trees (i.e. second-level sub-trees). Wherein, the root node (i.e. the secondary root node d 2.1) of the secondary subtree2.1 and the root node (i.e. the secondary root node d 2.2) of the secondary subtree2.2 are child nodes of the root node (i.e. the primary root node d 1.1) of the corresponding primary subtree respectively; similarly, the root node (i.e., the second-level root node d 2.3) of the second-level sub-tree 2.3 and the root node (i.e., the second-level root node d 2.4) of the second-level sub-tree 2.4 are child nodes of the root node (i.e., the first-level root node d 1.2) of the corresponding first-level sub-tree, respectively. Taking the primary subtree1.1 as an example, if the node B determines that the secondary subtree2.1 contains leaf nodes corresponding to the candidate block chain nodes, at least one target block chain node record can be selected from the candidate block chain nodes corresponding to the subtree2.1 to the target node set; and/or, if it is determined that the secondary sub-tree 2.2 contains leaf nodes corresponding to the candidate block chain nodes, selecting at least one target block chain node record from the candidate block chain nodes corresponding to the sub-tree 2.2 to the target node set. By the mode, on the basis of the first-level subtree, the leaf nodes corresponding to each target node set corresponding to the first-level subtree are ensured to be distributed uniformly in the first-level subtree as much as possible, so that the path hop count between each block chain node and other block chain nodes is further reduced.

For any i-level sub-tree including leaf nodes corresponding to the candidate block chain nodes, the first number of the i-level sub-trees corresponding to the any block chain node may be determined first, so as to select a first number of target block chain nodes from the candidate block chain nodes corresponding to the any i-level sub-tree. Wherein the first number may be determined in a number of ways. For example, the first number may be positively correlated with a number of candidate blockchain nodes corresponding to the any i-level sub-tree. In other words, the more candidate blockchain nodes corresponding to any i-level sub-tree are found in the blockchain network by any blockchain node, the more target blockchain nodes are selected from the candidate blockchain nodes corresponding to the i-level sub-tree, and vice versa. By the method, the number of the recorded block chain nodes in the node set corresponding to each primary subtree can be positively correlated with the number of the candidate block chain nodes corresponding to the primary subtree, so that leaf nodes corresponding to the target block chain node points recorded in the node set are uniformly distributed in the corresponding primary subtree as much as possible, and the method is favorable for further reducing the hop count and weakening the empty bucket phenomenon.

For another example, the first number may be equal to a second number of target blockchain nodes selected from candidate blockchain nodes of another i-level subtree. At this time, the number of target block chain nodes corresponding to any two i-level subtrees is the same, so that the number determination logic is simplified, and the maintenance difficulty of the target node set is reduced. For another example, the difference between the first number and the second number may also be smaller than a preset difference, for example, a quotient obtained by dividing the total number of the target block chain nodes corresponding to the i-1 level sub-tree by the number of the i-level sub-tree is used as the first number and the second number, but it should be ensured that the first number and the second number are both integers, that is, the quotient may be rounded, and the first number and the second number are respectively determined according to the result, so as to ensure that the difference between the first number and the second number is smaller than the preset difference.

In addition, the any blockchain node may select at least one target blockchain node from candidate blockchain nodes corresponding to any m-level subtree in various ways. For example, at least one target blockchain node may be randomly selected from candidate blockchain nodes corresponding to any m-level sub-tree; at the moment, the selection logic is simpler, and the leaf nodes corresponding to the link points of the selected target block can be ensured to be uniformly distributed in any m-level subtree as far as possible. For another example, the any blockchain node may respectively determine a first connection time of the any blockchain node and each candidate blockchain node corresponding to any m-level sub-tree, and select at least one target blockchain node having an earliest first connection time from the candidate blockchain nodes. The first connection time can be used for reflecting the connection time between the other block chain link node and the any block chain node and indirectly reflecting the stability of network connection between the other block chain link node and the any block chain node, so that the other block chain node with the earliest first connection time is used as the target block chain node, the recorded network connection between the target block chain link node and the any block chain node can be ensured to be stable as much as possible, and the communication performance of the block chain network can be ensured. For another example, the any one of the blockchain nodes may also determine network delays between the any one of the blockchain nodes and each candidate blockchain node corresponding to any one of the m-level sub-trees, respectively, and select at least one target blockchain node with the smallest network delay from the candidate blockchain nodes. The network delay may be RTT, or may also be response time or other time indicators, which is not described in detail herein. By the method, the delay of the block chain node recorded in the target node set and any block chain node can be ensured to be short.

In an embodiment, when any target blockchain node is recorded to the target node set, the corresponding method may be used to record the number of target blockchain nodes that have been recorded by the target node set. For example, in a case where the number of the block link points recorded in the target node set is smaller than the upper limit of the node number of the set, any target block link node may be added to the set, and in this case, the target block link node is added to the target node set. Or, in a case that the number of the recorded block link points in the target node set is equal to the upper limit of the number of nodes in the set, any target block chain node may be used to replace any block chain node already recorded in the set. By the method, the number of the recorded target block chain nodes in the target node set can be ensured not to exceed the corresponding upper limit of the number, so that the stability of the storage space corresponding to the target node set is ensured, and the maintenance difficulty of the target node set is reduced.

Before recording any target block chain node, the upper limit of the node number of the target node set can be determined by any block chain node in various ways. For example, a preset number may be determined as an upper limit of the number of nodes of the target node set, and the preset number should not be greater than the total number of leaf nodes of the target sub-tree. The upper limit of the number of the nodes is the maximum number of the blockchain nodes which can be stored in the target node set at any time. As shown in fig. 1, upper limits of the number of nodes in the node sets corresponding to subtrees 0.1, 0.2, 0.3, and 0.4 may be set in advance. And the upper limit of the number of the nodes in each node set can be the same or different. If the upper limit of the number of nodes of the node sets corresponding to the four subtrees is set to be 1, at this time, one block chain node record may be selected from the nodes I to P to the node set corresponding to the subtree0.1, one block chain node record may be selected from the nodes E to H to the node set corresponding to the subtree0.2, one record of the node C or D to the node set corresponding to the subtree0.3, and the node a to the node set corresponding to the subtree 0.1.

For another example, the upper limit of the number of nodes in the target node set may also be determined according to the total amount of leaf nodes included in the target sub-tree, and the upper limit of the number of nodes is positively correlated with the total amount. If the node B finds that 6, 4, 2, and 1 candidate blockchain nodes exist in subtree 0.1-subtree 0.4, respectively, the upper limit of the number of nodes in the node set corresponding to each subtree may be determined to be 3, 2, 1, and 1, respectively, according to 1/2 of the number of preset blockchain nodes. For another example, the upper limit of the number of nodes in the target node set may also be determined according to the number of leaf nodes corresponding to the candidate node of the block chain that are included in the target sub-tree, where the upper limit of the number of nodes is positively correlated with the number of leaf nodes. Considering that the total amount of leaf nodes corresponding to subtrees 0.1 to 0.4 is different, the preset amount corresponding to each subtree may be positively correlated with the total amount of leaf nodes of the subtree, and for example, 4, 3, 1 (or 6, 2, 1, etc.) may be set as the upper limit of the node amount of the node set for the node sets corresponding to subtrees 0.1 to 0.4.

As shown in fig. 1, a subtree0.1 is taken as an example, and it is assumed that the upper limit of the number of nodes of the subtree is 4, that is, 4 target block chain nodes need to be recorded in the target node set corresponding to the subtree. For subtree0.1, the subtree1.1 and subtree1.2 at the next level are the left subtree and the right subtree, respectively. If the node B finds that the nodes I-P in the subtree0.1 are candidate block chain nodes, 2 target block chain nodes can be selected from the candidate block chain nodes respectively corresponding to the subtree1.1 and the subtree1.2 at the first level, namely 2 target block chain nodes need to be selected from the nodes M-P corresponding to the left subtree and 2 target block chain nodes need to be selected from the nodes I-L corresponding to the right subtree. Further, for the first-level sub-tree 1.1, its two-level sub-trees 2.1 and 2.2 are the left sub-tree and the right sub-tree, respectively. At this time, 1 target block chain node may be selected from candidate block chain nodes corresponding to the secondary subtrees subtree2.1 and subtree2.2, that is, 1 node from nodes O and P corresponding to the left subtree needs to be selected as a target block chain node, and 1 node from M and N corresponding to the right subtree needs to be selected as a target block chain node. Similarly, for the primary subtree1.2, its secondary subtree2.3 and subtree2.4 are its left and right subtrees, respectively. At this time, 1 target block chain node may be selected from candidate block chain nodes corresponding to the secondary subtrees 2.3 and 2.3, that is, 1 node from nodes K and L corresponding to the left subtree needs to be selected as a target block chain node, and 1 node from nodes I and J corresponding to the right subtree needs to be selected as a target block chain node.

In some embodiments, the node B may not discover some nodes in A-P (e.g., a node in the network but not yet discovered by the node B, or a node in the network does not exist at all), and the appropriate manner of the target tile node can be adjusted accordingly. Taking the upper limit of the number of nodes in the subtree d0.1 as 4, if the node B finds the nodes M to P but does not find the nodes I to L, 4 target blockchain nodes can be selected from the nodes M to P, and at this time, the nodes M to P can all be selected as the target blockchain nodes. Or, if the node B finds the nodes M to P but does not find the node I, then 2 target blockchain nodes can be selected from the nodes M to P and 2 target blockchain nodes can be selected from the nodes J to L. Or, if the node B finds the nodes M to P but does not find the nodes I and L, at this time, 3 target blockchain nodes may be selected from the nodes M to P and 1 target blockchain node may be selected from the nodes H and L, which is not described again.

In an embodiment, for each node set maintained by itself, any blockchain node may maintain it. For example, the any blockchain node may initiate a presence confirmation request to at least one target blockchain node recorded in any node set, where the request sent to any target blockchain node is used to query the node about its current status (e.g., whether it is still in the blockchain network, whether it is working normally, etc.). Therefore, in the case of receiving the existence confirmation response returned by any target blockchain node, the node still can normally communicate with any blockchain node, so that any target blockchain node recorded in any node set can be maintained. On the contrary, in the case that the reception of the existence confirmation response returned by any one of the target blockchain nodes fails (for example, the existence confirmation response is not received after exceeding the preset time), it indicates that the node cannot normally communicate with any one of the block chain nodes, and at this time, the any one of the target blockchain nodes recorded in any one of the node sets may be deleted. By the method, the target node set can be updated in time according to the current state of any target block chain node, and the block chain nodes recorded in the set are ensured to have higher timeliness.

In one embodiment, based on the target node set maintained in the foregoing manner, any one of the blockchain nodes may perform message transmission with other blockchain nodes (i.e., the target destination blockchain node described below). For example, for a block chain message generated by itself or transmitted by other block chain nodes, any block chain node needs to transmit it to the target block chain node. For this, any blockchain node may determine a destination blockchain node corresponding to the message and a destination node identifier of a leaf node corresponding to the destination blockchain node; and then calculating the XOR distance between the link point of the target block and the link node of any block according to the identifier of the target node and the source node identifier of the leaf node corresponding to the link point of any block, and determining an intermediate node set corresponding to the XOR distance. As described above, each node set maintained by any blockchain node corresponds to a corresponding preset value, and the preset value is a value of the xor distance. Therefore, the xor distance between each block link point recorded in the intermediate node set and any one of the block link nodes is equal to the xor distance between the destination block link point and any one of the block link nodes.

The destination blockchain node may already be recorded in the intermediate node set, and at this time, any one of the blockchain nodes may directly determine the blockchain node from the intermediate node set (specifically, information such as a communication address of the node may be determined), and send the blockchain message to the blockchain node. Alternatively, the destination blockchain link point may not be recorded in the intermediate node set, and then the any blockchain node may send the blockchain message to any intermediate blockchain node in the intermediate node set, so as to forward the blockchain message to the destination blockchain node by the any intermediate blockchain link point. The specific process of forwarding the blockchain message by any intermediate blockchain node is similar to the process of sending the message by any blockchain node, and is not described again. By the mode, the block chain information can be directly sent to the corresponding target block chain node by any block chain node based on the self-maintained node set; or, a plurality of block chain nodes may sequentially forward a block chain message through a recursive algorithm based on a node set maintained by the block chain node, so that the message is accurately forwarded to a corresponding destination block chain node through a multi-hop path.

FIG. 3 is a schematic block diagram of an apparatus provided in an exemplary embodiment. Referring to fig. 3, at the hardware level, the apparatus includes a processor 302, an internal bus 304, a network interface 306, a memory 308, and a non-volatile memory 310, but may also include hardware required for other services. One or more embodiments of the present description may be implemented in software, such as by processor 302 reading a corresponding computer program from non-volatile storage 310 into memory 308 and then executing. Of course, besides software implementation, the one or more embodiments in this specification do not exclude other implementations, such as logic devices or combinations of software and hardware, and so on, that is, the execution side of the following processing flow is not limited to each logic unit, and may also be hardware or logic devices.

Fig. 4 is a block diagram of a node set maintenance apparatus according to an exemplary embodiment, which may be applied to the device shown in fig. 3 to implement the technical solution of the present specification. The device is applied to any block chain node in a block chain network, the block chain network is constructed based on a structured P2P network, and each block chain node and 2 in the block chain network ⁿ At least part of leaf nodes in the tree are in one-to-one correspondence, wherein any two areasThe XOR distance of the node of the block chain is calculated from the node identification of the corresponding leaf node, and 2 ⁿ The node identifiers of all leaf nodes belonging to the same subtree in the cross tree are respectively the same as the XOR distances calculated by the node identifiers of the leaf nodes corresponding to the chain link points of any block, and n is a positive integer; the device comprises a plurality of block chain nodes, wherein each block chain node is provided with a node set corresponding to each preset value, the node set corresponding to any preset value is used for recording the block chain node with the XOR distance of any block chain node as any preset value, and the device comprises:

a target sub-tree searching unit 401, configured to search the 2 for a target node set corresponding to any preset value ⁿ A corresponding target sub-tree in the cross tree, wherein the target sub-tree comprises 2 ⁿ The root nodes of all the primary subtrees are child nodes of the root nodes of the target subtrees respectively;

a primary sub-tree determining unit 402, configured to determine a primary sub-tree including a leaf node corresponding to a candidate block chain node, where the candidate block chain node is a block chain node found in the block chain network by any one block chain node;

a node recording unit 403, configured to select at least one target block chain node from candidate block chain nodes corresponding to any one level sub-tree to record into the target node set when any one level sub-tree includes a leaf node corresponding to the candidate block chain node, so that when the any one level sub-tree sends a block chain message to another block chain node, the block chain message is routed and forwarded through the block chain node recorded in the target node set.

Optionally, the target sub-tree includes m hierarchical subordinate sub-trees, where m is a positive integer; the subordinate subtrees of the ith level are i-level subtrees, the root nodes of the i-level subtrees are child nodes of the root nodes of the i-1-level subtrees, i is more than 1 and less than or equal to m, and i is a positive integer; the node recording unit 403 is further configured to:

selecting at least one target blockchain node from candidate blockchain nodes corresponding to any i-level subtree in the case that the any i-level subtree includes a leaf node corresponding to the candidate blockchain node.

Optionally, each i-level sub-tree including a leaf node corresponding to the candidate block link point satisfies one of the following conditions:

a first number of target blockchain nodes selected from candidate blockchain nodes corresponding to any level-i sub-tree is positively correlated with a number of candidate blockchain nodes corresponding to the any level-i sub-tree;

the first number is equal to a second number of target block chain nodes selected from candidate block chain nodes of another i-level sub-tree;

the difference between the first quantity and the second quantity is smaller than a preset difference.

Optionally, the node recording unit 403 is further configured to:

randomly selecting at least one target block chain node from candidate block chain nodes corresponding to any m-level subtree;

respectively determining the first connection time of any block chain node and each candidate block chain node corresponding to any m-level sub-tree, and selecting at least one target block chain node with the earliest first connection time from each candidate block chain node;

respectively determining the latest connecting time of the chain node of any block and each candidate block chain node corresponding to any m-level sub-tree, and selecting at least one target block chain node with the latest connecting time from each candidate block chain node;

and respectively determining the network delay between the block chain node and each candidate block chain node corresponding to any m-level sub-tree, and selecting at least one target block chain node with the minimum network delay from the candidate block chain nodes.

Optionally, the node recording unit 403 is further configured to:

under the condition that the number of the recorded block chain link points in the target node set is smaller than the upper limit of the node number of the target node set, adding any target block chain node into the target node set; or,

and under the condition that the number of the recorded block chain link points in the target node set is equal to the upper limit of the node number of the target node set, replacing any recorded block chain node in the target node set with any target block chain node.

Optionally, the node recording unit 403 is further configured to:

determining a preset number as an upper limit of the number of nodes of the target node set, wherein the preset number is not more than the total amount of leaf nodes of the target subtree;

determining the upper limit of the number of nodes of the target node set according to the total amount of leaf nodes contained in the target subtree, wherein the upper limit of the number of nodes is positively correlated with the total amount;

and determining the upper limit of the number of nodes of the target node set according to the number of leaf nodes corresponding to the candidate block chain nodes contained in the target subtree, wherein the upper limit of the number of nodes is positively correlated with the number of leaf nodes.

Optionally, the primary subtree determining unit 402 is further configured to:

node discovery requests are sent to other block chain nodes in the block chain network, and corresponding candidate block chain nodes are determined according to node identity information of the block chain nodes returned by the other block chain nodes; or,

and under the condition that a block chain message sent by any other block chain node is received, determining the any other block chain link node as a candidate block chain node.

Optionally, the method further includes: a request initiating unit 404, configured to initiate an existence confirmation request to at least one target block chain node recorded in any node set;

a set maintaining unit 405, configured to maintain any target block chain node recorded in any node set when receiving a presence confirmation response returned by any target block chain node;

a node deleting unit 406, configured to delete any target blockchain node recorded in any node set when receiving a presence confirmation response returned by any target blockchain node fails.

Optionally, the method further includes:

a node determining unit 407, configured to determine a destination block chain node corresponding to a block chain message to be sent, and a destination node identifier of a leaf node corresponding to the destination block chain node;

a distance calculating unit 408, configured to calculate an exclusive or distance between the destination block chain link point and the any block chain link node according to the destination node identifier and a source node identifier of a leaf node corresponding to the any block chain link point, and determine an intermediate node set corresponding to the exclusive or distance;

a message sending unit 409, configured to send the blockchain message to any intermediate blockchain node in the intermediate node set, so that the blockchain message is forwarded to the destination blockchain node by the any intermediate blockchain node.

In the 90 s of the 20 th century, improvements in a technology could clearly distinguish between improvements in hardware (e.g., improvements in circuit structures such as diodes, transistors, switches, etc.) and improvements in software (improvements in process flow). However, as technology advances, many of today's process flow improvements have been seen as direct improvements in hardware circuit architecture. Designers almost always obtain the corresponding hardware circuit structure by programming an improved method flow into the hardware circuit. Thus, it cannot be said that an improvement in the process flow cannot be realized by hardware physical modules. For example, a Programmable Logic Device (PLD), such as a Field Programmable Gate Array (FPGA), is an integrated circuit whose Logic functions are determined by programming the Device by a user. A digital system is "integrated" on a PLD by the designer's own programming without requiring the chip manufacturer to design and fabricate application-specific integrated circuit chips. Furthermore, nowadays, instead of manually manufacturing an Integrated Circuit chip, such Programming is often implemented by "logic compiler" software, which is similar to a software compiler used in program development and writing, but the original code before compiling is also written by a specific Programming Language, which is called Hardware Description Language (HDL), and HDL is not only one but many, such as ABEL (Advanced Boolean Expression Language), AHDL (alternate Hardware Description Language), traffic, CUPL (core universal Programming Language), HDCal, jhddl (Java Hardware Description Language), lava, lola, HDL, PALASM, rhyd (Hardware Description Language), and vhigh-Language (Hardware Description Language), which is currently used in most popular applications. It will also be apparent to those skilled in the art that hardware circuitry that implements the logical method flows can be readily obtained by merely slightly programming the method flows into an integrated circuit using the hardware description languages described above.

The controller may be implemented in any suitable manner, for example, the controller may take the form of, for example, a microprocessor or processor and a computer-readable medium storing computer-readable program code (e.g., software or firmware) executable by the (micro) processor, logic gates, switches, an Application Specific Integrated Circuit (ASIC), a programmable logic controller, and an embedded microcontroller, examples of which include, but are not limited to, the following microcontrollers: ARC 625D, atmel AT91SAM, microchip PIC18F26K20, and Silicone Labs C8051F320, the memory controller may also be implemented as part of the control logic for the memory. Those skilled in the art will also appreciate that, in addition to implementing the controller as pure computer readable program code, the same functionality can be implemented by logically programming method steps such that the controller is in the form of logic gates, switches, application specific integrated circuits, programmable logic controllers, embedded microcontrollers and the like. Such a controller may thus be considered a hardware component, and the means included therein for performing the various functions may also be considered as a structure within the hardware component. Or even means for performing the functions may be conceived to be both a software module implementing the method and a structure within a hardware component.

The systems, apparatuses, modules or units described in the above embodiments may be specifically implemented by a computer chip or an entity, or implemented by a product with certain functions. One typical implementation device is a server system. Of course, the present invention does not exclude that as future computer technology develops, the computer implementing the functionality of the above described embodiments may be, for example, a personal computer, a laptop computer, a vehicle-mounted human-computer interaction device, a cellular phone, a camera phone, a smart phone, a personal digital assistant, a media player, a navigation device, an email device, a game console, a tablet computer, a wearable device or a combination of any of these devices.

Although one or more embodiments of the present description provide method operational steps as described in the embodiments or flowcharts, more or fewer operational steps may be included based on conventional or non-inventive approaches. The order of steps recited in the embodiments is merely one manner of performing the steps in a multitude of orders and does not represent the only order of execution. When an actual apparatus or end product executes, it may execute sequentially or in parallel (e.g., parallel processors or multi-threaded environments, or even distributed data processing environments) according to the method shown in the embodiment or the figures. The terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, the presence of additional identical or equivalent elements in processes, methods, articles, or apparatus that include the recited elements is not excluded. For example, the use of the terms first, second, etc. are used to denote names, but not to denote any particular order.

For convenience of description, the above devices are described as being divided into various modules by functions, and are described separately. Of course, when implementing one or more of the present description, the functions of each module may be implemented in one or more software and/or hardware, or a module implementing the same function may be implemented by a combination of multiple sub-modules or sub-units, etc. The above-described embodiments of the apparatus are merely illustrative, and for example, the division of the units is only one logical division, and other divisions may be realized in practice, for example, a plurality of units or components may be combined or integrated into another system, or some features may be omitted, or not executed. In addition, the shown or discussed mutual coupling or direct coupling or communication connection may be an indirect coupling or communication connection through some interfaces, devices or units, and may be in an electrical, mechanical or other form.

The present invention has been described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each flow and/or block of the flow diagrams and/or block diagrams, and combinations of flows and/or blocks in the flow diagrams and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks. In a typical configuration, a computing device includes one or more processors (CPUs), input/output interfaces, network interfaces, and memory.

The memory may include forms of volatile memory in a computer readable medium, random Access Memory (RAM) and/or non-volatile memory, such as Read Only Memory (ROM) or flash memory (flash RAM). Memory is an example of a computer-readable medium.

Computer-readable media, including both permanent and non-permanent, removable and non-removable media, may implement the information storage by any method or technology. The information may be computer readable instructions, data structures, modules of a program, or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static Random Access Memory (SRAM), dynamic Random Access Memory (DRAM), other types of Random Access Memory (RAM), read Only Memory (ROM), electrically Erasable Programmable Read Only Memory (EEPROM), flash memory or other memory technology, compact disc read only memory (CD-ROM), digital Versatile Disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage, graphene storage or other magnetic storage devices, or any other non-transmission medium, which can be used to store information that can be accessed by a computing device. As defined herein, a computer readable medium does not include a transitory computer readable medium such as a modulated data signal and a carrier wave.

As will be appreciated by one skilled in the art, one or more embodiments of the present description may be provided as a method, system, or computer program product. Accordingly, one or more embodiments of the present description may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, one or more embodiments of the present description may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.

One or more embodiments of the present description may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. One or more embodiments of the present specification can also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

The embodiments in the present specification are described in a progressive manner, and the same and similar parts among the embodiments are referred to each other, and each embodiment focuses on the differences from the other embodiments. In particular, as for the system embodiment, since it is substantially similar to the method embodiment, the description is relatively simple, and reference may be made to the partial description of the method embodiment for relevant points. In the description of the specification, reference to the description of "one embodiment," "some embodiments," "an example," "a specific example," or "some examples" or the like means that a particular feature, structure, material, or characteristic described in connection with the embodiment or example is included in at least one embodiment or example of the specification. In this specification, the schematic representations of the terms used above are not necessarily intended to refer to the same embodiment or example. Furthermore, the particular features, structures, materials, or characteristics described may be combined in any suitable manner in any one or more embodiments or examples. Furthermore, various embodiments or examples and features of different embodiments or examples described in this specification can be combined and combined by one skilled in the art without contradiction.

The above description is intended to be illustrative of one or more embodiments of the disclosure, and is not intended to limit the scope of one or more embodiments of the disclosure. Various modifications and alterations to one or more embodiments described herein will be apparent to those skilled in the art. Any modification, equivalent replacement, improvement or the like made within the spirit and principle of the present specification should be included in the scope of the claims.

Claims

1. A maintenance method of a node set is applied to any blockchain node in a blockchain network, the blockchain network is constructed based on a structured P2P network, and each blockchain node and 2 in the blockchain network ⁿ At least part of leaf nodes in the fork tree are in one-to-one correspondence, wherein the XOR distance between any two block chain nodes is calculated by the node identification of the corresponding leaf node, and 2 ⁿ The node identifiers of all leaf nodes belonging to the same subtree in the cross tree are respectively the same as the XOR distances calculated by the node identifiers of the leaf nodes corresponding to the chain link points of any block, and n is a positive integer; the node set corresponding to any preset value is used for recording the block chain node point of which the exclusive OR distance from the block chain node is any preset value; the method comprises the following steps:

aiming at a target node set corresponding to any preset value, searching the node 2 ⁿ A corresponding target sub-tree in the cross tree, wherein the target sub-tree comprises 2 ⁿ The root nodes of all the primary subtrees are child nodes of the root nodes of the target subtrees respectively;

determining a primary sub-tree containing leaf nodes corresponding to candidate blockchain nodes, wherein the candidate blockchain nodes are blockchain nodes found by any blockchain node in the blockchain network;

under the condition that any one level sub-tree contains leaf nodes corresponding to the candidate block chain nodes, selecting at least one target block chain node from the candidate block chain nodes corresponding to the any one level sub-tree to record into the target node set, so that when the block chain node sends a block chain message to other block chain nodes, the block chain message is routed and forwarded through the block chain nodes recorded in the target node set.

2. The method of claim 1, the target sub-tree comprising m levels of subordinate sub-trees, m being a positive integer; the subordinate subtrees of the ith level are i-level subtrees, the root nodes of the i-level subtrees are child nodes of the root nodes of the i-1-level subtrees, i is more than 1 and less than or equal to m, and i is a positive integer; the selecting at least one target blockchain node from candidate blockchain nodes corresponding to the any one level subtree comprises:

3. The method of claim 2, comprising respective i-level subtrees of leaf nodes corresponding to the candidate block link points satisfying one of:

4. The method of claim 2, selecting at least one target blockchain node from the candidate blockchain nodes corresponding to any m-level sub-tree, comprising one of:

5. The method of claim 1, logging any target blockchain node into the set of target nodes, comprising:

6. The method of claim 5, determining an upper limit on the number of nodes of the target set of nodes, comprising one of:

7. The method of claim 1, discovering the candidate blockchain node, comprising:

8. The method of claim 1, further comprising:

initiating a presence confirmation request to at least one target block chain node recorded in any node set;

maintaining any target block chain node recorded in any node set under the condition of receiving a presence confirmation response returned by any target block chain node;

and deleting any target block chain node recorded in any node set under the condition that the receiving of the existence confirmation response returned by any target block chain node fails.

9. The method of claim 1, further comprising:

determining a target block chain node corresponding to a block chain message to be sent and a target node identifier of a leaf node corresponding to the target block chain node;

calculating the XOR distance between the link point of the target block and the link point of any block according to the identifier of the target node and the identifier of the source node of the leaf node corresponding to the link point of any block, and determining a middle node set corresponding to the XOR distance;

and sending the blockchain message to any intermediate blockchain node in the intermediate node set so as to forward the blockchain message to the target blockchain node by any intermediate blockchain node.

10. A node set maintenance device is applied to any blockchain node in a blockchain network, the blockchain network is constructed based on a structured P2P network, and each blockchain node and 2 in the blockchain network ⁿ At least part of leaf nodes in the fork tree are in one-to-one correspondence, wherein the XOR distance between any two block chain nodes is calculated by the node identification of the corresponding leaf node, and 2 ⁿ The node identifiers of all leaf nodes belonging to the same subtree in the cross tree are respectively the same as the XOR distances calculated by the node identifiers of the leaf nodes corresponding to the chain link points of any block, and n is a positive integer; the node set corresponding to any preset value is used for recording the block chain node point of which the exclusive OR distance from the block chain node is any preset value; the device comprises:

a primary sub-tree determining unit, configured to determine a primary sub-tree including a leaf node corresponding to a candidate block chain node, where the candidate block chain node is a block chain node found in the block chain network by any one of the block chain nodes;

11. An electronic device, comprising:

a processor;

a memory for storing processor-executable instructions;

wherein the processor implements the method of any one of claims 1-9 by executing the executable instructions.

12. A computer readable storage medium having stored thereon computer instructions which, when executed by a processor, carry out the steps of the method according to any one of claims 1 to 9.