問題：要證明你在一本你扛不動的帳簿裡
把村裡的帳本想成一本已經長到像一棟樓那麼大的書。每一筆曾經發生的付款都寫在它某一頁裡。你昨天付了一小筆錢，想要證明它確實被記下來了——但你身上只有一支手機，那本書卻重得像一輛卡車。為了核對一行字而把整本書抄一遍，荒謬至極。然而這正是加密錢包的處境：一個 比特幣 或 以太坊 區塊可以裝下數百甚至上千筆交易，而它背後的鏈更裝著數以億計的交易。你的手機不可能存下這一切，卻仍然得確認「沒錯，我那 0.2 ETH 確實進了第 18,000,000 號區塊」。
Merkle 樹是由 Ralph Merkle 於 1979 年提出的資料結構，正是它讓上述事情成為可能。訣竅一句話講完：你不去比對整本書，而是去比對一個極小的數字——整個網路早已對它取得共識——也就是 Merkle 根，然後證明你的交易能「向上濃縮」成的，恰好就是那個數字。你需要的證明只有幾百位元組，無論區塊多大都一樣。
一對一對地蓋出一棵 Merkle 樹
我們用四筆交易 A、B、C、D 來蓋一棵。全程以 `H(x)` 表示「x 的雜湊」。（比特幣其實會把 SHA-256 連做兩次——寫作 SHA-256d——但結構完全一樣，所以我們就寫成 `H`。）這棵樹由下往上長：先把每筆交易雜湊成一片葉子，再不斷把成對的節點一起雜湊，直到頂端只剩下一個值為止。
- 把每筆交易雜湊成一片葉子。 HA = H(A)、HB = H(B)、HC = H(C)、HD = H(D)。四片葉子，每片 32 位元組。
- 把葉子成對雜湊。 HAB = H(HA ‖ HB)、HCD = H(HC ‖ HD)，其中 ‖ 表示「把兩段位元組串接起來，再雜湊」。每兩片葉子各自合成一個父節點。
- 再把這對父節點雜湊。 ROOT = H(HAB ‖ HCD)。最後只剩一個值站著——這就是 Merkle 根。它是同時涵蓋全部四筆交易的 32 位元組指紋。
# H(x) = hash of x. || means "join the two byte strings, then hash".
function merkle_root(transactions):
layer = [ H(tx) for tx in transactions ] # the leaf row
while len(layer) > 1:
if len(layer) is odd:
layer.append(layer[-1]) # duplicate the lonely last node
parents = []
for i in range(0, len(layer), 2):
parents.append( H(layer[i] || layer[i+1]) )
layer = parents
return layer[0] # the Merkle root如果某一列的節點數是奇數——比方說五個——怎麼辦？常見的做法（比特幣採用的）是把最後一個節點複製一份，讓它和自己配對，正如上面的虛擬碼所示。這是個小細節，卻曾經咬傷過真實的鏈，我們會在結尾看到。
Merkle 證明：一條由兄弟節點鋪成的路徑
魔法就在這裡。要證明交易 B 在這棵樹裡，你不需要 C、D，甚至連 A 的完整交易都不需要。你只需要在 B 一路往上抵達根的途中，站在它旁邊的那些雜湊——也就是路徑上的兄弟節點。對我們這棵四葉子的樹，B 的證明就只有兩個雜湊：HA（B 在葉子層的兄弟）與 HCD（再上一層的兄弟）。就這樣。
- 從自己的葉子出發：h = H(B)。
- 證明告訴你 HA 在左邊，於是合併：h = H(HA ‖ h) = H(HA ‖ HB) = HAB。
- 證明告訴你 HCD 在右邊，於是合併：h = H(h ‖ HCD) = H(HAB ‖ HCD) = ROOT。
- 把你算出的 h 與網路早已信任的那個根比對。若兩者相符，就可被證明 B 在這棵樹裡——而你從頭到尾沒看過 A、C、D。
# proof = ordered list of (sibling_hash, position), from leaf up to root
function verify(tx, proof, known_root):
h = H(tx) # start at our leaf
for (sibling, position) in proof:
if position == "left": # sibling sits on the left
h = H(sibling || h)
else: # sibling sits on the right
h = H(h || sibling)
return h == known_root # true -> tx is provably included算一下工作量。四片葉子只需要 2 道雜湊。規律就是 log₂(n)：一棵有 n 片葉子的樹，其證明深度大約是 log₂(n) 個兄弟雜湊。1,024 筆交易的區塊只需 10 個雜湊的證明；1,048,576（約一百萬）筆的也只需 20 個雜湊。每個 32 位元組，就是用一份 640 位元組的證明，在一百萬筆交易中釘出特定的一筆——相較於把它們全部下載要好幾 MB。這正是 Merkle 樹無所不在的原因。
為什麼你偽造不出一個證明
假設你想騙一個錢包，讓它接受一筆從未出現在區塊裡的交易 X。你得交給它一串兄弟雜湊，使它們向上摺疊後仍然得出網路所共識的那個根。但根不是你能挑的——它早已固定。於是你必須替 H 找到能與路徑上真實中間值碰撞的輸入。在 SHA-256 中找到這樣的碰撞，工作量約在 2¹²⁸ 量級——完全不可行。每一個 Merkle 證明的安全性，全然繫於底層雜湊的抗碰撞性（以及第二抗原像性）。雜湊一破，樹就破；否則這個證明牢靠得像數學一樣。
根住在哪裡：區塊標頭與輕用戶端
如果根擱在無關緊要的地方，Merkle 樹不過是個聰明的玩具。它真正的職責是：根被存進區塊標頭裡。在比特幣中，標頭只有 80 位元組，其中 32 個就是該區塊內所有交易的 Merkle 根。當礦工與節點對某個標頭取得共識時，他們就是透過那一個 32 位元組的欄位，對整套交易取得了共識——沒有誰需要逐筆去比對交易。
正是這一點，讓輕用戶端（中本聰在比特幣白皮書第 8 節稱之為 SPV——簡化付款驗證）能住在一支手機裡。它只下載那串 80 位元組的標頭，而非整個區塊。要核對你的付款，它向任何一個全節點索取你那筆交易的 Merkle 證明（一條「分支」），再拿它去和對應標頭裡的根驗證。最美的一點是：你不必信任那個給你證明的節點。 說謊的節點偽造不出有效的證明——錯的證明根本摺不出標頭裡的那個根。你唯一要信任的，是那串標頭鏈本身（背後累積最多工作量或質押的那一條）。
以太坊加了個轉折。它的標頭帶著三個根——`transactionsRoot`、`stateRoot` 與 `receiptsRoot`——每一個都是一棵 Merkle Patricia 字典樹的根，那是把 Merkle 樹與「鍵→值」查找結合起來的結構。這個結合讓你不只能證明「交易 X 被包含進來了」，還能證明「帳戶 X 此刻在世界狀態中的餘額是 Y」，而且能高效地更新單一帳戶，無須重蓋整棵樹。核心概念依舊相同——一個替整個結構留下指紋的根——只是從一份扁平清單，擴展成了一個完整的鍵值資料庫。
真實的鏈踩過的坑
那條看似無害、針對奇數列「複製最後一個節點」的規則，藏著一道利刃。2012 年，比特幣發現了 CVE-2012-2459：只要以恰當的方式複製交易，攻擊者就能蓋出兩份不同的交易清單，卻產出相同的 Merkle 根。由於節點部分是用這個根來索引區塊的，惡意的對等節點可以散播一個被竄改過、無效的有效區塊副本；接受了它的節點會把真正區塊的雜湊標記為壞掉並拒絕它——形成一次阻斷服務攻擊。修法是明確拒絕任何 Merkle 樹中含有重複雜湊配對的區塊。這提醒我們：樹裡一行邊界情況的疏漏，可能變成全網級的漏洞。
再補兩個實務要點。其一，比特幣用雙重 SHA-256 雜湊，並以內部小端序的位元組順序儲存雜湊，所以若天真地把區塊瀏覽器上看到的十六進位直接串接，會算出錯誤的根——這是經典的初次實作 bug。其二，如果你把葉子排序後依序存放，會多得到一項好處：排序過的 Merkle 樹還能證明不包含（「這個位址絕對不在集合裡」），方法是出示它本該落在其間的左右兩個鄰居。