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

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

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

Чушь.

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

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

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

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

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

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

ECDSA.

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

Алгоритм Шора позволяет эффективно решать задачу дискретного логарифмирования на эллиптических кривых.

То есть если у вас есть публичный ключ:

Q = dG

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

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

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

Нет.

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

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

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

HASH160(pubkey)

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

Он появляется только в момент расходования средств.

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

Сегодня оно составляет минуты.

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

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

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

Потому что в этот момент рухнет вообще вся современная инфраструктура.

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

Весь интернет превратится в тыкву.

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

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

Нет.

Они убьют вообще всю современную криптографию.

Причем банки пострадают значительно сильнее.

Потому что блокчейн можно обновить хардфорком.

Можно заменить ECDSA на CRYSTALS-Dilithium, Falcon или SPHINCS+.

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

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

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

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

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

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

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

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

Логистика.

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

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

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

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

Решение задач комбинаторной оптимизации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это не вопрос ближайших лет.

Возможно даже не вопрос ближайших десятилетий.

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

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

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

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