CN103218574A - Hash tree-based data dynamic operation verifiability method - Google Patents

Abstract

The invention discloses a data dynamic operation verifiability method based on a hash tree, which is composed of three parts connected by a communication network including a user USER, a cloud computing data center CDC and a third-party audit agency TPA. As the requesting party for the data storage service, USER hopes to store the data files it owns in the cloud storage space of the cloud computing data center. USER can be either an individual user or an enterprise user. CDC is responsible for responding to users' data storage service requests, storing users' data files in its own huge data center according to certain rules, and is responsible for the management and maintenance of data files. As a reliable third-party auditor, TPA is entrusted by USER to review the integrity and consistency of the data files stored in the CDC data center. The invention solves the problem of verifying the integrity and consistency of user data files under the cloud computing environment.

Description

A Verifiable Method of Data Dynamic Operation Based on Hash Tree

technical field

The invention belongs to the technical field of computers and relates to a hash tree-based data dynamic operation verifiability method.

Background technique

At present, although cloud computing service providers can enable users to obtain convenient and efficient remote data storage access services through stable and high-speed network connections, due to the many characteristics of cloud computing, such as virtualization, large-scale, dynamic configuration, and scalability, It still brings many security risks and challenges to large-scale data storage services in the cloud computing environment. In order to improve storage efficiency and utilization of storage space, large data files are usually divided into several small data blocks by cloud computing service providers for storage. The geographical location and storage status of each data block are determined by the user. Unknown, users will inevitably doubt the integrity and consistency of their own data files. As a key indicator for measuring data storage services, how to ensure the integrity and consistency of user data files stored in huge server clusters with unknown geography has always been a major problem faced by cloud computing data storage services. Especially after accidents such as Amazon Simple Storage Service and Google Docs service were unexpectedly interrupted one after another, users have great distrust of whether cloud computing service providers will conceal more security incidents in order to save resources and save costs. Users hope to have a complete set of mechanisms to enable them to have the ability to review the integrity and consistency of data files without consuming too much computing resources and time.

Relevant research has been carried out a long time ago, and good results have been achieved in the efficiency, verifiability, queryability and recoverability of the design scheme. At present, there are two types of common solutions for data integrity and consistency: private audit and public audit, as shown in Figure 1.

As the name implies, the private audit means that the user undertakes the audit of the data files, while the public audit entrusts a trusted third-party audit agency to complete the audit. Although private auditing has higher auditing efficiency due to its simple logic, public auditing can not only provide users with safe and reliable data auditing, but also save users a lot of computing resources and time to a large extent. In a cloud computing environment, users are unlikely to have a lot of time and energy to perform frequent audits on their own data files, and this time-consuming and laborious task is entrusted to a trusted third party with reliable audit protocols and complete solutions It can be said that it is a very good choice for audit institutions to complete. The present invention has a cloud computing data storage security architecture of a trusted third-party audit institution, and designs a data dynamic operation verifiability scheme based on MerkleHash Tree for the storage and operation characteristics of data files in the cloud computing environment.

The research on the verifiability of data storage has been widely concerned by the industry a long time ago, and the solutions proposed by scholars have also achieved certain results in terms of efficiency, verifiability, queryability and recoverability. Unfortunately, the research content of most scholars is limited to the operation of static data files, and many research results cannot satisfy the frequent dynamic operations of data files. The following is a summary of the previous research results of scholars.

In terms of remote storage data authentication, Burns et al. first proposed to ensure the verifiability of data stored in untrusted storage media, and proposed a model concept called provable data possession (PDP). Burns et al. used RSA-based tags to implement the audit function for external data. Unfortunately, Burns et al. did not fully consider the dynamic storage of data. Subsequently, Ateniese et al. proposed a new model that supports dynamic data operations under the PDP model, aiming at the defect of potential safety hazards in the process of converting static storage to dynamic storage based on the PDP model. Unfortunately, the new model of Ateniese et al. does not support all basic data dynamic operations, and important data operation methods including insert operations are not able to appear in the new model. Dr. Wang Cong, a Chinese scientist at the Illinois Institute of Technology in the United States, and others later proposed a solution for distributed environments that can review the correctness of data files and locate possible failure nodes, but similar to the model proposed by Ateniese et al., Wang The scheme of Cong et al. also fails to support all basic dynamic operations. Furthermore, Juels and Kaliski proposed a conceptual model called proof of retrievability (POR). In their literature, checksums and sampling methods are used to ensure the retrievability of the data and guarantee the integrity of the data stored in the data center. Juels and Kaliski use the method of randomly adding additional information to the data block to achieve the purpose of detection. But the POR model limits the number of queries and does not support public auditing schemes. Waters and Shacham then designed an improved POR model, but the improved model only has the ability to provide data recovery for static data. Papamanthou et al. were the first scholars to explore the possibility of constructing a dynamic PDP model. The improved PDP model proposed by them has complete dynamic operation functions and successfully avoids the use of additional data labels. In addition, Devanbu et al. gave a data query verification solution based on Merkle Hash Tree in the literature. Currently, mainstream query verification algorithms based on Merkle Hash Tree structure use it as the basis. A data block verification model based on the POR model is given in the prior art, which is also based on the Merkle Hash Tree data structure, but does not consider the impact of the geographical location of data storage on computing efficiency in a distributed environment.

Contents of the invention

In order to solve the above technical problems, the present invention provides a data dynamic operation verifiability scheme based on Merkle Hash Tree, which is composed of three parts: the user (USER), the cloud computing data center (CDC) and the third-party audit agency (TPA) through the communication network Connection composition. As the requesting party for the data storage service, USER hopes to store the data files it owns in the cloud storage space of the cloud computing data center. USER can be either an individual user or an enterprise user. CDC is responsible for responding to users' data storage service requests, storing users' data files in its own huge data center according to certain rules, and is responsible for the management and maintenance of data files. As a reliable third-party auditor, TPA is entrusted by USER to review the integrity and consistency of the data files stored in the CDC data center. On the basis of referring to previous research results, the solution uses the special tree structure of Merkle Hash Tree to solve the problem of verifying the integrity and consistency of user data files in the cloud computing environment. It not only effectively supports all basic data dynamic operations in the cloud computing environment (including data addition, deletion and modification, etc.), but also fully considers the impact of the geographic location of data storage on computing efficiency in a distributed environment, and is based on Merkle Hash Tree Research on verifiability has made some contributions.

Its technical scheme is as follows:

A method for verifiability of data dynamic operations based on a hash tree, comprising the following steps:

A file preprocessing

Before the file is preprocessed, USER will request CDC to store the data file. CDC authenticates USER according to its preset access control rules. Legitimate users authenticated by the CDC will be granted permission to store files.

After USER passes the CDC authentication, CDC starts to receive the data files that USER needs to store and preprocess them:

(1) First, the data file will be divided into several data blocks of the same size, F→(f1, f2, f3, f4, f5, f6, ...fn).

(2) Then, CDC performs a hash operation on each data block and obtains the hash value H(fi) (1≤i≤n) of all data blocks.

(3) After the hash operation, the data file can be recorded as: F'→(f1+H(f1), f2+H(f2), f3+H(f3), ..., fn+H(fn)) . CDC will temporarily save the hash values of all data blocks in preparation for the next construction of the verification data structure Merkle Hash Tree of the file.

(4) In order to uniquely mark the geographic location of the data block, the scheme adds a 5-byte location tag (LTag) to each data block, and the tag consists of 2-byte sequence tag information and 1-byte rack Composed of tag information and 2-byte node tag information. The sequence mark information records the sequence number of the data block in all data blocks, the rack mark information records the specific rack number of the data block stored in the data center, and the node mark information indicates the specific number of the node server where the data block is stored. serial number. CDC maintains an LTag label list for each data file, recording the LTag label information of all data blocks in the file.

(5) After the tags are added, all data blocks will be stored in the data center by CDC, and the geographical location information stored in the data blocks will also be recorded in the LTag tags of the data blocks themselves. After the LTag tags of all data blocks are recorded, CDC will create an LTag tag information list for the data file that includes the geographic location information of all data blocks.

(6) Subsequently, the construction of the key data structure Merkle Hash Tree is carried out.

1) First, CDC takes out the rack value Rack(LTag(fi)) of all data blocks in the file from the Ltag label list, divides the data blocks stored in different racks, and stores them in the ListRack[] list of the corresponding rack .

2) Then, the CDC sequentially takes out the node information in the Ltag tags of all data blocks from the ListRack[] lists of different racks, and divides the data blocks stored in different nodes of the same rack again.

3) Next, for the data blocks stored in the same rack and the same node, CDC will take out the sequence information in their Ltag tags, arrange them in order, use the hash value of the data block as the leaf node to construct the node Merkle Hash Tree, and calculate Its root node value (if the node has only one data block, the hash value of the data block is the root node value of the node's Merkle Hash Tree), recorded as NRoot[i, j] (where i represents the rack number, j stands for the node number where it is located).

4) After completing the construction of the Merkle Hash Tree of all nodes stored in the file and the calculation of the root node value, CDC will sort the root node values of the Merkle Hash Tree of all nodes stored in the same rack according to the order of the nodes, and use it as a leaf node construction Merkle Hash Tree of each rack, and calculate its root node value (if there is only one node in the rack to store data files, then the Merkle Hash Tree root node value of the node is the root node value of the rack Merkle Hash Tree), record It is RRoot[i] (where i represents the serial number of the rack).

5) Finally, arrange the root node values of all rack Merkle Hash Trees in order, use their root node values as the Merkle Hash Tree of the leaf node construction file, and calculate their root node values (if only one rack stores data file, then the Merkle Hash Tree root node value of the rack is the root node value of the file Merkle Hash Tree), denoted as FRoot.

Verification of B data files

(1) First, CDC completes the storage of USER's data files and submits relevant verification information of USER's stored data files to TPA. Before the data file is deleted by USER, as long as there is a change, CDC will be responsible for generating the latest verification information for the data file and updating it with TPA in real time.

(2) Then, CDC notifies USER that the storage of data files and the generation of verification information have been completed, and informs USER that it can start entrusting TPA to verify the integrity and consistency of data files.

(3) USER can choose to communicate with TPA immediately or another time to entrust TPA to verify the integrity and consistency of data files.

(4) After receiving the audit entrustment request from USER, TPA will conduct regular or irregular audit verification of data files according to USER's needs, and keep verification logs for all audit operations for future inspection by USER. During the verification process, if data file verification fails, TPA will inform USER by email or SMS, and at the same time request CDC to take remedial measures such as copy recovery of data files.

The verification process of data files in the scheme refers to the periodic and irregular data file integrity and consistency review entrusted by TPA by USER. TPA completes the verification work entrusted by USER by submitting a data file integrity and consistency verification request to CDC and reviewing the verification information replied by CDC. The specific description is as follows:

1) In the initial phase of verification, TPA generates verification information checkM(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j])). The checkM verification message consists of three parts: one is the user's personal information UInfo, UInfo can help CDC quickly and accurately locate the owner of the data file that needs to be checked; the other is the data file information that needs to be checked FInfo, FInfo clearly points out that it needs to be checked The third is the specific Merkle Hash Tree root node information RInfo, RInfo consists of the data file Merkle Hash Tree root node value FRoot, the specified rack Merkle Hash Tree root node value RRoot[i] and the specified node Merkle Hash Tree root node value NRoot[i, j] consists of three parts.

2) After the verification message checkM is generated, the TPA will transmit the checkM to the CDC through the communication network.

3) After CDC receives the verification information, it first decomposes checkM to determine the relevant content to be reviewed by TPA.

4) Then, CDC uses the relevant Merkle Hash Tree generation algorithm introduced in Section A above to regenerate and calculate the corresponding Merkle Hash Tree and its root node value.

5) After completing the generation of all verification information, CDC will generate verification reply information respondM(UInfo, FInfo, RInfo'(FRoot', RRoot'[i], NRoot'[i, j])). Among them, the contents of UInfo and FInfo are consistent with the first two parts of the checkM verification information, and RInfo' returns the relevant Merkle Hash Tree root node values that TPA needs to review, including the specified data file Merkle Hash Tree root node value FRoot', the specified The rack Merkle Hash Tree root node value RRoot'[i] and the specified node Merkle Hash Tree root node value NRoot'[i, j] are three parts.

6) Finally, after receiving the response message from respondM, TPA will compare it with the root node value of the relevant Merkle Hash Tree saved by itself. If the result is consistent, the review fails and the data is complete and consistent with the previous version. On the contrary, it means that the data is inconsistent with the previous version, and TPA will require CDC to perform abnormal handling operations such as copy recovery of data files, and inform USER of the review results.

Dynamic manipulation of C data

Insert operation of C1 data

The insert operation is the most basic dynamic operation content of the data file, and it is also the most complex dynamic operation in the scheme compared to the modify and delete operations. For example, to insert data block fi' after the i-th data block fi' of the data file, the operation steps of the scheme can be described as follows:

(1) CDC calculates the hash value H(fi') of the new data block fi', and creates tag information LTag(fi') for the data block fi' that needs to be inserted.

(2) Generate and run the insert operation function Insert(fi', H(fi'), LTag(fi)), and use LTag(fi) to locate the specific position where the data block is inserted, and perform the insert operation of the data block.

(3) Call the Merkle Hash Tree insertion function MerkleInsert(h(fi), h(fi'), LTag(fi)), which connects h(fi) and h(fi'), and The value of is hashed again. Then CDC uses the new result generated by the hash operation to replace the hash value of the node at the LTag(fi) position in the original node Merkle Hash Tree. It is worth noting that the result obtained by hashing the values after the connection is no longer the leaf node of the Merkle Hash Tree, but an intermediate node generated by the two leaf nodes h(fi) and h(fi’).

(4) Call the Merkle Hash Tree generation function CreateMerkle() of the node where fi' is located to generate a new node MerkleHashTree, and calculate its root node value NRoot[i, j], where i represents the node where the data block is located, and j represents the data block where the rack is located.

(5) Call the Merkle Hash Tree generation function CreateMerkle() of the rack where fi’ is located to generate a new rack Merkle Hash Tree, and calculate its root node value RRoot[i], where i represents the rack where the data block is located.

(6) Recall the file Merkle Hash Tree generation function CreateMerkle() to generate a new file Merkle HashTree and calculate its root node value FRoot.

(7) CDC reports the update information to TPA, and sends update request information UpdateRequest(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j]). Among them, UInfo, FInfo and RInfo are the same as defined in Section B .

(8) The TPA updates the verification information of the data file according to the specific content of the update request information for future inspection.

C2 data modification operation

Modification operations are the most frequent data dynamic operations in cloud computing applications. For example, if the i-th data block fi of the data file is modified, the i-th data block will become fi' after the modification. The specific operation steps of the scheme are described as follows:

(1) CDC calculates the hash value H(fi’) of the new data block fi’, and uses the tag information LTag(fi) of fi as the tag information LTag(fi’) of fi’.

(2) Generate and run the update operation function Update(fi', H(fi'), LTag(fi)), locate the specific position of the data block that needs to be modified through LTag(fi), and perform the modification operation of the data block.

(3) Call the Merkle Hash Tree modification operation function MerkleUpdate(fi', H(fi'), LTag(fi')), use LTag(fi') to locate the specific location of the data block that needs to be modified, use H(fi' ) instead of H(fi).

(4) Call the Merkle Hash Tree generation function CreateMerkle() of the node where fi' is located to generate a new node Merkle Hash Tree, and calculate its root node value NRoot[i, j], where i represents the node where the data block is located, and j represents the data The rack where the block resides.

(5) Call the Merkle Hash Tree generation function CreateMerkle() of the rack where fi’ is located to generate a new rack Merkle Hash Tree, and calculate its corresponding root node value RRoot[i], where i represents the rack where the data block is located.

(6) Call the file Merkle Hash Tree generation function CreateMerkle() to generate a new file Merkle Hash Tree and calculate its root node value FRoot.

(7) CDC reports the update information to TPA, and sends update request information UpdateRequest(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j]). Among them, UInfo, FInfo and RInfo are the same as defined in Section B .

(8) The TPA updates the verification information of the data file according to the specific content of the update request information for future inspection.

C3 data deletion operation

For example, to delete the data block fi+1 after the i-th data block fi of the data file, the specific operation steps of the scheme are described as follows:

(1) Generate and run the delete operation function Delete(fi+1, H(fi+1), LTag(fi+1)), use LTag(fi+1) to locate the specific location of the data block to be deleted, and perform data Block delete operation.

(2) Call the Merkle Hash Tree delete operation function MerkleDelete(LTag(fi+1), LTag(fi)) to delete h(fi+1) at the position of LTag(fi+1), and use the value of h(fi) Replace the Merkle Hash Tree intermediate node h(h(fi)+h(fi+1)) generated by the hash of h(fi) and h(fi+1). It is worth noting that although the deletion operation reduced the Merkle Hash Tree by two leaf nodes, the basic logical structure of the Merkle Hash Tree has not changed.

(3) Call the Merkle Hash Tree generation function CreateMerkle() of the node where fi is located to generate a new node MerkleHash Tree, and calculate its root node value NRoot[i, j], where i represents the node where the data block is located, and j represents the data block the rack on which it is located.

(4) Call the Merkle Hash Tree generation function CreateMerkle() of the rack where fi is located to generate a new rack Merkle Hash Tree, and calculate its corresponding root node value RRoot[i], where i represents the rack where the data block is located.

(5) Call the file Merkle Hash Tree generation function CreateMerkle() to generate a new file Merkle Hash Tree and calculate its root node value FRoot.

(6) CDC reports the update information to TPA, and sends update request information UpdateRequest(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j]). Among them, UInfo, FInfo and RInfo are the same as defined in Section B .

(7) The TPA updates the data file of the USER according to the specific content of the update request information for future inspection.

Further preferably, (2) CDC in A performs a hash operation on each data block and obtains hash values of all data blocks. The scheme selects SHA-1 as the hash function to perform hash operations on data blocks.

Further preferably, (6) in said A carries out the construction of key data structure Merkle HashTree. The scheme stipulates that the hash values of all data blocks in the data file are used as the leaf nodes of the Merkle Hash Tree to construct the tree. The scheme is different from the previous scholars who only arranged the file Merkle Hash Tree according to the sequence information of the data blocks, but will refer to the LTag tag information of all data blocks, and construct the data files sequentially in the order of nodes first, then racks, and then files The node MerkleHash Tree, the rack Merkle Hash Tree and the file Merkle Hash Tree, and calculate its root node value.

Further preferably, in 1) of (4) in B, at the initial stage of verification, the TPA generates verification information checkM(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j])). The scheme allows TPA to arbitrarily select one, two or three items of Merkle Hash Tree root node information for review.

Further preferably, the insertion operation of the data in C1. The scheme defines an insert operation as inserting a new data block after a specific data block in the data file. The scheme stipulates that the newly inserted data block will be stored in the same server node as the specific data block before it. Therefore, the data insertion operation in the scheme does not change the logical structure of the single server node MerkleHash Tree.

Further preferably, the modification operation of the data in C2. The scheme defines the basic data modification operation as replacing the data block that needs to be modified with a new data block. The scheme stipulates that the modified data block is the same as the storage node before it was modified. Therefore, the data modification operation in the scheme does not change the logical structure of the Merkle Hash Tree of a single server node.

Further preferably, the data in C3 is deleted. The scheme defines it as deleting data blocks after a specific data block of the data file. The scheme stipulates that if the deleted data block is the only data block of the node where it is located, step 2 in C3 will directly operate on the rack Merkle Hash Tree, then skip steps 3 and 4, and start directly from step 5.

Beneficial effects of the present invention:

The present invention is based on certain security assumptions (communication channel reliability, TPA trustworthiness, CDC faithfulness, etc.). Therefore, not only can USER safely hand over the verification and auditing of data files to TPA, but also the maintenance and calculation of verification information does not have to be done by USER himself. The solution makes full use of CDC's huge computing resources and storage space in the cloud computing environment, not only maximizes the advantages of large-scale and virtualization of cloud computing, but also saves a lot of user resources. Moreover, compared with the previous research results of scholars, the scheme can support all basic data dynamic operations (insert, delete and modify, etc.) in the cloud computing environment. In terms of data integrity and consistency verification, the scheme uses the root node value of the divided MerkleHash Tree as verification information, and compares the advantages of the data structure in data integrity and consistency verification with the cloud computing environment. The distribution characteristics of data storage are organically integrated. In terms of the construction of the Merkle Hash Tree and the calculation of the root node value, the scheme cleverly uses the LTag tag marked with the geographical location information of the data block storage, which not only effectively reduces the internal communication of the CDC during the calculation process of the Merkle HashTree root node value It takes a lot of time, and at the same time, after the USER performs dynamic operations on the data files, the system no longer needs to use the hash values of all data blocks in the data files to reconstruct the file Merkle Hash Tree and calculate the root node value, effectively improving The rate at which data file verification messages are generated after dynamic operations. In addition, the proposal of LTag tags and hierarchical Merkle Hash Tree design ideas allows the scheme to allow TPA to audit and verify a single server node or rack that stores data blocks in CDC. Compared with the scheme without hierarchical construction of Merkle Hash Tree, this scheme can verify the information of specific storage nodes or racks through checkM. When there is an inconsistency in the verification, the failure node can be quickly and accurately located. At the same time, in terms of Merkle Hash Tree reconstruction, since it is not necessary to use all the data blocks of the file to reconstruct the Merkle Hash Tree of the file, the scheme has a greater efficiency advantage in terms of time. Compared with the research results of previous scholars, the scheme of the present invention has certain efficiency advantages.

Description of drawings

Fig. 1 is the audit type of cloud computing data files in the background technology;

Figure 2 is a flow chart of CDC performing USER identity verification;

Figure 3 is a schematic diagram of file segmentation;

Figure 4 is a schematic diagram of the format of the LTag tag;

Figure 5 is a schematic diagram of the construction of Merkle HashTree;

Fig. 6 is the rack division flowchart of data block;

Fig. 7 is the node division flow chart of data block;

Figure 8 is a flowchart of the construction of the node Merkle Hash Tree and the calculation of the root node value;

Figure 9 is a flowchart of the construction of the rack Merkle Hash Tree and the calculation of the root node value;

Figure 10 is a flowchart of the construction of the file Merkle Hash Tree and the calculation of the root node value;

Figure 11 is a description of the basic tasks of USER, CDC and TPA;

Fig. 12 is the verification process figure of data file;

Figure 13 is a schematic diagram of the insertion operation of the Merkle Hash Tree;

Figure 14 is a schematic diagram of the modification operation of the Merkle Hash Tree;

Figure 15 is a schematic diagram of the deletion operation of Merkle Hash Tree;

Figure 16 is a comparison diagram of the reconstruction time of the delete operation;

Figure 17 is a comparison diagram of the reconstruction time of the modification operation;

Figure 18 is a comparison chart of the reconstruction time of the insert operation.

Detailed ways

The technical solutions of the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

security assumption

The scheme assumes that all communication channels do not have a large area of data packet loss (communication channels include three parts between USER and CDC, between CDC and TPA, and between TPA and USER). At the same time, the TPA in the scheme is an unbiased and completely credible third-party audit organization, which can faithfully complete all tasks entrusted by USER. The security assumption of CDC in the scheme is slightly different from previous studies. CDC is no longer completely untrustworthy, but has a certain degree of curiosity but can faithfully complete all tasks. CDC guarantees the correctness, non-deception and non-repudiation of all parameter calculation results undertaken by itself, and can unconditionally respond to audit requests for any user data files at any time. After all user data files in the scheme are preprocessed, there is no possibility of mutual interference between data blocks. In addition, the focus of the solution is how to support the integrity and consistency verification of user data files stored in CDC and the dynamic operation of data.

file preprocessing

Before the file is preprocessed, USER will request CDC to store the data file. CDC authenticates USER according to its preset access control rules. Legitimate users who pass the CDC authentication will obtain permission to store files, as shown in Figure 2.

After USER passes the CDC authentication, CDC starts to receive the data files that USER needs to store and preprocess them:

First, the data file will be divided into several data blocks of the same size, F→(f ₁ , f ₂ , f ₃ , f ₄ , f ₅ , f ₆ , . . . f _n ), as shown in FIG. 3 .

Then, CDC performs a hash operation on each data block and obtains the hash value H(f _i ) (1≤i≤n) of all data blocks. The scheme selects SHA-1 as the hash function to perform hash operations on data blocks. After the hash operation, the data file can be recorded as: F'→(f ₁ +H(f ₁ ), f ₂ +H(f ₂ ), f ₃ +H(f ₃ ),..., f _n +H (f _n )). CDC will temporarily save the hash values of all data blocks in preparation for the subsequent construction of the file verification data structure Merkle Hash Tree.

In order to uniquely mark the geographic location of the data block, the scheme adds a 5-byte location tag (LTag) to each data block. The tag consists of 2-byte sequence tag information, 1-byte rack tag information, and 2 bytes of node tag information. The sequence mark information records the sequence number of the data block in all data blocks, the rack mark information records the specific rack number of the data block stored in the data center, and the node mark information indicates the specific number of the node server where the data block is stored. serial number. CDC maintains an LTag label list for each data file, recording the LTag label information of all data blocks in the file. The specific format of the label is shown in Figure 4.

The LTag tag plays an extremely important role in the subsequent operation of the scheme. At present, the data block storage allocation scheme that adopts the rate priority is more and more favored by people in the industry. The principle of speed priority enables data blocks to be quickly stored in idle server nodes in the data center, effectively avoiding queuing and waiting during the storage of data blocks. For example, a data center with 10 racks and 100 nodes in each rack stores a data file with 10,000 data blocks. Each node does not store 10 data blocks on average, but stores them according to data blocks. The status of the server nodes in each rack at the time determines the specific location of the data block storage. Adding LTag tags to data blocks clarifies the specific node location information stored in all data blocks, which provides important location information for the construction of the Merkle Hash Tree, the calculation of the root node value, and the location of error nodes, making the solution more efficient. can get some improvement.

After the tag is added, all data blocks will be stored in the data center by CDC, and the geographical location information stored in the data block will also be recorded in the LTag tag of the data block itself. After the LTag tags of all data blocks are recorded, CDC will create an LTag tag information list for the data file that includes the geographic location information of all data blocks.

Subsequently, the construction of the key data structure Merkle Hash Tree is carried out. The scheme stipulates that the hash values of all data blocks in the data file are used as the leaf nodes of the Merkle Hash Tree to construct the tree. The scheme is different from the previous scholars who only arranged the file Merkle Hash Tree according to the sequence information of the data blocks, but will refer to the LTag tag information of all data blocks, and construct the data files sequentially in the order of nodes first, then racks, and then files The node Merkle Hash Tree, the rack Merkle Hash Tree and the file Merkle Hash Tree, and calculate its root node value. The description of the construction algorithm is shown in Figure 5:

First, CDC takes out the rack value Rack(LTag(f _i )) of all data blocks in the file from the Ltag tag list, divides the data blocks stored in different racks, and stores them in the ListRack[] list of the corresponding rack. Then, the CDC sequentially takes out the node information in the Ltag tags of all data blocks from the ListRack[] lists of different racks, and divides the data blocks stored in different nodes of the same rack again. Next, for the data blocks stored in the same rack and the same node, CDC will take out the order information in their Ltag tags, arrange them in order, use the hash value of the data block as the leaf node to construct the node Merkle HashTree, and calculate its root node value (if there is only one data block in the node, the hash value of the data block is the root node value of the node’s Merkle Hash Tree), recorded as NRoot[i, j] (where i represents the rack number, j represents the node number where it is located). After completing the construction of the Merkle Hash Tree of all nodes stored in the file and the calculation of the root node value, CDC will sort the root node values of the Merkle Hash Tree of all nodes stored in the same rack in order of nodes, and use them as leaf nodes to construct each machine Merkle Hash Tree of the rack, and calculate its root node value (if the rack has only one node to store data files, then the Merkle Hash Tree root node value of the node is the root node value of the rack Merkle Hash Tree), recorded as RRoot [i] (where i represents the serial number of the rack). Finally, sort the root node values of all rack Merkle Hash Trees in order, use their root node values as the Merkle Hash Tree of leaf node construction files, and calculate their root node values (if only one rack stores data files , then the Merkle Hash Tree root node value of the rack is the root node value of the file Merkle HashTree), denoted as FRoot.

The Merkle Hash Tree construction algorithm, codes and flowcharts of each step in the scheme are described as follows:

The scheme stipulates that in the rack division stage of data blocks, all data blocks that make up the data file will be traversed, and the data blocks will be classified according to the rack information to which all data blocks belong, and the data blocks belonging to different racks will be divided ,As shown in Figure 6.

After the rack division of the data block is completed, the scheme will divide the nodes of the data blocks belonging to different racks. The scheme stipulates that CDC will traverse all the data blocks belonging to the same rack, and divide them again according to the different racks they belong to, as shown in Figure 7.

After the division of data blocks is completed, the key data structure of the scheme, the Merkle Hash Tree, can be constructed. CDC will first build the Merkle Hash Tree of all nodes. CDC will sort the hash values of the data blocks belonging to the same node in order, and then call the tree building function to build the Merkle Hash Tree. After the node Merkle Hash Tree is built, CDC will also calculate the root node values of all node Merkle Hash Trees, as shown in Figure 8.

The construction of the rack Merkle Hash Tree in the scheme is to use the root node value of the relevant node Merkle Hash Tree as its leaf node for construction. CDC will first sort the Merkle Hash Tree root node values of nodes belonging to the same rack in sequence, and then call the tree building function to build the rack Merkle Hash Tree. After the construction of Merkle Hash Tree of all racks is completed, CDC will calculate its corresponding root node value, as shown in Figure 9.

The construction of the file Merkle Hash Tree is similar to that of the rack Merkle Hash Tree, except that during the construction of the file Merkle HashTree, CDC uses the root node values of all rack Merkle Hash Trees and calculates their root node values. CDC will sort the Merkle Hash Tree root node values of all racks in order, and then call the tree building function to build the Merkle Hash Tree of the file. Finally, CDC will calculate the Merkle Hash Tree root node value of the data file, as shown in Figure 10.

Validation of data files

In the process of file preprocessing, the scheme constructs the Merkle Hash Tree of nodes, racks and files respectively, and calculates the corresponding root node values. All root node values will become the main verification information of the scheme. The scheme stipulates that all verification information of data files will not only be stored in CDC, but also have a backup in TPA. CDC is responsible for updating the latest verification information of data files in real time through the communication network and TPA, so that TPA can complete the verification of data integrity and consistency entrusted by USER. The scheme stipulates that TPA needs to update the latest LTag list information of data files in real time, the Merkle Hash Tree root node values of all nodes in the stored data files, the Merkle Hash Tree root node values of all racks in the stored data files, and the files of the stored data files Merkle Hash Tree root node value. In addition, TPA is clear about the generation rules and methods of all verification information of data files.

The following describes the interoperation of USER, CDC and TPA in the solution, as shown in Figure 11:

First, CDC completes the data file storage of USER and submits relevant verification information of the data files stored by USER to TPA. Before the data file is deleted by USER, as long as there is a change, CDC will be responsible for generating the latest verification information for the data file and updating it with TPA in real time. Then, CDC notifies USER that the storage of data files and the generation of verification information have been completed, and informs USER that it can start entrusting TPA to verify the integrity and consistency of data files. USER can choose to communicate with TPA immediately or choose another time to entrust TPA to verify the integrity and consistency of data files. After receiving the audit entrustment request from USER, TPA will conduct regular or irregular audit verification of data files according to USER's needs, and keep verification logs for all audit operations for future inspection by USER. During the verification process, if data file verification fails, TPA will inform USER by email or SMS, and at the same time request CDC to take remedial measures such as copy recovery of data files.

The verification process of data files in the scheme refers to the periodic and irregular data file integrity and consistency review entrusted by TPA by USER. TPA completes the verification work entrusted by USER by submitting a data file integrity and consistency verification request to CDC and reviewing the verification information replied by CDC, as shown in Figure 12. The specific description is as follows:

In the initial phase of verification, TPA generates verification information checkM(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j])). The checkM verification message consists of three parts: one is the user's personal information UInfo, UInfo can help CDC quickly and accurately locate the owner of the data file that needs to be checked; the other is the data file information that needs to be checked FInfo, FInfo clearly points out that it needs to be checked The third is the specific Merkle Hash Tree root node information RInfo, RInfo consists of the data file Merkle Hash Tree root node value FRoot, the specified rack Merkle Hash Tree root node value RRoot[i] and the specified node Merkle Hash Tree root node value NRoot[i, j] consists of three parts. The scheme allows TPA to arbitrarily select one, two or three items of Merkle Hash Tree root node information for review. After the verification message checkM is generated, the TPA will transmit checkM to the CDC through the communication network. After CDC receives the verification information, it first decomposes checkM to determine the relevant content to be reviewed by TPA. Then, CDC uses the relevant Merkle Hash Tree generation algorithm to regenerate and calculate the corresponding Merkle Hash Tree and its root node value. After completing the generation of all verification information, CDC will generate verification reply information respondM(UInfo, FInfo, RInfo'(FRoot', RRoot'[i], NRoot'[i, j])). Among them, the contents of UInfo and FInfo are consistent with the first two parts of the checkM verification information, and RInfo' returns the relevant Merkle Hash Tree root node values that TPA needs to review, including the specified data file Merkle Hash Tree root node value FRoot', the specified The rack Merkle Hash Tree root node value RRoot'[i] and the specified node Merkle Hash Tree root node value NRoot'[i, j] are three parts. Finally, after receiving the respondM verification reply message, TPA will compare it with the relevant Merkle Hash Tree root node value saved by itself. If the result is consistent, the review fails and the data is complete and consistent with the previous version. On the contrary, it means that the data is inconsistent with the previous version, and TPA will require CDC to perform abnormal handling operations such as copy recovery of data files, and inform USER of the review results.

Dynamic manipulation of data

In the cloud computing environment, most data files frequently perform three basic dynamic operations: data insertion, data modification, and data deletion. In this solution, after the data files undergo these three dynamic operations, all verification information related to the data files must be regenerated by CDC. The present invention will specifically introduce three reconstruction algorithms of the MerkleHash Tree data structure after the data file is dynamically operated.

data insertion

The insert operation is the most basic dynamic operation content of the data file, and it is also the most complex dynamic operation in the scheme compared to the modify and delete operations. The scheme defines an insert operation as inserting a new data block after a specific data block in the data file. The scheme stipulates that the newly inserted data block will be stored in the same server node as the specific data block before it. Therefore, the data insertion operation in the scheme does not change the logical structure of the single server node Merkle Hash Tree. For example, to insert data block f _i ' after the i-th data block f _i of the data file, the operation steps of the scheme can be described as follows:

1. The CDC calculates the hash value H(f _i ') of the new data block f _i ', and creates tag information LTag(f _i ') for the data block f _i ' that needs to be inserted.

2. Generate and run the insert operation function Insert(f _i ', H(f _i '), LTag(f _i )), locate the specific position where the data block is inserted through LTag(f _i ), and perform the insert operation of the data block.

3. Call the Merkle Hash Tree insertion function MerkleInsert(h(f _i ), h(f _i '), LTag(f _i )), which connects h(f _i ) and h(f _i '), And perform a hash operation on the concatenated values again. Then CDC uses the new result generated by the hash operation to replace the hash value of the node at the LTag(f _i ) position in the original node Merkle Hash Tree. It is worth noting that the result obtained by hashing the values after concatenation is no longer a leaf node of the Merkle Hash Tree, but an intermediate node generated by the two leaf nodes h(f _i ) and h(f _i '). Figure 13 depicts the change process of this step in the node Merkle Hash Tree in detail.

4. Call the Merkle Hash Tree generation function CreateMerkle() of the node where f _i 'is located to generate a new node MerkleHash Tree, and calculate its root node value NRoot[i, j], where i represents the node where the data block is located, and j represents the data The rack where the block resides.

5. Call the Merkle Hash Tree generation function CreateMerkle() of the rack where f _i ' is located to generate a new rack MerkleHash Tree, and calculate its root node value RRoot[i], where i represents the rack where the data block is located.

6. Recall the file Merkle Hash Tree generation function CreateMerkle() to generate a new file Merkle HashTree and calculate its root node value FRoot.

7. The CDC reports the update information to the TPA, and sends update request information UpdateRequest(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j]).

8. The TPA updates the verification information of the data file according to the specific content of the update request information for future inspection.

Data modification operations

Modification operations are the most frequent data dynamic operations in cloud computing applications. The scheme defines the basic data modification operation as replacing the data block that needs to be modified with a new data block. The scheme stipulates that the modified data block is the same as the storage node before it was modified. Therefore, the data modification operation in the scheme does not change the logical structure of the Merkle Hash Tree of a single server node. For example, the i-th data block f _i of the data file is modified, and the i-th data block will become f _i ' after the modification. The specific operation steps of the scheme are described as follows:

1. The CDC calculates the hash value H(f _i ') of the new data block f _i ', and uses the tag information LTag(f _i ) of f _i as the tag information LTag(f _{i '} ) of f i '.

2. Generate and run the update operation function Update(f _i ', H(f _i '), LTag(f _i )), use LTag(f _i ) to locate the specific location of the data block to be modified, and modify the data block operate.

3. Call the Merkle Hash Tree modification operation function MerkleUpdate(f _i ', H(f _i '), LTag(f _i ')), use LTag(f _i ') to locate the specific location of the data block to be modified, use H (f _i ') replaces H(f _i ). Figure 14 depicts the change process of this step in the node Merkle Hash Tree in detail.

4. Call the Merkle Hash Tree generation function CreateMerkle() of the node where f _i 'is located to generate a new node MerkleHash Tree, and calculate its root node value NRoot[i, j], where i represents the node where the data block is located, and j represents the data The rack where the block resides.

5. Call the Merkle Hash Tree generating function CreateMerkle() of the rack where f _i ' is located to generate a new rack MerkleHash Tree, and calculate its corresponding root node value RRoot[i], where i represents the rack where the data block is located.

6. Call the file Merkle Hash Tree generation function CreateMerkle() to generate a new file Merkle Hash Tree and calculate its root node value FRoot.

7. The CDC reports the update information to the TPA, and sends the update request information UpdateRequest(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j]). Among them, UInfo, FInfo and RInfo are the same as defined in Section 3.4.

8. The TPA updates the verification information of the data file according to the specific content of the update request information for future inspection.

Data deletion operation

Regarding the data deletion operation, the scheme defines it as deleting the data blocks following the specific data block of the data file. For example, the data block f _i+1 after the i-th data block f _i of the data file is deleted, and the specific operation steps of the scheme are described as follows:

1. Generate and run the delete operation function Delete(f _i+1 , H(f _i+1 ), LTag(f _i+1 )), and use LTag(f _i+1 ) to locate the specific location of the data block to be deleted , to delete the data block.

2. Call the Merkle Hash Tree delete operation function MerkleDelete(LTag(f _i+1 ), LTag(f _i )) function to delete h(f _i+1 ) at the position of LTag(f _i+1 ), use h( The f _i ) value replaces the intermediate node h(h(f _i )+h(f _i+1 )) of the Merkle Hash Tree generated by the hash of h(f _i ) and h(f _i+1 ). It is worth noting that although the deletion operation reduced the Merkle Hash Tree by two leaf nodes, the basic logical structure of the Merkle Hash Tree has not changed. Figure 15 depicts in detail the change process of this step in the node Merkle HashTree.

3. Call the Merkle Hash Tree generation function CreateMerkle() of the node where f _i is located to generate a new node MerkleHash Tree, and calculate its root node value NRoot[i, j], where i represents the node where the data block is located, and j represents the data block the rack on which it is located.

4. Call the Merkle Hash Tree generation function CreateMerkle() of the rack where f _i is located to generate a new rack MerkleHash Tree, and calculate its corresponding root node value RRoot[i], where i represents the rack where the data block is located.

5. Call the file Merkle Hash Tree generation function CreateMerkle() to generate a new file Merkle Hash Tree and calculate its root node value FRoot.

6. The CDC reports the update information to the TPA, and sends the update request information UpdateRequest(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j]). Among them, UInfo, FInfo and RInfo are the same as defined in Section 3.4.

7. TPA updates the data file of USER according to the specific content of the update request information for future inspection.

In addition, the plan stipulates that if the deleted data block is the only data block of the node where it is located, step 2 will directly operate on the rack Merkle Hash Tree, then skip steps 3 and 4, and start directly from step 5.

analysis of the program

Because the scheme is based on certain security assumptions (communication channel is reliable, TPA is credible and CDC is faithful, etc.). Therefore, not only can USER safely hand over the verification and auditing of data files to TPA, but also the maintenance and calculation of verification information does not have to be done by USER himself. The solution makes full use of CDC's huge computing resources and storage space in the cloud computing environment, not only maximizes the advantages of large-scale and virtualization of cloud computing, but also saves a lot of user resources. Moreover, compared with the previous research results of scholars, the scheme can support all basic data dynamic operations (insert, delete and modify, etc.) in the cloud computing environment. In terms of data integrity and consistency verification, the scheme uses the root node value of the divided MerkleHash Tree as verification information, and compares the advantages of the data structure in data integrity and consistency verification with the cloud computing environment. The distribution characteristics of data storage are organically integrated. In terms of the construction of the Merkle Hash Tree and the calculation of the root node value, the scheme cleverly uses the LTag tag marked with the geographical location information of the data block storage, which not only effectively reduces the internal CDC in the calculation process of the Merkle Hash Tree root node value A lot of time is spent on communication, and at the same time, after the USER performs dynamic operations on the data file, the system does not need to use the hash value of all data blocks of the data file to reconstruct the Merkle Hash Tree of the file and calculate the value of the root node, effectively Increased the rate at which datafile validation messages are generated after dynamic operations. In addition, the proposal of LTag tags and hierarchical Merkle Hash Tree design ideas allows the scheme to allow TPA to audit and verify a single server node or rack that stores data blocks in CDC. Compared with the scheme without hierarchical construction of Merkle Hash Tree, this scheme can verify the information of specific storage nodes or racks through checkM. When there is an inconsistency in the verification, the failure node can be quickly and accurately located. At the same time, in terms of Merkle Hash Tree reconstruction, since it is not necessary to use all the data blocks of the file to reconstruct the Merkle Hash Tree of the file, the scheme has a greater efficiency advantage in terms of time. Compared with the research results of previous scholars, the scheme of the present invention has certain efficiency advantages.

Table 1 lists the comparison results between the scheme described in this paper and the research results of previous scholars in terms of support for dynamic operations, support for public auditing, time complexity for verifying data integrity, and support for locating inconsistent server nodes. .

Table 1 Comparison of schemes

In Table 1, the solution proposed in prior art 2 only supports a limited number of integrity verifications, and does not support data insertion operations. The literature does not give a clear program implementation process design. From the comparison of the data shown in the table, it can be seen that the scheme of the present invention is not inferior to the previous research results in the support of dynamic operations, the support of public auditing and the time complexity of verifying data integrity, but for inconsistent server nodes In terms of positioning support, it has advantages that other research results do not have.

Assuming that the hash time of a single data block is T _h , and the construction time of Merkle Hash Tree is (LeafA-1)T _m (where LeafA is the number of leaf nodes of Merkle Hash Tree), the unit information communication between nodes in the same rack The time is T _n , and the unit communication time between racks is T _r . Then the calculation formula of time overhead calculation formula for the construction of file Merkle Hash Tree and dynamic operations such as insertion, modification and deletion of data files can be summarized as follows:

The calculation of the file Merkle Hash Tree construction time T _CreatMHT of the data file in the file preprocessing process is shown in formula 3-1.

${\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; CreateMHT</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; RackA</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; Rac</span>}{\mathrm{<span\; class="notranslate">\; k</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}\mathrm{<span\; class="notranslate">\; NA</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; [</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; \&times;</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; rack</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}\mathrm{<span\; class="notranslate">\; BA</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; RackA</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; [</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; \&times;</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; RackNA</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$ $<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; \&times;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; RackA</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; RackA</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; RackNA</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; RackA</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; FileBA</span>}$

Among them, RackA is the total number of racks where the data blocks are distributed, Rack _i NA is the total number of nodes in the i-th rack, Rack _i N _j BA is the total number of data blocks of the j-th node in the i-th rack, and RackNA _i is The total number of nodes in the i-th rack, and FileBlockA is the total number of data blocks in the file.

The insertion operation time of the data file consumes the calculation of T _Inserter t, as shown in Formula 3-2:

T _Insert ＝T _m ×(Rack _i N _j BA-1)+T _m ×(RackNA _i -1) (2)

+T _m ×(RackA-1)+T _n ×RackNA _i +T _r ×RackA+T _h

The data file deletion operation takes time to calculate T _Delete , as shown in Equation 3-3:

T _Delete =T _m ×(Rack _i N _j BA-1)+T _m ×(RackNA _i -1) (3)

+T _m ×(RackA-1)+T _n ×RackNA _i +T _r ×RackA

The modification operation time of the data file consumes the calculation of T _Update , as shown in Formula 3-4:

T _Update =T _m ×(Rack _i N _j BA-1)+T _m ×(RackNA _i -1) (4)

+T _m ×(RackA-1)+T _n ×RackNA _i +T _r ×RackA+T _h

In addition, this paper also uses the OpenSSL0.9.81 function library to write the relevant simulation experiment codes of the scheme. The experimental environment is to run Ubuntu 10.04 on a VMware Workstation 6.0 virtual machine built on the Windows XP operating system, the processor is a Pentium dual-core E5300 processor, and the allocated memory capacity is 0.5GB. The file size is 1GB and the chunk size is 0.5MB.

The simulation experiment describes how the hierarchical Merkle Hash Tree reconstruction described in this paper and the non-hierarchical Merkle Hash Tree reconstruction after the data files are deleted, modified, and inserted in the case of different numbers of data block distribution nodes are described. The comparison of structures in terms of time.

The reconstruction time comparison of Merkle Hash Tree after the data file is deleted is shown in Figure 16.

The reconstruction time comparison of Merkle Hash Tree after the data file is modified is shown in Figure 17.

The reconstruction time comparison of Merkle Hash Tree after the data file is inserted is shown in Figure 18.

In order to make the comparison effect more obvious, the experiment assumes that all data blocks of the data file are stored in different nodes of the same rack on average. Therefore, when the number of nodes is 1, the hierarchical Merkle Hash Tree structure can also be regarded as performing a hash operation on all data blocks of the data file to construct the Merkle Hash Tree of the data file, which is different from the Merkle HashTree without hierarchical Same construction. From the above simulation results, it can be seen that whether the data file is deleted, modified or inserted, the hierarchical Merkle Hash Tree structure obviously saves time compared to the non-hierarchical Merkle Hash Tree structure. Moreover, within a certain range of the number of nodes, the construction time of the hierarchical Merkle Hash Tree will decrease as the number of nodes increases. Therefore, the hierarchical Merkle Hash Tree construction scheme adopted in this paper has obvious advantages in terms of time overhead compared with previous schemes.

In terms of storage space overhead, the solution adds an additional 5-byte LTag tag to each data block at the initial stage of data file storage, and generates an LTag tag information list for all data files, LTag tags and tags The storage space occupied by the information list is determined by the number of blocks in the data file. The verification information in the scheme consists of three parts: node Merkle Hash Tree root node value, rack Merkle Hash Tree root node value and file Merkle Hash Tree root node value. Since this scheme uses SHA-1 as the hash function of the data block hash operation, the root node value of each MerkleHash Tree is 160 bits, that is, 20 bytes. The size of the storage space occupied by the verification information of the data file is determined by the number of nodes and racks where the data blocks are distributed. In addition, during the initialization phase of the scheme, CDC will temporarily retain the hash value of all data blocks. During the reconstruction phase of the dynamic operation of the Merkle Hash Tree, CDC will temporarily retain the hash values of all data blocks of the server node where the data block is located. During the generation phase of respondM verification response information, CDC will also temporarily retain the hash values of all data blocks that need to verify nodes, racks or files. All temporarily retained intermediate records will be destroyed along with the reconstruction of the Merkle Hash Tree and the generation of verification information.

The above is only the best implementation mode of the present invention, any simple changes or equivalent replacements of the technical solutions that can be clearly obtained by any person skilled in the art within the technical scope disclosed in the present invention all fall into the scope of the present invention within the scope of protection.

Claims (7)

1. A method for verifiability of data dynamic operation based on hash tree, it is characterized in that, comprising the following steps: A file preprocessing Before the file is pre-processed, the USER will submit a data file storage request to the CDC, and the CDC will authenticate the USER according to its preset access control rules, and the legal user who passes the CDC authentication will obtain the permission to store the file; After USER passes the CDC authentication, CDC starts to receive the data files that USER needs to store and preprocess them: (1) First, the data file will be divided into several data blocks of the same size, F→(f1, f2, f3, f4, f5, f6,...fn), (2) Then, CDC performs a hash operation on each data block and calculates the hash value H(fi) (1≤i≤n) of all data blocks, (3) After the hash operation, the data file can be recorded as: F'→(f1+H(f1), f2+H(f2), f3+H(f3), ..., fn+H(fn)) , CDC will temporarily store the hash values of all data blocks in preparation for the next construction of the verification data structure Merkle Hash Tree of the file, (4) In order to uniquely mark the geographic location of the data block, the scheme adds a 5-byte location tag (LTag) to each data block, and the tag consists of 2-byte sequence tag information and 1-byte rack The tag information is composed of 2-byte node tag information. The sequence tag information records the sequence number of the data block in all data blocks. The rack tag information records the specific rack number of the data block stored in the data center. The node The tag information indicates the specific number of the node server where the data block is stored, and CDC will maintain a list of LTag tags for each data file, recording the LTag tag information of all data blocks in the file; (5) After the tag is added, all data blocks will be stored in the data center by CDC, and the geographical location information stored in the data block will also be recorded in the LTag tag of the data block itself, and the LTag tags of all data blocks will be recorded After completion, CDC will create a LTag tag information list for the data file that contains the geographic location information of all data blocks. (6) Subsequently, construct the key data structure Merkle Hash Tree, 1) First, CDC takes out the rack value Rack(LTag(fi)) of all data blocks in the file from the Ltag label list, divides the data blocks stored in different racks, and stores them in the ListRack[] list of the corresponding rack , 2) Then, the CDC sequentially takes out the node information in the Ltag label of all data blocks from the ListRack[] lists of different racks, and divides the data blocks stored in different nodes of the same rack again, 3) Next, for the data blocks stored in the same rack and the same node, CDC will take out the sequence information in their Ltag tags, arrange them in order, use the hash value of the data block as the leaf node to construct the node Merkle Hash Tree, and calculate Its root node value, if the node has only one data block, the hash value of the data block is the root node value of the node Merkle Hash Tree, recorded as NRoot[i, j], where i represents the rack number, j stands for the node number, 4) After completing the construction of the Merkle Hash Tree of all nodes stored in the file and the calculation of the root node value, CDC will sort the root node values of the Merkle Hash Tree of all nodes stored in the same rack according to the order of the nodes, and use it as a leaf node construction Merkle Hash Tree of each rack, and calculate its root node value, if the rack has only one node to store data files, then the Merkle Hash Tree root node value of this node is the root node value of the rack Merkle Hash Tree, recorded as RRoot[i], where i represents the serial number of the rack, 5) Finally, arrange the root node values of the Merkle HashTree of all racks in order, use their root node values as the Merkle Hash Tree of the leaf node construction file, and calculate the root node value (if only one rack stores data file, then the Merkle Hash Tree root node value of the rack is the root node value of the file Merkle Hash Tree), denoted as FRoot; Verification of B data files (1) First, CDC completes the data file storage work of USER, and submits the relevant verification information of the data files stored by USER to TPA. Before the data files are deleted by USER, as long as any changes occur, CDC will be responsible for generating the latest data files. Verification information, and real-time update with TPA, (2) Then, CDC notifies USER that the storage of data files and the generation of verification information have been completed, and informs USER that it can start entrusting TPA to verify the integrity and consistency of data files, (3) USER can choose to communicate with TPA immediately or at another time to entrust TPA to verify the integrity and consistency of data files, (4) After receiving the audit entrustment request from USER, TPA will conduct regular or irregular audit verification of data files according to USER's needs, and keep verification logs for all audit operations for future inspection by USER. During the verification process, if If data file verification fails, TPA will inform USER by email or SMS, and at the same time request CDC to perform remedial measures such as copy recovery of data files, The verification process of data files in the scheme refers to the periodic and irregular data file integrity and consistency review entrusted by USER to TPA. TPA submits a data file integrity and consistency verification request to CDC and verifies CDC’s reply. The information is reviewed to complete the verification work entrusted by USER. The specific description is as follows: 1) In the initial stage of verification, TPA generates verification information checkM(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j])), and the checkM verification message consists of three parts: one is the user's personal information UInfo, UInfo can help CDC quickly and accurately locate the owner of the data file that needs to be checked; the second is the data file information that needs to be checked FInfo, FInfo clearly points out the data file that needs to be checked; the third is the specific Merkle Hash Tree root node information RInfo, RInfo is composed of three parts: the Merkle Hash Tree root node value FRoot of the data file, the specified rack Merkle Hash Tree root node value RRoot[i], and the specified node Merkle Hash Tree root node value NRoot[i, j]. 2) After the verification message checkM is generated, TPA will transmit checkM to CDC through the communication network, 3) After CDC receives the verification information, it will first decompose checkM to determine the relevant content to be reviewed by TPA. 4) Then, CDC uses the relevant Merkle Hash Tree generation algorithm introduced in Section A above to regenerate and calculate the corresponding Merkle Hash Tree and its root node value, 5) After completing the generation of all verification information, CDC will generate verification reply information respondM(UInfo, FInfo, RInfo'(FRoot', RRoot'[i], NRoot'[i, j])), among them, UInfo and FInfo The content is consistent with the first two parts of the checkM verification information, and RInfo' returns the relevant Merkle Hash Tree root node values that TPA needs to review, including the specified data file Merkle Hash Tree root node value FRoot', the specified rack Merkle Hash Tree The root node value RRoot'[i] and the specified node Merkle Hash Tree root node value NRoot'[i, j] are three parts, 6) Finally, after receiving the respondM verification reply message, TPA will compare it with the relevant Merkle Hash Tree root node value saved by itself. If the result is consistent, the review will fail, and the data is complete and consistent with the previous version. Otherwise, it means If the data is inconsistent with the previous version, TPA will require CDC to perform abnormal handling operations such as copy recovery of data files, and inform USER of the review results; Dynamic manipulation of C data Insert operation of C1 data The insertion operation is the most basic dynamic operation content of the data file. Compared with the modification and deletion operations, it is also the most complicated dynamic operation in the scheme. After inserting the data block fi' after the i-th data block fi in the data file, the operation steps of the scheme can be described as follows: (1) CDC calculates the hash value H(fi') of the new data block fi', and creates tag information LTag(fi') for the data block fi' that needs to be inserted, (2) Generate and run the insertion operation function Insert(fi', H(fi'), LTag(fi)), locate the specific position of the data block insertion through LTag(fi), and perform the insertion operation of the data block, (3) Call the Merkle Hash Tree insertion function MerkleInsert(h(fi), h(fi'), LTag(fi)), which connects h(fi) and h(fi'), and Then the CDC uses the new result generated by the hash operation to replace the hash value of the node at the LTag(fi) position in the original node Merkle Hash Tree. After the connection, the result obtained by hashing the value is no longer The leaf node of the Merkle Hash Tree, but as an intermediate node generated by the two leaf nodes h(fi) and h(fi'), (4) Call the Merkle Hash Tree generation function CreateMerkle() of the node where fi' is located to generate a new node Merkle Hash Tree, and calculate its root node value NRoot[i, j], where i represents the node where the data block is located, and j represents the data the rack where the block resides, (5) Call the Merkle Hash Tree generation function CreateMerkle() of the rack where fi’ is located to generate a new rack Merkle Hash Tree, and calculate its root node value RRoot[i], where i represents the rack where the data block is located, (6) Recall the file Merkle Hash Tree generation function CreateMerkle() to generate a new file Merkle HashTree and calculate its root node value FRoot, (7) CDC reports the update information to TPA, and sends update request information UpdateRequest(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j]), where UInfo, FInfo and RInfo are the same as those defined in Section B ,, (8) TPA updates the verification information of the data file according to the specific content of the update request information for future inspection purposes, C2 data modification operation The modification operation is the most frequent data dynamic operation in cloud computing applications. Modify the i-th data block fi of the data file. After the modification, the i-th data block will become fi'. The specific operation steps of the scheme are described as follows: (1) CDC calculates the hash value H(fi’) of the new data block fi’, and uses the tag information LTag(fi) of fi as the tag information LTag(fi’) of fi’, (2) Generate and run the update operation function Update(fi', H(fi'), LTag(fi)), locate the specific position of the data block that needs to be modified through LTag(fi), and perform the modification operation of the data block, (3) Call the Merkle Hash Tree modification operation function MerkleUpdate(fi', H(fi'), LTag(fi')), use LTag(fi') to locate the specific location of the data block that needs to be modified, use H(fi' ) instead of H(fi), (4) Call the Merkle Hash Tree generation function CreateMerkle() of the node where fi' is located to generate a new node MerkleHashTree, and calculate its root node value NRoot[i, j], where i represents the node where the data block is located, and j represents the data block on the rack, (5) Call the Merkle Hash Tree generation function CreateMerkle() of the rack where fi’ is located to generate a new rack Merkle Hash Tree, and calculate its corresponding root node value RRoot[i], where i represents the rack where the data block is located, (6) Call the file Merkle Hash Tree generation function CreateMerkle() to generate a new file Merkle Hash Tree and calculate its root node value FRoot, (7) CDC reports the update information to TPA, and sends update request information UpdateRequest(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j]), where UInfo, FInfo and RInfo are the same as those defined in Section B , (8) The TPA updates the verification information of the data file according to the specific content of the update request information for future inspection; C3 data deletion operation For example, to delete the data block fi+1 after the i-th data block fi of the data file, the specific operation steps of the scheme are described as follows: (1) Generate and run the delete operation function Delete(fi+1, H(fi+1), LTag(fi+1)), use LTag(fi+1) to locate the specific location of the data block to be deleted, and perform data Block delete operations, (2) Call the Merkle Hash Tree delete operation function MerkleDelete(LTag(fi+1), LTag(fi)) to delete h(fi+1) at the position of LTag(fi+1), and use the value of h(fi) Replace the intermediate node h(h(fi)+h(fi+1) of the Merkle Hash Tree generated by the hash of h(fi) and h(fi+1). Although the deletion operation reduces the Merkle Hash Tree by two leaf nodes, the The basic logical structure of MerkleHash Tree has not changed. (3) Call the Merkle Hash Tree generation function CreateMerkle() of the node where fi is located to generate a new node MerkleHash Tree, and calculate its root node value NRoot[i, j], where i represents the node where the data block is located, and j represents the data block the rack where the (4) Call the Merkle Hash Tree generation function CreateMerkle() of the rack where fi is located to generate a new rack Merkle Hash Tree, and calculate its corresponding root node value RRoot[i], where i represents the rack where the data block is located, (5) Call the file Merkle Hash Tree generation function CreateMerkle() to generate a new file Merkle Hash Tree and calculate its root node value FRoot, (6) CDC reports the update information to TPA, and sends update request information UpdateRequest(UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j]), where UInfo, FInfo and RInfo are the same as defined in section B , (7) The TPA updates the data file of the USER according to the specific content of the update request information for future inspection. 2. the data dynamic operation verifiability method based on hash tree according to claim 1, is characterized in that, (2) CDC among the described A carries out hash operation to each data block and obtains all data blocks hash value, the scheme selects SHA-1 as the hash function to perform hash operations on the data block. 3. the data dynamic operation verifiability method based on hash tree according to claim 1, it is characterized in that, (6) in the described A carries out the structure of key data structure Merkle Hash Tree, and scheme stipulates, data file The hash values of all data blocks are used as the leaf nodes of the Merkle Hash Tree to construct the tree. The scheme is different from the previous scholars who only arrange the file Merkle Hash Tree according to the order information of the data blocks, but will refer to the LTag of all data blocks For label information, the node Merkle Hash Tree, rack Merkle Hash Tree and file Merkle Hash Tree of the data file are sequentially constructed in the order of first node, second rack, and last file, and the root node value is calculated. 4. the data dynamic operation verifiability method based on hash tree according to claim 1, is characterized in that, 1) in (4) in described B, the initial stage of verification, TPA generates verification information checkM (UInfo, FInfo, RInfo(FRoot, RRoot[i], NRoot[i, j])), the scheme allows TPA to arbitrarily select one, two or three items of Merkle Hash Tree root node information for review. 5. The method for verifiability of data dynamic operation based on hash tree according to claim 1, characterized in that, the insertion operation of the data in the C1, the scheme defines the insertion operation as certain specific data in the data file A new data block is inserted after the block. The plan stipulates that the newly inserted data block and the specific data block before it will be stored in the same server node. The data insertion operation in the plan does not change the logical structure of the single server node Merkle Hash Tree . 6. The method for verifiability of data dynamic operation based on hash tree according to claim 1, characterized in that, for the modification operation of the data in the C2, the scheme defines the basic data modification operation as using a new data block To replace the data block that needs to be modified, the plan stipulates that the modified data block is the same as the storage node before the modification, and the data modification operation in the plan does not change the logical structure of the single server node Merkle Hash Tree. 7. The method for verifiability of data dynamic operation based on hash tree according to claim 1, characterized in that, the deletion operation of the data in the C3 is defined by the scheme as the data after the specific data block of the data file The scheme stipulates that if the deleted data block is the only data block of the node where it is located, step (2) in C3 will directly operate on the MerkleHash Tree of the rack, and then skip steps (3) and (4), Execute directly from step (5).

Images