Using a tree structure to segment and distribute records across one or more decentralized, acyclic graphs of cryptographic hash pointers

• US 10,505,740 B2
• Filed: 12/05/2018
• Issued: 12/10/2019
• Est. Priority Date: 06/02/2015
• Status: Active Grant

• Current Assignee: Altr Solutions, Inc.
• Original Assignee: Altr Solutions, Inc.
• Inventors: Struttmann, Christopher Edward, Beecham, James Douglas
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): Raza, Muhammad
• Application Number:
  US16/211,057
• Publication Number:
  US 20190116047A1
• Time in Patent Office: 370 Days
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 21/78 to assure secure storage of data address-based protection against unauthorised use of memory G06F12/14; record carriers for use with machines and with at least a part designed to carry digital markings G06K19/00
• CPC Class Codes: H04L 9/0637 Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Provided is a process including: receiving, with one or more processors, a first request to store a record from a computing entity; encoding, with one or more processors, the record in a first plurality of segments; arranging, with one or more processors, the first plurality of segments in respective content nodes of a first content graph, wherein at least some content nodes of the first content graph have two or more content edges of the first content graph pointing to two or more respective other content nodes of the first content graph; and storing, with one or more processors, the content nodes of the first content graph in a verification graph.

Claims

1. A tangible, non-transitory, machine-readable medium storing instructions that when executed by one or more processors effectuate operations configured to expedite retrieval of records written to persistent storage, the operations comprising:

receiving, with one or more processors, a first request to store a record from a computing entity;

encoding, with one or more processors, the record in a first plurality of segments;

arranging, with one or more processors, the first plurality of segments in respective content nodes of a first content graph, wherein;

each segment is stored in a different content node of the first content graph;

directed content edges of the first content graph connect respective pairs of the content nodes of the first content graph;

the directed content edges define a plurality of directed paths through the first content graph by which each of the segments is reachable from a first root content node of the first content graph; and

at least some content nodes of the first content graph have two or more content edges of the first content graph pointing to two or more respective other content nodes of the first content graph;

storing, with one or more processors, the content nodes of the first content graph in a verification graph, wherein;

the verification graph comprises a plurality of verification nodes;

the content nodes and content edges are stored as content of the verification nodes;

respective pairs of the verification nodes are connected by respective directed verification edges; and

the verification graph is configured to indicate tampering with any of a plurality of records stored in the verification graph;

returning, with one or more processors, a first identifier of the first root content node to the computing entity, wherein the first identifier identifies a verification node of the verification graph storing the first root content node;

receiving a request to read the record from persistent storage, the request indicating the first identifier of the root content node; and

traversing the content graph from the first root content node to retrieve every content node of the content graph from the verification graph, wherein at least some of the content nodes are retrieved concurrently, wherein;

the verification graph includes a plurality cryptographic hash pointers;

read latency of the record from the verification graph scales at less than O(n) in big O notation, where n is a number of the segments.

2. The medium of claim 1, wherein:

the first content graph includes a binary tree that accounts for at least half of the content nodes of the content graph.

3. The medium of claim 2, wherein:

the first content graph is a balanced binary tree.

4. The medium of claim 1, wherein:

the first content graph includes a skip list defined by content edges of the content graph.

5. The medium of claim 1, wherein:

the first content graph defines k-ary tree in which each content node of the k-ary tree has fewer k or fewer child content nodes, wherein k is 3 or larger.

6. The medium of claim 5, wherein:

the first content graph includes three or more levels of hierarchy.

7. The medium of claim 5, wherein:

at least half of the content nodes of the k-ary tree have 2 or more child nodes.

8. The medium of claim 5, wherein arranging the first plurality of segments in the first content graph comprises iteratively, in a plurality of iterations, executing operations comprising:

obtaining a set of the first plurality of segments to be arranged;

determining a size of the set;

selecting 1/k of the size of the set from the set to form a selected subset;

arranging the selected subset in a current level of a hierarchy of the first content graph;

removing the subset from the set of the first plurality of segments to be arranged; and

designating a next level higher than the current level of the hierarchy as the current level.

9. The medium of claim 8, wherein:

the subset is a sequential collection of segments of the record;

the subset precedes unselected members of the set in the record; and

a last segment of the record is stored in the first root content node.

10. The medium of claim 1, wherein:

the first content graph comprises means for storing segmented data to facilitate concurrent retrieval.

11. The medium of claim 1, wherein:

the record is a file;

the first identifier distinguishes the first root content node from other content nodes of the first content graph; and

the request is a request to write the file to persistent storage from a security driver of an operating system of a user computing device.

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

receiving a second request to store a revised version of the record from the computing entity, the second request being associated with the first identifier of the first root content node;

encoding the revised version of the record in a second plurality of revised segments, wherein a first subset of the revised segments are identical to corresponding ones of the first plurality of segments and a second subset of the revised segments are different from corresponding ones of the first plurality of segments;

arranging the second subset of segments in a second content graph that partially overlaps the first content graph, wherein;

the overlap includes at least some content nodes storing respective segments of the first subset previously stored in the verification graph;

the second content graph includes a second root content node;

the second content graph does not include the first root content node;

both content nodes storing the second subset of segments and the at least some content nodes storing respective segments of the first subset are reachable in the second content graph from the second root node; and

content nodes storing the second subset of segments are not reachable from the first root content node of the first content graph;

storing the second subset in the verification graph without re-writing the at least some content nodes storing respective segments of the first subset to the verification graph; and

returning a second identifier of the second root content node to the computing entity.

13. The medium of claim 12, comprising:

identifying the second subset by comparing respective cryptographic hashes of the segments and revised segments without retrieving the record from storage in the verification graph.

14. The medium of claim 1, wherein:

the directed verification edges correspond to cryptographic hash pointers based on content of respective verification nodes to which respective cryptographic hash pointers point; and

content of verification nodes includes respective cryptographic hash values of respective cryptographic hash pointers of respective edges of respective verification nodes.

15. The medium of claim 1, wherein:

the verification graph includes a plurality of directed acyclic graphs of the cryptographic hash pointers; and

different portions of the content graph are stored as content of verification nodes of the different directed acyclic graphs of cryptographic hash pointer.

16. The medium of claim 1, wherein:

encoding the record in a first plurality of segments comprises partitioning a bitstream of a file into the plurality of segments; and

the segments are respective subsequences of the bitstream.

17. The medium of claim 1, wherein:

encoding the record in the first plurality of segments comprises applying linear coding to the record.

18. The medium of claim 1, wherein:

traversing the content graph comprises performing a breadth first traversal of the content graph.

19. A method, comprising:

receiving, with one or more processors, a first request to store a record from a computing entity;

encoding, with one or more processors, the record in a first plurality of segments;

arranging, with one or more processors, the first plurality of segments in respective content nodes of a first content graph, wherein;

each segment is stored in a different content node of the first content graph;

directed content edges of the first content graph connect respective pairs of the content nodes of the first content graph;

the directed content edges define a plurality of directed paths through the first content graph by which each of the segments is reachable from a first root content node of the first content graph; and

at least some content nodes of the first content graph have two or more content edges of the first content graph pointing to two or more respective other content nodes of the first content graph;

storing, with one or more processors, the content nodes of the first content graph in a verification graph, wherein;

the verification graph comprises a plurality of verification nodes;

the content nodes and content edges are stored as content of the verification nodes;

respective pairs of the verification nodes are connected by respective directed verification edges; and

the verification graph is configured to indicate tampering with any of a plurality of records stored in the verification graph;

returning, with one or more processors, a first identifier of the first root content node to the computing entity, wherein the first identifier identifies a verification node of the verification graph storing the first root content node;

receiving a request to read the record from persistent storage, the request indicating the first identifier of the root content node; and

traversing the content graph from the first root content node to retrieve every content node of the content graph from the verification graph, wherein at least some of the content nodes are retrieved concurrently, wherein;

the verification graph includes a plurality cryptographic hash pointers;

read latency of the record from the verification graph scales at less than O(n) in big O notation, where n is a number of the segments.

20. The method of claim 19, wherein:

the first content graph includes a binary tree that accounts for at least half of the content nodes of the content graph.

21. The method of claim 20, wherein:

the first content graph is a balanced binary tree.

22. The method of claim 19, wherein:

the first content graph includes a skip list defined by content edges of the content graph.

23. The method of claim 19, wherein:

the first content graph defines k-ary tree in which each content node of the k-ary tree has fewer k or fewer child content nodes, wherein k is 3 or larger.

24. The method of claim 23, wherein:

the first content graph includes three or more levels of hierarchy.

25. The method of claim 23, wherein:

at least half of the content nodes of the k-ary tree have 2 or more child nodes.

26. The method of claim 23, wherein arranging the first plurality of segments in the first content graph comprises iteratively, in a plurality of iterations, executing operations comprising:

obtaining a set of the first plurality of segments to be arranged;

determining a size of the set;

selecting 1/k of the size of the set from the set to form a selected subset;

arranging the selected subset in a current level of a hierarchy of the first content graph;

removing the subset from the set of the first plurality of segments to be arranged; and

designating a next level higher than the current level of the hierarchy as the current level.

27. The method of claim 26, wherein:

the subset is a sequential collection of segments of the record;

the subset precedes unselected members of the set in the record; and

a last segment of the record is stored in the first root content node.

28. The method of claim 19, wherein:

the first content graph comprises means for storing segmented data to facilitate concurrent retrieval.

29. The method of claim 19, wherein:

the record is a file;

the first identifier distinguishes the first root content node from other content nodes of the first content graph; and

the request is a request to write the file to persistent storage from a security driver of an operating system of a user computing device.

30. The method of claim 19, comprising:

receiving a second request to store a revised version of the record from the computing entity, the second request being associated with the first identifier of the first root content node;

encoding the revised version of the record in a second plurality of revised segments, wherein a first subset of the revised segments are identical to corresponding ones of the first plurality of segments and a second subset of the revised segments are different from corresponding ones of the first plurality of segments;

arranging the second subset of segments in a second content graph that partially overlaps the first content graph, wherein;

the overlap includes at least some content nodes storing respective segments of the first subset previously stored in the verification graph;

the second content graph includes a second root content node;

the second content graph does not include the first root content node;

both content nodes storing the second subset of segments and the at least some content nodes storing respective segments of the first subset are reachable in the second content graph from the second root node; and

content nodes storing the second subset of segments are not reachable from the first root content node of the first content graph;

storing the second subset in the verification graph without re-writing the at least some content nodes storing respective segments of the first subset to the verification graph; and

returning a second identifier of the second root content node to the computing entity.

31. The method of claim 30, comprising:

identifying the second subset by comparing respective cryptographic hashes of the segments and revised segments without retrieving the record from storage in the verification graph.

32. The method of claim 19, wherein:

the directed verification edges correspond to cryptographic hash pointers based on content of respective verification nodes to which respective cryptographic hash pointers point; and

content of verification nodes includes respective cryptographic hash values of respective cryptographic hash pointers of respective edges of respective verification nodes.

33. The method of claim 19, wherein:

the verification graph includes a plurality of directed acyclic graphs of the cryptographic hash pointers; and

different portions of the content graph are stored as content of verification nodes of the different directed acyclic graphs of cryptographic hash pointer.

34. The method of claim 19, wherein:

encoding the record in a first plurality of segments comprises partitioning a bitstream of a file into the plurality of segments; and

the segments are respective subsequences of the bitstream.

35. The method of claim 19, wherein:

encoding the record in the first plurality of segments comprises applying linear coding to the record.

36. The method of claim 19, wherein:

traversing the content graph comprises performing a breadth first traversal of the content graph.