В прошлой статье («Тестируем программы для вскрытия биткойн-головоломок») я сравнивал программы, которые ищут ключ по адресу — перебором. Но у части головоломок (номера, кратные пяти: 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. Образно его можно представить как поиск точки на огромном круге, который символизирует диапазон поиска:

1. Определённый сектор этого круга («ловушка») предварительно рассчитывается малыми шагами и сохраняется в памяти.

2. Тестируемая точка начинает двигаться вперед большими фиксированными прыжками.

3. Как только прыжок попадает в заранее сохраненный сектор-ловушку (в котором все точки известны), задача считается решенной.

Ограничение по памяти:

Для решения задачи дискретного логарифмирования на эллиптической кривой в рамках больших биткойн-головоломок ловушка должна быть колоссального размера — на практике под неё требуется объём памяти порядка . Для реальных диапазонов такого объема оперативной памяти просто не существует.

Существуют оптимизации (например, использование фильтров Блума для компактного удержания точек-кандидатов в 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.

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 потоков, ни одного сбоя.

Эталон — JLP Kangaroo. btcmole быстрее его в 88 парах из 100 при одинаковой скорости прыжков (283 и 288 Mkeys/s): выигрыш даёт метод — путь кенгуру RCKangaroo (симметрия, K ≈ 1.15 против ≈ 2 у классической схемы), а не арифметика. Кенгуру на процессоре вдвое-вчетверо быстрее лучшего BSGS, хотя BSGS печатает скорости на восемь порядков выше.

GPU: 2^66

100 ключей, ни одного сбоя. Эталон — RCKangaroo v4.0.

Парное сравнение на тех же ключах: 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 с и программа всё время считала с полной скоростью.

Время до ключа, ключи 2^70, DP 14, ни одного сбоя:

Код 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.

«Петаключи в секунду» у 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 точек.

Кто не вошёл и почему

Выводы

Самая быстрая программа с открытым кодом — 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 ООО «МТ ФИНАНС»