梅克爾樹

梅克爾樹（Merkle trees）是區塊鏈的基本組成部分。雖說從理論上來講，沒有梅克爾樹的區塊鏈當然也是可能的，只需創建直接包含每一筆交易的巨大區塊頭（block header）就可以實現，但這樣做無疑會帶來可擴展性方面的挑戰，從長遠發展來看，可能最後將只有那些最強大的計算機，才可以運行這些無需受信的區塊鏈。 正是因為有了梅克爾樹，以太坊節點才可以建立運行在所有的計算機、筆記本、智慧型手機，甚至是那些由Slock.it生產的物聯網設備之上。

基本介紹

• 中文名：梅克爾樹
• 外文名：Merkle trees
• 別稱：Merkle樹
• 屬性：數據類型
• 作用：歸納校驗區塊數據的存在性完整性
• 套用領域：區塊鏈

相關概念

區塊鏈

區塊鏈是隨著比特幣等數字加密貨幣的日益普及而逐漸興起的一種全新的去中心化基礎架構與分散式計算範式， 目前已經引起政府部門、金融機構、科技企業和資本市場的高度重視與廣泛關注。 區塊鏈技術具有去中心化、時序數據、集體維護、可程式和安全可信等特點, 特別適合構建可程式的貨幣系統、金融系統乃至巨觀社會系統.。

哈希（散列）

哈希（hash），一般翻譯做“散列”，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的訊息壓縮到某一固定長度的訊息摘要的函式。

梅克爾樹

梅克爾樹是區塊鏈的重要數據結構， 其作用是快速歸納和校驗區塊數據的存在性和完整性。一般意義上來講，它是哈希大量聚集數據“塊”的一種方式，它依賴於將這些數據“塊”分裂成較小單位的數據塊，每一個bucket塊僅包含幾個數據“塊”，然後取每個bucket單位數據塊再次進行哈希，重複同樣的過程，直至剩餘的哈希總數僅變為1。

構成原理

梅克爾樹通常包含區塊體的底層 (交易) 資料庫， 區塊頭的根哈希值 (即Merkle根) 以及所有沿底層區塊數據到根哈希的分支。梅克爾樹運算過程一般是將區塊體的數據進行分組哈希， 並將生成的新哈希值插入到梅克爾樹中，如此遞歸直到只剩最後一個根哈希值並記為區塊頭的 Merkle根。 最常見的梅克爾樹是比特幣採用的二叉梅克爾樹,，其每個哈希節點總是包含兩個相鄰的數據塊或其哈希值。其特點如下：

1. 梅克爾樹是一種樹，大多數是二叉樹，也可以多叉樹，無論是幾叉樹，它都具有樹結構的所有特點；
2. Merkle Tree的葉子節點的value是數據集合的單元數據或者單元數據HASH。
3. 非葉子節點的value是根據它下面所有的葉子節點值，然後按照Hash算法計算而得出的。

優點

梅克爾樹有諸多優點，首先是極大地提高了區塊鏈的運行效率和可擴展性，使得區塊頭只需包含根哈希值而不必封裝所有底層數據,，這使得哈希運算可以高效地運行在智慧型手機甚至物聯網設備上；其次是梅克爾樹可支持 “簡化支付驗證” 協定, 即在不運行完整區塊鏈網路節點的情況下，也能夠對（交易）數據進行檢驗。

種類

即根哈希（root hash）

梅克爾樹最為常見和最簡單的形式，是二進制梅克爾樹（ binary Mekle tree），其中一bucket單位的數據塊總是包含了兩個相鄰的塊或哈希。哈希算法允許了一個整齊的機制，我們稱之為梅克爾證明（Merkle proofs）。一個梅克爾證明包含了一個數據塊，這顆梅克爾樹的根哈希，以及包含了所有沿數據塊到根路徑哈希的“分支”。

即根哈希

帕特里夏樹（Patricia Trees）

以太坊所使用的梅克爾樹，我們稱之為“梅克爾.帕特里夏樹”（Merkle Patricia tree）。其工作原理，最為簡單的解釋是，一個以編碼形式存儲到記錄樹的“路徑”的值。每個節點會有16個子（children），所以路徑是由十六進制編碼來確定的：例如，狗（dog）的鍵的編碼為6 4 6 15 6 7，所以你會從這個根開始，下降到第六個子，然後到第四個，並依次類推，直到你達到終點。

套用

數字簽名

最初Merkle Tree目的是高效的處理Lamport one-time signatures。 每一個Lamport key只能被用來簽名一個訊息，但是與Merkle tree結合可以來簽名多條Merkle。這種方法成為了一種高效的數字簽名框架，即Merkle Signature Scheme。

P2P網路

在P2P網路中，Merkle Tree用來確保從其他節點接受的數據塊沒有損壞且沒有被替換，甚至檢查其他節點不會欺騙或者發布虛假的塊。

Trusted Computing

可信計算是可信計算組為分散式計算環境中參與節點的計算平台提供端點可信性而提出的。可信計算技術在計算平台的硬體層引入可信平台模組(Trusted Platform，TPM)，實際上為計算平台提供了基於硬體的可信根(Root of trust，RoT)。從可信根出發，使用信任鏈傳遞機制，可信計算技術可對本地平台的硬體及軟體實施逐層的完整性度量，並將度量結果可靠地保存再TPM的平台配置暫存器(Platform configuration register，PCR)中，此後遠程計算平台可通過遠程驗證機制(Remote Attestation)比對本地PCR中度量結果，從而驗證本地計算平台的可信性。可信計算技術讓分散式套用的參與節點擺脫了對中心伺服器的依賴，而直接通過用戶機器上的TPM晶片來建立信任，使得創建擴展性更好、可靠性更高、可用性更強的安全分散式套用成為可能。可信計算技術的核心機制是遠程驗證(remote attestation),分散式套用的參與結點正是通過遠程驗證機制來建立互信,從而保障套用的安全。

IPFS

IPFS(InterPlanetary File System)是很多NB的網際網路技術的綜合體，如DHT( Distributed HashTable，分散式哈希表)，Git版本控制系統，Bittorrent等。它創建了一個P2P的集群，這個集群允許IPFS對象的交換。全部的IPFS對象形成了一個被稱作Merkle DAG的加密認證數據結構。

比特幣

梅克爾樹最早的套用是比特幣，它是由中本聰在2009年描述並創建的。Bitcoin的Blockchain利用Merkle proofs來存儲每個區塊的交易。