Dynamic Hash
動的ハッシュは、データセットへの要素の挿入・削除に合わせてダイジェストを効率的に更新し、動的集合の完全性を維持する。
目的
要素の追加/削除が可能な動的データセット上でハッシュダイジェストを維持し、各更新を O(1) または O(log n) で行う。
メカニズム
挿入（乗算）と削除（除算）をサポートする準同型ハッシュ（乗法ハッシュ H(S)=∏ H(e_i) mod p）に基づく方法と、挿入/削除後の局所更新をサポートするマークルツリーに基づく方法がある。
ユースケース
- 動的セットの完全性
- ブロックチェーンのステートルート
- 可変データベースのダイジェスト