git コミット ID の衝突確率

git はコミットを SHA1 で管理していることは、こんな場末の日記を好きこのんでご覧になられている皆さんならよくご存じかと思いますが、最近メイドガチャピン先生の「革命の日々！ git のsha1は何桁あれば安全か」など、Linux において Git デフォルトの 7 桁表示のコミット ID が被りまくっていると話題のようですので、これについて考えてみましょう。

さて、ハッシュ関数については昔まとめたことがありますが、ようするに Radium Software Development さんの記事が素晴らしいという話です。それによると、Bob Jenkins 曰く「2^n 個のキーに関して，衝突の可能性を 1/(2^m) 程度に抑えたいならば， 2(n+m) ビットのハッシュ値を用いる必要があります」だそうな。

Linuxのコミット数は 220k=~262144=2^18 なので、衝突確率を 1/2 にするには 2 * (18 + 1) = 38bit 必要ですね。10文字(=40bit)でも衝突しているLinuxは行いが悪い感じですが、まぁ想定通りの確率って事になるんじゃないでしょうか。

逆に7文字で足りる範囲がどのくらいか考えてみましょう。4bit/文字 * 7文字 = 28bit なので、これが衝突確率が 1/2 になる入力数を計算すると、(28bit / 2) - 1 = 13bit = 8192
おい、全然ダメじゃねーか。

結論: git はまぬけ