Oto, dlaczego kwant nie zabije Bitcoina…

Przez Maciej Kosior Ostatnia aktualizacja mar 10, 2022 5 339

Komputery kwantowe bywają używane jako straszak dla Bitcoina. Czy „kwantowi” górnicy mają przewagę nad klasycznymi górnikami? A jeśli tak, czy rzeczywiście Bitcoin ma się czego obawiać? Sprawdźmy.

Czy komputery kwantowe zagrażają Bitcoinowi? Czy pewnego dnia pojawi się komputer kwantowy, opróżni wszystkie portfele i wykopie wszystkie bitcoiny dzięki swojej najwyższej mocy obliczeniowej? Niektórzy mówią, że tak. Inni twierdzą, że najmniejszych powodów do zmartwień nie będzie jeszcze przez bardzo długi czas.

O komputerach kwantowych, Bitcoinie i algorytmie podpisu ECDSA pisaliśmy już całkiem sporo (patrz lista linków pod artykułem). Dzisiaj zajmiemy się pytaniem, czy istnieje zagrożenie dla Bitcoina ze strony górników kwantowych, a jeśli tak, to jakie.

Problem nie jest nowy, aczkolwiek jawi się jako nad wyraz istotny. Warto zatem spojrzeć na niego z każdej możliwej strony.

Spis treści

Wielki skok naprzód

Punkt wyjścia do naszych rozważań przedstawia się zaskakująco jasno: jeśli górnik stanie się zbyt potężny, może zagrozić sieci. Jeśli ma absolutną większość, może prowadzić atak 51%, ale nawet poniżej tego może spowodować szkody poprzez „agresywne” lub „samolubne” wydobycie.

A co, jeśli dzięki obliczeniom kwantowym górnik uzyska taką przewagę, że jego udział w hash rate wzrośnie nieproporcjonalnie?

To wszystko mieliśmy już wcześniej i jest to dość trywialne: postęp technologiczny przyspiesza wydobycie. Nie dzieje się to stopniowo, ale często skokowo. Od 2011 r. karty graficzne wyparły wiodące procesory, a od 2013 r. układy ASIC wyparły karty graficzne. W takich momentach wydajność nie wzrasta już liniowo, ale kwadratowo lub wykładniczo. Teraz, gdy ASIC wyczerpał przede wszystkim potencjał klasycznych chipów, komputery kwantowe mogą zapoczątkować kolejny, wielki skok.

Samo w sobie nie powinno to stanowić problemu. Teoretyczna mechanika Bitcoina motywuje racjonalnych graczy do uczciwości i trzymania się nawzajem w ryzach. Mimo to skok technologiczny może być wyboisty i być może stanie się bramą dla wrogich sił działających irracjonalnie, aby zaszkodzić Bitcoinowi.

Dlatego warto wiedzieć, kiedy to się stanie. Co musi się wydarzyć, aby komputery kwantowe wyparły klasycznego ASIC-a z wydobywania bitcoinów?

Przeszukiwanie nieposortowanych baz danych

Wydobywanie BTC można postrzegać jako działalność górników generujących dużo mocy obliczeniowej. Generują losowe skróty, a jeśli hash spełnia określone, rzadkie wymagania, górnik znajduje blok. Można to również nazwać atakiem rangi brute force na funkcję SHA256.

Jak to ujęli dwaj kanadyjscy profesorowie, „górnicy próbują częściowo odwrócić funkcję skrótu kryptograficznego”. To „częściowe odwrócenie funkcji skrótu” jest „odpowiednikiem wyszukiwania zaznaczonego elementu na nieuporządkowanej liście elementów (wyszukiwanie nieustrukturyzowane)”. Brzmi to być może nieco trywialnie, ale ma fundamentalne znaczenie dla wszystkiego, o czym będzie mowa za chwilę.

Jednym z niewielu zadań, w których komputery kwantowe przyćmiewają klasyczne komputery, jest wyszukiwanie określonego elementu na nieuporządkowanej liście.

Podczas przeszukiwania nieposortowanej bazy danych – lub ataku typu brute force -klasyczny komputer musi pracować z jednym wpisem na raz. Możesz myśleć o tym jako o dwuwymiarowym wskaźniku, który przemieszcza się od elementu do elementu. Gdy zobaczy 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 pozycji.

Komputery kwantowe mają następującą zaletę: kubit może mieć jednocześnie ładunek 0 i 1, dlatego kilka kubitów może symultanicznie reprezentować wszystkie możliwe warianty. Możesz myśleć o tym jako o wskaźniku wskazującym na N wymiarów. Jeśli kubity są w tej „superpozycji”, rozwiązanie problemu już się tam znajduje.

To słynny dylemat kwantowy: Jeśli tylko zechciałbyś przyłożyć do tego jakąś miarę, rozwiązanie ucieka w mgnieniu oka. Zmuszasz kwant do przyjęcia określonego, ale losowego stanu. Komputer kwantowy zna zatem rozwiązanie, ale w wyniku pewnego zwrotu akcji gubi je w chwili, gdy tylko wyciągasz po nie rękę.

Algorytm Grovera: kwadratowe przyspieszenie praktyczne

Tu właśnie pojawia się algorytm Grovera. Opracowany przez Lova Grovera w 1996 roku, algorytm jest metodą sprawdzania wyniku. Łącząc różne „bramy kwantowe” – które są operacjami w komputerach kwantowych – kubity wykrywają nieprawidłowe wyniki i tłumią je. Tak więc prawdopodobieństwo uzyskania prawidłowego wyniku wzrasta z każdym powtórzeniem – w wyniku tak zwanej “iteracji Grovera”.

Całość jest szalenie skomplikowana w szczegółach. Ale jedno nie budzi wątpliwości: przy odpowiedniej liczbie iteracji algorytm Grovera może radykalnie przyspieszyć takie wyszukiwanie. W końcu, aby znaleźć przedmiot na nieposortowanej liście, Grover potrzebuje tylko kilku prób. W ten sposób jest prawie kwadratowo szybszy.

Dwa przykłady: jeśli są cztery elementy, klasyczne komputery i komputery kwantowe podejmują dwie próby. Z drugiej strony, jeśli jest 5198400 elementów, komputer kwantowy znajduje rozwiązanie po 2280 próbach, podczas gdy konwencjonalny komputer musi podjąć ponad dwa miliony obliczeń.

Różnica jest olbrzymia, szczególnie w przypadku niezwykle trudnych zadań lub ekstremalnie wysokiego N, jak w przypadku wydobywania bitcoinów. Ta różnica to tak zwana przewaga kwantowa. To jeden z tych skoków, które wstrząsają całymi ekosystemami. Przynajmniej w teorii.

Przewaga kwantowa topnieje

W praktyce górnik kwantowy napotyka szczególny problem: nie może znaleźć bloku, dopóki nie zmierzy wyniku – i tym samym nie zatrzyma procesu. Musi więc z góry wiedzieć, ile iteracji wykona.

Wyzwanie jest trudne. Ponieważ zarówno za dużo, jak i za mało obliczeń pociąga za sobą określony rodzaj implikacji. Więcej iteracji zwiększa szansę na znalezienie poprawnego rozwiązania i ryzyko, że inny górnik będzie szybszy. Z drugiej strony mniejsza liczba iteracji zmniejsza prawdopodobieństwo uzyskania prawidłowego wyniku, a tym samym przewagę kwantową.

Gdyby komputer kwantowy dysponował nieograniczonym limitem czasu na obliczenia, mógłby w pełni wykorzystać przewagę kwantową. Ale w miningu Bitcoina nie jest to możliwe. Górnik musi zatem znaleźć kompromis między zbyt małą a zbyt dużą liczbą iteracji.

Aby obliczyć optymalny kompromis, naukowcy stworzyli łańcuch Markowa z określonymi, możliwymi scenariuszami. Łańcuch Markowa to matematyczne sformułowanie możliwych, przeważnie losowych lub częściowo nieoczekiwanych sekwencji. Taki łańcuch wskazuje, które ścieżki w gąszczu prawdopodobieństw prowadzą średnio do najlepszych wyników. Innymi słowy chodzi o to, jakie ustawienie algorytmu Grovera byłoby idealne.

O dziwo, opiewałoby ono na 16 minut.

Dwa niezwykłe odkrycia

Załóżmy, że górnik kwantowy czeka 16 minut, aby odczytać wynik algorytmu Grovera. W takim przypadku jego przewaga nad klasycznymi górnikami osiąga maksimum w stosunku do wad, które wynikają z długiego czasu. Zdaniem naukowców ta przewaga istnieje niezależnie od trudności.

Wynik jest bardzo godny uwagi, ponieważ można go zastosować w praktyce. Widać tutaj dwie poważne konsekwencje:

Po pierwsze, górnik stosujący taką taktykę dyskwalifikuje się z około 80 procent bloków. Dzieje się tak, ponieważ można je znaleźć w mniej niż 16 minut. Maksymalizuje swoje szanse na sukces z pozostałymi 20 %. Powinna to być maksymalna całkowita moc wydobywcza, jaką komputery kwantowe mogą osiągnąć bez poświęcania 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. Przewaga kwantowa nie ma tutaj zastosowania. Te blockchainy są już bezpieczne kwantowo – przynajmniej w górnictwie.

Równoległość komputerów kwantowych również wydaje się ślepą uliczką. Chociaż jest to możliwe w przypadku algorytmu Grovera, poprawia ona wydajność tylko o współczynnik √m. W przypadku klasycznych komputerów element to m, jest więc kwadratowo większy. To sprawia, że wątpliwe jest, czy komputery kwantowe będą kiedykolwiek przydatne w górnictwie.

78 megahaszy

Te obliczenia eliminują znacząco niebezpieczeństwo ze strony komputerów kwantowych dla Bitcoina. Bez odpowiedzi pozostaje jednak kluczowe pytanie: co musi się stać, aby górnicy kwantowi mieli przewagę nad klasycznymi górnikami? W którym momencie taniej będzie znaleźć blok z komputerem kwantowym – jeśli w ogóle?

Decydujące w tym zakresie są dwa czynniki: koszt na iterację Grovera i stosunek liczby skrótów wymaganych dla bloku do liczby koniecznych iteracji Grovera. Naukowcy obliczają to na przykładzie typowego obecnie komputera kwantowego z „prędkością bramy” 66,7 megaherca. Bramy są operacjami kwantowymi. Naukowcy obliczyli, że taki komputer kwantowy poradziłby sobie z 224 iteracjami Grovera na sekundę.

Co to znaczy? 224 iteracje Grovera odpowiadają prędkości 78 megahashy na sekundę. To mikroskopijny ułamek hashrate Bitcoina, w rzeczywistości tylko maleńki ułamek tego, co robią współczesne układy ASIC. Śmiesznie byłoby tu wyczuć niebezpieczeństwo.

Energooszczędność przede wszystkim?

No dobrze…Ale jeśli górnicy kwantowi nie stanowią zagrożenia – czy są przynajmniej bardziej wydajni? Czy zatem może być przynajmniej stopniowa konwersja do górnictwa kwantowego? W którym momencie?

Aby być bardziej wydajnym, koszt energii iteracji Grovera powinien być co najwyżej 3,49 x 105 razy większy od kosztu klasycznego mieszania. W porównaniu do klasycznych górników, którzy mają wydajność energetyczną 10–10 juli na hash, komputer kwantowy potrzebowałby wydajności lepszej niż 3,49 x 105 x 10–10, czyli około dziesięciu μJ na iterację Grovera (lub nawet 2240 μJ na sekundę).

Wygląda na to, że to bardzo niewiele. Ale komputery kwantowe są bardzo energooszczędne. Gdy system zostanie schłodzony do 15 milikelwinów, czyli blisko zera absolutnego, bity kwantowe stają się nadprzewodnikiem: praktycznie nie potrzebują elektryczności i prawie nie wytwarzają ciepła. Obecnie chłodzenie w stosunku do mocy nadal sprawia, że komputer kwantowy jest nieekonomiczny. Wraz z postępem technologii powinno się to zmienić.