# Cryptographic hash that supports efficient update after random-access plaintext modification

Is there a cryptographic hash algorithm that, given the hash of a plaintext, supports supports efficient recomputation of the hash after modifying a single byte of the plaintext?

Specifically, is there a hash function H() such that, given plaintext P and Q of the same length that differ only in the byte at position K, there exists another function R() such that R(P, Q, K, H(P)) = H(Q) and R is O(1)? If so, what are H and R?

Such a function would be interesting because it would allow creating a filesystem that efficiently tracks a cryptographic hash for each of its files. Such a filesystem could be useful for implementing highly efficient file transfer (like rsync) or version control (like git) systems.

• Would a universal hash function family be acceptable? Many of those can be efficiently updated when the input changes, but the catch is that they're only "secure" (for any halfway sensible definition of the word) against adversaries who don't know the key used to select the particular hash function from the universal family. – Ilmari Karonen Jul 16 at 13:40
• @IlmariKaronen I don't think this is relevant for the use-case I have in mind (a filesystem that tracks cryptographic hashes of its files). Since the key would be public (part of the filesystem implementation), the hash would not provide cryptographic security. – Kerrick Staley Jul 16 at 20:06

I don't have a proof, but I don't think an $$O(1)$$ R is possible. That would make it very easy to calculate the hash of a changed input, and while this wouldn't contradict any defining property of a hash, it would make the hash weak for constructs like key derivation. So it would have to be a pretty unusual hash.
The standard solution is hash trees, also known as Merkle trees. It's an old technique, older than all modern hash functions, but still very much relevant for filesystems with integrity checks. Hash trees give you an R function with $$O(n)$$ extra storage and $$O(\log n)$$ calculation time and data transfer to make an update. The idea is to divide the data into blocks and to maintain a tree whose leaves are the data blocks and whose inner nodes contain hashes of their children. Whenever a block is updated, you only need to update the path from that block to the root of the tree.