Patent ID: 8606764

Claim:
A method for data integrity protection, comprising: arranging in an integrity hierarchy a plurality of data blocks, which contain data, the integrity hierarchy including multiple levels of signature blocks containing signatures computed respectively over lower levels in the hierarchy, wherein the levels culminate in a top-level block that contains a top-level signature computed over all of the hierarchy; and in response to a modification of data stored in a given data block within the integrity hierarchy: recording, in a copy of the top-level block, pointers to locations of the given data block and signature blocks containing signatures in the integrity hierarchy that have been recomputed based on the modification of data stored in the given data block, including the top-level signature, wherein the pointers comprise a list of the data blocks and the signature blocks in the lower levels of the hierarchy of which valid copies are stored in the second location; and recording in the copy of the top-level block an indication that the copy is a valid version of the top-level block; receiving a subsequent modification to the data after recording the copy of the top-level block; and in response to the subsequent modification, performing a recomputation of the signatures in the hierarchy, including the top-level signature, and storing a subsequent copy of the top-level block in the storage medium with an indication that the subsequent copy is the valid version of the top-level block.