Fragmenting data for the purposes of persistent storage across multiple immutable data structures

• US 10,242,219 B2
• Filed: 12/18/2017
• Issued: 03/26/2019
• 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): Vo, Truong V
• Application Number:
  US15/845,436
• Publication Number:
  US 20180121673A1
• Time in Patent Office: 463 Days
• 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 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD

Abstract

Provided is a process including: receiving one or more write requests; selecting a first subset of the values as corresponding to higher-security fields; segmenting a first value in the first subset; instructing a first computing device to store a first subset of segments among the plurality of segments in memory; and instructing a second computing device to store a second subset of segments among the plurality of segments in memory.

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;

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; and

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

2. The medium of claim 1, 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; and

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.

3. The medium of claim 1, wherein:

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; and

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.

4. The medium of claim 3, wherein:

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

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

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

5. The medium of claim 3, 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;

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.

6. The medium of claim 3, 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.

7. The medium of claim 1, comprising:

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.

8. The medium of claim 7, 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.

9. The medium of claim 7, 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.

10. The medium of claim 9, 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.

11. The medium of claim 7, wherein:

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

12. The medium of claim 11, wherein:

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

13. The medium of claim 1, wherein:

read latency of the data structure scales proportionate to nlog(n), where n is a number of entries in the data structure.

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

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

16. The medium of claim 1, comprising:

segmenting the document into a plurality of segments; and

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

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

17. The medium of claim 16, wherein segmenting comprises:

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

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

18. The medium of claim 1, 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;

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.

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

20. 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;

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; and

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