Kvantumszámítógépek és a Bitcoin/Blockchain viszonya?

Gyakran kerül elő a modern kriptográfia kapcsán az ismert frázis mely szerint a kvantumszámítógépek rohamos fejlődése komoly fenyegetést jelent. A kvantumszámítógépek speciális adatábrázolási lehetősége (qubitek és azok szuperpozíciója) miatt már a közeljövőben várható olyan technológia amivel könnyedén lehet majd “feltörni” az olyan modern kriptográfiai eszközöket mint az SSL és annak alapját adó aszimmetrikus kriptográfia, mely végső soron az egész modern informatika egyik alapköve… Eme halmazba pedig igencsak beletartozik a Bitcoin és úgy egyébként a teljes blockchain technológia is.

TLDR: Ezt a postot eredendően egy rövid szösszenetnek szántam, de szokás szerint kifejtős lett; teletűzdelve olyan háttér-információkkal, melyre az olvasók nagy részének nem hiszem, hogy szüksége lenne; éppen ezért lelőném előre a poént, így csak annak kell tovább olvasnia a cikket, akit érdekel az egész történet szakmai háttere is: A Bitcoin hálózat által használt ECDSA (256) titkosítás bár alapvetően sérülékeny lehet a Shor módszertanos prímtényezős felbontásra, azonban az ehhez szükséges információt a hálózat már csak akkor rakja bele a blockláncba, amikor elköltésre került egy-egy address bitcoin tartalma. Tehát ha a Bitcoinista BETARTJA azt a szabályt, hogy minden addresst csak egyszer használ, akkor nem kell tartania a kvantumszámítógépek okozta fenyegetéstől. Az “address reuse”-t a legtöbb szélesebb körben elterjedt bitcoin pénztárca eleve elkerüli így ez a fajta fenyegetés csak akkor lehet valós, ha valaki egyéb módon (pl paperwallet) szeletelgeti a meglévő egy addressen felhalmozott vagyonát.

Még június végén mutattam be itt a blogon egy – emlékeim szerint Gartner által kiadott – ábrát, amin a legnagyobb üzleti hatással rendelkező technológiák között a “high” és a “transformational” kategóriák között előkelő helyen szerepel a kvantum-számítástechnika, melyhez kaptunk is egy céldátumot: 2019+

Így 2017 végéhez közeledve adja magát a kérdés: mennyire is sci-fi a kvantumszámítógépek létezése és mennyire is valós a fenyegetés a “szuperpénz” jövőjét tekintve?

Nem szeretnék nagyon mélyen belemenni a kvantum-számítástechnika rejtelmeibe, de elkerülhetetlen, hogy legalább minimálisan képbe kerüljünk: A kvantum-számítástechnika adatmodelljének elemi egysége a kvantumbit, azaz a qubit. Ez hasonló a ‘hagyományos’ informatika bitjeihez, azaz két állapottal rendelkezik: 0 és 1. Emellett viszont létezik egy harmadik állapota is a szuperpozíció, amikor egyszerre rendelkezik a qubit az összes lehetséges állapottal. Ennél is izgalmasabb, hogy a szuperpozíció kiterjeszhető több qubit együttesére is a összefonódottság elve miatt. Ilyenkor nem csak egy elemi qubit, hanem akár több qubit is képes egyszerre szuperpozícióba kerülni. Innentől már adja magát a feladvány: ha meg tudsz fogalmazni egy olyan matematikai feladatot, aminek ismert a megoldása akkor az összekapcsolt qubitek számának arányába megállapítható az adott megoldáshoz vezető paraméterek értéke is, hiszen a qubitek egyszerre tudják az összes lehetséges értéket felvenni.

Ez tényleg jól hangzik, de miért is tűnik ez annyira veszélyesnek? Azért, mert a modern kriptográfia egyik legnagyobb vívmánya egy pofonegyszerű matematikai műveleten alapszik:

• Végtelenül leegyszerűsítve és beáldozva a szakmai pontosságot is: végy két baromi nagy számot, ami lehetőleg legyen prím, vagy legalábbis nagyon közel legyen prímhez. A két elemi szám legyen a legnagyobb titkod (privát kulcs). Szorozd össze a két számot melyet ezt követően már osztogathatsz boldog boldogtalannak mint publikus kulcsot, hiszen tudhatod, hogy az azzal végzett titkosításokat csak az lesz képes visszafejteni, aki ismeri a két elemi baromi nagy prímszámot. A titkosítás kulcsa az a tény, hogy a szorzatra bontás a modern matematika egyik legköltségesebb művelete. Iszonyat mennyiségű bonyolult művelet kell hozzá.

Kivéve persze, ha van egy nagyon-nagyon okos kvantumszámítógépünk: hiszen, ha képesek vagyunk egy szorzatot ábrázolni qubitekben, akkor technológiailag képesek vagyunk azok szuperpozícióján keresztül kiolvasni azok összes lehetséges szorzatpárját is. Ez eddig így eléggé wikipédiás bullshitnek hangzik ugye? Akkor egy picit pontosítsuk: A szuperpozíción és a qubitek kvantum-összefonódásán keresztüli extrém párhuzamosítás képességét már számos konkrét esetben bizonyították és alkalmazzák is. Ilyen például a Lov Grover eljárás, ami rendezetlen adatbázisban képes az elemek számának négyzetgyöke O(√_N) által megadott iteráció alatt megtalálni egy konkrét értéket, ez  az a módszer ami néhány éven belül várhatóan az összes adatbázismotort meg fogja reformálni vagy éppen szükségtelenné teszi azokat. Azonban jelen cikk szempontjából sokkal fontosabb vívmány a Shor algoritmus, mely segítségével egy kvantumszámítógép polinom időben képes véges prímtényezős felbontásra. Ez az a bizonyos módszer ami miatt egyáltalán felmerül a Bitcoin kapcsán a kvantum-számítógépes fenyegetés, persze ehhez fontos előfeltétel, hogy létezzen olyan kvantumszámítógép, ami képes megfelelően magas mennyiségű qubit esetén biztosítani a kvantum-összefonódást.

Hogy mennyi qubit-et kellene, ahhoz szuperpozícióban és összefonódott állapotban tartani, hogy egy publikus kulcs prímtényezős bontását végig lehessen csinálni? Ehhez nagyjából 1300-1500 qubit kellene minimum és ezzel is csak a nagyon korai (2009-2010-es) addressek mögött meghúzódó kulcsokat lehetne talán feltörni. Jelenleg a legkomolyabb – még csak laboratóriumi körülmények között működő – kvantum masinák is 39-40 qubit körül pörögnek, de a Google nagyon vadul dolgozik már 50 qubites környezet kialakításán. A fentebbi képen is látható jelenlegi 20 qubites IBM kvantumgép kapcsán nemrégiben jelent meg a nyilatkozat mely szerint a következő évtizedben várnak egy jelentősebb szakmai áttörést amivel elérhetővé válna az akár 100 qubit is. Szóval itt még hiányzik azért néhány nagyságrend…

Persze bárki azonnal emelhetné a kezét, hogy “Na de mi a helyzet a Dwave-vel?”. A Kanadai illetőségű cég már évek óta értékesíti a Dwavet és nemrégiben nemrégiben piacra dobta annak upgradejét a Dwave2-őt is. Előbbi 2000 qubiten ketyeg, utóbbi pedig 4000 qubiten. Szóval az utóbbival elvileg nem csak a Bitcoint, de a legnagyobb katonai titkosítási protokollokat is fel lehetne törni. A bibi csak annyi, hogy a Dwave valójában nem kvantumszámítógép, hanem lényegében egy kvantumszámítógép szimulátor. Valójában nem rendelkezik a gép univerzális kvantum logikai kapukkal így bár tényleg kilóra van benne ennyi qubit, amelyekbe be is lehet tölteni a szükséges adatokat, de azokkal mégsem lehet pl egy Shor algoritmust elvégezni. Mindettől függetlenül persze a Dwave nagyon fontos a kutatók számára, nem véletlenül veszik mint a cukrot, hiszen bár maga a masina nem alkalmas pl az RSA, ECDSA, stb. kulcsok törésére, de valóban minden benne van ahhoz, hogy előre tudjanak kísérletezni vele és olyan újabb technológiákat kidolgozni, amik később alkalmasak lehetnek az “igazi” kvantumszámítógépeken is.

A Bitcoin természetes védelme…

Sokszor esem magam is abba a hibába, hogy Satoshit egyfajta felsőbbrendű lényként aposztrofálom, aki a Bitcoinban formálta meg grandiózus világmegváltó, vagy éppen hatalomátvevő tervét. És bár ez nem feltétlenül szerencsés, hiszen egyfajta bálványt építek, azonban magam is el kell ismerjem, a Bitcoin mögött rejlő blockchain technológia és a gazdasági és monetáris refaktorálás mellett  még arra is maradt ideje Nakamotonak, hogy egy tökéletesen kvantumszámítógép védetté tegye a Bitcoin protokollt. Persze ez a védelem “opt-in” jellegű, tehát kell hozzá a felhasználó is.

Alapvető tény, hogy a Bitcoin protokoll által használt SHA256 algoritmus már igencsak kopottnak számít a modern kriptográfiában, ennek megfelelően a privát kulcsok is 256 bitesek, azaz 32 byte hosszúak. Ez az a karaktersorozat, amit érdemes felírni és jól elrakni a nehezebb időkre. A privát kulcsból az ECDSA módszerrel (Elliptikus Görbe Digitális aláírási algoritmus) képződik a publikus kulcs. A privát kulcsból a publikus kulcs szabadon létrehozható, azonban az algoritmus biztosítja azt, hogy visszafelé a művelet már csak kísérletezéses (brute-force) módszerrel legyen csak lehetséges. Ez az a pont ahol a kvantumszámítógépek komoly fenyegetést jelenthetnének a Shor algoritmus miatt. És szintén ez az a pont ahol Nakamoto egy hatalmasat alkotott: A Bitcoin protokollban a privát kulcs mellett a publikus kulcs sem kerül sehol felfedésre, ez alól egyetlen kivétel az amikor ELKÖLTÉSRE kerül egy adott bitcoin. Egészen addig csak a publikus kulcsból képzett address ismert, mely irreverzibilis hashing algoritmussal képződik. Pontosabban mindjárt kettő különbözővel: előbb leképződik a publikus kulcs SHA256 hash-e, majd abból képződik egy RIPEMD-160 hash is, erre kerül még rá egy double-SHA256, majd egy checksum a végére az első négy bájtra pedig bekerül a verzió, ami a jól ismert 1-es (P2PKH) és a 3-as (P2SH) address előtagokat képezi.

Tehát hiába is ismerjük a bitcoin milliomosok addresseit, nem rendelkezhetünk azok publikus kulcsával egészen addig amíg nem költenek az addressükről. Ez az a pont ahol nyilvánosságra kerül a nyers publikus kulcs (hiszen ezzel lehet ellenőrizni a tranzakció hitelességét) és bár ezen a ponton (megfelelő kvantumszámítógéppel) fel is lehetne törni (ELVILEG!!!) a privát kulcsot is: addigra az address már üres kellene hogy legyen.

Közismert tény, hogy lehetőség szerint kerülni kell a Bitcoin esetén az “address reuse”-t, tehát azt, hogy egy Bitcoin Addresst többször használjunk. Ennek a fő oka pontosan az előzőekben bemutatott lehetséges sérülékenység és pont az az oka annak, hogy az összes modern SPV és API wallet is (használva a HD address protokollt) minden egyes művelet után egy új “charge” (visszajáró) addresst használ.

Szóval, ha ezt az egy nagyon fontos szabályt betartod, akkor soha semmi félnivalód nem kell, hogy legyen a kvantumszámítógépektől és a shor módszertől.

[commercial_break]

Ui: És csak így a végére megcáfoljam az mindazt a pozitív képet amit a cikkben felfestettem: Akad a Bitcoin protokollják egy igen komoly sérülékenység, amit nyilvánvalóan nem Nakamoto hagyott ott, hanem már a későbbi fejlesztőgárda erőszakolt bele a scaling debate kapcsán. Ez pedig az RBF (replace-by-fee) és a 0-confirmation. E két témáról részletes cikk készült korábban (-link-), ezért szorítkozva a tényekre: az RBF lehetővé teszi, hogy egy még unconfirmed tx-et annak blockba foglalása előtt szabadon lehessen módosítani a mempoolban. Ez persze csak akkor lehetséges, hogy a függő tx nSequence értéke nincs UNIT_MAX-ra állítva.

Mindennek fényében az RBF fenyegetés is csak opt-in, szóval a felhasználón múlik, hogy él-e vele. Ha bárkit kerülget a kvantum paranoia, akkor a következő két lépésben tud ultra biztonságot teremteni:

• minden address-t csak egyszer használ, ha utalnia kell onnan, akkor egyrészt új address-re utalja a “visszajárót”, másrészt pedig gondoskodik arról, hogy ne lehessen módosítani a tx-et (nSequence=UNIT_MAX)