Verifiable record storage service

Patent metadata

Field	Value
Publication number	US-10904264-B2
Application number	US-201816127091-A
Country	US
Kind code	B2
Filing date	Sep 10, 2018
Priority date	Aug 26, 2016
Publication date	Jan 26, 2021
Grant date	Jan 26, 2021

Abstract

A record storage system maintains an interdependent series of hash values for records submitted to the record storage service by one or more clients. The record storage service generates a hash value for each record based at least in part on the content of the record and a hash value of one or more previous records. In some examples, the generated hash values are saved in an audit database by the clients. Clients may retain some, all, or none of the hash values based on the amount of auditing desired and the amount of storage space available in the audit database. The clients are able to verify the integrity of records submitted to the record storage system by retrieving the records from the system, recalculating the hash values of the records, and comparing the recalculated hash values to the hash values retained by the client.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
determining a set of record identifiers for a batch of records acquired from a client;
determining a hash value for the batch of records, the hash value based at least in part on a hash value associated with another batch of records previously acquired, and the batch of records to be stored in association with the set of record identifiers and the hash value;
providing the batch of records, the hash value, and the set of record identifiers to the client, wherein the client is able to confirm integrity of the batch of records by determining that the hash value matches an expected hash value determined by the client; and
as a result of providing the hash value to the client, obtaining an indication from the client that the batch of records does not match an original batch of records provided by the client.

2. The computer-implemented method of claim 1 , further comprising:
receiving, from the client, a request for audit information associated with the batch of records; and
providing, to the client, a hash value of a record batch prior to the batch of records.

3. The computer-implemented method of claim 1 , wherein the batch of records is comprised of ordered log entries.

4. A computer system, comprising one or more processors and a physical memory storing executable instructions that, as a result of being executed by the one or more processors, cause the computer system to:
generate an integrity indicator for a particular record batch in a sequence of record batches by at least determining an integrity indicator for a record in the particular record batch based at least in part on the record and an integrity indicator of a previous record in the particular record batch;
provide, to a client, audit information that includes the integrity indicator for the particular record batch and information that identifies a set of records associated with the particular record batch; and
as a result of providing the audit information to the client, receiving an indication from the client that the particular record batch does not match an original record batch provided by the client.

5. The computer system of claim 4 , wherein the executable instructions further cause the computer system to establish an ordering for the records by at least associating a comparable identifier to each record in the sequence of record batches, wherein the information that identifies the set of records associated with the particular record batch comprises the identifiers associated with the particular record batch.

6. The computer system of claim 4 , wherein the integrity indicator for the particular record batch is based at least in part on a cryptographic hash of the records associated with the particular record batch and the integrity indicator of a previous record batch.

7. The computer system of claim 4 , wherein the executable instructions further cause the computer system to generate an initial integrity indicator for an initial record batch in the sequence of record batches, the initial integrity indicator based at least in part on records associated with the initial record batch, and an initial seed value accessible to the client.

8. The computer system of claim 4 , wherein the integrity indicator for the particular record batch in the sequence of record batches is generated by at least:
arranging the records associated with the particular record batch into a sequence of records;
determining an integrity indicator for each record in the sequence of records, the integrity indicator of a particular record in the sequence of records based at least in part on the particular record and an integrity indicator of a record previous, in the sequence of records, to the particular record; and
wherein the integrity indicator for the particular record batch matches the integrity indicator of the last record in the sequence of records.

9. The computer system of claim 4 , wherein the integrity indicator for the particular record batch in the sequence of record batches is generated by at least:
determining an integrity indicator for each of the records associated with the particular record batch to produce a set of integrity indicators; and
combining the set of integrity indicators into a single integrity indicator using a commutative function.

10. The computer system of claim 9 , wherein the set of integrity indicators is deterministically combined using a logical operation to form a combined integrity indicator.

11. The computer system of claim 4 , wherein the executable instructions further cause the computer system to:
receive a verification request from the client, the verification request identifying a particular record batch; and
provide, to the client, the records associated with the particular record batch.

12. A non-transitory computer-readable storage medium having stored 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:
provide, to a client, a first integrity indicator associated with a first batch of records and a first set of identifiers associated with the first batch of records;
determine a second integrity indicator by at least generating a integrity indicator for a record in a second batch of records, the integrity indicator of the record based at least in part on a integrity indicator of a previous record in the second batch of records and the first integrity indicator;
provide, to the client, the second integrity indicator and a second set of identifiers associated with the second batch of records; and
as a result of providing the second integrity indicator to the client, receiving an indication from the client that the second batch of records does not match an original batch of records provided by the client.

13. The non-transitory computer-readable storage medium of claim 12 , wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to:
store the first integrity indicator in association with the first batch of records; and
store the second integrity indicator in associate with the second batch of records.

14. The non-transitory computer-readable storage medium of claim 12 , wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to store the first integrity indicator in association with each record in the second batch of records.

15. The non-transitory computer-readable storage medium of claim 12 , wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to:
receive, from the client, a request for the second batch of records;
provide, in response to the request, the second batch of records and the first integrity indicator; and
whereby the client is able to determine an expected integrity indicator for the second batch of records based on the first integrity indicator and the second batch of records.

16. The non-transitory computer-readable storage medium of claim 12 , wherein the instructions, as a result of being executed by the one or more processors, further cause the computer system to determine the second integrity indicator by at least generating a integrity indicator for each record in the second batch of records, an integrity indicator of each record based at least in part on the integrity indicator of a previous record in the second batch of reco

Assignees

• Amazon Tech Inc

Inventors

• Waugh Robert Mark
• Vassallo Daniel

Classifications

• H04L9/50

  using hash chains, e.g. blockchains or hash trees · CPC title

• H04L63/1425

  Traffic logging, e.g. anomaly detection · CPC title

• H04L9/3239

  involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD · CPC title

• H04L63/123 Primary

  received data contents, e.g. message integrity · CPC title

• H04L2209/38

  Electricity · mapped topic