Immutable datastore for low-latency reading and writing of large data sets

• US 10,042,782 B2
• Filed: 08/11/2017
• Issued: 08/07/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 A
• Application Number:
  US15/675,460
• Publication Number:
  US 20170364450A1
• Time in Patent Office: 361 Days
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: H04L 63/102 Entity profiles
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Provided is a process including: receiving a write command requesting that a document associated with the write command be stored in an immutable data structure that prevents an attacker attempting to modify the document from concealing that the document was modified after storing the document in the data structure; forming a tamper-evident, immutable directed acyclic graph having the document in one or more nodes of the graph; and storing the directed acyclic graph.

Claims

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

receiving, with one or more processors, a write command requesting that a document associated with the write command be stored in an immutable data structure that prevents an attacker attempting to modify the document from concealing that the document was modified after storing the document in the data structure;

in response to the write command, forming, with one or more processors, at least part of a directed acyclic graph having a plurality of nodes and edges linking respective pairs of the nodes, wherein;

nodes of the directed acyclic graph have respective node identifiers that distinguish between different nodes of the directed acyclic graph;

nodes of the directed acyclic graph have node content;

each of at least some nodes of the directed acyclic graph have the node content that includes a plurality of cryptographic hash values;

the cryptographic hash values of each node are each (i) a cryptographic hash function output based on node content of another respective node of the directed acyclic graph and (ii) associated with a node identifier of the other respective node, thereby designating an edge of the directed acyclic graph; and

forming the at least part of the directed acyclic graph comprises;

writing data encoding at least some of the document to node content of a first set of nodes of the directed acyclic graph; and

from the first set of nodes, traversing edges of the directed acyclic graph and forming node content of nodes visited via the traversing by determining the cryptographic hash values of the visited nodes;

storing, with one or more processors, the directed acyclic graph in memory;

receiving a read command requesting that the document be retrieved from the immutable data structure;

accessing the first set of nodes of the directed acyclic graph to retrieve at least part of the document;

determining whether the at least part of the document has been modified at least in part by;

calculating one or more cryptographic hash values based on node content of the first set of nodes;

comparing the one or more calculated cryptographic hash values to one or more corresponding cryptographic hash values of node content of nodes adjacent the first set of nodes in the directed acyclic graph; and

determining that the at least part of the document has not been modified based on the comparison, wherein;

the document is a file larger than 1 kilobyte;

the directed acyclic graph includes a binary tree;

the document is stored in one or more leaf nodes of the binary tree;

the directed acyclic graph includes a second set of nodes disjoint from the first set of nodes, the second set of nodes being part of the binary tree and visited nodes during the traversing of edges of the directed acyclic graph;

traversing comprises forming a visited node to which traversal occurs such that at least part of the binary tree is formed during traversing;

traversing comprises traversing from leaf nodes of the binary tree toward a root node of the binary tree;

forming at least part of the directed acyclic graph comprises forming the entire binary tree;

storing the directed acyclic graph in memory comprises storing three or more different instances of the directed acyclic graph in three or more different computing devices on three or more different subnetworks;

the directed acyclic graph is a binary tree;

at least part of the document is stored in one or more leaf nodes of the binary tree;

a root node of the binary tree has node content including a cryptographic hash value that is based on node content of every node of the binary tree;

the document is encoded in encrypted form in the node content of one or more leaf nodes;

the document is compressed with entropy coding before being encrypted into the encrypted form; and

read latency of the data structure scales at least in part based on a value proportionate to nlog(n), where n is a number of entries in the data structure.

2. The medium of claim 1, wherein:

the entire document is stored in node content of a single leaf node; and

the document is encoded in encrypted form in the node content of the single leaf node.

3. The medium of claim 1, wherein:

the document is stored in a plurality of leaf nodes of the binary tree;

different parts of the document are stored in node content of different leaf nodes; and

node content of nodes adjacent the leaf nodes in the binary tree each comprise;

a first identifier of a first adjacent leaf node that is adjacent the respective node in the binary tree;

a first cryptographic hash value based on a cryptographic hash of node content of the first adjacent leaf node;

a second identifier of a second adjacent leaf node that is adjacent the respective node in the binary tree; and

a second cryptographic hash value based on a cryptographic hash of node content of the second adjacent leaf node.

4. The medium of claim 1, wherein storing the directed acyclic graph in memory comprises appending a node to a linked list of nodes, the appended node having a node content including (i) a cryptographic hash value based on node content of every node in the linked list, and (ii) a cryptographic hash value based on node content of every node in the binary tree.

5. The medium of claim 1, wherein:

calculating the one or more cryptographic hash values comprises inputting node content of at least some of the first set of nodes into an SHA-256 hash function; and

comparing comprises determining that an output of the function matches a corresponding value stored in node content of an adjacent node of the directed acyclic graph.

6. The medium of claim 1, wherein determining whether the at least part of the document has been modified comprises:

accessing a node of the directed acyclic graph having node content with a given cryptographic hash value based on node content of every node in the directed acyclic graph; and

re-calculating the given cryptographic hash value based on the node content of the first set of nodes; and

determining that the given cryptographic hash value is identical to the re-calculated cryptographic hash value.

7. The medium of claim 6, wherein determining whether the at least part of the document has been modified comprises:

traversing a chain of cryptographic hash values extending from a most-recently added node in the directed acyclic graph to nodes adjacent the first set of nodes; and

validating that current node content produces matching cryptographic hash values for each cryptographic hash value in the chain.

8. The medium of claim 1, wherein:

the data structure stores more than 100,000 documents occupying more than 100 Gb of storage.

9. The medium of claim 8, wherein:

the document is retrieved and validated as having not been modified within 250 milliseconds of receiving the read command.

10. The medium of claim 1, wherein:

writing data encoding at least some of the document to node content of the first set of nodes of the directed acyclic graph comprises steps for storing a document in a directed acyclic graph.

11. The medium of claim 1, wherein:

forming at least part of the directed acyclic graph comprises steps for forming a directed acyclic graph with edges corresponding to cryptographic hash pointers.

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

segmenting the document into a plurality of segments; and

storing a first subset of the segments in the directed acyclic graph; and

storing a second subset of the segments in another directed acyclic graph, the second subset being a different set from the first subset.

13. The medium of claim 12, wherein segmenting comprises:

determining frequencies with which sequences of symbols occur in the document or a corpus; and

segmenting the document at boundaries of sequences of symbols selected based on at least some of the frequencies.

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

storing a first subset of information from the document in the directed acyclic graph;

storing a second subset of information from the document in a second directed acyclic graph; and

storing a third subset of information from the document in a third directed acyclic graph, wherein;

each pairwise combination of the first subset of information, the second subset of information, and the third subset of information contain sufficient redundant information such that if a given subset of information not part of the respective pairwise combination is unavailable, the given subset of information is retrievable from the respective pairwise combination but not from individual members of the pairwise combination.

15. The medium of claim 1, comprising:

storing a first part of a mutable relational database in the data structure; and

providing a enterprise application based on the database.

16. A method, comprising:

receiving, with one or more processors, a write command requesting that a document associated with the write command be stored in an immutable data structure that prevents an attacker attempting to modify the document from concealing that the document was modified after storing the document in the data structure;

in response to the write command, forming, with one or more processors, at least part of a directed acyclic graph having a plurality of nodes and edges linking respective pairs of the nodes, wherein;

nodes of the directed acyclic graph have respective node identifiers that distinguish between different nodes of the directed acyclic graph;

nodes of the directed acyclic graph have node content;

each of at least some nodes of the directed acyclic graph have the node content that includes a plurality of cryptographic hash values;

the cryptographic hash values of each node are each (i) a cryptographic hash function output based on node content of another respective node of the directed acyclic graph and (ii) associated with a node identifier of the other respective node, thereby designating an edge of the directed acyclic graph; and

forming the at least part of the directed acyclic graph comprises;

writing data encoding at least some of the document to node content of a first set of nodes of the directed acyclic graph; and

from the first set of nodes, traversing edges of the directed acyclic graph and forming node content of nodes visited via the traversing by determining the cryptographic hash values of the visited nodes;

storing, with one or more processors, the directed acyclic graph in memory;

receiving a read command requesting that the document be retrieved from the immutable data structure;

accessing the first set of nodes of the directed acyclic graph to retrieve at least part of the document;

determining whether the at least part of the document has been modified at least in part by;

calculating one or more cryptographic hash values based on node content of the first set of nodes;

comparing the one or more calculated cryptographic hash values to one or more corresponding cryptographic hash values of node content of nodes adjacent the first set of nodes in the directed acyclic graph; and

determining that the at least part of the document has not been modified based on the comparison, wherein;

the document is a file larger than 1 kilobyte;

the directed acyclic graph includes a binary tree;

the document is stored in one or more leaf nodes of the binary tree;

the directed acyclic graph includes a second set of nodes disjoint from the first set of nodes, the second set of nodes being part of the binary tree and visited nodes during the traversing of edges of the directed acyclic graph;

traversing comprises forming a visited node to which traversal occurs such that at least part of the binary tree is formed during traversing;

traversing comprises traversing from leaf nodes of the binary tree toward a root node of the binary tree;

forming at least part of the directed acyclic graph comprises forming the entire binary tree;

storing the directed acyclic graph in memory comprises storing three or more different instances of the directed acyclic graph in three or more different computing devices on three or more different subnetworks;

the directed acyclic graph is a binary tree;

at least part of the document is stored in one or more leaf nodes of the binary tree;

a root node of the binary tree has node content including a cryptographic hash value that is based on node content of every node of the binary tree;

the entire document is stored in node content of one or more leaf nodes;

the document is encoded in encrypted form in the node content of the one or more leaf nodes;

the document is compressed with entropy coding before being encrypted into the encrypted form; and

read latency of the data structure scales at least in part based on a value proportionate to nlog(n), where n is a number of entries in the data structure.

17. The method of claim 16, wherein:

the entire document is stored in node content of a single leaf node; and

the document is encoded in encrypted form in the node content of the single leaf node.

18. The method of claim 16, wherein:

the document is stored in a plurality of leaf nodes of the binary tree;

different parts of the document are stored in node content of different leaf nodes; and

node content of nodes adjacent the leaf nodes in the binary tree each comprise;

a first identifier of a first adjacent leaf node that is adjacent the respective node in the binary tree;

a first cryptographic hash value based on a cryptographic hash of node content of the first adjacent leaf node;

a second identifier of a second adjacent leaf node that is adjacent the respective node in the binary tree; and

a second cryptographic hash value based on a cryptographic hash of node content of the second adjacent leaf node.

19. The method of claim 16, wherein storing the directed acyclic graph in memory comprises appending a node to a linked list of nodes, the appended node having a node content including (i) a cryptographic hash value based on node content of every node in the linked list, and (ii) a cryptographic hash value based on node content of every node in the binary tree.

20. The method of claim 16, wherein:

calculating the one or more cryptographic hash values comprises inputting node content of at least some of the first set of nodes into an SHA-256 hash function; and

comparing comprises determining that an output of the function matches a corresponding value stored in node content of an adjacent node of the directed acyclic graph.

21. The method of claim 16, wherein determining whether the at least part of the document has been modified comprises:

accessing a node of the directed acyclic graph having node content with a given cryptographic hash value based on node content of every node in the directed acyclic graph; and

re-calculating the given cryptographic hash value based on the node content of the first set of nodes; and

determining that the given cryptographic hash value is identical to the re-calculated cryptographic hash value.

22. The method of claim 21, wherein determining whether the at least part of the document has been modified comprises:

traversing a chain of cryptographic hash values extending from a most-recently added node in the directed acyclic graph to nodes adjacent the first set of nodes; and

validating that current node content produces matching cryptographic hash values for each cryptographic hash value in the chain.

23. The method of claim 16, wherein:

the data structure stores more than 100,000 documents occupying more than 100 Gb of storage.

24. The method of claim 23, wherein:

the document is retrieved and validated as having not been modified within 250 milliseconds of receiving the read command.

25. The method of claim 16, wherein:

writing data encoding at least some of the document to node content of the first set of nodes of the directed acyclic graph comprises steps for storing a document in a directed acyclic graph.

26. The method of claim 16, wherein:

forming at least part of the directed acyclic graph comprises steps for forming a directed acyclic graph with edges corresponding to cryptographic hash pointers.

27. The method of claim 16, comprising:

segmenting the document into a plurality of segments;

storing a first subset of the segments in the directed acyclic graph; and

storing a second subset of the segments in another directed acyclic graph, the second subset being a different set from the first subset.

28. The method of claim 27, wherein segmenting comprises:

determining frequencies with which sequences of symbols occur in the document or a corpus; and

segmenting the document at boundaries of sequences of symbols selected based on at least some of the frequencies.

29. The method of claim 16, comprising:

storing a first subset of information from the document in the directed acyclic graph;

storing a second subset of information from the document in a second directed acyclic graph; and

storing a third subset of information from the document in a third directed acyclic graph, wherein;

each pairwise combination of the first subset of information, the second subset of information, and the third subset of information contain sufficient redundant information such that if a given subset of information not part of the respective pairwise combination is unavailable, the given subset of information is retrievable from the respective pairwise combination but not from individual members of the pairwise combination.

30. The method of claim 16, comprising:

storing a first part of a mutable relational database in the data structure; and

providing a enterprise application based on the database.