Kvantové počítače jsou považovány za hrozbu pro Bitcoin. Dva vědci to spočítali: Mají kvantoví těžaři skutečně výhodu oproti klasickým těžařům? A pokud ano – představuje to hrozbu pro Bitcoin?
Bitcoin a kvantové počítače: Toto téma jsme tu už jednou nebo dvakrát měli a vlastně straší Bitcoin od samého počátku.
Ohrožují kvantové počítače Bitcoin? Přijde jednoho dne kvantový počítač a díky svému vynikajícímu výpočetnímu výkonu vyprázdní všechny peněženky a vytěží všechny Bitcoiny? Někteří říkají ano, v dlouhodobém horizontu by se to mohlo stát, jiní říkají ne, po velmi dlouhou dobu se nebudeme obávat ani gramu.
O kvantových počítačích, Bitcoinu a podpisovém algoritmu ECDSA jsme již psali. Dnes se podíváme na článek, ve kterém dva kanadští profesoři informatiky analyzují, zda kvantoví těžaři představují nebezpečí, a pokud ano, tak jaké.
Toto téma není triviální, zejména pro matematické laiky. Ale protože je to vzrušující pro každého, kdo se zajímá o Bitcoin a budoucnost výpočetní techniky, pokusím se článek představit co nejjednodušeji.
Skokový pokrok
Základní rámec, na kterém autoři staví svou otázku, je následující teorie: Pokud se těžař stane příliš silným, může ohrozit síť. Pokud má absolutní většinu, může vést 51% útoky, ale i pod touto hranicí může způsobit škody „agresivní“ nebo „sobeckou“ těžbou.
A co když těžař získá díky kvantovým výpočtům takovou výhodu, že jeho podíl na hashrate neúměrně vzroste?
V podstatě už jsme to všechno probrali a je to celkem triviální: technologický pokrok urychluje těžbu. Neděje se to postupně, ale často skokově. Od roku 2011 grafické karty vytlačily hlavní procesory, od roku 2013 grafické karty vytlačily Asics. V takových okamžicích již účinnost neroste lineárně, ale kvadraticky nebo exponenciálně. Nyní, když se zdá, že společnost Ascis do značné míry vyčerpala potenciál klasických čipů, by kvantové počítače mohly znamenat další velký skok.
To by samo o sobě nemělo představovat problém. Teoretická mechanika hry bitcoin motivuje racionální hráče k poctivosti a vzájemné kontrole. Přesto může být technologický skok hrbolatý a možná se stane vstupní branou pro nepřátelské síly, které budou jednat iracionálně, aby poškodily Bitcoin.
Proto má smysl vědět, kdy k tomu může dojít. Co se musí stát, aby kvantové počítače vytlačily klasické Asicsy z těžby bitcoinů?
Vyhledávání v netříděných databázích
Těžbu bitcoinů si můžete představit jako těžaře, kteří svým výpočetním výkonem generují spoustu peněz. Generují náhodné hashe, a pokud hash splňuje určité velmi vzácné požadavky, těžař najde blok. Můžete to také nazvat útokem hrubou silou na hašovací funkci SHA256.
Oba profesoři to vyjádřili takto: „Těžaři se snaží částečně invertovat kryptografickou hashovací funkci“. Tato „částečná inverze hashovací funkce“ je „ekvivalentní hledání označené položky v neuspořádaném seznamu položek (nestrukturované hledání)“. Zdá se to jako maličkost, ale je to základ všeho ostatního.
Kvantové počítače toho totiž prokazatelně moc neumějí. Jednou z mála úloh, kde kvantové počítače předčí klasické počítače, je hledání konkrétní položky v neuspořádaném seznamu.
Klasický počítač musí při prohledávání neuspořádané databáze – nebo při útoku hrubou silou – procházet jeden záznam za druhým. Můžete si ji představit jako dvourozměrný ukazatel, který se pohybuje od položky k položce. Když vidí polovinu záznamů, je šance na úspěch vyšší než 50 %. Klasický počítač tedy potřebuje v průměru N/2 operací, kde N je celkový počet možných položek.
Kvantové počítače mají nyní výhodu: qubit může být současně 0 i 1, a proto může řada qubitů současně reprezentovat všechny myslitelné varianty. Můžete si ji představit jako ukazatel směřující do rozměru N. Když jsou qubity v této „superpozici“, řešení je již v nich. Je tam.
Jakmile však začnete měřit, zničíte řešení. To je známé kvantové dilema: pokud měříte, nutíte kvanta, aby zaujala určitý, ale náhodný stav. Kvantový počítač tedy zná řešení, ale tragickým způsobem ho znehodnotí, když si ho jdete vyzvednout.
Groverův algoritmus: prakticky urychlený čtverec
Tady přichází na řadu Groverův algoritmus. Groverův algoritmus, který vyvinul Lov Grover v roce 1996, je metoda kontroly výsledku. Kombinací různých „kvantových bran“, což jsou operace v kvantových počítačích, qubity detekují falešné výsledky a potlačují je. S každým opakováním – takzvanou Groverovou iterací – se tak zvyšuje pravděpodobnost získání správného výsledku.
Celá věc je v detailech šíleně složitá. Jedno je však jasné: při správném počtu iterací může Groverův algoritmus takové vyhledávání výrazně urychlit. Protože k nalezení položky v nesetříděném seznamu potřebuje Grover pouze √n pokusů. Je tedy téměř kvadraticky rychlejší.
Dva příklady: Pokud jsou k dispozici 4 položky, klasické počítače a kvantové počítače potřebují 2 pokusy. Naproti tomu kvantový počítač s 5 198 400 položkami je nalezen po 2280 pokusech, zatímco konvenční počítač musí pracovat více než dva milionykrát.
Zejména u úloh s extrémní obtížností nebo extrémně vysokým N, jako je těžba bitcoinů, je tento rozdíl – tzv. kvantová výhoda – obrovský. Je to jeden z těch skoků, které otřesou celými ekosystémy. Alespoň teoreticky.
Kvantová výhoda se rozplývá
V praxi narazí kvantový těžař na velmi specifický problém: blok může najít pouze tehdy, když změří výsledek – a tím proces přeruší. Musí tedy předem vědět, kolik iterací provede.
Otázka je záludná. Protože jak příliš mnoho, tak příliš málo má své nevýhody. Více iterací zvyšuje šanci na nalezení správného řešení – ale také nebezpečí, že jiný těžař bude rychlejší. Menší počet iterací naopak snižuje pravděpodobnost správného výsledku – a tím i kvantovou výhodu.
Kdyby měl kvantový počítač nekonečný čas, mohl by plně využít kvantové výhody. To však při těžbě není možné. Musí najít kompromis mezi příliš malým a příliš velkým počtem iterací.
Pro výpočet optimálního kompromisu vytvořili výzkumníci Markovův řetězec s možnými scénáři. Markovův řetězec je matematická formulace posloupností možných, obvykle náhodných nebo částečně náhodných událostí. Takový řetězec ukazuje, které cesty džunglí pravděpodobností vedou v průměru k nejlepším výsledkům: jaké nastavení Groverova algoritmu by bylo ideální.
Překvapivě by to bylo 16 minut.
Dvě pozoruhodná zjištění
Čeká-li kvantový těžař na přečtení výsledku Groverova algoritmu 16 minut, jeho výhoda oproti klasickým těžařům dosahuje maxima v poměru k nevýhodám, které vyplývají z dlouhého časového rozpětí. Podle vědců tato výhoda existuje bez ohledu na obtížnost.
Výsledek je velmi pozoruhodný, protože jej lze přenést do praxe. Zde lze vidět dva závažné důsledky:
Za prvé, těžař s takovou taktikou se diskvalifikuje z přibližně 80 procent bloků. Ty se totiž nacházejí za méně než 16 minut. Se zbývajícími 20 procenty maximalizuje své šance na úspěch. To by měl být maximální celkový těžební výkon, kterého mohou kvantové počítače dosáhnout, aniž by byla obětována účinnost.
Za druhé, většina kryptoměn má kratší intervaly mezi bloky. Dogecoin a Litecoin mají asi několik minut, Ethereum a Ripple jen několik sekund. Kvantoví těžaři dostanou s těmito blockchainy krvavý nos, protože kvantová výhoda zde neplatí. Již nyní jsou kvantově bezpečné – přinejmenším při těžbě.
Slepou uličkou se zdá být i paralelizace kvantových počítačů. Ačkoli je to u Groverova algoritmu možné, podle výpočtů autorů to zvyšuje výkon pouze o faktor √m. U klasických počítačů je tento faktor m, tj. je kvadraticky větší. Proto je sporné, zda budou kvantové počítače někdy relevantní pro těžbu.
78 Megahashes
Tyto výpočty výrazně snižují nebezpečí kvantových počítačů. Zásadní otázka však stále zůstává nezodpovězena: Co se musí stát, aby kvantoví těžaři skutečně získali výhodu oproti klasickým těžařům? V jakém okamžiku bude levnější najít blok s kvantovým počítačem – pokud vůbec někdy?
Rozhodující jsou přitom dva faktory: náklady na jednu iteraci groveru a poměr počtu hashů potřebných pro blok k počtu potřebných iterací groveru. Autoři to vypočítali na příkladu v současnosti běžného kvantového počítače s „rychlostí brány“ 66,7 megahertzů. Brány jsou kvantové operace. Vědci spočítali, že tento kvantový počítač by zvládl 224 groverových iterací za sekundu.
Co to znamená? 224 Groverových iterací odpovídá rychlosti hašování 78 megahashe za sekundu. To je naprosto mikroskopická část hashrate Bitcoinu, ve skutečnosti jen nepatrný zlomek toho, čeho dosahují moderní Asics. Bylo by směšné cítit zde nebezpečí.
V budoucnu budou pravděpodobně energeticky účinnější
Ale pokud kvantové těžaře nepředstavují hrozbu – jsou alespoň účinnější? Může tedy dojít alespoň k postupnému přechodu na kvantovou těžbu? A v jakém okamžiku?
Aby byla iterace Groverova algoritmu efektivnější, měly by být energetické náklady na ni maximálně 3,49 x 105krát vyšší než náklady na klasický hash. V porovnání s klasickými těžaři, které mají energetickou účinnost 10-10 Julesů na hash, by kvantový počítač potřeboval účinnost lepší než 3,49 x 105 x 10-10, tedy asi 10 μJ na jednu Groverovu iteraci. Nebo 2240 μJ za sekundu.
To zní velmi nízko. Kvantové počítače jsou však energeticky velmi úsporné. Jakmile se systém ochladí na 15 milikalvinů, tedy téměř na absolutní nulu, stanou se kvantové bity supravodičem: nepotřebují prakticky žádnou elektřinu a neprodukují prakticky žádné teplo. V současné době je chlazení v poměru k výkonu kvantového počítače stále neekonomické. To se však s rozvojem technologií pravděpodobně změní.
Celkově tedy můžeme jako bitcoináři spát klidně a o něco moudřeji a bez hrůzy snít o budoucnosti kvantových počítačů.
