В прошлой статье («Тестируем программы для вскрытия биткойн-головоломок») я сравнивал программы, которые ищут ключ по адресу — перебором. Но у части головоломок (номера, кратные пяти: 135, 140, 145, …) публичный ключ уже раскрыт в блокчейне, и для них работают совсем другие алгоритмы — с квадратично меньшей работой:
Кенгуру Полларда (Pollard’s kangaroo): два «стада» кенгуру прыгают по кривой псевдослучайными прыжками; «различимые точки» (DP) складываются в базу, совпадение точек домашнего и дикого кенгуру даёт ключ. Работа ≈ K·√N прыжков, где N — ширина диапазона, K ≈ 1.15 у лучших реализаций.
Baby-Step Giant-Step (BSGS): таблица «детских шагов» m точек строится заранее, затем «гигантскими шагами» по m ключей проверяется весь диапазон. Работа ≈ N/m шагов, но таблица требует памяти и большого времени на построение, поэтому мы включаем его в замер.
Алгоритмы решения биткойн-головоломок: Кенгуру Полларда vs Baby-step Giant-step
Принцип работы Baby-step Giant-step (встреча посередине)
Алгоритм BSGS часто называют методом встречи посередине или алгоритмом класса meet-in-the-middle. Образно его можно представить как поиск точки на огромном круге, который символизирует диапазон поиска:
Определённый сектор этого круга («ловушка») предварительно рассчитывается малыми шагами и сохраняется в памяти.
Тестируемая точка начинает двигаться вперед большими фиксированными прыжками.
Как только прыжок попадает в заранее сохраненный сектор-ловушку (в котором все точки известны), задача считается решенной.
Ограничение по памяти:
Для решения задачи дискретного логарифмирования на эллиптической кривой в рамках больших биткойн-головоломок ловушка должна быть колоссального размера — на практике под неё требуется объём памяти порядка 
. Для реальных диапазонов такого объема оперативной памяти просто не существует.
Существуют оптимизации (например, использование фильтров Блума для компактного удержания точек-кандидатов в RAM с последующей проверкой на HDD). Однако даже подобные методы не спасают: сохранить, к примеру, 
точек-ловушек для головоломки №140 технически невозможно. Чем больше диапазон, тем меньшую долю сектора мы способны удержать в памяти, из-за чего количество необходимых шагов лавинообразно растёт, а BSGS начинает проигрывать алгоритму Полларда в сотни тысяч и миллионы раз.
Алгоритм Кенгуру Полларда
Об алгоритме Полларда я уже кратко рассказывал в одной из прошлых публикаций — «Головоломка на 1000 BTC».
Он устроен иначе. По легенде, Джон Поллард вдохновился австралийским методом отлова кенгуру: к диким особям выпускают прирученного «домашнего» кенгуру, который возвращается на ферму, приводя с собой диких.
В алгоритме используются две группы траекторий:
«Домашние» кенгуру начинают путь от известных координат.
«Дикие» кенгуру стартуют от неизвестного ключа.
Обе группы совершают детерминированные прыжки: длина и направление каждого следующего шага жёстко привязаны к текущей точке. Как только пути дикого и домашнего кенгуру пересекаются, благодаря единому правилу перехода они начинают двигаться по абсолютно одинаковому маршруту.
Выделенные точки или Distinguished Points:
Чтобы не хранить каждый шаг, алгоритм фиксирует только так называемые «особые точки» — например, координаты, у которых заданное количество начальных или конечных бит равно нулю (примерно каждый миллиардный шаг). Это снимает жесткую зависимость от гигантских объемов RAM, присущую BSGS.
Нюансы метрик: почему нельзя напрямую сравнивать скорости
При запуске программ на базе BSGS утилиты могут демонстрировать колоссальные показатели скорости — терахеши или даже петахеши в секунду, что на порядки превосходит цифры реализаций Кенгуру.
Однако сравнивать эти значения «в лоб» некорректно:
Скорости отражают совершенно разные математические операции.
Алгоритм Кенгуру обладает квадратичной эффективностью: просмотр
состояний статистически эквивалентен проверке диапазона порядка 
.
Поэтому, несмотря на визуально скромные цифры хешрейта, алгоритм Полларда на реальных дистанциях оказывается несравнимо эффективнее BSGS.
Программные решения и GPU-оптимизации
Эталонные по производительности решения для алгоритма Кенгуру принадлежат анонимусу с ником RetiredCoder (подробнее о нём — в статье «Биткойн-головоломка 135 вскрыта! Who is RetiredCoder?», его ветка на BitcoinTalk).
Его турбо-ядра для GPU используют низкоуровневый ассемблер SASS (в обход промежуточного PTX). Это позволило совершить технологический скачок и в разы поднять производительность на видеокартах поколений RTX 4090 и RTX 5090. Сегодня эти наработки лежат в основе практически всех передовых решений.
Прорыв RCKangaroo держится на трёх решениях. Состояние стада кенгуру размещено так, чтобы помещаться в кэш L2 — на картах 4000-й и 5000-й серий он достаточно велик, и прыжки почти не ходят в видеопамять. Самая дорогая операция — инверсия в поле — вынесена на отдельные блоки-инверторы на своих SM: остальные SM только прыгают и отдают им накопленные значения. И, наконец, весь горячий код написан на SASS вручную.
Практический нюанс:
Код RetiredCoder создавался в первую очередь для демонстрации рекордных скоростей. В исходном виде он держит данные непосредственно в памяти видеокарты, поэтому «из коробки» не предназначен для вскрытия сложных головоломок (для этого требуется подключение внешней БД или работа в пуле). Большинство открытых решений представляют собой скорее демонстрацию state-of-the-art скорости, тогда как реальные пулы дорабатывают и модифицируют эти ядра под свои распределённые архитектуры самостоятельно.
Какие программы участвуют
Только Linux. Всё собрано из исходников, кроме btcmole (релизный бинарник) и закрытых библиотек iceland2k14.
Программа | Алгоритм | Железо | Версия (коммит) |
|---|---|---|---|
RCKangaroo v4.0 | Kangaroo | CUDA | 618473a + патч загрузки кубина |
RCKangaroo v3.1 | Kangaroo | CUDA | f302c4c |
PSCKangaroo (форк RC) | Kangaroo | CUDA | 021e997 |
Kangaroo | CUDA | 4b6aa34 | |
Kangaroo | CPU и CUDA | 37576c8 | |
keyhunt (режим bsgs) | BSGS | CPU | 2134a20 |
BSGS | CPU | 5bf3bb3 | |
btcmole | Kangaroo | CPU и CUDA | 0.8.0 (релизный бинарник) |
btcmole — программа с закрытым кодом. Для головоломок с публичным ключом это не помеха: известный публичный ключ можно перед поиском сместить на тайное значение (Q′ = Q + t·G и диапазон, сдвинутый на t), и программа ищет ключ, по которому нельзя понять, какую головоломку она решает. Поэтому btcmole включён в обзор наравне с открытыми программами.
Кого не удалось включить и почему — в конце статьи.
Методика
Та же, что в прошлый раз: замеряется только время от запуска процесса до момента, когда в поток вывода попал искомый приватный ключ. Никаких внутренних метрик в зачёт. Для каждого блока генерируется 100 случайных ключей (seed 42), все программы блока решают одни и те же ключи; раунд — один ключ для каждой программы, порядок программ сдвигается на каждом раунде; перед замером — один разогревочный ключ, в зачёт не идёт.
Отличия от прошлого замера:
Цель — публичный ключ (раньше был адрес).
Диапазоны больше, потому что алгоритмы квадратично быстрее: CPU — 2^60, GPU — 2^66.
Таблицы BSGS. Время построения таблицы детских шагов входит в результат. Если программа умеет сохранять таблицу (keyhunt
-S), таблица строится один раз, а время её построения прибавляется к каждому запуску — результат тот же, что при построении в каждом запуске, а стенд не тратит часы. Таблица — не больше 32 ГБ RAM и не дольше 10 минут построения; размер подобран пристрелкой под минимум суммы «построение + средний поиск» на 2^60.DP у кенгуру. В GPU-блоке у всех одна битность DP = 14 (минимум, который позволяет RCKangaroo). В CPU-блоке — автовыбор программы или рекомендация автора.
Ресурсы. CPU-программам — 112 потоков (ядра 16–127); GPU-программы привязаны к ядрам 0–15. Блоки шли одновременно, не отнимая процессор друг у друга. btcmole на CPU прогнан позже отдельно, на тех же ключах и ядрах.
Зависания. Таймаут 180 с на ключ и «проверяльщик запуска»: программа, молчащая 60 с, останавливается.
Скорость по данным программы — медиана по запускам последней скорости, которую программа напечатала сама. Это справочная колонка: программы считают «ключи в секунду» по-разному.
Репозиторий
Скрипт pubkey_bench.py в репозитории бенчмарка (рядом с bench.py из прошлой статьи): --prepare клонирует и собирает все программы, --device cpu|cuda прогоняет блок, --from-log собирает отчёт из логов. Патчи сборки — в patches/.
Стенд
CPU: AMD EPYC 7C13 (64 ядра / 128 потоков, 2.45 GHz base)
GPU: NVIDIA CMP 90HX (Ampere, sm_86, 50 SM)
ОС: Linux (Calculate Linux), CUDA 12.9
CPU: 2^60
100 ключей, 112 потоков, ни одного сбоя.
# | Программа | Алгоритм | OK / FAIL | Среднее, с | Медиана, с | × эталон | Скорость по данным программы |
|---|---|---|---|---|---|---|---|
1 | btcmole kang (CPU) | Kangaroo | 100 / 0 | 5.04 | 4.66 | 2.16 | 283 Mkeys/s |
2 | JLP Kangaroo (CPU) | Kangaroo | 100 / 0 | 10.89 | 9.62 | 1.00 | 288 Mkeys/s |
3 | keyhunt | BSGS | 100 / 0 | 24.61 | 24.36 | 0.44 | 103 Pkeys/s |
4 | JLP BSGS | BSGS | 100 / 0 | 50.51 | 51.53 | 0.22 | 248 MKey/s гигантских шагов |
Эталон — JLP Kangaroo. btcmole быстрее его в 88 парах из 100 при одинаковой скорости прыжков (283 и 288 Mkeys/s): выигрыш даёт метод — путь кенгуру RCKangaroo (симметрия, K ≈ 1.15 против ≈ 2 у классической схемы), а не арифметика. Кенгуру на процессоре вдвое-вчетверо быстрее лучшего BSGS, хотя BSGS печатает скорости на восемь порядков выше.
GPU: 2^66
100 ключей, ни одного сбоя. Эталон — RCKangaroo v4.0.
# | Программа | OK / FAIL | Среднее, с | Медиана, с | × эталон | Скорость по данным программы, Mkeys/s |
|---|---|---|---|---|---|---|
1 | btcmole 0.8.8 (режим kang) | 100 / 0 | 7.96 | 7.72 | 1.13 | 2 896 |
2 | RCKangaroo v4.0 | 100 / 0 | 9.00 | 8.80 | 1.00 | 1 787 |
3 | RCKangaroo v3.1 | 100 / 0 | 11.68 | 11.15 | 0.77 | 1 890 |
4 | PSCKangaroo | 100 / 0 | 16.01 | 15.45 | 0.56 | 1 910 |
5 | theCollider (CUDA) | 100 / 0 | 27.90 | 27.12 | 0.32 | ≈ 2 185 (по итогу работы) |
6 | JLP Kangaroo (GPU) | 100 / 0 | 31.14 | 30.52 | 0.29 | 1 734 |
Парное сравнение на тех же ключах: btcmole быстрее RCKangaroo v4.0 в 63 случаях из 100.
Заметно, что «скорость по данным программы» плохо предсказывает время до ключа: theCollider печатает больше, чем RCKangaroo, а решает втрое медленнее; RCKangaroo v3.1 печатает больше, чем v4.0, а решает на 30% дольше. Решают K (сколько прыжков реально нужно), накладные расходы на DP и время запуска.
Современные карты: RTX 4090, 5070 Ti, 5090
На картах 4000-й и 5000-й серий RCKangaroo v4.0 включает турбо-ядра на SASS. По данным автора RCKangaroo, на RTX 5090 скорость около 19 000 Mkeys/s. В btcmole для этих серий тоже есть ядра на SASS.
Карты арендованные, поэтому главное здесь — скорости, которые печатают сами программы: в рамках одного алгоритма их можно сравнивать напрямую. Два чередующихся прогона каждой программы по 40 с на диапазоне 2^100, DP 14 у обеих. Диапазон выбран так, чтобы ключ заведомо не нашёлся за эти 40 с и программа всё время считала с полной скоростью.
Карта | btcmole, Mkeys/s | RCKangaroo v4.0, Mkeys/s | btcmole / RC |
|---|---|---|---|
RTX 5090 (лимит 600 Вт) | 20 168 / 20 155 | 18 986 / 18 941 | 1.064 |
RTX 4090 (лимит 480 Вт) | 14 697 / 14 711 | 14 443 / 14 443 | 1.018 |
RTX 5070 Ti (зажата до 250 Вт) | 8 621 / 8 630 | 7 692 / 7 631 | 1.126 |
Время до ключа, ключи 2^70, DP 14, ни одного сбоя:
Карта | Ключей | btcmole, среднее / медиана, с | RCKangaroo v4.0, среднее / медиана, с | × RC | Побед btcmole |
|---|---|---|---|---|---|
RTX 5090 | 100 | 4.39 / 4.33 | 4.70 / 4.49 | 1.07 | 60 из 100 |
RTX 5070 Ti | 100 | 6.57 / 6.44 | 7.00 / 6.95 | 1.07 | 56 из 100 |
Код btcmole закрыт, но, судя по результатам, его автор взял на вооружение часть идей RCKangaroo и дополнил их собственными улучшениями — это и позволило обойти RCKangaroo по скорости. На это указывает и RTX 4090: там программы идут почти вровень (разница меньше 2%), как будто на этой серии btcmole повторяет схему RCKangaroo, а свои улучшения раскрывает только на 5000-й серии.
Карты AMD
Из протестированных программ на AMD запускаются только две: btcmole и oritwoen/kangaroo (Vulkan) — остальные написаны под CUDA. Карта AMD у нас одна — R9 Fury (GCN3, 2015 год); арендовать AMD не удалось: площадки предлагают почти исключительно NVIDIA.
btcmole — 760–830 Mkeys/s (оседает по мере нагрева карты), ключ 2^48 — за 5.3 с вместе с запуском.
oritwoen/kangaroo — запускается, ~7.5 млн операций/с, но ключ 2^47 за 150 с не нашёл, хотя сделал в ~30 раз больше операций, чем требует алгоритм.
BSGS между собой
Ключи CPU-блока 2^60.
Программа | Железо | Таблица | Время таблицы, с | OK / FAIL | Среднее, с | Медиана, с | Заявленная скорость |
|---|---|---|---|---|---|---|---|
keyhunt | CPU |
| 14.2 (один раз) | 100 / 0 | 24.61 | 24.36 | 103 PKeys/s |
JLP BSGS | CPU | 2^27 детских шагов | в каждом запуске | 100 / 0 | 50.51 | 51.53 | 248 MKey/s ≈ 33 PKeys/s эффективно |
GPU | 2^24 (0.86 ГБ) | 117 (один раз) + ≈ 90 загрузка в каждом запуске | — | ≈ 95 + 90 (оценка) | — | 3 PKeys/s | |
bsgs_scan | GPU | 2^26 | в каждом запуске | — | ≈ 4 ч (оценка) | — | 39 TKeys/s |
iceland2k14 bsgs v6 | CPU | 10⁸ элементов | 135.6 | — | ≈ 4.4 ч (оценка) | — | 36.5 TKeys/s |
«Петаключи в секунду» у BSGS — это ширина диапазона, вычеркнутая одной проверкой гигантского шага, умноженная на темп шагов. Для сравнения: те же 2^60 кенгуру JLP на том же процессоре решает в среднем за 11 с при «скромных» 288 Mkeys/s.
keyhunt-GPU — форк keyhunt, который выполняет BSGS на видеокарте. На CMP 90HX с таблицей из 2^24 детских шагов (0.86 ГБ) он правильно нашёл контрольный ключ 2^47 и показал 3 PKeys/s — около 180 млн гигантских шагов в секунду. Для ключа 2^60 это в среднем ≈ 95 с поиска, плюс ≈ 90 с на загрузку и проверку таблицы при каждом запуске (построение таблицы — ещё 117 с, один раз). Полного прогона на 100 ключах не было: это оценка по одному длинному прогону. keyhunt на процессоре с теми же ключами быстрее в несколько раз.
Почему эффективный BSGS на GPU сделать трудно.
Таблица не помещается туда, где поиск быстрый. Быстрая память видеокарты — shared memory (LDS): обычно это 48–99 КБ на мультипроцессор, то есть несколько тысяч точек. Фактически размер сектора детских шагов, по которому можно искать без задержек, ограничен именно ею. Всё, что больше, уходит в кэш L2 (72–96 МБ даже у RTX 4090/5090) или в видеопамять, где каждое обращение стоит сотни тактов.
Обращения случайные. На каждом гигантском шаге каждый поток ищет свою точку по таблице — по хешу, в случайном месте. Соседние потоки варпа идут в разные места памяти, и видеокарта теряет своё главное преимущество — слитные чтения. У keyhunt-GPU фильтр Блума делает семь таких обращений на шаг.
Поиск расходится внутри варпа. Проверка — это ветвления: фильтр ответил «нет» — шаг закончен, «возможно» — идём точно сравнивать по корзине, а длина корзины у каждого потока своя. Варп исполняет 32 потока одной командой, поэтому ждёт самый медленный из них: пока один поток перебирает корзину, остальные простаивают.
Таблица ограничена видеопамятью. Даже в видеопамяти помещается 10–24 ГБ на игровых картах, тогда как у процессора под таблицу сотни гигабайт RAM. А размер таблицы — это и есть ширина, которую вычёркивает один гигантский шаг: меньше таблица — больше шагов.
Таблицу надо построить и загрузить. Это время входит в решение каждого ключа, если таблицу нельзя держать в памяти между запусками; у keyhunt-GPU загрузка с проверкой занимает полторы минуты.
И главное — BSGS проигрывает кенгуру по самой работе. BSGS делает N/m шагов, кенгуру — порядка √N прыжков. С ростом диапазона никакая оптимизация таблицы этот разрыв не закроет: для головоломки №140 нужна таблица порядка 2^70 точек.
Кто не вошёл и почему
Программа | Причина | Данные |
|---|---|---|
Mark1 (Dookoo2) | на стенде не нашёл ключ даже на примере из своего README (60 бит) | README: 60 бит — 4.1 с, 126.5 MH/s; 80 бит — 38 мин |
RetiredCoder Kang-1 / Kang-2 | исследовательские программы к статьям автора (Windows, MFC): каждый поток решает свой ключ, полная инверсия на каждый прыжок — годятся только для исследований | консольный порт для Linux, 48 бит, 112 ключей на 112 потоках: Kang-1 SOTA+ — K = 1.046, ≈ 305 тыс. прыжков/с на поток; Kang-2 — K = 1.196, ≈ 320 тыс. прыжков/с на поток. Автор: SOTA+ K ≈ 1.02 / 0.99 / 1.05 в зависимости от цены второй точки |
theCollider и oritwoen/kangaroo, CPU-режим | запасной бэкенд: ~357 тыс. ключей/с, 2^60 за 3 мин не решён | — |
oritwoen/kangaroo, Vulkan | ~10 млн операций/с на CMP 90HX, 2^66 за 120 с не решён | — |
bsgs_scan (GPU) | ≈ 39 TKeys/s → в среднем ≈ 4 ч на ключ 2^60 | — |
iceland2k14 bsgs v6 | поиск в одном процессе, 36.5 TKeys/s на таблице 10⁸ → ≈ 4.4 ч на ключ 2^60; таблица под заявленные 1.2 PKeys/s строится больше часа | README: 15 PetaKeys за ~11–12 с |
KeyHunt-Cuda (форк keyhunt от Qalander) | BSGS не умеет — по публичному ключу только перебор ( | — |
iceland2k14 bsgs v7 GPU | закрытая библиотека под CUDA 11 без кода для sm_86: «named symbol not found» | — |
Etayson BSGS-cuda, Etarkangaroo, fraction-bsgs | только Windows | Etarkangaroo: RTX 3070 — 1535 Mkey/s |
Выводы
Самая быстрая программа с открытым кодом — RCKangaroo (GPU), с закрытым — btcmole (GPU и CPU).
Среди BSGS-программ лучшая — keyhunt (CPU и GPU): на процессоре он решает ключ 2^60 за 25 с, его форк keyhunt-GPU выполняет BSGS на видеокарте, но упирается в объём видеопамяти под таблицу, поэтому медленнее CPU-версии.
В погоне за скоростью RetiredCoder вышел на новый уровень безумства — написал ядра прямо на SASS, машинном языке видеокарт NVIDIA, в обход компилятора. И забрал головоломку №135 («Биткойн-головоломка 135 вскрыта! Who is RetiredCoder?»).
Соревнование скоростей сегодня — способ показать пределы современных технологий и престиж. Хотя кто знает — может, появятся новые головоломки. В одиночку малореально взломать даже головоломку №140, если у тебя нет доступа к сотням карт или ты не в пуле.
© 2026 ООО «МТ ФИНАНС»
