Hash
是否可以安全地組合多個散列而不散列它們?
假設我們有 1000 個文件和 1000 個已經為這些文件計算的加密雜湊。現在我們要派生一個單一的雜湊來驗證所有這些。有沒有比僅僅在不犧牲安全性的情況下對所有這些散列的串聯進行散列(從而大概呼叫散列輪函式大約 1000 次)更有效的方法?還要驗證序列怎麼樣?
您要查找的內容稱為Merkle 樹。BLAKE2b是一種現代散列,是 SHA-3 決賽入圍者之一 (BLAKE) 的演變,本機支持樹散列。
編輯:這實際上可能是也可能不是您正在尋找的東西。最初散列樹將需要更多的工作( $ \mathcal{O}(n\log(n)) $ 操作)而不僅僅是散列散列集,但後續的部分更新將花費更少的工作( $ \mathcal{O}(\log(n)) $ 操作)。如果您要更新列表,Merkle 樹可能更有效。
如果文件的數量是固定的,那麼連接散列(以明確定義的順序)構成散列函式。反轉它需要反轉其中一個文件的散列,因此如果每個文件的散列函式是加密散列,那麼 1000 個文件的散列也是如此。
如果文件的數量是可變的,那麼組合散列的自然方法就是對它們進行散列。這是一個非常便宜的操作,我不明白你為什麼希望找到更便宜的東西。畢竟你必須處理所有的雜湊,這是一個 $ \Omega(k) $ 操作在哪裡 $ k $ 是文件的數量。