Merkle Tree 入門
要確保整串非常長的資料（例如區塊鏈）的完整性，理論上，我們可以有幾種方法：
- 直接將整條資料 Hash 成一個 hash value
- 將資料斬成一個一個區塊 (block)，然後下一個 block 記低上一個 block 的 hash value
- 將資料斬成一個一個區塊 (block)，然後算出每個 block 的 hash value，最後以 binary tree 形色不斷向上計算，直至得到最後一個 hashed value，又稱為 Merkle Root
Merkle Tree 指就是第三種方法。當 block 數量為雙數時，Merkle Root 可以這樣得出 [1]：
簡單而言，就是計算 L1 - L4 的 Hash，得出 H(L1) - H(L4)，
然後計算 H0 = H(H(L1) || H(L2)) 和 H0 = H(H(L3) || H(L4))，
最後計算 Merkle Root = H(H0 || H1)。
當 Block 數為單數時，以上圖為例，假設只有 L1-L3，我們就可以：
假設有一個 block L4 = L3，
然後故技重施，最後得出 Merkle Root。
當 Block 數為單數，並導致上一層也是單數，我們也同樣故技重施，直至單數消失。
這種架構，對於本身資料結構已經是 linked list 的區塊鏈 (Blockchain) 來講特別方便。
因為不需要花額外的工作處理資料切割，就能直接用這個方法，確保資料完整性。
而且當區塊鏈不斷變長，我們也不需要重新計算舊的區塊，變相可以刪掉舊區塊節省空間。
（例如當加入 L5， 我們並不需重新計過 H(L1) ~ H(L4)，也可以找到 Merkle Root）
Merkle Tree 在 Bitcoin 的應用
作為第一個引人注目的 Blockchain 應用，Bitcoin 中同樣引入了 Merkle Tree，
而它的出發點同樣是想保護整條 Block 的完整性。
我們可先看一下 Bitcoin 的 header 架構 [2]：
| Bytes | Name | Data Type | Description |
|---|---|---|---|
| 4 | version | int32_t | The block version number |
| 32 | previous block header hash | char[32] | A SHA256(SHA256()) hash in internal byte order of the previous block’s header. This ensures no previous block can be changed without also changing this block’s header. |
| 32 | merkle root hash | char[32] | A SHA256(SHA256()) hash in internal byte order. The merkle root is derived from the hashes of all transactions included in this block, ensuring that none of those transactions can be modified without modifying the header. |
| 4 | time | uint32_t | The block time is a Unix epoch time when the miner started hashing the header (according to the miner). |
| 4 | nBits | uint32_t | An encoded version of the target threshold |
| 4 | nonce | uint32_t | An arbitrary number miners change to modify the header hash in order to produce a hash less than or equal to the target threshold. |
當中可見，Previous Block Header Hash 是用來確保上一個 block 的合法性。理論上，我們如果要確定任何一個 block 是否合法，最簡單的方法，就是用這個欄目，一直追溯直至第一個 block（又稱作 Coinbase）即可。但這種做法，將會耗費大量時間，所以理論上可行，實際上卻十分困難。
Bitcoin 的發明者 Satoshi Nakamoto 似乎一早就發現這個情況，所以他增加了 Merkle Root Hash 這個項目。自此，如果你要確認某一個 block，你只需要重新找出該 block 的 H(block)，然後向上推演，計出 Merkle Root，再比對 chain head 中的 Merkle Root Hash 是否相等即可。根據 [3] 所指，要推算任何一個 block，理論上只需要
2*log2(N) 次計算，變相快速有效得多。Merkle Tree 其他應用
Merkle Tree 提供一種便捷的驗證方法，所以一直有不少地方均用到。
例如 Tor，Git，SEMUD [4] 等等。
---
參考：
[1] - https://en.wikipedia.org/wiki/Merkle_tree#/media/File:Hash_Tree.svg
[2] - https://bitcoin.org/en/developer-reference#block-headers
[3] - Mastering Bitcoin by Andreas M. Antonopoulos - https://www.oreilly.com/library/view/mastering-bitcoin/9781491902639/ch07.html
[4] - http://ieeexplore.ieee.org/document/8264846/
