On-disk file format for serverless distributed file system with signed manifest of file modifications

• US 7,478,243 B2
• Filed: 03/21/2001
• Issued: 01/13/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
• Primary Examiner(s): Vu; Kim
• Assistant Examiner(s): GYORFI, THOMAS A
• Application Number:
  US09/814,337
• Publication Number:
  US 20020194484A1
• Time in Patent Office: 2,855 Days
• Field of Search: 713/181, 713/189, 713/176, 707/200, 707/203, 717169-170
• US Class Current: 713/181
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 2221/2101 Auditing as a secondary aspect
• 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 2209/80 Wireless
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

In a serverless distributed file system, the writer of a file can provide file authentication information to a verifying machine without having to compute a new digital signature every time a written file is closed. Periodically, the writer compiles a list of the hash values of all files that have been written over a recent interval, computes a hash of the list, and signs the hash. This signed list of hash values is known as a manifest, akin to a shipping manifest that enumerates the items in a shipment. The advantage of using a signed manifest is that the writer need only perform a single signature computation in order to authenticate the writes to multiple files, rather than having to compute a separate signature for each file, as it would if a signature were embedded in each file.

Claims

1. In a distributed file system that stores encrypted files across multiple computers, a method comprising:

modifying one or more of the encrypted files;

computing a hash value of each modified encrypted file, one or more of the modified encrypted files comprising file data and a metadata stream that comprises a header and an indexing structure, the indexing structure comprising one or more hashes of the file and a structure to access the one or more hashes of the file;

collecting the hash values into a group;

computing a hash value of the group; and

digitally signing the hash value of the group of hash values.

2. A method as recited in claim 1, wherein the computing a hash value of each modified encrypted file further comprises deriving a hash of the header and at least part of the structure.

3. A method as recited in claim 1, wherein the metadata stream further comprises per user information and the indexing structure comprises an indexing tree, the indexing tree including the one or more hashes of the file, branch nodes to access the one or more hashes, and a root node, the computing a hash value of each modified encrypted file further comprising hashing as a single composite the header, the per user information, and the root node.

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

5. One or more computer readable storage media comprising computer-executable instructions that, when executed, direct a computing device to:

modify individual files stored in a serverless distributed file system;

divide one or more of the files into a plurality of data blocks;

compute a hash value of each of the data blocks, one or more of the modified files comprising file data that includes the data blocks and a metadata stream that comprises a header and an indexing structure, the indexing structure comprising one or more hashes of the data blocks and a structure to access the one or more hashes of the data blocks;

collect the hash values into a group; and

digitally signing the group of hash values.

6. One or more computer readable storage media as recited in claim 5, wherein the storage media further comprises computer-executable instructions that, when executed, direct a computing device to derive a hash of the header and at least part of the structure.

7. One or more computer readable storage media as recited in claim 5, wherein the metadata stream further comprises per user information and the indexing structure comprises an indexing tree, the indexing tree comprising the one or more hashes of the data blocks, branch nodes to access the one or more hashes, and a root node, the storage media further comprising computer-executable instructions that, when executed, direct a computing device to hash as a single composite the header, the per user information, and the root node.