その他技術 Qiita Tech Festa 2025

Qiita Tech Festa20252025年7月15日まで開催中！

企業向けブロックチェーンビジネスについてあれこれ語ろう！Advent Calendar 2024

Day 7

@mnishiguchi(Masatoshi Nishiguchi)in

fukuoka.ex：福岡Elixirコミュ

「全部まとめてハッシュ」では不十分？Elixir で学ぶ Merkle Tree の強み

Last updated at 2025-07-07Posted at 2025-07-06

はじめに

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

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

本記事では、以下についてElixirコードを書きながら学んでいきます。

単一ハッシュ方式とその限界
Merkle Tree の仕組みと利点
Elixir での実装と可視化・検証

単一ハッシュ方式

最もシンプルな整合性チェックの方法は、すべてのデータを連結して一括でハッシュすることです。

たとえば、複数のファイル（テキスト、画像、動画など）をすべて結合し、SHA-256 を一度だけ計算するという方式です。

data_blocks = ["foo", "bar", "baz"]
all_data = Enum.join(data_blocks)
big_hash = :crypto.hash(:sha256, all_data) |> Base.encode16(case: :lower)
IO.puts("Big Hash: #{big_hash}")

図にすると以下のようになります：

[ "foo" ]   [ "bar" ]   [ "baz" ]
     ↓          ↓          ↓
 ──────────────────────────────
      データをすべて連結
 ──────────────────────────────
                ↓
     SHA256("foobarbaz") → 単一ハッシュ

メリット

実装が非常にシンプル
データ全体の整合性を一度に検証できる

限界と課題

証明ができない
特定のデータが含まれていたことを証明するには、全体のデータを再送・再ハッシュする必要がある
部分更新が非効率
一部のデータが変更されると、全体を再ハッシュする必要がある
メモリや I/O に弱い
大規模データをすべてメモリに載せる必要があり、スパイクの原因になる可能性がある

Merkle Tree 方式

Merkle Tree は、データをハッシュのツリー構造で管理し、効率的な整合性チェックと部分証明を可能にします。

基本構造

各データブロックを個別にハッシュする（葉ノード）
隣り合うハッシュを結合して再ハッシュ（中間ノード）
最後に 1 つのルートノード（Merkle Root）を得る

data_blocks = ["foo", "bar", "baz", "qux"]
tree = MerkleTree.new(data_blocks)
IO.puts("Merkle Root: #{tree.root}")

         [ Root ]
            ↑
        ╱       ╲
   [H1 + H2]   [H3 + H4]
     ↑   ↑       ↑   ↑
   [H1] [H2]   [H3] [H4]
     ↑   ↑       ↑   ↑
  "foo" "bar"  "baz" "qux"

メリット

部分証明が可能
"baz" が含まれていたことを、兄弟ノードのハッシュのみで証明できる（全データは不要）
局所的な更新が可能
"baz" の内容が変更されても、該当ブランチのみを再ハッシュすればよい
固定サイズのルート
データ件数が 4 件でも 400 万件でも、ルートハッシュは常に 32 バイト（SHA-256）

限界と課題

実装がやや複雑
ペアのハッシュ処理や奇数ノード対応、証明パスの生成など、単一ハッシュ方式と比べてロジックが増える
証明のための構造を保持する必要がある
後から証明を行うには、途中のノード情報（証明経路）を保持・管理する仕組みが必要になる

単一ハッシュ方式 vs. Merkle Tree の比較

項目	単一ハッシュ方式	Merkle Tree
証明サイズ	O(n) — 全データの再送・再ハッシュが必要	O(log n) — 兄弟ノードのみで証明可能
更新コスト	O(n) — 全体を再ハッシュ	O(log n) — 一部のブランチのみ再ハッシュ
メモリ / I/O 負荷	高 — 全データを結合	低 — ペア単位で処理、ストリーム処理可能
並列処理のしやすさ	難しい — 結合がボトルネック	容易 — 葉・中間ノード単位で並列処理可能
実装の手軽さ	非常に簡単（2〜3 行）	やや複雑（ツリー構築・証明ロジックが必要）
主なユースケース	チェックサム、簡易整合性検証	Git、Bitcoin、Tapyrus、監査ログなど

使い分けの目安

単一ハッシュ方式が向いている場合

小規模かつ静的なデータを対象とする
全体の整合性を一括で確認したい
証明・部分更新などが不要な場合

Merkle Tree が向いている場合

個別データの存在証明が必要
部分更新・局所的な検証を効率化したい
分散処理やチェーン構造など、スケーラブルな設計を求められる場合

Elixir で体験する 2 つの方式

ここからは、Elixir を使って両者を実際に比較してみます。

サンプルデータの準備

まずは、テキスト・画像・動画を模した 3 種類のデータを用意します。

text_data   = "闘魂とは己に打ち克つこと"
image_bytes = :crypto.strong_rand_bytes(1024)   # 1KB の疑似画像データ
video_bytes = :crypto.strong_rand_bytes(2048)   # 2KB の疑似動画データ

data_list = [text_data, image_bytes, video_bytes]

Merkle Tree モジュールを定義

次に、簡易的な Merkle Tree を構築・検証できるモジュールを定義します。

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

  def verify(%MerkleTree{leaf_hashes: leaves}, item) do
    hash = :crypto.hash(:sha256, item)
    Enum.any?(leaves, &(&1 == hash))
  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
end

単一ハッシュの計算

データをすべて結合し、1 回の SHA-256 ハッシュで全体の整合性を確認します。

big_hash =
  data_list
  |> Enum.reduce(<<>>, fn chunk, acc ->
    acc <> chunk
  end)
  |> then(fn merged_data ->
    :crypto.hash(:sha256, merged_data)
    |> Base.encode16(case: :lower)
  end)

出力例

"07044c2ec18d57901a9e1a61c6c5c02c3962ec230085eefa7ed7b7c662f1ce55"

Merkle Tree の構築とルートハッシュの取得

同じデータを使って Merkle Tree を構築し、ルートハッシュ（Merkle Root）を確認してみます。

tree = 
  data_list 
  |> MerkleTree.new()

出力例

%MerkleTree{
  root: "5188ebac04f78d5c8b5b880cc74b9fdf5876761e60495c9b42ee962b30b2e9fb",
  leaf_hashes: [
    <<140, 149, 141, 136, 189, 206, 189, 249, 26, 80, 170, 128, 161, 22, 142, 47, 200, 15, 232, 168,
      179, 84, 172, 15, 47, 242, 178, 89, 110, 125, 27, 98>>,
    <<136, 107, 185, 62, 103, 206, 96, 22, 96, 207, 99, 193, 24, 114, 97, 243, 35, 3, 201, 8, 115,
      212, 107, 60, 220, 244, 250, 114, 137, 226, 91, 114>>,
    <<117, 161, 124, 206, 230, 137, 13, 72, 170, 171, 205, 209, 149, 76, 132, 94, 134, 173, 48, 139,
      145, 55, 179, 243, 50, 73, 120, 53, 150, 170, 11, 48>>,
    <<117, 161, 124, 206, 230, 137, 13, 72, 170, 171, 205, 209, 149, 76, 132, 94, 134, 173, 48, 139,
      145, 55, 179, 243, 50, 73, 120, 53, 150, 170, 11, 48>>
  ]
}

特定データの存在検証

最後に、Merkle Tree を使って「あるデータが含まれていたかどうか」を検証してみます。

MerkleTree.verify(tree, "闘魂とは己に打ち克つこと")
#=> true

MerkleTree.verify(tree, "もし負けるということがあると")
#=> false

このように、Elixir を使うことで Merkle Tree の構造やメリットを手軽に体感することができます。

おわりに

本記事では、データの整合性を担保する手法として次の 2 つを比較し、それぞれを Elixir で実装・検証してみました。

単一ハッシュ方式: 全データを連結して 1 回ハッシュするシンプルな方法
Merkle Tree 方式: ツリー構造により部分証明や局所的な更新を可能にする構造化アプローチ

それぞれの特徴を簡潔にまとめると、次のようになります：

観点	単一ハッシュ方式	Merkle Tree
構造	フラットな 1 ハッシュ	階層的なツリー構造
更新	全再計算が必要	一部再計算で済む（log n）
証明	不可	コンパクトに証明可能
活用例	チェックサム、ファイル整合性	Git、Bitcoin、Tapyrus、監査ログなど

シナリオ	推奨方式
小さなデータの整合性をシンプルに確認したい	単一ハッシュ方式
データの一部を証明・部分更新したい	Merkle Tree
分散台帳や改ざん検知などスケーラブルな用途に	Merkle Tree

このように、Merkle Tree は構造化された整合性・証明の基盤として非常に優れており、Elixir のような関数型言語でも実装しやすいことがわかりました。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up