Zur Hauptseite  ..\..\..\                                                                       Zur Themenliste ..\..\                                                         Zur Bitcoin Übersicht ..\


Technische Angriffsmöglichkeiten auf Bitcoin

Können Quantencomputer Bitcoin brechen?



In "normalen" Computern werden Algorithmen Schritt für Schritt abgearbeitet. Je schwieriger die Aufgabe, und je grösser die Zahlen, desto grösser ist der Algorithmus, und desto länger braucht der Computer.
Kryptographische Aufgaben sind derart schwierig, und die verwendeten Zahlen so unermesslich gross, dass selbst mit aller irdischen Rechenkapazität niemals auch nur ein einziger Key aus einer Adresse berechnet werden kann. Möglichkeiten in der Art, dass Computer in 100 Jahren möglicherweise 1 Million mal so schnell sein werden wie heute, ändern nichts daran, das Problem wäre in 100 Jahren gleichermassen unlösbar.
Weiter oben wurde bereits die trivial anmutende Feststellung gemacht, dass der Kern des Problems, bzw. die Grenze der heute verfügbaren Computertechnik darin besteht, dass mit wachsender Komplexität der Aufgabe die Zeitdauer für ihre Lösung ansteigt.
Der entscheidende Punkt ist, dass Quantencomputer genau dieses Problem nicht haben !
Um Bitcoin zu brechen, bringt die Erhöhung der Arbeitsgeschwindigkeit vorhandener Technik also nichts. Man braucht daher einen vollkommenen anderen Ansatz.

Was sind Quantencomputer?

Quantencomputer haben mit heutigen Computern nicht das Geringste zu tun. Es sind vollkommen andersartige Geräte, und zwar bezüglich
"Normale" Computer wurden erfunden, um Aufgaben schneller lösen zu können. Ob es sich dabei um echte Rechenaufgaben, oder Datenverarbeitung im Allgemeinen handelt, ist nebensächlich.

Bei Quantencomputern ist die Denkrichtung anders herum:
"In der Physik wurden sehr interessante Effekte entdeckt. Mit denen kann man ganz tolle Sachen machen. Die Frage ist, wie kann man das nutzbringend einsetzen?"

Das theoretische Modell "Quantencomputer", insbesondere einige darauf ausführbare Algorithmen, existiert spätestens seit den 1980er Jahren, also lange bevor das erste funktionierende Gerät gebaut wurde.
Bereits vor dem ersten funktionierenden Gerät wurden schon Algorithmen dafür entwickelt, mit denen man aktuelle Probleme schneller lösen kann als mit "normalen" Computern. 


Während bei "normalen" Computern jedes Bit lediglich mit einer einzigen Null oder Eins belegt werden, jedes Bit also gleichzeitig nur mit einer Null oder einer Eins rechnen kann, kann man jedes Bit eines Quantencomputers mit theoretisch beliebig vielen, sagen wir, Zuständen belegen, und mit allen Zuständen gleichzeitig rechnen. Diese Bits nennt man  Qbits, doch das ist vollkommen nebensächlich. 
Die Arbeitsgeschwindigkeit von Quantencomputern beruht darauf,
 Ein weiterer, noch weit gewichtiger Grund ist, dass durch die Natur, wie Qbits funktionieren, bestimmte Aufgaben der Komplexitätsklasse NP auf genial einfache Weise, und damit in kürzester Zeit, gelöst werden können. Alle bei Bitcoin verwendeten kryptographischen Methoden sind davon betroffen.

Die Funktionsweise von Quantencomputern kann man ohne gewisse Kenntnisse in Physik, Mathematik und Informatik nicht ansatzweise verstehen. Der Verfasser, selbst Physiker, hat für die einfachen Grundlagen  mehrere Stunden gebraucht. Deshalb soll an dieser Stelle eine Analogie helfen.

1. Eine Analogie
Angenommen, wir wollten die Untiefen eines Sees kartieren. Mit "klassischer" Technik würde man den gesamten See Stück für Stück abfahren, und, abhängig von der verfügbaren Technik, alle Untiefen mehr oder weniger schnell, jedenfalls nacheinander finden. Wäre der See 10 mal so gross, dann würden wir wahrscheinlich 10 mal so lange dafür brauchen. Wäre der See sehr tief, dann würden wir vermutlich sehr viel länger brauchen, weil die Aufgabe dadurch schwieriger wird.

Nun betrachten wir das Ganze aus einem anderen Blickwinkel.
Wir haben einen Zauberstab gefunden. Irgendwann stellt jemand fest, dass man damit schlagartig beliebige Mengen Wasser verschwinden lassen kann.
Ab dem Zeitpunkt fragen wir uns, was man damit Nützliches anstellen könnte, und finden schliesslich durchaus ein paar Anwendungsfälle. Jeder davon ist sehr speziell, aber alle sind so gut, dass sie bis dato bekannte Verfahren um Längen schlagen. Ein Anwendungsfall ist die Kartierung von Untiefen in Gewässern. Durch Gebrauch des Zauberstabs können wir jedes beliebige Gewässer schlagartig entleeren, sodass wir alle Untiefen auf einmal zu Gesicht bekommen. Davon machen wir ein Foto, ggfs von einem Satelliten aus.
Bei dieser Methode spielt es kaum eine Rolle, wie gross oder tief das Gewässer ist, denn auf den Zauberstabsalgorithmus hat beides keine Auswirkung. Die Verarbeitung aller Informationen bezüglich Untiefen geschieht parallel, und in diesem Beispiel sogar sehr schnell.

Den Zauberstab mag man gut finden oder nicht, jedenfalls zeigt dieses Beispiel alle wesentlichen Aspekte auf:
2. Der Algorithmus von Deutsch

David Deutsch fand ca. 1990 einen Algorithmus, der auf heutigen Quantencomputern tatsächlich praktisch funktioniert.
Auf die Analogwelt übertragen kann man es so beschreiben: Dieser Algorithmus kann durch Betrachten lediglich einer Seite einer Münze folgende Fälle unterscheiden:
  1. Beide Seiten sind gleich (entweder 2 x Kopf oder 2 x Zahl --> Fälschung)
  2. Beide Seiten sind unterschiedlich (1 x Kopf und 1 x Zahl)

Der Algorithmus schaut sich also lediglich eine Seite an, und weiss dann, welcher der beiden Fälle zutrifft.

Bei diesem tatsächlich funktionierenden Anwendungsfall mag man sich fragen, wozu das gut sein soll.

Aber immerhin zeigt es, dass der Algorithmus von Deutsch systematisch kürzer ist als die klassische Methode, die die Betrachtung beider Seiten erfordern würde.


Dieser Algorithmus funktioniert genauso schnell für z.B. 10 Münzen: Er schaut sich von allen Münzen nur jeweils eine Seite an, und das für alle gleichzeitig, und weiss hinterher, welcher Fall für jede Münze im einzelnen zutrifft. Wichtig ist, dass in einem einzigen Schritt alle Münzen gleichzeitig behandelt werden. Jede klassische Methode würde die Betrachtung beider Seiten aller Münzen erfordern, was in diesem Fall 20 Schritten entspricht.

Dieses Beispiel zeigt deutlich, dass der Rechenaufwand allein durch die Natur der Aufgabe bestimmt wird, wohingegen der Umfang der Aufgabe keinen Einfluss hat.


3. Der Algorithmus von Shor


Etwa um 2000 fand Peter Shor einen Algorithmus, mit dem man die kryptographischen Verfahren, die Bitcoin nutzt, insbesondere die SHA256 Hashfunktion, in polynomialer Zeit brechen kann. Dadurch kann man die eigentlich der Komplexitätsklasse NP zugeordnete SHA256 Hashfunktion mit einem Aufwand brechen, der dem einer der Komplexitätsklasse P zugeordneten Aufgabenstellung entspricht: Die ursprünglich unlösbare Aufgabe "Brechen der SHA256 Hashfunktion" würde effizient lösbar.


Die Folgen für Bitcoin wären auch in diesem Fall dieselben wie bereits zweimal angedeutet, und werden später diskutiert.

Real existierende Quantencomputer

Die heute existierenden Quantencomputer können "normalen" Computern nicht das Wasser reichen. Das hat folgende Gründe:
Es ist wichtig zu erkennen, dass die Methode an sich grundsätzlich funktioniert, ihr praktischer Einsatz aber am technologischen Stand scheitert.
Grundsätzlich gilt:
Was heute technologisch nicht funktioniert, kann morgen bereits funktionieren. Daher ist es gefährlich zu sagen, eine bestimmte Technik wird sich nicht etablieren.
Andererseits verkennt man die Situation vollkommen, wenn man sagt, es scheitere "lediglich" an der verfügbaren Technologie, und es sei daher nur eine Frage der Zeit (siehe z.B. Kernfusion).
Im Falle von Quantencomputern muss man grundsätzlich festhalten:
Nach Einschätzung des Verfassers wird es praktisch verwendbare Quantencomputer nie geben, zumindest nicht im 21. Jahrhundert.
Sollte er sich täuschen: Die Folgen für Bitcoin wären auch in diesem Fall dieselben wie bereits mehrfach angedeutet. Dies wird im folgenden Kapitel näher beschrieben.

Weiter

Datenschutzhinweise
September 2020