Threaded leaf nodes in database journal
AssigneeAmazon Technologies, Inc.
InventorsTate Andrew Certain, Benjamin Nelson Glowney, Allan Henry Vermeulen
Life of this patent
Estimating the term…
Abstract
A database management system stores an entry in a journal. The journal, upon storage of the entry, comprises an ordered plurality of leaf nodes and a hierarchy of interior nodes based upon the leaf nodes. A node in the ordered plurality of nodes comprises a hash value computed based on the hash of a corresponding entry and a hash of a prior leaf node. A cryptographic proof of the entry comprises successive application of a hash operator to one or more hashes of the leaf nodes.
Claims20
A system, comprising:
- at least one processor;
- and
- a memory comprising instructions that, in response to execution by the at least one processor, cause the system to at least:
- store an entry in a journal, wherein the journal, upon storage of the entry, comprises a hierarchy of interior nodes and an ordered plurality of leaf nodes, wherein a leaf node of the ordered plurality of leaf nodes comprises a hash value based at least in part on the entry and a hash value of a prior leaf node of the ordered plurality of leaf nodes;
- and
- provide a list of hash values from the ordered plurality of leaf nodes, wherein the list of hash values is sufficient for a cryptographic proof that the entry was stored in the journal.
A computer-implemented method, comprising:
- storing an entry in a journal comprising a hierarchy of interior nodes and a plurality of leaf nodes, wherein a second leaf node of the plurality of leaf nodes comprises a hash value based at least in part on the entry and a hash value of a first leaf node of the plurality of leaf nodes;
- and
- providing a list of hash values from the plurality of leaf nodes, wherein the list of hash values is sufficient for proving that the entry was stored in the journal.
A non-transitory computer-readable storage medium storing thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:
- store an entry in a journal, wherein the journal, upon storage of the entry, comprises a hierarchy of interior nodes and a plurality of leaf nodes, wherein a first leaf node of the plurality of leaf nodes comprises a hash value based at least in part on the entry and a hash value of a second leaf node of the plurality of leaf nodes;
- and
- provide a list of hash values from the plurality of leaf nodes, wherein the list of hash values is usable for a cryptographic proof that the entry was stored in the journal.
Dependencies are inferred from the claim text.