重點總結
Merkle 樹是一種加密資料結構，它將資料組織成雜湊對，向上組合這些哈希，直到得到一個單獨的雜湊（即 Merkle 根），該雜湊代表整個資料集。
Merkle 根允許區塊鏈網路在不下載整個區塊的情況下驗證交易是否包含在區塊中，它使用緊湊的 Merkle 證明，其規模隨交易數量呈對數增長。
比特幣將梅克爾根嵌入到每個區塊頭中，使輕量級客戶端能夠僅使用區塊頭而不是整個區塊鏈來驗證交易。
以太坊使用更複雜的 Merkle Patricia Trie 演算法來儲存帳戶餘額和智慧合約狀態，使得輕客戶端和 Layer-2 Rollup 的狀態證明成為可能。
介紹
梅克爾樹是區塊鏈系統高效且可大規模驗證的基礎概念之一。它允許網路將整個資料集概括為一個單一的加密指紋，同時也能證明特定交易或資訊包含在其中。為了理解梅克爾樹在區塊鏈設計中的重要性，讓我們來看看它的工作原理、不同網路如何使用它，以及像維克爾樹這樣的新型結構未來可能如何改進它。
梅克爾樹的工作原理
梅克爾樹（Merkle tree）以計算機科學家拉爾夫·默克爾（Ralph Merkle）的名字命名，他於1979年獲得了該概念的專利。梅克爾樹是一種用於高效匯總和驗證大型資料集完整性的資料結構。在區塊鏈中，梅克爾樹將數千筆交易壓縮成一個緊湊的值，並儲存在區塊頭中。
這棵樹是從下往上建構的，使用加密雜湊函數。每個葉子節點包含一條資料（例如一筆交易）的雜湊值。這些葉子節點的雜湊值兩兩配對：每對雜湊值的計算方法是將兩個子節點的雜湊值連接起來，然後對結果進行雜湊運算。這個過程逐層向上重複，直到樹頂只剩下一個哈希值，即默克爾根。
由於每個父節點都依賴其兩個子節點，因此對單一葉節點的任何變更都會向上級聯，並產生完全不同的默克爾根。這項特性使得梅克爾樹成為偵測竄改的有效工具：如果資料集的兩個副本產生相同的梅克爾根，則這兩個資料集極有可能相同。
梅克爾根
Merkle 根是一個固定大小的雜湊值，在區塊鏈應用中通常為 32 個位元組（256 位元），它充當整個資料集的數位指紋。大多數區塊鏈網路的區塊頭都包含 Merkle 根以及其他元數據，例如時間戳記和前一個區塊的雜湊值，這既能保持區塊頭的簡潔，又能以加密方式確保區塊內所有交易的完整資訊。
為了簡單說明，我們來看一個 8GB 的文件，它被分割成八個片段。我們把這些片段分別稱為 A 到 H。然後，每個片段都經過一個雜湊函數處理，得到八個不同的雜湊值。
有了所有片段的雜湊值，如果其中一個片段有誤，你可以透過將其與原始檔案的雜湊值進行比較來發現，對嗎？或許如此，但這效率極低。如果你的檔案有成千上萬個片段，你會對它們全部進行哈希處理並仔細比較結果嗎？
梅克爾根提供了一種更優雅的解決方案。取每一對雜湊值，將它們組合起來，然後再進行哈希運算。這樣就得到了雜湊值 hA + hB、hC + hD、hE + hF 和 hG + hH，最後得到四個雜湊值。
然後，再進行一輪哈希運算，你會得到兩個結果：hABCD 和 hEFGH。最後，將剩下的兩個結果進行雜湊運算，得到主雜湊值，也就是梅克爾根（或根雜湊值）：hABCDEFGH。
梅克爾證明與驗證
Merkle 樹最實用的功能之一是能夠在不洩露整個資料集的情況下證明特定資料屬於資料集。這被稱為 Merkle 證明。為了驗證某個交易是否包含在區塊中，輕客戶端只需要交易本身、沿著路徑到達根節點的一小部分兄弟哈希值，以及來自區塊頭的 Merkle 根節點。驗證器重新計算路徑上的雜湊值，並檢查結果是否與已知的根節點相符。如果匹配，則從數學上證明該交易是區塊的一部分。
我們來看一個驗證交易 ID 為 hD 的交易的場景。如果提供了 hC，就可以計算出 hCD。然後，使用 hAB 計算 hABCD。最後，使用 hEFGH 檢查產生的 Merkle 根是否與區塊頭中的 Merkle 根相符。如果匹配，則證明該交易已包含在區塊中。使用不同的資料幾乎不可能產生相同的雜湊值。
在上面的例子中，你只需要哈希三次。如果沒有梅克爾證明，則需要哈希七次。由於現在的區塊包含數千筆交易，使用梅克爾證明可以節省大量時間和運算資源。
證明的大小隨葉子節點的數量呈對數增長：對於一百萬筆交易（深度為 20 的二叉樹），只需要大約 20 個哈希值，約 640 位元組。這使得輕量級節點（有時稱為簡化支付驗證 (SPV) 用戶端）無需下載整個區塊鏈即可驗證交易，否則下載整個區塊鏈將需要數百 GB 的資料。
區塊鏈網路中的梅克爾樹
比特幣和交易驗證
在比特幣中，每個區塊頭都包含一個 32 個位元組的梅克爾根，它承諾該區塊中的所有交易。比特幣礦工根據他們包含的交易建立梅克爾樹，並將生成的梅克爾根與工作量證明機制一起嵌入區塊頭中。這種設計意味著，通常約 80 位元組的區塊頭足以驗證任何特定交易是否包含在該區塊中，而無需驗證其他交易。
比特幣在其 MAST（默克爾化抽象語法樹）提案中也使用了梅克爾樹，這使得比特幣腳本中複雜的支出條件能夠以梅克爾樹的形式表示。這樣一來，只需要公開腳本中已執行的分支，從而保護未使用的條件的隱私性並減少交易規模。
以太坊和狀態證明
以太坊使用了一種更複雜的變體，稱為 Merkle Patricia Trie，它是一種十六進制（16 路）樹狀結構，用於儲存帳戶餘額、合約代碼和儲存資料。與比特幣交易使用的簡單二叉 Merkle 樹不同，Merkle Patricia Trie 旨在支援頻繁的狀態更新：當帳戶餘額發生變化時，只需重新計算從該葉節點到根節點的路徑，而無需重建整棵樹。
基於 Merkle-Patricia-Trie 產生的狀態證明允許以太坊輕客戶端和 Layer-2 Rollup 在無需運行完整節點的情況下驗證帳戶餘額和合約儲存。這些證明對於需要從一條鏈驗證另一條鏈上事件的跨鏈橋也至關重要。
限制和未來發展
儘管梅克爾樹提供了高效的驗證方式，但證明的大小仍然會隨著資料集呈對數增長。對於以太坊而言，隨著狀態的成長，區塊見證（即驗證區塊所需的證明）的大小可能會達到數兆位元組。這給無狀態客戶端帶來了可擴展性挑戰，因為它們需要接收並驗證每個區塊的這些證明。
Verkle 樹使用基於多項式（Kate-Zaverucha-Goldberg，簡稱 KZG）承諾的向量承諾，而非傳統的雜湊演算法，提供了潛在的解決方案。透過在每個節點下分組多個子節點（分支因子為 256），Verkle 樹產生的證明大小幾乎恆定，約為 170 位元組，無論資料集有多大。以太坊正在積極開發 Verkle 樹集成，預計將在未來的升級中部署。這項轉變將顯著降低輕客戶端的資料負載，並提升整個網路的可擴展性。
常問問題
簡單來說，什麼是默克爾樹？
梅克爾樹是一種組織資料的方法，它使得一個很小的資訊單元（梅克爾根）可以代表一大組資料。其工作原理是反覆對資料對進行雜湊運算，直到只剩下一個雜湊值為止，這樣就可以在不逐個檢查每個資料項的情況下，驗證某個特定資料項是否屬於該集合。
什麼是梅克爾根？
默克爾根是默克爾樹頂端的單一哈希。它就像一個緊湊的數位指紋，代表其下的所有數據。在區塊鏈網路中，梅克爾根儲存在區塊頭中，並提交到該區塊中的每筆交易，從而可以有效地驗證交易是否屬於某個區塊。
梅克爾證明是如何運作的？
Merkle 證明提供了一個交易以及重新計算從該交易到 Merkle 根的路徑所需的最小兄弟哈希集合。驗證者對交易進行雜湊處理，將其與提供的兄弟雜湊按正確順序組合，並檢查最終結果是否與區塊頭中已知的 Merkle 根匹配。如果匹配，則證明該交易包含在 Merkle 根中。
為什麼梅克爾樹對區塊鏈很重要？
Merkle樹允許區塊鏈網路將區塊頭與完整的交易資料分開。輕客戶端只需下載區塊頭（每個區塊約80位元組），即可使用簡潔的Merkle證明驗證交易是否包含在內。如果沒有Merkle樹，驗證交易則需要下載完整的區塊或整個鏈。
Merkle樹和Verkle樹有什麼差別？
兩者都是用來證明資料成員關係的加密累加器，但它們使用的數學原理不同。梅克爾樹使用雜湊函數，產生的證明檔案大小隨資料集呈對數增長（O(log n)）。而維克爾樹使用多項式（KZG）承諾，產生的證明檔案大小幾乎恆定，無論資料集大小如何，都只有幾百字節，因此更適合大規模區塊鏈狀態證明。
結語
Merkle樹是區塊鏈架構的基石，它能夠實現大規模的無需信任的驗證。透過將整個交易區塊壓縮成一個32位元組的雜湊值，Merkle樹允許參與者在無需下載所有資料的情況下驗證資料。這項原理支撐著從比特幣SPV錢包到以太坊狀態證明和跨鏈橋等各種技術。隨著區塊鏈網路的不斷發展，諸如Verkle樹之類的新型加密結構最終可能會補充或取代Merkle樹，但其底層概念——高效的、基於哈希的數據完整性——很可能在未來幾年內仍將是分散式系統的基本構建模組。
延伸閱讀
什麼是區塊鏈共識演算法？
密碼學史
區塊鏈第一層與第二層擴展解決方案
什麼是分片？它是如何運作的？
免責聲明：本內容僅供一般資訊和教育用途，按「原樣」提供，不作任何形式的陳述或保證。本內容不應被視為財務、法律或其他專業建議，亦不旨在推薦購買任何特定產品或服務。您應向合適的專業顧問尋求建議。如內容由第三方貢獻者提供，請注意，其表達的觀點僅代表該第三方貢獻者，並不一定反映幣安學院的觀點。數位資產價格可能波動。您的投資價值可能下跌或上漲，您可能無法收回全部投資金額。您對您的投資決策負完全責任，而幣安學院對您可能遭受的任何損失概不負責。更多信息，請參閱我們的使用條款、風險提示和幣安學院條款。