2の256乗がいかに馬鹿デカいか
概要
SHA-256 のような 暗号学的ハッシュ関数 に対する総当たり探索が、なぜ現実的でないのかを数量で示す。2の256乗を40億の累乗へ分解し、GPU、Google規模の計算資源、地球、銀河へと段階的に拡張する。それでも正解へ到達する確率は極端に低い。終盤では Bitcoin の採掘に使われる ASIC の効率にも触れる。
要点
- 256ビットの特定ハッシュ値に一致する入力を総当たりで探すには、平均して2の256乗回規模の試行が必要になる。
- 2の256乗は、約40億に相当する2の32乗を8回掛けた値として捉えられる。
- GPU搭載マシン、Google規模の計算資源、地球、銀河を40億倍ずつ積み上げても、探索空間は埋まらない。
- 想像上の銀河スーパーコンピューターを宇宙年齢の約37倍にわたって動かしても、正解を得る確率は約40億分の1にとどまる。
- Bitcoin の採掘では、汎用GPUより効率的な専用ハードウェア ASIC が使われる。
構造化サマリ
256ビットの探索空間
前回の暗号通貨解説では、電子署名と暗号学的ハッシュ関数の安全性に関わる256ビットの数を扱った。たとえば SHA-256 で特定のハッシュ値になるメッセージを探す場合、ランダムな入力を試すより良い方法は基本的になく、平均して2の256乗回規模の推測が必要になる。
この数は日常的な尺度から離れすぎている。そこで2の256乗を、約40億である2の32乗を8回掛けた値として可視化する。
GPUからキロGoogleへ
高性能なGPUを使い、1台のコンピューターで毎秒40億回のハッシュ計算ができると仮定する。次にそのコンピューターを40億台集める。これは、動画内の概算では強化されたGoogleの計算資源を1000個集めた規模に相当し、「1キロGoogle」と呼ばれる。
さらに地球上の約80億人の半数へ、それぞれ1キロGoogleを与える。このように約40億倍の拡張を段階的に繰り返すことで、2の256乗の巨大さを具体的な比喩へ置き換える。
地球、銀河、宇宙年齢
人口の半数が1キロGoogleを持つ地球を40億個用意する。続いて、その地球群を持つ銀河を40億個集める。こうして作った銀河スーパーコンピューターでも、毎秒処理できる推測は2の160乗回にとどまる。
40億秒は約126.8年であり、その40億倍は約5070億年になる。これは現在の宇宙年齢の約37倍に相当する。それだけの時間を費やしても、256ビットの正解を見つける確率は約40億分の1にすぎない。
Bitcoin 採掘と ASIC
英語版動画の制作時点では、Bitcoin のハッシュ計算量は毎秒約50億の10億倍回で、動画内の1キロGoogleの約3分の1に相当した。ただし、実際に何十億台ものGPU搭載マシンが動いているわけではない。
採掘者はGPUより効率的な ASIC を使う。SHA-256 の計算だけに特化し、汎用計算を捨てた専用ハードウェアによって高い効率を得ている。最後にチャンネル登録、高評価、共有を案内して動画を締めくくる。
登場エンティティ・コンセプト
- sha-256 — Bitcoin でも使われる、256ビットの出力を持つ暗号学的ハッシュ関数。
- asic — 特定用途へ最適化した専用集積回路。Bitcoin 採掘ではGPUより効率よくハッシュを計算する。
- cryptographic-hash-function — 入力から固定長の値を生成し、改ざん検知や電子署名などに使う関数。
印象的な引用
宇宙の年齢の37倍計算したとしても、それでもまだ正しい推測を見つけた確率っていうのは40億分の1なんですね。
一般的な多様な計算を捨てて、一つの目的のためだけにデザインすると、かなり効率が上がるんですね。