Разбор Bitcoin Puzzle: почему подбор приватного ключа практически невозможен

Введение

В 2015 году в интернете появилась Bitcoin-головоломка – серия Bitcoin-адресов с реальными деньгами. Изначально общий призовой фонд составлял 32 BTC и со временем вырос до 1000 BTC. Головоломка состоит из 160 Bitcoin-адресов, на каждом из которых лежит определенная сумма. Доступ к средствам на каждом адресе возможен только при знании соответствующего приватного ключа.

Приватный ключ – это секретное число из огромного диапазона возможных значений, которое позволяет подписывать транзакции и распоряжаться биткоинами на конкретном адресе.

Для каждого адреса головоломки приватный ключ неизвестен, однако, он гарантированно находится в ограниченном числовом диапазоне. Теоретически это означает, что ключ можно найти, последовательно перебирая все возможные значения из этого диапазона и проверяя их. Тот, кто первым найдет правильный приватный ключ, получит биткоины, находящиеся на соответствующем адресе. Сложность заключается в том, что с каждым следующим адресом диапазон возможных значений приватного ключа увеличивается вдвое. На ранних этапах адреса удавалось опустошать довольно быстро, но по мере роста диапазона количество вариантов растет настолько быстро, что поиск ключа становится вычислительно невозможным даже при использовании современного оборудования. Создатель головоломки остался анонимен, однако в криптосообществе ходят слухи, что это мог быть Сатоши Накамото – основатель Bitcoin, который таким образом хотел на практике продемонстрировать криптографическую устойчивость и безопасность Bitcoin.

Для кого статья?

Данная статья предназначена для всех читателей, интересующихся устройством Bitcoin и криптографии в целом. Она будет полезна тем, кто слышал о Bitcoin-головоломке, но не до конца понимает, как она работает, а также любителям, энтузиастам и всем, кто хочет разобраться, почему подбор приватного ключа в Bitcoin является практически невозможной задачей. Приятного прочтения!

1. Знакомство с Bitcoin Puzzle

1.1 Погружаемся в историю Bitcoin-головоломки

2015 – Появление головоломки

• В январе 2015 года в блокчейне Bitcoin обнаруживают серию необычных транзакций: средства распределяются по 256 новым адресам.
• На каждом адресе лежит фиксированная сумма BTC, а сами адреса образуют строгую последовательность.
• Позже стало ясно, что каждый адрес соответствует приватному ключу из конкретного диапазона, причем каждый следующий диапазон в два раза шире предыдущего.
• Начальный призовой фонд составлял около 32 BTC.
• Первые десятки адресов (с малыми диапазонами ключей) были решены сравнительно быстро, что подтвердило: это не случайность, а намеренно созданная криптографическая головоломка.

2016 - 2017 – Рост интереса и корректировка структуры

• Головоломка активно обсуждается на форумах.
• Энтузиасты начинают писать программы для перебора ключей, использовать GPU и распределенные вычисления.
• Выясняется, что изначальная версия с 256 адресами была избыточной.
• В 2017 году средства с адресов 161–256 перераспределяются: автор фактически оставляет 160 основных головоломок, увеличив награды на более ранних уровнях.

2018 – Замедление прогресса

• Становится очевидно, что дальнейший рост сложности не компенсируется ни оптимизациями кода, ни ростом вычислительных мощностей.
• Сообщество начинает активно обсуждать, почему задача упирается в фундаментальные ограничения.

2019 – Новые направления в решении головоломки

• С адресов, чей номер кратен пяти отправляются микротранзакции по 1000 сатоши.
• Эти транзакции раскрывают публичные ключи соответствующих адресов.
• Предполагаемая цель: проверить, влияет ли наличие публичного ключа на поиск приватного ключа.

2020 - 2022 – Стагнация

• Новые уровни головоломки практически не решаются.
• Большинство активных участников сходятся во мнении, что дальнейший прогресс возможен только при:
• - принципиально новых алгоритмах,
• - существенном скачке в вычислительных технологиях.

2023 – Увеличение наград

• В апреле 2023 года награды за нерешенные головоломки увеличиваются в 10 раз.
• Общий призовой фонд возрастает почти до 1000 BTC.
• Даже относительно «ранние» нерешенные уровни начинают содержать несколько BTC на одном адресе.
• Это вновь привлекает внимание к головоломке, но не приводит к заметному прогрессу в ее решении.

2024 - настоящее время

• Решено 82 из 160 головоломок.
• Головоломки с большими диапазонами (например, начиная примерно с №71 и выше) остаются нерешенными.
• Рост сложности происходит экспоненциально, в то время как рост вычислительных мощностей – линейно

1.2 Идея головоломки

Главная идея Bitcoin Puzzle – наглядно показать рост сложности при поиске приватного ключа и продемонстрировать, как устроена криптографическая защита Bitcoin на практике. Адреса в головоломке выстроены по уровням: каждый следующий уровень соответствует все более широкому диапазону возможных приватных ключей, из‑за чего сложность растет экспоненциально. Важная особенность головоломки заключается в том, что для каждого пятого адреса известен публичный ключ.

Публичный ключ – это ключ, который вычисляется из секретного ключа с помощью эллиптического умножения кривых, которое является необратимым (об этом подробнее позже).

В обычных адресах публичный ключ скрыт до первой траты средств, но из-за ранее упомянутых "микротранзакций" эти ключи стали известны для каждого пятого адреса головоломки. Это принципиально меняет постановку задачи: вместо обычного поиска ключа перебором участник получает прямую задачу ECDLP – восстановления приватного ключа по публичному ключу на кривой secp256k1, что значительно упрощает головоломку. Таким образом, головоломка одновременно демонстрирует защищенность сразу двух аспектов криптографической стойкости:

• для обычных уровней – сложность обычного перебора приватных ключей в диапазоне.
• для уровней, кратных 5 – чистую криптографическую стойкость.

Первые уровни можно решить сравнительно быстро, но уже на средних уровнях требуются специализированные алгоритмы и серьезные вычислительные ресурсы. По мере приближения к пределу адресного пространства Bitcoin (160 бит информации - адресу под номером 160) задачи становятся практически нерешаемыми. Именно этот постепенный переход от решаемого к невозможному и составляет суть Bitcoin Puzzle.

1.3 Почему это не взлом Bitcoin

Важно понимать, что решение Bitcoin-головоломки не является взломом сети Bitcoin. В ходе решения не происходит атаки на блокчейн, майнеров или механизм консенсуса. Никто не изменяет правила сети, не подделывает транзакции и не вмешивается в работу узлов. Все действия выполняются строго в рамках протокола Bitcoin. Речь идет исключительно о поиске конкретного приватного ключа к заранее известному адресу. Если ключ найден, средства переводятся легитимной транзакцией, корректно подписанной этим ключом. С точки зрения сети Bitcoin это ничем не отличается от обычного использования кошелька. Головоломка лишь использует фундаментальное свойство системы: тот, кто знает приватный ключ, и есть владелец средств (если не учитывать морально-правовые нормы, а лишь правила консенсуса Bitcoin).

2. Как из приватного ключа получается Bitcoin-адрес

Этот раздел важен для понимания всей Bitcoin-головоломки. Необходимо понять, что именно пытаются найти участники, и какой путь проходит приватный ключ (обычное число) до того как стать привычным BTC-адресом.

2.1. Приватный ключ – просто большое число

Приватный ключ k – это одно целое число в диапазоне $1 \le k < n$где n – порядок эллиптической кривой secp256k1. Размер этого диапазона ≈ 2^{256}.

Приватный ключ обладает рядом свойств:

• любой ключ в допустимом диапазоне валиден и ему соответствует уникальный адрес Bitcoin кошелька,
• позволяет совершать транзакции в сети Bitcoin,
• система не хранит список существующих ключей.

2.2. Получение публичного ключа из приватного

Чтобы понять, как из приватного ключа получается публичный, нужно сначала разобраться, в каком математическом пространстве вообще происходит эта операция.

Все вычисления выполняются не над вещественными числами, а в конечном поле по модулю большого простого числа. Это означает, что:

• количество возможных точек конечно,
• все операции точны, без округлений,
• каждая операция имеет однозначный результат.

Именно в таком пространстве можно определить специальные операции над точками – сложение и умножение на число – которые и используются в криптографии.

Связь между приватным и публичным ключом в Bitcoin описывается одной формулой: $Q = k \cdot G$где:

• Q – публичный ключ,
• k – приватный ключ (секретное число),
• G – базовая точка эллиптической кривой secp256k1.

На первый взгляд эта запись может выглядеть как обычное умножение, но это принципиально не так.

Что такое точка G? Точка G – это фиксированная точка, заранее заданная в параметрах кривой secp256k1. Важно:

• она одна и та же для всех пользователей сети Bitcoin,
• она не выбирается случайно,
• ее координаты жестко прописаны в стандарте.

Можно провести аналогию: G – это «точка отсчета», от которой строятся все публичные ключи в системе.

Что на самом деле означает умножение $k \cdot G?$

Знак «×» здесь не означает обычное умножение чисел. В эллиптической криптографии:

• умножение точки на число означает многократное сложение точки самой с собой,
• операция сложения точек строго определена правилами кривой.

При этом:

• результат всегда снова является точкой на кривой,
• одно и то же k всегда дает один и тот же Q,
• операция умножения необратима (это очень важное свойство умножения точек на кривой).

Когда говорится, что публичный ключ получается «сложением точек», это не геометрия в привычном смысле и не сложение координат. Это специальная операция, искусственно определенная правилами кривой. Если упростить, операция сложения точек устроена так:

1. Берутся две точки на кривой: T_1 и T_2,
2. Через них проводится прямая линия,
3. Эта линия обязательно пересекает кривую в третьей точке,
4. Эта третья точка отражается относительно оси – и получается результат T_{1} + T_{2} = T_{3} .

Это определение не случайно:

• оно делает операцию детерминированной,
• результат всегда остается точкой на кривой,
• операция сложения обратима (для сложения существует вычитание).

В реальной реализации все считается алгебраически по формулам, но логика именно такая.

2.3. Получение Bitcoin-адреса из публичного ключа

Публичный ключ в Bitcoin почти никогда не используется напрямую. Вместо этого из него формируется Bitcoin-адрес – компактный и удобный идентификатор.

Bitcoin-адрес – это не ключ и не точка эллиптической кривой, а результат хэширования публичного ключа.

Зачем вообще нужен адрес? Публичный ключ:

• имеет длину 33 или 65 байт,
• неудобен для ручного ввода,
• напрямую раскрывает точку Q эллиптической кривой.

Адрес решает сразу несколько задач:

• сокращает размер данных,
• защищает от ошибок при вводе,
• скрывает публичный ключ до момента траты средств.

Как формируется (стандартный P2PKH) адрес? Процесс состоит из четырех последовательных шагов:

1. Хэширование публичного ключа
2. Публичный ключ последовательно хэшируется алгоритмами SHA-256 и RIPEMD-160. Результат – 160-битное значение (HASH160).
3. Добавление версии сети
4. К HASH160 добавляется байт, определяющий тип и сеть адреса.
5. Контрольная сумма
6. Вычисляется и добавляется короткая контрольная сумма для защиты от ошибок при вводе.
7. Кодирование Base58Check
8. Финальный результат кодируется в строку удобного формата – Bitcoin-адрес.

Принципиально важно

1. Адрес – это хэш, а не ключ.
2. По адресу нельзя восстановить:
3. - публичный ключ,
4. - приватный ключ,
5. - точку на кривой.
6. Пока средства не потрачены:
7. - информации о публичном ключе нет в сети,
8. - публичный ключ появляется в блокчейне только при совершении транзакции с соответствующего адреса (важно для головоломки).

Связь с Bitcoin-головоломкой Для большинства адресов головоломки:

• известен только адрес,
• публичный ключ скрыт,
• задача сводится к поиску приватного ключа методом перебора.

Исключение – адреса кратные 5, где:

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

3. Почему невозможно восстановить приватный ключ напрямую

3.1. Задача ECDLP – что это такое

Мы уже видели формулу получения публичного ключа из приватного в Bitcoin:

• Q – публичный ключ,
• k – приватный ключ (секретное число),
• G – фиксированная базовая точка эллиптической кривой secp256k1.

Зная k и G, легко можно найти Q, однако обратная задача – вычисление k по известным Q и G – практически невозможна.

Именно эта задача обратного нахождения публичного ключа по приватному называется ECDLP –
задача дискретного логарифма на эллиптической кривой

3.2. Почему эта задача считается сложной

Важно понимать, что операция $k \cdot G$:

• не является обычным умножением,
• не имеет аналитической обратной функции,
• представляет собой многократное сложение точек на эллиптической кривой с вычислениями по модулю большого простого числа.

В результате получается односторонняя функция:

• прямое вычисление (k → Q) выполняется быстро,
• обратное (Q → k) не имеет эффективного алгоритма.

При этом пространство возможных значений k огромно – приблизительно 2^{256}. Это означает, что даже при скорости 1 млрд ключей в секунду полный перебор всех приватных ключей занял бы примерно $1.38 \cdot 10^{60}лет$. Сложность задачи ECDLP обеспечивает безопасность Bitcoin.

3.3. Интуитивные, но провальные пути решения

При взгляде на задачу возникает ощущение, что решение должно существовать каким-то относительно простым способом. Приватный ключ – это просто число, а публичный ключ получен из него через повторяющуюся операцию сложения точки G с самой собой. Логично предположить, что эту операцию можно обратить и найти исходный ключ k. На практике подобные идеи быстро упираются в фундаментальные ограничения эллиптической криптографии.

Идея № 1 – попытка решить уравнение аналитически

В классической математике уравнение вида $Q = k \cdot G$ можно было бы попытаться решить делением. Однако умножение точки на эллиптической кривой:

• не является линейной операцией,
• не допускает определения обратной функции,
• не имеет аналога алгебраического логарифма.

Отсутствие аналитического обратного преобразования делает задачу ECDLP криптографически стойкой.

Идея № 2 – пошаговое приближение к верному решению Еще одна интуитивная идея – постепенно приближаться к правильному значению приватного ключа, подбирая его и наблюдая за значением публичного. Может показаться, что если при изменении значения k соответствующее значение Q приближается к известному, то нужно продолжать изменять k в том же направлении и следить за результатом, пока не получится подобрать верный приватный ключ. Но эллиптическая кривая в конечном поле:

• не является непрерывной,
• не имеет понятия расстояния до решения или направления,
• не дает информации о том, стало ли текущее значение k ближе к верному или нет.

Каждый новый кандидат на приватный ключ выглядит так же случайно, как и предыдущий.

Идея № 3 – многократное вычитание точки G из Q

Может показаться, что если публичный ключ находится как $Q = k \cdot G$ и операция умножения на самом деле представляет собой многократное сложение точки G с самой собой, то можно попробовать "разделить" Q на G. Идея такая: последовательно вычитать G из Q, считая шаги, и предположить, что их количество даст искомое k.

Однако, чтобы &amp;quot;разделить&amp;quot; Q на G нам необходимо знать, сколько раз нужно вычесть G из Q, чтобы получить 0, а это и есть значение k. Этот парадокс показывает, почему операция деления не определена в ECDLP, а многократное вычитание точки G из Q равносильно полному перебору и не имеет смысла.

Идея № 4 – использование геометрии кривой Название «эллиптическая кривая» создает ощущение, что геометрия формы может помочь в решении задачи. На практике вычисления ведутся не в обычном пространстве, а по модулю большого простого числа. Геометрическая интуиция здесь не работает: все точки распределены псевдослучайным образом, а сама кривая специально выбрана так, чтобы не обладать полезными симметриями или уязвимыми структурами.

3.4. Лучшие известные алгоритмы для ECDLP

Задача дискретного логарифма на эллиптической кривой изучается уже десятилетия. За это время были предложены различные алгоритмы, которые существенно улучшают асимптотическую сложность по сравнению с полным перебором, однако принципиально не решают задачу. Они позволяют ускорить поиск лишь в том случае, если диапазон возможных значений приватного ключа заранее ограничен. Без такого ограничения вычисление ключа для кривой secp256k1 остается вычислительно недостижимым.

1. Полный перебор (brute-force)

Идея: последовательно проверять все возможные допустимые k, вычисляя $k \cdot G$ и сравнивая результат с Q.

Особенности:

• сложность перебора O(N) , где N \approx 2 ^{256},
• гарантированно находит ключ, но абсолютно невозможен на практике.

Вывод: возможен только в теории и служит основой для других алгоритмов.

2. Алгоритм больших и малых шагов (BSGS)

Это означает, что одна и та же точка на эллиптической кривой может быть получена двумя разными способами: как результат «малого шага» jG и как результат «большого шага» Q − i(mG).

Вывод: BSGS теоретически эффективен, но на практике неприменим для реальных Bitcoin-адресов. Он имеет смысл, если диапазон возможных значений приватного ключа заранее ограничен.

3. Алгоритмы Pollard’s Rho и Kangaroo

В задаче дискретного логарифма на эллиптических кривых этим множеством является группа точек порядка N. Pollard’s Rho строит детерминированную, но ведущую себя как случайная, последовательность точек вида $X = \alpha G + \beta Q$, где коэффициенты α и β изменяются по фиксированному правилу

Вывод: Pollard алгоритмы эффективны для Bitcoin-головоломок, где пространство поиска искусственно ограничено, но практически бесполезны для реальных Bitcoin-адресов, где приватный ключ равномерно распределен по всей группе secp256k1.

4. Алгоритм Шора Алгоритм Шора – квантовый алгоритм, позволяющий решать задачу ECDLP за полиномиальное время на квантовом компьютере. Его идея в том, чтобы находить скрытую периодичность в эллиптической кривой через квантовое преобразование Фурье и напрямую восстанавливать приватный ключ.

Вывод: Алгоритм Шора теоретически решает ECDLP за полиномиальное время, но для практического применения на кривой secp256k1 требуется квантовый компьютер масштабом, недостижимым на современном уровне технологий.

3.5. Общий вывод

Задача ECDLP приобретает почти философский смысл. Она наглядно демонстрирует человеческое бессилие перед фундаментальными, «вечными» структурами математики: несмотря на то что эллиптические кривые и сама постановка задачи созданы человеком, их обратное решение непосильно ему. В то же время, многолетние попытки приблизиться к решению ECDLP отражают противоположную сторону – настойчивость и отказ мириться с ограничениями.

4. Возвращаемся к Bitcoin Puzzle

Головоломка построена как последовательность уровней, каждый из которых соответствует адресу и неизвестному соответствующему ему приватному ключу, выбранному из заранее заданного числового диапазона. Номер уровня напрямую определяет размер этого диапазона и, следовательно, вычислительную сложность поиска ключа.

Каждый следующий уровень удваивает пространство поиска по сравнению с предыдущим. Это приводит к экспоненциальному росту сложности при линейном росте порядкового номера уровня. Как упоминалось ранее, все уровни головоломки также делятся на два разных типа, несмотря на то что внешне они выглядят одинаково – как набор Bitcoin-адресов с вознаграждением за нахождение ключа.

• Первый тип – адреса, для которых известен только сам Bitcoin-адрес (HASH160), а публичный ключ скрыт.
• Второй тип – адреса, для которых публичный ключ уже раскрыт в блокчейне.

Эти два типа уровней соответствуют двум различным криптографическим задачам и требуют принципиально разных подходов к поиску приватного ключа.

4.1. Уровни с неизвестным публичным ключом

Для уровней первого типа известен только Bitcoin-адрес, то есть результат хэширования публичного ключа. Сам публичный ключ отсутствует и не может быть восстановлен из адреса. Задача выглядит так: требуется найти приватный ключ k из заранее известного диапазона значений, при котором выполняется цепочка преобразований:

k ⭢$Q = k \cdot G$⭢$\mathrm{HASH160}(Q) = Bitcoin-адрес$

Поскольку публичный ключ неизвестен, задача не является ECDLP. Единственный способ решения – полный перебор значений k и проверка соответствующих им Bitcoin-адресов на совпадение с истинным известным адресом. На ранних уровнях этот подход оказался эффективным. Диапазон возможных значений k там достаточно мал, чтобы перебор с использованием оптимизированных алгоритмов и подходящего оборудования давал результат за разумное время. Этим объясняется быстрый прогресс на начальных этапах Bitcoin Puzzle. За годы существования головоломки сообщество добилось заметных успехов на уровнях этого типа. Были реализованы и почти доведены до предела эффективности:

• оптимизированные реализации эллиптического умножения на CPU и GPU,
• специализированные программы перебора с минимальными накладными расходами,
• распределенные системы поиска с точным разбиением диапазонов между участниками(пулы),
• агрессивные методы распараллеливания и балансировки вычислительной нагрузки.

Все эти улучшения позволяли сокращать время перебора и постепенно продвигаться по уровням головоломки. На сегодняшний день последним решенным уровнем данного типа является уровень №69. При этом принципиально важно, что достигнутые оптимизации не изменили фундаментальную сложность задачи. Экспоненциальный рост пространства поиска быстро перекрывает любые технические улучшения. В результате дальнейший прогресс на уровнях с неизвестным публичным ключом ограничен не качеством кода и не объемом вычислительных ресурсов, а самой природой задачи.

4.2. Уровни с известным публичным ключом (ECDLP)

Для уровней второго типа публичные ключи соответствующих Bitcoin-адресов уже раскрыты в блокчейне – это произошло в результате ранее совершенных микротранзакций.

4.3. Текущий прогресс Bitcoin Puzzle

На момент выпуска статьи:

• Решено 82 из 160 уровней головоломки.
• - Уровни с неизвестным публичным ключом: последний решенный – уровень №69. Все они были пройдены с помощью оптимизированного перебора, ускоренного CPU и GPU, распределенных пулов и эффективного распараллеливания.
• - Уровни с известным публичным ключом (ECDLP): активное использование алгоритмов BSGS, Pollard’s Rho и Kangaroo. Самый выдающийся результат – решение уровня №130 с помощью модифицированного Kangaroo.
• Награды, полученные участниками:
• - Общий призовой фонд вырос с 32 BTC на старте до почти 1000 BTC.
• - Участники получили ~72 BTC, в призовом фонде осталось ~916 BTC.
• Достижения сообщества:
• - Созданы и протестированы распределенные системы перебора с делением диапазонов между участниками (пулы).
• - Разработаны и оптимизированы алгоритмы хэширования, умножения точек на кривой для CPU и GPU.
• - Значительное улучшение алгоритмов решения ECDLP благодаря уменьшению констант.
• - Созданы специализированные программы для решения головоломок с открытым исходным кодом.
• - Активное взаимодействие на форумах и обмен знаниями между участниками.

5. Заключение

Bitcoin Puzzle – это не только доказательство криптографической стойкости Bitcoin, но и уникальная история коллективного поиска на границе возможного. В течение многих лет она объединяет людей со всего мира вокруг одной задачи, превращая абстрактную математику в практический опыт. Каждый решенный уровень стал одновременно техническим достижением и свидетельством того, что человеческий энтузиазм, сотрудничество и настойчивость способны создавать научный прогресс даже там, где окончательный ответ заведомо недостижим. Полезные ссылки:

• Puzzle Transaction

• Список всех уровней головоломки

• Обсуждение головоломки на форуме

• Задача ECDLP