Kangaroo

GPU-accelerated Pollard's Kangaroo algorithm for solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) on secp256k1.

Features

• 🖥️ Cross-platform GPU — Vulkan (AMD, NVIDIA, Intel), Metal (Apple Silicon), DX12 (Windows) via wgpu
• 🦀 Pure Rust + WGSL — no CUDA dependency, compute shaders compiled at runtime
• ⚡ Distinguished Points — efficient collision detection with auto-tuned DP bits
• 🔄 Negation map — ~1.29× speedup via Y-parity directed walks with cycle guards
• 🦘 Multi-set kangaroos — tame, wild1, wild2 herds for higher collision probability
• 🎯 Modular constraints — if k ≡ R (mod M), reduce search space by factor M
• ⚙️ Auto-calibration — GPU dispatch timing and workgroup size tuned at startup
• 📊 Built-in benchmarks — --benchmark to test hardware, --save-benchmarks to record results
• 📦 Data providers — pluggable puzzle sources (boha integration for Bitcoin puzzles)
• 💻 CPU fallback — pure CPU solver for testing and comparison

Why This Project?

Most existing Kangaroo implementations (JeanLucPons/Kangaroo, RCKangaroo, etc.) only support NVIDIA GPUs via CUDA. This implementation uses WebGPU/wgpu which provides cross-platform GPU compute through Vulkan, Metal, and DX12.

Installation

Arch Linux (AUR)

paru -S kangaroo

Cargo

cargo install kangaroo

From source

git clone https://github.com/oritwoen/kangaroo
cd kangaroo
cargo build --release

With boha provider

cargo build --release --features boha

Usage

kangaroo --pubkey <PUBKEY> --start <START> --range <BITS>

Arguments

Argument	Default	Description
-t, --target	-	Data provider target (e.g., boha:b1000/135)
-p, --pubkey	-	Target public key (compressed hex, 33 bytes)
-s, --start	0	Start of search range (hex, without 0x prefix)
-r, --range	32	Search range in bits (key is in [start, start + 2^range - 1])
-d, --dp-bits	auto	Distinguished point bits
-k, --kangaroos	auto	Number of parallel kangaroos
--gpu	0	GPU device index
--backend	auto	GPU backend: auto, vulkan, dx12, metal, gl
-o, --output	-	Output file for result
-q, --quiet	false	Minimal output, just print found key
--max-ops	0	Max operations (0 = unlimited)
--cpu	false	Use CPU solver instead of GPU
--json	false	Output benchmark results in JSON format
--benchmark	false	Run benchmark suite
--save-benchmarks	false	Save benchmark results to BENCHMARKS.md when --benchmark is used
--mod-step	1	Modular step M (hex): search only k ≡ R (mod M)
--mod-start	0	Modular residue R (hex): 0 ≤ R < M
--list-providers	false	List available puzzles from providers

Either --target or --pubkey is required.

Examples

Using data provider (boha):

# Solve puzzle using boha data (auto: pubkey, start, range)
kangaroo --target boha:b1000/66

# Override range (search smaller subset)
kangaroo --target boha:b1000/66 --range 60

# List available puzzles
kangaroo --list-providers

Manual parameters:

kangaroo \
    --pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 \
    --start 8000000000 \
    --range 40

With modular constraint (k ≡ 37 mod 60):

kangaroo \
    --pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 \
    --start 8000000000 \
    --range 40 \
    --mod-step 3c \
    --mod-start 25

This reduces the search space by ~60×. Useful when partial key structure is known (e.g., key generated with a predictable step pattern).

How It Works

The Pollard's Kangaroo algorithm solves the discrete logarithm problem in O(√n) time where n is the search range. It works by:

1. Tame kangaroos start from a known point and make random jumps
2. Wild kangaroos start from the target public key and make the same type of jumps
3. When a wild and tame kangaroo land on the same point (collision), we can compute the private key

Distinguished Points (DP) optimization: Instead of storing all visited points, we only store points whose x-coordinate has a specific number of leading zero bits. This dramatically reduces memory usage while still allowing collision detection.

Performance

Expected operations: ~2^(range_bits/2)

Run kangaroo --benchmark to test your hardware without touching files. Use kangaroo --benchmark --save-benchmarks to update BENCHMARKS.md.

Use Cases

Use Case	Example
Partial key decoded	Puzzle gives ~240 bits, need to find remaining ~16
Key in known range	Know key is between X and Y
Verify near-solution	Have candidate, search ±N bits around it

NOT useful for:

• Full 256-bit key search (mathematically impossible)
• BIP39 passphrase brute-force (use dictionary attack instead)
• Puzzles without partial key information

Library Usage

use kangaroo::{KangarooSolver, GpuContext, GpuBackend, parse_pubkey, parse_hex_u256, verify_key};

fn main() -> anyhow::Result<()> {
    let pubkey = parse_pubkey("03...")?;
    let start = parse_hex_u256("8000000000")?;

    let ctx = pollster::block_on(GpuContext::new(0, GpuBackend::Auto))?;
    let mut solver = KangarooSolver::new(
        ctx,
        pubkey.clone(),
        start,
        40,  // range_bits
        12,  // dp_bits
        1024, // num_kangaroos
    )?;

    loop {
        if let Some(key) = solver.step()? {
            if verify_key(&key, &pubkey) {
                println!("Found: {}", hex::encode(&key));
                break;
            }
        }
    }

    Ok(())
}

Data Providers

Kangaroo supports external data providers for puzzle sources. Providers supply pubkey, key range, and other puzzle metadata.

boha (optional feature)

boha provides crypto puzzle data including Bitcoin Puzzle Transaction (b1000).

Build with boha support:

cargo build --release --features boha

Usage:

# Solve specific puzzle
kangaroo --target boha:b1000/66

# List solvable puzzles (unsolved with known pubkey)
kangaroo --list-providers

Provider validates range overrides - you cannot search outside the puzzle's key range.

Architecture

src/
├── main.rs              # CLI entry point
├── lib.rs               # Library entry + Args + run()
├── solver.rs            # GPU solver coordination
├── cli.rs               # CLI utilities (tracing, progress bar)
├── benchmark.rs         # Built-in benchmark suite
├── modular.rs           # Modular constraint transformation
├── math.rs              # 256-bit arithmetic, DP mask generation
├── convert.rs           # Limb/byte conversions for GPU↔CPU
├── provider/
│   ├── mod.rs           # Provider system interface
│   └── boha.rs          # boha provider (feature-gated)
├── cpu/
│   ├── cpu_solver.rs    # Pure CPU solver (testing/comparison)
│   ├── dp_table.rs      # Distinguished Points collision detection
│   └── init.rs          # Kangaroo initialization + jump tables
├── crypto/
│   └── mod.rs           # k256/secp256k1 wrappers
├── gpu/
│   ├── pipeline.rs      # Compute pipeline setup
│   └── buffers.rs       # GPU buffer management
├── gpu_crypto/
│   ├── context.rs       # GPU context + backend selection
│   └── shaders/         # WGSL shader library
│       ├── field.wgsl   # secp256k1 field arithmetic
│       └── curve.wgsl   # Jacobian point operations
└── shaders/
    └── kangaroo_affine.wgsl  # Main Kangaroo compute shader

Requirements

• Rust 1.70+
• Vulkan-capable GPU (AMD, NVIDIA, Intel) or Metal (macOS)
• On Linux with AMD RADV, Mesa 25.x or newer is required (older Mesa versions may crash on WGSL dynamic indexing in shader loops)
• GPU drivers installed

License

MIT License - see LICENSE for details.

Related Projects

• JeanLucPons/Kangaroo - CUDA implementation (NVIDIA only)
• RCKangaroo - CUDA implementation (NVIDIA only)
• boha - Crypto puzzles and bounties data library