One embodiment of the present invention provides a system that facilitates detecting data tampering within a table in a database. The system operates by hashing a row in the table to create a row-hash. The system then hashes a block of consecutive row-hashes to create a block-hash. Finally, the system signs the block-hash with an encryption key, so that tampering with data in the row will result in an invalid row-hash and an invalid block-hash.