# US 2020/0401626 A1 · Threaded leaf nodes in database journal > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2020/0401626 A1 - Document ID: US20200401626A1 - Status: Published application - Kind: A1 - Application number: 16/446,528 - Filed: 2019-06-19 - Published: 2020-12-24 - Earliest claimed: 2019-06-19 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Tate Andrew Certain; Benjamin Nelson Glowney; Allan Henry Vermeulen - Web page: https://patentgrep.com/patent/US20200401626A1 ## CPC - G06F 16/9027: {Trees} - G06F 21/316: {by observing the pattern of computer usage, e.g. typical user behaviour} - G06F 9/466: {Transaction processing} - G06F 16/21: Design, administration or maintenance of databases - G06F 21/602: {Providing cryptographic facilities or services} - H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD} - H04L 9/50: {using hash chains, e.g. blockchains or hash trees} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The system of claim 1, wherein the list of hash values is sufficient for a cryptographic proof that the entry and a plurality of additional entries were stored in the journal. ### Claim 3 (depends on 1) The system of claim 1, wherein an interior node comprises a hash value based at least in part on first and second leaf nodes of the ordered plurality of leaf nodes. ### Claim 4 (depends on 1) The system of claim 1, wherein the hash value is calculated using a symmetric hash operator. ### Claim 5 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. ### Claim 6 (depends on 5) The computer-implemented method of claim 5, further comprising: providing the list of hash values in response to a request to prove that the entry was stored in the journal. ### Claim 7 (depends on 5) The computer-implemented method of claim 5, wherein the entry is indicative of a database transaction. ### Claim 8 (depends on 5) The computer-implemented method of claim 5, wherein the list of hash values is provided to a client for proving that the entry and a plurality of additional entries were stored in the journal. ### Claim 9 (depends on 5) The computer-implemented method of claim 5, further comprising: calculating a hash value for an interior node based at least in part on first and second leaf nodes, wherein the first and second leaf nodes are children of the interior node. ### Claim 10 (depends on 5) The computer-implemented method of claim 5, further comprising: computing the hash value of the second leaf node based at least in part on a symmetric hash operator. ### Claim 11 (depends on 5) The computer-implemented method of claim 5, wherein the list of hash values comprises a hash value for a leaf node prior to the first and second leaf nodes. ### Claim 12 (depends on 5) The computer-implemented method of claim 5, wherein the list of hash values is sufficient when a digest value can be computed by one more applications of a symmetric hash operator to hash values of the list. ### Claim 13 (depends on 5) The computer-implemented method of claim 5, wherein the plurality of leaf nodes comprises a digest leaf node, the digest leaf node comprises a hash value based at least in part on hash values of the first and second leaf nodes. ### Claim 14 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. ### Claim 15 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the executable instructions further comprise executable instructions that, as a result of being executed by the one or more processors, cause the computer system to at least: provide the list of hash values in response to a request to prove that the entry was stored in the journal. ### Claim 16 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the executable instructions further comprise executable instructions that, as a result of being executed by the one or more processors, cause the computer system to at least: compute a hash value for an interior node based at least in part on the first and second leaf nodes, wherein the first and second leaf nodes are children of the interior node. ### Claim 17 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the executable instructions further comprise executable instructions that, as a result of being executed by the one or more processors, cause the computer system to at least: compute the hash value of the first leaf node based at least in part on a symmetric hash operator. ### Claim 18 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the list of hash values comprises a hash value for a leaf node prior to the first and second leaf nodes. ### Claim 19 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the list of hash values is sufficient when a digest value can be computed by one more applications of a symmetric hash operator to hash values of the list. ### Claim 20 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the plurality of leaf nodes comprises a digest leaf node, the digest leaf node comprises a hash value based at least in part on hash values of the first and second leaf nodes.