Merkle 樹與 SPV 驗證

進階 🏷️ bitcoin, merkle, spv, technical 計算中...

理解比特幣區塊頭的 Merkle 根與簡化支付驗證。

Merkle 樹與 SPV 驗證：數學證明、形式化驗證與實作深度分析

比特幣區塊鏈的核心數據結構之一是 Merkle 樹（Merkle Tree），它將大量交易資料聚合成一個簡潔的根哈希值，使輕客戶端（SPV）能夠在不下載完整區塊的情況下驗證交易的有效性。本文從密碼學、離散數學、資訊理論和形式化驗證的角度，深入分析 Merkle 樹的數學基礎、驗證協議、攻擊防禦機制，並提供完整的實作細節與學術論文參考。

##kle 樹 Mer的密碼學基礎

哈希函數的數學性質

Merkle 樹的建造基於密碼學哈希函數的核心性質。理解這些數學假設是分析 Merkle 樹安全性的前提。

密碼學哈希函數的形式化定義：

一個安全的哈希函數 H: {0,1}* → {0,1}^n 必須滿足以下計算困難性假設：

1. 單向性（Preimage Resistance）
   ∀y ∈ {0,1}^n，找不到多項式時間算法 A 使得 A(y) = x 且 H(x) = y
   （除非以可忽略的概率）

2. 抗第二原像（Second Preimage Resistance）
   已知輸入 x ∈ {0,1}*，找不到多項式時間算法 A 使得
   A(x) = x' 且 x ≠ x' 且 H(x) = H(x')

3. 抗碰撞性（Collision Resistance）
   找不到多項式時間算法 A 使得 A() = (x, x') 且 x ≠ x' 且 H(x) = H(x')

比特幣使用的 SHA-256 哈希函數：
- 輸出長度：256 位元（32 位元組）
- 輸入長度：最多 2^64 - 1 位元
- 設計標準：NIST FIPS 180-4

安全假設：
如果 SHA-256 滿足上述三個性質，則 SHA-256 是計算安全的
（即在現有計算能力下無法有效破解）

比特幣交易的哈希計算

比特幣中的 Merkle 樹使用交易的哈希值（txid）作為葉節點。txid 的計算有特定的細節需要注意。

交易 ID（txid）計算細節：

txid = SHA256(SHA256(transaction_data))

重要細節：
1. 輸入數據：交易的序列化格式（wire format）
2. 雙重哈希：用於防止長度擴展攻擊（length-extension attack）
3. SegWit 之前：txid 基於完整交易數據
4. SegWit 之後：txid 仍基於 legacy data，但隔離見證數據不參與計算

交易序列化結構（SegWit 前）：
┌─────────────────────────────────────────────────────────────┐
│  版本號 (4 bytes)  │  輸入數量 (1-9 bytes)                │
├─────────────────────────────────────────────────────────────┤
│  輸入列表 (可變)    │  輸出數量 (1-9 bytes)                │
├─────────────────────────────────────────────────────────────┤
│  輸出列表 (可變)    │  鎖定時間 (4 bytes)                  │
└─────────────────────────────────────────────────────────────┘

輸入數據必須完全匹配，包括：
- 輸入數量
- 每個輸入的 previous txid 和輸出索引
- 序列號
- 輸出數量和內容
- 鎖定時間

Merkle 樹的數學結構

樹結構的形式化定義

Merkle 樹是一種二叉哈希樹，其數學結構可以用集合論和圖論精確定義。

Merkle 樹的形式化定義：

設 T 為 Merkle 樹，定義如下：

1. 葉節點集合
   L = {h_1, h_2, ..., h_n}
   其中 h_i = H(tx_i)，tx_i 為第 i 筆交易的 txid

2. 遞歸建構規則
   對於每個內部節點 v，其哈希值為：
   H_v = H(H_left || H_right)

   其中：
   - H_left：左子節點的哈希值
   - H_right：右子節點的哈希值
   - ||：字節串接（concatenation）

3. 根節點
   root = H_n
   其中 H_n 是樹的頂層哈希值

4. 樹的高度
   height(T) = ⌈log₂(n)⌉ + 1
   （包含根節點和葉節點層）

數學性質：

性質 1：確定性
   對於固定的交易集合 {tx_1, ..., tx_n}，
   Merkle 根 root 是唯一確定的

性質 2：單向性
   已知 root，無法推導出具體的交易內容
   （除非利用碰撞攻擊）

性質 3：可驗證性
   已知 root 和 Merkle proof，
   可以驗證特定交易包含於區塊中

奇數節點的處理

當交易數量不是 2 的幂時，需要特殊的處理機制。這是 Merkle 樹建構中的一個重要細節。

奇數節點處理機制：

比特幣採用「複製最後一個節點」的策略：

情況 1：n = 2^k（偶數個交易）
   直接成對計算：
   h_0 = H(tx_0 || tx_1)
   h_1 = H(tx_2 || tx_3)
   ...

情況 2：n = 2^k + 1（奇數個交易）
   最後一個節點複製湊成偶數：
   h_0 = H(tx_0 || tx_1)
   h_1 = H(tx_2 || tx_3)
   ...
   h_{m-1} = H(tx_{n-2} || tx_{n-1})
   h_m = H(tx_{n-1} || tx_{n-1})  // 複製最後一個

情況 3：n = 2^k - 1（幾乎滿的樹）
   仍需複製最後一個節點：
   h_{m-1} = H(tx_{n-2} || tx_{n-1})
   h_m = H(tx_{n-1} || tx_{n-1})

數學表示：
   設 k = ⌈log₂(n)⌉
   定義擴展的交易集合 L'：
   |L'| = 2^k

   對於 i ≥ n：h_i = h_{n-1}（複製最後一個）

實例：
   3 筆交易：tx_0, tx_1, tx_2
   擴展為 4 個葉節點：
   h_0 = H(tx_0)
   h_1 = H(tx_1)
   h_2 = H(tx_2)
   h_3 = h_2  // 複製

   第一層內部節點：
   h_{0,1} = H(h_0 || h_1)
   h_{2,3} = H(h_2 || h_3)

   Merkle 根：
   root = H(h_{0,1} || h_{2,3})

Merkle Proof 的數學原理

包含性證明

Merkle proof（又稱 Merkle path）是讓驗證者確認特定交易包含於 Merkle 樹中的關鍵數據結構。

Merkle Proof 的數學定義：

設：
- T：Merkle 樹
- tx：目標交易
- root：Merkle 根
- path(tx)：從葉節點到根的路徑

Merkle proof 結構：
path(tx) = [sibling_0, sibling_1, ..., sibling_{h-1}]

其中：
- sibling_0：葉節點的兄弟節點哈希
- sibling_1：上一層的兄弟節點哈希
- ...
- sibling_{h-1}：根節點的兄弟節點哈希

驗證過程的數學表達：

遞推計算：
h_0 = H(tx)  // 計算目標交易的哈希

對於 i = 0 到 h-1：
   如果 tx 在左側：
      h_{i+1} = H(h_i || sibling_i)
   如果 tx 在右側：
      h_{i+1} = H(sibling_i || h_i)

最終驗證：
   h_h == root ? 接受 : 拒絕

正確性證明：

定理：Merkle proof 驗證成功當且僅當目標交易包含於區塊中

證明：
1. 假設驗證成功，即計算得到的 h_h = root
2. 由於 H 是抗碰撞的，、路徑上的每個哈希值都與原樹一致
3. 因此，根哈希的一致性證明葉節點存在於原樹中
4. 葉節點是交易的哈希，故交易包含於區塊中 ∎

證明大小的數學分析

Merkle proof 的大小直接影響輕客戶端的頻寬需求。這裡我們分析證明大小的複雜度。

Merkle Proof 複雜度分析：

空間複雜度：
   |proof| = O(log₂(n)) 個哈希值

   每個哈希：32 bytes（SHA-256 輸出）
   總大小：32 × log₂(n) bytes

不同交易數量的證明大小：

┌──────────────┬─────────────┬──────────────────┐
│   交易數 n   │  樹深度 h   │  Proof 大小      │
├──────────────┼─────────────┼──────────────────┤
│            2 │           1 │   32 bytes       │
│            4 │           2 │   64 bytes       │
│           16 │           4 │  128 bytes       │
│          256 │           8 │  256 bytes       │
│        1,000 │          10 │  320 bytes       │
│       10,000 │          14 │  448 bytes       │
│      100,000 │          17 │  544 bytes       │
│    1,000,000 │          20 │  640 bytes       │
└──────────────┴─────────────┴──────────────────┘

比特幣區塊平均包含約 2,500 筆交易
→ 典型 Merkle proof 大小：≈ 320 bytes

與完整區塊的比較：
- 完整區塊：~1-2 MB
- Merkle proof：~320 bytes
- 頻寬節省：> 99.97%

時間複雜度：
   驗證時間：O(log₂(n)) 次哈希計算

   每次 SHA-256：~100-500 ns（在現代 CPU 上）
   典型驗證時間：< 1 微秒

比特幣的 Merkle 根結構

比特幣區塊頭中包含 Merkle 根，其結構和計算有特定的規則。

比特幣區塊頭中的 Merkle 根：

區塊頭結構（80 bytes）：
┌─────────────────────────────────────────────────────────────┐
│  版本號 (4)    │  前一區塊哈希 (32)  │  Merkle 根 (32)   │
├────────────────┼─────────────────────┼───────────────────┤
│  時間戳 (4)    │  難度目標 (4)       │  Nonce (4)        │
└─────────────────────────────────────────────────────────────┘

Merkle 根位置：第 72-103 位元組（0-indexed: 36-67）

區塊頭哈希計算：
   block_hash = SHA256(SHA256(block_header))

注意：
   Merkle 根是區塊頭的一部分
   區塊頭哈希用於工作量證明計算
   這創造了區塊交易與工作量證明的綁定

完整建構流程：

1. 計算每筆交易的 txid
   txid_i = SHA256(SHA256(serialized_tx_i))

2. 構建葉節點層
   L_0 = [txid_0, txid_1, ..., txid_{n-1}]

3. 遞迴計算內部節點
   for i = 0 to h-1:
      for j = 0 to |L_i|/2 - 1:
         L_{i+1}[j] = SHA256(SHA256(L_i[2j] || L_i[2j+1]))

4. 根節點即為 Merkle 根
   merkle_root = L_h[0]

SPV 驗證的協議與安全性

簡化支付驗證（SPV）的原理

SPV（Simplified Payment Verification）是中本聰白皮書中提出的輕客戶端驗證方案。

SPV 驗證的白皮書定義（中本聰，2009）：

「節點可以不保存完整區塊鏈而驗證支付。節點只需保存區塊頭，
並連接至目標交易的 Merkle 分支。不需要保存完整的交易歷史。」

SPV 客戶端的工作流程：

1. 獲取區塊頭
   從全節點下載所有區塊頭（~80 bytes × 區塊數）
   驗證工作量證明

2. 請求 Merkle proof
   向全節點發送 getdata 訊息，請求：
   - 目標交易的 txid
   - 該交易的 Merkle proof

3. 驗證證明
   使用區塊頭中的 Merkle 根
   驗證交易確實包含於區塊中

4. 檢查確認數
   根據所需安全級別，等待足夠的區塊確認

SPV 的安全性假設：

假設 1：攻擊者無法控制大多數算力
   否則可以創建虛假的區塊頭

假設 2：網路中至少有部分誠實全節點
   否則無法獲取真實的 Merkle proof

假設 3：哈希函數是抗碰撞的
   否則可以偽造 Merkle proof

SPV 驗證的完整協議

SPV 驗證的詳細協議：

客戶端（SPV 節點）：

1. 初始化
   - 下載所有區塊頭
   - 建立區塊頭鏈
   - 驗證每個區塊的工作量證明

2. 交易查詢
   - 維護感興趣的交易列表（watch-only）
   - 向相鄰全節點發送 getdata 請求

3. 請求格式（Bitcoin P2P 協議）：
   MSG_FILTERED_BLOCK + PartialMerkleTree

4. 驗證步驟
   algorithm SPV_Verify(tx, block_header, merkle_proof):
      root = block_header.merkle_root
      computed_root = merkle_proof.compute_root(tx.txid)
      if computed_root != root:
         return REJECT
      if merkle_proof.num_merkle_branches > desired_confirmations:
         return WAIT_FOR_MORE_CONFIRMATIONS
      return ACCEPT

全節點（Server）：

1. 接收請求
   - 解析 getdata 訊息
   - 確認請求的交易存在於區塊中

2. 建構 Merkle proof
   - 找到目標交易在 Merkle 樹中的位置
   - 收集路徑上的所有兄弟節點
   - 編碼為 PartialMerkleTree 格式

3. 發送回應
   - 區塊頭
   - Merkle proof
   - 交易數據（可選）

PartialMerkleTree 編碼格式：

┌─────────────────────────────────────────────────────────────┐
│  交易數量 (varint)                                         │
├─────────────────────────────────────────────────────────────┤
│  標誌位元組 (flags) - 每個節點的標記                        │
├─────────────────────────────────────────────────────────────┤
│  哈希列表 (hashes) - 內部和葉節點哈希                      │
└─────────────────────────────────────────────────────────────┘

SPV 的安全性分析

SPV 安全性分析：

威脅模型：

威脅 1：虛假區塊頭攻擊
   攻擊者向 SPV 節點提供假的區塊頭鏈
   防禦：SPV 節點應連接多個獨立全節點
   防禦：使用檢查點（checkpoint）機制

威脅 2：Merkle proof 欺騙
   攻擊者提供指向不存在交易的 Merkle proof
   防禦：SPV 節點應驗證證明結構
   防禦：驗證交易數量合理性

威脅 3：選擇性區塊隱藏
   攻擊者隱藏特定區塊不傳給 SPV 節點
   防禦：SPV 節點應請求特定區塊
   防�體：比較不同節點的區塊頭

威脅 4：Eclipse 攻擊
   攻擊者壟斷 SPV 節點的所有連接
   防禦：維護多個連接
   防禦：使用可信的區塊頭來源

安全建議：

1. 連接數量
   至少連接 8-10 個獨立全節點

2. 區塊頭驗證
   驗證每個區塊頭的工作量證明
   使用預設的檢查點

3. 確認數要求
   小額交易：1-3 確認
   中額交易：6 確認
   大額交易：10+ 確認

4. 額外驗證
   對於大額交易，獨立廣播交易
   等待足夠確認後再確認

形式化驗證

Merkle 樹的形式化定義

學術文獻中對 Merkle 樹進行了嚴格的形式化驗證。

形式化驗證的數學框架：

定義 1：Merkle 樹數據類型

   type MerkleTree = Empty | Node(MerkleTree, MerkleTree, Hash)

   其中 Hash = {0,1}^256

定義 2：Merkle 路徑

   type MerklePath = List(Direction × Hash)

   其中 Direction = Left | Right

定義 3：驗證函數

   verify_inclusion(
      txid: Hash,
      proof: MerklePath,
      root: Hash,
      leaf_position: Position
   ): Bool

形式化命題：

命題 1：包含性正確性
   ∀txid, proof, root, pos:
      verify_inclusion(txid, proof, root, pos) = true
      ⇒ ∃tree: root_of(tree) = root ∧ contains(tree, txid, pos)

命題 2：拒絕欺詐
   ∀fake_proof, root:
      verify_inclusion(txid, fake_proof, root, pos) = true
      ⇒ fake_proof 是有效的 Merkle proof
      （不存在假陽性的驗證結果）

命題 3：證明最小性
   Merkle proof 的大小是 Ω(log₂(n))
   （資訊理論下界）

學術驗證項目

主要的 Merkle 樹形式化驗證項目：

1. Coq 驗證（法國國家科學研究院，2014）
   - 項目：Merkle 樹的證明助手驗證
   - 成果：完整的包含性/排斥性證明
   - 工具：Coq 證明助手

2. Isabelle/HOL 驗證（劍橋大學，2016）
   - 項目：區塊鏈數據結構的驗證
   - 成果：Merkle 樹的數學證明
   - 工具：Isabelle/HOL

3. CertiK 驗證（2019）
   - 項目：智能合約中的 Merkle 驗證
   - 成果：防止常見的實現漏洞
   - 工具：CertiK 形式化驗證框架

4. K 框架驗證（2018）
   - 項目：比特幣腳本的形式化語義
   - 成果：Merkle 證明的區塊鏈整合驗證
   - 工具：K 框架

常見問題與解答（FAQ）

基本概念問題

Q1：為什麼比特幣使用 Merkle 樹而不是簡單的哈希列表？

A1：Merkle 樹的主要優勢：

1. 效率
   - 驗證單筆交易：O(log n) vs O(n)
   - 10,000 筆交易：~14 次哈希 vs 10,000 次

2. 隱私
   - SPV 節點可以驗證交易存在
   - 無需知道其他交易的詳細資訊
   - 可以隱藏未包含的交易

3. 完整性
   - 支持「pruned」節點模式
   - 可以刪除舊交易但保持驗證能力

4. 歷史
   - 早期比特幣客戶端資源受限
   - Merkle 樹大幅降低存儲需求

Q2：Merkle 根如何與工作量證明綁定？

A2：綁定機制：

1. Merkle 根是區塊頭的一部分
2. 區塊頭哈希用於工作量證明計算
3. 如果修改任何交易，Merkle 根會改變
4. 工作量證明必須重新計算
5. 因此，交易的 commitment 與工作量證明不可分離

Q3：可以從 Merkle 根反推交易內容嗎？

A3：不能（假設哈希函數安全）：

1. 單向性：已知輸出無法推導輸入
2. 抗碰撞：無法找到不同輸入產生相同輸出
3. 資訊理論：root 只包含 256 位元資訊
4. 交易總資訊量遠大於 256 位元

理論上，如果哈希函數存在碰撞，
攻擊者可能構造不同的交易集合產生相同根
這就是為什麼抗碰撞性如此重要

安全性問題

Q4：Merkle 樹有哪些已知的攻擊向量？

A4：主要攻擊向量：

1. 哈希碰撞攻擊
   - 如果 SHA-256 被破解，可偽造 Merkle proof
   - 目前認為不可行（2^128 攻擊複雜度）

2. 延展性攻擊（SegWit 前）
   - 交易 ID 不包含簽名
   - 攻擊者可以修改未簽名的欄位
   - 導致不同的 txid 但相同的 Merkle 證明
   - SegWit 修復了此問題

3. 選擇性拒絕服務
   - 攻擊者可以選擇不傳播特定區塊
   - 導致部分節點無法驗證特定交易
   - 需要連接多個獨立節點防禦

Q5：SPV 節點如何防禦虛假 Merkle5：防禦策略：

1 根？

A. 驗證工作量證明
   每個區塊頭必須滿足目標難度

2. 使用檢查點
   預先存儲已知正確的歷史區塊頭
   例如：比特幣區塊 #500,000 的區塊頭

3. 多源驗證
   連接多個獨立的全節點
   比較來自不同來源的 Merkle 根

4. 活躍監控
   監控區塊頭鏈的連續性
   檢測可能的攻擊跡象

Q6：量子計算機可以破解 Merkle 樹嗎？

A6：取決於攻擊類型：

1. 對 SHA-256 的 Grover 攻擊
   - 提供 √N 加速（平方根加速）
   - 經典：2^128 步驟
   - 量子：2^64 步驟
   - 結論：仍然不安全但風險增加

2. 對橢圓曲線的 Shor 攻擊
   - 與 Merkle 樹無直接關係
   - 影響比特幣地址的私鑰
   - 使用一次性地址可以緩解

3. 緩解措施
   - 升級到 SHA-3 或 SHAKE
   - 使用後量子簽名方案
   - 比特幣社群正在討論中

實作問題

Q7：如何驗證收到的 Merkle proof 是正確的？

A7：驗證步驟：

1. 解析 proof 結構
   提取路徑上的兄弟節點
   確定目標交易的位置

2. 計算目標交易的哈希
   txid = SHA256(SHA256(serialized_tx))

3. 沿路徑計算
   for each (position, sibling_hash) in path:
      if position == LEFT:
         current = SHA256(current || sibling_hash)
      else:
         current = SHA256(sibling_hash || current)

4. 比較根哈希
   computed_root == block_header.merkle_root ?

Q8：為什麼有時會收到「無效的 Merkle proof」錯誤？

A8：常見原因：

1. 區塊重組（Reorg）
   - 區塊被確認後可能被撤銷
   - 需要等待足夠確認
   - 請求新區塊的 proof

2. 交易不存在
   - 請求的交易可能從未被確認
   - 或已被確認但區塊被重組

3. 編碼錯誤
   - Proof 格式解析錯誤
   - 字節序（endianness）問題

4. 節點同步問題
   - 全節點的區塊鏈可能落後
   - 嘗試連接其他節點

Q9：Bloom 濾波器如何與 Merkle 樹配合使用？

A9：Bloom 過濾器的作用：

1. SPV 節點可以使用 Bloom 過濾器
   請求符合特定模式的所有交易

2. 隱私權衡
   - 輕量級：只暴露感興趣的地址模式
   - 犧牲：可能收到無關交易
   - 安全性：依賴 Merkle 證明驗證

3. BIP-37 協議
   - CLIENT_FILTER_ADD：添加過濾模式
   - MERKLE_BLOCK：返回匹配的 Merkle proof
   - 組合使用實現隱私保護的 SPV

高級問題

Q10：Merkle 樹可以支持哪些高級功能？

A10：高級應用：

1. 簡化資料庫同步
   - 同步雙方只傳輸根哈希
   - 發現差異後使用 Merkle 證明
   - 應用：I2P 資料庫同步

2. 累加器（Accumulator）
   - 可以證明元素是集合成員
   - 比 Merkle 樹更高效
   - 實現：RSA 累加器、向量承諾

3. 可驗證延遲函數（VDF）
   - 與 Merkle 樹結合
   - 提供時間證明
   - 應用：隨機數生成

4. 零知識證明
   - Merkle 樹是 zk-SNARK 的基礎
   - 實現私有交易驗證
   - 應用：Zcash、Stellar

Q11：為什麼比特幣的 Merkle 樹不採用更高效的結構？

A11：設計權衡：

1. 歷史兼容性
   - 2009 年的設計決策
   - 需要保持向後兼容性

2. 簡單性
   - 簡單的二叉樹結構
   - 易於理解和實現
   - 減少bug風險

3. 足夠效率
   - 實際使用中效率足夠
   - 典型區塊：~2,500 交易
   - Proof 大小：~320 bytes

4. 研究表明
   - 複雜結構可能引入新攻擊向量
   - 「足夠好」是比特幣的設計原則

Q12：Merkle 樹的未來發展方向？

A12：研究方向：

1. 壓縮 Merkle 證明
   - 使用向量承諾
   - 減少頻寬需求

2. 隱私增強
   - 使用防彈證明（Bulletproofs）
   - 實現範圍證明

3. 通用化
   - Merkle 累加器
   - 支持動態集合操作

4. 量子抵抗
   - 後量子哈希函數
   - 結構升級

實作範例

完整的 Merkle Proof 驗證實現

Python 實現 Merkle Proof 驗證：

import hashlib

from typing import List, Tuple, Optional

def sha256(data: bytes) -> bytes:

"""雙重 SHA-256（比特幣標準）"""

return hashlib.sha256(hashlib.sha256(data).digest()).digest()

def merklerootfrom_proof(

txid: bytes,

proof: List[Tuple[bool, bytes]], # (isleft, siblinghash)

position: int

) -> bytes:

"""

從 Merkle proof 計算根哈希

參數：

txid: 交易的哈希（32 bytes）

proof: 兄弟節點列表

每個元素為 (方向, 哈希值)

方向 True = 目標在左側

position: 交易在區塊中的位置

"""

current = txid

for is_left, sibling in proof:

if is_left:

目標在左側：current || sibling

current = sha256(current + sibling)

else:

目標在右側：sibling || current

current = sha256(sibling + current)

更新位置（用於追踪路徑）

position //= 2

return current

def verifymerkleproof(

txid: bytes,

proof: List[Tuple[bool, bytes]],

merkle_root: bytes,

expected_index: int

) -> bool:

"""

驗證 Merkle proof 的完整性

返回：True = 有效，False = 無效

"""

計算根哈希

computedroot = merklerootfromproof(txid, proof, expected_index)

比較

return computedroot == merkleroot

def buildmerkleproof(

txids: List[bytes],

target_index: int

) -> Tuple[bytes, List[Tuple[bool, bytes]], int]:

"""

建構交易的 Merkle proof

參數：

txids: 區塊中所有交易的 txid 列表

target_index: 目標交易的索引

返回：

(txid, proof, index)

"""

if target_index >= len(txids):

raise ValueError("目標索引超出範圍")

txid = txids[target_index]

proof = []

currentindex = targetindex

current_hashes = txids[:]

建構樹直到只剩根節點

while len(current_hashes) > 1:

處理奇數情況

if len(current_hashes) % 2 == 1:

currenthashes.append(currenthashes[-1])

計算當前層

next_hashes = []

for i in range(0, len(current_hashes), 2):

left = current_hashes[i]

right = current_hashes[i + 1]

parent = sha256(left + right)

next_hashes.append(parent)

收集 proof

if i // 2 == current_index // 2:

if current_index % 2 == 0:

目標在左側

proof.append((True, right))

else:

目標在右側

proof.append((False, left))

移動到上一層

currenthashes = nexthashes

current_index //= 2

return txid, proof, target_index


JavaScript 實現（在瀏覽器中使用）：

const crypto = require('crypto');

function sha256(data) {

return crypto.createHash('sha256')

.update(crypto.createHash('sha256').update(data).digest())

.digest();

}

function verifyMerkleProof(txid, proof, merkleRoot) {

let current = txid;

for (const [isLeft, sibling] of proof) {

if (isLeft) {

current = sha256(Buffer.concat([current, sibling]));

} else {

current = sha256(Buffer.concat([sibling, current]));

}

}

return current.equals(merkleRoot);

}


Rust 實現（記憶體安全）：

use sha2::{Sha256, Digest};

fn double_sha256(data: &[u8]) -> [u8; 32] {

let mut hasher = Sha256::new();

hasher.update(data);

let first = hasher.finalize();

let mut hasher = Sha256::new();

hasher.update(first);

let result = hasher.finalize();

let mut arr = [0u8; 32];

arr.copyfromslice(&result);

arr

}

fn verifymerkleproof(

txid: &[u8; 32],

proof: &[(bool, [u8; 32])],

merkle_root: &[u8; 32],

) -> bool {

let mut current = *txid;

for (is_left, sibling) in proof {

let mut combined = [0u8; 64];

if *is_left {

combined[..32].copyfromslice(&current);

combined[32..].copyfromslice(sibling);

} else {

combined[..32].copyfromslice(sibling);

combined[32..].copyfromslice(&current);

}

current = double_sha256(&combined);

}

current == *merkle_root

}

學術論文與技術規範

原始技術規範

比特幣相關 BIP 規範：

1. BIP-37：Bloom 過濾器
   標題：Connection Bloom Filters
   作者：Mike Hearn, Matt Corallo
   日期：2012
   描述：SPV 節點如何使用 Bloom 過濾器請求交易

2. BIP-157：Compact Filter 過濾器
   標題：Compact Block Filters for SPV Clients
   作者：Olaoluwa Osuntokun, Alex Akselrod
   日期：2017
   描述：改進的 SPV 過濾方案，替代 BIP-37

3. BIP-158：Filter 類型定義
   標題：Compact Block Filters
   作者：Pieter Wuille
   日期：2017
   描述：Golomb-Rice 編碼的 Filter 格式

4. BIP-339：交易 ID 索引
   標題：Transaction Tag Indexing
   作者： Suleman Elahi
   日期：2020
   描述：支援按標籤查詢交易的索引

學術論文：

1. 中本聰的白皮書
   標題：Bitcoin: A Peer-to-Peer Electronic Cash System
   作者：Satoshi Nakamoto
   日期：2008
   URL：https://bitcoin.org/bitcoin.pdf

2. Merkle 的原始論文
   標題：Certifying Cryptographic Protocols
   作者：Ralph Merkle
   日期：1980
   描述：Merkle 樹的首次提出

3. 形式化驗證研究
   標題：A Formal Analysis of Bitcoin's Consensus
   作者：Renat Gummerus
   日期：2020
   描述：使用 TLA+ 驗證比特幣共識

4. SPV 安全性分析
   標題：An Analysis of Bitcoin SPV Security
   作者：Nicolas T. Courtois, P. S. L. M. Barrett
   日期：2015
   描述：SPV 客戶端的安全性分析

進一步閱讀資源

推薦書籍：

1. Mastering Bitcoin
   作者：Andreas Antonopoulos
   內容：比特幣技術的全面指南
   章節：第 9 章區塊鏈、第 10 章挖礦與共識

2. Bitcoin and Cryptocurrency Technologies
   作者：Narayanan, Bonneau, Felten, Miller, Goldfeder
   內容：普林斯大學加密貨幣課程教材
   章節：第 3 章共識機制

3. Grokking Bitcoin
   作者：Kalle Rosenbaum
   內容：比特幣技術的視覺化解釋
   章節：Merkle 樹章節

線上資源：

1. Bitcoin Wiki - Merkle Trees
   URL：https://en.bitcoin.it/wiki/Merkle_tree

2. BIP-37 規範
   URL：https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki

3. BIP-157 規範
   URL：https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki

4. Bitcoin Developer Guide - Merkle Blocks
   URL：https://developer.bitcoin.org/devguide/contracts.html#merkle-proofs

開源項目：

1. bcoin：Node.js 比特幣完整實現
   GitHub：https://github.com/bcoin-org/bcoin

2. Bitcoin Core：官方比特幣實現
   GitHub：https://github.com/bitcoin/bitcoin

3. btcd：Go 語言比特幣實現
   GitHub：https://github.com/btcsuite/btcd

結論

Merkle 樹是比特幣區塊鏈的核心數據結構，它在密碼學、資訊理論和分散式系統的交叉點上發揮了關鍵作用。通過本文的深入分析，我們可以得出以下核心結論：

第一，Merkle 樹的數學安全性基於 SHA-256 哈希函數的抗碰撞性。這意味著在現有的計算能力下，找到兩個產生相同哈希的輸入在計算上是不可行的。

第二，Merkle proof 提供了高效且安全的交易包含性驗證。SPV 客戶端只需要下載區塊頭（約 80 bytes per block），就能驗證任意交易是否包含於區塊中，頻寬節省超過 99.97%。

第三，Merkle 樹與工作量證明的結合創造了比特幣的不可變性。任何對歷史交易的修改都需要重新計算所有後續區塊的工作量證明，經濟上不可行。

第四，形式化驗證已經證明了 Merkle 樹的核心安全屬性。學術界使用 Coq、Isabelle 等工具提供了機器可驗證的數學證明。

第五，雖然面臨量子計算等未來威脅，但比特幣社群已經在討論後量子升級方案。Merkle 樹結構的簡單性使其易於適應新的密碼學標準。

相關文章：

學術引用：

更新日期：2026-02-26

版本：2.0

延伸閱讀與來源

這篇文章對您有幫助嗎？

評論

發表評論

注意：由於這是靜態網站，您的評論將儲存在本地瀏覽器中，不會公開顯示。

目前尚無評論，成為第一個發表評論的人吧！