# US 11,310,054 B2 · Symmetric function for journaled database proof

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,310,054 B2
- Document ID: US11310054B2
- Status: Granted
- Kind: B2
- Application number: 16/446,543
- Filed: 2019-06-19
- Published: 2020-12-24
- Granted: 2022-04-19
- 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/US11310054B2

## CPC

- H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- H04L 9/3218: {using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## 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 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.

### Claim 2 (depends on 1)

The system of claim 1, wherein output of the symmetric hash operator is based at least in part on a sorting and concatenation of the first and second operands.

### Claim 3 (depends on 1)

The system of claim 1, wherein the output of the symmetric hash operator is equivalent to the first operand when the first operand is not null and the second operand is null.

### Claim 4 (depends on 1)

The system of claim 1, wherein the hierarchy of nodes comprises a leaf node, wherein the leaf node comprises a reference to the entry and a hash value, the hash value based at least in part on application of the symmetric hash operator.

### Claim 5 (depends on 1)

The system of claim 1, wherein the list of hash values is sufficient for a cryptographic proof that an entry was stored in a nested journal.

### Claim 6

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.

### Claim 7 (depends on 6)

The computer-implemented method of claim 6, wherein output of the symmetric hash operator is based at least in part on a sorting and concatenation of the first and second operands.

### Claim 8 (depends on 7)

The computer-implemented method of claim 7, wherein a hash is computed from the concatenation of the first and second operands.

### Claim 9 (depends on 6)

The computer-implemented method of claim 6, wherein the output of the symmetric hash operator is equivalent to the first operand when the second operand is null.

### Claim 10 (depends on 6)

The computer-implemented method of claim 6, wherein the hierarchy of nodes comprises a leaf node, wherein the leaf node comprises a reference to the entry and a hash value based at least in part on application of the symmetric hash operator to an entry hash and a hash value of a second leaf node.

### Claim 11 (depends on 6)

The computer-implemented method of claim 6, wherein the cryptographic proof is based at least in part on application of the symmetric hash operator to one or more hash values of the list of hash values.

### Claim 12 (depends on 6)

The method of claim 6, wherein a leaf node of the journal is usable to provide a proof that validates a set of entries represented in the journal.

### Claim 13 (depends on 6)

The method of claim 6, wherein the list of hash values is sufficient for a cryptographic proof that an entry was stored in a nested journal.

### 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 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.

### Claim 15 (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 the symmetric hash operator to hash values of the list.

### Claim 16 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, wherein output of the symmetric hash operator is based at least in part on a sorting and concatenation of the first and second operands.

### Claim 17 (depends on 16)

The non-transitory computer-readable storage medium of claim 16, wherein a hash is computed from the concatenation of the first and second operands.

### Claim 18 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, wherein the output of the symmetric hash operator is equivalent to the first operand when the second operand is null.

### Claim 19 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, wherein the hierarchy of nodes comprises a leaf node, wherein the leaf node comprises a reference to the entry and a hash value.

### Claim 20 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, wherein an entry associated with a leaf node of the journal comprises a nested journal, and a hash of the entry corresponds to a digest node of the nested journal.