什麼是默克爾樹？
Merkle 樹的概念是由 Ralph Merkle 在 20 世紀 80 年代初提出的，他是一位以公鑰密碼學研究而聞名的計算機科學家。
Merkle Tree 是一種用於有效檢查一組數據完整性的結構。這種結構在點對點網絡的背景下特別有趣，其中參與者需要獨立共享和驗證信息。
哈希函數是 Merkle 樹結構的基本組成部分，因此我們建議閱讀文章什麼是哈希？在繼續之前。
默克爾樹如何工作？
假設您要下載一個大文件。對於開源軟件，您通常需要驗證下載文件的哈希值是否與開發人員發佈的哈希值相匹配。如果是這樣，您就知道您計算機上的文件與他們的完全相同。
如果哈希值不匹配，就會遇到問題。您可能下載了僞裝成軟件的惡意文件，或者該文件未正確下載，因此無法運行。如果是這種情況，您可能不會太高興等待文件再次下載。現在，您必須重新啓動該過程並希望該文件不會再次損壞。
然後你會想，如果有一種更簡單的方法來做到這一點就好了。幸運的是，有默克爾樹。您可以將文件分成幾個部分。如果是 50 GB 的文件，您可以將其分爲一百個部分，每個部分的大小爲 0.5 GB。然後你下載每個部分。這本質上就是下載 torrent 文件時發生的情況。
在這種情況下，您的源將提供一個稱爲 Merkle 根的哈希。這個唯一的哈希值代表了組成文件的所有數據片段。 Merkle Root 使數據驗證變得更加容易。
爲了簡單起見，我們舉一個例子，其中我們使用一個 8 GB 的文件，分爲八個部分。我們將不同的片段命名爲 A 到 H。每個片段都經過哈希處理，提供八種不同的哈希值。
將八個片段中的每一個都通過哈希函數以獲得它們各自的哈希值。
好吧，現在我們有了一些更有意義的東西。我們有所有片段的哈希值；所以如果其中一個有缺陷，我們通過將其與來源進行比較就可以知道，對吧？這是有可能的，但效率很低。如果您的文件有數千個片段，您是否打算對它們進行哈希處理並仔細比較結果？
不。相反，我們將每對哈希值組合起來，然後將它們一起提交給哈希函數。然後我們對 hA + hB、hC + hD、hE + hF 和 hG + hH 進行哈希。現在我們有四個哈希值。然後我們對它們進行另一輪哈希，獲得兩個哈希值。最後，我們使用剩下的兩個來獲得我們的主要哈希——默克爾根（或根哈希）。
它類似於樹的倒置結構。在底行，我們有葉子，它們組合起來產生樹枝，最後產生根。
現在我們有了代表我們下載的文件的默克爾根。我們可以將此根哈希與源提供的根哈希進行比較。如果匹配的話就完美了！但如果哈希值不同，我們就可以確定數據已被修改。也就是說，一個或多個片段產生不同的散列。因此，對數據的任何微小修改都會導致完全不同的 Merkle Root。
幸運的是，有一種方便的方法可以檢查哪個片段有問題。在這種情況下，假設是 hE。首先，您可以向對等點（網絡對等點）詢問生成 Merkle 根的兩個哈希值（hABCD 和 hEFGH）。您的 hABCD 值必須與他們的值匹配，因爲該子樹中沒有錯誤。但是，hEFGH 不會匹配，因此您知道此時要進行檢查。然後，您請求 hEF 和 hGH 哈希值並將它們與您的進行比較。 hGH 看起來正確，因此您知道問題出在 hEF 上。最後，比較 hE 和 hF 哈希值。現在您知道 hE 是錯誤的哈希值，您可以再次下載該片段。
簡而言之，Merkle Tree 是通過將數據分成幾個部分來創建的，這些部分被重複哈希以形成 Merkle Root。這樣，您可以有效地檢查任何數據是否出現問題。正如我們將在下一節中看到的，還有其他有趣的應用程序。
考慮投資加密貨幣？在幣安上購買比特幣！
爲什麼比特幣使用默克爾根？
默克爾樹有很多用途，但在這裏我們將重點關注它們對區塊鏈的重要性。默克爾樹對於比特幣和許多其他加密貨幣至關重要。它們是所有塊的組成部分，可以在塊頭（每個塊的單獨標識）中找到。爲了獲取樹的葉子，我們使用塊中包含的所有交易的交易哈希（TXID）。
在這種情況下，默克爾根有幾個用途。我們來分析一下它在加密貨幣挖礦和交易驗證方面的應用。
礦業
比特幣區塊由兩部分組成。第一部分是塊頭（單個塊標識），一個包含塊元數據的固定大小的段。第二部分是交易列表，其大小各不相同，但往往比塊頭大得多。
礦工需要反覆對數據進行哈希處理，產生滿足一定條件的輸出，從而提取出有效的區塊。他們可以進行數萬億次嘗試，直到找到解決方案。在每次試驗中，他們都會更改塊頭中的隨機數（隨機數）以產生不同的輸出。然而，該區塊的大部分內容保持不變。一個塊可以包含數千個交易，您仍然需要每次都對它們進行哈希處理。
Merkle Root 大大簡化了這個過程。當您開始挖礦時，您會收集您想要包含的所有交易並構建默克爾樹。您將生成的根哈希（32 字節）插入到塊頭中。所以，當你挖礦的時候，你只需要對區塊頭進行哈希處理，而不需要對整個區塊進行哈希處理。
這個過程之所以有效，是因爲它是防篡改的。您可以有效地將所有塊交易彙總爲更緊湊的格式。不可能找到有效的塊頭並隨後更改交易列表，因爲這會更改 Merkle Root。當塊被髮送到其他節點時，它們計算交易列表的根。如果根與塊頭不匹配，則該塊將被拒絕。
確認
Merkle Roots 還有另一個有趣的特性可以利用。我們要提到的與輕客戶端（沒有區塊鏈完整副本的節點）有關。如果您在資源有限的設備上運行節點，您不想下載並散列塊中的所有交易。你能做的就是簡單地請求一個Merkle Proof——即全節點提供的證據，證明你的交易是在特定的區塊中。這個過程被稱爲簡化支付驗證或 SPV，中本聰在比特幣白皮書中對此進行了解釋。
要檢查 hD，我們只需要紅色的哈希值。
考慮這樣的場景：我們想要了解 TXID 爲 hD 的交易信息。如果給出hC，我們就可以計算hCD。所以我們需要hAB來計算hABCD。最後，使用 hEFGH，我們可以檢查生成的 Merkle Root 是否與塊頭的 Merkle Root 匹配。如果發生這種情況，就證明交易已插入到區塊中——實際上不可能用不同的數據創建相同的哈希值。
在上面的例子中，我們必須哈希三次。如果沒有默克爾證明，則需要七次。由於現在的區塊包含數千個交易，使用 Merkle Proofs 可以節省我們大量的時間和計算資源。
最後的考慮因素
事實證明，默克爾樹在各種計算機科學應用中非常有用——正如我們所見，它們對於區塊鏈來說非常有價值。在分佈式系統中，默克爾樹可以輕鬆驗證信息，而不會導致網絡充斥不必要的數據。
如果沒有默克爾樹（和默克爾根），其他加密貨幣的比特幣區塊將不會像今天這樣緊湊。雖然輕客戶端面臨隱私和安全性的缺乏，但 Merkle 證明允許用戶驗證交易是否已添加到區塊中，而不會給網絡帶來負擔。
