Кенгуру

Ускоренный на GPU алгоритм Полларда «Кенгуру» для решения задачи дискретного логарифмирования эллиптической кривой (ECDLP) на secp256k1.

Возможности

• 🖥️ Кроссплатформенный GPU — Vulkan (AMD, NVIDIA, Intel), Metal (Apple Silicon), DX12 (Windows) через wgpu
• 🦀 Чистый Rust + WGSL — без зависимости от CUDA, вычислительные шейдеры компилируются во время выполнения
• ⚡ Отличительные точки — эффективное обнаружение коллизий с автоматически подбираемыми битами DP
• 🔄 Карта отрицания — ускорение ~1.29× за счёт направленных переходов по чётности Y с защитой от циклов
• 🦘 Множественные стада кенгуру — tame, wild1, wild2 для повышения вероятности коллизии
• 🎯 Модульные ограничения — если k ≡ R (mod M), пространство поиска сокращается в M раз
• ⚙️ Автокалибровка — время отправки GPU и размер рабочей группы настраиваются при запуске
• 📊 Встроенные бенчмарки — --benchmark для проверки оборудования, --save-benchmarks для записи результатов
• 📦 Поставщики данных — подключаемые источники головоломок (интеграция boha для Bitcoin-головоломок)
• 💻 Запасной CPU — чисто CPU-решатель для тестирования и сравнения

Зачем этот проект?

Большинство существующих реализаций Кенгуру (JeanLucPons/Kangaroo, RCKangaroo и др.) поддерживают только GPU NVIDIA через CUDA. Эта реализация использует WebGPU/wgpu, что обеспечивает кроссплатформенные GPU-вычисления через Vulkan, Metal и DX12.

Установка

Arch Linux (AUR)

paru -S kangaroo

Cargo

cargo install kangaroo

Из исходников

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

С провайдером boha

cargo build --release --features boha

Использование

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

Аргументы

Требуется либо --target, либо --pubkey.

Примеры

Использование поставщика данных (boha):

# Решить головоломку, используя данные boha (авто: pubkey, start, range)
kangaroo --target boha:b1000/66

# Переопределить диапазон (искать меньший поддиапазон)
kangaroo --target boha:b1000/66 --range 60

# Список доступных головоломок
kangaroo --list-providers

Ручные параметры:

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

С модульным ограничением (k ≡ 37 mod 60):

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

Это сокращает пространство поиска примерно в 60 раз. Полезно, когда известна частичная структура ключа (например, ключ сгенерирован с предсказуемым шагом).

Как это работает

Алгоритм Полларда «Кенгуру» решает задачу дискретного логарифмирования за время O(√n), где n — диапазон поиска. Работает следующим образом:

1. Ручные кенгуру начинают с известной точки и совершают случайные прыжки
2. Дикие кенгуру начинают с целевого открытого ключа и совершают те же типы прыжков
3. Когда дикое и ручное кенгуру оказываются в одной точке (коллизия), мы можем вычислить закрытый ключ

Оптимизация отличительных точек (DP): вместо хранения всех посещённых точек мы сохраняем только те, чья x-координата имеет определённое количество ведущих нулевых битов. Это значительно снижает использование памяти, позволяя при этом обнаруживать коллизии.

Производительность

Ожидаемое количество операций: ~2^(range_bits/2)

Запустите kangaroo --benchmark, чтобы проверить своё оборудование без обращения к файлам. Используйте kangaroo --benchmark --save-benchmarks для обновления BENCHMARKS.md.

Сценарии использования

НЕ применимо для:

• Полный поиск 256-битного ключа (математически невозможно)
• Перебор BIP39 мнемоник (используйте атаку по словарю)
• Головоломки без частичной информации о ключе

Использование библиотеки

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,  // количество бит диапазона
        12,  // количество бит отличительных точек
        1024, // количество кенгуру
    )?;

    loop {
        if let Some(key) = solver.step()? {
            if verify_key(&key, &pubkey) {
                println!("Найден: {}", hex::encode(&key));
                break;
            }
        }
    }

    Ok(())
}

Поставщики данных

Kangaroo поддерживает внешние поставщики данных для источников головоломок. Поставщики предоставляют открытый ключ, диапазон ключа и другие метаданные головоломки.

boha (опциональная возможность)

boha предоставляет данные криптографических головоломок, включая Bitcoin Puzzle Transaction (b1000).

Сборка с поддержкой boha:

cargo build --release --features boha

Использование:

# Решить конкретную головоломку
kangaroo --target boha:b1000/66

# Список решаемых головоломок (нерешённые с известным открытым ключом)
kangaroo --list-providers

Провайдер проверяет переопределение диапазона — нельзя искать вне диапазона ключа головоломки.

Архитектура

src/
├── main.rs              # Входная точка CLI
├── lib.rs               # Входная точка библиотеки + Args + run()
├── solver.rs            # Координация GPU-решателя
├── cli.rs               # Утилиты CLI (трассировка, индикатор прогресса)
├── benchmark.rs         # Встроенный набор бенчмарков
├── modular.rs           # Преобразование модульных ограничений
├── math.rs              # 256-битная арифметика, генерация маски DP
├── convert.rs           # Преобразования Limb/byte для GPU↔CPU
├── provider/
│   ├── mod.rs           # Интерфейс системы провайдеров
│   └── boha.rs          # Провайдер boha (условная компиляция)
├── cpu/
│   ├── cpu_solver.rs    # Чистый CPU-решатель (тестирование/сравнение)
│   ├── dp_table.rs      # Обнаружение коллизий по отличительным точкам
│   └── init.rs          # Инициализация кенгуру + таблицы прыжков
├── crypto/
│   └── mod.rs           # Обёртки k256/secp256k1
├── gpu/
│   ├── pipeline.rs      # Настройка вычислительного конвейера
│   └── buffers.rs       # Управление GPU-буферами
├── gpu_crypto/
│   ├── context.rs       # Контекст GPU + выбор бэкенда
│   └── shaders/         # Библиотека шейдеров WGSL
│       ├── field.wgsl   # Арифметика поля secp256k1
│       └── curve.wgsl   # Операции с точками в координатах Якоби
└── shaders/
    └── kangaroo_affine.wgsl  # Основной вычислительный шейдер Кенгуру

Требования

• Rust 1.70+
• GPU с поддержкой Vulkan (AMD, NVIDIA, Intel) или Metal (macOS)
• На Linux с AMD RADV требуется Mesa 25.x или новее (более старые версии Mesa могут падать при динамической индексации WGSL в шейдерных циклах)
• Установленные драйверы GPU

Лицензия

Лицензия MIT — подробнее см. в LICENSE.

Связанные проекты

• JeanLucPons/Kangaroo — CUDA-реализация (только NVIDIA)
• RCKangaroo — CUDA-реализация (только NVIDIA)
• boha — Библиотека данных криптографических головоломок и наград