Apparatus, methods, and computer program products providing dynamic provable data possession

摘要

In one exemplary embodiment, a method includes: storing data for a file, organized as blocks, each having a portion of the file; and maintaining a skip list for the data. The skip list is an ordered tree structure having a root node, internal nodes and leaf nodes. Each leaf node corresponds to a block. Each node has a rank value corresponding to size of a subtree rooted at the node. The skip list employs a hashing scheme. The hash value of the root node and internal nodes is computed from a level of the node, the rank value and an interval between the node and another linked node to the right of or below the node. The hash value of the leaf nodes is computed from a level of the node, the rank value and an interval associated with the node.

主权项

1. An apparatus comprising:
at least one memory configured to store data; and at least one processor configured to perform operations on the stored data, where the data comprises at least one file organized as a plurality of blocks with each block comprising at least a portion of the at least one file, where the apparatus is configured to maintain a skip list corresponding to the stored data, where the skip list comprises an ordered tree structure having a root node, at least one internal node and at least one leaf node, where each of the at least one leaf nodes corresponds to a block of the plurality of blocks, where each node of the skip list has an associated rank value corresponding to a size of a subtree of the skip list rooted at the node, where the skip list employs a hashing scheme to assign a hash value to each node of the skip list, where the hash value of the root node and the at least one internal node is computed from a level of the node within the skip list, the rank value of the node within the skip list and an interval between the node and another linked node that is to the right of or below the node, where the hash value of the at least one leaf node is computed from a level of the at least one leaf node within the skip list, the rank value of the least one leaf node and an interval associated with the at least one leaf node.