Merkle Tree 雜湊樹 — 建樹 / Merkle proof / 防篡改

想像你從網路下載了一部由上千個小分塊組成的大檔案，想確認「其中第 372 塊」沒被人偷偷改過——難道要把整份檔案重新算一次雜湊比對嗎？ Merkle Tree（雜湊樹）給的答案是：不用。把每個資料區塊先各自算出一個雜湊（指紋），再兩兩往上合併，最後收斂成單一的 root hash。這個 root 就像整份資料的「總指紋」：只要任何一塊被改動一個位元，沿途每一層的雜湊、直到 root 都會跟著變—— 這就是 git 的 commit、區塊鏈的交易、BitTorrent 分塊校驗背後共同的防篡改機制。

更妙的是驗證：要證明「某個區塊確實屬於這個 root」，你不需要整棵樹，只要那條路徑上每一層的兄弟雜湊—— 對 n 個區塊只需 O(log n) 個。這串兄弟雜湊就叫 Merkle proof（audit path）。下面這棵固定的 4 區塊小樹會依序帶你走三步： ① 建樹（葉子雜湊 → 逐層合併 → root）、② Merkle proof（用 2 個兄弟雜湊驗證某區塊屬於 root）、 ③ 篡改（改一個葉子，看它如何沿路把 root 整個掀翻）。

教學誠實揭露：本頁的雜湊用「決定性教學雜湊」H(str)=逐字元 x=(x*31+code) mod 大質數，再取低 16 位當 4 位 16 進位短碼顯示（方便在小圓圈裡看清楚）。它不是密碼學雜湊——真實的 git／區塊鏈用的是 SHA-256。這裡示範的是 Merkle Tree 的結構性質（改一葉 → root 全變、proof 只需 O(log n) 兄弟），這些性質與雜湊的密碼學強度無關；教學雜湊只是讓你把每一步的值看得一清二楚。資料區塊固定為 A B C D，播放軌跡決定性（每次重播完全一致）。

Merkle Tree 建樹 / Merkle proof / 防篡改

這棵樹用堆積式陣列索引表示（與 Min-Heap 同款）：root 是索引 0、兩個內部節點是 1／2、四個葉子是 3～6，節點 k 的左子固定為 2k+1、右子 2k+2、父為 (k-1)/2。建樹時，四個葉子先各自算 leafHash = H("L"+資料)，再由下而上把每對兄弟合併成 parentHash = H("B"+左+"-"+右)，直到 root。 Merkle proof 對 data[1]="B" 示範：沿葉往上收集每一層的兄弟雜湊（本樹高 2，只需 2 個），再用它們逐層重算，得到的值若等於原 root 就證明 B 確實屬於這個 root——全程不需碰其他子樹。篡改則把 data[2] 從 "C" 改成 "X"，你會看到葉子雜湊先變，接著沿「葉 → root」每個祖先被迫重算，root 最終從 2f5f 變成 2da6，與原 root 不符即代表偵測到竄改。

固定示範：資料區塊 A B C D → ① build（4 葉雜湊 + 3 次合併）→ ② verify(data[1]="B")（收集 2 個兄弟 → 逐層重算 → 比對 root）→ ③ tamper(data[2]:"C"→"X")（沿路徑重算 → root 2f5f→2da6）。

三階段腳本

build：葉子 leafHash("A"/"B"/"C"/"D") → 由下而上合併兩對兄弟 → root
verify：對 data[1]="B" 收集 audit path（兄弟節點）→ 逐層重算 → 比對 root（Merkle proof）
tamper：data[2] "C"→"X" → 重算該葉 → 沿路徑重算祖先 → root 改變（篡改被偵測）

階段：build 雜湊運算次數（hashOps）：0

圓圈內是該節點目前的短雜湊（低 16 位，4 位 16 進位）；節點上方小字是葉子的資料區塊字元。紅色（current）= 當前正在計算／比對的節點；黃框（frontier）= 正在被合併的兩個子節點（或 proof 的兄弟）；綠色（visited）= 本階段已走過的路徑。尚未算出的節點顯示「—」。

目前 root hash —

原始 root（建樹後） —

Merkle proof 結果（尚未驗證）

資料區塊（葉子，篡改後即時反映）

audit path（Merkle proof 的兄弟雜湊）

（尚未收集）

Merkle Tree 雜湊樹（Build / Proof / Tamper）

Merkle Tree 建樹 / Merkle proof / 防篡改

三階段腳本

資料區塊（葉子，篡改後即時反映）

audit path（Merkle proof 的兄弟雜湊）

雜湊運算紀錄