Generation of hash values within a blockchain

• US 10,075,298 B2
• Filed: 08/11/2017
• Issued: 09/11/2018
• Est. Priority Date: 06/02/2015
• Status: Active Grant

• Current Assignee: Altr Solutions, Inc.
• Original Assignee: Altr Solutions, Inc.
• Inventors: Struttmann, Christopher Edward
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): Raza, Muhammad
• Application Number:
  US15/675,470
• Publication Number:
  US 20170366353A1
• Time in Patent Office: 396 Days
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Provided is a process including: obtaining a plurality of records to be protected; forming a tamper-evident log configured to prevent an attacker from undetectably modifying any of the plurality of records stored in the tamper-evident log, wherein the cryptographic hash value of a given entry in the tamper-evident log is sequence agnostic to the sequence of entries in virtue of being based on values that do not specify a position in the sequence of entries; and storing the tamper-evident log in memory.

Claims

1. A tangible, non-transitory, machine-readable medium storing instructions that when executed by one or more processors effectuate operations comprising:

obtaining, with one or more processors, a plurality of records to be protected;

forming, with one or more processors, a tamper-evident log configured to prevent an attacker from undetectably modifying any of the plurality of records stored in the tamper-evident log, wherein;

the tamper-evident log comprises a plurality of entries sequentially added to the tamper-evident log at different times in a sequence of the entries specified by the tamper-evident log;

each entry comprises;

an identifier that distinguishes among the entries,

a respective record among the plurality of records,

an identifier of a previous consecutive record relative to the respective record in the sequence of the entries specified by the tamper-evident log,

a cryptographic hash value based on both a record and a cryptographic hash value of the previous consecutive entry relative to the respective record in the sequence of the entries specified by the tamper-evident log;

the cryptographic hash value of a given entry in the tamper-evident log is sequence agnostic to the sequence of entries in virtue of being based on values that do not specify a position in the sequence of entries;

the cryptographic hash value of the given entry is formed by selecting which types of parameters are input into a cryptographic hash function used to calculate at least some of the cryptographic hash values such that parameters that specify a position in the sequence are excluded;

storing, with one or more processors, the tamper-evident log in memory; and

splitting the tamper-evident log at or adjacent the given entry into a newer tamper-evident log and an older tamper-evident log, wherein cryptographic hash values in both the newer tamper-evident log and the older tamper-evident log are valid with respect to protected records after splitting, wherein;

the selected types of parameters exclude time, date, and order in the sequence of the entries specified by the tamper-evident log;

the selected types of parameters include records logged by the tamper-evident log of which the plurality of records are respective instances;

the cryptographic hash function is configured by supplying a lambda function;

splitting comprises changing pointers between entries in the newer tamper-evident log without changing cryptographic hash values in the newer tamper-evident log;

the cryptographic hash value of at least a plurality of entries in the tamper-evident log is sequence agnostic to the sequence of entries in virtue of being based on values that do not specify a position in the sequence of entries; and

different cryptographic hash function implementations are used for different cryptographic hash values of different entries.

2. The medium of claim 1, wherein:

the selected types of parameters consist essentially of records obtained to be logged by the tamper-evident system of which the plurality of records are respective instances.

3. The medium of claim 2, wherein:

the selected types of parameters consist of records obtained to be logged by the tamper-evident system of which the plurality of records are respective instances.

4. The medium of claim 1, wherein selecting which types of parameters are input into the cryptographic hash function comprises:

determining that a cryptographic hash function or method is designated as an abstract function or method in a programming language supporting delegation or inheritance; and

determining a non-abstract implementation of the abstract class or method, the implementation including the selection of types of parameters.

5. The medium of claim 1, wherein:

each record is a cryptographic hash value based on attributes of every node in a respective directed acyclic graph having 16 or more nodes.

6. The medium of claim 5, wherein:

each directed acyclic graph is a binary tree;

leaf nodes of the binary tree store values referenced by placeholders in a relational database; and

each record is a cryptographic hash value based on the values referenced by placeholders in a database.

7. The medium of claim 1, wherein:

splitting is performed without changing every cryptographic hash value in the newer tamper-evident log or the older tamper-evident log.

8. The medium of claim 7, wherein:

splitting is performed without changing any cryptographic hash value in the newer tamper-evident log or the older tamper-evident log.

9. The medium of claim 1, wherein:

the operations comprise determining that a size of the tamper-evident log has or will exceed a threshold; and

splitting in response to the determination that the size of the tamper-evident log has or will exceed the threshold.

10. The medium of claim 1, wherein:

the cryptographic hash function includes repeatedly, for an input longer than one-way compression function of the cryptographic hash function is configured to accept, until a beginning or ending portion of the input to the cryptographic hash function is reached;

obtaining a parsed portion by parsing a remaining portion of the input that is of a length determined based on a difference between a length of input the one-way compression function of the cryptographic hash function is configured to accept and a length of an output of the one-way compression function is configured to emit;

appending or prepending an output of a previous iteration of the one-way compression function to the parsed portion to form an input for a current iteration of the one-way compression function; and

transforming the input for the current iteration with the one-way compression function to form an output of the one-way function.

11. The medium of claim 1, wherein:

the operations comprise logging database access requests to the tamper-evident log, wherein the records are based on the logged database access requests.

12. The medium of claim 1, wherein:

the tamper-evident log is part of a collection of tamper-evident logs that store more than 1 million database values each distributed among multiple ones of the collection of tamper-evident logs;

the collection of collection of tamper-evident logs are configured to make the database values retrievable within 100 milliseconds of a query;

the collection of collection of tamper-evident logs are configured such that retrieval latency of the database values scales according to n log(n), where n is a number of the database values in the collection of tamper-evident logs; and

the operations comprise throttling responses to retrievals based on a risk assessment associated with the retrievals.

13. The medium of claim 1, the operations comprising:

steps for obtaining records to be protected;

steps for forming a tamper-evident log;

steps for retrieving data from a tamper-evident log;

steps for forming a sequence agnostic cryptographic hash value; and

steps for refactoring a tamper-evident log.

14. The medium of claim 1, comprising:

executing an application that generates data upon which the entries are based;

intercepting write requests from the application to a database where the data upon which the entries are based is stored; and

substituting pointers in the write request and causing the pointers to be stored in the database in place of the data upon which the entries are based.

15. A method, comprising:

obtaining, with one or more processors, a plurality of records to be protected;

forming, with one or more processors, a tamper-evident log configured to prevent an attacker from undetectably modifying any of the plurality of records stored in the tamper-evident log, wherein;

the tamper-evident log comprises a plurality of entries sequentially added to the tamper-evident log at different times in a sequence of the entries specified by the tamper-evident log;

each entry comprises;

an identifier that distinguishes among the entries,

a respective record among the plurality of records,

an identifier of a previous consecutive record relative to the respective record in the sequence of the entries specified by the tamper-evident log,

a cryptographic hash value based on both a record and a cryptographic hash value of the previous consecutive entry relative to the respective record in the sequence of the entries specified by the tamper-evident log;

the cryptographic hash value of a given entry in the tamper-evident log is sequence agnostic to the sequence of entries in virtue of being based on values that do not specify a position in the sequence of entries;

the cryptographic hash value of the given entry is formed by selecting which types of parameters are input into a cryptographic hash function used to calculate at least some of the cryptographic hash values such that parameters that specify a position in the sequence are excluded;

storing, with one or more processors, the tamper-evident log in memory; and

splitting the tamper-evident log at or adjacent the given entry into a newer tamper-evident log and an older tamper-evident log, wherein cryptographic hash values in both the newer tamper-evident log and the older tamper-evident log are valid with respect to protected records after splitting, wherein;

the selected types of parameters exclude time, date, and order in the sequence of the entries specified by the tamper-evident log;

the selected types of parameters include records logged by the tamper-evident log of which the plurality of records are respective instances;

the cryptographic hash function is configured by supplying a lambda function;

splitting comprises changing pointers between entries in the newer tamper-evident log without changing cryptographic hash values in the newer tamper-evident log; and

the cryptographic hash value of at least a plurality of entries in the tamper-evident log is sequence agnostic to the sequence of entries in virtue of being based on values that do not specify a position in the sequence of entries and

different cryptographic hash function implementations are used for different cryptographic hash values of different entries.

16. The method of claim 15, wherein:

the selected types of parameters consist essentially of records obtained to be logged by the tamper-evident system of which the plurality of records are respective instances.

17. The method of claim 16, wherein:

the selected types of parameters consist of records obtained to be logged by the tamper-evident system of which the plurality of records are respective instances.

18. The method of claim 15, wherein selecting which types of parameters are input into the cryptographic hash function comprises:

determining that a cryptographic hash function or method is designated as an abstract function or method in a programming language supporting delegation or inheritance; and

determining a non-abstract implementation of the abstract class or method, the implementation including the selection of types of parameters.

19. The method of claim 15, wherein:

each record is a cryptographic hash value based on attributes of every node in a respective directed acyclic graph having 16 or more nodes.

20. The method of claim 19, wherein:

each directed acyclic graph is a binary tree;

leaf nodes of the binary tree store values referenced by placeholders in a relational database; and

each record is a cryptographic hash value based on the values referenced by placeholders in a database.

21. The method of claim 15, wherein:

splitting is performed without changing every cryptographic hash value in the newer tamper-evident log or the older tamper-evident log.

22. The method of claim 21, wherein:

splitting is performed without changing any cryptographic hash value in the newer tamper-evident log or the older tamper-evident log.

23. The method of claim 15, wherein:

the operations comprise determining that a size of the tamper-evident log has or will exceed a threshold; and

splitting in response to the determination that the size of the tamper-evident log has or will exceed the threshold.

24. The method of claim 15, wherein:

the cryptographic hash function includes repeatedly, for an input longer than one-way compression function of the cryptographic hash function is configured to accept, until a beginning or ending portion of the input to the cryptographic hash function is reached;

obtaining a parsed portion by parsing a remaining portion of the input that is of a length determined based on a difference between a length of input the one-way compression function of the cryptographic hash function is configured to accept and a length of an output of the one-way compression function is configured to emit;

appending or prepending an output of a previous iteration of the one-way compression function to the parsed portion to form an input for a current iteration of the one-way compression function; and

transforming the input for the current iteration with the one-way compression function to form an output of the one-way function.

25. The method of claim 15, wherein:

the operations comprise logging database access requests to the tamper-evident log, wherein the records are based on the logged database access requests.

26. The method of claim 15, wherein:

the tamper-evident log is part of a collection of tamper-evident logs that store more than 1 million database values each distributed among multiple ones of the collection of tamper-evident logs;

the collection of collection of tamper-evident logs are configured to make the database values retrievable within 100 milliseconds of a query;

the collection of collection of tamper-evident logs are configured such that retrieval latency of the database values scales according to n log(n), where n is a number of the database values in the collection of tamper-evident logs; and

the operations comprise throttling responses to retrievals based on a risk assessment associated with the retrievals.

27. The method of claim 15, the operations comprising:

steps for forming a tamper-evident log.

28. The method of claim 15, comprising:

executing an application that generates data upon which the entries are based;

intercepting write requests from the application to a database where the data upon which the entries are based is stored; and

substituting pointers in the write request and causing the pointers to be stored in the database in place of the data upon which the entries are based.