Merkle 樹是一種用於計算機應用程序的數據結構。在比特幣和其他加密貨幣中，默克爾樹有助於更高效、更安全地編碼信息。
Merkle 樹是區塊鏈技術的基本組成部分，因為它們有助於它正常運行。
它們使高效、安全地驗證大型數據結構成為可能，在區塊鏈的情況下，還可以驗證潛在的無限數據集。
Merkle 樹在區塊鏈中的實施具有多重效果。它使他們能夠擴展，同時還提供基於哈希的架構來維護信息完整性並使認證變得簡單。
加密貨幣散列函數是允許默克爾樹工作的技術的一個非常重要的部分，所以我們將停下來了解它們是如何工作的。
加密貨幣哈希函數
簡單來說，哈希函數是一種函數，它允許你將信息從任意大小的輸入映射到固定大小的輸出。
去中心化算法應用於你輸入的信息，以便結果始終具有相同的長度。此信息輸出稱為散列。
哈希函數的結果不僅具有固定大小，而且相對於輸入也是唯一的，這被稱為確定性。
無論我們運行該算法多少次，如果輸入相同，它總是會產生相同的輸出。
例如，如果我們有以下條目列表，則每個條目的結果始終是唯一的。但這還不是全部，我們還可以看到，如果我們只更改一個單詞或一個字母，結果是完全不同的。
後者很重要，以便以後沒人能猜到信息。
輸出總是相同的長度這一事實使我們能夠使用這樣的算法對大量信息進行編碼。如果我們有散列，就沒有必要存儲原始信息。
在存在大量信息的系統中，能夠以固定數量的字符存儲和識別信息的好處可以幫助節省空間並提高效率。
在區塊鏈的情況下，該算法用於確定區塊鏈的狀態。
塊鍊或區塊鍊是一組鏈接在一起的塊，其中包含前一個塊的信息和哈希值，它創建了連接塊的鏈，並因此而得名。
每個塊通過一個散列指針連接到另一個塊，散列指針是來自前一個塊的信息及其地址的散列。
通過以這種方式鏈接信息塊，在新塊中創建的每個哈希代表區塊鏈的總體狀態。它就像是那些相互包含的俄羅斯娃娃之一（每個散列是另一個散列的結果，這是另一個散列的結果，等等）。
哈希可能是用不同的算法創建的，但比特幣使用的並且最普遍的算法是SHA-256。一個看起來像這樣：
183492419c7b553a05328725f7a754d3293f790a31d2d1c95a0a09736e223059
雖然我們可以在不需要Merkle 樹的情況下使用加密貨幣哈希，但現實情況是，由於它的低效和可擴展性，我們並不強烈推薦它。例如，如果我們按時間順序存儲塊的哈希值，那麼在搜索時，就需要付出更多的努力。
正如我們現在將看到的，Merkle 樹可以非常輕鬆地解決數據完整性問題，以及通過這種結構映射數據和使用Merkle 測試。
默克爾樹和默克爾測試
以1979 年獲得該概念專利的人Ralph Merkle 的名字命名，這些結構具有樹格式，其中每個不是子節點的節點都是其各自子節點的散列。
葉節點是位於結構底部的節點。這樣理解起來可能有些困難，但是如果你看下圖，你一定會明白的。
重要的是要注意左側的不是葉子的節點，也稱為分支（這裡用散列0-0 和散列0-1 表示）是各自子信息1 和信息2 的散列。然後我們看到根哈希連接子哈希0 和哈希1。
這個例子是最常見和最簡單的Merkle 樹，因為它是一棵二叉樹。
如你所見，頂部是一個表示整個樹的哈希的頂部哈希，稱為Merkle 根或根哈希。
簡而言之，Merkle 樹是一種數據結構，它可以採用“n”個哈希值並僅用一個來表示它們。
樹的結構允許你有效地映射大量信息，並允許你確定其中發生更改的位置。
這就是使Merkle 測試成為可能的原因，在該測試中，任何人都可以驗證一條信息的哈希值在整個樹中是否一致，直到根。無需分析所有散列，只需分析它所在的分支即可實現這一點。
我們只是簡單地檢查從散列子集一直到頂部的信息，這比解析所有存在的散列要快得多，資源消耗更少。特別是如果樹非常大。
只要根哈希是公開的和可信的，任何想要在數據庫中搜索關鍵值的人都可以使用默克爾測試來驗證數據庫中一段數據的位置和完整性，該數據具有具體的根。
當根哈希可用時，可以從任何不受信任的來源接收哈希樹，並且可以同時檢查樹的一個分支，並立即驗證數據完整性，即使我們還沒有完成所有下載。樹.
Merkle 樹結構最重要的優勢之一是能夠使用類似於用於驗證小得多的數據量的散列機制來驗證任意大的數據集。
該樹對於將大型數據集分佈為更小且更易於管理的部分很有趣，儘管數據的整體大小更大，但完整性驗證的複雜性卻大大降低。
根哈希可以用作整個數據集的指紋，包括整個數據庫或代表區塊鏈的整個狀態。
在以下部分中，我們將深入探討比特幣和其他系統如何實現默克爾樹。
比特幣中的默克爾樹
我們已經看到比特幣哈希算法是SHA-256。這是“Secure Hashing Algorithm”的首字母縮寫，其結果是256位的固定長度。
比特幣對默克爾樹的使用是存儲並最終修剪每個區塊的交易。
在區塊鏈中，區塊是通過前一個區塊的哈希值連接起來的。特別是在比特幣的情況下，每個塊都包含內部的所有交易以及由以下部分組成的標頭：
從比特幣白皮書中提取的圖像向我們展示了默克爾樹與區塊的關係。
交易被礦工包含在區塊中，然後通過哈希函數成為默克爾樹的一部分。最後，它是存儲在標頭中的根（根哈希）。
所有這些都有很大的好處。
最有趣的是，正如文件所指出的，它允許存在所謂的簡單支付驗證(SPV) 節點，也稱為“瘦客戶端”。
這些節點不必下載整個比特幣區塊鏈，只需下載最長鏈的區塊頭。
SPV 節點可以通過諮詢他們的對等節點來實現這一點，直到他們對所操作的存儲區塊頭是較長鏈的一部分感到滿意為止。
然後，SPV 節點可以通過使用Merkle 測試將交易映射到特定的Merkle 樹，並在作為較長鏈一部分的區塊頭中使用Merkle 樹的根的相應散列來確定交易的狀態。
此外，比特幣的默克爾樹的實施允許區塊鏈修剪以節省空間。
這是因為只有根哈希存儲在塊頭中，因此可以通過從Merkle 樹中刪除不必要的分支並僅保留Merkle 測試所需的分支來修剪舊塊。
在其他區塊鍊和系統中的實現
雖然比特幣是第一個實現默克爾樹的，因為它是第一個加密貨幣，但許多其他區塊鏈也遵循了類似的路徑並選擇了這種結構。甚至有些人選擇了一個更複雜的。
以太坊是第二個最受認可的加密貨幣，也是實現這一點的一個很好的例子。不同之處在於，由於以太坊是圖靈完備類型，因為它是一個我們可以在其上構建應用程序的平台，所以它的Merkle 樹實現也不同，更加複雜。
這被稱為Merkle Patricia 樹，有3 棵獨立的Merkle 樹用於不同的事情。
不要認為Merkle 樹只適用於區塊鏈。它們的使用範圍更廣，我們可以在不同的系統中找到它們。
我們也可以在Git 或IPFS 等分佈式版本系統中找到這些結構。因為它們非常適合保護和驗證以P2P 方式在計算機之間共享的信息。
結論
Merkle 樹對區塊鏈生態系統很重要，因為它們允許它們在保持完整性和無法更改信息的同時發揮作用。
如果你對這項技術感興趣，你想了解更多關於分佈式網絡如何工作的信息。今天看到的哈希和結構是你必須掌握的基本概念，以便讓自己沉浸在所有技術細節中。
資訊來源：由0x資訊編譯自CRIPTOTARIO。版權歸作者Criptotario所有，未經許可，不得轉載
