coindesk.com
Teil 1 dieser Serie erklärte, was Quantencomputer tatsächlich sind. Nicht einfach schnellere Versionen herkömmlicher Computer, sondern eine grundlegend andere Art von Maschine, die die merkwürdigen Gesetze der Physik nutzt, die nur auf der Skala von Atomen und Partikeln gelten.
Aber zu wissen, wie ein Quantencomputer funktioniert, sagt nicht aus, wie er von einem böswilligen Akteur verwendet werden kann, um Bitcoin zu stehlen. Dafür ist es notwendig zu verstehen, was tatsächlich angegriffen wird, wie die Sicherheit von Bitcoin aufgebaut ist und genau, wo die Schwachstelle liegt.
Dieser Artikel beginnt mit der Verschlüsselung von Bitcoin und führt weiter bis zum neuneinhalbminütigen Zeitfenster, das benötigt wird, um sie zu knacken, wie von festgestellt wurde.Googles jüngste Veröffentlichung zum Quantencomputing.
Die Einbahnkarte
Bitcoin verwendet ein System namens elliptische Kurvenkryptographie, um nachzuweisen, wem was gehört. Jede Wallet verfügt über zwei Schlüssel. Einen privaten Schlüssel, der eine geheime Zahl ist, 256 Stellen lang in Binärform, ungefähr so lang wie dieser Satz. Ein öffentlicher Schlüssel wird aus dem privaten Schlüssel abgeleitet, indem eine mathematische Operation auf der speziellen Kurve namens durchgeführt wird.secp256k1.""
Betrachten Sie es als eine Einbahnkarte. Beginnen Sie an einem bekannten Punkt auf der Kurve, auf den sich alle einigen, genannt der Erzeugerpunkt G (wie in der unten stehenden Grafik dargestellt). Nehmen Sie eine private Anzahl von Schritten in einem durch die Mathematik der Kurve definierten Muster. Die Anzahl der Schritte ist Ihr privater Schlüssel. Der Punkt, an dem Sie auf der Kurve landen, ist Ihr öffentlicher Schlüssel (Punkt K im Diagramm). Jeder kann überprüfen, dass Sie an genau diesem Ort angekommen sind. Niemand kann herausfinden, wie viele Schritte Sie dorthin gemacht haben.
Technisch wird dies als K = k × G geschrieben, wobei k Ihr privater Schlüssel und K Ihr öffentlicher Schlüssel ist. Die „Multiplikation“ ist keine gewöhnliche Multiplikation, sondern eine geometrische Operation, bei der ein Punkt wiederholt entlang der Kurve zu sich selbst addiert wird. Das Ergebnis landet an einer scheinbar zufälligen Stelle, die nur Ihre spezifische Zahl k hervorbringen würde.
Die entscheidende Eigenschaft besteht darin, dass das Vorwärtsgehen einfach ist, während das Zurückgehen für klassische Computer praktisch unmöglich ist. Wenn Sie k und G kennen, dauert die Berechnung von K nur wenige Millisekunden. Wenn Sie K und G kennen und k herausfinden möchten, lösen Sie das, was Mathematiker als das elliptische Kurvendiskrete Logarithmusproblem bezeichnen.
Es wird geschätzt, dass die bekanntesten klassischen Algorithmen für eine 256-Bit-Kurve länger als das Alter des Universums.
Diese Einweg-Falle ist das gesamte Sicherheitsmodell. Ihr privater Schlüssel beweist, dass Sie Ihre Coins besitzen. Ihr öffentlicher Schlüssel ist sicher zu teilen, da kein klassischer Computer die Mathematik rückgängig machen kann. Wenn Sie Bitcoin senden, verwendet Ihre Wallet den privaten Schlüssel, um eine digitale Signatur zu erstellen, einen mathematischen Beweis, dass Sie die geheime Zahl kennen, ohne sie preiszugeben.
Shors Algorithmus öffnet die Tür in beide Richtungen
Im Jahr 1994 entwickelte ein Mathematiker namens Peter Shor entdeckte einen Quantenalgorithmus das die Hintertür durchbricht.
Der Shor-Algorithmus löst das diskrete Logarithmusproblem effizient. Dieselbe Mathematik, für die ein klassischer Computer länger als das Universum existiert, bewältigt der Shor-Algorithmus in dem, was Mathematiker nennen.polynomielle Zeit, was bedeutet, dass die Schwierigkeit langsam zunimmt, wenn die Zahlen größer werden, anstatt explosiv.
Die Intuition, wie es funktioniert, basiert auf den drei quantenmechanischen Eigenschaften von Teil 1 dieser Serie.
Der Algorithmus muss Ihren privaten Schlüssel k finden, gegeben Ihren öffentlichen Schlüssel K und den Erzeugungspunkt G. Er wandelt dies in ein Problem um, die Periode einer Funktion zu finden. Denken Sie an eine Funktion, die eine Zahl als Eingabe nimmt und einen Punkt auf der elliptischen Kurve zurückgibt.
Wenn Sie ihm sequenzielle Zahlen zuführen, 1, 2, 3, 4, wiederholen sich die Ausgaben schließlich in einem Zyklus. Die Länge dieses Zyklus wird als Periode bezeichnet, und sobald bekannt ist, wie oft die Funktion sich wiederholt, löst sich die Mathematik des diskreten Logarithmusproblems in einem einzigen Schritt auf. Der private Schlüssel ergibt sich fast sofort.
Die Bestimmung der Periode einer Funktion ist genau das, wofür Quantencomputer entwickelt wurden. Der Algorithmus versetzt sein Eingangsregister in eine Superposition (oder, in der Quantenmechanik, existiert ein Teilchen gleichzeitig an mehreren Orten) und repräsentiert somit alle möglichen Werte gleichzeitig. Anschließend wird die Funktion auf alle Werte gleichzeitig angewendet.
Anschließend wird eine Quantenoperation namens Fourier-Transformation angewendet, die dazu führt, dass sich die falschen Antworten gegenseitig auslöschen, während die richtigen Antworten verstärkt werden.
Wenn Sie das Ergebnis messen, erscheint die Periode. Aus dieser Periode gewinnt die gewöhnliche Mathematik k zurück. Das ist Ihr privater Schlüssel und somit Ihre Coins.
Der Angriff nutzt alle drei quantenmechanischen Methoden aus dem ersten Artikel. Die Superposition bewertet die Funktion gleichzeitig für jeden möglichen Eingang. Die Verschränkung verknüpft Ein- und Ausgabe, sodass die Ergebnisse korreliert bleiben. Die ‚Interferenz‘ filtert das Rauschen, bis nur die Antwort übrig bleibt.
Warum Bitcoin heute weiterhin funktioniert
Der Shor-Algorithmus ist seit mehr als 30 Jahren bekannt. Der Grund, warum Bitcoin weiterhin existiert, liegt darin, dass dessen Ausführung einen Quantencomputer mit einer ausreichend großen Anzahl stabiler Qubits erfordert, um die Kohärenz während der gesamten Berechnung aufrechtzuerhalten.
Der Bau dieser Maschine war bisher unerreichbar, aber die Frage war stets, wie groß „groß genug“ ist.
Frühere Schätzungen sprachen von Millionen physischer Qubits. Das Papier von Google, Anfang April veröffentlicht von der Quantum AI-Abteilung mit Beiträgen des Forschers der Ethereum Foundation Justin Drake und des Kryptografen der Stanford University Dan Boneh, reduzierte diese Zahl auf weniger als 500.000.
Oder eine etwa 20-fache Reduzierung gegenüber früheren Schätzungen.
Das Team hat zwei Quantenschaltkreise entwickelt, die Shor's Algorithmus gegen die spezifische elliptische Kurve von Bitcoin implementieren. Der eine verwendet etwa 1.200 logische Qubits und 90 Millionen Toffoli-Gatter. Der andere verwendet etwa 1.450 logische Qubits und 70 Millionen Toffoli-Gatter.
Ein Toffoli-Gatter ist eine Art Gatter, das auf drei Qubits wirkt: zwei Steuer-Qubits, die den Zustand eines dritten, Ziel-Qubits beeinflussen. Man kann sich das vorstellen wie drei Lichtschalter (Qubits) und eine spezielle Glühbirne (das Ziel), die nur leuchtet, wenn zwei bestimmte Schalter gleichzeitig eingeschaltet sind.
Da Qubits ihren Quantenzustand ständig verlieren, wie in Teil 1 erklärt wurde, benötigt man Hunderte von redundanten Qubits, die gegenseitig ihre Arbeit überprüfen, um einen einzigen zuverlässigen logischen Qubit aufrechtzuerhalten. Der Großteil eines Quantencomputers besteht nur dazu, die eigenen Fehler der Maschine zu erkennen, bevor sie die Berechnung ruinieren. Das etwa 400-zu-1-Verhältnis zwischen physischen und logischen Qubits spiegelt wider, wie viel von der Maschine als selbstüberwachende Infrastruktur existiert.
Das neunminütige Zeitfenster
Googles Studie reduzierte nicht nur die Anzahl der Qubits. Sie führte ein praktisches Angriffsszenario ein, das die Betrachtungsweise der Bedrohung verändert.
Die Teile von Shors Algorithmus, die nur von den festgelegten Parametern der elliptischen Kurve abhängen, welche öffentlich bekannt und für jede Bitcoin-Brieftasche identisch sind, können vorab berechnet werden. Der Quantencomputer befindet sich in einem vorgeladenen Zustand, bereits halb durch die Berechnung, wartend.
In dem Moment, in dem ein Ziel-öffentlicher Schlüssel erscheint, sei es durch die Übermittlung in einer Transaktion an den Mempool des Netzwerks oder bereits auf der Blockchain aus einer vorherigen Transaktion offengelegt, muss die Maschine nur noch die zweite Hälfte abschließen.
Google schätzt, dass die zweite Hälfte etwa neun Minuten dauert.
Die durchschnittliche Bestätigungszeit eines Bitcoin-Blocks beträgt 10 Minuten. Das bedeutet, dass ein Nutzer, der eine Transaktion sendet und dessen öffentlicher Schlüssel im Mempool sichtbar ist, einem Quantenangreifer etwa neun Minuten Zeit gibt, um einen privaten Schlüssel abzuleiten und eine konkurrierende Transaktion einzureichen, die die Gelder umleitet.
Die Berechnung gibt dem Angreifer eine ungefähre 41%ige Chance, vor der Bestätigung Ihrer ursprünglichen Transaktion fertigzustellen.
Das ist der Mempool-Angriff. Er ist alarmierend, aber er erfordert einen Quantencomputer, der bisher noch nicht existiert.
Die größere Sorge ist jedoch die Menge von 6,9 Millionen Bitcoin (etwa ein Drittel des Gesamtangebots), die sich in Wallets befinden, deren öffentlicher Schlüssel bereits dauerhaft auf der Blockchain offengelegt wurde. Diese Coins sind anfällig für einen „At-Rest“-Angriff, der keinen Wettlauf gegen die Zeit erfordert. Der Angreifer kann sich so viel Zeit nehmen, wie er benötigt.
Ein Quantencomputer, der den Shor-Algorithmus ausführt, kann einen Bitcoin-öffentlichen Schlüssel in den privaten Schlüssel umwandeln, der die Münzen kontrolliert. Für Münzen, die seit Taproot (einem Privatsphären-Upgrade von Bitcoin, das im November 2021 live ging) übertragen wurden, ist der öffentliche Schlüssel bereits sichtbar. Für Münzen in älteren Adressen ist der öffentliche Schlüssel verborgen, bis Sie ausgeben, woraufhin Sie ungefähr neun Minuten haben, bevor der Angreifer aufholt.
Was dies in der Praxis bedeutet, welche 6,9 Millionen Bitcoin bereits exponiert sind, was Taproot verändert hat und wie schnell die Hardware die Lücke schließt, ist Thema des nächsten und letzten Beitrags dieser Serie.