CN115208817B - A trusted cross-link routing method based on cross-chain gateway and Floyd algorithm - Google Patents

Abstract

The invention relates to a trusted cross-link routing method based on a cross-link gateway and a Floyd algorithm, belonging to the technical field of block chain cross-link routing. According to the method, information interaction between block chains is realized by using the cross-chain gateway, iteration times and intermediate data are reduced when the problem of shortest paths among cross-links is solved in a network, and a cross-chain shortest path of a cross-chain task route is selected by using a Floyd algorithm. The method has no limitation and centralization risk of heterogeneous blockchain, and improves the expandability of a blockchain system. Meanwhile, the method has good reliability, dynamic programming is added by using a Di Jie Style algorithm, and the executable performance can be ensured. The method has high efficiency, and is obviously optimized in space complexity and time complexity.

Description

A trusted cross-link routing method based on cross-chain gateway and Floyd algorithm

Technical field

The invention relates to a trusted cross-link routing method based on a cross-chain gateway and Floyd algorithm, and belongs to the technical field of blockchain cross-link routing.

Background technique

Currently, the existing cross-chain methods mainly include the following:

1. Notary mechanism. Introduce one or more trusted centralized entities for credit endorsement to carry out information cross-chain. The notary mechanism is relatively simple to implement technically, but because the notary mechanism requires sufficient trust in the notary, there is a risk of centralization.

2. Hash locking mechanism. This mechanism takes advantage of the low collision characteristics of the hash function and the delayed execution characteristics of blockchain transactions. By setting a hash puzzle between the two parties of the transaction, the user pays for the transaction by guessing the original value of the hash value within a specified time period, and then A cross-chain mechanism to realize transactions.

3. Relay chain mechanism. By introducing other blockchain systems to be responsible for transaction collection, endorsement and forwarding, a third-party public chain is constructed to connect other chains in the blockchain network. The relay chain mechanism can entrust the verification and endorsement of transactions to the relay chain. However, the cross-chain implementation method is complex and relies on its own set of cross-chain protocols to a certain extent. The access to heterogeneous chains There are certain difficulties.

In the context of the existing cross-chain mechanism, the gateway cross-chain implementation mechanism is simple, and because the essence of gateway cross-chain is to achieve data synchronization on the cross-chain gateway connected to the application chain, there are no restrictions on heterogeneous chains. At the same time, in order to solve large-scale routing problems in the cross-chain process, the traditional Dijkstra routing algorithm and dynamic programming are difficult to meet the needs of large-scale applications. The program execution time for gateway nodes within 1,000 is acceptable. However, if the scale continues to expand to 10 times or 100 times, the cost of energy consumption and time will be too high. Therefore, in order to reduce the cost of time and energy consumption and improve the efficiency of cross-chain task program execution, it is necessary to reduce the number of iterations and process the storage of intermediate data to achieve optimization in both time and space.

Contents of the invention

The purpose of this invention is to overcome the shortcomings of the existing technology and to solve the technical problems of long time and low efficiency in large-scale cross-link routing in blockchain systems, and proposes a trusted cross-chain based on cross-chain gateway and Floyd algorithm. routing method.

The present invention uses a cross-chain gateway to realize information interaction between blockchains, reduces the number of iterations and intermediate data when finding the shortest path problem in a cross-chain routing network, and uses the Floyd algorithm to select the shortest cross-chain path for cross-chain task routing.

In order to achieve the above object, the present invention adopts the following technical solutions.

First, the conceptual content involved in the present invention will be described.

1. Cross-chain gateway. It is an interactive component that connects different blockchain systems, assumes the role of collecting and disseminating transactions between blockchains, and supports message interaction between application chains.

2. Gateway routing table. Generated, updated and maintained by cross-chain gateway. The gateway routing table stores the addresses of all cross-chain gateways in the cross-link routing network, the optimal distance from the local cross-chain gateway to other cross-chain gateways, and the routing selection for the optimal distance (the routing selection at this time is the best routing selection) . The optimal distance represents the minimum energy consumption when transmitting information between two cross-chain gateways.

In order to maintain the optimal distance between two cross-chain gateways in the gateway routing table, each cross-chain gateway periodically exchanges information with all its neighboring gateways. If the optimal distance from a gateway to any adjacent gateway changes after the exchange, the exchange process will be repeated until all gateways complete the routing table update.

3.Floyd algorithm. Also known as the interpolation point method, it is an algorithm used to find the shortest path between multiple source points in a given weighted graph. Initially, for any two nodes, if there is an edge between the nodes, the weight on this edge will be used as the shortest path length between them; if there is no directed edge, then ∞ will be used as the shortest path between them. length, and then gradually try to add nodes to the original path as intermediate nodes. If the path obtained after adding intermediate nodes is shorter than the original path, replace the original path with this new path.

4. Application chain. Responsible for the specific business logic of cross-chain tasks, isomorphic application chains have similar block structures and transaction data storage formats, and have the same consensus algorithm and encryption mechanism.

5. Smart contracts. A computer protocol designed to communicate, verify, or enforce contracts in an information-based manner. The smart contract accepts the user's business request, transfers the business to the distribution server, and uploads the data information of each business in identity management and mortgage loans to the chain.

6. Cross-chain tasks. Cross-chain messages or cross-chain transactions initiated by accounts on the application chain, including local account address, source application chain ID, target account address, target application chain ID, timestamp of cross-chain events, cross-chain task content and cross-chain Mission proof.

7. Cross-link routing network. A P2P network composed of multiple cross-chain gateways, including cross-chain gateways associated with application chains. Cross-chain tasks are delivered and forwarded in the cross-chain routing network.

A trusted cross-link routing method based on cross-chain gateway and Floyd algorithm, including cross-chain task proposal and verification, cross-chain routing and cross-chain task receipt, as follows:

Step 1: Connect the cross-chain gateway to the application chain and configure the application chain port information.

Step 2: Cross-chain gateways register each other's addresses in order to find operating cross-chain gateways for adjacent application chains; based on the energy consumption value of information transmitted between gateways, the Floyd algorithm is generated and the gateway routing table is maintained.

Step 3: The cross-chain gateway enters the initial listening state and monitors user operations; based on the source chain ID, target chain ID and gateway routing table of the cross-chain task, find the best route for the cross-chain task.

Specifically, step 3 may include the following steps:

Step 3.1: The local account on the application chain initiates a cross-chain task, and the cross-chain task is submitted to the cross-chain gateway associated with the application chain;

Specifically, step 3.1 may include the following steps:

Step 3.1.1: The local account submits the cross-chain task request to the application chain through the smart contract;

Step 3.1.2: After the application chain receives the cross-chain task request, it verifies whether the structure and content of the cross-chain task are valid (whether the local account address is legal, etc.). If it is not legal, the execution of the cross-chain task is rejected. If it is legal, then Perform step 3.1.3;

Step 3.1.3: The application chain forwards the cross-chain task to the associated cross-chain gateway, and at the same time, the cross-chain task is stored on the blockchain.

Step 3.2: The cross-chain gateway detects the validity of the account's cross-chain tasks (including whether the local account has permissions, whether the account assets are sufficient, etc.); if the cross-chain task initiated by the local account is illegal, the execution of the cross-chain task will be refused. If the chain transaction is legal, proceed to step 3.3;

Step 3.3: The cross-chain gateway queries the target cross-chain gateway associated with the target application chain in the locally stored gateway routing table based on the target application chain ID of the cross-chain task, and finds the local cross-chain gateway to the target cross-chain based on the information in the gateway routing table. The best route of the gateway, and forward the cross-chain task to the target cross-chain gateway according to the best route selection;

Step 4: When the target cross-chain gateway detects the cross-chain task, it first detects whether the target account address of the cross-chain task is legal. If the target account address is illegal, it refuses to execute and sends a rejection receipt; if the target account address is legal, the target cross-chain The gateway accepts cross-chain tasks and forwards cross-chain tasks to the target application chain;

Step 5: The target application chain forwards the cross-chain task to the target account for execution based on the target account address in the cross-chain task, and returns a successful cross-chain task execution receipt.

Specifically, step 5 may include the following steps:

Step 5.1: Based on the target account address in the cross-chain task, the target application chain sends the cross-chain task determined to be executed to the target account through the smart contract;

Step 5.2: Each node of the target application chain reaches consensus on the cross-chain task;

Step 5.3: After the consensus among the nodes of the target application chain is successful, the cross-chain task will be added to the blockchain;

Step 5.4: The target application chain returns a successful cross-chain task execution receipt.

Step 6: After detecting that the cross-chain task is successfully executed, the cross-chain gateway sends back a successful execution receipt to the application chain. At this time, a cross-chain task is completed.

beneficial effects

Compared with the existing technology, the method of the present invention has the following advantages:

1. This method uses a cross-chain gateway to interact with information between different blockchains, without the restrictions and centralization risks of heterogeneous blockchains, and improves the scalability of the blockchain system.

2. This method has good reliability. It adopts the idea of adding dynamic programming to Dijkstra's algorithm, and its executability can be guaranteed.

3. This method is highly efficient and has been significantly optimized in both space complexity and time complexity.

Description of the drawings

Figure 1 is a schematic flow chart of the method of the present invention.

Detailed ways

The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments. The described embodiments are only some, but not all, of the embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts fall within the scope of protection of the present invention.

As shown in Figure 1, a trusted cross-link routing method based on cross-chain gateway and Floyd algorithm.

This embodiment elaborates on cross-chain gateway routing in the information interaction scenario empowered by the blockchain. For example, in a recruitment scenario, Company A, a recruitment company, has business needs such as collection and certification of degree information for applicants B and students. In response to Company A’s request for degree information certification, University C, where Student B is located, needs to provide Student B’s degree certificate.

This embodiment describes the cross-chain transmission of degree certificates from University C to Company A in the above-mentioned recruitment scenario using the method of the present invention, including the following process:

Step 1: Cross-chain gateway A connects to University C’s application chain and configures University C’s application chain port information; cross-chain gateway B connects to Company A’s application chain and configures Company A’s application chain port information.

Step 2: Cross-chain gateways register each other’s addresses in order to find operating cross-chain gateways for adjacent application chains. Cross-chain gateway A and cross-chain gateway B use the Floyd algorithm based on the energy consumption value of information transmitted between gateways. , generate and maintain gateway routing table A and gateway routing table B respectively.

Specifically, this method utilizes the energy consumption of message transfer between cross-chain gateways and generates a gateway routing table based on the Floyd algorithm for cross-chain gateway selection when forwarding information. In a graph composed of cross-link networks, nodes represent cross-chain gateways, and the edges between two nodes represent the information that can be exchanged between the two cross-chain gateways. The weight of the edge represents the distance between the two nodes. That is, the energy consumption cost when information is transmitted between two cross-chain gateways.

The characters involved in the method in this embodiment are as shown in Table 1:

Table 1 The method in this embodiment involves character descriptions

Input:G,i

Output:Gop

First, each node must generate a local initial routing matrix. The initial routing matrix records the initial distance between the local node and all other nodes.

Taking the initial routing matrix generated by node i as an example, for any node j, if there is an edge between i and j, then the weight g[i][j] of this edge is used as the initial distance between them. If there is no to the edge, then the initial distance between them is infinite, that is, g[i][j]=∞. At this time, the best route between i and j is from node i to node j. Set the The optimal route is -1, from which the initial routing matrix is generated.

Then, update the initial routing matrix to generate a gateway routing table by inserting points, and perform the following operations on the initial distance from local node i to each other node: If from node i to node j passes through node k, and g[i][j]> g[i][k]+g[k][j], then the best distance from i to j is g[i][k]+g[k][j], and the best route from i to j is updated from i to k and then to j. This generates the gateway routing table of the local node;

Similarly, for each node in the cross-link routing network, the gateway routing table is generated according to the above process.

Step 3: Cross-chain gateway A enters the initialization listening state, monitors the operations of student B on the application chain of University C, and selects the best link to cross-chain gateway B based on the source chain ID, target chain ID and gateway routing table A of student B’s cross-chain task. Best route.

Step 3.1: Student B’s account on University C’s application chain initiates a degree certificate cross-chain task. The degree certificate cross-chain task is submitted to the cross-chain gateway A associated with University C’s application chain. The degree certificate cross-chain task includes Student B’s account address. , University C’s application chain ID, Company A’s application chain ID, Company A’s recruiting unit account address, timestamp of cross-chain events, student B’s degree certificate and cross-chain task certificate;

Step 3.1.1: Student B’s account submits the degree certificate cross-chain task request to University C’s application chain through the smart contract;

Step 3.1.2: After receiving the degree certificate cross-chain task request, the University C application chain verifies whether the structure and content of the degree certificate cross-chain task are valid (whether the account address of student B is legal, etc.). If it is not legal, it rejects the degree certificate cross-chain task. Execution of chain tasks, if legal, proceed to step 3.1.3;

Step 3.1.3: The University C application chain forwards the degree certificate cross-chain task to the associated cross-chain gateway A, and at the same time, the degree certificate cross-chain task is stored in the University C application chain.

Step 3.2: Cross-chain gateway A detects the validity of the degree certificate cross-chain task of student B’s account (whether student B’s account has permissions, whether the account assets are sufficient, etc.). If the degree certificate cross-chain task initiated by student B’s account is illegal, it will be rejected. The degree proves the execution of the cross-chain task; if the degree proves that the cross-chain transaction is legal, proceed to step 3.3;

Step 3.3: Cross-chain gateway A queries the cross-chain gateway B associated with company A's application chain in the gateway routing table A stored locally in cross-chain gateway A based on the application chain ID of company A that proves the cross-chain task. According to the gateway routing table A Record the best distance and best route between cross-chain gateways A and B, and forward the cross-chain task to cross-chain gateway B according to the best route selection;

Step 4: Cross-chain gateway B detects the degree certificate cross-chain task. It first detects whether the degree certificate cross-chain task of Company A’s recruiting unit account address is legal. If the account address of Company A’s recruiting unit is illegal, it refuses to execute and sends a rejection receipt; If the account address of Company A’s recruiting unit is legal, cross-chain gateway B accepts the degree certificate cross-chain task and forwards the degree certificate cross-chain task to Company A’s application chain;

Step 5: Company A’s application chain forwards the cross-chain task of degree certificate to Company A’s recruitment unit account for execution based on the account address of Company A’s recruiting unit in the cross-chain task, and returns a receipt of successful execution of the degree certificate cross-chain task to cross-chain gateway B;

Step 5.1: Based on the target account address in the degree certificate cross-chain task, Company A’s application chain sends the confirmed degree certificate cross-chain task to Company A’s recruitment unit through the smart contract;

Step 5.2: Each node of Company A’s recruitment unit reaches consensus on the cross-chain task of degree certificate;

Step 5.3: After the consensus among the nodes of Company A’s recruitment unit is successful, add the degree certificate cross-chain task to Company A’s application chain;

Step 5.4: Company A’s application chain returns a receipt proving the successful execution of the cross-chain task to cross-chain gateway B.

Step 6: After detecting that the degree certificate cross-chain task is successfully executed, cross-chain gateway B sends back an execution success receipt to cross-chain gateway A. Cross-chain gateway A sends back an execution success receipt to the University C application chain to complete a cross-chain task.

Claims (4)

1. A trusted cross-link routing method based on cross-chain gateway and Floyd algorithm, which is characterized by including the following steps: Step 1: Connect the cross-chain gateway to the application chain and configure the application chain port information; Step 2: Cross-chain gateways register each other’s addresses in order to find cross-chain gateways of adjacent application chains. Based on the energy consumption value of information transfer between gateways, a gateway routing table is generated and maintained based on the Floyd algorithm; Step 3: The cross-chain gateway enters the initial listening state, monitors user operations, and finds the best route for the cross-chain task based on the source chain ID, target chain ID and gateway routing table of the cross-chain task; Step 3.1: The local account on the application chain initiates a cross-chain task, and the cross-chain task is submitted to the cross-chain gateway associated with the application chain; Step 3.2: The cross-chain gateway detects the validity of the account's cross-chain task. If the cross-chain task initiated by the local account is illegal, the execution of the cross-chain task will be refused; if the cross-chain task is legal, step 3.3 will be executed; Step 3.3: The cross-chain gateway queries the target cross-chain gateway associated with the target application chain in the locally stored gateway routing table based on the target application chain ID of the cross-chain task, and finds the local cross-chain gateway to the target cross-chain based on the information in the gateway routing table. The best route of the gateway, and forward the cross-chain task to the target cross-chain gateway according to the best route selection; Step 4: When the target cross-chain gateway detects the cross-chain task, it first detects whether the target account address of the cross-chain task is legal. If the target account address is illegal, it refuses to execute and sends a rejection receipt; if the target account address is legal, the target cross-chain The gateway accepts cross-chain tasks and forwards cross-chain tasks to the target application chain; Step 5: The target application chain forwards the cross-chain task to the target account for execution based on the target account address in the cross-chain task, and returns a successful cross-chain task execution receipt; Step 6: After detecting that the cross-chain task is successfully executed, the cross-chain gateway sends back a successful execution receipt to the application chain. At this time, a cross-chain task is completed. 2. A trusted cross-link routing method based on cross-chain gateway and Floyd algorithm as claimed in claim 1, characterized in that step 3.1 includes the following steps: Step 3.1.1: The local account submits the cross-chain task request to the application chain through the smart contract; Step 3.1.2: After the application chain receives the cross-chain task request, it verifies whether the structure and content of the cross-chain task are valid. If it is illegal, the execution of the cross-chain task is refused. If it is legal, step 3.1.3 is executed; Step 3.1.3: The application chain forwards the cross-chain task to the associated cross-chain gateway, and at the same time, the cross-chain task is stored on the blockchain. 3. A trusted cross-link routing method based on cross-chain gateway and Floyd algorithm as claimed in claim 1, characterized in that step 5 includes the following steps: Step 5.1: Based on the target account address in the cross-chain task, the target application chain sends the cross-chain task determined to be executed to the target account through the smart contract; Step 5.2: Each node of the target application chain reaches consensus on the cross-chain task; Step 5.3: After the consensus among the nodes of the target application chain is successful, add the cross-chain task to the blockchain; Step 5.4: The target application chain returns a successful cross-chain task execution receipt. 4. A trusted cross-link routing method based on cross-chain gateways and Floyd algorithm as claimed in claim 1, characterized in that gateway routing is generated and maintained based on Floyd algorithm according to the energy consumption value of information transfer between gateways. The table method is as follows: First, each node must generate a local initial routing matrix. The initial routing matrix records the initial distance between the local node and all other nodes; In a graph composed of cross-link networks, nodes represent cross-chain gateways, and the edges between two nodes represent the information interaction between the two cross-chain gateways; the edge weight g represents the distance between the two nodes. , that is, the energy consumption cost when information is transmitted between two cross-chain gateways; i, j, k represent the nodes in the graph composed of cross-link networks; When node i generates the initial routing matrix, for any node j, if there is an edge between i and j, the weight of this edge g[i][j] will be used as the initial distance between them. If there is no directed edges, then the initial distance between them is infinite, that is, g[i][j]=∞. At this time, the best route between i and j is from node i to node j. Set the minimum distance between i and j. The optimal route is -1, thus generating an initial routing matrix; Then, update the initial routing matrix to generate a gateway routing table by inserting points, and perform the following operations on the initial distance from local node i to each other node: If from node i to node j passes through node k, and g[i][j]> g[i][k]+g[k][j], then the best distance from i to j is g[i][k]+g[k][j], and the best route from i to j is updated From i to k and then to j; thus generating the gateway routing table of the local node; Similarly, for each node in the cross-link routing network, the gateway routing table is generated according to the above process.