Bitcoin Kangaroo Solver

Pollard's Kangaroo (lambda-method) Bitcoin puzzle solver — the most advanced open-source implementation available, written in Rust with triple-backend acceleration: CPU multi-threading, CUDA GPU, and WGPU cross-platform GPU.

• Not C++ — memory unsafety is unacceptable for financial computation; use-after-free in a 2-month solver run = catastrophic
• Not OpenCL — deprecated on macOS, poor Windows driver support, lower peak throughput vs native APIs
• Not pure Python — GIL-bound, 100-1000x slower for the tight secp256k1 inner loop; Python is acceptable only for orchestration
• Not a commercial service — you retain full control of your keys, no third-party trust required

The Pollard's Kangaroo algorithm is mathematically proven to find private keys given the corresponding public key. This implementation has been verified through:

• E2E integration test — generates random private keys in range [1, 10000), runs the solver, confirms it recovers the exact key
• Deterministic jumping — jump tables are derived from SHA-256(public key), ensuring reproducible walks across runs
• Collision-finding correctness — X-coordinate based tame↔wild detection is mathematically equivalent to full point comparison but 2x faster

For a key in range of size N, the expected number of iterations is 2√N (with SOTA K=1.15: ≈ 2.3√N). This is exponentially faster than brute-force which requires N/2 iterations on average.

For reference:

• Puzzle #135 (2^135 range) → ~2^67.6 expected steps (≈ ×ばつ10^20)
• Puzzle #160 (2^160 range) → ~2^80.6 expected steps (≈ ×ばつ10^24)

Expected time varies enormously by range size. Higher puzzles scale exponentially — Puzzle #135 (2^135 range) is ×ばつ harder than Puzzle #66.

These are estimates based on field size and known hardware benchmarks. Actual performance depends on memory bandwidth, core clock, and driver overhead.

• Use --release build with LTO (cargo build --release --features gpu-wgpu)
• Close all GPU-using applications (browser hardware acceleration, games)
• On AMD + Windows: ensure AMD Adrenalin driver is up to date
• On Linux + NVIDIA: use the proprietary driver (nouveau is 10x slower)
• Monitor GPU temperature — throttle starts at ~85°C
• Use 24/7 stable power (UPS recommended for multi-month runs)
• For multi-GPU: run separate instances per GPU, split the range

• Pollard's Kangaroo algorithm — O(√N) vs O(N) brute-force, requires public key
• Triple-backend acceleration:
  • CPU multi-threading (Rayon, works everywhere)
  • CUDA GPU (NVIDIA, --features gpu)
  • WGPU GPU (AMD/NVIDIA/Intel via Vulkan/DX12/Metal, --features gpu-wgpu)
• Negation map — ±Y symmetry halves search space (free 2x speedup)
• SOTA K=1.15 — optimal jump distribution, ~35% fewer steps vs standard
• Checkpoint/resume — periodic bincode serialization of distinguished points
• Graceful shutdown — Ctrl+C saves state, resumes from where it left off
• Telegram notification — instant alert when key is found
• Log file — timestamped key discovery records
• Built-in puzzle table — Puzzles #135, #140, #145, #150, #155, #160 with known ranges, addresses & embedded pubkeys

• Rust 1.75+ (edition 2021)
• Vulkan SDK (for WGPU) or CUDA Toolkit 11+ (for CUDA) — optional

# CPU-only (works everywhere)
cargo build --release
# CPU + WGPU (Vulkan/DX12/Metal — recommended for AMD/Intel GPUs)
cargo build --release --features gpu-wgpu
# CPU + CUDA (NVIDIA only)
cargo build --release --features gpu

# List built-in puzzles
bitcoin-kangaroo-solver --list
# Solve puzzle #135 with CPU (pubkey embedded, no --pubkey needed)
bitcoin-kangaroo-solver --puzzle 135 --threads 8
# Solve with WGPU GPU (AMD/NVIDIA/Intel)
bitcoin-kangaroo-solver --puzzle 140 --gpu wgpu
# Solve with CUDA GPU (NVIDIA only)
bitcoin-kangaroo-solver --puzzle 145 --gpu cuda
# Custom range with Telegram + checkpoint
bitcoin-kangaroo-solver \
 --start-range 0000000000000000000000000000000000000000000000000000000000000001 \
 --end-range 0000000000000000000000000000000000000000000000000000000001000000 \
 --pubkey 02<64_HEX_CHARS> \
 --address 1PVoXoTNaGWtnFfGAhf1RMycFUssCPnCGE \
 --checkpoint puzzle.cp \
 --telegram-bot-token <BOT_TOKEN> \
 --telegram-chat-id <CHAT_ID>
# Resume from checkpoint
bitcoin-kangaroo-solver --puzzle 135 --checkpoint puzzle.cp

src/
├── main.rs # CLI: clap args → config → solver dispatch
├── lib.rs # Module exports, INTERRUPTED flag
├── kangaroo/
│ ├── point.rs # secp256k1: Scalar, ProjectivePoint, jump table, address derivation
│ ├── walk.rs # KangarooWalk: step(), is_distinguished(), affine X cache
│ ├── collision.rs # CollisionFinder: X-coordinate based tame↔wild detection
│ ├── params.rs # KangarooParams: all solver configuration
│ └── distinguished.rs # is_distinguished() via SHA256 leading-zero bits
├── solver/
│ ├── mod.rs # Solver trait
│ ├── cpu/mod.rs # Rayon parallel solver, shared collision database
│ ├── gpu/mod.rs # CUDA init + CPU fallback (feature-gated)
│ └── wgpu_solver/ # WGPU compute shader solver (Vulkan/DX12/Metal)
├── checkpoint/mod.rs # bincode serialization
├── notification/mod.rs # FoundKey → Telegram, console, log file
└── puzzle/mod.rs # Built-in puzzle table (#135, #140, #145, #150, #155, #160 with embedded pubkeys)
kernels/
├── kangaroo.cu # CUDA kernel: Jacobian arithmetic, jump table, distinguished detection
└── kangaroo.wgsl # WGSL compute shader: cross-platform GPU kernel

1. Two herds of kangaroos — tame (red) and wild (blue) walk pseudo-randomly through the key space
2. Distinguished points — when a kangaroo lands on a point with specific bit pattern, it records its position
3. Collision — when tame and wild kangaroos visit the same X-coordinate, the private key is recovered: privkey = tame_dist - wild_dist
4. Parallelism — each GPU workgroup or CPU thread runs independent tame+wild pairs; distinguished points shared via collision database

# All unit + integration tests
cargo test
# E2E solver test (generates random key in [1, 10000), verifies solver finds it)
cargo test -- --ignored
# Clean check
cargo check

• Requires public key — Kangaroo algorithm cannot work with Bitcoin address alone. Most Bitcoin Puzzle challenges are address-only; you must obtain the compressed public key from out-of-band sources. Only puzzles #135, #140, #145, #150, #155, #160 have known public keys and are suitable for Kangaroo.
• Checkpoint resume trade-off — old distinguished points from previous run are kept as collision database, but all kangaroos start fresh (stale distances are incomparable across runs)
• WGPU on AMD: driver crash on complex shaders — the kernel itself (WGSL) compiles and dispatches correctly after the batch_invert → per-thread mod_inv fix. However, the full solver pipeline (multiple storage buffers, bind groups, dispatch loop) still crashes with STATUS_ACCESS_VIOLATION on the AMD RX 550 (Vulkan driver). This is a deeper driver-level issue. Workaround: CPU solver is fully functional; GPU solver requires a different AMD GPU or a future driver update.
• Deprecated: naga-0.20.0-patch.md — the earlier naga function-call argument caching bug has been resolved by restructuring shader code to avoid problematic patterns; the patch file is retained for reference only.

MIT

Developer: gkhantyln — Bitcoin Kangaroo Solver