International Business Machines Corporation
Hashed balanced tree data structure

Abstract:

Aspects create a tree data structure that indexes a collection of documents present in a data repository at a point in time. The tree data structure includes a plurality of nodes. For each such node, a respective root hash value of that node is determined. The root hash value of a leaf node is determined from hash value(s) for element(s) of that node that are keyed to documents in the collection. The root hash value of a parent node is determined from a root hash value for each of its child nodes. For a given document that is purported to be a target document present in the data repository at the point in time, processing is performed that uses the tree data structure in facilitating verification that the given document is the target document. This includes providing a cryptographic proof to demonstrate whether the given document is the target document.