為什麼使用雜湊樹而不是使用單個雜湊值？
如果有文件 $ x_1, x_2, .., x_n $ . 使用雜湊樹有什麼好處 $ - $ 也稱為默克爾樹 $ - $ （例如在 git 中）而不是計算一個雜湊值 $ h(x_1,x_2,..,x_n) $ ?
Merkle 樹用於在網路上有效檢索或發送數據，您可以按任何訂單發送/檢索數據，並使用額外的驗證目前數據 $ O(\log n) $ - 數據傳輸和輸入 $ O(\log n) $ -時間。實際上，只儲存了根雜湊 $ O(1) $ . 在保持根雜湊的同時，對檢索/發送的任何數據進行驗證。
$$ \begin{array}{lcr} & \text{With Merkle Tree } & \ \hline \text{receiver} & \text{data transmit } & \text{Databank} \ \hline \text{keeps the root hash} & & \text{keeps the files}\ O(1)\text{-space} & & \ & \xrightarrow{\text{request the ith file }} & \ & \xleftarrow{\text{sends ith file with the }O(\log n) \text{ siblings to the root hash}}\ \text{Verification in} & & \ O(\log n)\text{- time} & & \end{array} $$
上圖表明您是數據的所有者並將其外包。如果客戶端想要上傳數據，首先他們可以將數字簽名的根雜湊傳輸到圖表繼續的伺服器。
如果您使用一個雜湊，那麼要驗證您需要發送/接收所有數據併計算整個雜湊 $ O(n) $ - 數據傳輸和輸入 $ O(n) $ -時間。還有並行散列，如 SHA3 或 Blake3 的 ParallelHash。這可以減少散列時間 $ h(x_1,x_2,..,x_n) $ 如果您有多個核心/執行緒。理論上，這是 $ O(\log n) $ ，然而，在實踐中，它可能不會。不過，要驗證，需要一次全部轉移，即 $ O(n) $ - 數據傳輸。
$$ \begin{array}{lcr} & \text{With Single Hash } & \ \hline \text{receiver} & \text{data transmit } & \text{Databank} \ \hline \text{keep hash} & & \text{keeps the files}\ O(1)\text{-space} & & \ & \xrightarrow{\text{request the ith file }} & \ & \xleftarrow{\text{sends all files } O( n) \text{-data transmit}}\ \text{Verification in} & & \ O(n)\text{- time} & & \end{array} $$
因此，好處是減少了散列時間並減少了數據傳輸。