A method for data integrity protection includes arranging data in a plurality of data blocks. A respective block signature is computed over each of the data blocks, thereby generating multiple block signatures. The data blocks and the block signatures in an integrity hierarchy are stored in a storage medium, the hierarchy comprising multiple levels of signature blocks containing signatures computed over lower levels in the hierarchy, culminating in a top-level block containing a top-level signature computed over all of the hierarchy. A modification is made in the data stored in a given data block within the hierarchy. The respective block signature of the given data block is recomputed in response to the modification, and the recomputed block signature is stored in the top-level block for use in verifying a subsequent requests to read data from the given data block.