Merkle樹是什麼

1.比特幣中的Merkle樹

在講Merkle樹之前，我們來看下 比特幣 上某一個區塊它的結構組成，可以看到，裏面有一個二進制哈希樹根。這個哈希值是當前區塊下所有包含的交易以Merkle Tree結構生成的哈希值。

查看區塊的鏈接地址： https://blockchain.info/zh-cn/block-index/1648717

2.Merkle樹概念

Merkle Tree，也叫 哈希樹 ，是由Ralph Merkle於1979年提出申請的專利。它是一種用做快速歸納和校驗大規模數據完整性的樹形數據結構。

它具有以下特點：

• 它是一種樹，大多數是 二叉樹 ，也可以是多叉樹，具有樹結構的所有特點。

• Merkle Tree的葉子節點是數據塊的哈希。

• Merkle Tree的非葉子節點的哈希值是根據它下面所有葉子節點的值哈希計算得到，如下圖所示。

備註：如果最開始葉子節點是奇數個，可以複製最後一個葉子節點，湊成偶數個。

可以發現，只要存儲的葉子節點數據有任何的變動，就會逐級向上傳遞到相應的父節點，最終使得Merkle樹的根節點哈希值發生變化。

3.Merkle樹的應用

Merkle樹的應用場景有以下幾種：

• 快速比較大量數據：當兩個Merkle樹的根哈希值相同時，說明所代表的的數據都相同

• 快速定位修改：如上圖，如果交易C發生改變，那麼就會導致N2、N5和Merkle Root發生改變。所以，我們想要快速定位，只需要沿着Root==>N5==>N2就可以定位到交易C發生改變。

• 零知識證明：例如，想要證明一組交易中包含某個交易A，但又不想讓對方知道交易A的具體內容，那麼就可以構建Merkle樹（如上圖），向對方公佈N0、N1、N4和Root，對方就可以確認交易A的存在，但無法知道交易A的具體內容。

比特幣的簡單支付認證（SPV）

1.SPV是什麼

簡單支付認證，即Simple Payment Verification，簡稱SPV。SPV的目標是爲了驗證某個交易支付是否存在，以及得到比特幣網絡多少個確認（多少個區塊）。比特幣中的SPV功能就應用到了Merkle樹的特性。

2.爲什麼需要SPV機制

我們知道，比特幣網絡中所有產生的交易均打包進區塊中，一般情況下，一個區塊中包含幾百上千筆交易是很常見的。在2014年4月份，比特幣網絡中一個全節點要存儲、處理所有區塊的數據，需要佔用15GB的空間，並且每個月以超過1GB的速度在增長，到現在呢？要完整下載比特幣的所有區塊數據，需要整整200GB以上的空間！！。

如果用戶要用手機來使用比特幣，那完全不夠空間去存儲這麼龐大的數據，而且以後還是逐年繼續增長。於是中本聰在比特幣白皮書中提出了SPV的概念：不運行全節點也可以驗證支付，用戶只需要保存所有的區塊頭就可以了。雖然用戶不能自己驗證交易，但如果能夠從區塊鏈的某處找到符合的交易，就可以知道這筆交易已被網絡確認，也可以確認該筆交易得到網絡多少筆確認。

這裏需要注意的是，SPV強調的是驗證支付，不是驗證交易。這兩個概念是不同的。驗證支付，比較簡單，只需要判斷用於支付的那筆交易是否被驗證過，以及得到網絡多少次確認（即有多少個區塊疊加）。而交易驗證則複雜的多，需要驗證賬戶餘額是否足夠支出、是否存在雙重支付、交易腳本是否通過等問題，一般這個操作是由全節點的礦工來完成。

如下圖，我們知道比特幣中區塊結構分成兩部分，一個是區塊頭，包含區塊的必要屬性，僅80字節大小。另一個是區塊體，包含當前區塊下的所有交易，一般一個區塊包含成百上千筆交易，每筆交易一般要400多字節。

3. 比特幣網絡節點類型

這裏需要介紹下比特幣網絡中幾種常見的節點類型：

（1）全節點

包含錢包（支付驗證）、礦工、完整區塊鏈數據庫、網絡路由節點的功能。

（2）SPV節點

就只有簡單的支付驗證功能

除此之外，還有獨立礦工等其他類型的節點，這裏不涉及，就不一一介紹。詳細的可以參考《精通比特幣》一書的第六章比特幣網絡。

4.SPV驗證過程

在SPV節點上，不保存全部區塊鏈數據，不下載區塊全部交易，只保存區塊頭數據。所以這種節點不能驗證全部交易，只能用於驗證支付（確認支付是在區塊鏈中，以及確認多少次）。截止到現在爲止，比特幣高度爲： 521283 （時間：2018-05-05 15:41），按照區塊頭80字節來算，總共也就10MB大小而已（80*521283/1024/1024）,這對整個存儲容量的要求就大大減少。

那麼，從用戶A在購買商品時通過比特幣支付，並聲稱自己已經轉了1BTC給商家，到商家驗證支付有效（SPV驗證），這個過程是怎樣的呢？

• Step1：SPV節點如果只關心某個支付到自己比特幣地址的交易，則可以通過建立布隆過濾器（布隆過濾器是一種基於哈希的高效查找結構，能夠快速確定某個元素是否在一個集合內）限制只接收含有目標比特幣地址的交易。

• Step2：一旦比特幣網絡中其他當節點探測到某個交易符合SPV節點設置的布隆過濾器條件時，其它節點將以Merkleblock消息的形式發送該區塊，Merkleblock消息包含區塊頭和一條連接目標交易與Merkle根的Merkle路徑。

• Step3：接下來，SPV節點需要驗證交易，需要做2個檢查，分別是： 交易的存在性檢查和交易是否重花的檢查 。

• Step4：SPV節點通過該Merkle路徑找到跟該交易相關的區塊，並驗證對應區塊中是否存在目標交易（該過程也被稱爲： Merkle Path Proof ）。SPV節點所收到的Merkleblock數據量通常少於1KB，只有一個完整區塊（大約1MB）大小的千分之一左右。

• Step5：現在通過Merkle Path Proof，SPV節點確認了交易確實存在於區塊鏈中，但是這個還是無法保證這筆交易（Transaction）的Input（引用的上一筆UTXO）沒有被重花（雙重支付）。這時候SPV節點通過去看這筆交易所在區塊之後的區塊個數，Block個數越多說明該區塊被全網更多節點共識，一般來說，一筆交易所屬區塊之後的區塊個數達到6個時，就說明這筆交易是被大家覈准過（達成共識）的，沒有重花，而且被篡改的可能性也很低，如下圖所示。

5.Merkle路徑

在上一節中，我們提到了通過Merkle路徑可以證明一筆交易是否存在區塊中。下面我們通過一個例子來說明下Merkle路徑。

如下圖，如果需要證明某個區塊上是否存在一筆交易C（如上圖區塊結構所示，我們是可以拿到Merkle樹根的哈希值），那麼我們只需要N3和N4的哈希值構成的Merkle路徑就可以證明，過程如下：

• • Step1：獲取交易C的哈希值，N2=Hash(交易C)
• • Step2：通過N2和N3的哈希值，得到父節點的哈希值：N5=Hash(N2+N3)
• • Step3：同上，通過N4和N5的哈希值，得到根節點的哈希值：Root=Hash(N4+N5)

• Step4：然後將上一步得到的根哈希值對比區塊頭中MerkleTree的根哈希值，如果相同，則證明該區塊中存在交易C，否則說明不存在

也就是說，對於一個包含4個交易的區塊，我們只需要2個哈希節點就可以進行支付驗證。

這裏，由於區塊中交易數量少，我們可能不能很明顯看出Merkle Tree結構的優點。下面，我們來逐漸增加區塊中交易的數量，來看看Merkle Tree的優點。

| 交易數量 | 區塊近似大小 | 哈希數量 | Merkle路徑大小 | | --- | --- | --- | --- | | 16筆交易 | 4KB | log2(16)=4 | 4 32 = 128字節 | | 512筆交易 | 128KB | log2(512)=9 | 9 32 = 288字節 | | 2048筆交易 | 512KB | log2(2048)=11 | 11 32 = 352字節 | | 65536筆交易 | 16MB | log2(65536)=16 | 16 32 = 512字節 |

備註：一個哈希大小爲32字節

由上表可以看到，當交易數量成幾何速度成長時，Merkle路徑的開銷增長就很緩慢。所以，通過Merkle路徑，SPV節點只需要很小的開銷就可以快速定位一筆交易。

本文轉載自： 《Merkle樹和SPV機制》 | shuwoom.com

喜歡的話，前往作者網站打賞。

相關文章