Komputery kwantowe są uważane za zagrożenie dla Bitcoina. Dwóch naukowców dokonało obliczeń: Czy górnicy kwantowi rzeczywiście mają przewagę nad klasycznymi? A jeśli tak – czy stanowi to zagrożenie dla Bitcoina?
Bitcoin i komputery kwantowe: Mieliśmy już ten temat raz czy dwa, i tak naprawdę prześladuje on Bitcoina od samego początku.
Czy komputery kwantowe zagrażają Bitcoinowi? Czy pewnego dnia pojawi się komputer kwantowy, który dzięki swojej najwyższej mocy obliczeniowej opróżni wszystkie portfele i wydobędzie wszystkie Bitcoiny? Niektórzy mówią, że tak, w dłuższej perspektywie może się to zdarzyć, inni mówią, że nie, nie będzie ani grama zmartwień przez bardzo długi czas.
Pisaliśmy już o komputerach kwantowych, Bitcoinie i algorytmie podpisu ECDSA. Dziś przyglądamy się pracy, w której dwaj kanadyjscy profesorowie informatyki analizują, czy górnicy kwantowi stanowią zagrożenie, a jeśli tak, to jakie.
Temat nie jest trywialny, zwłaszcza dla matematycznych laików. Ale ponieważ jest to ekscytujące dla każdego, kto interesuje się Bitcoinem i przyszłością informatyki, postaram się przedstawić ten artykuł tak prosto, jak to tylko możliwe.
Skokowy postęp
Podstawowym szkieletem, na którym autorzy budują swoje pytanie, jest następująca teoria: Jeśli górnik stanie się zbyt potężny, może zagrozić sieci. Jeśli ma większość absolutną, może prowadzić 51-procentowe ataki, ale nawet poniżej tej wartości może wyrządzić szkody poprzez „agresywne” lub „samolubne” wydobycie.
A co jeśli górnik uzyska taką przewagę dzięki obliczeniom kwantowym, że jego udział w hashrate wzrośnie nieproporcjonalnie?
W zasadzie już to wszystko przerabialiśmy i jest to dość banalne: postęp technologiczny przyspiesza wydobycie. Nie dzieje się to stopniowo, ale często skokowo. Od 2011 roku karty graficzne wypierały procesory główne, od 2013 roku Asics wypierał karty graficzne. W takich momentach wydajność nie wzrasta już liniowo, ale czterokrotnie lub wykładniczo. Teraz, gdy wydaje się, że Ascis w znacznym stopniu wyczerpał potencjał klasycznych układów scalonych, komputery kwantowe mogą stać się kolejnym wielkim skokiem.
Samo w sobie nie powinno to stanowić problemu. Teoretyczna mechanika gry Bitcoin motywuje racjonalnych graczy do bycia uczciwymi i trzymania się nawzajem w szachu. Mimo to, skok technologiczny może być wyboisty, a być może stanie się furtką dla wrogich mocarstw działających irracjonalnie, by zaszkodzić Bitcoinowi.
Dlatego warto wiedzieć, kiedy to może nastąpić. Co musi się stać, aby komputery kwantowe wyparły klasyczne Asics z wydobywania Bitcoinów?
Szukanie nieposortowanych baz danych
Można pomyśleć o wydobywaniu bitcoinów jako o górnikach generujących dużo za pomocą swojej mocy obliczeniowej. Generują one losowe hashe, a jeśli hash spełnia pewne bardzo rzadkie wymagania, górnik znajduje blok. Można to również nazwać atakiem brute force na funkcję skrótu SHA256.
Dwaj profesorowie ujęli to w ten sposób: „Górnicy próbują częściowo odwrócić kryptograficzną funkcję skrótu”. To „częściowe odwrócenie funkcji haszującej” jest „równoważne z szukaniem zaznaczonego elementu na nieuporządkowanej liście elementów (wyszukiwanie nieuporządkowane)”. Brzmi to jak drobiazg, ale ma fundamentalne znaczenie dla całej reszty.
Niewiele jest bowiem rzeczy, co do których udowodniono, że komputery kwantowe są w stanie zrobić. Jednym z niewielu zadań, w których komputery kwantowe są znane z przewagi nad klasycznymi, jest wyszukiwanie określonego elementu na nieuporządkowanej liście.
Klasyczny komputer, przeszukując nieposortowaną bazę danych – lub wykonując atak brute force – musi pracować nad jednym wpisem na raz. Możesz myśleć o tym jak o dwuwymiarowym wskaźniku, który porusza się od elementu do elementu. Gdy obejrzy połowę wpisów, szansa na trafienie przekracza 50 procent. Dlatego klasyczny komputer potrzebuje średnio N/2 operacji, gdzie N jest całkowitą liczbą możliwych elementów.
Komputery kwantowe mają teraz pewną przewagę: qubit może być jednocześnie 0 i 1, dlatego seria qubitów może jednocześnie reprezentować wszystkie możliwe warianty. Można o nim myśleć jak o wskaźniku wskazującym w N wymiarach. Kiedy qubity znajdują się w tej „superpozycji”, rozwiązanie już w nich jest. To jest tam.
Ale jak tylko dokonasz pomiaru, zniszczysz rozwiązanie. Jest to słynny dylemat kwantowy: jeśli mierzysz, zmuszasz kwanty do przyjęcia określonego, ale przypadkowego stanu. Komputer kwantowy zna więc rozwiązanie, ale w tragiczny sposób dewaluuje je, gdy idziesz po nie.
Algorytm Grovera: kwadrat praktycznie przyspieszony
Tutaj wkracza algorytm Grovera. Opracowany przez Lov Grovera w 1996 roku algorytm Grovera jest metodą sprawdzania wyniku. Poprzez połączenie różnych „bramek kwantowych” – są to operacje w komputerach kwantowych – qubity wykrywają fałszywe wyniki i tłumią je. Z każdym powtórzeniem – tzw. iteracją Grovera – wzrasta więc prawdopodobieństwo uzyskania poprawnego wyniku.
Cała sprawa jest szalenie skomplikowana w szczegółach. Ale jedno jest pewne: przy odpowiedniej liczbie iteracji algorytm Grovera może drastycznie przyspieszyć takie wyszukiwanie. Ponieważ, aby znaleźć element na nieposortowanej liście, Grover potrzebuje tylko √n prób. Jest więc prawie czterokrotnie szybszy.
Dwa przykłady: Jeśli są 4 elementy, to komputery klasyczne i kwantowe potrzebują 2 prób. Z kolei przy 5 198 400 elementach komputer kwantowy zostaje odnaleziony po 2280 próbach, podczas gdy konwencjonalny komputer musi działać ponad dwa miliony razy.
Szczególnie w zadaniach o ekstremalnej trudności lub ekstremalnie wysokim N, takich jak wydobywanie bitcoinów, ta różnica – tzw. przewaga kwantowa – jest ogromna. Jest to jeden z tych skoków, które wstrząsają całymi ekosystemami. Przynajmniej w teorii.
Kwantowa przewaga topnieje
W praktyce górnik kwantowy napotyka na bardzo specyficzny problem: może znaleźć blok tylko wtedy, gdy zmierzy wynik – i dlatego przerywa proces. Musi więc wiedzieć wcześniej, ile iteracji wykona.
Pytanie jest podchwytliwe. Ponieważ zarówno zbyt wiele, jak i zbyt mało ma wady. Więcej iteracji zwiększa szansę na znalezienie poprawnego rozwiązania – ale także niebezpieczeństwo, że inny górnik będzie szybszy. Z drugiej strony, mniejsza liczba iteracji obniża prawdopodobieństwo uzyskania poprawnego wyniku – a tym samym przewagę kwantową.
Gdyby komputer kwantowy miał nieskończony czas, mógłby w pełni wykorzystać przewagę kwantów. Nie jest to jednak możliwe w przypadku górnictwa. Musi znaleźć kompromis pomiędzy zbyt małą a zbyt dużą liczbą iteracji.
Aby obliczyć optymalny kompromis, badacze utworzyli łańcuch Markowa z możliwymi scenariuszami. Łańcuch Markowa jest matematycznym sformułowaniem ciągów możliwych, zwykle losowych lub częściowo losowych zdarzeń. Taki łańcuch wskazuje, które ścieżki przez dżunglę prawdopodobieństw prowadzą średnio do najlepszych wyników: jakie ustawienie algorytmu Grovera byłoby idealne.
Niesamowite, że będzie to 16 minut.
Dwa niezwykłe odkrycia
Jeśli górnik kwantowy czeka 16 minut na odczytanie wyniku działania algorytmu Grovera, jego przewaga nad klasycznymi górnikami osiąga maksimum w stosunku do wad wynikających z długiego czasu. Według naukowców, przewaga ta istnieje niezależnie od stopnia trudności.
Rezultat jest bardzo godny uwagi, ponieważ można go przenieść do praktyki. Widać tu dwie poważne konsekwencje:
Po pierwsze, górnik stosujący taką taktykę dyskwalifikuje się z około 80 procent bloków. Ponieważ są one znalezione w mniej niż 16 minut. Z pozostałymi 20 procentami maksymalizuje swoje szanse na sukces. Powinna to być maksymalna łączna moc wydobywcza, jaką komputery kwantowe mogą osiągnąć bez utraty wydajności.
Po drugie, większość kryptowalut ma krótsze odstępy między blokami. Dogecoin i Litecoin mają około kilku minut, Ethereum i Ripple tylko kilka sekund. Górnicy kwantowi dostają krwawy nos z tymi blockchainami, ponieważ przewaga kwantowa nie ma tu zastosowania. Są one już kwantowo bezpieczne – przynajmniej w górnictwie.
Równoległość komputerów kwantowych również wydaje się być ślepym zaułkiem. Chociaż jest to możliwe w przypadku algorytmu Grovera, to według obliczeń autorów poprawia to wydajność tylko o współczynnik √m. W przypadku klasycznych komputerów współczynnik ten wynosi m, czyli jest czterokrotnie większy. To sprawia, że wątpliwe jest, czy komputery kwantowe kiedykolwiek będą miały znaczenie dla górnictwa.
78 Megahashes
Te obliczenia znacznie zmniejszają niebezpieczeństwo związane z komputerami kwantowymi. Ale zasadnicze pytanie wciąż pozostaje bez odpowiedzi: Co musi się wydarzyć, aby górnicy kwantowi mieli przewagę nad klasycznymi? W którym momencie znalezienie bloku z komputerem kwantowym stanie się tańsze – o ile w ogóle?
Decydują o tym dwa czynniki: koszt jednej iteracji grovera oraz stosunek liczby hashy potrzebnych dla danego bloku do liczby wymaganych iteracji grovera. Autorzy obliczają to na przykładzie powszechnego obecnie komputera kwantowego o „szybkości bramek” 66,7 megaherców. Bramki są operacjami kwantowymi. Naukowcy obliczają, że taki komputer kwantowy mógłby wykonywać 224 iteracje grovera na sekundę.
Znaczenie? 224 iteracje Grovera odpowiadają szybkości haszowania 78 megaheksów na sekundę. Jest to absolutnie mikroskopijna część hashrate Bitcoin, w rzeczywistości tylko niewielki ułamek tego, co osiągają nowoczesne Asics. Niedorzecznością byłoby wyczuwać tu niebezpieczeństwo.
Prawdopodobnie będą bardziej wydajne energetycznie w przyszłości
Ale jeśli minery kwantowe nie stanowią zagrożenia – czy są przynajmniej bardziej wydajne? Czy zatem może nastąpić, przynajmniej stopniowe, przejście na górnictwo kwantowe? I w którym momencie?
Aby być bardziej wydajnym, koszt energetyczny iteracji Grovera powinien być co najwyżej 3,49 x 105 razy większy niż koszt klasycznego haszowania. W porównaniu z klasycznymi górnikami, których wydajność energetyczna wynosi 10-10 Julek na hash, komputer kwantowy potrzebowałby wydajności lepszej niż 3,49 x 105 x 10-10, czyli około 10 μJ na iterację Grovera. Lub 2240 μJ na sekundę.
To brzmi niezwykle nisko. Ale komputery kwantowe są bardzo energooszczędne. Jak tylko system zostanie schłodzony do 15 milikalwinów, tj. blisko zera absolutnego, bity kwantowe stają się nadprzewodnikiem: nie potrzebują praktycznie żadnej energii elektrycznej i nie wytwarzają praktycznie żadnego ciepła. Obecnie chłodzenie w stosunku do mocy wciąż czyni komputer kwantowy nieopłacalnym. Jednak wraz z postępem technologicznym może się to zmienić.
Więc w sumie, jako Bitcoiners, możemy spać spokojnie i trochę mądrzej i marzyć bez strachu o przyszłości komputerów kwantowych.
