Elixirで学ぶ Merkle Tree: 奇数ノード対応（CVE-2012-2459）

はじめに

Git や Blockchain のような分散システムでは、大量のデータの整合性を効率よく証明する仕組みが欠かせません。その中核を支えるのが Merkle Tree です。

前回までの記事では、包含証明とローカル更新を Elixir で体験しました。

今回はもう一歩踏み込み、奇数ノードをどう扱うかという実装上の課題に注目します。

Bitcoin の初期実装では、ノード数が奇数だった場合、最後のノードを複製してペアを作るという方式を採用していました。

[A] [B] [C]  → [A,B] [C,C]

一見すると自然な処理に見えますが、のちにCVE-2012-2459として重大な脆弱性が報告されました。

CVE-2012-2459： 末尾複製の落とし穴

末尾ノードをコピーして (C, C) のようなペアを作ると、異なるデータ集合でも同じ Merkle Root が生成されるリスクがあります。
これはデータ整合性を保証する仕組みとしては致命的であり、
場合によっては不正に作られたブロックが正当と見なされることすらあり得ます。

末尾複製あり vs 末尾複製なし

① バランス木（末尾複製あり、非推奨）

defp build_tree(level) do
  padded =
    if rem(length(level), 2) == 1 do
      level ++ [List.last(level)]   # 末尾を複製
    else
      level
    end

  parent =
    padded
    |> Enum.chunk_every(2)
    |> Enum.map(fn [a, b] -> :crypto.hash(:sha256, a <> b) end)

  [level | build_tree(parent)]
end

[A] [B] [C]     ← 3 ノード（奇数）

[A,B] [C,C]     ← C を複製してペア化
   │     │
hash    hash    ← (C+C) は常に同じ値
  │     │
  └──┬──┘
     ▼
    Root

末尾複製方式は実装が簡単という利点がある一方で、同じノードをペアにする (C, C) のような構造を生み出しやすく、これが固定されたハッシュ値を持つため、衝突の温床になってしまいます。

② アンバランス木（末尾複製なし、推奨）

defp build_tree(level) do
  parent =
    level
    |> Enum.chunk_every(2, 2, :discard) # 偶数ペアだけ
    |> Enum.map(fn [a, b] -> :crypto.hash(:sha256, a <> b) end)

  next_level =
    if rem(length(level), 2) == 1 do
      parent ++ [List.last(level)] # 余りをそのまま持ち上げ
    else
      parent
    end

  [level | build_tree(next_level)]
end

[A] [B] [C]     ← 3 ノード（奇数）

[A,B]   [C]     ← C は複製せず複製せず持ち上げる
  │      │
hash     │
  │      │
  └──┬───┘
     ▼
    Root

アンバランス木では、末尾ノードを複製せずにそのまま次の階層へ持ち上げるため、同じノード同士の組み合わせを避けることで、ハッシュ衝突のリスクを軽減し、より安全な構造を実現できます。

Elixir で実装するアンバランス木 Merkle Tree

defmodule MerkleTree do
  defstruct root: nil, leaf_hashes: []

  def new(data_blocks) when is_list(data_blocks) do
    leaf_hashes = Enum.map(data_blocks, &:crypto.hash(:sha256, &1))

    levels = build_tree(leaf_hashes)
    root = List.first(List.last(levels))

    %MerkleTree{
      root: Base.encode16(root, case: :lower),
      leaf_hashes: leaf_hashes
    }
  end

  defp build_tree([hash]), do: [[hash]]
  
  defp build_tree(current_level_hashes) do
    parent_level_hashes =
      current_level_hashes
      |> Enum.chunk_every(2, 2, :discard)
      |> Enum.map(fn [a, b] -> :crypto.hash(:sha256, a <> b) end)

    next_level_hashes =
      if rem(length(current_level_hashes), 2) == 1 do
        parent_level_hashes ++ [List.last(current_level_hashes)]
      else
        parent_level_hashes
      end

    [current_level_hashes | build_tree(next_level_hashes)]
  end
end

動かしてみる

# 奇数ノード（a, b, c）
tree_odd = MerkleTree.new(["a", "b", "c"])

# 末尾複製を模したデータ
tree_dup = MerkleTree.new(["a", "b", "c", "c"])

# ルートが必ず異なることを確認
tree_odd.root != tree_dup.root
#=> true

おわりに

奇数ノード対応としてよく使われる末尾複製には、CVE-2012-2459 にもつながる衝突リスクがあることを学びました。

一方、末尾を複製せずにそのまま持ち上げるアンバランス木は、より安全で、実装も比較的簡単です。

Elixir なら Enum.chunk_every/4 を使って直感的に書けるので、仕組みを理解しながら手を動かすにはぴったりです。