Patent ID: 8082236

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; storing the plurality of data blocks of the integrity hierarchy in respective first locations in a storage medium; receiving a modification to be made in the data stored in a given data block within the integrity hierarchy; in response to the modification, recomputing one or more of the signatures in the integrity hierarchy, including the top-level signature; storing, in respective second locations in the storage medium, copies of the given data block in which the modification has been made and copies of the signature blocks containing the signatures that have been recomputed, including a copy of the top-level block; recording, in the copy of the top-level block, pointers to the respective second locations of the given data block and the signature blocks containing the signatures that have been recomputed, 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.