Kangaroo

Algoritmo Pollard's Kangaroo acelerado por GPU para resolver o Problema do Logaritmo Discreto de Curva Elíptica (ECDLP) no secp256k1.

Funcionalidades

• 🖥️ GPU multiplataforma — Vulkan (AMD, NVIDIA, Intel), Metal (Apple Silicon), DX12 (Windows) via wgpu
• 🦀 Rust puro + WGSL — sem dependência CUDA, shaders de computação compilados em tempo de execução
• ⚡ Pontos Distintos — detecção eficiente de colisão com bits DP ajustados automaticamente
• 🔄 Mapa de negação — ~1,29× de aceleração via caminhos direcionados por paridade Y com guardas de ciclo
• 🦘 Cangurus multi-conjunto — rebanhos tame, wild1, wild2 para maior probabilidade de colisão
• 🎯 Restrições modulares — se k ≡ R (mod M), reduz o espaço de busca pelo fator M
• ⚙️ Calibração automática — temporização de dispatch da GPU e tamanho do workgroup ajustados na inicialização
• 📊 Benchmarks integrados — --benchmark para testar hardware, --save-benchmarks para registrar resultados
• 📦 Provedores de dados — fontes de puzzles plugáveis (integração boha para puzzles Bitcoin)
• 💻 Fallback CPU — resolvedor puro em CPU para teste e comparação

Por Que Este Projeto?

A maioria das implementações existentes de Kangaroo (JeanLucPons/Kangaroo, RCKangaroo, etc.) suporta apenas GPUs NVIDIA via CUDA. Esta implementação usa WebGPU/wgpu, que fornece computação GPU multiplataforma através de Vulkan, Metal e DX12.

Instalação

Arch Linux (AUR)

paru -S kangaroo

Cargo

cargo install kangaroo

A partir do código fonte

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

Com provedor boha

cargo build --release --features boha

Uso

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

Argumentos

É necessário fornecer --target ou --pubkey.

Exemplos

Usando provedor de dados (boha):

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

# Sobrescrever range (buscar subconjunto menor)
kangaroo --target boha:b1000/66 --range 60

# Listar puzzles disponíveis
kangaroo --list-providers

Parâmetros manuais:

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

Com restrição modular (k ≡ 37 mod 60):

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

Isso reduz o espaço de busca em ~60×. Útil quando a estrutura parcial da chave é conhecida (ex.: chave gerada com um padrão de passo previsível).

Como Funciona

O algoritmo Pollard's Kangaroo resolve o problema do logaritmo discreto em tempo O(√n), onde n é a faixa de busca. Ele funciona da seguinte forma:

1. Cangurus tame começam de um ponto conhecido e fazem saltos aleatórios
2. Cangurus wild começam da chave pública alvo e fazem o mesmo tipo de saltos
3. Quando um canguru wild e um tame pousam no mesmo ponto (colisão), podemos calcular a chave privada

Otimização de Pontos Distintos (DP): em vez de armazenar todos os pontos visitados, armazenamos apenas pontos cuja coordenada x tenha um número específico de bits zero à esquerda. Isso reduz drasticamente o uso de memória, ainda permitindo a detecção de colisões.

Desempenho

Operações esperadas: ~2^(range_bits/2)

Execute kangaroo --benchmark para testar seu hardware sem tocar em arquivos. Use kangaroo --benchmark --save-benchmarks para atualizar BENCHMARKS.md.

Casos de Uso

NÃO é útil para:

• Busca completa de chave de 256 bits (matematicamente impossível)
• Força bruta de frase-semente BIP39 (use ataque de dicionário)
• Puzzles sem informações parciais da chave

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

Provedores de Dados

Kangaroo suporta provedores de dados externos para fontes de puzzles. Os provedores fornecem pubkey, faixa de chave e outros metadados do puzzle.

boha (funcionalidade opcional)

boha fornece dados de puzzles criptográficos, incluindo Bitcoin Puzzle Transaction (b1000).

Compile com suporte a boha:

cargo build --release --features boha

Uso:

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

# Listar puzzles solucionáveis (não resolvidos com pubkey conhecida)
kangaroo --list-providers

O provedor valida substituições de range — você não pode pesquisar fora da faixa de chave do puzzle.

Arquitetura

src/
├── main.rs              # Ponto de entrada CLI
├── lib.rs               # Entrada da biblioteca + Args + run()
├── solver.rs            # Coordenação do resolvedor GPU
├── cli.rs               # Utilitários CLI (tracing, barra de progresso)
├── benchmark.rs         # Conjunto de benchmarks integrado
├── modular.rs           # Transformação de restrição modular
├── math.rs              # Aritmética de 256 bits, geração de máscara DP
├── convert.rs           # Conversões Limb/byte para GPU↔CPU
├── provider/
│   ├── mod.rs           # Interface do sistema de provedores
│   └── boha.rs          # Provedor boha (protegido por feature)
├── cpu/
│   ├── cpu_solver.rs    # Resolvedor puro em CPU (teste/comparação)
│   ├── dp_table.rs      # Detecção de colisão por Pontos Distintos
│   └── init.rs          # Inicialização dos cangurus + tabelas de salto
├── crypto/
│   └── mod.rs           # Wrappers k256/secp256k1
├── gpu/
│   ├── pipeline.rs      # Configuração do pipeline de computação
│   └── buffers.rs       # Gerenciamento de buffers GPU
├── gpu_crypto/
│   ├── context.rs       # Contexto GPU + seleção de backend
│   └── shaders/         # Biblioteca de shaders WGSL
│       ├── field.wgsl   # Aritmética de corpo secp256k1
│       └── curve.wgsl   # Operações de ponto Jacobiano
└── shaders/
    └── kangaroo_affine.wgsl  # Shader de computação principal Kangaroo

Requisitos

• Rust 1.70+
• GPU com capacidade Vulkan (AMD, NVIDIA, Intel) ou Metal (macOS)
• No Linux com AMD RADV, é necessário Mesa 25.x ou mais recente (versões mais antigas do Mesa podem falhar em indexação dinâmica WGSL em loops de shader)
• Drivers GPU instalados

Licença

Licença MIT — veja LICENSE para detalhes.

Projetos Relacionados

• JeanLucPons/Kangaroo — Implementação CUDA (apenas NVIDIA)
• RCKangaroo — Implementação CUDA (apenas NVIDIA)
• boha — Biblioteca de dados de puzzles e recompensas criptográficas