CN112966001B - BCTkPQ query method based on blockchain - Google Patents

Abstract

The invention discloses a BCTkPQ query method based on a block chain, which comprises the following steps: constructing a collaborative query framework (CQM); step 2: constructing a source-destination S-D index, and constructing a business logic relationship in each transaction; step 3: constructing a path-score P-SC index according to a query request sent by a user on the basis of the S-D index, and establishing a mapping relation between the path and the transaction score, wherein the P-SC index and the S-D index form a secondary index; step 4: the top k transactions with the highest score of the weight W on attribute O in the transaction of path p in the query request are obtained. The invention can realize BCTkPQ rapid query based on the block chain based on the CQM model and the secondary index, and the query efficiency can be improved along with the increase of the number of CP nodes and the number of users.

Description

A blockchain-based BCTkPQ query method

technical field

The invention relates to the technical field of path query, in particular to a blockchain-based BCTkPQ query method.

Background technique

At present, blockchain, as the cornerstone of the cryptocurrency system, has received high attention from the industry and academia. Blockchain has been successfully applied in various real-world scenarios, such as Internet of Things, smart medical care, supply chain, database architecture, data service outsourcing, etc. A blockchain can be viewed as a distributed database maintained through a consensus protocol by nodes that do not fully trust each other. According to different scenarios, the blockchain can design specific transaction models based on specific business logic. Among them, the common transaction model is based on financial transactions and is used to represent transfer information between banks or financial institutions. Obviously, in the financial transaction scenario, the blockchain can safely and completely store the user's financial bills and daily transfer records. All transaction data contains useful information and knowledge, expresses the business preferences of users in different scenarios, and can be used to improve the quality of application services such as data analysis, data security, and recommendation systems. Therefore, there is an increasing need for diverse query processing.

The traditional query method is to send query requests to complete nodes that maintain complete blocks and transactions, and obtain eligible transactions by traversing all blocks of the entire blockchain. Obviously, the efficiency of this solution is too low to meet a large number of query requirements. The main reason for the inefficiency is that the entire node needs to traverse all blockchain data stored in local storage, resulting in excessive computational workload.

Contents of the invention

Aiming at the deficiencies of the above-mentioned prior art, the present invention provides a BCTkPQ query method based on blockchain. For the top-k transaction path query (Blockchaintop-kPathQuery, BCTkPQ) in the blockchain, it returns the top k transactions that meet the specified conditions in the given query path p.

In order to solve the problems of the technologies described above, the technical solution adopted by the present invention is: a BCTkPQ query method based on blockchain, comprising the steps of:

Step 1: Build a collaborative query framework CQM (Collaborative QueryModel) consists of three key parts, namely the application programming interface API, the collaborative network CN (Collaborative Network) maintained by a group of collaborative peers CP (CollaborativePeer) and the storage of raw transaction data Blockchain BC (BlockChain); where the API includes distributors and responders;

Step 2: Construct the source-destination S-D (Source-Destination) index, construct the business logic relationship in each transaction, the process is as follows:

Step 2.1: Initialize three collections <S, D, E> to store the logic of each transaction;

Step 2.2: Define T _x as a transaction on the blockchain. According to the general financial transfer operation between accounts, define the structure of T _x as, T _x = {ID, T _x Hash, from, to, O}, where ID represents The serial number of T _x , T _x Hash indicates the hash value of T _x , the <from, to> field is the business logic of the T _x transmission operation, which is called the transaction path p, and O is the remaining attributes of the transaction. When the blockchain transaction When T _x has m attributes, O is {attr ₁ , attr ₂ ,...,attr _m }, and attr is a certain attribute;

Step 2.3: traverse all transactions on the blockchain, and add the from field and to field of T _x to the S collection and the D collection respectively;

Step 2.4: Save the path of the current transaction into the E set, that is, p→<from,to>.

Step 3: On the basis of the S-D index, according to the query request <p,k,W,O> sent by the user, construct the path-score P-SC (Path-Score) index, and establish the mapping relationship between the path and the transaction score, P-SC index and S-D index constitute a secondary index; where p is the transaction path, O is the set of other attributes of the transaction, W is the set of weights, and k is the top k transactions with the highest query scores. The specific process is as follows:

Step 3.1: Obtain the newly added path p _i in the E collection of the SD index;

Step 3.2: When the obtained p _i does not exist in the P-SC index, create a new package bucket ^* to store the path p _i , that is, add p _i →<Txi _> to the bucket ^* ;

Step 3.3: When the obtained p _i exists in the P-SC index, obtain the corresponding bucket, and store the _Txi corresponding to p _i in the bucket.

Step 4: Obtain the query result, the user sends a query request <p,k,W,O>, and obtains the top k transactions with the highest weight W on attribute O among the transactions whose path is p→<from ^* , to ^* >, The process is as follows:

Step 4.1: The user broadcasts the request <p,k,W,O> to all CPs through the CQM distributor;

Step 4.2: Each CP obtains all package buckets containing p→<from ^* , to ^* > in the local P-SC index, and calculates its transaction score score _i according to the weight set W in the query condition;

The calculation method of the transaction score score _i is as follows:

F _s (T _x )＝∑attr _i ×w _i

Among them, F _s (T _x ) is the score _i of the transaction, attri _i is the i-th attribute of the transaction T _x , w _i ≥ 0 is the i-th value of the weight set W in the query condition, and is the weight of the corresponding attribute _attri .

Step 4.3: Sorting from largest to smallest according to the transaction score, adding the top k blockchain transactions with the highest scores in the bucket to the result set resultSet;

Step 4.4: Calculate the digest digest for the resultSet, and broadcast the digest to other CPs;

Step 4.5: When the received digests are all the same and the number exceeds the given threshold (the general threshold is set to two-thirds of the number of all CPs), return resultSet, terminate the current calculation and wait for the next call.

The beneficial effects produced by adopting the above-mentioned technical scheme are:

1. The method provided by the present invention is based on the cooperative query model CQM to deal with the BCTkPQ problem, which can realize the BCTkPQ fast query based on the block chain.

2. The query method of the present invention constructs a secondary index based on the P-SC index and the S-D index. Compared with the traditional query method, the diversified query method based on the secondary index will improve the query efficiency and reduce it. Because the entire node needs Traverse all blockchain data stored in local storage, resulting in excessive computational workload. Based on the CQM model and the secondary index, fast BCTkPQ queries based on the blockchain can be realized, and the query efficiency will increase with the increase in the number of CP nodes and users.

Description of drawings

FIG. 1 is a schematic structural diagram of a collaborative query framework in an embodiment of the present invention;

Fig. 2 is the flowchart of constructing S-D index in the embodiment of the present invention;

Fig. 3 is the flowchart of constructing P-SC index in the embodiment of the present invention;

FIG. 4 is a schematic structural diagram of a secondary index in an embodiment of the present invention;

Fig. 5 is a flow chart of the query process in the embodiment of the present invention.

Detailed ways

The specific implementation manners of the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. The following examples are used to illustrate the present invention, but are not intended to limit the scope of the present invention.

In this embodiment, three users S _U = {U ₁ , U ₂ , U ₃ }, five nodes CP = {P ₁ , P ₂ ,..., P ₅ }, and 100 pieces of data are used for experiments, and each piece of data The format is T _x = {ID, T _x Hash, from, to, money}. In this embodiment, a BCTkPQ query method based on blockchain is as follows:

Step 1: Build a collaborative query framework (Collaborative QueryModel, CQM), the structure is shown in Figure 1, including three key parts, namely the application programming interface (API), maintained by a group of collaborative peers (CollaborativePeer, CP) A collaborative network (CollaborativeNetwork, CN) and a blockchain (BlockChain, BC) that stores raw transaction data; where the API includes distributors and responders;

The execution process of CQM is briefly described as follows: First, the query request is broadcast to all CPs through the dispatcher in the API. Then, all CPs respond to query requests synchronously, and each CP contains three modules, namely, parser, indexer, and executor. These modules can access BC in a read-only manner, which means that all modules can read data objects stored in the blockchain and create indexes to fulfill query requests locally. Finally, CN returns the result through the responder in the API after processing the query request.

Step 2: Construct a source-destination (Source-Destination, S-D) index, and construct the business logic relationship in each transaction, the process is shown in Figure 2;

Step 2.1: Initialize three collections <S, D, E> to store the logic of each transaction;

Step 2.2: Define T _x as a transaction on the blockchain. According to the general financial transfer operation between accounts, define the structure of T _x as, T _x = {ID, T _x Hash, from, to, O}, where ID represents The serial number of T _x , T _x Hash indicates the hash value of T _x , the <from, to> field is the business logic of the T _x transmission operation, called the transaction path p, and O is the remaining attributes of the transaction. When the blockchain transaction When T _x has m attributes, O is {attr ₁ , attr ₂ ,...,attr _m }, and attr is a certain attribute;

In this embodiment, there is only one other attribute of the transaction, which is money;

Step 2.3: Traverse all transactions on the chain, add the from field and to field of T _x to the S collection and the D collection respectively, as shown in Figure 3, extract the from field S={U ₁ , U ₁ from 100 pieces of data , U ₂ , U ₂ , U ₃ , U ₁ }, extract the to field D from 100 pieces of data = {U ₂ , U ₃ , U ₁ , U ₃ , U ₁ , U ₃ };

Step 2.4: Save the mapping relationship between the current transactions as the E set, that is, p→<from,to>, construct E={<U ₁ , U ₂ >,<U ₁ ,U ₃ >, <U ₂ ,U ₁ >,<U ₂ ,U ₃ >,<U ₃ ,U ₁ >...}, the structure is shown on the left side of Figure 4;

Step 3: Based on the SD index, according to the query request <p,k,W,O> sent by the user, simulate the query <<U ₁ ,U ₃ >,2,1,money>, and construct the path-score (Path- Score, P-SC) index, establishes the mapping of path and transaction score, the process is shown in Figure 3, the P-SC index and SD index form a secondary index, and the structure is shown in Figure 4;

Step 3.1: Obtain the newly added path p _i in the E collection of the SD index;

Step 3.2: When the obtained p _i does not exist in the P-SC index, for example, when the T _x3 path p ₃ =<U ₂ , U ₁ > does not exist in the P-SC, create a new package bucket ^* to store The path p _i =<U ₂ , U ₁ >, that is, p _i →<Tx ₃ > is added to the bucket ^* ;

Step 3.3: When the obtained p _i exists in the P-SC index, for example, if the T _x6 path p ₆ =<U ₁ , U ₃ > exists in the P-SC, obtain the corresponding bucket and store the Tx ₆ corresponding to p ₆ into the bucket;

Step 4: Obtain the query result, the user sends a query request <p,k,W,O>=<<U ₁ ,U ₃ >,2,1,money>, and the obtaining path is p→<from ^* ,to ^* >= Among the transactions of <U ₁ , U ₃ >, the top k=2 transactions with the highest score of weight W=1 on the data object O=money, as shown in Figure 5;

Step 4.1: The user broadcasts the request <p,k,W,O>=<<U ₁ ,U ₃ >,2,1,money> to all CPs={P ₁ ,P ₂ ,…, P ₅ };

Step 4.2: Each CP obtains all buckets containing p→<from ^* ,to ^* >=<U ₁ ,U ₃ > in the local P-SC index, and calculates its transaction score score according to the weight set W in the query condition _i . The transaction score score _i is F _x (T _x ), F _x (T _x )=∑attr _i ×w _i . Among them, attri _i is the i-th attribute of the transaction T _x , w _i ≥ 0 is the i-th value of the weight set W in the query condition, which is the weight of the corresponding attribute _attri .

In this embodiment, W contains only one attribute money, and its weight is 1, so the transaction T _xi in the E set, score _i =F _s (T _xi )=money _i ×1;

Step 4.3: Sort from largest to smallest according to score, and add the 2 highest-scoring transactions in the bucket to the result set resultSet,

Step 4.4: Calculate the digest digest for the resultSet, and broadcast the digest to other CPs;

Step 4.5: When the received digests are all the same and the number exceeds the given threshold, which is two-thirds of the number of all CPs, return resultSet, terminate the current calculation and wait for the next call.

Claims (3)

1. The BCTkPQ query method based on the blockchain is characterized by comprising the following steps of:

step 1: constructing a collaborative query framework CQM comprising three key parts, namely an application programming interface API, a collaboration network CN maintained by a set of collaboration peers CP, and a blockchain BC storing raw transaction data; wherein the API comprises a dispatcher and a responder;

step 2: constructing a source-destination S-D index, and constructing a business logic relationship in each transaction;

the specific process is as follows:

step 2.1: initializing three sets < S, D, E > for storing logic for each transaction;

step 2.2: definition T _x For transactions on a blockchain, T is defined in accordance with a general inter-account financial transfer operation _x The structure is T _x ＝{ID，T _x Hash, from, to, O }, where ID represents T _x Sequence number T of (1) _x Hash represents T _x Is used to determine the hash value of (c),<from,to>the field is a representation T _x The business logic of the transfer operation, called transaction path p, O is the rest of the attribute of the transaction, when the block chain transaction T _x When m attributes are present, O is { attr ₁ ,attr ₂ ,……,attr _m Attr is a certain attribute;

step 2.3: traversing all transactions on the blockchain, T _x The from field and the to field of (a) are added to the S set and the D set, respectively;

step 2.4: saving the path of the current transaction into the E set, namely p & gtfwdarw < from, to >;

step 3: constructing a path-score P-SC index according to query requests < P, k, W and O > sent by a user on the basis of the S-D index, and establishing a mapping relation between the path and the transaction score, wherein the P-SC index and the S-D index form a secondary index; wherein p is a transaction path, O is the rest attribute set of the transaction, W is a weight set, and k is the first k transactions with highest query scores;

the specific process is as follows:

step 3.1: obtaining newly added path p in E set of S-D index _i ；

Step 3.2: when p is obtained _i Creating a new packet bucket when not present in the P-SC index ^* To store the path p _i I.e. p _i →<Tx _i >Added to socket ^* In (a) and (b);

step 3.3: when p is obtained _i When the P-SC index exists, the corresponding socket is acquired, and P is stored _i Corresponding Tx _i Into a socket;

step 4: acquiring a query result, and sending a query request by a user<p,k,W,O>The acquisition path is p →<from ^* ,to ^* >The top k transactions with the highest scoring for weight W on attribute O.

2. The BCTkPQ query method based on blockchain of claim 1, wherein the procedure of step 4 is as follows:

step 4.1: the user broadcasts the request < p, k, W, O > to all CPs through the distributor of the CQM;

step 4.2: each CP obtains all the contained P-in the local P-SC index<from ^* ,to ^* >According to the weight set W in the query condition, calculating the transaction score of the packet socket _i ；

Step 4.3: according to the transaction score, the first k blockchain transactions with the highest scores in the bucket are added into a result set according to the sequence from big to small;

step 4.4: calculating abstract digest for the result set, and broadcasting the digest to other CPs;

step 4.5: and when the received digees are all the same and the number exceeds a given threshold value, returning to a resultSet, terminating the current calculation and waiting for the next call.

3. The BCTkPQ query method based on blockchain of claim 2, wherein the transaction score _i The calculation method of (2) is as follows:

F _s (T _x )＝∑attr _i ×w _i

wherein F is _s (T _x ) Score for transaction _i ，attr _i For transaction T _x Is the ith attribute, w _i 0 is the ith value of the weight set W in the query condition, is the corresponding attribute attr _i Is a weight of (2).