Программы для вскрытия биткойн-головоломок с публичным ключом сравнили в тесте
Автор блога на Habr сравнил программы для вскрытия биткойн-головоломок, у которых публичный ключ уже раскрыт в блокчейне. Для таких задач работают алгоритмы с квадратично меньшей вычислительной сложностью, чем перебор по адресу. В тесте участвовали реализации метода кенгуру Полларда и метода Baby-Step Giant-Step (BSGS, встреча посередине) на центральных и графических процессорах.
Метод кенгуру Полларда моделирует две группы траекторий. Домашние кенгуру стартуют от известных координат, дикие - от неизвестного ключа. Обе группы прыгают по эллиптической кривой по детерминированным правилам: длина и направление каждого шага зависят от текущей точки. Когда пути пересекаются, дальше они движутся одинаково, и это позволяет вычислить ключ. Алгоритм фиксирует только особые точки, например координаты с заданным числом нулевых бит, поэтому не требует гигантских объёмов памяти.
BSGS работает иначе. Сначала строится таблица детских шагов, затем диапазон проверяется гигантскими шагами. Проблема в том, что таблица для больших головоломок должна быть колоссальной. Для головоломки номер 140 сохранить нужное число точек технически невозможно. Чем больше диапазон, тем меньшую долю таблицы удаётся удержать в памяти, и BSGS начинает проигрывать кенгуру Полларда в сотни тысяч и миллионы раз.
Программы BSGS при этом печатают впечатляющие скорости - тераключи и даже петаключи в секунду. Но сравнивать эти цифры с показателями кенгуру напрямую нельзя: алгоритмы выполняют разные математические операции. Кенгуру Полларда за один просмотр состояния статистически эквивалентен проверке диапазона порядка квадрата этого числа.
В тесте на центральном процессоре с диапазоном 2^60 эталоном выступил JLP Kangaroo. Закрытая утилита btcmole оказалась быстрее его в 88 парах из 100 при одинаковой скорости прыжков - около 285 миллионов ключей в секунду. Выигрыш даёт метод: путь кенгуру RCKangaroo с симметрией требует примерно 1,15 корня из ширины диапазона прыжков против 2 у классической схемы. Кенгуру на процессоре решает задачу вдвое-вчетверо быстрее лучшего BSGS, хотя BSGS печатает скорости на восемь порядков выше.
На графическом процессоре с диапазоном 2^66 эталоном был RCKangaroo v4.0. btcmole обошла его в 63 случаях из 100. Автор отмечает, что скорость, которую печатает программа, плохо предсказывает время до ключа. Например, theCollider печатает больше, чем RCKangaroo, а решает втрое медленнее. Решают реальное число прыжков, накладные расходы на особые точки и время запуска.
На современных картах RTX 4090, 5070 Ti и 5090 RCKangaroo v4.0 включает турбо-ядра на низкоуровневом ассемблере SASS. По данным автора RCKangaroo, на RTX 5090 скорость достигает 19 000 миллионов ключей в секунду. В btcmole для этих серий тоже есть ядра на SASS. На RTX 4090 программы идут почти вровень с разницей меньше 2 процентов, а на 5000-й серии btcmole раскрывает собственные улучшения и выходит вперёд.
Прорыв RCKangaroo держится на трёх решениях. Состояние стада кенгуру размещается в кэше L2, чтобы прыжки почти не обращались к видеопамяти. Самая дорогая операция - инверсия в поле - вынесена на отдельные блоки-инверторы. Весь горячий код написан на SASS вручную.
Из протестированных программ на видеокартах AMD запускаются только две: btcmole и oritwoen/kangaroo на Vulkan. Остальные написаны под CUDA. На старой R9 Fury btcmole показала 760-830 миллионов ключей в секунду и нашла ключ диапазона 2^48 за 5,3 секунды вместе с запуском. Вторая программа запустилась, но ключ 2^47 за 150 секунд не нашла, хотя сделала в 30 раз больше операций, чем требует алгоритм.
Код btcmole закрыт, но результаты указывают, что её автор взял часть идей RCKangaroo и дополнил их собственными улучшениями. Код RetiredCoder, создателя RCKangaroo, в исходном виде держит данные в памяти видеокарты и не предназначен для вскрытия сложных головоломок без внешней базы данных или работы в пуле. Реальные пулы дорабатывают эти ядра под свои распределённые архитектуры самостоятельно.
Читайте также
Quantus запустил торговлю через NEAR Intents и бросил вызов квантовой уязвимости биткоина
Glassnode: треть всех биткоинов лежит на уязвимых для квантового взлома адресах
Суд обязал Apple доплатить Masimo $184 млн процентов по патентному спору
Минцифры готовит ежегодные субсидии до 10 млрд рублей на проекты с искусственным интеллектом
Конференция Bitcoin Asia вернется в Гонконг в августе 2027 года