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 (301); and maintaining a skip list for the data (302). 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.