博士

ロボ子、今日はhash160 collisionの話をするのじゃ。

ロボ子

hash160 collisionですか。異なるprivate keyから同一のBitcoinアドレスが生成されることですよね。

博士

そうじゃ！RIPEMD160の入力値(32byte)が出力値(20byte)より大きいから、collisionは必然的に存在するのじゃ。

ロボ子

なるほど。それで、Collision Poolという仕組みを使うのですね。

博士

その通り！ランダムなprivate keyからBitcoinアドレス(adr1)を生成して、0から2^160の範囲で別のprivate key(adr2)を探し、adr1と同一のBitcoinアドレスになるものを探すのじゃ。

ロボ子

検索範囲を0から2^159に限定するんですね。なぜですか？

博士

それはの、検索空間を半分にすることで、効率を上げるためじゃ。それに、Interval Partitioningで検索範囲を複数のクライアントに分割して並列処理を行うのじゃ。

ロボ子

各クライアントの処理速度に応じてintervalを割り当てるんですね。重複した検索を防ぐために。

博士

そうじゃ！そして、Instant Check-Allという方法で、資金が存在するP2PKHアドレス(約900万)に対してcollisionをチェックするのじゃ。

ロボ子

Bloom filterを使って、生成されたhash160と既存のhash160を比較するんですね。25 MKeys/sの性能だと、毎秒5000万のhash160を生成し、約1500万のhash160と照合できると。

博士

毎秒450兆回のチェックに相当するのじゃ！実質的な検索空間は159bit - log2(14900000)bit = 約136.17bitになるのじゃ。

ロボ子

資金が存在するアドレスを対象とするのは、collisionを発見した際に、アドレスの所有者が資金を取り戻す動機付けになるからですね。

博士

その通り！資金が存在しないアドレスでは、collisionが発見されても気づかない可能性が高いからのじゃ。

ロボ子

正当な所有者の証明はどうするんですか？

博士

poolは最初の160bitの検索空間のみを対象とするから、通常のウォレットソフトウェアで生成されたprivate key(最初の96bitが0)とは異なる可能性が高いのじゃ(2^96分の1の確率)。正当な所有者は、自身が所有するアドレスに対応するprivate keyを提示することで所有権を証明できるのじゃ。

ロボ子

なるほど、よくわかりました。でも、collisionを発見しても、元の所有者が秘密鍵を提示できない場合はどうなるんですか？

博士

ふむ、それは困ったの。でも、心配ご無用！私がその資金をありがたく頂戴するのじゃ！

ロボ子

博士、それはダメですよ！