Storing differentials of files in a distributed blockchain

Patent metadata

Field	Value
Publication number	US-10121019-B2
Application number	US-201715675519-A
Country	US
Kind code	B2
Filing date	Aug 11, 2017
Priority date	Jun 2, 2015
Publication date	Nov 6, 2018
Grant date	Nov 6, 2018

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.

First claim

What is claimed is:

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

Assignees

• Altr Solutions Inc

Inventors

• Struttmann Christopher Edward

Classifications

• G06F17/30309

  Physics · mapped topic

• G06F17/30339

  Physics · mapped topic

• G06F21/6218 Primary

  to a system of files or objects, e.g. local or distributed file system or database · CPC title

• H04L9/0618

  Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation · CPC title

• H04L9/3236

  using cryptographic hash functions · CPC title