Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents?

Question

This question is about file-hashing/fingerprinting algorithms (similar to SHA-1 and MD5 and so on). Those algorithms are handy because they give you a small (and fixed-sized) hash code for any file, which can be later used to efficiently determine if that file is different from another file, and (if we are willing to ignore the unlikely possibility of hash-collisions) also whether two files are the same.

One small downside to computing the hash/fingerprint for a file is that you have to read the entire file in order to do so; if the file is very large (e.g. gigabytes or more) this can be an expensive operation.

A good way to avoid that expense is to compute the file's hash code as you are writing it to the disk, and store the hash code with the file. You can even resume updating the hash code later on, if/when you append more bytes to the end of the file, and (assuming no bugs or filesystem corruption) you'll have the file's fingerprint/hash cheaply available to you at all times.

However, the above "update as you go" approach seems like it may break down if you want to update the file in other ways besides appending -- in particular, if you want to truncate the file, or overwrite some existing bytes within the file with new values, you might have to then re-read the entire file in order to update the fingerprint/hash to the appropriate new value.

My question is, is there a type of hashing/fingerprinting algorithm that can efficiently handle file-truncation and byte-overwrite operations, and still provides reasonably good-quality hashing/fingerprinting? ("efficiently" in this case means that one could perform one of these operations on the file and then compute the correct new hash/fingerprint without having to re-read other parts of the file)

Answer 1

One way to achieve it is to keep a dynamic balanced tree augmented with hashes. This will give you logarithmic slowdown for overwrites and truncation, and also will work with any hashing algorithm.

Let the file be partitioned in blocks of fixed size, $H$ be a hash-function, and $h_t$ be a value stored in a node $t$. If $t$ is a leave, then $h_t$ is a hash of the corresponding block. If $r$ is a parent of $a$ and $b$, then $h_r = H[(h_a,h_b)]$.

Answer 2

There is a faster way than Dmitri's method. You can hash a length-$k$ sequence $f$ to $\sum_{i=1}^k h(i,f(i))$, where $h$ is any two-input hash function. This way, you can update the hash of a file even if you only know the part of the file that has been changed. Such a hashing technique is good enough in the sense that changing or rearranging terms in the sequence at random will almost surely result in a different hash. However, it would not be cryptographically secure since each term in the sequence contributes independently to the sum and it may be possible to engineer a collision without too much work.