Quantumcomputers worden gezien als een bedreiging voor Bitcoin. Twee wetenschappers hebben de wiskunde gedaan: Hebben quantummijnwerkers echt een voordeel ten opzichte van klassieke mijnwerkers? En zo ja – vormt dit een bedreiging voor Bitcoin?
Bitcoin en quantumcomputers: Dit onderwerp is al een paar keer aan de orde geweest, en eigenlijk heeft het Bitcoin vanaf het begin achtervolgd.
Bedreigen kwantumcomputers de Bitcoin? Zal er op een dag een kwantumcomputer komen die met zijn superieure rekenkracht alle portemonnees leeghaalt en alle Bitcoins wegmijnt? Sommigen zeggen ja, op de lange duur kan dit gebeuren, anderen zeggen nee, er zal voor een zeer lange tijd geen grammetje zorg zijn.
We hebben al geschreven over kwantumcomputers, Bitcoin en het ECDSA-handtekeningalgoritme. Vandaag bekijken we een paper waarin twee Canadese professoren computerwetenschappen analyseren of quantum miners een gevaar vormen, en zo ja, wat voor gevaar.
Het onderwerp is niet triviaal, zeker niet voor wiskundige leken. Maar omdat het spannend is voor iedereen die geïnteresseerd is in Bitcoin en de toekomst van computers, zal ik proberen het stuk zo eenvoudig mogelijk te presenteren.
Het basiskader waarop de auteurs hun vraag bouwen is de volgende theorie: Als een mijnwerker te machtig wordt, kan hij het netwerk bedreigen. Als hij een absolute meerderheid heeft, kan hij 51 procent aanvallen, maar zelfs daaronder kan hij schade aanrichten door “agressieve” of “egoïstische” mijnbouw.
Wat nu als een mijnwerker door quantumcomputing zo’n voordeel behaalt dat zijn aandeel in de hashrate onevenredig toeneemt?
We hebben het hier al eerder over gehad, en het is nogal triviaal: technologische vooruitgang versnelt mijnbouw. Het gebeurt niet geleidelijk, maar vaak met sprongen. Vanaf 2011 verdringen grafische kaarten de hoofdprocessoren, vanaf 2013 verdringen Asics de grafische kaarten. Op dergelijke momenten neemt de efficiëntie niet langer lineair toe, maar kwadratisch of exponentieel. Nu Ascis het potentieel van klassieke chips grotendeels lijkt te hebben uitgeput, zouden kwantumcomputers de volgende grote sprong voorwaarts kunnen inluiden.
Op zich hoeft dit geen probleem te zijn. De speltheoretische mechanismen van Bitcoin motiveren rationele spelers om eerlijk te zijn en elkaar in toom te houden. Toch kan een technologische sprong hobbelig zijn, en misschien wordt het een poort voor vijandige machten die irrationeel handelen om Bitcoin schade toe te brengen.
Daarom is het zinvol te weten wanneer het zou kunnen gebeuren. Wat moet er gebeuren voordat kwantumcomputers de klassieke Asics kunnen verdringen bij het Bitcoin-mijnen?
Ongesorteerde databases doorzoeken
Je kunt bitcoin mijnen zien als mijnwerkers die veel genereren met hun rekenkracht. Ze genereren willekeurige hashes, en als een hash aan bepaalde zeer zeldzame eisen voldoet, vindt de miner een blok. Je zou het ook een brute kracht aanval op de SHA256 hash functie kunnen noemen.
De twee professoren zeggen het zo: “De miners proberen een cryptografische hashfunctie gedeeltelijk om te keren”. Deze “gedeeltelijke inversie van een hashfunctie” is “equivalent met het zoeken naar een gemarkeerd item in een ongeordende lijst van items (een ongestructureerde zoekopdracht)”. Klinkt als een klein punt, maar het is fundamenteel voor al het andere.
Want er is niet veel waarvan bewezen is dat kwantumcomputers het kunnen. Een van de weinige taken waarbij kwantumcomputers het beter doen dan klassieke computers is het zoeken naar een bepaald item in een ongeordende lijst.
Een klassieke computer moet bij het doorzoeken van een ongesorteerde database – of bij een brute kracht aanval – één invoer tegelijk doorwerken. Je kunt het zien als een tweedimensionale wijzer die van item naar item beweegt. Als het de helft van de inzendingen heeft gezien, is de kans op een hit meer dan 50%. Een klassieke computer heeft dus gemiddeld N/2 bewerkingen nodig, waarbij N het totale aantal mogelijke items is.
Kwantumcomputers hebben nu een voordeel: een qubit kan tegelijkertijd 0 en 1 zijn, waardoor een reeks qubits tegelijkertijd alle denkbare varianten kan voorstellen. Je kunt het zien als een wijzer die wijst in N dimensies. Als de qubits in deze “superpositie” zijn, zit de oplossing er al in. Het is daar.
Maar zodra je meet, vernietig je de oplossing. Dit is het beroemde kwantumdilemma: als je meet, dwing je de kwanta om een bepaalde maar willekeurige toestand aan te nemen. Dus de kwantumcomputer kent de oplossing, maar in een tragische draai, devalueert hij het als je het gaat halen.
Grover’s algoritme: kwadraat praktisch versneld
Dit is waar Grover’s algoritme om de hoek komt kijken. Het algoritme van Grover, dat in 1996 door Lov Grover is ontwikkeld, is een methode om het resultaat te controleren. Door verschillende “quantum gates” te combineren – dit zijn de bewerkingen in quantumcomputers – detecteren de qubits valse resultaten en onderdrukken deze. Met elke herhaling – de zogenaamde Grover-iteratie – neemt de kans op het juiste resultaat dus toe.
De hele zaak is waanzinnig ingewikkeld in detail. Maar één ding is duidelijk: met het juiste aantal iteraties kan het Grover-algoritme dergelijke zoekacties drastisch versnellen. Want om een item in een ongesorteerde lijst te vinden, heeft Grover maar √n poging nodig. Het is dus bijna kwadratisch sneller.
Twee voorbeelden: Als er 4 items zijn, hebben klassieke computers en quantumcomputers 2 pogingen nodig. Met 5.198.400 items daarentegen is een quantumcomputer na 2280 pogingen gevonden, terwijl een conventionele computer meer dan twee miljoen keer moet werken.
Vooral bij taken met een extreme moeilijkheidsgraad of een extreem hoge N, zoals bitcoin mining, is dit verschil – het zogenaamde quantumvoordeel – enorm. Het is een van die sprongen die hele ecosystemen doen schudden. Tenminste in theorie.
Het kwantumvoordeel smelt
In de praktijk stuit een kwantumminer op een heel specifiek probleem: hij kan alleen een blok vinden als hij het resultaat meet – en dus het proces afbreekt. Hij moet dus op voorhand weten hoeveel iteraties hij zal uitvoeren.
De vraag is lastig. Omdat zowel te veel als te weinig nadelen hebben. Meer iteraties verhogen de kans op het vinden van een correcte oplossing – maar ook het gevaar dat een andere miner sneller is. Minder iteraties daarentegen verlagen de kans op een geldig resultaat – en dus het kwantumvoordeel.
Als een kwantumcomputer oneindig veel tijd had, zou hij het kwantumvoordeel volledig kunnen benutten. Maar dit is niet mogelijk met mijnbouw. Het moet een compromis vinden tussen te weinig en te veel iteraties.
Om de optimale afweging te berekenen, vormden de onderzoekers een Markov-keten met de mogelijke scenario’s. Een Markovketen is een wiskundige formulering van opeenvolgingen van mogelijke, gewoonlijk willekeurige of gedeeltelijk willekeurige gebeurtenissen. Zo’n keten geeft aan welke paden door het oerwoud van waarschijnlijkheden gemiddeld tot de beste resultaten leiden: welke instelling van het Grover-algoritme ideaal zou zijn.
Verbazingwekkend, dit zou 16 minuten zijn.
Twee opmerkelijke bevindingen
Als een quantumminer 16 minuten wacht om het resultaat van Grover’s algoritme te lezen, bereikt zijn voordeel ten opzichte van klassieke miners het maximum in verhouding tot de nadelen die voortvloeien uit de lange tijdspanne. Volgens de wetenschappers bestaat dit voordeel ongeacht de moeilijkheidsgraad.
Het resultaat is zeer opmerkelijk omdat het in de praktijk kan worden gebracht. Hier ziet men twee ernstige gevolgen:
Ten eerste diskwalificeert de mijnwerker zich met een dergelijke tactiek voor ongeveer 80 procent van de blokken. Omdat deze gevonden zijn in minder dan 16 minuten. Hij maximaliseert zijn kansen op succes met de resterende 20 procent. Dit zou het maximale totale ontginningsvermogen moeten zijn dat quantumcomputers kunnen bereiken zonder aan efficiëntie in te boeten.
Ten tweede, de meeste cryptocurrencies hebben kortere intervallen tussen blokken. Dogecoin en Litecoin hebben ongeveer een paar minuten, Ethereum en Ripple slechts een paar seconden. Quantum miners krijgen een bloedneus met deze blockchains omdat het quantum voordeel hier niet van toepassing is. Ze zijn al quantum-veilig – tenminste in de mijnbouw.
Ook de parallellisering van kwantumcomputers lijkt een doodlopende weg te zijn. Hoewel dit mogelijk is met het Grover-algoritme, verbetert dit de prestaties slechts met een factor √m volgens de berekeningen van de auteurs. Bij klassieke computers is de factor m, d.w.z. dat hij kwadratisch groter is. Dit maakt het twijfelachtig of kwantumcomputers ooit relevant zullen zijn voor mijnbouw.
78 Megahashes
Deze berekeningen maken het gevaar van kwantumcomputers aanzienlijk kleiner. Maar de cruciale vraag is nog steeds niet beantwoord: Wat moet er gebeuren opdat quantummijnwerkers daadwerkelijk een voordeel hebben ten opzichte van klassieke mijnwerkers? Op welk punt zal het goedkoper worden om een blok met een quantumcomputer te vinden – als dat al ooit gebeurt?
Twee factoren zijn hiervoor bepalend: de kosten per grover iteratie en de verhouding tussen het aantal hashes dat nodig is voor een blok en het aantal grover iteraties dat nodig is. De auteurs berekenen dit aan de hand van het voorbeeld van een thans gangbare quantumcomputer met een “poortsnelheid” van 66,7 megahertz. De poorten zijn de kwantumbewerkingen. De wetenschappers hebben berekend dat deze quantumcomputer 224 grover iteraties per seconde zou aankunnen.
Wat betekent dat? 224 Grover-iteraties komen overeen met een hash-snelheid van 78 megahashes per seconde. Dat is een absoluut microscopisch klein deel van de Bitcoin-hashrate, ja, slechts een minieme fractie van wat moderne Asics bereiken. Het zou belachelijk zijn om hier gevaar te ruiken.
Maar als quantum miners geen bedreiging vormen, zijn ze dan wel efficiënter? Dus, kan er, tenminste geleidelijk, een omschakeling komen naar quantum mijnbouw? En op welk punt?
Om efficiënter te zijn, mogen de energiekosten van een Grover-iteratie hoogstens 3,49 x 105 maal zo hoog zijn als de kosten van een klassieke hash. Vergeleken met klassieke miners, die een energie-efficiëntie hebben van 10-10 Jules per hash, zou een quantumcomputer een efficiëntie nodig hebben die beter is dan 3,49 x 105 x 10-10, of ongeveer 10 μJ per Grover iteratie. Of 2240 μJ per seconde.
Dat klinkt extreem laag. Maar kwantumcomputers zijn zeer energie-efficiënt. Zodra het systeem wordt afgekoeld tot 15 millikalvin, d.w.z. dicht bij het absolute nulpunt, worden de kwantumbits een supergeleider: zij hebben vrijwel geen elektriciteit nodig en produceren vrijwel geen warmte. Op dit moment is een quantumcomputer nog oneconomisch door de verhouding tussen koeling en stroomverbruik. Maar dit zal waarschijnlijk veranderen naarmate de technologie voortschrijdt.
Al met al kunnen wij als Bitcoiners dus rustig en wat wijzer slapen en zonder angst dromen van een toekomst van kwantumcomputers.