Patent ID: 8726034

Claim:
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 operations comprise at least one of generating and maintaining an accumulation tree corresponding to the stored data, where the accumulation tree comprises an ordered tree structure having a root node, at least one leaf node and at least one internal node disposed between the root node and the at least one leaf node, where each of the at least one leaf nodes corresponds to at least a portion of the stored data, where a depth of the accumulation tree remains constant, where a bound on a degree of each of the at least one internal nodes is a function of a number of leaf nodes of a subtree rooted at the internal node, and wherein the operations further comprise receiving a query on the stored data and to return, in response to the received query, an answer and a corresponding verification proof, where the verification proof is an ordered sequence of tuples, each tuple comprised of a prime representative and a branch witness, where the branch witnesses authenticate every node of a path from a queried node to the root node of the accumulation tree, where each node of the accumulation tree has a corresponding accumulation value, where the accumulation values of the root node and the at least one internal node are determined by hierarchically employing an accumulator over the accumulation values of the nodes lying one level below the node for which the accumulation value is determined, where the accumulation value of the root node comprises a digest for the accumulation tree.