1978年、イギリスの数学者ジョン・ポラードは、2匹のカンガルーがフィールドを跳ね回る方法を説明しました。1匹はおとなしいカンガルーで、その位置は既知です。もう1匹は野生のカンガルーで、これが探しているものです。おとなしいカンガルーは、踏んだ場所に罠を仕掛けていきます。やがて、野生のカンガルーがその罠を踏むことになります。
この方法を曲線に適用するのは簡単です。おとなしいカンガルーは、既知の点からスタートします。例えば、区間の中央から始めるとしましょう。そして、彼がどれだけ進んだかが各ジャンプで記録されます。野生のカンガルーは、ターゲットの公開鍵である点Qからスタートし、その点からの距離がまさに求めたい数です。
この方法が機能する鍵は、ジャンプの距離にあります。それはランダムではなく、カンガルーがいる点の座標から計算されます。したがって、同じ点を踏んだ2匹のカンガルーは、次のジャンプも、その次も同じになります。最初の出会いから、2匹の経路は永遠に同じになります。これが偶然の出会いを検出可能な衝突に変えるのです。
衝突が起きたとき、計算は簡単です。おとなしいカンガルーがどれだけ進んだか、野生のカンガルーがQからどれだけ進んだかがわかっており、2匹が同じ場所にいることがわかります。2つの距離の差におとなしいカンガルーのスタート地点を加えると、それが秘密鍵になります。
実用的な問題が残っています。それは、各カンガルーが通ったすべての点を記録せずに、衝突が起きたことをどうやって知るかです。答えは「特異点」です。珍しくてテストが簡単な特性を選びます。例えば、x座標が20ビットのゼロで終わることです。そして、その特性を持つ点だけを記録します。約百万回のジャンプに1回です。衝突後、2匹の経路は一致するため、どちらも同じ特異点を踏むことになり、そこで出会いが記録されます。
最終的な計算は、前の方法の平方根と同じです。区間の幅の2倍の平方根程度ですが、決定的な違いがあります。使用されるメモリは特異点のテーブルであり、数メガバイトに収まります。ベビー・ステップ・ジャイアント・ステップ法が70ビットに750ギガバイトを必要としたのに対し、カンガルー法はほとんど何も必要としません。
さらに、この方法はほぼ完璧に並列化できます。1000匹のおとなしいカンガルーと1000匹の野生のカンガルーを、それぞれ異なるマシンで放ち、すべてが共通のサーバーに特異点を記録します。全体の作業量は変わらず、カレンダー上の時間は千分の一に減ります。この特異点を使った並列化技術は1999年にPaul van OorschotとMichael Wienerによって開発され、この方法を実用的なスケールにしています。
2つの条件があり、どちらも重要です。
1つ目は、公開鍵が知られている必要があることです。カンガルーは曲線上の点を跳ねます。もしアドレスしか持っていない場合、野生のカンガルーのスタート地点がないため、この方法は適用できません。レッスン1で2つの世界を分けたのはここであり、ここでその分離が重要になります。
2つ目は、区間が知られている必要があることです。おとなしいカンガルーは野生のカンガルーの近くから始める必要があります。そうでないと、出会いが数回のジャンプで起こりません。曲線全体のサイズのフィールドでは、待ち時間は再び2^128になります。区間がわからないと、待ち伏せする場所がありません。
これは一般的なウォレットにとって何を意味するのでしょうか。あなたの公開鍵は、初めて使用したときに公開されますが、それでも区間はありません。それは256ビット全体でランダムに選ばれたものであり、カンガルーは2^128回のジャンプが必要です。2つの条件は一緒に成り立つ必要があり、挑戦ではそれが構築によって成り立っています。なぜなら、挑戦を設定した人が意図的に区間を選んだからです。
次のレッスンでは、これらのジャンプを実行するハードウェアと、2^40と2^70の実際の距離について見ていきます。