Rindrics Mumbles logo

Rindrics Mumbles

冪等性キー生成に関する技術選定: ハッシュアルゴリズム

冪等性キーの生成に利用するハッシュアルゴリズムとしてBLAKE3を選定した。

はじめに

資源評価に利用するデータの永続化を担うdata-registryの開発をすすめている。

Tag "data-registry" | rindrics.com

https://rindrics.com/tags/data-registry/

前回の記事では、冪等性キーをサーバー側で生成する意思決定をした。 本記事では、その冪等性キー生成に用いるハッシュアルゴリズムを選ぶ。

背景

通常、ハッシュアルゴリズム選定における比較観点は下記の通りだ:

  • 衝突耐性
  • 計算コスト
  • 標準性
  • 相互運用性
  • 出力サイズ

ただしこれらの観点の重みは均等ではなく、特にdata-registryの冪等性キー生成においては何よりも衝突確率の低さを重視する必要がある。

「衝突確率の低さ」とは

攻撃による衝突ではなく、単なる確率的な衝突が起こる程度を指している。理由としては、本ケースではセキュリティ目的で利用するわけではないので、「攻撃への耐性」という観点は必要ないため。

これは、冪等処理において、ハッシュ衝突が起きた場合に下記の流れでデータ喪失が生じるためだ:

先行リクエストA: hash(何らかのデータ) → hash=H
  → Revision "newRev" が作成される → 返却

後続リクエストB: hash(何らかの別のデータ) → hash=H (衝突)
  → ルックアップで "newRev" を発見 → 返却
  → クライアントは成功を受け取るが、登録依頼したデータは登録されていない（データ喪失）

このたび選定対象とした候補アルゴリズムは下記の三つ1:

  • SHA-256
  • SHA-512
  • BLAKE3

上記のうち、まず衝突確率の低さが想定リクエスト数に照らして必要十分なものを選び、続いてその他の選定観点を比較して採用アルゴリズムを決める。

衝突確率に着目した一次選定

ということで、まずアルゴリズムの衝突確率がdata-registryの想定リクエスト数に照らして高すぎないかを調べてみる。 SHA-256とBLAKE3はともに出力長が256ビットで衝突確率は同じなので、まず出力長256ビットにおける衝突ペア数の期待値が想定リクエスト数のもとで1未満に収まるかを調べることで候補を絞る。 256ビットで足りなければSHA512の衝突確率の概算に進み、一方で256ビットで充分であればSHA256とBLAKE3の比較に進むということ。

衝突確率は要は誕生日問題として考えることができるので、\(k\)個のリクエストから得られるハッシュ値について、衝突するペア数の期待値\(E[C]\)は、ハッシュ出力を\(b\)ビットとすると次式で近似できる。

$$ E[C] \approx \frac{k^2}{2^{b+1}} $$

衝突が十分まれな範囲では、1組以上の衝突が発生する確率も次式で近似できる。

$$ P(\text{1組以上が衝突}) \approx \frac{k^2}{2^{b+1}} $$

したがって、いま考える256ビットのハッシュでは、

$$ E[C] \approx \frac{k^2}{2^{257}} $$

となる。

選定にあたっては、衝突するペア数の期待値が1となるリクエスト数を求め、それが想定リクエスト数に対して余裕があるかを確認する。

256ビットの場合、

$$ \frac{k^2}{2^{257}} = 1 $$

より、

$$ k \approx 2^{128.5} \approx 4.8 \times 10^{38} $$

となる。

利用程度に関するパラメータ

想定リクエスト数の算出に必要なパラメータを、オーダー規模で見積もる。 見積もりは悲観値で出したいので、オーダー単位で切り上げた値を利用する。

ユーザー数

水産研究・教育機構の「水産資源に関する情報」ページを見ると、本記事の執筆時点（2026年9月）において 沿岸沖合資源（192魚種） という記述がある（こんな多かったっけ…？）。 192魚種それぞれの主担当者は、ほぼ確実に延べ人数つまり兼務があると見てよいと思うが、ここでは悲観見積もりとして一応192人の主担当者がいることにする。

また資源評価プラットフォームに機能を充実させた場合、評価案査読者や、認証済みの（物好きな）一般利用者からの利用も考えられる。 合計ユーザー数をオーダー規模で見積もるにあたり、これらの利用者が808人を超えるようだと1000人のオーダーとなるが、まずそんなことはないだろう。

ということで、ユーザー数は多くても数百人のオーダーに収まると考えられ、見積もり用に切り上げオーダーとしては 1000人 を用いる。

運用期間

資源評価事業は将来的にも継続するだろう。 10年未満ということはないはず。 しかし1000年はいくらなんでもやりすぎだろう。その頃にはもっと良い技術があるはず。

ということでオーダーとしては 100年。

ユーザーあたり並列計算数

資源評価プラットフォームがいい感じに構築できるとしたら、パラメータセットの組み合わせが異なる複数シナリオをバックグラウンドで並列計算できるようにしたい。 並列計算機能が実現した場合、ユーザーごとに並列計算ジョブを持つことになる。 各ジョブに書き込み系の処理をさせるかどうかは設計次第ではあるが、ここでは悲観見積もりということでユーザーあたりの並列計算数も考慮しておく。

実用的な視点に立つとは、並列計算の単位としては、名前をつけられるようなレベルの大きいシナリオだけでなく、パラメータの探索などでも利用する局面があるだろう。 そう考えると、10のオーダーの並列計算はあまり嬉しくないだろうと思う。百数十とか、数百の並列計算ができると、探索的検討がスムーズにできるはず。

ということで、数百を切り上げるとオーダーとしては 1000。

バースト利用期間

悲観的に見積もるため、ここではバースト利用が資源評価の準備期間中にわたって続くと仮定する。

なお事業の性質上、資源評価プラットフォームは年間通して平均的に利用されることはない。 data-registryが冪等性キーを生成する想定リクエスト数に関しては、利用はほぼ評価期間に限られるだろう。 このことから、定常利用はバーストに対して無視できる程度と思われる。

ということで、バースト利用が3ヶ月間続くとし、オーダー単位で切り上げて 100日。

リクエスト数の見積もり

上記から、data-registryの冪等性キー生成リクエスト数の悲観見積もりのパラメータは下記のようになった:

  • ユーザー数: 1000人
  • 運用期間: 100年
  • ユーザーあたり並列計算数: 1000
  • バースト利用期間: 100日

このパラメータもとでは、衝突ペア数の期待値を1未満に保つうえで、1ユーザーが発行できる年間のリクエスト数は

$$ \frac{4.8 \times 10^{38}}{1000 \times 100 \times 1000 \times 100} = 4.8 \times 10^{28} $$

となる。

実際には、ユーザー数も運用期間もここまでにはならないと思われるので、並列計算数もまだ増やす余地がある。 以上から、アルゴリズムのアウトプット長は256ビットで充分と思われたため、SHA512は選択肢から外す。

ということで、以下では、SHA256とBLAKE3を、残る3観点について比較する:

  • 衝突耐性 衝突確率の低さ
  • 計算コスト
  • 標準性
  • 相互運用性
  • 出力サイズ
    • ともに256ビットのためスキップ

その他の観点での比較

SHA256

  • 計算コスト: こちらのベンチマーク結果によると、5 MBの写真ファイルのハッシュ化の所要時間が139.10 msということで、処理速度は35.9 MB/sとする
  • 標準性: 米国国立標準技術研究所（NIST）により仕様化されており充分
  • 相互運用性: 実質上の業界標準なので充分

BLAKE3

  • 計算コスト: こちらのベンチマーク結果によると、5 MBの写真ファイルのハッシュ化の所要時間が38.00 msということで、処理速度は131.6 MB/sとする
  • 標準性: RFC準拠の仕様が公開されており充分
  • 相互運用性: 主要言語に対応しており、ClojureでもJavaライブラリをJava interop経由で利用可能なので充分

比較観点をまとめると下記のようになる:

Algorithm 処理速度 標準性 相互運用性
SHA-256 35.9 MB/s ✓ ✓
🥇 BLAKE3 131.6 MB/s ✓ ✓

その他、CPU負荷やメモリ効率についてもBLAKE3の優位性が報告されていた（ref）。

以上から、標準性・相互運用性は両アルゴリズムともに良好なため、計算コストの低さを重視してBLAKE3を採用する。

所感

今回のケースでは、採用技術のスペックが非機能要件を大幅に上回っていたために、些細なことを大げさにやった感があるかもしれない。 しかしこれをやらないと、「キャパ的に3日と保たないシステムを作ってました」みたいな事態にもなりかねない。 仰々しくはあるが、やはり必要なのだ。

次の記事では、冪等性キーを安定して生成するために必要なJSONシリアライズについて考える予定。

  1. セキュリティ目的での利用ではないが、MD5とSHA-1については候補から除外した。理由としては、両者の衝突耐性が破られているため採用が減り、コミュニティ内でライブラリや情報の更新が途絶える懸念を回避するため ↩︎