Kwantumcomputers en de Bitcoin-blockchain

Auteurs: Itan Barmes, Bram Bosch, Olaf Haalstra

De belangrijkste focus van dit artikel zal zijn om de volgende vragen te beantwoorden:

1. Hoeveel Bitcoins zouden er nu gestolen kunnen worden als er een voldoende grote kwantumcomputer beschikbaar zou zijn?
2. Wat kan men doen om het risico te verkleinen dat Bitcoins worden gestolen door een tegenstander met een kwantumcomputer?
3. Is de Bitcoin-blockchain inherent veerkrachtig tegen kwantumaanvallen, nu en in de toekomst?

Kwantumcomputers en cryptografie

Er is een grote hoeveelheid digitale inkt gemorst over hoe kwantumcomputers een existentiële bedreiging vormen voor de momenteel gebruikte asymmetrische cryptografie. We gaan hier dan ook niet in detail op in, maar lichten in dit artikel alleen de aspecten toe die relevant zijn voor de analyse.

In asymmetrische cryptografie wordt een privaat-publiek sleutelpaar op zo'n manier gegenereerd dat de twee sleutels een wiskundige relatie tussen hen hebben. Zoals de naam al doet vermoeden, wordt de privésleutel geheim gehouden, terwijl de openbare sleutel openbaar wordt gemaakt. Hierdoor kunnen individuen een digitale handtekening maken (met behulp van hun privésleutel) die kan worden geverifieerd door iedereen die de bijbehorende openbare sleutel heeft. Dit schema is heel gebruikelijk in de financiële sector om de authenticiteit en integriteit van transacties te bewijzen.

De beveiliging van asymmetrische cryptografie is gebaseerd op een wiskundig principe dat een "eenrichtingsfunctie" wordt genoemd. Dit principe schrijft voor dat de publieke sleutel gemakkelijk kan worden afgeleid van de private sleutel, maar niet andersom. Alle bekende (klassieke) algoritmes om de private key af te leiden uit de publieke sleutel vergen een astronomische hoeveelheid tijd om zo'n berekening uit te voeren en zijn daarom niet praktisch. In 1994 publiceerde de wiskundige Peter Shor echter een kwantumalgoritme dat de veiligheidsaanname van de meest voorkomende algoritmen van asymmetrische cryptografie kan doorbreken. Dit betekent dat iedereen met een voldoende grote kwantumcomputer dit algoritme kan gebruiken om een privésleutel af te leiden uit de bijbehorende openbare sleutel, en zo elke digitale handtekening te vervalsen.

Bitcoin 101

Om de impact van kwantumcomputers op Bitcoin te begrijpen, beginnen we met een korte samenvatting over hoe Bitcoin-transacties werken. Bitcoin is een gedecentraliseerd systeem voor het overdragen van waarde. In tegenstelling tot het banksysteem waar het de verantwoordelijkheid van een bank is om klanten van een bankrekening te voorzien, is een Bitcoin-gebruiker verantwoordelijk voor het genereren van zijn eigen (willekeurige) adres. Door middel van een eenvoudige procedure berekent de computer van de gebruiker een willekeurig Bitcoin-adres (gerelateerd aan de openbare sleutel) en een geheim (privésleutel) dat nodig is om transacties vanaf dit adres uit te voeren.

Het verplaatsen van Bitcoins van het ene adres naar het andere wordt een transactie genoemd. Zo'n transactie is vergelijkbaar met het overmaken van geld van de ene bankrekening naar de andere. In Bitcoin moet de afzender zijn transactie autoriseren door een digitale handtekening te verstrekken die bewijst dat hij eigenaar is van het adres waar het geld is opgeslagen. Onthoud: iemand met een werkende kwantumcomputer die uw publieke sleutel heeft, kan deze handtekening vervalsen en daarom mogelijk iemands Bitcoins uitgeven!

In het Bitcoin-netwerk wordt de beslissing welke transacties in het netwerk worden geaccepteerd uiteindelijk overgelaten aan de zogenaamde miners. Miners strijden in een race om de volgende reeks transacties te verwerken, ook wel een blok genoemd. Degene die de race wint, mag het volgende blok bouwen en krijgt daarbij nieuwe munten. Bitcoin-blokken zijn op een sequentiële manier aan elkaar gekoppeld. Samen vormen ze een keten van blokken, ook wel de "blockchain" genoemd.

De zegevierende miner die een nieuw blok aanmaakt, is vrij om elke transactie op te nemen die hij wil. Andere miners geven uiting aan hun instemming door te bouwen op blokken waar ze het mee eens zijn. In geval van onenigheid zullen ze voortbouwen op het meest recent geaccepteerde blok. Met andere woorden, als een malafide miner probeert een ongeldig blok te bouwen, zullen eerlijke miners het ongeldige blok negeren en in plaats daarvan bovenop het meest recente geldige blok bouwen.

Soorten adressen

Bitcoin-transacties maken het mogelijk om een aangepaste logica te implementeren, waardoor een groot aantal soorten financiële transacties mogelijk wordt, zoals escrow en gedeeld eigendom. Voor de toepassing van dit artikel beperken we ons echter tot eenvoudige betalingen van persoon tot persoon. Deze kunnen worden onderverdeeld in 2 categorieën, die elk op een andere manier worden beïnvloed door een kwantumcomputer.

In het eerste type dient een publieke sleutel direct als het Bitcoin-adres van de ontvanger. Een transactie naar zo'n adres wordt om voor de hand liggende redenen 'pay to public key' (p2pk) genoemd. In de begindagen van Bitcoin, in 2009, was dit het dominante adrestype. Veel van de originele munten die door Satoshi Nakamoto zelf zijn gedolven, worden nog steeds op dergelijke adressen bewaard. Een van de problemen met deze adressen is het ontbreken van een mechanisme om typefouten van adressen te detecteren (bijvoorbeeld een laatste controlesom die bijvoorbeeld wordt gebruikt in creditcardnummers). Een bijkomend probleem is dat deze adressen erg lang zijn, wat resulteert in een groter transactiebestand en dus een langere verwerkingstijd. Wat betreft de dreiging van een kwantumcomputer, is de openbare sleutel direct te verkrijgen van het adres. Aangezien alle transacties in Bitcoin openbaar zijn, kan iedereen de openbare sleutel verkrijgen van elk p2pk-adres. Een kwantumcomputer met het algoritme van Shor kan vervolgens worden gebruikt om de privésleutel uit dit adres af te leiden. Dit zou een tegenstander die een kwantumcomputer heeft, in staat stellen de munten uit te geven die het adres had.

In het tweede type transactie bestaat het adres van de ontvanger uit een hash van de openbare sleutel. Aangezien een hash een cryptografische functie in één richting is, wordt de openbare sleutel niet direct door het adres onthuld. De eerste en meest populaire implementatie hiervan heet 'pay to public key hash' (p2pkh) en is ontworpen om de twee hierboven beschreven problemen op te lossen (checksum en address length, voor een uitgebreidere uitleg verwijzen we naar deze pagina. Zoals hierboven vermeld, kan de openbare sleutel niet van het adres worden opgehaald. De publieke sleutel wordt pas onthuld op het moment dat de eigenaar een transactie wil starten. Dit betekent dat zolang er nog nooit geld is overgemaakt vanaf een p2pkh-adres, de publieke sleutel niet bekend is en de private sleutel niet kan worden afgeleid met behulp van een kwantumcomputer. Er is wel een 'maar'! Als er ooit geld wordt overgemaakt vanaf een specifiek p2pkh-adres (ongeacht het bedrag), wordt de openbare sleutel onthuld. Vanaf dat moment is dit adres gemarkeerd als "gebruikt" en zou het idealiter niet opnieuw moeten worden gebruikt om nieuwe munten te ontvangen. In feite zijn veel wallets geprogrammeerd om hergebruik van adressen zo goed mogelijk te voorkomen. Het vermijden van het hergebruik van adressen wordt beschouwd als een best practice voor Bitcoin-gebruikers, maar het zou u verbazen hoeveel mensen dit advies niet ter harte nemen. Daarover meer in het volgende hoofdstuk.

Hoeveel Bitcoins zouden er nu gestolen kunnen worden als er voldoende grote kwantumcomputers beschikbaar zouden zijn?

Stel u voor dat iemand er vandaag in slaagt om een kwantumcomputer te bouwen en daardoor in staat is om privésleutels af te leiden. Hoeveel Bitcoins zullen in gevaar zijn?

Om deze vraag te beantwoorden, hebben we de hele Bitcoin-blockchain geanalyseerd om te identificeren welke munten kwetsbaar zijn voor een aanval van een kwantumcomputer. Zoals uitgelegd in de vorige paragraaf, zijn alle munten in p2pk-adressen en hergebruikte p2pkh-adressen kwetsbaar voor een kwantumaanval. Het resultaat van onze analyse is weergegeven in de onderstaande figuur. Het toont de verdeling van Bitcoins in de verschillende adrestypen in de loop van de tijd. Zoals duidelijk te zien is in de grafiek, domineerden p2pk-adressen de Bitcoin-blockchain in het eerste jaar van zijn bestaan. Interessant is dat het aantal munten in p2pk-adressen praktisch constant is gebleven (circa 2 miljoen Bitcoins). Een redelijke veronderstelling is dat deze munten zijn gegenereerd door middel van mijnbouw en nooit zijn verplaatst van hun oorspronkelijke adres.

Toen p2pkh in 2010 werd geïntroduceerd, werd het al snel dominant. De meeste munten die sindsdien zijn gemaakt, worden op dit type adres opgeslagen. In de grafiek zien we dat het aantal Bitcoins dat is opgeslagen in hergebruikte p2pkh toeneemt van 2010 tot 2014, en sindsdien langzaam afneemt om de huidige hoeveelheid van 2,5 miljoen Bitcoins te bereiken. Dit suggereert dat mensen over het algemeen de beste praktijk volgen om geen p2pk-adres te gebruiken en p2pkh-adressen niet opnieuw te gebruiken. Toch zijn er nog steeds meer dan 4 miljoen BTC (ongeveer 25% van alle Bitcoins) die potentieel kwetsbaar zijn voor een kwantumaanval. Tegen de huidige prijs is dit meer dan 40 miljard USD!

Wat kan men doen om het risico te verkleinen dat Bitcoins worden gestolen door een tegenstander met een kwantumcomputer?

In de vorige paragraaf hebben we uitgelegd dat p2pk en hergebruikte p2pkh-adressen kwetsbaar zijn voor kwantumaanvallen. P2pkh-adressen die nog nooit zijn gebruikt om Bitcoins uit te geven, zijn echter veilig, omdat hun openbare sleutels nog niet openbaar zijn. Dit betekent dat als u uw Bitcoins overzet naar een nieuw p2pkh-adres, ze niet kwetsbaar zouden moeten zijn voor een kwantumaanval.

Het probleem met deze aanpak is dat veel eigenaren van kwetsbare Bitcoins hun privésleutels zijn kwijtgeraakt. Deze munten kunnen niet worden overgedragen en wachten op de eerste persoon die erin slaagt een voldoende grote kwantumcomputer te bouwen. Een manier om dit probleem aan te pakken, is door tot een consensus te komen binnen de Bitcoin-gemeenschap en mensen een ultimatum te stellen om hun munten naar een veilig adres te verplaatsen. Na een vooraf bepaalde periode zouden munten op onveilige adressen onbruikbaar worden (technisch gezien betekent dit dat miners transacties van deze adressen zullen negeren). Zo'n drastische stap moet zorgvuldig worden overwogen voordat deze wordt uitgevoerd, om nog maar te zwijgen van de complexiteit van het bereiken van consensus over zo'n gevoelig onderwerp.

Is de Bitcoin-blockchain inherent veerkrachtig tegen kwantumaanvallen, nu en in de toekomst?

Laten we er even van uitgaan dat alle bezitters van kwetsbare Bitcoins hun geld overmaken naar veilige adressen (iedereen die zijn privésleutel 'magisch' is kwijtgeraakt, vindt ze). Betekent dit dat de Bitcoin-blockchain niet langer kwetsbaar is voor kwantumaanvallen? Het antwoord op deze vraag is eigenlijk niet zo eenvoudig. De voorwaarde om "kwantumveilig" te zijn, is dat de openbare sleutel die aan dit adres is gekoppeld, niet openbaar is. Maar zoals we hierboven hebben uitgelegd, op het moment dat u coins wilt overmaken vanaf zo'n "veilig" adres, onthult u ook de publieke sleutel, waardoor het adres kwetsbaar wordt. Vanaf dat moment totdat uw transactie is "gedolven", krijgt een aanvaller die in het bezit is van een kwantumcomputer de kans om uw munten te stelen. Bij zo'n aanval zal de tegenstander eerst uw privésleutel afleiden van de openbare sleutel en vervolgens een concurrerende transactie naar zijn eigen adres starten. Ze zullen proberen voorrang te krijgen op de oorspronkelijke transactie door een hogere miningvergoeding aan te bieden.

In de Bitcoin-blockchain duurt het momenteel ongeveer 10 minuten voordat transacties zijn gemined (tenzij het netwerk overbelast is, wat in het verleden vaak is gebeurd). Zolang een kwantumcomputer er langer over doet om de privésleutel van een specifieke publieke sleutel af te leiden, zou het netwerk veilig moeten zijn tegen een kwantumaanval. De huidige wetenschappelijke schattingen voorspellen dat een kwantumcomputer er ongeveer 8 uur over zal doen om een RSA-sleutel te kraken, en sommige specifieke berekeningen voorspellen dat een Bitcoin-handtekening binnen 30 minuten kan worden gehackt. Dit betekent dat Bitcoin in principe bestand moet zijn tegen kwantumaanvallen (zolang u adressen niet hergebruikt). Omdat het vakgebied van kwantumcomputers echter nog in de kinderschoenen staat, is het onduidelijk hoe snel zo'n kwantumcomputer in de toekomst zal worden. Als een kwantumcomputer ooit dichter bij de 10 minuten komt om een privésleutel af te leiden uit zijn openbare sleutel, dan zal de Bitcoin-blockchain inherent kapot zijn.

Afsluitende opmerkingen

Kwantumcomputers vormen een serieuze uitdaging voor de veiligheid van de Bitcoin-blockchain. Momenteel is ongeveer 25% van de Bitcoins in omloop kwetsbaar voor een kwantumaanval. Als u Bitcoins op een kwetsbaar adres heeft en denkt dat de vooruitgang in kwantumcomputing geavanceerder is dan algemeen bekend, dan moet u uw munten waarschijnlijk overzetten naar een nieuw p2pkh-adres (vergeet niet om een veilige back-up van uw privésleutel te maken).

In het geval dat uw eigen Bitcoins veilig zijn in een nieuw p2pkh-adres, kunt u nog steeds worden beïnvloed als veel mensen niet dezelfde beschermingsmaatregelen zullen (of kunnen) nemen. In een situatie waarin een groot aantal Bitcoins wordt gestolen, zal de prijs hoogstwaarschijnlijk crashen en zal het vertrouwen in de technologie verloren gaan.

Zelfs als iedereen dezelfde beschermingsmaatregelen neemt, kunnen kwantumcomputers uiteindelijk zo snel worden dat ze het Bitcoin-transactieproces zullen ondermijnen. In dit geval zal de beveiliging van de Bitcoin-blockchain fundamenteel worden verbroken. De enige oplossing in dit geval is om over te stappen op een nieuw type cryptografie, 'post-kwantumcryptografie' genaamd, dat wordt beschouwd als inherent resistent tegen kwantumaanvallen. Dit soort algoritmen vormen andere uitdagingen voor de bruikbaarheid van blockchains en worden onderzocht door cryptografen over de hele wereld. We verwachten dat toekomstig onderzoek naar post-kwantumcryptografie uiteindelijk de nodige verandering zal brengen om robuuste en toekomstbestendige blockchain-toepassingen te bouwen.