oritwoen/kangarooАлгоритм Полларда «Кенгуру» с ускорением на GPU для решения задачи дискретного логарифмирования на эллиптической кривой (ECDLP) на secp256k1, поддерживающий бэкенды Vulkan, Metal и DX12.
Ускоренный на GPU алгоритм Полларда «Кенгуру» для решения задачи дискретного логарифмирования эллиптической кривой (ECDLP) на secp256k1.
--benchmark для проверки оборудования, --save-benchmarks для записи результатовБольшинство существующих реализаций Кенгуру (JeanLucPons/Kangaroo, RCKangaroo и др.) поддерживают только GPU NVIDIA через CUDA. Эта реализация использует WebGPU/wgpu, что обеспечивает кроссплатформенные GPU-вычисления через Vulkan, Metal и DX12.
paru -S kangaroo
cargo install kangaroo
git clone https://github.com/oritwoen/kangaroo
cd kangaroo
cargo build --release
cargo build --release --features boha
kangaroo --pubkey <PUBKEY> --start <START> --range <BITS>
| Аргумент | По умолчанию | Описание |
|---|---|---|
-t, --target | - | Цель поставщика данных (например, boha:b1000/135) |
-p, --pubkey | - | Целевой открытый ключ (сжатый hex, 33 байта) |
-s, --start | 0 | Начало диапазона поиска (hex, без префикса 0x) |
-r, --range | 32 | Размер диапазона поиска в битах (ключ в [start, start + 2^range - 1]) |
-d, --dp-bits | auto | Биты отличительных точек |
-k, --kangaroos | auto | Количество параллельных кенгуру |
--gpu | 0 | Индекс GPU-устройства |
--backend | auto | Бэкенд GPU: auto, vulkan, dx12, metal, gl |
-o, --output | - | Выходной файл для результата |
-q, --quiet | false | Минимальный вывод, только найденный ключ |
--max-ops | 0 | Максимальное количество операций (0 = без ограничений) |
--cpu | false | Использовать CPU-решатель вместо GPU |
--json | false | Вывод результатов бенчмарка в формате JSON |
--benchmark | false | Запустить набор бенчмарков |
--save-benchmarks | false | Сохранить результаты бенчмарка в BENCHMARKS.md при использовании --benchmark |
--mod-step | 1 | Модульный шаг M (hex): искать только k ≡ R (mod M) |
--mod-start | 0 | Модульный остаток R (hex): 0 ≤ R < M |
--list-providers | false | Вывести список доступных головоломок от провайдеров |
Требуется либо --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 — диапазон поиска. Работает следующим образом:
Оптимизация отличительных точек (DP): вместо хранения всех посещённых точек мы сохраняем только те, чья x-координата имеет определённое количество ведущих нулевых битов. Это значительно снижает использование памяти, позволяя при этом обнаруживать коллизии.
Ожидаемое количество операций: ~2^(range_bits/2)
Запустите kangaroo --benchmark, чтобы проверить своё оборудование без обращения к файлам. Используйте kangaroo --benchmark --save-benchmarks для обновления BENCHMARKS.md.
| Сценарий | Пример |
|---|---|
| Частично известный ключ | Головоломка даёт ~240 бит, нужно найти оставшиеся ~16 |
| Ключ в известном диапазоне | Известно, что ключ находится между X и Y |
| Проверка почти-решения | Есть кандидат, поиск ±N бит вокруг него |
НЕ применимо для:
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 предоставляет данные криптографических головоломок, включая Bitcoin Puzzle Transaction (b1000).
Сборка с поддержкой boha:
cargo build --release --features boha
Использование:
# Решить конкретную головоломку
kangaroo --target boha:b1000/66
# Список решаемых головоломок (нерешённые с известным открытым ключом)
kangaroo --list-providers
Провайдер проверяет переопределение диапазона — нельзя искать вне диапазона ключа головоломки.