On-disk file format for a serverless distributed file system

• US 7,539,867 B2
• Filed: 12/16/2004
• Issued: 05/26/2009
• Est. Priority Date: 03/21/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bolosky, William J., Douceur, John R., Adya, Atul, Cermak, Gerald
• Primary Examiner(s): LAFORGIA, CHRISTIAN A
• Application Number:
  US11/014,317
• Publication Number:
  US 20050097077A1
• Time in Patent Office: 1,622 Days
• Field of Search: None
• US Class Current: 713/175
• 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:

accessing a file composed of a data stream and a metadata stream at a computing device of a serverless distributed file system, the data stream containing multiple encrypted blocks that are each encrypted using hashes of a plaintext version of the encrypted blocks, the metadata stream containing an indexing structure to index to the individual encrypted blocks, the indexing structure having a leaf node for each corresponding encrypted block that contains a verification value used to verify the corresponding encrypted block;

traversing the indexing structure to a leaf node associated with a target encrypted block at the computing device;

verifying, at the computing device, an authenticity of the target encrypted block independently of other encrypted blocks by using the verification value in the leaf node associated with the target encrypted block;

generating a delegation certificate at the computing device, wherein the computing device is associated with a writer of the file, and the delegation certificate allows one or more additional computing devices to verify as a group authenticity of the file when the computing device is unavailable to verify the authenticity of the file; and

signing the delegation certificate at the computing device with a private key of the writer of the file.

2. A method as recited in claim 1, wherein the indexing structure contains a root and zero or more intervening nodes between the root and the leaf nodes, the traversing further comprising verifying an authenticity of the root and any intervening nodes on a path from the root to the leaf node associated with the target encrypted block.

3. A method as recited in claim 1, wherein the indexing structure is at least partially digitally signed with a digital signature, the method further comprising evaluating an authenticity of the digital signature.

4. A method as recited in claim 1, wherein the verification value in the leaf node is a hash value of the target encrypted block, and the verifying comprises:

computing a current hash value of the target encrypted block; and

comparing the current hash value with the hash value in the leaf node.

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

compiling a list of hash values at the computing device, wherein each hash value of the list of hash values is related to a respective file that has been written within a specified period of time;

computing a hash of the list of hash values at the computing device; and

signing the hash of the list of hash values at the computing device.

6. A method for reading a file stored in a computing device of a serverless distributed file system, the file containing a data stream with multiple encrypted blocks and a metadata stream with an indexing structure to index the encrypted blocks individually, the indexing structure having a leaf node for each corresponding encrypted block that contains an access value used to decrypt the corresponding encrypted block, the method comprising:

indexing, at the computing device, into the indexing structure to a leaf node associated with a target encrypted block;

decrypting, at the computing device, the target encrypted block using the access value of the leaf node associated with the target encrypted block;

reading the target encrypted block following said decrypting at the computing device;

generating a delegation certificate at the computing device, wherein the computing device is associated with a writer of the file, and the delegation certificate allows one or more additional computing devices to verify as a group authenticity of the file when the computing device is unavailable to verify the authenticity of the file; and

signing the delegation certificate at the computing device with a private key of the writer of the file.

7. A method as recited in claim 6, wherein the access value in the leaf node is an encrypted version of symmetric key used to encrypt the file block, the symmetric key being generated by hashing the file block.

8. A method for writing to a file stored in a computing device of a serverless distributed file system, the file containing a data stream with multiple encrypted blocks and a metadata stream with an indexing structure to index to the encrypted blocks individually, the method comprising:

modifying a block of the file at the computing device;

computing a hash value of the block at the computing device;

encrypting the block at the computing device using the hash value as an encryption key to produce an encrypted block;

reconstructing, at the computing device, a portion of the indexing structure that references the encrypted block;

generating a delegation certificate at the computing device, wherein the computing device is associated with a writer of the file, and the delegation certificate allows one or more additional computing devices to verify as a group authenticity of the file when the computing device is unavailable to verify the authenticity of the file; and

signing the delegation certificate at the computing device with a private key of the writer of the file.

9. A method as recited in claim 8, wherein the modifying the block comprises writing data to the block.

10. A method as recited in claim 8, wherein the indexing structure includes a leaf node for each corresponding encrypted block, and the reconstructing comprises creating a new leaf node for the encrypted block, the new leaf node containing an encrypted version of the hash value and a hash of the encrypted block.

11. In a distributed file system that stores files across multiple computers, wherein each file contains a data stream with multiple encrypted blocks and a metadata stream with an indexing structure to index the encrypted blocks individually, the indexing structure having a leaf node for each corresponding encrypted block that contains a verification value used to verify the corresponding encrypted block, one or more computer readable storage media comprising computer-executable instructions that, when executed, direct a computing device to perform acts comprising:

traverse the indexing structure to a leaf node associated with a target encrypted block;

verify an authenticity of the target encrypted block independently of other encrypted blocks by using the verification value in the leaf node associated with the target encrypted block;

generate a delegation certificate to allow one or more additional computing devices to verify as a group authenticity of a file when a particular computing device associated with a writer of the file is unavailable to verify the authenticity of the file; and

sign the delegation certificate with a private key of the writer of the file.

12. One or more computer readable media as recited in claim 11, wherein the indexing structure contains a root and zero or more intervening nodes between the root and the leaf nodes, further comprising computer-executable instructions that, when executed, direct a computing device to verify an authenticity of the root and any intervening nodes on a path from the root to the leaf node associated with the target encrypted block.

13. In a distributed file system that stores files across multiple computers, wherein each file contains a data stream with multiple encrypted blocks and a metadata stream with an indexing structure to index the encrypted blocks individually, the indexing structure having a leaf node for each corresponding encrypted block that contains an access value used to decrypt the corresponding encrypted block, one or more computer readable storage media comprising computer-executable instructions that, when executed, direct a computing device to perform acts comprising:

index into the indexing structure to a leaf node associated with a target encrypted block;

decrypt the target encrypted block using the access value of the leaf node associated with the target encrypted block;

read the target encrypted block following said decrypting;

generate a delegation certificate to allow one or more additional computing devices to verify as a group authenticity of a file when a particular computing device associated with a writer of the file is unavailable to verify the authenticity of the file; and

sign the delegation certificate with a private key of the writer of the file.

14. In a distributed file system that stores files across multiple computers, each file containing a data stream with multiple encrypted blocks and a metadata stream with an indexing structure to index to the encrypted blocks individually, one or more computer readable storage media comprising computer-executable instructions that, when executed, direct a computing device to perform acts comprising:

modify a block of a file;

compute a hash value of the block;

encrypt the block using the hash value as an encryption key to produce an encrypted block;

reconstruct a portion of the indexing structure that references the encrypted block;

generate a delegation certificate to allow one or more additional computing devices to verify as a group authenticity of the file when a particular computing device associated with a writer of the file is unavailable to verify the authenticity of the file; and

sign the delegation certificate with a private key of the writer of the file.