Кубиты и блокчейн

Каждый раз, когда выходит очередная новость про Google, IBM или какой-нибудь новый сверхпроводящий кубит, из всех щелей начинают вылезать эксперты с заявлениями:

«Биткоину конец».
«Блокчейн будет взломан».
«Крипта умрет».

Чушь.

Причем чушь сразу на нескольких уровнях.

Во-первых, большинство людей вообще не понимает, что именно в блокчейне может быть атаковано квантовыми вычислениями.

Хеш-функции SHA-256 и Keccak не «ломаются» алгоритмом Шора. Для них существует только алгоритм Гровера, который дает квадратичное ускорение перебора.

То есть вместо 2²⁵⁶ операций потребуется примерно 2¹²⁸.

Да, это очень много. Но 2¹²⁸ - это все еще настолько астрономическая величина, что практическая атака остается за пределами разумного.

Настоящая проблема лежит совсем в другом месте.

ECDSA.

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

Для публичного ключа на эллиптической кривой \(Q=dG\) лучшие известные общие классические атаки на подходящую кривую требуют работы, экспоненциальной по битовой длине ключа; это не доказательство экспоненциальности любого возможного классического алгоритма. Алгоритм Шора решает дискретный логарифм за полиномиальное время на достаточно мощном отказоустойчивом квантовом компьютере. Проблема касается и подписей Шнорра, а не только ECDSA.

И вот здесь начинается самое интересное.

Большинство людей думают, что это автоматически означает смерть биткоина.

Нет.

Во-первых, в Bitcoin адрес и публичный ключ - это разные вещи.

Новый выход P2PKH обычно скрывает публичный ключ до расходования, если тот же ключ не раскрыт где-то ещё. Повторно использованные ключи и выходы, уже показывающие публичный ключ, включая P2PK и Taproot, такой защиты не имеют. Сокрытие за HASH160 тоже не является вечной квантовой защитой: идеализированный общий поиск прообраза 160-битного хеша имеет сложность около 2^80 квантовых запросов, а не 2^128.

В блокчейне хранится только:

HASH160(pubkey)

То есть сначала злоумышленнику нужно получить публичный ключ.

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

Фактически возникает окно атаки между трансляцией транзакции и ее включением в блок.

Время подтверждения зависит от появления блоков, комиссии и загрузки; это не фиксированное число минут.

Чтобы украсть средства, квантовый компьютер должен:

1. Получить транзакцию из mempool.
2. Извлечь публичный ключ.
3. Запустить алгоритм Шора.
4. Восстановить приватный ключ.
5. Подписать собственную транзакцию.
6. Успеть включить ее раньше оригинальной.

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

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

TLS.
SSH.
PGP.
VPN.
Корпоративные PKI.
Электронные подписи государств.
Банковские HSM.
Половина военной связи.

«Весь интернет превратится в тыкву» является риторикой, а не техническим следствием алгоритма Шора. В перечисленных системах могут быть уязвимые компоненты с открытым ключом, но они тоже допускают обновление; часть систем уже использует гибридные или постквантовые механизмы.

И вот здесь особенно смешно наблюдать за людьми, которые говорят:

«Квантовые компьютеры убьют криптовалюты».

Нет.

Квантовые компьютеры не ломают всю криптографию. Шор угрожает RSA и системам на эллиптических кривых; симметричные шифры и хеши сталкиваются с другими атаками и могут сохранять полезную стойкость при подходящих параметрах.

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

Обновление блокчейна требует проектирования протокола, консенсуса, переноса ключей и решения о монетах неактивных владельцев; слово «хардфорк» само по себе этих задач не решает.

Постквантовые подписи ML-DSA на основе CRYSTALS-Dilithium и SLH-DSA на основе SPHINCS+ уже стандартизированы. Falcon является ещё одним семейством подписей.

Можно ввести гибридные схемы подписей.

Можно постепенно мигрировать UTXO.

А вот обновить миллиарды встроенных устройств, старые промышленные контроллеры, военную технику, спутники, банковские HSM, IoT устройства и корпоративный легаси-код - это уже совершенно другой уровень ада.

Но есть проблема куда интереснее.

Все почему-то рассматривают квантовые компьютеры исключительно как средство взлома.

Это крайне примитивный взгляд.

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

Портфельная оптимизация.

Логистика.

Поиск экстремумов.

Моделирование материалов.

Криптоанализ.

Обучение некоторых классов моделей.

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

Представьте себе фонд, который способен просчитывать рынок хотя бы на несколько порядков быстрее конкурентов.

Представьте маркет-мейкера, который способен оптимизировать тысячи стратегий одновременно.

Представьте государство, которое получает асимметричное преимущество в криптоанализе.

Вот это уже настоящий кошмар.

Потому что распределенность мира держится не на демократии и не на гуманизме.

Она держится на том, что вычислительные ресурсы более-менее доступны всем.

Да, у кого-то больше серверов.

Да, у кого-то больше денег.

Но фундаментально любой человек может скачать Linux, поднять узел Bitcoin, написать свой движок на Rust или Python и играть примерно по тем же правилам.

Квантовые вычисления потенциально могут это сломать.

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

Новая технологическая аристократия.

Не владельцы земли.

Не владельцы фабрик.

А владельцы вычислений.

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

До этого момента, впрочем, еще очень далеко.

Современные квантовые компьютеры по своему уровню развития напоминают компьютеры пятидесятых годов.

Красивые лабораторные игрушки.

Тысячи инженерных проблем.

Шумные кубиты.

Ужасающее время когерентности.

Чудовищные требования к коррекции ошибок.

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

Надёжная дата появления криптографически значимого квантового компьютера неизвестна. Эта неопределённость является поводом готовить миграцию, а не обещать десятилетия безопасности.

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

Но когда это все-таки произойдет, человечество столкнется не с кризисом криптовалют.

Оно столкнется с кризисом самой идеи цифрового доверия.

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

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