Elixirで学ぶ Merkle Tree：Taproot風Tagged Hash

はじめに

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

これまでの記事では、Elixir を使って Merkle Tree の基本的な構造やローカル更新、包含証明を学んできました。

今回はさらに一歩進み、Tagged Hash を用いたハッシュの構築方法、特に Bitcoin Taproot で採用されている方式を Elixir で実装してみます。

ちなみにこの手法については、bitcoinrb の SimpleBuilder 実装 に詳しく紹介されており、Taproot の仕様理解にも役立ちます。

Tagged Hash とは

通常の SHA-256 によるハッシュでは、文脈の異なるデータが、同じようにハッシュされてしまうという問題があります。
これにより、用途が異なるのに同じハッシュが得られてしまう衝突のリスクが生じます。

この問題を解決するために考案されたのが、Tagged Hash という技術です。

Tagged Hash はこの問題に対処する方法で、用途に応じた タグ を付けてハッシュを行うことで、安全性と構造的な明瞭さを保つテクニックです。

その名の通り、データに「タグ（文脈）」を付けてハッシュ化することで、より安全で意味のあるハッシュを生成します。

通常のハッシュ

          message
             │
             ▼
        SHA-256(hash) ──→ 0xabc123...

• message がどんな用途のデータなのか区別できない
• 違う文脈でも、同じ入力があれば同じハッシュ → 衝突の温床

文脈付きのハッシュ

      "TapLeaf"          "TapBranch"
         │                   │
         ▼                   ▼
    SHA-256(tag)        SHA-256(tag)   ← ステップ①: 
        ↓↓                  ↓↓           タグ名をハッシュして`tag_hash`を作成
[tag_hash][tag_hash]   [tag_hash][tag_hash]
         │                   │
         └──── message ──────┘         ← ステップ②:
                    │                    `tag_hash`を2回前置し、メッセージを連結して再度ハッシュ
                    ▼
             SHA-256(hash)

こうすることで、同じ message でもタグが違えば全く異なるハッシュが得られます。
Merkle Tree では 葉ノードと枝ノードでタグを分け、誤検証や長さ拡張攻撃を防ぎます。

Elixir 実装例：Tagged Merkle Tree

defmodule TaggedMerkleTree do
  @leaf_tag   "TapLeaf"
  @branch_tag "TapBranch"

  # タグハッシュを事前計算
  @leaf_tag_hash   :crypto.hash(:sha256, @leaf_tag)
  @branch_tag_hash :crypto.hash(:sha256, @branch_tag)

  defstruct root: nil, leaf_hashes: []

  @doc "データリストから Tagged Merkle Tree を構築"
  def new(data_blocks) when is_list(data_blocks) do
    leaf_hashes =
      Enum.map(data_blocks, fn data ->
        tagged_hash(@leaf_tag_hash, data)
      end)

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

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

  # Tagged Hash で枝ノードを構築
  defp build_tree([h]), do: [[h]]

  defp build_tree(current_level_hashes) do
    # 偶数ペアのみ hash、奇数の場合のあまりは次の階層へ
    parent_level_hashes =
      current_level_hashes
      |> Enum.chunk_every(2, 2, :discard)
      |> Enum.map(fn [a, b] ->
        tagged_hash(@branch_tag_hash, 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

  # Taproot の Tagged Hash 本体
  defp tagged_hash(tag_hash, msg) do
    :crypto.hash(:sha256, tag_hash <> tag_hash <> msg)
  end
end

実行例

iex> data = ["foo", "bar", "baz", "qux"]
iex> tree = TaggedMerkleTree.new(data)
iex> tree.root
"c65b3561b7c5d750fe7e58597ca84f0d6b38985c9545bf7aabe929c9816dc4c7"

おわりに

今回は、Bitcoin の Taproot にも採用されている Tagged Hash の仕組みを、Elixir を使って学びました。

通常の SHA-256 にタグを加えることで、文脈の違いによる衝突リスクを防ぎ、安全で構造化された Merkle Tree を実現できることがわかりました。

この手法については、bitcoinrb の SimpleBuilder 実装 に詳しく紹介されており、Taproot の仕様理解にも役立ちます。