Digest proofs in a journaled database
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. Upon storage of the entry, the journal comprises a plurality of threaded leaf nodes and a hierarchy of interior nodes comprising hash values computed from the threaded leaf nodes. A first set of hash values is provided to prove that the entry is stored in a first version of the journal. A second set is provided to prove that the entries stored in the first version of the journal are unmodified and stored in a second version of the journal.
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 one or more entries in a first version of a journal, wherein the first version of the journal, upon storage of the one or more entries, comprises:
- 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 a hash value of a prior node in the ordered plurality of leaf nodes;
- a hierarchy of interior nodes, wherein an interior node comprises a hash value based at least in part on hash values of one or more children of the interior node;
- and
- provide a first digest of the first version of the journal, wherein the first digest is usable in a proof that the one or more entries are unmodified and stored in the first version of the journal;
- provide, subsequent to one or more additional entries being added to the journal, a second digest of a second version of the journal;
- and
- provide hash values sufficient to prove that the second digest is based at least in part on information included in the first digest and that the one or more entries are unmodified and stored in the second version of the journal.
A computer-implemented method, comprising:
- storing an entry in a first version of a journal, wherein the first version of the journal, upon storage of the entry, comprises:
- a plurality of leaf nodes, wherein a leaf node of the plurality of leaf nodes comprises a hash value based at least in part on a hash value of a prior node in the plurality of leaf nodes;
- a hierarchy of interior nodes, wherein an interior node of the hierarchy of interior nodes comprises a hash value based at least in part hash values of one or more children of the interior node;
- providing a first digest of the first version of the journal, wherein the first digest is usable for proving that the entry is unmodified and stored in the first version of the journal;
- providing a second digest of a second version of the journal;
- and
- provide hash values sufficient to prove that the second digest is based at least in part on information included in the first digest and that the entry is unmodified and stored in the second version of 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 first version of a journal, wherein the first version of the journal, upon storage of the entry, comprises:
- a plurality of leaf nodes, wherein a leaf node of the plurality of leaf nodes comprises a hash value based at least in part on a hash value of a prior node in the plurality of leaf nodes;
- a hierarchy of interior nodes, wherein an interior node of the hierarchy of interior nodes comprises a hash value based at least in part hash values of one or more children of the interior node;
- provide a first digest of the first version of the journal, wherein the first digest is usable for proving that the entry is unmodified and stored in the first version of the journal;
- provide a second digest of a second version of the journal;
- and
- provide hash values sufficient to prove that the second digest is based at least in part on information included in the first digest and that the entry is unmodified and stored in the second version of the journal.
Dependencies are inferred from the claim text.