The algorithm that overcame the greatest challenges ever solved is named after an animal because the author himself explained it that way. In 1978, British mathematician John Pollard described a method where two kangaroos jump across a field: a tame one, whose position is known, and a wild one, which is the one being sought. The tame one leaves traps where it steps. Sooner or later, the wild one steps on one of them.
The translation to the curve is straightforward. The tame kangaroo starts from a known point within the interval — let's say the middle of it — and the distance it has already traveled is noted at each jump. The wild kangaroo starts from point Q, the target's public key, whose distance from the origin is exactly the number one wants to discover.
The detail that makes everything work is the size of the jumps. It is not random: it is calculated from the coordinate of the point where the kangaroo is. Two kangaroos that step on the same point, therefore, make the same next jump, and the next, and the next — from the first meeting, the two paths are identical forever. This is what turns a casual meeting into a detectable collision.
When the collision happens, the calculation is trivial. It is known how far the tame one has traveled, it is known how far the wild one has traveled from Q, and it is known that both are in the same place. The difference between the two distances, added to the starting point of the tame one, is the private key.
There remains a practical problem to solve: how to perceive that the collision happened without storing all the points each kangaroo passed through? The answer is distinguished points. A rare and easy-to-test property is chosen — for example, that the x-coordinate ends in twenty zero bits — and the point is only noted when it has this property. About one in every million jumps. Since after the collision the two paths coincide, both will eventually step on the same distinguished point, and it is there that the meeting is recorded.
The final calculation is the same square root as the previous method — something around two times the square root of the interval's width — with a decisive difference: the memory used is the table of distinguished points, which fits in a few megabytes. Where the baby step and giant step required seven hundred and fifty gigabytes for seventy bits, the kangaroo requires almost nothing.
Add to this that it parallelizes almost perfectly. Release a thousand tame kangaroos and a thousand wild ones, each on a different machine, all recording distinguished points on a common server: the total work does not change, and the calendar time drops by a thousand. The parallelization technique with distinguished points is from 1999, by Paul van Oorschot and Michael Wiener, and it is what makes the method practical on a large scale.
There are two conditions, and both matter.
The first is that the public key needs to be known. The kangaroo jumps over points on the curve; if you only have the address, there is no starting point for the wild one, and the method does not apply. It was Lesson 1 that separated the two worlds, and it is here that the separation takes its toll.
The second is that the interval needs to be known. The tame kangaroo needs to start near the wild one for the meeting to happen in a few jumps; in a field the size of the entire curve, the wait returns to 2^128. Without knowing the segment, there is nowhere to set the trap.
Notice what this means for a common wallet. Your public key is exposed as soon as you spend for the first time, and yet there is no interval: it was randomly chosen in 256 whole bits, and the kangaroo would need 2^128 jumps. Both conditions need to be met together, and in a challenge, they are met by design — because whoever set it up chose the interval on purpose.
We still need to look at the hardware that executes these jumps, and where it stops. In the next lesson, graphics cards, ASICs, and the real distance between 2^40 and 2^70.