Кубити и блокчејн

Сваки пут када изађе нова вест о 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 зависе од алгоритма, физичких грешака, архитектуре и потребног времена. Не постоји универзални праг од „милиона кубита”; број кубита без тих претпоставки није корисна прогноза.

Поуздан датум појаве криптографски значајног квантног рачунара није познат. Та неизвесност је разлог за припрему миграције, а не за обећавање деценија безбедности.

Обим последица зависиће од тога који ће рањиви системи тада остати у употреби.

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

Оно ће се суочити са кризом саме идеје дигиталног поверења.

Зато што смо последњих педесет година градили цивилизацију полазећи од претпоставке да су неки математички задаци рачунарски нерешиви.

И ако се једног дана испостави да то више није тако, мораће се преписати практично читав дигитални свет од нуле.