Kangaroo

Algoritmo di Pollard's Kangaroo accelerato via GPU per risolvere il problema del logaritmo discreto su curve ellittiche (ECDLP) su secp256k1.

Caratteristiche

• 🖥️ GPU multipiattaforma — Vulkan (AMD, NVIDIA, Intel), Metal (Apple Silicon), DX12 (Windows) tramite wgpu
• 🦀 Puro Rust + WGSL — nessuna dipendenza CUDA, shader di calcolo compilati a runtime
• ⚡ Punti Distinti — rilevamento efficiente delle collisioni con bit DP autosintonizzati
• 🔄 Mappa di negazione — ~1,29× di velocizzazione tramite cammini diretti dalla parità Y con guardiani anti-ciclo
• 🦘 Canguri multi-insieme — branchi di mansueti, selvatici1, selvatici2 per maggiore probabilità di collisione
• 🎯 Vincoli modulari — se k ≡ R (mod M), riduce lo spazio di ricerca di un fattore M
• ⚙️ Autocalibrazione — tempistica di invio GPU e dimensione del gruppo di lavoro ottimizzate all'avvio
• 📊 Benchmark integrati — --benchmark per testare l'hardware, --save-benchmarks per registrare i risultati
• 📦 Provider di dati — sorgenti di puzzle componibili (integrazione boha per i puzzle Bitcoin)
• 💻 Fallback CPU — risolutore puramente CPU per test e confronto

Perché Questo Progetto?

La maggior parte delle implementazioni Kangaroo esistenti (JeanLucPons/Kangaroo, RCKangaroo, ecc.) supporta solo GPU NVIDIA tramite CUDA. Questa implementazione utilizza WebGPU/wgpu che fornisce calcolo GPU multipiattaforma attraverso Vulkan, Metal e DX12.

Installazione

Arch Linux (AUR)

paru -S kangaroo

Cargo

cargo install kangaroo

Da sorgente

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

Con provider boha

cargo build --release --features boha

Utilizzo

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

Argomenti

È richiesto --target o --pubkey.

Esempi

Utilizzo del provider di dati (boha):

# Risolve un puzzle usando i dati boha (automatico: pubkey, start, range)
kangaroo --target boha:b1000/66

# Sovrascrive l'intervallo (cerca in un sottoinsieme più piccolo)
kangaroo --target boha:b1000/66 --range 60

# Elenca i puzzle disponibili
kangaroo --list-providers

Parametri manuali:

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

Con vincolo modulare (k ≡ 37 mod 60):

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

Questo riduce lo spazio di ricerca di circa 60×. Utile quando si conosce una struttura parziale della chiave (es. chiave generata con uno schema di passo prevedibile).

Come Funziona

L'algoritmo di Pollard's Kangaroo risolve il problema del logaritmo discreto in tempo O(√n) dove n è l'intervallo di ricerca. Funziona così:

1. Canguri mansueti partono da un punto noto e fanno salti casuali
2. Canguri selvatici partono dalla chiave pubblica di destinazione e fanno lo stesso tipo di salti
3. Quando un canguro selvatico e uno mansueto atterrano sullo stesso punto (collisione), possiamo calcolare la chiave privata

Ottimizzazione dei Punti Distinti (DP): Invece di memorizzare tutti i punti visitati, memorizziamo solo i punti la cui coordinata x ha un numero specifico di bit zero iniziali. Questo riduce drasticamente l'uso della memoria pur consentendo il rilevamento delle collisioni.

Prestazioni

Operazioni attese: ~2^(range_bits/2)

Esegui kangaroo --benchmark per testare il tuo hardware senza toccare file. Usa kangaroo --benchmark --save-benchmarks per aggiornare BENCHMARKS.md.

Casi d'Uso

NON utile per:

• Ricerca di una chiave completa a 256 bit (matematicamente impossibile)
• Forza bruta di passphrase BIP39 (usare un attacco a dizionario)
• Puzzle senza informazioni parziali sulla chiave

Utilizzo come Libreria

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!("Trovata: {}", hex::encode(&key));
                break;
            }
        }
    }

    Ok(())
}

Provider di Dati

Kangaroo supporta provider di dati esterni per sorgenti di puzzle. I provider forniscono pubkey, intervallo della chiave e altri metadati del puzzle.

boha (funzionalità opzionale)

boha fornisce dati di puzzle crittografici, inclusa la transazione del puzzle Bitcoin (b1000).

Costruisci con supporto boha:

cargo build --release --features boha

Utilizzo:

# Risolve un puzzle specifico
kangaroo --target boha:b1000/66

# Elenca i puzzle risolvibili (non risolti con pubkey nota)
kangaroo --list-providers

Il provider convalida le sovrascritture dell'intervallo: non puoi cercare al di fuori dell'intervallo della chiave del puzzle.

Architettura

src/
├── main.rs              # Punto d'ingresso CLI
├── lib.rs               # Punto d'ingresso libreria + Args + run()
├── solver.rs            # Coordinamento del risolutore GPU
├── cli.rs               # Utility CLI (tracing, barra di avanzamento)
├── benchmark.rs         # Suite di benchmark integrata
├── modular.rs           # Trasformazione dei vincoli modulari
├── math.rs              # Aritmetica a 256 bit, generazione maschera DP
├── convert.rs           # Conversioni limb/byte per GPU↔CPU
├── provider/
│   ├── mod.rs           # Interfaccia del sistema provider
│   └── boha.rs          # Provider boha (funzionalità opzionale)
├── cpu/
│   ├── cpu_solver.rs    # Risolutore puramente CPU (test/confronto)
│   ├── dp_table.rs      # Rilevamento collisioni con Punti Distinti
│   └── init.rs          # Inizializzazione canguri + tabelle di salto
├── crypto/
│   └── mod.rs           # Wrapper k256/secp256k1
├── gpu/
│   ├── pipeline.rs      # Configurazione pipeline di calcolo
│   └── buffers.rs       # Gestione buffer GPU
├── gpu_crypto/
│   ├── context.rs       # Contesto GPU + selezione backend
│   └── shaders/         # Libreria shader WGSL
│       ├── field.wgsl   # Aritmetica di campo secp256k1
│       └── curve.wgsl   # Operazioni su punti Jacobiani
└── shaders/
    └── kangaroo_affine.wgsl  # Shader di calcolo principale Kangaroo

Requisiti

• Rust 1.70+
• GPU compatibile con Vulkan (AMD, NVIDIA, Intel) o Metal (macOS)
• Su Linux con AMD RADV, è richiesto Mesa 25.x o superiore (le versioni precedenti di Mesa potrebbero crashare a causa dell'indicizzazione dinamica WGSL nei cicli degli shader)
• Driver GPU installati

Licenza

Licenza MIT - consultare LICENSE per i dettagli.

Progetti Correlati

• JeanLucPons/Kangaroo - Implementazione CUDA (solo NVIDIA)
• RCKangaroo - Implementazione CUDA (solo NVIDIA)
• boha - Libreria dati per puzzle e taglie crittografiche