Dynamic Hash
Dynamic hashing supports efficiently updating a digest as elements are inserted into or deleted from a dataset, maintaining integrity of dynamic sets.
Purpose
Maintains a hash digest over dynamic datasets (elements can be added/removed), with each update costing O(1) or O(log n).
Mechanism
Based on homomorphic hashing (multiplicative hash H(S)=∏ H(e_i) mod p) supporting insertion (multiplication) and deletion (division); or based on Merkle trees supporting local updates after insertions/deletions.
Use cases
- Dynamic set integrity
- Blockchain state roots
- Mutable database digests