A method for data integrity protection includes arranging in an integrity hierarchy a plurality of data blocks, which contain data. The integrity hierarchy includes multiple levels of signature blocks containing signatures computed respectively over lower levels in the hierarchy, wherein the levels culminate in a top-level block containing a top-level signature computed over the hierarchy. A modification to be made in the data stored in a given data block is received. One or more of the signatures is recomputed in response to the modification, including the top-level signature. Copies of the given data block, and of the signature blocks, including a copy of the top-level block, are stored in respective locations in a storage medium. An indication that the copy is a valid version of the top-level block is recorded in the copy of the top-level block.