Google hat kürzlich demonstriert, dass ein Quantencomputer manche Aufgaben bis zu 100 Millionen Mal schneller erledigt als ein herkömmlicher PC. Damit könnten, theoretisch, viele Verschlüsselungsverfahren hinfällig werden. Trifft dies auch für den Bitcoin zu?
Google hat 2013 für 10 Millionen Dollar den ersten kommerziellen Quantencomputer von der kanadischen Firma D-Wave gekauft. Gemeinsam mit der NASA hat Google in den vergangenen zwei Jahren erforscht und getestet, ob und wie sich ein Quantencomputer verwenden lässt. Seit kurzem liegen erste, spektakuläre Ergebnisse dieser Forschungen vor.
Quantencomputer gelten als einer der Hoffnungsträger für die künftige Entwicklung von Computern. Die bisherige Architektur von Chips stößt langsam an ihre Wachstumsgrenzen, da der physikalische Raum, um Transistoren zusammenzukleben, bald vollständig genutzt wird. Um auch in Zukunft die Gültigkeit des Mooreschen Gesetzes zu erhalten, das besagt, dass sich die Leistungsfähigkeit von Prozessoren alle 12 bis 24 Monate verdoppelt, erforschen Wissenschaftler rund um die Welt neue, innovative Architekturprinzipien für Computer bzw. Prozessoren. Eines davon ist der Quantencomputer.
Wie genau ein Quantencomputer funktioniert, weiß nur eine kleine erlauchte Anzahl von Physikern und Informatikern. Üblicherweise wird ein Quantencomputer durch den Vergleich herkömmlicher Bits und Quantenbits (qbits) beschrieben: Während die normalen Bits nur die Zustände 0 oder 1 kennen, kann ein Quantenbit noch einen dritten Zustand annehmen – nämlich sowohl 0 als auch 1. Eigentlich habe ich dies auch so beschrieben. Dies wurde aber von den Lesern in den Kommentaren einstimmig für falsch befunden.
Tatsächlich können qbits wohl unendlich viele Zustände gleichzeitig annehmen. Ein Quantencomputer kann so parallel exponentiell viele Zustände durchspielen, was ein normaler Computer nacheinander machen müsste. Dadurch können Algorithmen, die gewöhnlich exponentielle Laufzeiten haben – beispielsweise manche kryptographische Verfahren – in eine lineare Laufzeit umgemünzt werden.
Allerdings stehen Quantencomputer noch ganz am Anfang ihrer Entwicklung. Sie werden zwar seit mehrere Jahrzehnten vorausgesagt, sind aber bislang nur im Ansatz realisiert. Die Experimente von Google und der NASA mit dem D-Wave Quantencomputer dürften ein kleiner Meilenstein in der Geschichte des Quentenrechnens darstellen. Google hat sich ein Modell des kommerziellen Quantencomputers von D-Wave, der aus etwa 1.000 qbits, geclustert in Pakete von jeweils 8 verschränkten qbits, besteht, gekauft und zwei Jahre lang getestet.
Hartmut Neven, Leiter des Quantum AI Lab von Google, berichtete, dass man Beweise dafür habe, dass der Quantencomputer wirklich Quanten nutzt – und in einem Vergleichstest bei einer sehr speziellen Aufgabe 100 Millionen Mal schneller war als ein herkömmlicher Rechnern. Der Quantencomputer von D-Wave könne manche Probleme, für die normale Computer 10.000 Jahre brauchen, in einer einzigen Sekunde lösen.
Bedeutet das jetzt, dass kryptographische Verfahren, wie sie im Bitcoin verwendet werden, doch geknackt werden können? Bislang ging man davon aus, dass sowohl der für das Mining benutzte SHA-256-Algorithmus als auch der ECDSA, mit dem Transaktionen signiert werden, prinzipiell ewig hält. Von beiden Algorithmen ist keine Schwäche und keine Backdoor bekannt; um sie durch Brute Force, also zufälliges Raten, zu brechen, bräuchte selbst ein gigantischer Supercomputer Jahrtausende oder gar Jahrmillionen.
Kryptographische Algorithmen, die auf der Zerlegung von Zahlen in Primfaktioren und diskreten Logarithmen basieren, wie etwa die RSA-Verschlüsselung oder auch ECDSA, könnten allerdings durch Quantencomputer mit dem Shor-Algorithmus gelöst werden. Der Shor-Algorithmus ist eine quantenbasierte Methode, um Zahlen schneller in Primfaktoren zu zerlegen. Üblicherweise müssen Computer hierfür jede Zahl raten; der Shor-Algorithmus kann diesen Weg beschleunigen. 2001 wurde er erstmals von IBM auf einem Quantencomputer eingesetzt, doch es war lediglich möglich, die Zahl 15 zu faktorisieren. Zehn Jahre später gelang die Faktorisierung der Zahl 21, was zeigt, dass der technologische Fortschritt beruhigend langsam ist.
Auf Hash-Funktionen wie SHA-256, das beim Bitcoin-Mining eingesetzt wird, haben die bekannten Quantenalgorithmen keinen Einfluss. Ein Leser meinte jedoch, dass die Verschränkung der Quantenbits in Zukunft einen Angriff auslösen könnte. Bei Googles D-Wave Quantencomputer werden 8 qbits verschränkt, womit sich die Gruppe in 256 Zuständen gleichzeitig befindet. Wenn es gelingen würde, 256 qbits zu verschränken, könnte man mit einer Hashfunktion gleichzeitig sämtliches Hashes des SHA-256-Algorithmus berechnen. Ein Miner mit einem solchen Quantencomputer würde damit mit jeder Operation einen Block finden. Interessant wäre es, was passiert, wenn es zwei Miner gibt, die einen solchen Quantencomputer verwenden.
Aber auch Googles Quantencomputer ist noch weit davon entfernt, tatsächlich eine Gefahr darzustellen. D-Wave verschränkt lediglich 8 qbits. Das Hinzufügen von jedem weiteren qbit ist eine enorme Herausforderung. Und sollte es einmal soweit kommen, ließe sich SHA-256 problemlos durch SHA-512 ersetzen, womit weitere wertvolle Zeit gewonnen wäre, um einen quantensicheren Algorithmus zu implementieren.
Trotz allem stellt der Test von Google einen wichtigen Zwischenschritt dar, da er beweist, dass Quantencomputer in der Lage sind, gewisse Algorithmen wesentlich schneller abzuarbeiten als gewöhnliche Computer. Es dürfte nur eine Frage der Zeit sein, bis Quantencomputer ein weites Spektrum von Algorithmen verarbeiten und auch mehr als 8 qbits verschränken können, auch wenn Zeit hier eher Jahrzehnte als Jahre meint. Solche Quantencomputer sowie bereits bekannte oder noch zu entwickelnde Quanten-Algorithmen können theoretisch in der Lage sein, die kryptographischen Algorithmen des Bitcoins zu brechen.
Allerdings sollte es problemlos möglich sein, die Algorithmen im Bitcoin zu ändern, wenn sich eine Gefahr durch Quantencomputer anbahnt. Bereits die Erhöhung der Bits von SHA würde ausreichen, um einige Jahre Zeit zu gewinnen, in denen man quantensichere Algorithmen – die bereits in der Entwicklung bzw. entwickelt sind – zu implementieren. Sollte es einmal soweit kommen, dass RSA, SHA-256, ECDSA und weitere Algorithmen von Quanten-Computern geknackt werden, dann wird die Welt als ganzes, nicht nur der Bitcoin, sich relativ schnell auf die neuen Gegebenheit einstellen müssen.
—
Anmerkung: Der Autor ist leider weder ein Experte für Computerwissenschaften noch für Quantenphysik und noch weniger für Quantencomputer. Dank der Kommentare der Leser hat dieser Artikel jedoch erheblich an Qualität gewonnen. Ich hoffe, die aktuelle Version wird den komplexen Tatsachen wenigstens einigermaßen gerecht.