Kangaroo

GPU-beschleunigter Pollard's Kangaroo-Algorithmus zur Lösung des Problems des diskreten Logarithmus auf elliptischen Kurven (ECDLP) auf secp256k1.

Funktionen

• 🖥️ Plattformübergreifende GPU — Vulkan (AMD, NVIDIA, Intel), Metal (Apple Silicon), DX12 (Windows) über wgpu
• 🦀 Reines Rust + WGSL — keine CUDA-Abhängigkeit, Compute-Shader werden zur Laufzeit kompiliert
• ⚡ Ausgezeichnete Punkte — effiziente Kollisionserkennung mit automatisch abgestimmten DP-Bits
• 🔄 Negationsabbildung — ~1,29× Beschleunigung durch Y-Paritätsgesteuerte Läufe mit Zykluswächtern
• 🦘 Multi-Set-Kängurus — zahme, wilde1, wilde2 Herden für höhere Kollisionswahrscheinlichkeit
• 🎯 Modulare Einschränkungen — wenn k ≡ R (mod M), Reduzierung des Suchraums um den Faktor M
• ⚙️ Autokalibrierung — GPU-Dispatch-Timing und Workgroup-Größe werden beim Start optimiert
• 📊 Integrierte Benchmarks — --benchmark zum Testen der Hardware, --save-benchmarks zum Aufzeichnen der Ergebnisse
• 📦 Datenanbieter — steckbare Puzzle-Quellen (boha-Integration für Bitcoin-Puzzles)
• 💻 CPU-Notfalllösung — reiner CPU-Löser zum Testen und Vergleichen

Warum dieses Projekt?

Die meisten existierenden Kangaroo-Implementierungen unterstützen nur NVIDIA-GPUs über CUDA. Diese Implementierung nutzt WebGPU/wgpu, das plattformübergreifendes GPU-Computing über Vulkan, Metal und DX12 bereitstellt.

Installation

Arch Linux (AUR)

paru -S kangaroo

Cargo

cargo install kangaroo

Aus dem Quellcode

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

Mit boha-Anbieter

cargo build --release --features boha

Verwendung

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

Argumente

Entweder --target oder --pubkey ist erforderlich.

Beispiele

Datenanbieter verwenden (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

Manuelle Parameter:

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

Mit modularer Einschränkung (k ≡ 37 mod 60):

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

Dies reduziert den Suchraum um etwa das 60-fache. Nützlich, wenn die partielle Schlüsselstruktur bekannt ist (z.B. Schlüssel generiert mit einem vorhersagbaren Schrittmuster).

Funktionsweise

Der Pollard's Kangaroo-Algorithmus löst das Problem des diskreten Logarithmus in O(√n) Zeit, wobei n der Suchbereich ist. Er funktioniert wie folgt:

1. Zahme Kängurus beginnen an einem bekannten Punkt und machen zufällige Sprünge
2. Wilde Kängurus beginnen am Ziel-öffentlichen Schlüssel und machen die gleiche Art von Sprüngen
3. Wenn ein wildes und ein zahmes Känguru auf demselben Punkt landen (Kollision), können wir den privaten Schlüssel berechnen

Optimierung durch ausgezeichnete Punkte (DP): Anstatt alle besuchten Punkte zu speichern, speichern wir nur Punkte, deren x-Koordinate eine bestimmte Anzahl führender Nullbits aufweist. Dies reduziert den Speicherverbrauch drastisch und ermöglicht dennoch die Kollisionserkennung.

Leistung

Erwartete Operationen: ~2^(range_bits/2)

Führen Sie kangaroo --benchmark aus, um Ihre Hardware zu testen, ohne Dateien zu berühren. Verwenden Sie kangaroo --benchmark --save-benchmarks, um BENCHMARKS.md zu aktualisieren.

Anwendungsfälle

NICHT nützlich für:

• Vollständige 256-Bit-Schlüsselsuche (mathematisch unmöglich)
• BIP39-Passphrase-Brute-Force (verwenden Sie stattdessen einen Wörterbuchangriff)
• Puzzles ohne partielle Schlüsselinformationen

Bibliotheksnutzung

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

Datenanbieter

Kangaroo unterstützt externe Datenanbieter für Puzzle-Quellen. Anbieter liefern pubkey, Schlüsselbereich und andere Puzzle-Metadaten.

boha (optionale Funktion)

boha stellt Krypto-Puzzle-Daten einschließlich Bitcoin Puzzle Transaction (b1000) bereit.

Build mit boha-Unterstützung:

cargo build --release --features boha

Verwendung:

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

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

Der Anbieter validiert Bereichsüberschreibungen - Sie können nicht außerhalb des Schlüsselbereichs des Puzzles suchen.

Architektur

src/
├── main.rs              # CLI-Einstiegspunkt
├── lib.rs               # Bibliothekseinstieg + Args + run()
├── solver.rs            # GPU-Löser-Koordination
├── cli.rs               # CLI-Dienstprogramme (tracing, Fortschrittsbalken)
├── benchmark.rs         # Integrierte Benchmark-Suite
├── modular.rs           # Transformation modularer Einschränkungen
├── math.rs              # 256-Bit-Arithmetik, DP-Maskenerzeugung
├── convert.rs           # Limb/Byte-Konvertierungen für GPU↔CPU
├── provider/
│   ├── mod.rs           # Anbietersystem-Schnittstelle
│   └── boha.rs          # boha-Anbieter (feature-gated)
├── cpu/
│   ├── cpu_solver.rs    # Reiner CPU-Löser (Testen/Vergleichen)
│   ├── dp_table.rs      # Kollisionserkennung via ausgezeichneter Punkte
│   └── init.rs          # Känguru-Initialisierung + Sprungtabellen
├── crypto/
│   └── mod.rs           # k256/secp256k1-Wrapper
├── gpu/
│   ├── pipeline.rs      # Compute-Pipeline-Einrichtung
│   └── buffers.rs       # GPU-Pufferverwaltung
├── gpu_crypto/
│   ├── context.rs       # GPU-Kontext + Backend-Auswahl
│   └── shaders/         # WGSL-Shader-Bibliothek
│       ├── field.wgsl   # secp256k1-Feldarithmetik
│       └── curve.wgsl   # Jacobi-Punktoperationen
└── shaders/
    └── kangaroo_affine.wgsl  # Haupt-Kangaroo-Compute-Shader

Anforderungen

• Rust 1.70+
• Vulkan-fähige GPU (AMD, NVIDIA, Intel) oder Metal (macOS)
• Unter Linux mit AMD RADV ist Mesa 25.x oder neuer erforderlich (ältere Mesa-Versionen können bei dynamischem WGSL-Indexing in Shader-Schleifen abstürzen)
• GPU-Treiber installiert

Lizenz

MIT-Lizenz - siehe LICENSE für Details.

Verwandte Projekte

• JeanLucPons/Kangaroo - CUDA-Implementierung (nur NVIDIA)
• RCKangaroo - CUDA-Implementierung (nur NVIDIA)
• boha - Krypto-Puzzles und Bounties-Datenbibliothek