Werden herkömmliche Computer in der Zukunft Bitcoin brechen können?
Wenn wir mit Bleistift und
Papier etwas ausrechnen, dann brauchen wir dafür umso länger,
je
grösser die dabei vorkommenden Zahlen sind
z.B. dauert es länger, 2 mit 2 zu multiplizieren, als 234 mit 91.
je schwieriger die Aufgabenstellung ist
z.B. ist es schwieriger, die Wurzel aus 125 zu ziehen, als 125 durch 5 zu dividieren.
Man kann sagen, wir lösen die
Aufgabe so, indem wir sie Schritt für Schritt abarbeiten. Daraus folgt
unmittelbar, dass wir für grössere Zahlen und/oder schwierigere
Aufgaben mehr Schritte benötigen als für einfache Zahlen / einfachere Aufgaben. Computer, wie wir sie
heute kennen, funktionieren im Prinzip genau so wie der Mensch, der auf
Papier etwas ausrechnet. Daher gelten hier dieselben Zusammenhänge: Je grösser die Zahlen, und je schwieriger die Aufgabe, desto
länger braucht der Computer. Der Flaschenhals beim Menschen ist das
Gehirn; dieses arbeitet alle Rechenschritte hintereinander (seriell)
ab. Beim Computer ist es der Mikroprozessor, speziell die Arithmetisch
Logische Einheit (ALU), auch sie arbeitet alle Schritte seriell ab. Computer sind zwar um
Grössenordnungen schneller als Menschen, doch man braucht die Aufgabe nur schwierig
genug zu machen, und die Zahlen nur gross genug, sodass auch sie die
Aufgabe irgendwann nicht mehr in akzeptabler Zeit lösen können. Der Kern des Problems, bzw.
die Grenze der heute verfügbaren Computertechnik besteht folglich darin, dass
mit wachsender Komplexität der Aufgabe die Zeitdauer für ihre Lösung
ansteigt. Diese trivial anmutende Feststellung ist gleichzeitig ein Vorgriff: Genau dieses Problem haben Quantencomputer nämlich nicht!
In der theoretischen Informatik werden Aufgaben ihrem Schwierigkeitsgrad entsprechend in zwei Komplexitätsklassen eingeteilt: Einfach (P) und Schwierig
(NP), wer hätte das gedacht. Um zu verstehen, welche Eigenschaften eine Aufgabe "einfach" bzw.
"schwierig" machen, braucht man Mathematikkenntnisse auf universitärem
Niveau. An dieser Stelle muss folgendes genügen:
Die Unterscheidung
zwischen den beiden Klassen erfolgt nach strengen mathematischen
Kriterien. Diese liegen weit jenseits dessen, was in den Beispielen
weiter oben anschaulich beschrieben wurde, und werden hier nicht
vertieft.
Das gilt insbesondere für die Begriffe "einfach", "schwierig", und "effizient".
Bei einfachen Aufgaben steigt der Rechenaufwand nur langsam mit der Grösse der verwendeten Zahlen
Die Rechenzeit wächst Polynomial mit der Zahlengrösse, daher "P")
Statt nur
"Polynomial" müsste man der Vollständigkeit halber "Deterministisch
Polynomial" sagen. Deterministisch bedeutet, der Algorithmus, der die
Aufgabe lösen kann, ist in seinem detaillierten Ablauf für alle
gewählten Zahlen vorhersagbar. Für Software bedeutet das, das Programm
wird immer einen vorhersehbaren Ablauf haben, egal, welche Zahlen man
als Eingabe wählt.
Ohne Begründung: Alle Aufgaben der Komplexitätsklasse P sind gleichzeitig deterministisch.
Die praktische
Konsequenz ist, dass Computer diesen Aufgabentyp selbst dann noch
in akzeptabler Zeit lösen können, wenn man die Zahlen sehr gross wählt.
Man sagt daher, dieser Aufgabentyp sei effizient lösbar.
Aufgaben der Komplexitätsklasse P sind in polynomialer Zeit und daher effizient lösbar.
Bei schwierigenAufgaben steigt der Rechenaufwand schnell mit der Grösse der verwendeten Zahlen (Die Rechenzeit wächst nichtdeterministisch polynomial (NP), beispielsweise exponentiell, mit der Zahlengrösse).
Im Gegensatz zu eins weiter oben bedeutet das P hier etwas anderes.
N bedeutet, dass die Rechenzeit für die Lösung der Aufgabe Nichtdeterministisch
wächst,
P bedeutet andererseits, dass Lösungsvorschläge mit polynomialem Aufwand, und
daher effizient, überprüft werden können.
Vereinfacht: Aufgaben der Komplexitätsklasse NP sind schwierig zu lösen, aber Lösungsvorschläge sind effizient überprüfbar.
Nichtdeterministisch
bedeutet, der
Algorithmus, der die Aufgabe lösen kann, hängt in seinem detaillierten
Ablauf in einer Weise von der gewählten Zahl ab, die nicht systematisch
vorhersehbar ist. Für Software bedeutet
das, das Programm wird Fallunterscheidungen und Verzweigungen aufweisen
wo die letztlich eingeschlagene Richtung erst dann ermittelt werden
kann, wenn das Programm an der Verzweigung / Fallunterscheidung
angekommen ist. Die letztlich eingeschlagenen Richtungen hängen in
nicht vorhersehbarer Weise von den gewählten Zahlen ab.
Ohne Begründung: Lösungsvorschläge aller Aufgaben der Komplexitätsklasse NP sind effizient (und daher schnell) überprüfbar.
Die praktische Konsequenz
ist, dass Computer
diesen Aufgabentyp bereits dann nicht mehr in akzeptabler
Zeit lösen können, wenn man die Zahlen moderat gross wählt,
Lösungsvorschläge hingegen im Handumdrehen verifiziert oder falsifiziert werden können.
Aufgaben der Komplexitätsklasse NP sind nicht in polynomialer Zeit, und daher nicht effizient lösbar, jedoch können Lösungsvorschläge in polynomialer Zeit, und daher effizient, überprüft werden.
In der praktischen und angewandten Mathematik und Informatik ist es fast immer wünschenswert, dass Aufgaben, einfach, und daher effizient lösbar sind, weil man ja normalerweise Probleme lösen will. Es wäre also wünschenswert wenn fast alle Aufgaben der Komplexitätsklasse P angehörten. Bei kryptographischen Anwendungen will man aber genau das Gegenteil: Die
Aufgabe soll so schwierig sein, dass kein Computer, am besten nicht
einmal die vereinigte irdische Rechenkapazität, in der Lage ist, die
Aufgabe z.B. innerhalb von 100 Milliarden Jahren zu lösen. Das ist aber
noch nicht alles. In der Kryptographie braucht man neben der
praktischen Unlösbarkeit der Aufgabe noch zusätzlich folgende
Eigenschaft: Lösungsvorschläge sollen nicht nur effizient, sondern sprichwörtlich in einem Augenblick überprüfbar sein.
Daraus folgt, dass kryptographischen Aufgabenstellungen der Komplexitätsklasse
NP angehören müssen. Das bekannteste Grundprinzip funktioniert bei Bitcoin wie folgt:
Die Adresse ist öffentlich, d.h., jeder kann mir darauf Bitcoins überweisen.
Den Key für diese Adresse kenne nur ich selbst.
Ich kann ihn als Lösungsvorschlag anwenden, worauf im Handumdrehen bestätigt wird, dass der Key zu der
Adresse passt, demnach ich im Besitz der darauf befindlichen Bitcoins
bin: Die Aufgabe "Passt ein bestimmter Key zu der Adresse" gehört zur
Komplexitätsklasse P, ist also in polynomialer Zeit, praktisch sogar im
Handumdrehen lösbar.
Es
ist für heutige Rechenleistungen unmöglich, für diese
Adresse den Key zu berechnen, demnach wird niemand anderes als ich
selbst jemals auf diese Bitcoins zugreifen können: Die Aufgabe "Finde
den Key zu einer bestimmten Adresse" gehört nicht zur
Komplexitätsklasse P (und damit zu NP), ist nicht in polynomialer Zeit,
und praktisch nach heutigem Stand überhaupt nicht lösbar.
dass es Aufgaben der Komplexitätsklasse NP überhaupt gibt,
insbesondere, dass die jeweilige Aufgabenstellung tatsächlich der Klasse NP angehört.
Sollte tatsächlich einmal
jemand ein Verfahren entdecken, das ECDSA effizient
löst, dann wäre Bitcoin grundsätzlich angreifbar. Der Angreifer wäre
grundsätzlich in der Lage, die Bitcoins vieler (bei weitem nicht aller) Adressen in seinen
Besitz zu bringen. Die weiteren Zusammenhänge und Folgen werden später diskutiert.
Die weitaus schwerwiegendere Frage, gleichzeitig Gegenstand der Forschung mit sehr hohen Preisgeldern, lautet:
Ist P = NP ?
Sind die heute der Komplexitätsklasse NP angehörigen Aufgaben tatsächlich
(also mathematisch beweisbar) schwierig, oder sind sie es lediglich
deshalb, weil noch keine Verfahren gefunden wurden, mit denen sich
diese Aufgaben in polynomialer Zeit, also effizient lösen lassen?
Sollte die Antwort auf P = NP ? eines Tages tatsächlich einmal "Ja"
lauten, dann hätte dies vermutlich keine praktischen Folgen. Die weiteren Zusammenhänge und Folgen werden später diskutiert.