Storing differentials of files in a distributed blockchain

• US 10,121,019 B2
• Filed: 08/11/2017
• Issued: 11/06/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,519
• Publication Number:
  US 20170364701A1
• Time in Patent Office: 452 Days
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• 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/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/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/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Provided is a process including: receiving a request to write a new version of a document to a tamper-evident, immutable data repository; determining that the new version of the document is different from the previous version of the document; and in response to determining, storing a difference between the previous version of the document and the new version of the document in the tamper-evident, immutable data repository.

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 request to write a new version of a document to a tamper-evident, immutable data repository, wherein;

the tamper-evident, immutable data repository stores a previous version of the document;

the tamper-evident, immutable data repository stores a plurality of versions of a plurality of other documents; and

the tamper-evident, immutable data repository stores versions of the document and the other documents in a data structure that renders previously stored versions of documents computationally infeasible to modify without making the data structure verifiably internally inconsistent;

after receiving the request, determining, with one or more processors, that the new version of the document is different from the previous version of the document; and

in response to determining that the new version of the document is different from the previous version of the document, storing, with one or more processors, a difference between the previous version of the document and the new version of the document by;

obtaining the previous version of the document from the tamper-evident, immutable data repository;

determining a set of changes that, when made to the previous version of the document, transform the previous version of the document into the new version of the document by comparing the new version of the document to the previous version of the document;

storing the set of changes in the tamper-evident, immutable data repository without storing a full copy of the new version of the document in the tamper-evident, immutable data repository; and

storing a pointer to the previous version of the document in association with the set of changes, the pointer directly or indirectly indicating wherein in the tamper-evident, immutable data repository to obtain the previous version of the document, the previous version being an initial version or a set of differences,

wherein;

the tamper-evident, immutable data repository comprises a plurality of directed acyclic graphs having edges defined by cryptographic hash pointers based on versions of documents stored in the tamper-evident, immutable data repository;

determining that at least part of the new version of the document is different from a previous version of the document comprises;

calculating a hash digest of at least part of the new version of the document;

accessing a hash digest of at least part of the previous version of the document stored outside of the tamper-evident, immutable data repository; and

determining that the hash digest of at least part of the new version of the document is different from the hash digest of at least part of the previous version of the document, wherein the new version of the document is determined to be different from the previous version of the document before retrieving the previous version of the document from the tamper-evident, immutable data repository responsive to the write request;

obtaining the previous version of the document comprises;

retrieving a previous difference between the previous version of the document and another version of the document previous to the previous version, the previous difference including another set of changes that transform the other version of the document previous to the previous version into the previous version of the document;

accessing a pointer associated with the previous difference, the pointer identifying a location of a copy of the other version of the document previous to the previous version in the tamper-evident, immutable data repository;

retrieving the other version of the document previous to the previous version with the pointer; and

applying the other set of changes to the retrieved other version of the document to form the previous version of the document;

obtaining the previous version of the document comprises;

iteratively, in three or more iterations, through three or more previous version of the document, sequentially applying previous sets of changes, retrieving versions starting from a most recent version until reaching an initial version and then combining the versions starting from the initial version of the document until reaching the previous version to form the previous version;

the three or more previous versions form a version graph for the document that contains a sequence of sets of changes to the document between writes to the tamper-evident, immutable data repository;

one of the three or more previous versions of the document branches into a different document based on the one of the three or more previous versions of the document; and

after writing, two current versions of documents in the tamper-evident, immutable data repository share overlapping subsets of previous versions.

2. The medium of claim 1, wherein:

receiving the request to write the new version of the document comprises receiving a request from a workload application executing in an operating system on a computing device to a filesystem driver executing on the computing device;

the tamper-evident, immutable data repository is not stored on the computing device;

a file system of the computing device includes pointers to documents stored in the tamper-evident, immutable data repository;

the pointers are arranged in a hierarchical directory data structure;

the pointers appear to be files in a filesystem explorer workload application executing on the computing device;

the pointers are labeled with filesystem file names of documents; and

one of the pointers references the previous version of the document in the tamper-evident, immutable data repository and is labeled in the file system with a filesystem file names name of the document.

3. The medium of claim 1, wherein:

the tamper-evident, immutable data repository comprises a blockchain.

4. The medium of claim 1, wherein:

a version graph of the document is stored in a verification graph of the tamper-evident, immutable data repository, wherein version nodes of the version graph correspond to sets of changes between consecutive writes to the tamper-evident, immutable data repository and edges of the version graph indicate a sequence of the sets changes.

5. The medium of claim 4, wherein:

a node of the version graph of the document has a plurality of changes stored in a plurality of segments stored in nodes of a content graph distributed among a plurality of verification graphs of the tamper-evident, immutable data repository.

6. The medium of claim 1, wherein determining the set of changes comprises:

determining a minimal set of changes required to transform the previous version of the document into the new version of the document.

7. The medium of claim 6, wherein the set of changes consists essentially of deleting, changing, and appending operations.

8. The medium of claim 1, wherein determining the set of changes comprises:

hashing each line of each of the new version of the document and the previous version of the document into respective hash digests that are 4 bytes or less and comparing the hash digests to identify lines that have changed.

9. The medium of claim 1, wherein determining the set of changes comprises:

finding a longest common sequence between the new version of the document and the previous version of the document.

10. The medium of claim 1, wherein the operations comprise reading the new version of the document from the tamper-evident, immutable data repository by:

retrieving an initial version of the document by tracing back from a newest version by retrieving each of a sequence of sets of changes from the tamper-evident log along a linked list of the sets of changes; and

sequentially applying the changes,

wherein;

the data repository stores more than 100,000 documents and more than 100 GB of data;

the document is retrieved in less than 200 milliseconds in an operation that scales in latency proportional to, or faster than, nlog(n), where n is a number of versions of documents in the tamper-evident, immutable data repository; and

the read request or the write request is logged in the tamper-evident, immutable data repository or another tamper-evident, immutable data repository.

11. The medium of claim 1 wherein the operations comprise:

steps for storing a log of changes to a document in a tamper-evident, immutable data repository.

12. The medium of claim 1, wherein the operations comprise:

steps for securing data.

13. The medium of claim 1, wherein the operations comprise:

executing a workload application issuing the write request within a computing device on an enterprise network configured to access a plurality of enterprise workload applications.

14. A method, comprising:

receiving, with one or more processors, a request to write a new version of a document to a tamper-evident, immutable data repository, wherein;

the tamper-evident, immutable data repository stores a previous version of the document;

the tamper-evident, immutable data repository stores a plurality of versions of a plurality of other documents; and

the tamper-evident, immutable data repository stores versions of the document and the other documents in a data structure that renders previously stored versions of documents computationally infeasible to modify without making the data structure verifiably internally inconsistent;

after receiving the request, determining, with one or more processors, that the new version of the document is different from the previous version of the document; and

in response to determining that the new version of the document is different from the previous version of the document, storing, with one or more processors, a difference between the previous version of the document and the new version of the document by;

obtaining the previous version of the document from the tamper-evident, immutable data repository;

determining a set of changes that, when made to the previous version of the document, transform the previous version of the document into the new version of the document by comparing the new version of the document to the previous version of the document;

storing the set of changes in the tamper-evident, immutable data repository without storing a full copy of the new version of the document in the tamper-evident, immutable data repository; and

storing a pointer to the previous version of the document in association with the set of changes, the pointer directly or indirectly indicating wherein in the tamper-evident, immutable data repository to obtain the previous version of the document, the previous version being an initial version or a set of differences,

wherein;

the tamper-evident, immutable data repository comprises a plurality of directed acyclic graphs having edges defined by cryptographic hash pointers based on versions of documents stored in the tamper-evident, immutable data repository;

determining that at least part of the new version of the document is different from a previous version of the document comprises;

calculating a hash digest of at least part of the new version of the document;

accessing a hash digest of at least part of the previous version of the document stored outside of the tamper-evident, immutable data repository; and

determining that the hash digest of at least part of the new version of the document is different from the hash digest of at least part of the previous version of the document, wherein the new version of the document is determined to be different from the previous version of the document before retrieving the previous version of the document from the tamper-evident, immutable data repository responsive to the write request;

obtaining the previous version of the document comprises;

retrieving a previous difference between the previous version of the document and another version of the document previous to the previous version, the previous difference including another set of changes that transform the other version of the document previous to the previous version into the previous version of the document;

accessing a pointer associated with the previous difference, the pointer identifying a location of a copy of the other version of the document previous to the previous version in the tamper-evident, immutable data repository;

retrieving the other version of the document previous to the previous version with the pointer; and

applying the other set of changes to the retrieved other version of the document to form the previous version of the document;

obtaining the previous version of the document comprises;

iteratively, in three or more iterations, through three or more previous version of the document, sequentially applying previous sets of changes, retrieving versions starting from a most recent version until reaching an initial version and then combining the versions starting from the initial version of the document until reaching the previous version to form the previous version;

the three or more previous versions form a version graph for the document that contains a sequence of sets of changes to the document between writes to the tamper-evident, immutable data repository;

one of the three or more previous versions of the document branches into a different document based on the one of the three or more previous versions of the document; and

after writing, two current versions of documents in the tamper-evident, immutable data repository share overlapping subsets of previous versions.

15. The method of claim 14, wherein:

receiving the request to write the new version of the document comprises receiving a request from a workload application executing in an operating system on a computing device to a filesystem driver executing on the computing device;

the tamper-evident, immutable data repository is not stored on the computing device;

a file system of the computing device includes pointers to documents stored in the tamper-evident, immutable data repository;

the pointers are arranged in a hierarchical directory data structure;

the pointers appear to be files in a filesystem explorer workload application executing on the computing device;

the pointers are labeled with filesystem file names of documents; and

one of the pointers references the previous version of the document in the tamper-evident, immutable data repository and is labeled in the file system with a filesystem file names name of the document.

16. The method of claim 14, wherein:

the tamper-evident, immutable data repository comprises a blockchain.

17. The method of claim 14, wherein:

a version graph of the document is stored in a verification graph of the tamper-evident, immutable data repository, wherein version nodes of the version graph correspond to sets of changes between consecutive writes to the tamper-evident, immutable data repository and edges of the version graph indicate a sequence of the sets changes.

18. The method of claim 17, wherein:

a node of the version graph of the document has a plurality of changes stored in a plurality of segments stored in nodes of a content graph distributed among a plurality of verification graphs of the tamper-evident, immutable data repository.

19. The method of claim 14, wherein determining the set of changes comprises:

determining a minimal set of changes required to transform the previous version of the document into the new version of the document.

20. The method of claim 19, wherein the set of changes consists essentially of deleting, changing, and appending operations.

21. The method of claim 14, wherein determining the set of changes comprises:

hashing each line of each of the new version of the document and the previous version of the document into respective hash digests that are 4 bytes or less and comparing the hash digests to identify lines that have changed.

22. The method of claim 14, wherein determining the set of changes comprises:

finding a longest common sequence between the new version of the document and the previous version of the document.

23. The method of claim 14, comprising reading the new version of the document from the tamper-evident, immutable data repository by:

retrieving an initial version of the document by tracing back from a newest version by retrieving each of a sequence of sets of changes from the tamper-evident log along a linked list of the sets of changes; and

sequentially applying the changes,

wherein;

the data repository stores more than 100,000 documents and more than 100 GB of data;

the document is retrieved in less than 200 milliseconds in an operation that scales in latency proportional to, or faster than, n log(n), where n is a number of versions of documents in the tamper-evident, immutable data repository; and

the read request or the write request is logged in the tamper-evident, immutable data repository or another tamper-evident, immutable data repository.

24. The method of claim 14, comprising:

steps for storing a log of changes to a document in a tamper-evident, immutable data repository.

25. The method of claim 14, comprising:

steps for securing data.

26. The method of claim 14, comprising:

executing a workload application issuing the write request within a computing device on an enterprise network configured to access a plurality of enterprise workload applications.