Eine genial-aufwändige Methode, um ziemlich wenig Hashpower zu produzieren

Quantencomputer gelten als Bedrohung für Bitcoin. Zwei Wissenschaftler haben es durchgerechnet: Haben Quantenminer wirklich einen Vorteil gegenüber klassischen Minern? Und wenn ja – erwächst daraus eine Gefahr für Bitcoin?

Bitcoin und Quantencomputer: Das Thema hatten wir schon das eine oder andere Mal, und es geistert eigentlich von Anfang an mit Bitcoin mit.

Bedrohen Quantencomputer Bitcoin? Wird eines Tages ein Quantencomputer ankommen und durch seine überlegene Rechenkraft alle Wallets leerräumen und alle Bitcoins wegminen? Die einen sagen, ja, langfristig könnte das passieren, die anderen sagen nein, es wird sehr lange kein Quentchen Grund zur Sorge geben.

Über Quantencomputer, Bitcoin und den Signaturalgorithmus ECDSA haben wir bereits geschrieben. Heute nehmen wir uns ein Paper vor, in dem zwei kanadische Informatik-Professoren analysieren, ob eine und wenn ja welche Gefahr von Quantenminern ausgeht.

Das Thema ist nicht trivial, vor allem für mathematische Laien. Aber weil es spannend für jeden ist, der sich für Bitcoin und die Zukunft von Computern interessiert, versuche ich, das Paper so einfach wie möglich vorzustellen.

Der springende Fortschritt

Das Grundgerüst, auf dem die Autoren ihre Frage aufbauen, ist die folgende Theorie: Wenn ein Miner zu mächtig wird, kann er das Netzwerk bedrohen. Hat er eine absolute Mehrheit, kann er 51-Prozent-Angriffe fahren, aber auch schon darunter kann er durch „aggressives“ oder „egoistisches“ Mining Schäden anrichten.

Was nun, wenn sich ein Miner durch Quantencomputer einen solchen Vorteil verschafft, dass sein Anteil an der Hashrate unverhältnismäßig wächst?

Im Grunde hatten wir all das schon mal, und es ist ziemlich trivial: Der technologische Fortschritt beschleunigt das Mining. Er läuft nicht graduell statt, sondern oft sprunghaft. Ab 2011 verdrängten die Grafikkarten die Hauptprozessoren, ab 2013 die Asics die Grafikkarten. In solchen Momenten nimmt die Effizienz nicht mehr linear zu, sondern quadratisch oder exponentiell. Nachdem Ascis offenbar das Potenzial klassischer Chips weitgehend ausgereizt haben, könnten Quantencomputer den nächsten großen Sprung einleiten.

An sich sollte daraus kein Problem erwachsen. Die spieltheoretische Mechanik von Bitcoin motiviert rationale Akteure, ehrlich zu sein und sich gegenseitig in Schach zu halten. Dennoch kann ein technologischer Sprung holprig ablaufen, und vielleicht wird er zum Einfallstor für feindliche Mächte, die irrational handelnd Bitcoin schaden wollen.

Daher ist es sinnvoll, zu wissen, wann es denn soweit sein könnte. Was muss passieren, damit Quantencomputer klassische Asics vom Bitcoin-Mining verdrängen?

Suchen in unsortierten Datenbanken

Man kann sich das Bitcoin-Mining so vorstellen, dass die Miner mit ihrer Rechenpower Lose erzeugen. Sie generieren zufällige Hashes, und wenn eine Hash bestimmte, sehr seltene Anforderungen erfüllt, findet der Miner einen Block. Man könnte es auch einen Brute-Force-Angriff gegen die Hashfunktion SHA256 nennen.

Die beiden Professoren formulieren es so: „Die Miner versuchen, eine kryptographische Hash-Funktion partiell umzukehren“. Diese „partielle Inversion einer Hashfunktion“ sei „äquivalent dazu, ein markiertes Item in einer ungeordneten Liste von Items zu suchen (eine unstrukturierte Suche)“. Klingt wie eine Nebensache, ist aber für alles weitere fundamental.

Denn es gibt nicht vieles, was Quantencomputer erwiesenermaßen können. Eine der wenigen Aufgaben, bei denen man weiß, dass Quantencomputer klassische Computer in den Schatten stellen, ist das Suchen eines bestimmten Items in einer ungeordneten Liste.

Ein klassischer Computer muss bei einer Suche in einer unsortierten Datenbank – oder einem Brute-Force-Angriff – einen Eintrag nach dem anderen abarbeiten. Man kann sich das wie einen zweidimensionalen Zeiger vorstellen, der von Item zu Item wandert. Wenn er die Hälfte der Einträge gesehen hat, übersteigt die Chance, einen Treffer zu landen, 50 Prozent. Daher benötigt ein klassischer Computer im Durchschnitt N/2 Operationen, wobei N die Gesamtzahl der möglichen Items ist.

Quantencomputer haben nun einen Vorteil: Ein Qubit kann gleichzeitig 0 und 1 sein, weshalb eine Reihe von Qubits gleichzeitig alle denkbaren Varianten darstellen kann. Man kann es sich wie einen Zeiger vorstellen, der in N Dimensionen weist. Wenn die Qubits in dieser „Superposition“ sind, steckt in ihnen bereits die Lösung. Sie ist da.

Doch sobald man misst, zerstört man die Lösung. Das ist das berühmte Quantendilemma: Wenn man misst, zwingt man die Quanten dazu, einen bestimmten, aber zufälligen Zustand anzunehmen. Der Quantencomputer kennt also die Lösung, doch in einer tragischen Wendung entwertet er sie, wenn man sie abholen möchte.

Grovers Algorithmus: Quadratisch praktisch beschleunigt

Hier setzt Grovers Algorithmus ein. Der 1996 von Lov Grover entwickelte Algorithmus ist eine Methode, um das Ergebnis zu prüfen. Durch die Kombination verschiedener „Quantengatter“ – das sind die Operationen bei Quantencomputern – erkennen die Qubits falsche Ergebnisse und unterdrücken sie. Mit jeder Wiederholung – die sogenannte Grover-Iteration – steigt so die Wahrscheinlichkeit, das richtige Ergebnis zu erhalten.

Das ganze ist im Detail irre kompliziert. Klar ist aber: Mit der entsprechenden Anzahl an Iterationen kann der Grover-Algorithmus solche Suchen dramatisch beschleunigen. Denn um ein Item in einer unsortierten Liste zu finden, braucht Grover nur √n Anläufen. Er ist also beinah quadratisch schneller.

Zwei Beispiele: Wenn es 4 Items gibt, brauchen klassische Computer und Quantencomputer 2 Versuche. Bei 5.198.400 Items wird ein Quantencomputer dagegen nach 2280 Anläufen gefunden, während ein herkömmlicher Rechner mehr als zwei Millionen Mal operieren muss.

Gerade bei Aufgaben mit einer extremen Schwierigkeit bzw. einem extrem hohen N wie dem Bitcoin-Mining ist dieser Unterschied – der sogenannte Quantenvorteil – enorm. Es handelt sich um einen jener Sprünge, die ganze Ökosysteme erschüttern. Zumindest in der Theorie.

Der Quantenvorteil schmilzt

In der Praxis stößt ein Quantenminer auf ein sehr spezielles Problem: Er kann einen Block erst finden, wenn er das Ergebnis misst – und damit den Prozess abbricht. Er muss also schon vorher wissen, wie viele Iterationen er ausführen wird.

Die Frage ist vertrackst. Denn sowohl zuviel als auch zuwenig hat Nachteile. Mehr Iterationen erhöhen die Chance, ein korrekte Lösung zu finden – aber auch die Gefahr, dass ein anderer Miner schneller ist. Weniger Iterationen senken dagegen die Wahrscheinlichkeit eines gültigen Ergebnisses – und damit den Quantenvorteil.

Hätte ein Quantencomputer endlos lange Zeit, könnte er den vollen Quantenvorteil ausschöpfen. Doch dies ist beim Mining nicht möglich. Er muss einen Kompromiss zwischen zu wenigen und zu vielen Iterationen finden.

Um den optimalen Kompromiss zu kalkulieren, haben die Forscher eine Markov-Kette mit den möglichen Szenarien gebildet. Eine Markov-Kette ist eine mathematische Formulierung von Sequenzen möglicher, meist zufälliger oder teilzufällig-bedingter Ereignisse. Eine solche Kette zeigt an, welche Pfade durch den Wahrscheinlichkeitsdschungel im Durchschnitt zu den besten Ergebnissen führen: welche Einstellung des Grover-Algorithmus ideal wäre.

Verblüffenderweise wären dies 16 Minuten.

Zwei bemerkenswerte Erkenntnisse

Wenn ein Quantenminer 16 Minuten wartet, bis er das Ergebnis von Grovers Algorithmus abliest, erreicht sein Vorteil gegenüber klassischen Minern das Maximum im Verhältnis zu den Nachteilen, die aus der langen Zeitspanne erwachsen. Dieser Vorteil existiert, so die Wissenschaftler, unabhängig von der Schwierigkeit.

Das Ergebnis ist sehr bemerkenswert, weil man es in die Praxis überführen kann. Hier erkennt man zwei gravierende Folgen:

Zum einen disqualifiziert sich der Miner mit einer solchen Taktik von rund 80 Prozent der Blöcke. Denn diese werden in weniger als 16 Minuten gefunden. Er maximiert seine Erfolgsaussichten bei den verbleibenden 20 Prozent. Dies dürfte das Maximum der gesamten Mining-Power sein, die Quantencomputer erreichen können, ohne Effizienz zu opfern.

Zum anderen haben die meisten Kryptowährungen kürzere Intervalle zwischen den Blöcken. Dogecoin und Litecoin haben etwa wenige Minuten, Ethereum und Ripple nur einige Sekunden. Bei diesen Blockchains holen sich Quantenminer eine blutige Nase, weil der Quantenvorteil hier nicht greift. Sie sind schon jetzt quantensicher – zumindest im Mining.

Auch die Parallelisierung von Quantencomputern scheint eine Sackgasse zu sein. Diese ist zwar mit dem Grover-Algorithmus möglich, verbessert die Performance nach Kalkulationen der Autoren aber nur um den Faktor √m. Bei klassischen Computern beträgt der Faktor m, ist also quadratisch größer. Das macht es fraglich, ob Quantencomputer überhaupt jemals relevant fürs Mining sein werden.

78 Megahashes

Diese Berechnungen entschärfen die Gefahr von Quantencomputern schon mal deutlich. Aber die entscheidende Fragen bleibt noch unbeantwortet: Was muss geschehen, damit Quantenminer tatsächlich einen Vorteil gegenüber klassischen Minern haben? Ab wann wird es günstiger, einen Block mit einem Quantencomputer zu finden – falls überhaupt jemals?

Entscheidend hierfür sind zwei Faktoren: Die Kosten je Grover-Iteration und das Verhältnis der für einen Block notwendigen Anzahl Hashes zur Anzahl nötiger Grover-Iterationen. Dies berechnen die Autoren am Beispiel eines derzeit gängigen Quantencomputers mit einem „Gate Speed“ von 66,7 MegaHertz. Die Gates sind die Gatter, also die Quantenoperationen. Dieser Quantencomputer würde, kalkulieren die Wissenschaftler, je Sekunde 224 Grover-Iterationen schaffen.

Bedeutet? 224 Grover-Iterationen entsprechen einer Hashrate von 78 Megahashes je Sekunde. Das ist ein absolut mikroskopisch geringer Anteil der Bitcoin-Hashrate, ja, sogar nur ein winziger Bruchteil von dem, was moderne Asics leisten. Es wäre lächerlich, hier eine Gefahr zu riechen.

In Zukunft vermutlich stromsparender

Aber wenn Quantenminer keine Bedrohung darstellen – sind sie dann wenigsten effizienter? Also, kann es, zumindest graduell, zu einer Umrüstung aufs Quantenmining kommen? Und ab wann?

Um effizienter zu sein, dürften die Energiekosten einer Grover-Iteration maximal 3,49 x 105 Mal so teuer sein wie die Kosten einer klassischen Hash. Im Vergleich mit klassischen Minern, die eine Energieeffizienz von 10-10 Jules je Hash aufweisen, bräuchte ein Quantencomputer eine Effizienz besser als 3,49 x 105 x 10-10, also etwa 10 μJ je Grover-Iteration. Oder eben 2240 μJ je Sekunde.

Das klingt extrem wenig. Doch Quantencomputer sind sehr energiesparsam. Sobald das System auf 15 Millikalvin heruntergekühlt ist, also nahe des absoluten Nullpunktes ist, werden die Quantenbits zu einem Superleiter: Sie brauchen so gut wie keinen Strom und produzieren so gut wie keine Hitze. Derzeit macht das Abkühlen im Verhältnis zur Leistung einen Quantencomputer noch unökonomisch. Aber dies dürfte sich mit dem technischen Fortschritt ändern.

Insgesamt können wir als Bitcoiner also beruhigt und ein Stückchen klüger schlafen und ohne Schrecken von einer Zukunft der Quantencomputer träumen.