Patent Description:
<CIT> relates to a method and server for providing notary service for file and verifying file recorded by notary service. A method provides a notary service for the file and verifying the file recorded by using the notary service. The hash value triplesha256digest(coinplug_unique_message) of the certain message data "Coinplug <NUM>-<NUM>-<NUM>" is allocated to a node h0 which is the first leaf node. In case that the notary service request for the file is acquired, a leaf node next to the last leaf node of the currently configured Merkle tree is generated and the specific hash value or its processed value is allocate to the generated leaf node. If allocation is completed up to a node h1, at a previous step, a node h2 which is a next leaf node is generated and the specific hash value or its processed value triplesha256digest(input2) is allocated to the node h2. Further, the method calculates (i) the specific hash value and (ii) a hash value allocated to a sibling node h3 of the node h2, which is a third leaf node where the specific hash value is allocated to, to thereby acquire a resultant value. A hash value of the resultant value is allocated to a parent node h23 of the node h2 and the node h3. As the parent node h23 is not the root node of the Merkle tree, this process is repeated by using the hash value allocated to the node h23 as the specific hash value. In other words, the hash value allocated to the node h23 and a hash value allocated to a node h01 are used to generate a calculated value which is allocated to a node h0123, i.e., a parent node of the node h23 and the node h01. As the node h0123 is the root node of the Merkle tree, a processed value hex(h{node_index}) of the hash value is allocated to the node h0123 in the database.

<CIT> relates to to hash-based electronic signatures for data sets such as dnssec. The method generates leaf nodes from the accessed RRsets. This is accomplished by applying a hash function to each of the RRsets). The method constructs a recursive hash tree from the hashed RRset leaves. That is, the method treats the hashed RRsets as leaf nodes and builds therefrom a recursive hash tree. Pairs of nodes are concatenated and hashed in order to obtain parent nodes from child nodes. The method stores the root of the recursive hash tree in a ZSK DNSKEY resource record. That is, the method stores the recursive hash tree root where a public key of an asymmetric key pair would normally be stored in a ZSK DNSKEY resource record.

<CIT> relates to hash subtrees for grouping components by component type. A system for generating a hash tree with components grouped by component type is provided. Each non-leaf node of the hash tree has a hash of the hashes of its child nodes, and a leaf node has a hash of a component of the hash tree. The system generates, for each component type, a component subtree for that component type based on the leaf nodes that have hashes of the components of that component type. The system then generates a root subtree of the hash tree based on leaf nodes that are the root nodes of the component subtrees. The combination of the root subtree and the component subtrees form the hash tree.

It is therefore the object of the present invention to reduce computational complexity for maintaining data integrity of data in a database.

Methods, systems, apparatuses, and computer-readable storage mediums described herein are directed to compute and storage-efficient techniques for generating a tree-based data structure representative of a data set and the verification thereof. For instance, as each data item of a data set is updated (e.g., via a database transaction), a leaf node is generated that stores a hash value of that data item. For every even leaf node generated, a parent node for that leaf node and its sibling(s) are generated. The parent node stores a hash value based on the hash values of its child leaf nodes. For each level of the tree, the hash value of the last odd node generated therefor is stored in a different data structure (i.e., a state data structure). The foregoing process is performed recursively at each level of the tree, as long as a new node is to be generated at a parent level. The state data structure is used to retrieve hash values for generating parent nodes. After leaf nodes have been generated for all the updated data items of the data set, the resulting root node generated for the tree-based data structure stores a root hash value representative of the entire data set. The root hash value is subsequently utilized to verify whether the data set has been modified. For instance, during a verification process, the data set is retrieved, and a new tree-based data structure is generated in accordance with the foregoing process. The tree-based data structure is generated based on the same order in which the data items were updated. After the root hash value is determined for the new tree-based data structure, the root hash value is compared to the original root hash value determined for the data set. If the root hash values match, it is determined that the data set has not been modified. If the root hash values do not match, it is determined that the data set has been modified, and a remediation is performed to restore the data set.

Further features and advantages, as well as the structure and operation of various example embodiments, are described in detail below with reference to the accompanying drawings. It is noted that the example implementations are not limited to the specific embodiments described herein. Such example embodiments are presented herein for illustrative purposes only. Additional implementations will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein.

The accompanying drawings, which are incorporated herein and form a part of the specification, illustrate example embodiments of the present application and, together with the description, further serve to explain the principles of the example embodiments and to enable a person skilled in the pertinent art to make and use the example embodiments.

The features and advantages of the implementations described herein will become more apparent from the detailed description set forth below when taken in conjunction with the drawings, in which like reference characters identify corresponding elements throughout.

The present specification and accompanying drawings disclose numerous example implementations. The scope of the present application is not limited to the disclosed implementations, but also encompasses combinations of the disclosed implementations, as well as modifications to the disclosed implementations. References in the specification to "one implementation," "an implementation," "an example embodiment," "example implementation," or the like, indicate that the implementation described may include a particular feature, structure, or characteristic, but every implementation may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same implementation. Further, when a particular feature, structure, or characteristic is described in connection with an implementation, it is submitted that it is within the knowledge of persons skilled in the relevant art(s) to implement such feature, structure, or characteristic in connection with other implementations whether or not explicitly described.

In the discussion, unless otherwise stated, adjectives such as "substantially" and "about" modifying a condition or relationship characteristic of a feature or features of an implementation of the disclosure, should be understood to mean that the condition or characteristic is defined to within tolerances that are acceptable for operation of the implementation for an application for which it is intended.

Numerous example embodiments are described as follows. Implementations are described throughout this document, and any type of implementation may be included under any section/subsection. Furthermore, implementations disclosed in any section/subsection may be combined with any other implementations described in the same section/subsection and/or a different section/subsection in any manner.

Embodiments described herein are directed to compute and storage-efficient techniques for generating a tree-based data structure representative of a data set and the verification thereof. For instance, as each data item of a data set is updated (e.g., via a database transaction), a leaf node is generated that stores a hash value of that data item. For every even leaf node generated, a parent node for that leaf node and its sibling(s) are generated. The parent node stores a hash value based on the hash values of its child leaf nodes. For each level of the tree, the hash value of the last odd node generated therefor is stored in a different data structure (i.e., a state data structure). The foregoing process is performed recursively at each level of the tree, as long as a new node is to be generated at a parent level. The state data structure is used to retrieve hash values for generating parent nodes. After leaf nodes have been generated for all the updated data items of the data set, the resulting root node generated for the tree-based data structure stores a root hash value representative of the entire data set. The root hash value is subsequently utilized to verify whether the data set has been modified. For instance, during a verification process, the data set is retrieved, and a new tree-based data structure is generated in accordance with the foregoing process. The tree-based data structure is generated based on the same order in which the data items were updated. After the root hash value is determined for the new tree-based data structure, the root hash value is compared to the original root hash value determined for the data set. If the root hash values match, it is determined that the data set has not been modified. If the root hash values do not match, it is determined that the data set has been modified, and a remediation is performed to restore the data set.

As used herein, a tree-based data structure is defined as a collection of nodes starting at a root node (the uppermost node where the tree is represented as spreading downward), where each node includes a value and references to one or more other nodes ("child" nodes) represented by edges (or links). By convention, tree-based data structures are typically represented as growing downwards but may be oriented in other directions. Internal nodes of a tree-based data structure, or "parent nodes," have child nodes (nodes below them in the tree). Leaf nodes are nodes having no child nodes. A Merkle tree, as known to persons skilled in the relevant art(s), is a tree-based data structure where every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes. A "blockchain" (or "block chain") is a sequence ("chain") of records (e.g., in a list), referred to as "blocks," that are linked using cryptography. Each block in the "chain" contains a cryptographic hash of the previous block, a timestamp, and transaction data.

Conventional techniques generate a tree-based data structure after all data items have been updated and in a bottom-up fashion by computing the parent of every two leaf nodes, storing these nodes, then repeating this process until the root node (the topmost node in a tree-based structure that expands downward) is reached. This requires the storing of all data elements and revisiting them to compute the parent hashes, which is very compute and storage inefficient. The techniques described herein generate a tree-based data structure as the data items are updated and only stores one hash per level of the tree, therefor having logarithmic space complexity. As such, there no longer is the need to revisit any of the data items to obtain their hash values. Instead, the hash stored for a particular level is utilized.

Accordingly, the techniques described are advantageously compute and memory-efficient, as the time complexity of such techniques is O(N) and the space complexity is O(log N), where N is the number of leaf nodes of the tree-based data structure. The small space required to maintain the state of each level of the tree is also advantageously utilized to enable partial transaction rollbacks (e.g., supported by database applications). The logarithmic space needed for recording the state of the tree-based data structure enables a large number of savepoints to be supported with a minimal memory footprint and minimal overhead.

Moreover, the foregoing techniques advantageously improves the integrity of the data maintained by the database, and therefore, ensures that applications accessing the database operate on the correct data. That is, because the application utilizes valid data, the application will return valid results. Moreover, the availability of the database is improved, as hardware and/or software failures that are normally attributed to data inconsistencies is reduced. Still further, the performance of the database is improved, as the re-execution of queries that occurs (e.g., to retrieve a valid replica of the inconsistent data attempted to be accessed) is reduced.

Embodiments herein are applicable to system of record (SOR) applications (e.g., for banking, financial, healthcare, insurance applications, etc.) that maintain transaction histories for accounts, physician visits, prescriptions, medical records, and/or the like, which are expected by users thereof to provide security for their data and be able to prove that no transaction histories, medical records and medical history data, etc., have been improperly changed or otherwise tampered with. Embodiments are also extensible to security information and event management (SIEM) systems including physical access monitoring systems and security logging/monitoring systems, as well as to law enforcement systems that maintain databases of criminal evidence. Additionally, systems for analytics and reporting on shared data in blockchains, and/or the like, are also expected by users thereof to provide security for their data and be able to prove that no data and transaction histories have been tampered with, and the instant embodiments provide for that ability using cryptographic data structures and system implementations described herein. Embodiments provide for existing applications to remain unchanged in their underlying functionality, e.g., the full power and capability of a DB server to query relational transaction histories, as well as for rich ecosystems of reporting and development tools. That is, the solutions exemplarily described herein support existing DB server functionalities and are be easily adopted thereby.

For example, <FIG> shows a block diagram of system for generating a tree-based data structure representative of a data set and for the verification thereof, according to an example embodiment. As shown in <FIG>, system <NUM> includes a transaction manager <NUM>, one or more applications <NUM>, one or more data stores <NUM>, a tree generator <NUM>, and a data verifier <NUM>. Transaction manager <NUM>, application(s) <NUM>, data store(s) <NUM>, tree generator <NUM>, and/or data verifier <NUM> may be implemented via a respective computing device and/or may be communicatively coupled via one or more networks. Alternatively, one or more of transaction manager <NUM>, application(s) <NUM>, data store(s) <NUM>, tree generator <NUM>, and/or data verifier <NUM> may be implemented on the same computing device. Examples of network(s) include, but are not limited to, local area networks (LANs), wide area networks (WANs), enterprise networks, the Internet, etc., and may include one or more of wired and/or wireless portions. Data store <NUM> may be any type of physical memory and/or storage device that is described herein, and/or as would be understood by a person of skill in the relevant art(s) having the benefit of this disclosure.

Transaction manager <NUM> is configured to monitor transactions performed by application(s) <NUM>. Example of application(s) <NUM> include, but are not limited to, a database application configured to perform transactions with respect to data items of a data set (e.g., a relational table, a set of transaction records, etc.), a blockchain engine configured to generate a digital ledger, etc. Examples of transactions include, but are not limited to, queries, joins, unions, insertions, deletions, modifications, etc. Examples of data items, include, but are not limited to, a database object (e.g., row(s) of a table, structured data, etc.), a record of a block chain transaction (e.g., a transaction with respect to a digital ledger utilized in a block chain, etc.), etc. The data set may be maintained by data store(s) <NUM>. A transaction may be configured to add, update and/or modify any number of data items of a particular data set maintained by data store(s) <NUM>. Transaction manager <NUM> may be configured to monitor each addition, update, or deletion of a data item for a given transaction. Transaction manager <NUM> may provide a notification to tree generator <NUM> as each data time is added, updated, and/or deleted. The notification may comprise a sequence number associated with each data item that has been added, updated, and/or deleted. The sequence numbers are representative of the order in which each data item was added, updated, and/or deleted with respect to a particular data set. Alternatively, application(s) <NUM> may provide such notifications directly to tree generator <NUM>.

Tree generator <NUM> is configured to generate a tree-based data structure, such as, but not limited to a Merkle tree. The root of the tree-based structure comprises a hash value that is representative of all the data items added and/or updated to a particular data set. This is very efficient because it reduces a potentially huge volume of data down to a single hash value. The challenge, however, is that the number of data items updated or added can be very large and is not known upfront. Additionally, it would be inefficient to re-process them after the transaction that updates or adds the data items has completed.

Embodiments described herein utilize a streaming technique that generates the root of the tree-based data structure as each data item is updated and/or added to a data set (rather than waiting to generate the tree-based data structure after the entirety of the transaction is completed). For example, tree generator <NUM> may receive a notification from transaction manager <NUM> each time a data item is added and/or updated to a particular data set. Upon receiving a notification from transaction manager <NUM>, tree generator <NUM> may generate a hash value for the data item. For example, as shown in <FIG>, tree generator <NUM> may comprise a hash generator <NUM>. Hash generator <NUM> is configured to, responsive to receiving a notification from transaction manager <NUM>, generate a hash value (or "hash") for each data item added or updated for a given data set. In embodiments, any type of hash function may be used by hash generator <NUM> to generate hash values, such as but without limitation, SHA256 <NUM>-byte hashing. The hash value generated for a particular data item is stored in a newly-generated leaf node of the tree-based data structure, which is located at the lowest level (or L0) of the tree-based data structure.

After generating the leaf node, tree generator <NUM> determines whether the leaf node is an odd node or an even node with respect to the lowest level. In response to determining that the leaf node is an odd node, tree generator <NUM> stores the hash value of the leaf node in a first element of a data structure (referred herein as a state data structure). The data structure may be an array, linked list, etc., that stores, for each level of the tree-based data structure, the hash value of the last odd node generated therefor. In response to determining that the leaf node is an even node, tree generator <NUM> generates a parent (or intermediate) node at the next lowest level (e.g., L1) of the tree-based data structure. The parent node is the parent of the even node and the last node before the even node that was generated at the lowest level (i.e., the even node's sibling). Hash generator <NUM> generates a new hash value that is based on the hash values of the even node and its sibling node. The hash of the sibling node is retrieved from the state data structure. Tree generator <NUM> stores the new hash value in the parent node.

In response to generating the parent node, tree generator <NUM> determines whether the parent node is an odd node or an even node with respect to the L1. In response to determining that the parent node is an odd node, tree generator <NUM> stores the hash value of the parent node in a second element of the data structure. In response to determining that the parent node is an even node, tree generator <NUM> generates a parent (or intermediate) node at the next lowest level (e.g., L2) of the tree-based data structure. The parent node is the parent of the even node and the last node before the even node that was generated at the L1 (i.e., the parent node's sibling).

The foregoing operations are performed for each level in a recursive manner as long as a new node is to be added to a parent level of the tree-based data structure. When all leaf nodes have been appended to the tree-based data structure (at L0) (i.e., after the transaction has completed), a determination is made as to whether the last leaf node added at L0 is an even node or an odd node. If the last node is an even node, tree generator <NUM> generates a parent node at the next lowest level (i.e., L1), and hash generator <NUM> generates a new hash value that is based on the hash values of the even node and its sibling node in a similar manner as described above. If the last node is an odd node (i.e., it has no sibling) the last node is promoted as its parent. This is also performed recursively until the root node of the tree-based data structure is reached.

The time complexity of this streaming technique is O(N) and the space complexity is O(log N), where N is the number of leaf nodes of the tree-based data structure. The small space required to maintain the intermediate state of tree (via the state data structure) is advantageously utilized to enable partial transaction rollbacks (e.g., supported by database applications). For example, when a savepoint is created in the transaction, the current state of the tree-based data structure is copied and maintained as part of the savepoint information. As more operations occur, the tree-based data structure gets updated as described above. However, if the transaction rolls back to this savepoint, the copied state is utilized to restore the tree-based data structure back to the state it had when the savepoint was created. The logarithmic space needed for recording the state of the tree-based data structure enables a large number of savepoints to be supported with a minimal memory footprint and minimal overhead.

The root hash value stored by the root node of tree-based data structure may obtained by data verifier <NUM> and utilized to verify the integrity of the data set represented thereby. For example, at a later point in time, one may desire to verify whether the data set has been modified and/or tampered with. Data verifier <NUM> is configured to obtain the data set from data store(s) <NUM> and provide each data item in the data set to tree generator <NUM>. Data provider <NUM> provides each data item in the order in which the data item was appended to the tree-based data structure, as described above (e.g., using the sequence number). Tree generator <NUM> is configured to generate a tree-based data structure in the same manner as described above and determine the root hash value of the newly-generated tree-based data structure. Data verifier <NUM> compares this root hash value to the root hash value previously-obtained from the tree-based data structure. If the root hash values match, data verifier <NUM> determines that the data set has not been modified and/or tampered with. If the root hash values do not match, data verifier <NUM> determines that the data set has been modified and/or tampered with. In response, data verifier <NUM> may restore the data set to a state before the data set was not modified.

For example, data verifier <NUM> may periodically obtain data set(s) maintained by data store(s) <NUM> and provide such data set(s) to tree generator <NUM>. Tree generator <NUM> generates a tree-based data structure comprising a root node storing the root hash value representative of the data set, as described above. Data verifier <NUM> determines whether the root hash value matches a previously-determined root hash value for the data set. If the root hash values match, a backup (or copy) of the data set is created and maintained (e.g., in data store(s) <NUM> or in another data store (not shown). Upon detecting a root value mismatch, data verifier <NUM> may restore the data set with the backup version of the data set.

<FIG> depict diagrams illustrating a streaming technique utilized to generate a tree-based data structure <NUM> and to update a state data structure <NUM> for maintaining the state of tree-based data structure <NUM> in accordance with an example embodiment. The streaming technique will also be described with reference to a system <NUM>. As shown in <FIG>, system <NUM> comprises data store(s) <NUM> and a tree generator <NUM>, which are examples of data store(s) <NUM> and tree generator <NUM>, as described above with reference to <FIG>. Tree generator <NUM> comprises a hash generator <NUM>, a node generator <NUM>, a node analyzer <NUM>, and a state restorer <NUM>. Hash generator <NUM> is an example of hash generator <NUM>, as described above with reference to <FIG>.

As shown in <FIG>, hash generator <NUM> of tree generator <NUM> may receive a first notification 312A indicating that a first data item of a data set has been added and/or updated. Notification 312A may be received from transaction manager <NUM> or application(s) <NUM>, as described above with reference to <FIG>. Responsive to receiving notification 312A, hash generator <NUM> obtains the first data item (shown as data item 314A) corresponding to notification 312A from data store(s) <NUM>. Hash generator <NUM> provides first data item 314A as an input into a hash function performed thereby, which outputs a hash value 316A based on the first data item. Node generator <NUM> initiates the generation of a tree-based data structure <NUM>, by generating a leaf node at the lowest level of tree-based data structure <NUM> and storing hash value 316A in the leaf node. For example, as shown in <FIG>, node generator <NUM> generates a leaf node 206A at the lowest level (L0) of tree-based data structure <NUM>. Leaf node <NUM> stores hash value 316A (shown as "H1") of first data item 314A (shown as "D1"). Tree-based data structure <NUM> is an example of tree-based data structure <NUM>, as shown in <FIG>.

Referring again to <FIG>, node analyzer <NUM> determines whether leaf node 206A is an odd node or an even node with respect to level L0. In the example shown in <FIG>, leaf node 206A is an odd node. As a result, node analyzer <NUM> stores hash value 316A (stored in leaf node 206A (i.e., H1)) in a first element of state data structure <NUM>. The first element corresponds to L0. For example, as shown in <FIG>, node analyzer <NUM> stores H1 in a first element of data structure <NUM>, which is an example of data structure <NUM>. In the example shown in <FIG>, state data structure <NUM> is an array comprising a plurality of elements, where each element corresponds to a particular level of tree-based data structure <NUM>. However, it is noted that state data structure <NUM> is not limited to an array and may be other types of data structures, such as, but not limited to a linked list, a hash table, etc..

Continuing with the example above, hash generator <NUM> of tree generator <NUM> may receive a second notification 312B indicating that a second data item of the data set has been added and/or updated. Responsive to receiving notification 312B, hash generator <NUM> obtains the second data item (shown as data item 314B) corresponding to notification 312B from data store(s) <NUM>. Hash generator <NUM> provides second data item 314B as an input into the hash function performed thereby, which outputs a hash value 316B based on the second data item. Node generator <NUM> generates a second leaf node at the lowest level of tree-based data structure <NUM> and stores hash value 316B in the leaf node. For example, as shown in <FIG>, node generator <NUM> generates a leaf node 206B at the lowest level (L0) of tree-based data structure <NUM>. Leaf node 206B stores second hash value 316B (shown as "H2") of a first data item 314B (shown as "D2").

Referring again to <FIG>, node analyzer <NUM> determines whether leaf node 206B is an odd node or an even node with respect to level L0. In the example shown in <FIG>, leaf node 206B is an even node. As a result, node analyzer <NUM> sends a command <NUM> to node generator <NUM>, which generates a new node and adds the new node at the next level of tree-based data structure <NUM>. The new node is a parent to the leaf nodes generated for data items 314A and 314B. The new node also comprises a hash value that is generated based on the hash values of data items 314A and 314B. For example, node generator <NUM> may retrieve hash value 316A for data item 306A from the first element of state data structure <NUM> and provide a command <NUM> to hash generator <NUM>. Command <NUM> may comprise the retrieved hash value 316A and hash value 316B. Hash generator <NUM> inputs hash values 316A and 316B to the hash function and outputs a hash value 322A. Node generator <NUM> stores hash value 322A in the new node generated at the next lowest level. For example, as shown in <FIG>, node generator <NUM> generates a node 206C at the next lowest level (i.e. L1), which is a parent to nodes 206A and 206B. Node 206C stores hash value 322A (shown as "H12"), which is a hash value based on the hash values stored by node 206A (as retrieved from the first element of state data structure <NUM>) and node 206B.

Now that a node 206C is generated at L1, node analyzer <NUM> determines whether node 206C is an odd or even node. In the example shown in <FIG>, node 206C is an odd node. As a result, node analyzer <NUM> stores hash value 322A stored in leaf node 206C (i.e., H12) in a second element of data structure <NUM>. The second element corresponds to L1. For example, as shown in <FIG>, node analyzer <NUM> stores H12 in a second element of data structure <NUM>.

Continuing with the example above, hash generator <NUM> of tree generator <NUM> may receive a third notification 312C indicating that a third data item of the data set has been added and/or updated. Responsive to receiving notification 312C, hash generator <NUM> obtains the third data item (shown as data item 314C) corresponding to notification 312C from data store(s) <NUM>. Hash generator <NUM> provides third data item 314C as an input into the hash function performed thereby, which outputs a hash value 316C based on the third data item. Node generator <NUM> generates a third leaf node at the lowest level of tree-based data structure <NUM> and stores hash value 316C in the leaf node. For example, as shown in <FIG>, node generator <NUM> generates a leaf node 206D at the lowest level (L0) of tree-based data structure <NUM>. Leaf node 206D stores third hash value 316C (shown as "H3") of third data item 314C (shown as "D3").

Referring again to <FIG>, node analyzer <NUM> determines whether leaf node 206D is an odd node or an even node with respect to level L0. In the example shown in <FIG>, leaf node 206D is an odd node. As a result, node analyzer <NUM> stores hash value 316C stored in leaf node 206D (i.e., H3) in the first element of data structure <NUM> (i.e., the previous value stored therein is overwritten with hash value 316C). For example, as shown in <FIG>, node analyzer <NUM> stores H3 in the first element of data structure <NUM>.

Continuing with the example above, hash generator <NUM> of tree generator <NUM> may receive a fourth notification 312D indicating that a fourth data item of the data set has been added and/or updated. Responsive to receiving notification 312D, hash generator <NUM> obtains the fourth data item (shown as data item 314D) corresponding to notification 312D from data store(s) <NUM>. Hash generator <NUM> provides fourth data item 314D as an input into the hash function performed thereby, which outputs a hash value 316D based on the fourth data item. Node generator <NUM> generates a fourth leaf node at the lowest level of tree-based data structure <NUM> and stores hash value 316D in the leaf node. For example, as shown in <FIG>, node generator <NUM> generates a leaf node 206E at the lowest level (L0) of tree-based data structure <NUM>. Leaf node 206E stores hash value 316D (shown as "H4") of fourth data item 314D (shown as "D4").

Referring again to <FIG>, node analyzer <NUM> determines whether leaf node 206E is an odd node or an even node with respect to level L0. In the example shown in <FIG>, leaf node 206E is an even node. As a result, node analyzer <NUM> sends command <NUM> to node generator <NUM>, which generates a new node and adds the new node at the next lowest level of tree-based data structure <NUM> (i.e. L1). The new node is a parent to the leaf nodes generated for data items 314C and 314D. The new node also comprises a hash value that is generated based on the hash values of data items 314C and 314D. For example, node generator <NUM> may retrieve hash value 316C for data item 314C from the first element of data structure <NUM> and provide command <NUM> to hash generator <NUM>. Command <NUM> may comprise the retrieved hash value 316C and hash value 316D. Hash generator <NUM> inputs hash values 316C and 316D to the hash function and outputs a hash value 322B. Node generator <NUM> stores hash value 322B in the new node generated at the next lowest level. For example, as shown in <FIG>, node generator <NUM> generates a node 206F at the next lowest level (i.e. L1), which is a parent to nodes 206D and 206E. Node 206F stores hash value 322B (shown as "H34"), which is a hash value based on the hash values stored by node 206D (and retrieved from the first element of data structure <NUM>) and node 206E.

Now that a node 206F is generated at L1, node analyzer <NUM> determines whether node 206F is an odd or even node. In the example shown in <FIG>, node 206F is an even node. As a result, node analyzer <NUM> sends command <NUM> to node generator <NUM>, which generates a new node and adds the new node at the next lowest level of tree-based data structure <NUM> (i.e. L2). The new node is a parent to nodes 206C and 206F. The new node also comprises a hash value that is generated based on the hash values of nodes 206C and 206F (i.e., H12 and H34). For example, node generator <NUM> may retrieve hash value 322A (i.e., H12) for node 206C from the second element of state data structure <NUM> and provide command <NUM> to hash generator <NUM>. Command <NUM> may comprise the retrieved hash value 322A and hash value 322B. Hash generator <NUM> inputs hash values 322A and 322B to the hash function and outputs a hash value 324A. Node generator <NUM> stores hash value 324A in the new node generated at the next lowest level. For example, as shown in <FIG>, node generator <NUM> generates a node <NUM> at the next lowest level (i.e. L2), which is a parent to nodes 206C and 206F. Node <NUM> stores hash value 324A (shown as "H1234"), which is a hash value based on the hash values stored by node 206C (as retrieved from the second element of data structure <NUM>) and node 206F.

Now that node <NUM> is generated at L2, node analyzer <NUM> determines whether node <NUM> is an odd or even node. In the example shown in <FIG>, node <NUM> is an odd node. As a result, node analyzer <NUM> stores hash value 324A stored in leaf node <NUM> (i.e., H1234) and stores hash value 324A in a third element of data structure <NUM>. The third element corresponds to L2. For example, as shown in <FIG>, node analyzer <NUM> stores H1234 in a third element of data structure <NUM>.

Continuing with the example above, hash generator <NUM> of tree generator <NUM> may receive a fifth notification 312E indicating that a fifth data item of the data set has been added and/or updated. Responsive to receiving notification 312E, hash generator <NUM> obtains the fifth data item (shown as data item 314E) corresponding to notification 312E from data store(s) <NUM>. Hash generator <NUM> provides fifth data item 314E as an input into the hash function performed thereby, which outputs a hash value 316E based on the fifth data item. Node generator <NUM> generates a fifth leaf node at the lowest level of tree-based data structure <NUM> and stores hash value 316E in the leaf node. For example, as shown in <FIG>, node generator <NUM> generates a leaf node <NUM> at the lowest level (L0) of tree-based data structure <NUM>. Leaf node <NUM> stores hash value 316E (shown as "H5") of a fifth data item 314E (shown as "D5").

Referring again to <FIG>, node analyzer <NUM> determines whether leaf node <NUM> is an odd node or an even node with respect to level L0. In the example shown in <FIG>, leaf node <NUM> is an odd node. As a result, node analyzer <NUM> stores hash value 316E stored in leaf node <NUM> (i.e., H5) in the first element of data structure <NUM> (i.e., the previous value stored therein is overwritten with hash value 316E). For example, as shown in <FIG>, node analyzer <NUM> stores H5 in the first element of data structure <NUM>.

In the example above, data item 314E is the final data item to be updated and/or added. After a leaf node for the final data item is generated, tree generator <NUM> completes tree-based data structure <NUM> until all leaf nodes are associated with the same root node. As shown in <FIG>, leaf node <NUM> does not have a sibling. Therefore, leaf node <NUM> itself is promoted as its parent. For instance, node generator <NUM> may generate one or more null (or dummy) nodes to complete tree-based data structure <NUM>.

For example, as shown in <FIG>, node generator <NUM> generates null node 208A at level L0, such that node <NUM> now has a sibling. Now that node 208A is generated at L0, node analyzer <NUM> determines whether node 208A is an odd or even node. In the example shown in <FIG>, node 208A is an even node. As a result, node analyzer <NUM> sends command <NUM> to node generator <NUM>, which generates a new node and adds the new node at the next lowest level of tree-based data structure <NUM> (i.e. L1). The new node is a parent to the leaf node generated for data item <NUM> and null node 208A. The new node also comprises the hash value of node <NUM> (i.e., H5) (thereby promoting node <NUM> to a parent node). For example, node generator <NUM> may retrieve hash value 316E for data item 306E from the first element of data structure <NUM> and stores hash value 316E in the new node generated at the next lowest level. For example, as shown in <FIG>, node generator <NUM> generates a node 208B at the next lowest level (i.e. L <NUM>), which is a parent to nodes <NUM> and 208A. Node 208B stores hash value 316E (shown as "H5"), which is the same hash value stored by node <NUM>.

Now that node 208B is generated at L1, node analyzer <NUM> determines whether node 208B is an odd or even node. In the example shown in <FIG>, node 208B is an odd node. As a result, node analyzer <NUM> stores hash value 316E stored in node 208B (i.e., H5) in the second element of data structure <NUM>. For example, as shown in <FIG>, node analyzer <NUM> stores H5 in the second element of data structure <NUM>.

Node generator <NUM> continues to perform the aforementioned operations until the leaf nodes are associated with a common root node. For example, as shown in <FIG>, node generator <NUM> has generated null node 208E, which is a sibling to node 208B. Any node under node 208B is also a null node. As shown in <FIG>, nodes 208C and 208D are logically added to tree structure <NUM>. After generating node 208D, node generator <NUM> determines that node 208D is an even node, and therefore, generates null node 208E at level L1. Because null node 208E is an even node at level L1, node generator <NUM> sends command <NUM> to node generator <NUM>, which generates a new node and adds the new node at the next lowest level of tree-based data structure <NUM> (i.e. L2). The new node is a parent to the nodes 208B and 208E. The new node also comprises the hash value of node 208B (i.e., H5). For example, node generator <NUM> may retrieve hash value 316E for data item 306E from the second element of data structure <NUM> and stores hash value 316E in the new node generated at the next lowest level. For example, as shown in <FIG>, node generator <NUM> generates a node <NUM> at the next lowest level (i.e. L2), which is a parent to nodes 208B and 208E. Node <NUM> stores hash value 316E (shown as "H5"), which is the same hash value stored by nodes <NUM> and 208B.

Now that node <NUM> is generated at L2, node analyzer <NUM> determines whether node <NUM> is an odd or even node. In the example shown in <FIG>, node <NUM> is an even node. As a result, node analyzer <NUM> sends command <NUM> to node generator <NUM>, which generates a new node and adds the new node at the next lowest level of tree-based data structure <NUM> (i.e. L3). The new node is a parent to nodes <NUM> and <NUM>. The new node also comprises a hash value that is generated based on the hash values stored in nodes <NUM> and <NUM>. For example, node generator <NUM> may retrieve hash value 324A from the third element of data structure <NUM> and provide a command <NUM> to hash generator <NUM>. Command <NUM> may comprise the retrieved hash value 324A and hash value 316E. Hash generator <NUM> inputs hash values 324A and 316E to the hash function and outputs a hash value 326A. Node generator <NUM> stores hash value 326A in the new node generated at the next lowest level. For example, as shown in <FIG>, node generator <NUM> generates node 206I at the next lowest level (i.e. "L3"), which is a parent to nodes <NUM> and <NUM>. Node 206I stores hash value 326A (shown as "H12345"), which is a hash value based on the hash values stored by node <NUM> (as retrieved from the third element of data structure <NUM>) and node <NUM>.

As shown in <FIG>, node 206I is a common root node for all leaf nodes 206A, 206B, 206D, 206E, and <NUM>. Accordingly, node 206I is determined to be the root node of tree-based data structure <NUM>. The hash value stored by node 206I (hash value 326A) is the root hash value that is representative of all the data items (i.e., data items 314A-314E) added and/or updated with respect to a particular data set.

It is noted that while the example described above is with respect to five data items, any number of data items may be added and/or updated with respect to a particular data set, and that tree-based data structure <NUM> and <NUM> may comprise any number of nodes representative of such data items.

In an embodiment in which data items are rows of a table and operations that update or add rows of the table are database operations, one or more of the operations may comprise a savepoint. The savepoint indicates a point within a transaction (configured to update or add multiple rows) that can be rolled back to without affecting any work done in the transaction before the save point was created. A savepoint may be declared in a transaction via a SAVEPOINT statement. All changes made after a savepoint has been declared can be undone via a ROLLBACK TO SAVEPOINT command.

In embodiments, tree generator <NUM> is configured to determine whether a transaction comprises a savepoint and/or a rollback command. In response to determining that a transaction comprises a savepoint, tree generator <NUM> generates a copy of state data structure <NUM>, thereby preserving the logarithmic state of tree-based data structure <NUM> at the time of the savepoint. In the event that a rollback command is detected, tree generator <NUM> may bring the tree-based data structure <NUM> back to the state it had when the savepoint was created by using the values stored in the copied state data structure <NUM>.

For instance, as shown in <FIG>, each of notifications 312A-312E may also indicate whether the transaction corresponding thereto comprises a savepoint or rollback command. Each of notifications 312A-312E are provided to state restorer <NUM>, which determines whether notifications 312A-312E comprise a savepoint or rollback command. In response to determining that a notification of notifications 312A-312E comprises a savepoint, state restorer <NUM> saves the values stored in state data structure <NUM>. For instance, state restorer <NUM> may generate a copy of state data structure (shown as copied state data structure <NUM>). In an example, suppose that notification 312D specifies that its corresponding transaction comprises a savepoint. In this example, with reference to <FIG>, the values stored in data structure <NUM> (after leaf node 206E is added for data item 314B and node <NUM> is generated in tree-based data structure <NUM> (e.g., H3, H12, and H1234)) are saved and/or stored in copied state data structure <NUM>.

In the event that state restorer <NUM> determines that a subsequent transaction comprises a rollback command, state restorer <NUM> rolls back tree-based data structure <NUM> in accordance with the values stored in copied state data structure <NUM>. For example, state restorer <NUM> may cause the values stored in copied state data structure <NUM> to be copied to state data structure <NUM>, which effectively causes tree-based data structure <NUM> to be restored to the state shown in <FIG>.

It is noted that while tree generator <NUM> is described as generating a binary tree, such as a Merkle tree, the embodiments described herein are not so limited. For instance, tree generator <NUM> may be configured to generate other tree structures in which a parent node may have more than two child nodes. In such embodiments, the hash value stored by the parent may be based on the hash values of all of its child nodes.

Accordingly, a tree-based data structure representative of a data set may be generated in many ways. For example, <FIG> shows a flowchart <NUM> of a method for generating a tree-based data structure representative of a data set in accordance with an example embodiment. In an embodiment, flowchart <NUM> may be implemented by system <NUM> shown in <FIG>, although the method is not limited to that implementation. Accordingly, flowchart <NUM> will be described with reference to <FIG>. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the discussion regarding flowchart <NUM> and system <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. In step <NUM>, for each data item of the data set, a first hash value for the data item is generated. For example, with reference to <FIG>, hash generator <NUM> generates hash values 316A-316E for each of data items 314A-314E, respectively. Hash generator <NUM> generates hash values 316A-316E responsive to receiving respective notifications 312A-312E.

In step <NUM>, for each data item of the data set, a leaf node at the first level of a tree-based data structure is generated. The leaf node stores the first hash value of the data item. For example, with reference to <FIG>, node generator <NUM> generates a leaf node at the first level of tree-based data structure <NUM> for each of data items 314A-314E. Each leaf node stores a respective hash value of hash values 316A-316E. For instance, as shown in <FIG>, leaf nodes 206A and 206B are generated at level L0 of tree-based data structure <NUM>. Leaf node 206A stores first hash value 316A (shown as "H1"), and leaf node 206B stores first hash value 316B (shown as "H2").

Responsive to determining that the leaf node is an even node with respect to the first level, at least one of steps step <NUM> and <NUM> are performed. In step <NUM>, at a second level of the tree-based data structure, an intermediary node of the tree-based data structure is generated, the intermediary node storing a second hash value that is based on the first hash value of the leaf node and another first hash value of another leaf node of the first level that is a sibling of the leaf node. For example, with reference to <FIG>, node generator <NUM> generates an intermediary node of tree-based data structure <NUM> at an intermediary level thereof. The intermediary node stores a second hash value that is based on the first hash value of the leaf node and another first hash value of another leaf node of the first level. For example, with reference to <FIG> and <FIG>, node generator <NUM> generates intermediary node 206C at L1. Intermediary node 206C stores a second hash value (e.g., second hash value 322A), which is based on first hash value 316A (shown as "H1") stored in leaf node 206A and first hash value 316B (shown as "H2") stored in leaf node 206B.

In step <NUM>, at a root level of the tree-based data structure, a root node of the tree-based data structure is generated, the root node storing a root hash value that is based on the second hash value of the intermediary node and another second hash value of another intermediary node of the second level that is a sibling of the intermediary node. For example, with reference to <FIG>, node generator <NUM> generates a root node of tree-based data structure <NUM> at a root level thereof. The root node stores a root hash value that is based on the second hash value of the intermediary node and another second hash value of another intermediary node of the first second. For example, with reference to <FIG> and <FIG>, node generator <NUM> generates root node <NUM> at L2. Root node <NUM> stores a root hash value (e.g., third hash value 324A), which is based on second hash value 322A (shown as "H12") stored in intermediary node 206C and second hash value 322B (shown as "H34") stored in intermediary node 206F.

In step <NUM>, for each level of the tree-based data structure, a respective hash value generated for the last odd node generated for the level is stored in a data structure. For example, with reference to <FIG>, for each level of tree-based data structure <NUM>, state data structure <NUM> stores a respective hash value generated for the last odd node generated for the level. For example, as shown in <FIG>, state data structure <NUM> stores the hash value of leaf node <NUM> (which was the last odd node generated for L0) in a first element thereof, state data structure <NUM> stores the hash value of intermediary node 208B (which was the last odd node generated for L1) in a second element thereof, state data structure <NUM> stores the hash value of intermediary node <NUM> (which was the last odd node generated for L2) in a third element thereof, and state data structure <NUM> stores the hash value of root node 206I (which was the last odd node generated for L3) in a fourth element thereof.

In accordance with one or more embodiments, the tree-based data structure is a Merkle tree.

In accordance with one or more embodiments, the data set is a ledger of transactions utilized in a block chain.

In accordance with one or more embodiments, a determination is made that that a transaction with respect to a particular data item of the data set comprises a savepoint, and in response to such a determination, the hash values stored in the data structure are copied. For example, with reference to <FIG>, state restorer <NUM> may determine that a particular transaction corresponding to one of notifications 312A-312E comprises a savepoint. In response, state restorer <NUM> copies the values in state data structure <NUM> into another data structure (e.g., copied state data structure <NUM>).

In accordance with one or more embodiments, a request to roll back to the savepoint is detected, and in response to such detection, the tree-based data structure is restored in accordance with the copied hash values. For example, with reference to <FIG>, state restorer <NUM> may determine that a subsequent transaction comprises a rollback command. In response, state restorer <NUM> restores tree-based data structure <NUM> in accordance with the values stored in copied state data structure <NUM>. For instance, the values stored in copied state data structure <NUM> may be copied to state data structure <NUM>.

<FIG> shows a flowchart <NUM> of a method for verifying a data set utilizing a tree-based data structure in accordance with an example embodiment. In an embodiment, flowchart <NUM> may be implemented by system <NUM> shown in <FIG>, although the method is not limited to that implementation. Accordingly, flowchart <NUM> will be described with continued reference to <FIG>. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the discussion regarding flowchart <NUM> and system <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. In step <NUM>, the root hash value is compared to a previously-determined hash value for the data set. If a determination is made that the root hash value is equal to the previously-determined hash value, flow continues to step <NUM>. Otherwise, flow continues to step <NUM>. For example, with reference to <FIG>, data verifier <NUM> may obtain the root hash value from the tree-based data structure generated by tree generator <NUM> (e.g., tree-based data structure <NUM>) and compare the root hash value to a previously-determined hash value for the data set.

In step <NUM>, a determination is made that the data set has not been modified. For example, with reference to <FIG>, data verifier <NUM> determines that the data set maintained by data store(s) <NUM> has not been modified.

In step <NUM>, a determination is made that the data set has been modified. For example, with reference to <FIG>, data verifier <NUM> determines that the data set has been modified.

In step <NUM>, the data set is restored to a state before the data set was not modified. For example, with reference to <FIG>, data verifier <NUM> may restore the data set to a state before it was modified. For example, data verifier <NUM> may retrieve a backup of the data set (e.g., maintained by data store(s) <NUM>).

<FIG> shows a flowchart <NUM> of a method for completing a tree-based data structure in accordance with an example embodiment. In an embodiment, flowchart <NUM> may be implemented by system <NUM> shown in <FIG>, although the method is not limited to that implementation. Accordingly, flowchart <NUM> will be described with continued reference to <FIG>. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the discussion regarding flowchart <NUM> and system <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. In step <NUM>, a last node for a last data item of the data set is generated. The leaf node for the last data item stores a respective first hash value. For example, with reference to <FIG>, node generator <NUM> generates a last node for a last data item of the data set. For instance, as shown in <FIG>, leaf node <NUM> represents the node generated for last data item 314E.

In step <NUM>, a determination is made that the leaf node for the last data item is an odd node with respect to the first level. For example, with reference to <FIG>, node analyzer <NUM> determines that the leaf node (e.g., leaf node <NUM>) is an odd node with respect to L0.

In step <NUM>, the tree-based data structure is completed with at least one of one or more null nodes, one or more intermediary nodes, or a new root node, the one or more intermediary nodes storing a hash value that is based at least on the first hash value of the leaf node for the last data item. For example, with reference to <FIG>, node generator <NUM> completes the tree-based data structure with at least one of one or more null nodes, one or more intermediary nodes, or a new root node. For example, as shown in <FIG> and <FIG>, node generator <NUM> generates null nodes 208A, 208C, 208D, and 208E, generates new intermediary nodes 208B and <NUM> (which store the hash value generated for the last leaf node <NUM>), and generates new root node 206I. Root node 206J stores a hash value that is representative of the nodes 206A, 206B, 206D, 206E, and <NUM>.

The systems and methods described above in reference to <FIG>, may be implemented in hardware, or hardware combined with one or both of software and/or firmware. For example, system <NUM> of <FIG> may be used to implement any of transaction manager <NUM>, application(s) <NUM>, data store(s) <NUM>, tree generator <NUM>, hash generator <NUM>, data verifier <NUM>, tree-based data structure <NUM>, data structure <NUM>, tree generator <NUM>, data store(s) <NUM>, state restorer <NUM>, hash generator <NUM>, node generator <NUM>, node analyzer <NUM>, tree-based data structure <NUM>, state data structure <NUM>, copied state data structure <NUM>, and/or any of the components respectively described therein, and/or each of the components described therein, and flowcharts <NUM>, <NUM>, and/or <NUM> may be each implemented as computer program code/instructions configured to be executed in one or more processors and stored in a computer readable storage medium. Alternatively, any of transaction manager <NUM>, application(s) <NUM>, data store(s) <NUM>, tree generator <NUM>, hash generator <NUM>, data verifier <NUM>, tree-based data structure <NUM>, data structure <NUM>, tree generator <NUM>, data store(s) <NUM>, state restorer <NUM>, hash generator <NUM>, node generator <NUM>, node analyzer <NUM>, tree-based data structure <NUM>, state data structure <NUM>, copied state data structure <NUM>, and/or any of the components respectively described therein, and/or each of the components described therein, and flowcharts <NUM>, <NUM>, and/or <NUM> may be implemented as hardware logic/electrical circuitry. In an embodiment, any of transaction manager <NUM>, application(s) <NUM>, data store(s) <NUM>, tree generator <NUM>, hash generator <NUM>, data verifier <NUM>, tree-based data structure <NUM>, data structure <NUM>, tree generator <NUM>, data store(s) <NUM>, state restorer <NUM>, hash generator <NUM>, node generator <NUM>, node analyzer <NUM>, tree-based data structure <NUM>, state data structure <NUM>, copied state data structure <NUM>, and/or any of the components respectively described therein, and/or each of the components described therein, and flowcharts <NUM>, <NUM>, and/or <NUM> may be implemented in one or more SoCs (system on chip). An SoC may include an integrated circuit chip that includes one or more of a processor (e.g., a central processing unit (CPU), microcontroller, microprocessor, digital signal processor (DSP), etc.), memory, one or more communication interfaces, and/or further circuits, and may optionally execute received program code and/or include embedded firmware to perform functions.

<FIG> depicts an exemplary implementation of a computing device <NUM> in which embodiments may be implemented, including any of transaction manager <NUM>, application(s) <NUM>, data store(s) <NUM>, tree generator <NUM>, hash generator <NUM>, data verifier <NUM>, tree-based data structure <NUM>, data structure <NUM>, tree generator <NUM>, data store(s) <NUM>, state restorer <NUM>, hash generator <NUM>, node generator <NUM>, node analyzer <NUM>, tree-based data structure <NUM>, state data structure <NUM>, copied state data structure <NUM>, and/or any of the components respectively described therein, and/or each of the components described therein, and flowcharts <NUM>, <NUM>, and/or <NUM>. The description of computing device <NUM> provided herein is provided for purposes of illustration, and is not intended to be limiting. Embodiments may be implemented in further types of computer systems, as would be known to persons skilled in the relevant art(s).

A number of program modules may be stored on the hard disk, magnetic disk, optical disk, ROM, or RAM. These programs include operating system <NUM>, one or more application programs <NUM>, other programs <NUM>, and program data <NUM>. Application programs <NUM> or other programs <NUM> may include, for example, computer program logic (e.g., computer program code or instructions) for implementing the systems described above, including the embodiments described above with reference to <FIG>.

Display screen <NUM> may display information, as well as being a user interface for receiving user commands and/or other information (e.g., by touch, finger gestures, a virtual keyboard, by providing a tap input (where a user lightly presses and quickly releases display screen <NUM>), by providing a "touch-and-hold" input (where a user touches and holds his finger (or touch instrument) on display screen <NUM> for a predetermined period of time), by providing touch input that exceeds a predetermined pressure threshold, etc.).

As used herein, the terms "computer program medium," "computer-readable medium," and "computer-readable storage medium" are used to generally refer to physical hardware media such as the hard disk associated with hard disk drive <NUM>, removable magnetic disk <NUM>, removable optical disk <NUM>, other physical hardware media such as RAMs, ROMs, flash memory cards, digital video disks, zip disks, MEMs, nanotechnology-based storage devices, and further types of physical/tangible hardware storage media (including system memory <NUM> of <FIG>). Communication media typically embodies computer-readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave. Embodiments are also directed to such communication media.

A method is described herein. The method includes: for each data item of a data set: generating a first hash value for the data item; generating a leaf node at a first level of a tree-based data structure, the leaf node storing the first hash value of the data item; responsive to determining that the leaf node is an even leaf node with respect to the first level, performing at least one of: generating, at a second level of the tree-based data structure, an intermediary node of the tree-based data structure, the intermediary node storing a second hash value that is based on the first hash value of the leaf node and another first hash value of another leaf node of the first level that is a sibling of the leaf node; or generating, at a root level of the tree-based data structure, a root node of the tree-based data structure, the root node storing a root hash value that is based on the second hash value of the intermediary node and another second hash value of another intermediary node of the second level that is a sibling of the intermediary node; and for each level of the tree-based data structure: storing, in a data structure, a respective hash value generated for the last odd node generated for the level.

In one implementation of the foregoing method, the method further comprises: comparing the root hash value to a previously-determined hash value for the data set; in response to determining that the root hash value is equal to the previously-determined hash value, determining that the data set has not been modified; and in response to determining that the root hash value is not equal to the previously-determined hash value: determining that the data set has been modified; and restoring the data set to a state before the data set was not modified.

In one implementation of the foregoing method, the method further comprises: determining that a particular transaction with respect to a data item of the data set comprises a savepoint; and in response to said determining, copying the hash values stored in the data structure.

In one implementation of the foregoing method, the method further comprises: detecting a request to roll back to the savepoint; and in response to said detecting, restoring the tree-based data structure in accordance with the copied hash values.

In one implementation of the foregoing method, the method further comprises: generating a leaf node for a last data item of the data set, the leaf node for the last data item storing a respective first hash value; determining that the leaf node for the last data item is an odd node with respect to the first level; and completing the tree-based data structure with at least one of one or more null nodes, one or more intermediary nodes, or a new root node, the one or more intermediary nodes storing a hash value that is based at least on the first hash value of the leaf node for the last data item.

In one implementation of the foregoing method, the tree-based data structure is a Merkle tree.

In one implementation of the foregoing method, the data set comprises at least one of: a ledger of transactions utilized in a block chain; or a plurality of rows in a relational table.

In one implementation of the foregoing method, the other first hash value is retrieved from the data structure to generate the second hash value, and the other second hash value is retrieved from the data structure to generate the root hash value.

A system is also disclosed. The system includes: at least one processor circuit; and at least one memory that stores program code configured to be executed by the at least one processor circuit, the program code comprising: a tree generator configured to: for each data item of a data set: generate a first hash value for the data item; generate a leaf node at a first level of a tree-based data structure, the leaf node storing the first hash value of the data item; responsive to determining that the leaf node is an even leaf node with respect to the first level, performing at least one of: generate, at a second level of the tree-based data structure, an intermediary node of the tree-based data structure, the intermediary node storing a second hash value that is based on the first hash value of the leaf node and another first hash value of another leaf node of the first level that is a sibling of the leaf node; or generate, at a root level of the tree-based data structure, a root node of the tree-based data structure, the root node storing a root hash value that is based on the second hash value of the intermediary node and another second hash value of another intermediary node of the second level that is a sibling of the intermediary node; and for each level of the tree-based data structure: store, in a data structure, a respective hash value generated for the last odd node generated for the level.

In one implementation of the foregoing system, the program code further comprises a data verifier configured to: compare the root hash value to a previously-determined hash value for the data set; in response to determining that the root hash value is equal to the previously-determined hash value, determine that the data set has not been modified; and in response to determining that the root hash value is not equal to the previously-determined hash value: determine that the data set has been modified; and restore the data set to a state before the data set was not modified.

In one implementation of the foregoing system, the program code further comprises a state restorer configured to: determine that a particular transaction with respect to a data item of the data set comprises a savepoint; and in response to said determining, copy the hash values stored in the data structure.

In one implementation of the foregoing system, the state restorer is further configured to: detect a request to roll back to the savepoint; and in response to said detecting, restore the tree-based data structure in accordance with the copied hash values.

In one implementation of the foregoing system, the tree generator is further configured to: generate a leaf node for a last data item of the data set, the leaf node for the last data item storing a respective first hash value; determine that the leaf node for the last data item is an odd node with respect to the first level; and complete the tree-based data structure with at least one of one or more null nodes, one or more intermediary nodes, or a new root node, the one or more intermediary nodes storing a hash value that is based at least on the first hash value of the leaf node for the last data item.

In one implementation of the foregoing system, the tree-based data structure is a Merkle tree.

In one implementation of the foregoing system, the data set comprises at least one of: a ledger of transactions utilized in a block chain; or a plurality of rows in a relational table.

A computer-readable storage medium having program instructions recorded thereon that, when executed by at least one processor, perform a method. The method includes: for each data item of the data set: generating a first hash value for a data item; generating a leaf node at a first level of a tree-based data structure, the leaf node storing the first hash value of the data item; responsive to determining that the leaf node is an even leaf node with respect to the first level, performing at least one of: generating, at a second level of the tree-based data structure, an intermediary node of the tree-based data structure, the intermediary node storing a second hash value that is based on the first hash value of the leaf node and another first hash value of another leaf node of the first level that is a sibling of the leaf node; or generating, at a root level of the tree-based data structure, a root node of the tree-based data structure, the root node storing a root hash value that is based on the second hash value of the intermediary node and another second hash value of another intermediary node of the second level that is a sibling of the intermediary node; and for each level of the tree-based data structure: storing, in a data structure, a respective hash value generated for the last odd node generated for the level.

In one implementation of the foregoing computer-readable storage medium, the method further comprises: comparing the root hash value to a previously-determined hash value for the data set; in response to determining that the root hash value is equal to the previously-determined hash value, determining that the data set has not been modified; and in response to determining that the root hash value is not equal to the previously-determined hash value: determining that the data set has been modified; and restoring the data set to a state before the data set was not modified.

In one implementation of the foregoing computer-readable storage medium, the method further comprises: determining that a particular transaction with respect to a data item of the data set comprises a savepoint; and in response to said determining, copying the hash values stored in the data structure.

In one implementation of the foregoing computer-readable storage medium, the method further comprises: detecting a request to roll back to the savepoint; and in response to said detecting, restoring the tree-based data structure in accordance with the copied hash values.

In one implementation of the foregoing computer-readable storage medium, the method further comprises: generating a leaf node for a last data item of the data set, the leaf node for the last data item storing a respective first hash value; determining that the leaf node for the last data item is an odd node with respect to the first level; and completing the tree-based data structure with at least one of one or more null nodes, one or more intermediary nodes, or a new root node, the one or more intermediary nodes storing a hash value that is based at least on the first hash value of the leaf node for the last data item.

Claim 1:
A computer implemented method for verifying a data set, the method comprising:
for each data item of the data set:
generating (<NUM>) a first hash value for the data item;
generating (<NUM>) a leaf node at a first level of a tree-based data structure (<NUM>), the leaf node storing the first hash value of the data item, the first level being the lowest level of the tree-based data structure;
responsive to determining that the leaf node is an even node with respect to the first level, performing recursively at each level of the tree, and as long as a new node is generated at a parent level:
generating (<NUM>, <NUM>), at a next lowest level of the tree-based data structure, a parent node of the tree-based data structure, the parent node storing a second hash value that is based on the first hash value of the even node and another first hash value of a last node before the even node that is a sibling of the even node, wherein the another first hash value of the sibling node is retrieved from a state data structure (<NUM>); and
for each level of the tree-based data structure:
storing (<NUM>), in the state data structure, a respective hash value generated for the last odd node generated for the level.