Wie Bitcoin gegen Quantencomputer gewappnet ist: Ein Vergleich der Vor- und Nachteile von drei Gitter-Signaturverfahren

Verfasst von: Blockstream Team

Übersetzung: Saoirse, Foresight News

Das Blockstream Research Institute hat einen umfassenden Forschungsbericht zu Gitter-Signaturen für Bitcoin veröffentlicht. Dieser Artikel fasst die Inhalte der Forschung, die wichtigsten Erkenntnisse und die entsprechenden Empfehlungen zusammen. Der vollständige Bericht kann hier eingesehen werden.

Digitale Signaturen sind der zentrale Mechanismus zur Autorisierung von Transaktionen in Bitcoin, wobei die derzeit verwendeten Schnorr- und ECDSA-Signaturen sehr kostengünstig sind. Im Jahr 1994 bewies Shor, dass ein leistungsstarker Quantencomputer in der Lage ist, diese beiden Signaturtypen zu knacken. Obwohl es weitreichende Diskussionen darüber gibt, wann solche Maschinen verfügbar sein werden, müssen wir bereits jetzt einen praktikablen Plan für die Implementierung von post-quanten Signaturen entwickeln, bevor das Problem tatsächlich auftritt.

Gitter-Signaturverfahren sind beliebte Kandidaten zur Ablösung der bestehenden Signaturen. Gitterkryptografie hat eine über ein Jahrhundert lange Forschungsgeschichte, und ihre kryptografischen Anwendungen haben sich über fast drei Jahrzehnte entwickelt. In post-quanten Kryptosystemen bieten Gitter-Signaturen zahlreiche Vorteile: Die Gesamtgröße von öffentlichem Schlüssel und Signatur kann unter 1,6 Kilobyte liegen, und ihre algebraische Struktur hat das Potenzial, Multi-Signaturen, Schwellen-Signaturen und kurze Beweise zu unterstützen.

Dieser Bericht untersucht die drei Verfahren Dilithium, Falcon und Hawk. Für Leser, die mit Gitterkryptografie nicht vertraut sind, erläutern wir die Designideen der einzelnen Verfahren, stellen die Algorithmusabläufe vollständig vor und analysieren sie aus den Perspektiven Sicherheit, Leistung und praktische Implementierung (z. B. Ableitung von Wallet-Schlüsseln). Welche dieser Verfahren können tatsächlich auf der Bitcoin-Blockchain implementiert werden?

Bewertungsdimensionen

Bitcoin hat spezifische Einschränkungen bei der Auswahl von Signaturverfahren. Diese Bewertung konzentriert sich auf vier zentrale Kriterien:

• On-Chain-Kosten: Ein wichtiges Kriterium ist die Gesamtgröße von öffentlichem Schlüssel und Signatur. Wenn Ausgaben getätigt werden, werden sowohl der öffentliche Schlüssel als auch die Signatur in der Blockchain aufgezeichnet, und alle Knoten müssen jedes Byte herunterladen und speichern. Auch die Verifizierungskosten sind entscheidend: Jede Signatur muss von allen Knoten im Netzwerk verifiziert werden, und eine langsame Verifizierung kann das gesamte Netzwerk belasten.
• Implementierungskomplexität: Die sichere Implementierung des Verfahrens ist von entscheidender Bedeutung. Wenn das Design Fließkommaoperationen oder präzise Gaußsche Abtastungen erfordert, kann ein Fehler in der Implementierung oder ein Timing-Angriff zu einem Schlüsselverlust führen. Die Implementierungskomplexität ist ein nicht zu vernachlässigender Faktor für eine reibungslose Migration.
• Implementierungsrisiken: Bei der tatsächlichen Integration in Bitcoin können verschiedene praktische Hindernisse auftreten: die Auswahl der Hash-Funktion auf Konsensebene (die meisten Kandidaten verwenden SHAKE, während Bitcoin SHA-256 verwendet), die Reproduzierbarkeit von plattformübergreifenden Signaturergebnissen und ob das Signaturprogramm an die Speichereinschränkungen von Hardware-Wallets angepasst werden kann.
• Entwicklungspotenzial: Die meisten Bitcoin-Wallets verwenden den BIP-32 hierarchischen deterministischen Mechanismus: Durch einen einzigen Hauptschlüssel können unendlich viele Unteröffentliche Schlüssel abgeleitet werden, ohne den privaten Schlüssel zu berühren. Derzeit unterstützen standardisierte post-quanten Signaturverfahren diese Eigenschaft nicht nativ, weshalb wir die Kosten für die Ergänzung dieser Fähigkeit untersuchen; gleichzeitig betrachten wir verschiedene nicht-standardisierte Varianten, die möglicherweise zusätzliche Vorteile bieten könnten.

Welche Sicherheitsstufe sollte gewählt werden?

Bevor die Größen verglichen werden, muss die Ziel-Sicherheitsstufe festgelegt werden, was nicht so einfach ist, wie es scheint. NIST klassifiziert die Sicherheitsstufen in 1-5; je höher die Stufe, desto stärker die Sicherheit, aber auch die entsprechenden Schlüssel- und Signaturgrößen werden größer.

Wir sind der Meinung, dass Bitcoin mindestens Sicherheitsstandard der Stufe 3 verwenden sollte. Bitcoin-Ausgaben könnten Jahrzehnte lang nicht ausgegeben werden, und wenn Fortschritte in der Kryptoanalyse dazu führen, dass die tatsächliche Sicherheitsstufe des Verfahrens sinkt, würde das Vermögen durch einen geschwächten Schlüssel gesperrt und langfristig Risiken ausgesetzt. Gitterkryptografie hat sich seit fast dreißig Jahren der öffentlichen Kryptoanalyse unterzogen, und die Forschung zur Annahme elliptischer Kurven in Bitcoin hat noch länger gedauert. Dennoch gibt es in der komplexen algebraischen Struktur der Gitterkryptografie zahlreiche potenzielle Angriffsflächen, und wir sollten nicht alle unsere Sicherheitswetten auf eine weit entfernte Zukunft setzen.

Die großen Mainstream-Produkte haben dieselbe Einschätzung getroffen. Apples iMessage PQ3-Protokoll hat direkt die Gitterparameter der Stufe 1 verworfen und verwendet durchgehend die Parameter der Stufen 3 und 5; Cloudflare verwendet in der post-quanten TLS-Implementierung ML-KEM-768 (Stufe 3) und gibt an, dass, obwohl Stufe 1 derzeit sicher aussieht, ein Sicherheitsüberhang für die kommenden Jahrzehnte der Kryptoanalyse eingeplant werden muss. Die Sicherheitszeitspanne von Bitcoin ist sogar noch länger als die der beiden genannten Produkte.

Die Erhöhung der Sicherheitsstufe hat ihren Preis. Zum Beispiel würde die Erhöhung von Dilithium von Stufe 2 auf Stufe 3 die Gesamtgröße um etwa 1,5 Kilobyte erhöhen. Der Bericht vergleicht die Parameter-Sets unter allen Sicherheitsstufen, sodass die Leser selbst abwägen können. Der Fall von Hawk beweist, dass konservative Sicherheitsüberlegungen keineswegs nur theoretisch sind.

Detaillierte Kandidatenanalyse

Dilithium: Ein einfaches Design

Dilithium wurde von NIST als ML-DSA im FIPS 204 Standard standardisiert und überträgt das Commitment-Challenge-Response-Paradigma von Schnorr-Signaturen auf modulare Gitterarithmetik.

Das größte Merkmal ist die Einfachheit. Alle Berechnungen von Dilithium sind Ganzzahlberechnungen: Ringoperationen, Matrix-Vektor-Multiplikation, Hashing, Runden, keine Fließkommaoperationen und keine diskrete Gaußsche Abtastung. Es ist einfacher, eine sichere und konstante Implementierung zu schreiben. Es ist auch das am weitesten verbreitete Kandidatenverfahren, das bereits in OpenSSL, BoringSSL, AWS-LC und Apple CryptoKit integriert ist.

Der Preis ist eine größere Größe. Die ML-DSA-65 mit Sicherheitsstufe 3 hat einen öffentlichen Schlüssel von 1952 Bytes, eine Signatur von 3309 Bytes, insgesamt 5261 Bytes, was etwa 55-mal so groß ist wie die Gesamtgröße der nativen Bitcoin-Öffentlichen und privaten Schlüssel + Signatur und damit die größte Größe unter den drei Verfahren mit derselben Sicherheitsstufe.

Für Bitcoin ist der wertvollste Aspekt von Dilithium: Es ist das einzige Verfahren der drei, das der BIP-32-Stil Schlüsselableitung nahe kommt. Die rekombinierbare Schlüsselstruktur DilithiumRK kann nur mit öffentlichen Informationen von einem Elternschlüssel abgeleitet werden. Der Bericht analysiert drei Varianten, darunter unsere vorgeschlagene DilithiumRKS, bei der die Ableitungslogik vollständig in der Wallet-Software implementiert ist, sodass auf der Blockchain nur die Standardverifizierung für normale ML-DSA-Signaturen erforderlich ist. Aber alle drei Varianten haben noch nicht die Standards für den Einsatz erreicht: Zwei Varianten erfordern Änderungen am Verifier, und DilithiumRKS selbst fehlt ein vollständiger Nachweis der Unverfälschbarkeit; alle Verfahren sind auf eine gemeinsame Matrix im gesamten Netzwerk angewiesen, die zwar unter der Annahme von Module-LWE formal sicher ist, aber die Sicherheit aller Schlüssel an dasselbe Exemplar bindet. Wir glauben, dass die gegenwärtige Schlüsselableitung auf Basis von Dilithium nur als Konzeptnachweis betrachtet werden kann und nicht für die tatsächliche Implementierung geeignet ist.

Falcon: Ein kompaktes Verfahren

Falcon wurde von NIST ausgewählt und trägt den standardisierten Namen FN-DSA. Es ist das kompakteste der drei Verfahren. Der öffentliche Schlüssel und die Signatur der Sicherheitsstufe 1 Falcon-512 haben insgesamt 1563 Bytes; die Sicherheitsstufe 5 Falcon-1024 hat insgesamt 3073 Bytes. Falcon-1024 mit höherem Sicherheitsüberhang hat sogar eine kleinere Größe als das Dilithium der Stufe 3.

Falcon verfolgt einen anderen Ansatz als Dilithium: Es basiert auf dem Hash-Signatur-Modell von NTRU-Gittern. Der private Schlüssel des Unterzeichners ist eine Gruppe von kurzen Basen des Gitters; die Nachricht wird auf einen Punkt im Raum gehasht, und der Unterzeichner verwendet die kurzen Basen, um einen Vektor zu finden, der dem Punkt sehr nahe kommt. Der Punkt und dieser nahe Vektor bilden zusammen die Signatur; die Verifizierung prüft lediglich, ob der Vektor zu diesem Gitter gehört und ausreichend nahe ist. Die Herausforderung bei der Implementierung besteht darin, dass der Vektor gefunden werden muss, ohne Informationen über die Basis preiszugeben. Frühere Verfahren wie GGH und NTRUSign haben einfach nahe Gitterpunkte verwendet, was bei jeder Signatur einen Teil der geometrischen Informationen preisgibt. Falcon verwendet den GPV-Rahmen, um benachbarte Vektoren aus einer gaußschen Verteilung zu sampeln, was beweisen kann, dass die Ausgaben des Samplers unabhängig von der Basis sind und das Risiko eines Lecks beseitigt, aber die Implementierung des Samplers ist erheblich schwieriger.

Der Sampler ist ein Schwachpunkt auf der Ingenieurebene von Falcon. Er erfordert komplexe Berechnungen im komplexen Fourier-Raum, die Fließkommaoperationen benötigen. Unterschiedliche Prozessoren, Compiler und Compiler-Optimierungsoptionen können zu inkonsistenten Fließkomma-Ausgaben führen. Dies ist nicht nur ein Kompatibilitätsproblem, sondern auch ein Sicherheitsrisiko: Der Sicherheitsnachweis von GPV verlangt, dass der Unterzeichner für denselben Hash niemals zwei verschiedene kurze Vektoren ausgibt; wenn die Signatur zu einer deterministischen Signatur wird, können Unterschiede in der Fließkomma-Rundung, die durch die Plattform verursacht werden, diese Bedingung verletzen. Es gibt praktikable Lösungen: Deterministisches Falcon kann Fließkomma durch Ganzzahl-Simulation ersetzen, um auf allen Plattformen konsistente Signaturen zu erzeugen. Der Preis ist, dass die Signaturgeschwindigkeit um etwa das 15-fache sinkt und die Schlüsselgenerierungsgeschwindigkeit um etwa das 2-fache sinkt.

Wichtig ist, dass der Verifizierungsschritt nicht betroffen ist: Falcon verwendet während des gesamten Verifizierungsprozesses Ganzzahloperationen, die Ergebnisse sind deterministisch, und es ist auch das Verfahren mit der schnellsten Verifizierung. Diese asymmetrische Eigenschaft ist für Bitcoin sehr vorteilhaft: Die Signatur wird einmal von der Wallet bei der Ausführung einer Ausgaben-Transaktion durchgeführt, während jede Signatur von allen Knoten im gesamten Netzwerk verifiziert werden muss. Eine 15-fache Verlangsamung des Signaturprozesses ist ein geringer Aufwand, der durch die plattformübergreifende Reproduzierbarkeit und die Ganzzahloperationen gerechtfertigt ist. Daher ist das Fließkomma-Problem ein Hindernis, das durch Ingenieurlösungen überwunden werden kann, aber kein tödlicher Mangel ist.

Zwei Punkte sind zu beachten: Aufgrund struktureller Einschränkungen hat Falcon keine Parameter der Stufe 3 und kann nur zwischen Stufe 1 oder Stufe 5 wählen. Aufgrund des Sicherheitsüberhangs empfehlen wir Falcon-1024. Zweitens verbraucht die Signatur eine große Menge an Speicher: Der Sampler des 1024-Parameter-Sets benötigt eine vorab berechnete Baumstruktur, die etwa 90 Kilobyte Speicher benötigt. Hardware-Wallets können diesen Baum dynamisch pro Zweig rekonstruieren, wodurch der Speicherbedarf auf etwa 16 Kilobyte reduziert wird, aber die Signaturzeit verdoppelt wird. Eine Verlangsamung der Signatur auf Hardware-Geräten ist ein praktischer Kostenfaktor, aber noch akzeptabel.

Hawk: Ein gescheitertes Verfahren

Hawks Ziel war es, die Vorteile der beiden anderen Verfahren zu kombinieren: Die Hawk-512-Signatur hat nur 555 Bytes und ist damit kleiner als Falcon; die gesamte Berechnung auf der Signaturseite erfolgt mit Ganzzahlen, und der minimale Speicherbedarf beträgt nur 6 Kilobyte. Es ist auch der einzige verbleibende Gitterkandidat in der dritten Runde des NIST-Signaturwettbewerbs, und der Bericht widmet diesem Verfahren viel Raum.

Der Preis liegt in den Sicherheitsannahmen. Es hat nicht die über Jahrzehnte getesteten NTRU- und SIS-Probleme übernommen, sondern verlässt sich auf das Gitterisomorphismusproblem und die one-more-SVP-Annahme, deren Forschungszeitraum relativ kurz ist.

Kurz vor Abschluss des Berichts entdeckten Straznickas und Weis von Anthropic, dass die Gitterkonstruktion von Hawk strukturelle Mängel aufweist: Die Dimension des SVP-Problems, das zur Wiederherstellung des Schlüssels tatsächlich gelöst werden muss, beträgt nur die Hälfte dessen, was die Designer angenommen hatten. Die Sicherheit des Schlüssels der Kandidatenparameter wurde erheblich geschwächt. Die Forscher führten einen vollständigen End-to-End-Schlüsselwiederherstellungsangriff auf die für die Kryptoanalyse verwendeten Herausforderungsparameter HAWK-256 durch; selbst nach einem Angriff konnten die offiziellen Vorschläge HAWK-512 und HAWK-1024 nicht realistisch angegriffen werden. Das Hawk-Team bestätigte die Wirksamkeit des Angriffs und zog das Verfahren aus dem NIST-Prozess zurück; das Team erklärte, dass, wenn die Parameter verdoppelt werden, um die Schwachstelle zu beheben, der ursprünglich stolz präsentierte Größenvorteil von Hawk vollständig verschwinden würde.

Der Bericht behält dennoch die Abschnitte zu Hawk bei, da dieser Angriff auf die algebraischen Eigenschaften eines bestimmten Zahlensystems abzielt und nicht die gesamte Designphilosophie in Frage stellt. Ob ein Redesign die Schwachstelle umgehen kann, ist noch ungewiss. Der Hawk-Vorfall belegt auch anschaulich, warum wir auf konservative Sicherheitsüberhänge bestehen: Ein Verfahren, das auch bei hervorragender Größe und Geschwindigkeit alle Standardisierungsrunden durchläuft, kann durch einen einzigen Artikel erheblich in seiner geschätzten Sicherheitsstufe herabgestuft werden.

Vergleichstabelle der Verfahren

Alle in der obigen Tabelle aufgeführten Verfahren (einschließlich SPHINCS+) sind zustandslose Signaturen: Der Unterzeichner muss keine früheren Signaturen aufzeichnen. Zustandsbehaftete Hash-Signaturen wie XMSS können kleinere Signaturgrößen erreichen, erfordern jedoch die Pflege eines Signaturstatus; siehe den Bericht über Hash-basierte Signaturen, um den Vergleich zu verstehen.

Es gibt noch viele Hindernisse für die Implementierung

Falcon fehlt ein verfügbares Schlüsselableitungsverfahren. Derzeit gibt es nur einen öffentlichen BIP-32-Stil Falcon-Ableitungsansatz, der die Basis des privaten Schlüssels neu zufällig macht, wodurch die Norm der Signatur drastisch erhöht wird und die On-Chain-Signatur auf etwa 23,7 Kilobyte anwächst. Außerdem erfüllt dieser Ansatz nicht die eigenen Sicherheitsanforderungen; wenn dieses Problem behoben wird, wird die Größe weiter ansteigen. Derzeit gibt es keine praktikable Implementierung der öffentlichen Schlüsselableitung für Falcon, was das wertvollste ungelöste Problem des Berichts darstellt.

Der Falcon-Standard ist noch nicht finalisiert. Obwohl NIST Falcon ausgewählt hat, wurde der FN-DSA-Entwurf noch nicht offiziell veröffentlicht. Erst nach Abschluss der Standardisierung wird es geprüfte Implementierungen, Testvektoren und Hardwareunterstützung geben. Eine breite Implementierung könnte die Risiken und Schwierigkeiten bei der Integration in die Bitcoin-Konsensschicht verringern. Wir empfehlen, auf die offizielle Veröffentlichung von FN-DSA zu warten; bis dahin bleibt Falcon in einem Zustand der Veränderung.

Falcon-WS-Variante: Diese Variante lockert interne Parameter und kompensiert dies durch Ablehnungssampling, wodurch die Gesamtgröße der Stufe 1 auf 1114 Bytes und die der Stufe 5 auf 2387 Bytes komprimiert wird, was im Vergleich zur Originalversion von Falcon eine weitere Größenreduktion darstellt. Diese Richtung hat Forschungswert, wird jedoch nicht in den offiziellen Standard aufgenommen und benötigt weitere kryptographische Analysen zur Validierung. Frühere Studien haben Schwächen im Beweis der starken Unverfälschbarkeit ihrer Ableitungsansätze festgestellt (die normale Unverfälschbarkeit bleibt unberührt).

Wird es in Zukunft bessere Verfahren geben? Abgesehen von den oben genannten Verfahren stammt die Fiat-Shamir-Serie ursprünglich aus BLISS von 2013, und die neuesten Ergebnisse von Gärtner auf der CRYPTO 2025-Konferenz basieren auf etablierten Annahmen und können in der Papiergröße mit Falcon konkurrieren. Der Grund, warum diese Serie schwer in der Praxis umzusetzen ist, liegt in den Sicherheitsproblemen bei der Implementierung: BLISS wurde aufgrund von nicht konstanten Zeit-Gauß-Abtastungen durch Seitenkanalangriffe kompromittiert; nachfolgende Verfahren haben dieses Risiko nicht vollständig gelöst, und die neuesten Ergebnisse weisen darauf hin, dass der Schutz während des Abtastens noch schwieriger ist. Solange diese Probleme nicht gelöst sind, haben solche Verfahren nur theoretische Anziehungskraft und sind nicht für die Implementierung geeignet.

Gitter-Signaturen und Hash-Signaturen können sich ergänzen. Gitter-Signaturen können als Komponenten eines hybriden Verfahrens dienen. Zum Beispiel verwendet SHRINCS derzeit einen zustandslosen Wiederherstellungspfad mit SPHINCS+-Signaturen in der Größe von mehreren KB; der Austausch gegen Falcon (oder Falcon-WS)-Signaturen würde die Größe verringern und die Verifizierung beschleunigen, wodurch die Kosten des seltenen Wiederherstellungspfads erheblich gesenkt werden, während die täglichen Nutzungskosten nicht beeinträchtigt werden.

Forschungsergebnisse

Die Vor- und Nachteile der Gitterkandidaten sind sehr klar: Hawk hat nach dem Angriff des Anthropic-Teams den Wettbewerb verlassen; Dilithium hat die geringste Implementierungskomplexität und ist das einzige Verfahren mit einer Forschungsbasis zur Schlüsselableitung, aber die Größe ist für die On-Chain-Kosten von Bitcoin nicht günstig; Falcon bietet eine kompakte Größe, schnelle Verifizierung und etablierte Sicherheitsannahmen; sein Hauptnachteil – die Fließkommaoperationen auf der Signaturseite – kann jedoch durch praktikable Ingenieurlösungen behoben werden. Wenn wir jetzt ein Gitter-Signaturverfahren für Bitcoin auswählen müssten, würden wir Falcon-1024 wählen.

In der gegenwärtigen Situation stimmen wir mit dem Bericht über Hash-basierte Signaturen überein: Der kurzfristige konservative Ansatz bleibt weiterhin die Hash-basierten Signaturen, da die Sicherheitsannahmen am ausgereiftesten sind, das Risiko am geringsten ist und sie als Übergangslösung geeignet sind. Nach der offiziellen Fertigstellung von FN-DSA, mit stabilen Normen, geprüften Codebasen und Hardware-Wallet-Unterstützung, wird Falcon im Vergleich zu rein hash-basierten Signaturen erhebliche Verbesserungen bieten; es könnte auch eine hybride Implementierung in Betracht gezogen werden, um die beiden Signatursysteme gegenseitig zu ergänzen.

Dieser Inhalt wird nur zu allgemeinen Informationszwecken bereitgestellt und stellt keine finanzielle, Anlage-, Rechts- oder Steuerberatung dar. Alle erwähnten Ereignisse, Prämien, Online-Aktionen oder zugehörige Informationen sollten nicht als Empfehlung, Aufforderung oder Einladung zum Kauf, Verkauf, Handel oder anderweitigem Umgang mit Krypto-Assets betrachtet werden. Krypto-Assets sind sehr volatil und können zu Verlusten führen. Die Verfügbarkeit von WEEX Services, Produkten und zugehörigen Aktionen kann je nach Region unterschiedlich sein. Sie sind dafür verantwortlich sicherzustellen, dass Ihre Teilnahme mit geltenden lokalen Gesetzen und Vorschriften übereinstimmt.