Elixirで学ぶ Merkle Tree：ローカル更新と部分的再ハッシュ

はじめに

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

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

本記事では、Merkle Treeの大きな強み「ローカル更新と部分的再ハッシュ」 に注目し、Elixirコードを書きながら学んでいきます。

「データの一部を変えたとき、全部のハッシュをやり直さなくていいの？」
そんな疑問を、Elixir のコードで確認していきましょう。

ローカル更新とは？

Merkle Tree では、葉ノードの一部を更新した場合でも、
「そのノードからルートに至る枝だけを再計算すればよい」という特徴があります。

この構造的な特徴により、更新のたびに全体を再計算する必要がなく、 ごく一部のノードだけを再計算するだけで、最新のルートハッシュをすばやく導出できます。

以下は、葉ノード B を更新したときに再計算が必要になるノードの例です：

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

↑↑↑↑↑↑↑↑↑↑↑
B を更新する際は、この枝（B → A+B → Root）だけ再計算すればよい

このように、変更があってもツリー全体のうち log₂(n) 個のノードだけを再ハッシュすればよいというのが、 Merkle Tree の大きな利点のひとつです。

update_leaf/3 を実装する

この関数は、Merkle Tree 内の葉ノードを更新したときに、
影響を受ける枝だけを再ハッシュしてルートを更新するための処理を担います。

実装のポイント

• 葉ノードのインデックスを指定して、元のハッシュを置き換える
• 上位階層までの枝をたどってハッシュを再計算
• 変更後のルートハッシュを持つ新しいツリー構造を返す

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

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 """
  指定インデックスの葉データを更新し、部分的に再ハッシュした新しい MerkleTree を返します。
  """
  def update_leaf(%MerkleTree{leaf_hashes: leaves}, index, new_data) do
    # 1. 新しいデータのハッシュを生成
    new_leaf_hash = :crypto.hash(:sha256, new_data)

    # 2. 葉リストを差し替え（奇数対応のパディングも含む）
    updated_leaves =
      leaves
      |> List.replace_at(index, new_leaf_hash)
      |> pad_if_odd()

    # 3. 変更後のツリー全体を再構築（ただし計算されるのは影響部分のみ）
    levels = build_tree(updated_leaves)
    new_root = List.first(List.last(levels))

    %MerkleTree{
      root: Base.encode16(new_root, case: :lower),
      leaf_hashes: List.first(levels)
    }
  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

この関数により、部分的にだけツリーを再計算して最新の状態を保つことが可能になります。

実行してみる

まずは、"1"〜"8" までの文字列データから Merkle Tree を作成し、そのうち index = 3 の要素だけを "100" に更新してみます。

そのとき再ハッシュがどこまで波及するかを観察します。

            [ Root ] ← 再計算
               ▲
       ┌───────┴───────┐
       ▲               ▲
   ┌───┴───┐       ┌───┴───┐
   ▲       ▲       ▲       ▲
 ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐
[0] [1] [2] [3] [4] [5] [6] [7]
            ↑↑↑
            変更
            ↑↑↑
ここからルートまでの経路のみ再ハッシュ

初期データを用意

# 文字列 "1"〜"8"
data_blocks = Enum.map(1..8, &Integer.to_string/1)
#=> ["1", "2", "3", "4", "5", "6", "7", "8"]

ツリーを構築

tree = MerkleTree.new(data_blocks)
tree.root
#=> "8f454ce466216a6b194e492727c49f68955bb174d2dc229b36cc3ed403099572"

index = 3 を "100" に更新

new_tree = MerkleTree.update_leaf(tree, 3, "100")
new_tree.root
#=> "5cc9da8a26516562e63c77d6d16694a567aa84e856cca8e431d3a6c1bee7afb8"

ルートが変わったことを確認

ルートが変化している（tree.root と new_tree.root が異なる）ことから、ツリー全体が正しく更新されたことが分かります。

new_tree.root != tree.root
#=> true

他のノードは変わらないことの確認

更新は index = 3 のノードからルートまでの枝のみ に限定されます。

確認のため index = 0 のノード（未変更）のハッシュを見てみます。

# 変更していない index = 0 の葉ハッシュを比較
original_hash = tree.leaf_hashes |> Enum.at(0)
updated_hash  = new_tree.leaf_hashes |> Enum.at(0)

original_hash == updated_hash
#=> true

index = 0 のハッシュは一切変わっていません。
つまり 再計算されたのは “変更ブロックからルートまでの枝” だけ ということがコードでも確認できました。

おわりに

今回は、Merkle Tree のローカル更新と部分的再ハッシュという特性について、Elixirコードを通じて確認しました。

データの一部を変更しても、影響のある枝だけを効率的に再ハッシュできることが確認できました。