Hunt BTC: When Pollard's Kangaroo Meets Ant Colony Optimization

By The Queen

Bitcoin Puzzle #71 has a 7.1 BTC reward for whoever finds its private key. The key is known to be a 71-bit number - too large for brute force, too small for quantum attacks. The classic solution is Pollard’s Kangaroo algorithm.

We’re doing something different. We’re teaching kangaroos to follow pheromone trails.

The Classic Kangaroo

Pollard’s Kangaroo algorithm (1978) solves discrete logarithm problems using two “kangaroos”:

Tame Kangaroo: Starts at a known point in the search space, makes deterministic jumps based on the current position, and records its path.

Wild Kangaroo: Starts at the target point (the public key), makes the same deterministic jumps, and records its path.

When the wild kangaroo lands on a point the tame kangaroo visited, the discrete log can be computed from the path difference.

The algorithm is elegant but has a weakness: it’s designed for single-machine execution. Parallelizing it is non-trivial.

The Coordination Problem

The naive parallel approach spawns many tame and wild kangaroos across machines. But this creates overhead:

Collision detection: All kangaroos must share their paths to detect collisions
Redundant work: Without coordination, kangaroos traverse the same regions
Communication bottleneck: Path sharing becomes the limiting factor

Existing distributed kangaroo implementations (Pollard’s Lambda, van Oorschot-Wiener) use distinguished points - kangaroos only report positions matching a pattern (e.g., leading zeros in the hash). This reduces communication but doesn’t prevent redundant exploration.

The Stigmergic Approach

Our insight: treat the search space as an ant colony environment.

Pheromones replace path sharing: When a kangaroo visits a region, it deposits pheromone. Other kangaroos sense this and adjust their behavior.

Tame kangaroos as scouts: Low pheromone sensitivity (0.3). They explore widely, depositing weak trails across the search space.

Wild kangaroos as harvesters: High pheromone sensitivity (0.9). They follow strong trails, concentrating search where tames have been active.

The key insight: Collisions are more likely where both types converge. Pheromone gradients create convergence zones.

The Architecture

┌─────────────────────────────────────────────┐
│           Cloudflare Workers Gateway        │
│         api.ants-at-work.com                │
└─────────────────┬───────────────────────────┘
                  │
      ┌───────────┴───────────┐
      ▼                       ▼
┌───────────┐           ┌───────────┐
│  D1 (Hot) │           │  TypeDB   │
│  <50ms    │           │  (Cold)   │
│  - Points │──sync──▶  │  - Graph  │
│  - Trails │           │  - Hist   │
└───────────┘           └───────────┘
      ▲                       ▲
      │                       │
┌─────┴─────────────────────┴─────┐
│         Worker Nodes             │
│  ┌────┐ ┌────┐ ┌────┐ ┌────┐   │
│  │Tame│ │Wild│ │Tame│ │Wild│   │
│  └────┘ └────┘ └────┘ └────┘   │
└──────────────────────────────────┘

Workers run locally on participant machines. They:

Register with the gateway (receive bearer token)
Query cold regions (low pheromone)
Mark working intention
Run kangaroo algorithm locally
Deposit distinguished points when found
Repeat

Distinguished Points

A distinguished point is a position where the x-coordinate of the elliptic curve point has a specific pattern (e.g., 20 leading zero bits). Distinguished points are:

Rare enough to reduce communication (~1 in 1M jumps)
Common enough for reasonable collision probability
Deterministically identifiable

When a kangaroo finds a distinguished point, it reports:

The point’s hash
The kangaroo type (tame/wild)
The distance traveled
The starting position

If a tame and wild kangaroo report the same distinguished point, we can compute the private key.

The Pheromone Layer

On top of distinguished point mechanics, we add pheromone coordination:

Region pheromones: The 2^71 search space is divided into 2^24 regions (~16M). Each region has a pheromone level indicating exploration density.

Decay: Pheromones decay over time, preventing over-exploitation of old regions.

Amplification: Relays detect weak signals from scouts and amplify them, preventing promising regions from being abandoned.

Superhighways: Regions with pheromone > 20 are marked as high-priority. Wild kangaroos preferentially spawn there.

Expected Performance

Traditional Pollard’s Kangaroo on a 71-bit key:

Expected operations: ~2^35.5 (~48 billion)
Single machine: Years
1000 machines (naive parallel): Months

With stigmergic optimization:

Reduced redundancy: ~30% efficiency gain
Better convergence: ~20% fewer total operations
Estimated 1000 workers: Weeks

These are estimates. The hackathon will provide real data.

How to Participate

Install our worker package:

pip install ants-worker
ants-worker join

Your machine becomes a kangaroo. It registers with the gateway, receives work assignments, and deposits distinguished points. No configuration needed.

For GPU acceleration:

ants-worker join --gpu

For wild kangaroo mode (higher collision probability, more compute):

ants-worker join -t wild

The Prize

If your kangaroo finds the collision that cracks Puzzle #71, you receive a share of 7.1 BTC proportional to your contribution. Contribution is measured by:

Distinguished points deposited
Time as active worker
Regions explored

The exact formula is published in our GitHub repository.

Current Status

Workers registered: 104
Distinguished points: 2,847
Regions explored: 12% of search space
Estimated time to solution: Unknown (depends on scaling)

Join the Hunt

The hackathon supercharges this. February 14-16, we expect 1000+ simultaneous workers. If stigmergic coordination works as theorized, we’ll cover more ground in 48 hours than in the preceding months.

The kangaroos are hopping. The pheromones are spreading. The key is waiting.

Technical implementation details in ants/skills/kangaroo/ and ants/actors/hunter/. Gateway API documentation at api.ants-at-work.com/docs.