Symmetric function for journaled database proof
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, comprising a hierarchy of nodes. A node in the hierarchy comprises a hash value computed by application of a symmetric hash operator to hash values of first and second child nodes. The symmetric hash operator generates equivalent output irrespective of the order of the operands. A cryptographic proof of the entry comprises successive application of the symmetric hash operator to a list of hashes from the hierarchy.
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 nodes, wherein a node of the hierarchy of nodes comprises a hash value computed by a symmetric hash operator applied to a first hash value of a first child node and a second hash value of a second child node, wherein output of the symmetric hash operator is the same irrespective of an order of the first and second hash values;
- and
- provide a list of hash values of nodes of the hierarchy, wherein the list of hash values is sufficient for a cryptographic proof that the entry was stored in the journal, wherein a digest value sufficient for the cryptographic proof is computable based, at least in part, on successive applications of the symmetric hash operator to hash values provided in the list of hash values.
A computer-implemented method, comprising:
- storing an entry in a journal, wherein the journal, upon storage of the entry, comprises a hierarchy of nodes, wherein a node of the hierarchy of nodes comprises a hash value computed by a symmetric hash operator applied to a first hash value of a first child node and a second hash value of a second child node, wherein output of the symmetric hash operator is the same irrespective of an order of the first and second hash values;
- and
- providing a list of hash values of nodes of the hierarchy, wherein the list of hash values is sufficient for a cryptographic proof that the entry was stored in the journal, wherein a digest value sufficient for the cryptographic proof is computable based, at least in part, on successive applications of the symmetric hash operator to hash values in the list of hash values.
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 nodes, wherein a node of the hierarchy of nodes comprises a hash value computed by a symmetric hash operator applied to a first hash value of a first child node and a second hash value of a second child node, wherein output of the symmetric hash operator is the same irrespective of an order of the first and second hash values;
- and
- provide a list of hash values of nodes of the hierarchy, wherein the list of hash values is sufficient for a cryptographic proof that the entry was stored in the journal, wherein a digest value sufficient for the cryptographic proof is computable based, at least in part, on successive applications of the symmetric hash operator to hash values in the list of hash values.
Dependencies are inferred from the claim text.