On-disk file format for a serverless distributed file system

• US 20050108240A1
• Filed: 12/16/2004
• Published: 05/19/2005
• Est. Priority Date: 03/21/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bolosky, William J., Douceur, John R., Adya, Atul, Cermak, Gerald
• Granted Patent: US 7,401,220 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/0656 Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher
• 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/3249 using RSA or related signature schemes, e.g. Rabin scheme
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A file format for a serverless distributed file system is composed of two parts: a primary data stream and a metadata stream. The data stream contains a file that is divided into multiple blocks. Each block is encrypted using a hash of the block as the encryption key. The metadata stream contains a header, a structure for indexing the encrypted blocks in the primary data stream, and some user information. The indexing structure defines leaf nodes for each of the blocks. Each leaf node consists of an access value used for decryption of the associated block and a verification value used to verify the encrypted block independently of other blocks. In one implementation, the access value is formed by hashing the file block and encrypting the resultant hash value using a randomly generated key. The key is then encrypted using the user'"'"'s key as the encryption key. The verification value is formed by hashing the associated encrypted block using a one-way hash function. The file format supports verification of individual file blocks without knowledge of the randomly generated key or any user keys. To verify a block of the file, the file system traverses the tree to the appropriate leaf node associated with a target block to be verified. The file system hashes the target block and if the hash matches the access value contained in the leaf node, the block is authentic.

Claims

1. A method comprising:

segmenting a file into multiple blocks;

computing hashes of each of the blocks to produce corresponding block hash values; and

encrypting the blocks using their corresponding block hash values as encryption keys to produce encrypted blocks.

2. A method as recited in claim 1, wherein the segmenting comprises dividing the file into equal size blocks.

3. A method as recited in claim 1, wherein the encrypting comprises encrypting each block using a symmetric cryptographic cipher and the corresponding block hash value as the symmetric encryption key.

4. A method as recited in claim 1, further comprising storing the encrypted blocks as a primary data stream.

5. A method as recited in claim 4, further comprising storing header information in a separate metadata stream.

6. A method as recited in claim 1, further comprising verifying an authenticity of the encrypted blocks independently of one another.

7. A method as recited in claim 1, further comprising modifying content of a block in the file independent of other blocks.

8. A method as recited in claim 1, further comprising constructing an indexing structure to index individual encrypted blocks.

9. A method as recited in claim 8, wherein the constructing comprises creating a leaf node for each corresponding encrypted block, the leaf node containing an access value used to decrypt the corresponding encrypted block and a verification value used to verify the corresponding encrypted block.

10. A method as recited in claim 9, wherein the constructing further comprises hashing an array of the leaf nodes to produce a root.

11. A method as recited in claim 10, wherein the constructing further comprising digitally signing at least the root.

12. A method as recited in claim 10, further comprising:

storing the root together with header information and per user information; and

digitally signing a composite including the root, the header information, and the per user information.

13. A method as recited in claim 9, wherein the constructing further comprises:

grouping leaf nodes into multiple groups;

hashing each group of leaf nodes to form intermediate nodes; and

hashing an array of the intermediate nodes to produce a root.

14. A method as recited in claim 13, wherein the constructing further comprises digitally signing at least the root.

15. A method as recited in claim 1, further comprising digitally signing at least a portion of the file.

16. A method as recited in claim 1, further comprising generating a delegation certificate that grants other entities permission to collectively authenticate the file in absence of the signature of a last writer to the file.

17. A method as recited in claim 1, wherein the file comprises a sparse file.

18. A method as recited in claim 1, further comprising:

encrypting the block hash values with one or more access keys; and

encrypting the one or more access keys using one or more keys of users who are granted access to the file.

19. A method as recited in claim 18, wherein the one or more keys of users comprise one or more public keys.

20. A data structure, embodied on a computer-readable medium, produced by the method of claim 1.

21. One or more computer readable media comprising computer-executable instructions that, when executed, perform the method as recited in claim 1.

22. A distributed file system comprising:

a client component resident at a first computer to facilitate creation of a file by segmenting the file into multiple blocks and encrypting each block using its own hash value as an encryption key; and

a server component resident at a second computer to store the encrypted file.

23. A distributed file system as recited in claim 22, wherein the client component divides the file into equal size blocks.

24. A distributed file system as recited in claim 22, wherein the encrypted blocks are stored as a primary data stream.

25. A distributed file system as recited in claim 24, wherein the client component creates header information that is stored as a separate metadata stream.

26. A distributed file system as recited in claim 22, wherein the client component verifies an authenticity of the encrypted blocks independently of one another.

27. A distributed file system as recited in claim 22, wherein the client component modifies content of a block in the file independent of other blocks.

28. A distributed file system as recited in claim 22, wherein the client component digitally signs the file.