あらすじ
- ランダムトークンが衝突する確率について調べた
- 様々な条件で検証できるように、ハッシュ値（またはランダムトークン等）が衝突する確率を求めるWebサービスを作った
きっかけ
Webサービス等を開発していると、「ユーザーごとにユニークなトークンを発行したい」といったようなことが出てくるかと思います。
僕の場合は、
- ユーザーのIDを連番じゃなくてランダムなトークンにしたい
- ユーザーがパスワードリセットするときに、トークンを発行して認証したい
などの状況がありました。
データベース等を使っている場合は、カラムにユニーク制約を付けることで保障はできます。ですが、トークンが衝突してしまうと保存に失敗してしまうので、生成するときに衝突の確率は低くしたいです。
乱数とSHA-256等を使ってハッシュ値を生成するというのも考えられますが、SHA-256の場合だと64文字なので、URLとして表示するときに不格好だったり、レコード数が多い場合はその分容量が増えてしまうという問題があります。
トークンの長さを長くすれば衝突の確率が低くなるということはわかりますが、具体的にどのくらいの長さであれば安心できるのでしょうか。
誕生日のパラドックス
ある学校のクラスで30人生徒がいるとしたときに、その中で誕生日が同じ2人（以上）がいる確率はどのくらいでしょうか？
答えは約70%です。
誕生日は366通りあるので、30人程度なら同じ誕生日の人がいる確率はもっと低いと思ったかもしれません。
この結果が直感に反するので、誕生日のパラドックスとして知られています。
直感に反するということは、トークンの長さを決めるときに具体的な衝突確率を計算せずに決めるのは危険ということです。
様々な条件で検証できるようにWebサービスを作った
衝突確率を計算してみようと思ったときに調べてみたところ、計算方法は出てきますが、実際に数値を入れて計算してくれるというサービスはあまり存在しませんでした。無いのならば作ってしまえということで、作りました。
具体的な計算方法は他に説明してくれるサイトがいくらでもあるので割愛します。
ユーザーが100万人のときにユニークなトークンを発行する場合
実際の数値を入れて結果を見てみましょう。
ユーザーが100万人いて、ユーザーごとにユニークなトークンを1つ発行するとします。トークンはランダムな英数字としましょう。
そうすると、長さを10文字としたときに
組み合わせ数3656兆通りのハッシュ値を100万回生成したときに衝突が発生する確率は
7313分の1
ということで、10文字以上あれば衝突が発生する確率はそれなりに低いという事がわかります。ためしに生成回数を1000万回にすると、衝突が発生する確率は74分の1になります。それだと少し心配なので長さを12文字にすると確率は9.5万分の1ということで安心できそうだということがわかります。
余談 | 実装について
今回のサービスは勉強も兼ねてVue.js+Nuxt.jsで実装しました。Vue.jsを利用することで、フォームの入力からリアクティブに結果を表示するというようなアプリでも簡単に実装できて便利でした。このサービスは1ページだけなので恩恵は少ないかもしれませんが、Nuxt.jsのおかげで静的ファイルの生成までスムーズにできました。
ホスティングサービスはFirebaseを使っています。無料でここまでのことができるのはすごいですね。Firebase Realtime Databaseとかを使ったサービスも作っていきたいです。
衝突確率の計算は大きい数に対応するために近似を利用しています。なので小さい数だと誤差が大きいかもしれません。
実装のより細かい部分については、コメント等で要望があればまた別に書こうかなと思います。
バグ等の報告をしていただけると、僕が画面に向かって感謝の礼を10回ほど行いますのでよろしくお願いします。