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

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

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

Нісенітниця.

Причому нісенітниця одразу на кількох рівнях.

По-перше, більшість людей взагалі не розуміє, що саме у блокчейні може бути атаковано квантовими обчисленнями.

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

Тобто замість 2²⁵⁶ операцій знадобиться приблизно 2¹²⁸.

Так, це дуже багато. Але 2¹²⁸ — це все ще настільки астрономічна величина, що практична атака залишається за межами розумного.

Справжня проблема лежить зовсім в іншому місці.

ECDSA.

Саме цифрові підписи є потенційно вразливим місцем більшості блокчейнів.

Алгоритм Шора дозволяє ефективно вирішувати задачу дискретного логарифмування на еліптичних кривих. Для класичного комп’ютера ця задача є експоненціальною, а на досить потужному квантовому комп’ютері задача стає поліноміальною.

І ось тут починається найцікавіше.

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

Ні.

По-перше, у 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 оцінки зазвичай ідуть на мільйони фізичних кубітів та величезну кількість логічних операцій.

Це не питання найближчих років.

Можливо, навіть не питання найближчих десятиліть.

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

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

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

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