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

Щоразу, коли виходить чергова новина про 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 залежать від алгоритму, фізичних помилок, архітектури та потрібного часу. Універсального порога «мільйони кубітів» немає; кількість кубітів без цих припущень не є корисним прогнозом.

Надійна дата появи криптографічно значущого квантового комп’ютера невідома. Ця невизначеність є приводом готувати міграцію, а не обіцяти десятиліття безпеки.

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

Але коли це все-таки станеться, людство зіткнеться не з кризою криптовалют.

Воно зіткнеться з кризою самої ідеї цифрової довіри.

Тому що останні п'ятдесят років ми будували цивілізацію виходячи з припущення, що деякі математичні задачі є обчислювально нерозв'язними.

І якщо одного разу виявиться, що це більше не так, то доведеться переписувати практично весь цифровий світ з нуля.