Incremental Hash
Incremental hashing supports updating the digest in O(log n) time after a local data modification, without recomputing the hash of all data.
Purpose
Efficiently maintains integrity digests over frequently modified large data (e.g. file systems, databases).
Mechanism
Based on Merkle trees: after a leaf modification, only the O(log n) node hashes on the leaf-to-root path are updated. Or based on homomorphic hashing (e.g. MuHash) supporting incremental addition/removal of elements.
Use cases
- File system integrity
- Database auditing
- Version control digests