Elixirで学ぶ Merkle Tree：兄弟ノードだけで包含証明

はじめに

Git や Blockchain のようなシステムでは、大量のデータの中から「特定のデータが改ざんされていないこと」や「あるデータが確かに存在していたこと」を効率よく証明する必要があります。

こうした用途に使われているのが Merkle Tree（マークルツリー） です。

前回の投稿では、巨大なデータをまとめてハッシュする方式と、構造的に優れた Merkle Tree を比較しました。

今回はMerkle Tree の「兄弟ノードだけで証明できる」という特徴に注目します。

Merkle Tree の包含証明

Merkle Tree では、あるデータ（葉ノード）がツリー内に含まれていることを証明するために、そのデータの兄弟ノード（隣のハッシュ）をたどっていけば、最上位のルートハッシュを再構成できます。

このとき必要となるのは、各階層で1つの兄弟ノードだけ。つまり、全体の証明に必要な情報は log₂(n) 個のノード分だけで済みます。

             [ Root ]
                ▲
         ┌──────┴──────┐
     [A+B]           [C+D]
       ▲               ▲
   ┌───┴───┐       ┌───┴───┐
 [A]     [B]     [C]     [D]

ルートの再構成手順 (B がツリーに含まれていることを証明したい場合)

1. 証明対象である B をハッシュ化し、兄弟ノード A のハッシュと連結 → 中間ノード [A+B] のハッシュを得る
2. そのハッシュと、次の階層における兄弟ノード [C+D] のハッシュを連結し、最終的な Merkle Root を導出

このように、すべての階層で 兄弟ノードのハッシュが1つずつ あれば、
対象データからルートハッシュを再構成し、既知の Merkle Root と一致するかを検証できます。
一致すれば、そのデータがツリーに含まれていたことが証明されます。

build_inclusion_proof/2 を実装する

この関数は、Merkle Tree において「特定のデータがツリー内に含まれていること」を証明するための情報（包含証明）を生成します。

Merkle Tree の構造上、対象のデータ（葉ノード）からルートハッシュに至るまでの各階層で、
「兄弟ノードのハッシュ値」と「その位置（左か右）」が分かれば、ルートを再構成できます。

そのため、包含証明に必要な情報は 各階層で1つだけ、つまり全体で log₂(n) 個の兄弟ノードだけで済みます。

前回の投稿で定義したMerkleTree モジュールに、以下のように build_inclusion_proof/2 関数を追加します。

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

  def new(data_blocks) do
    leaf_hashes =
      data_blocks
      |> Enum.map(&(:crypto.hash(:sha256, &1)))
      |> pad_if_odd()

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

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

  @doc """
  指定インデックスの葉ノードについて、ルートまでの包含証明を返します。

  返される証明は、以下の形式のタプルのリストです：

      [{兄弟ノードのハッシュ（hex文字列）, :left | :right}, ...]

  各階層で1つずつ兄弟ノードをたどることで、ルートハッシュの再計算が可能になります。
  """
  def build_inclusion_proof(%MerkleTree{leaf_hashes: leaf_hashes}, leaf_index) do
    levels = build_tree(leaf_hashes)
    max_level_index = length(levels) - 1

    Enum.reduce(0..(max_level_index - 1), {leaf_index, []}, fn level_index,
                                                               {current_index, acc} ->
      level = Enum.at(levels, level_index) |> pad_if_odd()

      # 自分が偶数なら兄弟は右隣、奇数なら左隣
      {sibling_hash, side} =
        if rem(current_index, 2) == 0 do
          {Enum.at(level, current_index + 1), :right}
        else
          {Enum.at(level, current_index - 1), :left}
        end

      proof_entry = {Base.encode16(sibling_hash, case: :lower), side}

      # 上位の階層に進む（親ノードのインデックスを計算）
      next_index = div(current_index, 2)
      {next_index, acc ++ [proof_entry]}
    end)
    |> elem(1)
  end

  defp build_tree([hash]), do: [[hash]]
  defp build_tree(level) do
    level = pad_if_odd(level)

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

    [level | build_tree(next_level)]
  end

  defp pad_if_odd(list) do
    if rem(length(list), 2) == 1, do: list ++ [List.last(list)], else: list
  end
end

処理の流れ

• 各階層で、インデックス current_index を使って自分の位置を確認します。
• 偶数番なら兄弟ノードは「右隣」、奇数番なら「左隣」になります。
• 兄弟ノードのハッシュを取得し、それが左右どちらかを記録します。
• 親ノードの位置を div(current_index, 2) で計算して、次の階層に進みます。

この手順をルートまで繰り返すことで、対象データの包含証明ができます。

実行してみる

次のコードでは、32個のデータブロックのうち、中央（index = 16）の要素に対する包含証明を生成します。

data_blocks = Enum.map(1..32, &Integer.to_string/1)
tree = MerkleTree.new(data_blocks)
proof = MerkleTree.build_inclusion_proof(tree, 16)

出力例

[
  {"4ec9599fc203d176a301536c2e091a19bc852759b255bd6818810a42c5fed14a", :right},
  {"614a6c1e893421b0ca836da7bbd2fc2b6ccc81bbb405ba4c2a66977a8adf3733", :right},
  {"aa602355a22e3f795c93dc23c809aa5e22b41d7451f8a2c796a764cf25c30d10", :right},
  {"c8b40d9a8104120366f3ff77410f168a4f1d4a15ccfb922877ba87f05f98e4f7", :right},
  {"78c3e84729efee7b18ed984f64b00c2f53d6452e7384b4d3366a49eb5e6c46fc", :left}
]

データ数を変えながら build_inclusion_proof/2 の出力サイズを確認してみます。

for n <- [8, 16, 32, 64, 128] do
  proof =
    1..n
    |> Enum.map(&Integer.to_string/1)
    |> MerkleTree.new()
    |> then(&MerkleTree.build_inclusion_proof(&1, div(n, 2)))

  IO.puts("n = #{n} → proof size = #{length(proof)} (log₂(n) ≒ #{:math.log2(n) |> Float.round(1)})")
end

結果

n = 8   → proof size = 3 (log₂(n) ≒ 3.0)
n = 16  → proof size = 4 (log₂(n) ≒ 4.0)
n = 32  → proof size = 5 (log₂(n) ≒ 5.0)
n = 64  → proof size = 6 (log₂(n) ≒ 6.0)
n = 128 → proof size = 7 (log₂(n) ≒ 7.0)

ご覧の通り、証明サイズはデータ件数 n に対してほぼ log₂(n) に比例して増えるだけです。これは、Merkle Tree の構造が証明をコンパクトに保てることを示しています。

おわりに

今回は、Merkle Tree の「兄弟ノードだけで証明できる」という仕組みに注目し、その証明サイズが O(log n) に抑えられることを Elixir コードを通して確認しました。

この特性は、Git やブロックチェーンなどの分散システムにおいて、効率的な検証 や 部分的な同期 を可能にする非常に重要な基盤となっています。