Kangaroo

Algoritmo Pollard's Kangaroo acelerado por GPU para resolver el Problema del Logaritmo Discreto de Curva Elíptica (ECDLP) en secp256k1.

Características

• 🖥️ GPU multiplataforma — Vulkan (AMD, NVIDIA, Intel), Metal (Apple Silicon), DX12 (Windows) mediante wgpu
• 🦀 Rust puro + WGSL — sin dependencia de CUDA, shaders de cómputo compilados en tiempo de ejecución
• ⚡ Puntos distinguidos — detección eficiente de colisiones con bits DP autoajustados
• 🔄 Mapa de negación — ~1.29× de aceleración mediante recorridos dirigidos por paridad Y con guardas de ciclo
• 🦘 Canguros multi-conjunto — manadas tame, wild1, wild2 para mayor probabilidad de colisión
• 🎯 Restricciones modulares — si k ≡ R (mod M), reduce el espacio de búsqueda en un factor M
• ⚙️ Auto-calibración — temporización de despacho GPU y tamaño del grupo de trabajo ajustados al inicio
• 📊 Benchmarks integrados — --benchmark para probar el hardware, --save-benchmarks para registrar resultados
• 📦 Proveedores de datos — fuentes de acertijos conectables (integración boha para acertijos Bitcoin)
• 💻 Fallback a CPU — solucionador puro de CPU para pruebas y comparación

¿Por qué este proyecto?

La mayoría de implementaciones existentes de Kangaroo (JeanLucPons/Kangaroo, RCKangaroo, etc.) solo soportan GPUs NVIDIA mediante CUDA. Esta implementación utiliza WebGPU/wgpu, lo que proporciona cómputo GPU multiplataforma a través de Vulkan, Metal y DX12.

Instalación

Arch Linux (AUR)

paru -S kangaroo

Cargo

cargo install kangaroo

Desde el código fuente

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

Con el proveedor boha

cargo build --release --features boha

Uso

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

Argumentos

Se requiere --target o --pubkey.

Ejemplos

Usando proveedor de datos (boha):

# Resolver acertijo usando datos de boha (automático: pubkey, start, range)
kangaroo --target boha:b1000/66

# Sobrescribir rango (buscar subconjunto más pequeño)
kangaroo --target boha:b1000/66 --range 60

# Listar acertijos disponibles
kangaroo --list-providers

Parámetros manuales:

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

Con restricción modular (k ≡ 37 mod 60):

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

Esto reduce el espacio de búsqueda en ~60×. Útil cuando se conoce una estructura parcial de la clave (por ejemplo, clave generada con un patrón de paso predecible).

Cómo funciona

El algoritmo Pollard's Kangaroo resuelve el problema del logaritmo discreto en tiempo O(√n) donde n es el rango de búsqueda. Funciona así:

1. Canguros tame parten de un punto conocido y realizan saltos aleatorios
2. Canguros wild parten de la clave pública objetivo y realizan el mismo tipo de saltos
3. Cuando un canguro wild y uno tame aterrizan en el mismo punto (colisión), podemos calcular la clave privada

Optimización de Puntos Distinguidos (DP): En lugar de almacenar todos los puntos visitados, solo guardamos aquellos cuya coordenada x tiene un número específico de bits cero iniciales. Esto reduce drásticamente el uso de memoria y permite la detección de colisiones.

Rendimiento

Operaciones esperadas: ~2^(range_bits/2)

Ejecute kangaroo --benchmark para probar su hardware sin tocar archivos. Use kangaroo --benchmark --save-benchmarks para actualizar BENCHMARKS.md.

Casos de uso

NO útil para:

• Búsqueda de clave completa de 256 bits (matemáticamente imposible)
• Fuerza bruta de frase de contraseña BIP39 (usar ataque de diccionario)
• Acertijos sin información parcial de clave

Uso como biblioteca

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(())
}

Proveedores de datos

Kangaroo admite proveedores de datos externos para fuentes de acertijos. Los proveedores suministran clave pública, rango de clave y otros metadatos del acertijo.

boha (característica opcional)

boha proporciona datos de acertijos criptográficos, incluida la transacción de acertijos de Bitcoin (b1000).

Compilar con soporte boha:

cargo build --release --features boha

Uso:

# Resolver acertijo específico
kangaroo --target boha:b1000/66

# Listar acertijos resolubles (no resueltos con clave pública conocida)
kangaroo --list-providers

El proveedor valida las sobrescrituras de rango: no se puede buscar fuera del rango de clave del acertijo.

Arquitectura

src/
├── main.rs              # Punto de entrada CLI
├── lib.rs               # Entrada de biblioteca + Args + run()
├── solver.rs            # Coordinación del solucionador GPU
├── cli.rs               # Utilidades CLI (tracing, barra de progreso)
├── benchmark.rs         # Suite de benchmarks integrada
├── modular.rs           # Transformación de restricción modular
├── math.rs              # Aritmética de 256 bits, generación de máscara DP
├── convert.rs           # Conversiones limb/byte para GPU↔CPU
├── provider/
│   ├── mod.rs           # Interfaz del sistema de proveedores
│   └── boha.rs          # Proveedor boha (controlado por característica)
├── cpu/
│   ├── cpu_solver.rs    # Solucionador puro de CPU (pruebas/comparación)
│   ├── dp_table.rs      # Detección de colisiones de Puntos Distinguidos
│   └── init.rs          # Inicialización de canguros + tablas de saltos
├── crypto/
│   └── mod.rs           # Wrappers k256/secp256k1
├── gpu/
│   ├── pipeline.rs      # Configuración del pipeline de cómputo
│   └── buffers.rs       # Gestión de buffers GPU
├── gpu_crypto/
│   ├── context.rs       # Contexto GPU + selección de backend
│   └── shaders/         # Biblioteca de shaders WGSL
│       ├── field.wgsl   # Aritmética de campo secp256k1
│       └── curve.wgsl   # Operaciones de puntos Jacobianos
└── shaders/
    └── kangaroo_affine.wgsl  # Shader de cómputo principal de Kangaroo

Requisitos

• Rust 1.70+
• GPU compatible con Vulkan (AMD, NVIDIA, Intel) o Metal (macOS)
• En Linux con AMD RADV, se requiere Mesa 25.x o más reciente (versiones anteriores de Mesa pueden fallar con indexación dinámica WGSL en bucles de shaders)
• Controladores GPU instalados

Licencia

Licencia MIT - consulte LICENSE para más detalles.

Proyectos relacionados

• JeanLucPons/Kangaroo - Implementación CUDA (solo NVIDIA)
• RCKangaroo - Implementación CUDA (solo NVIDIA)
• boha - Biblioteca de datos de acertijos criptográficos y recompensas