Dynamic Hash
Dynamisches Hashing aktualisiert einen Digest effizient beim Einfügen und Löschen von Elementen und bewahrt so die Integrität dynamischer Mengen.
Zweck
Einen Hash-Digest über dynamischen Datensätzen (Elemente können hinzukommen oder entfallen) pflegen, wobei jedes Update O(1) oder O(log n) kostet.
Mechanismus
Entweder basierend auf homomorphem Hashing (multiplikatives Hash H(S)=∏ H(e_i) mod p) mit Einfügen (Multiplikation) und Löschen (Division); oder auf Merkle-Bäumen mit lokalen Updates nach Einfügungen und Löschungen.
Anwendungsfälle
- Integrität dynamischer Mengen
- State-Roots in Blockchains
- Digests mutabler Datenbanken