2.3.3　默克爾樹

默克爾樹（Merkle哈希樹）屬于二叉樹的一種，而比特幣的底層交易系統選擇了默克爾樹進行了實現。

1．什么是默克爾樹？

由一個根節點、一組中間節點和一組葉子節點組成。根節點表示的是最終的那個節點，只有一個。葉子節點可以有很多，但是不能再擴散，也就是沒有子節點。

如果把它想象成一棵樹，由樹根長出樹干，樹干上長出樹枝，樹枝長出葉子，但是，葉子上不會再長出葉子，如圖2-7所示。

圖2-7　默克爾樹示意圖

    Root：就是根節點，所有的子節點匯總到這里。
Hash：能將任意長度的二進制明文映射為較短的二進制串的算法，也叫“哈希算法”，如2.3.1
小節介紹的MD5、SHA等算法，經過哈希算法哈希后的結果，也稱為哈希值。
Data0, Data1……Data3：代表的是具體的原始數據。
B0, B1……B3：是把原始數據進行哈希運算后得到的對應哈希值。

一個簡單的默克爾樹就是圖2-7所顯示的那樣，由以下三個步驟來實現：

（1）把最底層的Data0, Data1……Data3這四條數據，每一條單獨進行Hash，得出4個哈希值作為葉子節點。

（2）把相鄰的兩個葉子節點的哈希值拿出來再進行Hash，如B0的哈希值加上B1的哈希值，求和的結果Hash后得出B4。

（3）遞歸執行這樣的Hash操作，直到最終Hash出一個根節點，就結束了。

默克爾樹的運行原理，在圖中展現是：B0 + B1 Hash得出B4，B2 + B3 Hash得出B5，B4 + B5 Hash得出Root根節點。由于每個節點上的內容都是哈希值，所以也叫“哈希樹”。

2．默克爾樹的三大特性

（1）任意一個葉子節點的細微變動都會導致Root節點發生翻天覆地的變化，這個可以用來判斷兩個加密后的數據是否完全一樣。

（2）快速定位修改，如果Data1中數據被修改，會影響到B1、B4和Root，當發現根節點Root的哈希值發生變化，沿著Root→B4→B1，最多通過O（log n）時間即可快速定位到實際發生改變的數據塊Data 1。

（3）零知識證明（詳細內容參見本書第3章），它指的是證明者能夠在不向驗證者提供任何有用信息的情況下，使驗證者相信某個論斷是正確的。比如怎么證明某個人擁有Data0……Data3這些數據呢？創建一棵如圖2-8所示的默克爾樹，然后對外公布B1、B5、Root；這時Data0的擁有者通過Hash生成B0，然后根據公布的B1生成B4，再根據公布的B5生成Root，如果最后生成的Root哈希值能和公布的Root一樣，則可以證明擁有這些數據，而且不需要公布Data1、Data2、Data3這些真實數據，具體實現方式如圖2-8所示。

圖2-8　零知識證明原理圖

3．默克爾樹在比特幣中的應用

• 默克爾路徑：表示從根節點到葉子節點所經過的節點組成的路徑，圖2-8中Root→ B4 → B1就是一條路徑。
• 比特幣中，默克爾樹被用作歸納一個區塊中打包的所有交易，同時生成整個交易集合的數字簽名，且提供了一種校驗區塊是否存在某交易的高效途徑，這就是默克爾路徑。生成默克爾樹需要遞歸地對各個子節點進行哈希運算，將新生成的哈希節點插入默克爾樹中，直到只剩一個哈希節點，該節點就是默克爾樹的根節點。
• 假設一個區塊中有16筆交易，根據公式O（log n）可以算出16的對數是4，也就是要找到這個區塊中的任意一筆交易，只需要4次就可以，它的默克爾路徑會保存4個哈希值，我們來看一個統計（見表2-1），直觀感受一下它搜索效率的提升。

表2-1　交易路徑對照表

（注：一筆交易的大小，大概需要250 Byte左右的存儲空間，路徑數代表哈希值的數量，路徑數是4表示這條路徑存了4個哈希值，每個哈希值是32 Byte，區塊大小=交易數* 250 Byte，路徑大小=路徑數* 32 Byte）

可以看出，當區塊大小由16筆交易（4KB）增加至262 144筆交易（65MB）時，為證明交易存在的默克爾路徑長度增長極其緩慢，僅僅從128字節到576字節。有了默克爾樹，一個節點能夠僅下載區塊頭（80字節／區塊，里面包含上一區塊頭的哈希值、時間戳、挖礦難度值、工作量證明隨機數，包含該區塊交易的默克爾樹的根哈希值），然后通過從一個滿節點 ，回溯一條小的默克爾路徑，就能認證一筆交易的存在，而不需要存儲或者傳輸大量區塊鏈中的大多數內容——這些內容可能有幾個G的大小。這種不需要維護一條完整的區塊鏈的節點，又被稱作“簡單支付驗證（SPV）節點”，它不需要下載整個區塊而僅僅通過默克爾路徑去驗證交易的存在。