大型 Merkle 樹的高效增量更新
我有一個包含 3 億個條目的數據集，每 5 分鐘就有 4000 個隨機條目在此表中更改。我需要在這個數據集上計算 merkle 根，以每 5 分鐘多次驗證完整性。
假設 sha224 散列，這對於葉節點將是 8 GB，並且幾乎 16 GB 的數據必須通過 sha224 處理以計算根，並且需要超過 5 分鐘的時間來計算。為了加速計算，我必須記憶體樹並進行增量更新。
是否有任何已知的方法來加速增量更新而不需要 16 GB 記憶體映射的默克爾樹？
是的，您應該能夠輕鬆處理這種情況。有許多優化可用。
一個關鍵的觀察結果是，如果您要訪問磁碟，那麼您不妨讀取大量數據：讀取整個數據塊所需的時間與讀取 1 個字節的時間一樣長。因此，我建議您將數據以 4096 字節的塊儲存在磁碟上，並在這些塊上創建 Merkle 樹。特別是，每個 4096 字節塊將有一個葉子。然後您可以將 Merkle 樹儲存在記憶體中。
其次，不需要使用 SHA224。160 位散列就足夠了，因此您可以使用截斷為 160 位的 SHA1（或 SHA224/SHA256）。這樣，每個散列將有 20 個字節長。
這將如何表現？磁碟上每個 4096 字節的塊可以儲存大約 200 個雜湊值。因此，您將擁有大約 150 萬個區塊。將每個塊的雜湊視為葉子，我們有一個有 150 萬個葉子的 Merkle 樹。這樣的 Merkle 樹總共有 300 萬個節點，您只需使用 60 MB 的 RAM 就可以將它們儲存在記憶體中。
每 5 分鐘，將修改 4000 個隨機條目。這需要您從磁碟讀取 4000 個塊，更新它們，重新計算它們的雜湊值，並更新 Merkle 樹。要讀取 4000 個塊、更新它們並將它們寫回磁碟，將涉及讀取 16 MB 數據和寫入 16 MB 數據；沒問題。散列所有這些數據大約需要 40 毫秒，因為您可以在大約 10 微秒內散列一個 4096 字節的塊。然後，您需要更新 Merkle 樹中的大約 8000 個節點。這涉及在短輸入上計算 8000 個散列，這將需要大約 4 毫秒，因為短輸入的每個散列大約需要 0.5 微秒。總體而言，對您的系統的性能影響應該非常低。（這些數字在我碰巧放置的一台特定機器上，使用 SHA1。您的數字可能會因常數因子而變化，
總的來說，這個解決方案在記憶體消耗和 CPU 使用方面都應該表現得非常好。
如果您想擠出 RAM 的最後一個字節，還有其他可用的技巧。如果您使用具有更高分支因子的樹而不是二叉樹，則最多可以節省 2 倍的記憶體使用量（儘管這會花費您一點點 CPU 使用率）。
此外，如果您使用 UOWHF，您可以安全地將散列的大小截斷到大約 80 位（10 個字節）。一種方法是選擇一個秘密的 128 位密鑰 $ K $ ，然後是數據的雜湊 $ X $ 是 $ H(X || K) $ （即，追加 $ K $ 散列前的數據），截斷為 80 位。密鑰的使用 $ K $ （即，使用 UOWHF）消除了生日攻擊的機會，因此在這種情況下，80 位就足夠了。這可以為您節省 2 倍的記憶體使用量。