Ist Googles Quantencomputer eine Gefahr für den Bitcoin?

Ping Pong Balls. Bild von Dean Hochmann via flickr.com. Lizenz: Creative Commons

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.

 

About Christoph Bergmann (1086 Articles)
Das Bitcoinblog wird von bitcoin.de gesponsort, ist inhaltlich aber unabhängig und gibt die Meinung des Redakteurs Christoph Bergmann wieder. Wenn Ihnen das Blog gefällt, freuen wir uns über Spenden an 1BvayiASVCmGmg4WUJmyRHoNevWWo5snqC. Jeder Satoshi wird dazu verwendet, um das Blog besser zu machen. Weitere Infos, wie Sie uns unterstützen können, finden Sie HIER. Gastbeiträge sind ebenfalls willkommen. Meinen öffentlichen PGP-Schlüssel sowie den Bitmessage-Schlüssel finden Sie HIER

15 Comments on Ist Googles Quantencomputer eine Gefahr für den Bitcoin?

  1. Carsten Otto // 17. December 2015 at 8:53 // Reply

    Das mit den drei Zuständen ist leider einfach nur Quark. Man erhöht nicht einfach von 2 auf 3 bits, das kann man auch wunderbar mit existierender Technik machen. Qubits prinzipiell unendlich viele Zustände gleichzeitig, und durch Quantenverschränkung kann man diese Zustände dann nach und nach auf etwas zurechtstutzen, was einem Ergebnis entspricht.

    Der eigentliche Vorteil, wenn auch sowohl theoretisch als auch praktisch schwer umsetzbar, ist, dass man mit Quantencomputern Algorithmen die normalerweise exponentielle Laufzeit haben, in einer schnelleren Laufzeitklasse (linear) berechnen kann. Anders gesagt werden parallel exponentiell viele Zustände durchgespielt, was ein klassischer Computer nacheinander machen müsste.

    Das Thema ist wirklich komplex, das ist aber keine Entschuldigung dafür falsche Tatsachen zu verbreiten.

    • Wie man an diesem Beitrag gut lesen kann sind Intelligenz und Klugheit zweierlei paar Schuhe. Klug wäre es gewesen, sein Wissen in höflicher Form zu schreiben, denn es kann sicherlich nicht klug sein, Jemanden der in guter Absicht und ohne Selbstzweck handelt, derartige Unterstellungen zu machen.

    • Sorry, ich bin wie gesagt kein Experte und auch kein Techniker. Daher vielen Dank für den aufschlussreichen Kommentar. Ich werde den Artikel im Lauf des Tages noch dementsprechend umbauen. Falsche Tatsachen sollten tatsächlich nicht verbreitet werden.

      Können wir darüber im Lauf des Tages noch mailen, Carsten?

  2. T. Büchling // 17. December 2015 at 10:46 // Reply

    genau, das mit den 3 Zuständen ist falsch. Der entscheidende Vorteil ist die Verschränkung von mehreren qbits..( bei d-wave sind jeweils 8 bits verschränkt – mehrere 8er gruppen arbeiten dann nicht zusammen, höchstens parallel.. man kann also nur 8bit probleme lösen.. ) eine solche gruppe befindet sich in allen 256 zuständen gleichzeitig. man kann nun eine Rechenoperation wie addition auf dieses “gatter” anwenden – die addition findet auch in allen zusänden gleichzeitig statt. die laufzeit sinkt daher von n^2 auf n.. möchte man nun bitcoins erzeugen, muss man eine 1024 bit ( bin mir unsicher, aber hohe zahl ) hashoperation durchführen. man benötigt also 1024 statt 8 qubits.. bis dahin ist es noch ein ewig langer weg! denn jedes zusätzliche der 1016 bits wird eine weitere herausforderung! aber wenn man einen solchen computer dann hat, kann man mit einer(!) hashoperation alle möglichen hashes gleichzeitig berechnen.. und hat somit definitiv einen block gefunden.. ist aber auch nicht weiter dramatisch.. denn wenn dann ein zweiter und dritter supercomputer gebaut werden, ist das netz wieder dezentral ^^

  3. wenn eine beliebige Verschlüsselung mit einem TOP10 Supercomputer innerhalb von ca 100 Jahren knackbar ist, sollte diese Verschlüsselungstechnik umgehend abgeschafft werden, oder so modifiziert werden , dass es schwerer wird Sie zu knacken.

    PS: Nach Moor´schen Gesetz: Nach 2 Jahren dauerts nur noch 50 Jahre, nach 4 noch 25, nach 6 noch 12, nach 8 noch 6, nach 10 Jahren noch 3 Jahre bis der Code geknackt ist,

    das heisst die aktuell 100 Jahre sind , wenn Moor rechtbehält nämlich dann nur noch reelle lächerliche 13 Jahre

    mfg

  4. “Wie genau ein Quantencomputer funktioniert, weiß nur eine kleine erlauchte Anzahl von Physikern und Informatikern. Das Kernprinzip scheint in den verrückten Besonderheiten der Quantenwelt zu liegen, in der Teilchen Dinge machen, die eigentlich unmöglich sind: Sie erfahren mit Überlichtgeschwindigkeit, was ein Partnerteilchen macht, tunneln andere Teilchen, teleportieren sich woanders hin und können an zwei Positionen gleichzeitig sein. Während ein herkömmliches “bit” nur die Zustände 0 oder 1 kennt, kann ein “qbit” – ein Quantenbit – kann noch einen dritten Zustand haben – nämlich beides.

    Dass all das revolutionär für die Computerarchitektur ist, sollte sich von selbst verstehen. Wenn ein bit drei anstatt zwei mögliche Zustände hat, führt dies zu einer exponentiellen Erhöhung der Rechenleistung. Während eine Folge aus 10 Bitzeichen – z. B. 0001010011 – 2¹⁰ – also 1024 Kombinationsmöglichkeiten hat, hätte eine ebensolange Zeichenfolge aus qbits 3¹⁰ – also 59.049 Kombinationsmöglichkeiten. Solche Steigerungen können auch kryptographische Berechnungen und das Knacken von Passwörtern nützlich sein.”

    Diese beiden Absätze sind mir besonders aufgestoßen 😉
    Qbits können nicht drei Zustände haben, sondern eine beliebige Überlagerung von den Zuständen 0 und 1. Superposition nennt man das im Fachjargon. Solange das Qbit in der Superposition ist, kann man mit der Überlagerung rechnen. Sobald man es jedoch misst um zu schauen, wie der Wert ist, kollabiert die Superposition in den Zustand 0 oder 1. Die Wahrscheinlichkeit in welchen Zustand es kollabiert hängt von der Superposition ab. Wenn es 70% im Zustand 0 ist und 30% im Zustand 1, dann kollabiert es bei einer Messung mit 70% Wahrscheinlichkeit in den Zustand 0, etc.

    Es gibt auch ternäre (statt binäre) Systeme mit Trits, statt Bits. Witzigerweise hatten die Sowjets sowas auf ihren ersten Computern.

    “Der Shor-Algorithmus ist eine quantenbasierte Methode, um Primzahlen zu zerlegen,”
    Ich glaub hier meinst du schon das richtige. Aber die Primzahl wird nicht zerlegt, sondern eine Zahl wird in ihre Primfaktoren zerlegt. Ich zerlege eine 10 zum Beispiel in 5*2.

    “Das bedeutet, der Quantencomputer löst nicht ein spezielles Problem schneller, sondern er löst ein spezielles Problem mit einem speziellen Algorithmus schneller.”
    Genaugenommen gibt es keinen klassischen (nichtquanten)-Algorithmus für die Primzahlzerlegung, der schneller ist als alle Zahlen auszuprobieren (für Zahlen, die keine spezielle Form haben). Ebenso beim diskreten Logarithmus (bis auf ein paar Spezialfälle). Der Shor-algorithmus kann das erstmals. Es gibt noch andere Quantenalgorithmen, die kein klassisches Äquivalent haben. Zum Beispiel hast du eine unsortierte Liste mit n Elementen und willst schauen ob ein bestimmtes Element drin ist. Dazu muss man klassisch jedes Element der Liste anschauen und vergleichen. Mit Grovers-Algorithmus geht es schneller, weil man ein Qbit als Superposition von den Dingen in der Liste darstellen kann und dann darauf rechnen.

    “Diese werden wohl vor allem im Machine-Learning, in der Simulation von Raketenstarts oder Gehirnzellen eingesetzt werden, aber es ist durchaus denkbar, dass sie auch dazu genutzt werden, um kryptografische Verfahren zu brechen.”
    Es gibt ein ganzes Feld, das Post-Quantenkryptographie heißt. Heutige Sicherheitsbeweise basieren auf Reduktionen. Dann kommen Aussagen raus wie “Man kann diese Signatur fälschen, wenn man den diskreten logarithmus berechnen kann”. Momentan geht das nicht und deswegen ist das Signaturverfahren als sicher angenommen. Allerdings ist das mit Quantencomputern dahin.

    Mit Quantencomputern ist RSA dahin, ECDSA auch. Für Hashfunktionen ist mir kein Angriff bekannt.

  5. Also ohne das ich das jetzt selber fachlich beurteilen könnte, möchte ich aber dennoch den Talk von Rüdiger Weis vom CCC einwerfen, der klipp und klar sagt “Bitcoin überlebt Quanten-Computer”. Die Stelle im Talk kann man hier ansehen: https://youtu.be/PoNHNLzSI0o?t=28m11s

  6. @Christoph
    “Tatsächlich können qbits wohl unendlich viele Zustände gleichzeitig
    annehmen.”
    Nja. Schon besser. Es ist immer noch nur ein Zustand, aber der ist
    halt nicht mehr binär (Null oder Eins). Sonern stetig, irgendeine
    reelle Zahl zwischen null und eins.
    Aber wie schon gesagt: Man kann damit rechnen, aber sobald man
    versucht es auszulesen wird es wieder binär. So wie die Geschichte mit
    Schrödingers Katze.

    @T. Büchling

    Der entscheidende Vorteil ist die Verschränkung von mehreren qbits..(
    bei d-wave sind jeweils 8 bits verschränkt – mehrere 8er gruppen
    arbeiten dann nicht zusammen, höchstens parallel.. man kann also nur
    8bit probleme lösen.. ) eine solche gruppe befindet sich in allen 256
    zuständen gleichzeitig. man kann nun eine Rechenoperation wie addition
    auf dieses “gatter” anwenden – die addition findet auch in allen
    zusänden gleichzeitig statt. die laufzeit sinkt daher von n^2 auf n..
    möchte man nun bitcoins erzeugen, muss man eine 1024 bit ( bin mir
    unsicher, aber hohe zahl ) hashoperation durchführen. man benötigt
    also 1024 statt 8 qubits.. bis dahin ist es noch ein ewig langer weg!
    denn jedes zusätzliche der 1016 bits wird eine weitere
    herausforderung! aber wenn man einen solchen computer dann hat, kann
    man mit einer(!) hashoperation alle möglichen hashes gleichzeitig
    berechnen..”

    Nein.
    Die Hashes bei Bitcoin sind 256 Bit lang. Längere Bitstrings sind
    eher für asymmetrische Kryptographie.
    Man kann auch nicht “alle möglichen Hashes gleichzeitig berechnen”.
    Bzw. geht das schon, aber man kann das Ergebnis nicht auslesen.
    Grovers Algorithmus beschleunigt das Durchsuchen von Listen und damit
    das finden eines gültigen Urbilds eines Hashes, das für einen neuen
    Block benötigt wird. Komplexitätstheoretisch ist ie LAufzeit nur noch
    wurzel(n), statt n Operationen.
    Allerdings müsste sich der Difficulty-Parameter um Blöcke zu erzeugen
    schnell anpassen.

    @wini242
    Der Signaturalgorithmus müsste getauscht werden, da ECDSA auf dem
    diskreten Logarithmusproblem für elliptische Kurven basiert. Ansonsten
    ist alles in Ordnung.

  7. Coole Sache, dass Christoph diesen Blog verfasst hat, auch wenn einige fachliche Ungereimtheiten enthalten sind. Fakt ist, dass dadurch weiterer toller Input zum Thema im Kommentarbereich entstanden ist. Einen Dank an die Kommentatoren, die ihr Fachwissen mit uns Lesern teilen.

  8. Super interessant! Vielen Dank für den Artikel und an alle, die ihn verbessert haben!

  9. hans klarsicht // 21. December 2015 at 18:20 // Reply

    naja, niemand garantiert uns, dass google und die nasa nicht doch schon etwas weiter sind als sie angeben. vielleicht haben sie sogar exklusivverträge mit NSA und co. und müssen für die nationale sicherheit die schnauze halten und in der zwischenzeit knacken sie uns alles weg von dem wir keinen dunst haben.

  10. sollte ausreichen, um’s einigermaßen zu verstehen 😉

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s