On-disk file format for a serverless distributed file system

• US 20050097313A1
• Filed: 12/16/2004
• Published: 05/05/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,415,608 B2
• Time in Patent Office: Days
• US Class Current: 713/150
• 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:

creating a primary data stream containing an encrypted file that is encrypted using at least one hash of some contents of the file; and

creating a metadata stream containing information pertaining to the encrypted file, the information including decryption capabilities used to decrypt the file and verification capabilities used to verify portions of the file without access to decryption keys.

2. A distributed file system comprising:

means for creating a primary data stream containing an encrypted file that is encrypted using at least one hash of some contents of the file; and

means for creating a metadata stream containing information pertaining to the encrypted file, the information including decryption capabilities used to decrypt the file and verification capabilities used to verify the file.

3. A distributed file system as recited in claim 2, wherein the file in the primary stream comprises multiple encrypted blocks, where each block is hashed and encrypted using a hash value of the block as an encryption key.

4. A distributed file system as recited in claim 2, wherein the means for creating the metadata stream comprises means for constructing leaf nodes for corresponding blocks, the leaf nodes containing an access value used to decrypt the corresponding encrypted block and a verification value used to verify the corresponding encrypted block.

5. A data structure stored on a computer-readable medium, comprising:

a primary data stream containing an encrypted file composed of multiple encrypted blocks, each block being separately encrypted by a symmetric cipher that uses a hash of the block as an encryption key;

a metadata stream containing information pertaining to the encrypted file.

6. A data structure as recited in claim 5, wherein information includes decryption capabilities used to decrypt the file.

7. A data structure as recited in claim 5, wherein information includes verification capabilities used to verify the file.

8. A data structure as recited in claim 5, wherein the metadata stream comprises:

a header with one or more fields that describe the encrypted file; and

an indexing structure to index individual encrypted blocks.