On-disk file format for a serverless distributed file system
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
105 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A method comprising:
-
segmenting a file into multiple blocks;
computing hashes of each of the blocks to produce corresponding block hash values;
encrypting the blocks using their corresponding block hash values as encryption keys to produce encrypted blocks;
storing the encrypted blocks as a primary data stream;
creating an indexing structure to index individual encrypted blocks, the indexing structure containing a leaf node for each corresponding encrypted block, the leaf node containing an access value formed by encrypting the block hash value for the corresponding encrypted block using an access key and a verification value formed by hashing the corresponding encrypted block;
storing the indexing structure in a separate metadata stream; and
encrypting the access key using a public key of a user who is granted access to the file. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 37, 38, 39)
-
-
35. 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.
-
-
36. A method comprising:
-
accessing a file composed of a data stream and a metadata stream, 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; and
verifying 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.
-
-
40. A method for reading a file stored in a 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 into the indexing structure to a leaf node associated with a target encrypted block;
decrypting the target encrypted block using the access value of the leaf node associated with the target encrypted block; and
reading the target encrypted block following said decrypting. - View Dependent Claims (41)
-
-
42. A method for writing to a file stored in a 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;
computing a hash value of the block;
encrypting the block using the hash value as an encryption key to produce an encrypted block; and
reconstructing a portion of the indexing structure that references the encrypted block. - View Dependent Claims (43, 44, 46, 47, 48, 49, 50)
-
-
45. A method comprising:
-
segmenting a sparse file into multiple blocks;
differentiating non-data blocks in the sparse file that contain no substantive content from data blocks in the sparse file that contain substantive data;
creating an indexing structure to index individual blocks; and
deallocating storage of the non-data blocks and portions of the indexing structure that reference the non-data blocks.
-
-
51. A method comprising:
-
segmenting a sparse file into multiple blocks, the sparse file containing at least one non-data block that contains no substantive data;
differentiating the non-data blocks from data blocks of the sparse file that contain substantive data;
computing hashes of each of the data blocks to produce block hash values;
encrypting the data blocks using their corresponding block hash values as encryption keys to produce encrypted data blocks;
creating an indexing structure to index individual blocks, the indexing structure containing first leaf nodes for each corresponding encrypted data block and second leaf nodes for each corresponding non-data block, the first leaf nodes containing an access value formed by encrypting the block hash value for the corresponding encrypted block using an access key and a verification value formed by hashing the corresponding encrypted block; and
setting the second leaf nodes to a first binary value. - View Dependent Claims (52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70)
-
-
56. One or more computer readable media comprising computer-executable instructions that, when executed, direct a computing device to:
-
segment a file into multiple blocks;
hash each of the blocks to produce block hash values;
encrypt the blocks using their corresponding block hash values as encryption keys to produce encrypted blocks;
create an indexing structure to index individual encrypted blocks, the indexing structure containing a leaf node for each corresponding encrypted block, the leaf node containing an access value formed by encrypting the block hash value for the corresponding encrypted block using an access key and a verification value formed by hashing the corresponding encrypted block;
encrypt the access key using a public key of a user who is granted access to the file.
-
-
69. 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 media comprising computer-executable instructions that, when executed, direct a computing device to:
-
traverse the indexing structure to a leaf node associated with a target encrypted block; and
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.
-
-
71. 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 media comprising computer-executable instructions that, when executed, direct a computing device to:
-
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; and
read the target encrypted block following said decrypting.
-
-
72. In a distributed file system that stores files across multiple computers, 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, one or more computer readable media comprising computer-executable instructions that, when executed, direct a computing device to:
-
modify a block of the file;
compute a hash value of the block;
encrypt the block using the hash value as an encryption key to produce an encrypted block; and
reconstruct a portion of the indexing structure that references the encrypted block.
-
-
73. One or more computer readable media comprising computer-executable instructions that, when executed, direct a computing device to:
-
segment a sparse file into multiple blocks, the sparse file containing at least one non-data block that contains no substantive data;
differentiate the non-data blocks from data blocks of the sparse file that contain substantive data;
compute hashes of each of the data blocks to produce block hash values;
encrypt the data blocks using their corresponding block hash values as encryption keys to produce encrypted data blocks;
creating an indexing structure to index the non-data blocks and the encrypted data blocks; and
deallocate portions of the indexing structure that reference the non-data blocks.
-
-
74. 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. - View Dependent Claims (75, 76, 77, 78, 79, 80)
-
-
81. A component in a distributed file system in which file are stored across multiple distributed computers, the component comprising:
-
a segmenting module to divide a file into multiple blocks;
a hash module to hash each of the blocks to produce block hash values;
a cryptographic engine to encrypt the blocks using their corresponding block hash values as encryption keys to produce encrypted blocks; and
an index builder to create an indexing structure for indexing individual encrypted blocks, the indexing structure containing a leaf node for each corresponding encrypted block, the leaf node containing an access value formed by encrypting the block hash value for the corresponding encrypted block using an access key and a verification value formed by hashing the corresponding encrypted block. - View Dependent Claims (82, 83, 84, 85, 86, 87, 88, 89, 90)
-
-
91. A component in a distributed file system in which files are stored across multiple distributed computers, the component comprising:
-
a segmenting module to divide a sparse file into multiple blocks, the sparse file containing at least one non-data block that contains no substantive data;
a control module to differentiate the non-data blocks from data blocks of the sparse file that contain substantive data;
a hash module to hash each of the data blocks to produce block hash values;
a cryptographic engine to encrypt the data blocks using their corresponding block hash values as encryption keys to produce encrypted blocks; and
an index builder to create an indexing structure to index individual blocks, the indexing structure containing first leaf nodes for each corresponding encrypted block and second leaf nodes for each corresponding non-data block, the first leaf nodes containing an access value formed by encrypting the block hash value for the corresponding encrypted block using an access key and a verification value formed by hashing the corresponding encrypted block, the second leaf nodes being set to a first binary value. - View Dependent Claims (92, 93)
-
-
94. 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. - View Dependent Claims (95, 96)
-
-
97. 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. - View Dependent Claims (98, 99, 100)
-
-
101. A data structure stored on a computer-readable medium, comprising:
-
multiple encrypted file blocks, each encrypted file block being encrypted by a symmetric cipher that uses a hash of the block as an encryption key; and
an indexing structure to index individual encrypted file blocks independently of other encrypted file blocks. - View Dependent Claims (102, 103, 104, 105)
-
Specification