默克爾樹 Merkle Tree

默克爾樹，透過將資料進行雜湊哈希運算後，逐層組合成樹狀結構，最終產生一個唯一的根雜湊值，用於高效率驗證大量資料的完整性與一致性。

Merkle Tree，默克爾樹，又稱哈希樹 Hash Tree，是由電腦科學家 Ralph Merkle 提出的一種資料結構，用於高效率驗證大量資料的完整性與一致性。

Merkle Tree 透過將資料進行雜湊哈希運算後，逐層組合成樹狀結構，最終產生一個唯一的根雜湊值，稱為 Merkle Root 默克爾根。只要任何一筆資料發生改變，最終的 Merkle Root 都會產生完全不同的結果。

比特幣區塊鏈使用 Merkle Tree 來組織區塊中的所有交易資料，並將產生的 Merkle Root 寫入區塊頭 Block Header 中，使節點能夠快速驗證交易是否存在於特定區塊，而無須下載所有交易資料。

默克爾樹基本概念

哈希值 Hash 每筆交易資料都會先經過雜湊函數運算，產生固定長度的哈希值。
葉節點 Leaf Node Merkle Tree 最底層的節點稱為葉節點，通常由單筆交易的雜湊值組成。
父節點 Parent Node 將兩個相鄰節點的哈希值連接後再次進行哈希運算，產生新的父節點哈希值。
Merkle Root 經過多層雜湊計算後，最頂端產生的唯一哈希值稱為 Merkle Root，代表整個資料集合的摘要。若任意一筆交易資料被修改，即使只改變一個字元，其雜湊值也會改變，進而影響上層所有節點，最終導致 Merkle Root 發生變化。因此，Merkle Tree 可以有效檢測資料是否遭到竄改。

比特幣區塊鏈 每個區塊內的所有交易都會建立成一棵 Merkle Tree，並產生唯一的 Merkle Root，記錄於區塊頭 Block Header 中。
輕量化節點 SPV Simplified Payment Verification，簡化支付驗證節點，可以透過 Merkle Proof 默克爾證明驗證交易是否存在，而不需要下載完整區塊鏈資料。
資料完整性驗證 大型資料庫、雲端儲存系統及分散式系統常利用 Merkle Tree 驗證資料是否一致。
版本控制系統 部分版本控制與分散式儲存系統利用類似 Merkle Tree 的結構追蹤檔案變更與驗證資料完整性。

交易雜湊生成 區塊中的每筆交易資料先經過雜湊函數運算，產生各自的交易哈希值。
節點配對 將相鄰的兩個交易雜湊值組合後，再次進行雜湊運算，產生上一層父節點。
逐層向上計算 重複進行節點組合與雜湊運算，直到產生唯一的頂層節點。
產生 Merkle Root 最終得到的頂層雜湊值即為 Merkle Root，代表整個交易集合。
Merkle Proof 驗證 當需要驗證某筆交易是否存在於區塊中時，只需提供該交易相關路徑上的少量雜湊值，即可驗證其是否屬於指定的 Merkle Root。

假設一個區塊包含四筆交易： Transaction A Transaction B Transaction C Transaction D
第一層： Hash(A) Hash(B) Hash(C) Hash(D)
第二層： Hash(Hash(A)+Hash(B)) Hash(Hash(C)+Hash(D))
第三層： Merkle Root Hash ( Hash(Hash(A)+Hash(B)) + Hash(Hash(C)+Hash(D)) ) 如果 Transaction A 的內容發生改變： Transaction A → Transaction A'
則： Hash(A) ≠ Hash(A') 進而導致： Hash(Hash(A)+Hash(B)) 改變
最終： Merkle Root 也會完全改變。

因此，只需比較 Merkle Root 是否一致，即可快速確認整個交易集合是否遭到修改。