1. 引言

本文重點解釋何為Merkle tree，及其如何在Bitcoin、Amazon的Dynamo DB 、ZFS filesystem 以及 Git version control system 中運用，

參考 Is there a difference between perfect, full and complete tree?有：

• Full Binary Tree：是每個節點具有0個或2個子節點，
  

• Complete Binary Tree：最底層具有左右節點或者只具有左節點；除最底層外，所有節點據具有左右節點，
  

• Perfect Binary Tree：是指所有節點都有左右子節點，
  

2. 何為Merkle tree?

Merkle tree又稱為Hash tree，本質為hash值的分級集合，其層級結構為：

• Merkle leaf：實際的資料對應的hash值，
• Merkle branch：中間hash值，
• Merkle root：將所有資料匯總為一個hash值，

基本的Merkle tree 示意為：

上圖：

• Data1~ Data4：為來自應用的實際資料，
• Hash1~ Hash4：為Data1~ Data4 對應的hash值，為Merkle leaf，
• Hash12和Hash34：為Merkle branch，Merkle tree為層級分布的，除Merkle leaf和Merkle root之外的所有均稱為Merkle branch，
• Hash1234：為Merkle root，

以上Merkle tree中的每一層的數量都為偶數，都可形成精準的pair對，又可稱為balanced Merkle tree，但實際，存在奇數數量的情況——如具有5個Data Node，此時，Data1+Data2形成一個Merkle branch，Data3+Data4形成一個Merkle branch，而Data5落單了，這種Merkle tree為unbalanced，

針對unbalanced Merkle tree的處理方式有：

• Bitcoin的做法是，復制落單的Data5的hash值來形成一個Merkle branch，具體示意為：【復制了Hash5和Hash55】
  
• Monero的做法是：簡單地服用落單的Data5對應的hash值，讓它保持un-paired狀態，如下圖所示的cf54b hash 值，Monero這種簡單復用的實際效果與Bitcoin中復制的效果是一樣的，【可見 mukatee撰寫的示例代碼】
  
  而實際在 Monero的代碼庫tree_hash.c 中，將Merkle tree轉換為了perfect binary tree：【可見 mukatee撰寫的Monero Merkle tree 示例代碼】
  
  實際的計算思路為：假設Merkle tree中包含有5個data node（或稱交易），而5的next_power_of_two為8，8-5=3，因此應從第4個（Data4）開始運行iteration 1，【詳細可參見 Teemu Kanstrén 2021年2月16日 medium博客 Merkle Trees: Concepts and Use Cases】

3. 區塊鏈中的Merkle tree

在Bitcoin等區塊鏈平臺，使用Merkle tree來對區塊中的交易進行匯總和驗證，并將Merkle root作為對所有交易的匯總 嵌入到block header中，詳細示意為：

在每個區塊中，包含有：

• 當前block ID value：為當前區塊header域的hash值，Merkle root為該header域的一部分，
• previous block ID：上圖中的Parent是指前一區塊的block ID值，

由于每個block ID中都包含了相應區塊中所有交易的Merkle root，通過以上鏈式結構，保證了交易的不可篡改性，

實際Bitcoin的block header中包含了：

• Difficulty target value（Bitcoin中稱為bits）；
• 當前區塊中所有交易的Merkle root；
• Nonce：a value changed in mining to find accepted blocks；
• previous block hash （block ID）：在上圖中將該previous hash稱為parent，實作了將當前區塊與前序區塊的鏈接，
• Timestamp：Time of mining (creating the hash for) the block；
• Block version：用于標識所支持的features和formats（同時在Monero中也用于區分所使用的hash函式），

以上所有block header內容均被打包hash以形成相應的block ID，這就使得幾乎不可能對block header進行修改，而將Merkle root包含進block ID中，進一步保證了幾乎不可能對區塊中的交易進行修改，

3.1 Merkle tree用于保證區塊中交易的不可篡改性

在Bitcoin中，將區塊中所有交易的Merkle root包含在block header中，借此保證沒有任何交易被篡改過，

如將上述例子中的Data4替換為Data6，則相應的Merkle tree修改為：【相應的Merkle root由aa8d3變為了f8932，由此可知，任何交易資料的變動都將造成Merkle root的修改，使得其不再與block header中所記錄的Merkle root匹配，借助block header的鏈接，這種交易的不可篡改性可傳遞至整個區塊鏈網路，】

為何選擇Merkle tree方案來 保證交易資料不可篡改呢？似乎：

• 將所有的交易資料拼接然后hash成一個單獨的root hash值，并將該root hash值包含進block header中 也可以滿足保證交易資料不可篡改的目標，
  
  

實際上，Merkle tree 相比于 以上拼接hash方案，除了能保證交易的不可篡改性之外，額外的優勢為——在hash驗證中提供了更多的粒度，使得其可運用某些聰明的技巧來更高效的處理區塊鏈，如：
在 Bitcoin白皮書中額外提及了將Merkle tree用于：

• blockchain pruning
• simplified payment verification (SPV)

除此之外，在Stratum mining pool protocol中也基于Merkle tree進行了巧妙的運用，

3.2 將Merkle tree用于blockchain pruning

隨著時間的推移，區塊鏈中的區塊越來越多，變得越來越大，
如截止2021年2月，Bitcoin區塊鏈已達380GB，

blockchain pruning 借助 Merkle tree實作了對空間的裁剪——將本地不再需要的交易資料移除，

事實上，我們仍然需要全量資料來進行全面的驗證和歷史追溯，但是，并不是P2P網路中的所有節點都需要全量資料，
在Bitcoin白皮書中提出可通過運用Merkle tree來prune (remove) 區塊中的 spent (used) transactions，

如下圖所示，假設Tx1 (Data1)、Tx2 (Data2)、Tx4 (Data4) 為已花費交易，而Tx3 (Data3)和Tx5 (Data5)為未花費交易：

接下來，針對的是不關注全量資料的非全節點，其僅需要維護可花費交易串列，
中本聰的提議是：
將區塊中的已花費交易移除，僅保留需要驗證未花費交易相關的Merkle tree branch，可示意為：

若在此基礎上再假設Tx3 (Data3)也為已花費交易：

則相應的Merkle tree可進一步裁剪為：

通過以上區塊裁剪，可節約：【總共可節約約80%的存盤空間】

• 4 out of 5 個交易的存盤空間；
• 6 out of 9 個Merkle tree node的存盤空間，

隨著區塊越來越長，已花費交易也會越來越多，因此也可節約更多的空間，

實際上，在 Bitcoin StackExchange 中就區塊裁剪實際方案有很多深入討論，盡管Merkle tree裁剪是一個很聰明的辦法，但是在Bitcoin的核心軟體層面并沒有做相應實作，主要基于以下考慮：

• 需要下載和驗證所有區塊后，才能進行裁剪操作；
• 當不需要維護old blocks和old merkle trees時，可以通過裁剪僅維護unspent outputs和相應的scriptPubKeys，裁剪后將無法用于幫助新節點進行區塊同步，

而實際Bitcoin實作的區塊裁剪方案為：
自Bitcoin Core v0.8.0起，將validation database （又名 “chainstate”或“UTXO set”或“account balance sheet”）從區塊鏈上分離了出來，當有新區塊時，將對該database進行remove spent inputs和add outputs操作，這就意味著，區塊的下載和驗證方式仍然保持跟之前一樣，但之后它們就不再被用于驗證了，區塊檔案仍然存盤在磁盤中以便于其它節點同步時進行發送區塊 操作，或者以便于對舊交易進行rescan，
而自Bitcoin Core v0.11.0起，就可能以真正的裁剪模式運行，即區塊檔案隨后會從本地磁盤洗掉；自v0.12起，可能可支持錢包以裁剪模式運行；自v0.14起，可能可支持手工裁剪（不再由應用程式決定，而可通過RPC命令來實作），

Bitcoin實際實作是將未花費交易存盤在獨立的資料庫中，以滿足快速查找的目的，初次啟動時，通過掃描區塊鏈來構建該資料庫，后續每當有新的和已花費的交易時，對該資料庫進行更新，每當有新的區塊在Bitcoin網路中廣播時，該資料庫將隨之持續更新，對于裁剪節點，將僅依賴該資料庫就足夠了，

對于基本操作，運行裁剪節點就足夠了，但是裁剪節點無法完整支持區塊鏈的所有功能，因此實際區塊鏈網路中，仍然需要一些節點來維護全量資料，

3.3 將Merkle tree用于simplified payment verification (SPV)

在Bitcoin白皮書中提及了 simplified payment verification (SPV)，
SPV，簡單支付驗證，是一種不用運行全節點、只需保存所有的區塊頭，就可以驗證支付的技術手段，是一個在輕客戶端環境下，就能驗證支付有效性的程序，
注意SPV 是支付驗證，不是交易驗證，SPV 只負責判斷用于支付的那筆交易，是否已經被驗證過，有多少個確認數，而不是全節點操作的復雜的交易驗證，

在SPV中，輕量級區塊鏈客戶端僅存盤block headers，但也希望驗證它在區塊鏈中收到的付款是否為有效交易，由于缺少完整的交易細節，SPV客戶端使用Merkle tree 與完整節點協作來有效地驗證交易細節，

借助上面的裁剪的例子，SPV client想要驗證該區塊中的TX5，示意為：

此時，SPV client節點需向全節點請求the Merkle branches required to build the Merkle root with the TX5 data，By rebuiding the Merkle root (aa8d3) from the transaction of interest (TX5), and the Merkle branches (96b8d) provided by the full node, the SPV client can have confidence in having received a valid transaction，將rebuilt的Merkle root和區塊頭中存盤的Merkle root對比，SPVCclient就可確認the whole tree (and thus TX5) is in fact valid, and is a part of the blockchain，

SPV 可很好的說明Merkle tree是如何使用的，
將 SPV 與 (block) data filtering (Bitcoin use Bloom filters) 結合，可用于：

• synchronize and verify existence and correctness of selected data in a distributed system，

3.4 將Merkle tree用于礦池 Stratum protocol

傳統的加密貨幣的產生都是通過proof of work (Pow) hashing 挖礦產生的，
礦池是指一種小型礦工聯合起來，并根據他們對礦池貢獻的算力（hash）獲得采礦獎勵的方式，
這就需要一個中心物體，即采礦池來協調礦工，它需要一種在所有客戶端上有效地分發和跟蹤整個挖掘程序的方法，通過一些巧妙的技巧，Stratum protocol 使用Merkle tree來實作這一點，

第一個版本的Stratum 使用Merkle tree來實作挖礦作業的高效分發：

• Pool server為每個礦工節點提供構建block所需的block header elements——如部分Merkle tree，以及the branches calculated for all other transactions except the Coinbase transaction，【注意Coinbase transaction為一種用于支付挖礦獎勵的特殊交易】詳細示意如下：【圖中的pool data是指礦池地址等，】
  
  上圖主要包含3大部分：

• the Merkle tree template：
  1）由礦池提供給礦工，包含the pre-calculated Merkle branches for the transactions in the block (此處為96b8d，從而大大降低了礦工的帶寬和計算需求)，
  2）礦工需要根據server提供的coinbase template構建合適的coinbase transaction，并將該coinbase transaction插入到Merkle tree template中，
  3）若插入的coinbase transaction使得最終的Merkle root hash值（為一個合適小的值）匹配區塊鏈網路的難度級別，則該礦工就為贏家，

• the Coinbase template：
  1）由礦池提供，由礦工來自主填寫相應的nonce和extranonce field，

• the search for the nonce(s)
  1）當將coinbase template插入到Merkle tree template中時，通過嘗試不同的nonce和extranonce值，直到某個block hash命中網路難度目標時，則成功了，【詳細見 Bitcoin block hashing 演算法】
  2）若礦工為Merkle template找到了滿足網路hash難度的nonce值，就可將其提交給礦池，
  在coinbase template中包含了礦池地址，以保證礦池可收到相應的區塊獎勵，以分發給所有礦工，

總之，此處，將Merkle tree用于分發部分解決方案（預先計算的Merkle tree branches和coinbase template），同時允許不同的分布式節點獨立作業，以嘗試找到缺少部分的解決方案（coinbase交易的nonce以構建可接受的PoW hash值），通過將礦池地址嵌入到模板中，可確保所有分布式節點都為共同目標做出貢獻，并且可以共享獎勵，

4. AWS Dynamo DB中的Merkle tree

Dynamo DB 為亞馬遜分布式云資料庫，其架構設計見：

• 2007年 Dynamo: Amazon’s Highly Available Key-value Store

在該論文中的第4.7節，提及了使用Merkle tree來高效同步差異節點，

5. ZFS分布式檔案系統中的Merkle tree

ZFS 為一種分布式檔案系統，支持資料spread over multiple volumes，

ZFS借助Merkle tree來保證資料的完整性，

ZFS uses Merkle trees to checksum data, to identify issues where some part of the data written to, or read from, disk is corrupted (or misread etc.)

6. Git Version Control系統中的Merkle tree

Git Version Control系統 中構建了 directed acyclic graph (DAG) 來管理commit：【可將該DAG看成是一種特殊的Merkle tree】

參考資料

[1] Teemu Kanstrén 2021年2月16日 medium博客 Merkle Trees: Concepts and Use Cases