Zusammenfassung der Lamport-Signaturen
Abstract: Wir erläutern Lamport-Signaturen, ein hash-basiertes, quantensicheres digitales Signaturschema, das 1979 entwickelt wurde. Damit zeigen wir, wie einfach quantensichere Signaturen sein können und dass sie keine komplexen Mathematiken erfordern. Wenn Bitcoin ein quantensicheres Signatursystem einführen möchte, könnten hash-basierte Signaturen der geeignete Weg sein. Es gibt keinen konkreten Grund zur Annahme, dass Quantencomputer eine unmittelbare oder mittelfristige Bedrohung für Bitcoin darstellen. Unserer Meinung nach ist der erste Schritt zur Minderung der vermeintlichen quantenbedingten Risiken, den Nutzern die Möglichkeit zu geben, Bitcoin auf quantensichere Weise auszugeben. Sobald eine solche Wahl besteht, kann die wirtschaftliche Nutzerakzeptanz als Treiber für die nächsten Schritte fungieren.
Aktuelle Diskussion über Quantenrisiken bei Bitcoin
Die Diskussion über die Gefahren von Quantencomputern für Bitcoin ist derzeit sehr angesagt. Kürzlich fand eine Konferenz in San Francisco zum Thema „Presidio Bitcoin“ statt. Wir sollten versuchen, so rational wie möglich zu sein. Wir sind nicht sicher, dass Quantencomputing in absehbarer Zeit konkrete Probleme verursachen wird. Dennoch erkennen wir, dass viele diese Thematik besorgniserregend finden und dass Entwicklungen im Bereich der Quanten-Technologie theoretisch unerwartet schnell geschehen könnten. Eine allgemeine Befürchtung ist, dass Bitcoin auf ein neues, kompliziertes post-quantum kryptografisches digitales Signaturschema umsteigen muss. Es gibt viele neuartige, klangvolle Ansätze, über die man lesen kann, darunter HAWK, SQI, Falcon und CRYSTALS. Doch was, wenn wir das falsche Schema auswählen? Im Jahr 2023 gab es Berichte, dass ein neues post-quantum Schema, der „SIKE-Algorithmus“, auf klassische nicht-quantenbasierte Weise geknackt wurde. Wer kann sagen, ob diese neuen Verfahren wirklich quantensicher sind?
Einfachheit der Lamport-Signaturen
Wenn Bitcoin sich jedoch für ein Upgrade auf ein post-quantum Signaturschema entscheidet, müssen wir nicht zwangsläufig auf komplizierte und risikobehaftete Neuheiten setzen. Denken wir daran, dass das digitale Signaturschema von Bitcoin, der Elliptic Curve Digital Signature Algorithm (ECDSA), potenziell quantenanfällig ist – aufgrund eines Faktorisierungsangriffs mithilfe von Shor’s Algorithmus. Hash-Funktionen hingegen sind größtenteils quantensicher. Hash-Funktionen wie SHA256 sind zwar quantenanfällig basierend auf Grover’s Algorithmus, was bedeutet, dass die Sicherheit um einen Quadratwurzelfaktor verringert werden kann. Anstelle von 256 Bit Sicherheit wären also nur 128 Bit Sicherheit gegeben. Dies scheint größtenteils akzeptabel, und man kann immer eine Hash-Funktion mit größerem Output verwenden, um die Sicherheit zu erhöhen, falls nötig.
Wie funktionieren Lamport-Signaturen?
Im folgenden Beispiel nehmen wir an, die Lamport-Signaturen verwenden den SHA256 Hash-Algorithmus, doch sie funktionieren mit nahezu jedem Hash-Algorithmus. Bei Lamport-Signaturen ist der private Schlüssel nicht einfach eine zufällige 256-Bit-Zahl wie beim ECDSA. Stattdessen besteht der private Schlüssel aus zwei Mengen von jeweils 256 Zufallszahlen. Diese zwei Mengen sind als Menge A und Menge B definiert. Daher ist der private Schlüssel 2 * 256 * 256 = 131.072 Bits = 16,3 KB. Jede dieser 512 Zufallszahlen von 256 Bit wird gehasht, und diese Hash-Ausgaben bilden den öffentlichen Schlüssel, der somit ebenfalls 16,3 KB groß ist. Eine Bitcoin-Adresse könnte dann eine SHA256-Hash des Zusammenführens aller Strings darstellen, die den öffentlichen Schlüssel ausmachen.
Verfahrensweise beim Signieren
Um eine Nachricht zu signieren, wird zunächst die Nachricht gehasht, wiederum mit SHA256, und die binary Ausgabe wird erstellt. Basierend auf jedem Bit der binären Ausgabe wird entschieden, welcher Teil des privaten Schlüssels in die Signatur aufgenommen wird. Ein Bitwert von Null entspricht Menge A, während ein Bitwert von Eins Menge B entspricht. Das erste Bit in der Hash-Ausgabe entspricht der ersten Zahl im privaten Schlüssel, das zweite Bit der zweiten Zahl und so weiter, sodass die Signatur eine zufällige Auswahl von genau 50 % des gesamten privaten Schlüssels darstellt.
Überprüfung der Signatur
Um die Nachricht zu verifizieren, muss der Prüfer lediglich die Nachricht hashen und die entsprechenden Teile des öffentlichen Schlüssels mit derselben Methodik auswählen. Dann muss der Prüfer jede Zahl in der Signatur hashen, um festzustellen, ob sie mit diesen 256 Teilen des öffentlichen Schlüssels übereinstimmt. Bei einer vollständigen Übereinstimmung ist die Signatur gültig. Der Unterzeichner musste den vollständigen privaten Schlüssel kennen, da die Hash-Funktion zufällig ist und nicht vorhergesagt werden kann, welche Teile aus Menge A oder Menge B benötigt werden, bis eine bestimmte Nachricht gewählt wird. So wird verständlich, wie sicher dieses Verfahren ist und dass die Verifikation recht einfach auszuführen ist.
Einschränkungen der Lamport-Signaturen
Nur einmalige Verwendung
Ein wesentliches Manko dieses Verfahrens ist, dass jede Signatur nur einmal verwendet werden kann. Nachdem eine Transaktion auf der Blockchain signiert wurde, ist 50 % des privaten Schlüssels veröffentlicht. Wird dieselbe Signatur erneut verwendet, werden weitere 50 % des Schlüssels offengelegt. Statistisch gesehen sind dann 75 % des gesamten privaten Schlüssels öffentlich verfügbar. Es ist einfach zu erkennen, wie die Sicherheit schnell allmählich sinkt, jedes Mal, wenn eine Signatur gesetzt wird. Dies bedeutet, dass Nutzer möglicherweise keine Adressen wiederverwenden können, was zwar positiv für die Privatsphäre ist, jedoch einige Herausforderungen mit sich bringt:
- Nutzer sind daran gewöhnt, Adressen wiederzuverwenden
- Was passiert, wenn jemand Mittel an eine bereits verwendete Adresse sendet?
- Wie würde RBF (Replace By Fee) funktionieren? Es könnte ein zusätzlicher Input hinzugefügt werden, und nur dieser könnte signiert werden, was jedoch Probleme bei der Kontrolle von Coins erzeugt.
Mathematische Einschränkungen
Ein weiterer Nachteil ist, dass man keine raffinierten mathematischen Verfahren wie bei ECDSA anwenden kann. So nutzt BIP-32 beispielsweise die Eigenschaften von ECDSA, um die Verwendung von „xpubs“ zu ermöglichen, was mit reinem Hashing nicht möglich ist.
Größe der Signaturen
Ein weiteres Problem ist die massive Größe der Signaturen und öffentlichen Schlüssel. Mit einer Signatur von 8 KB und einem öffentlichen Schlüssel von 16 KB summiert sich dies auf 24 KB. Ein Bitcoin-Block könnte dann nur wenige Transaktionen enthalten, anstelle der Tausenden von Transaktionen, die wir heute kennen. Dieses Problem scheint jedoch bei allen quantensicheren Verfahren in gewissem Maße vorhanden zu sein.
Alternative: SPHINCS+
Wir analysieren hier nur das ursprüngliche einfache Lamport-Signaturschema, um zu veranschaulichen, wie ein einfaches Signaturverfahren, das ausschließlich auf Hashes basiert und somit quantensicher ist, durchaus möglich ist. Wenn Bitcoin ein hash-basiertes Signatursystem einführen möchte, gibt es modernere Optionen. 1982 veröffentlichte Winternitz eine Variante des Lamport-Schemas. Das Winternitz-Schema beinhaltete das Aufteilen des Hashes der Nachricht in mehrere Teile und deren Zuordnung zu verschiedenen Teilen des privaten Schlüssels; dabei gab es weitere iterative Hash-Schritte. 2011 wurde eine neuere Variante XMSS veröffentlicht und 2015 erschien eine weitere Variante eines hash-basierten Signaturschemas, SPHINCS.
Vorteile von SPHINCS+
SPHINCS+ ermöglicht viel kleinere Signaturgrößen und private Schlüssel, die mehrmals verwendet werden können. Diese Verfahren beinhalten eine Merkle-Baumstruktur, wobei die Spitze des Baumes ein „globaler öffentlicher Schlüssel“ ist, sodass der öffentliche Schlüssel in der Regel nur 32 Byte groß ist. Wenn Bitcoin ein post-quantum Signaturschema annimmt, könnten diese hash-basierten Verfahren mit Merkle-Bäumen gewählt werden, da Merkle-Bäume bereits weitreichend in Bitcoin verwendet werden und daher bequem angewendet werden können. Der Mitbegründer von Lightning Labs, Olaoluwa Osuntokun, hielt auf der kürzlichen Quantenkonferenz in San Francisco einen Vortrag über SPHINCS+ Signaturen, in dem er erläuterte, dass es mehrere Anpassungsmöglichkeiten gibt, um die gewünschten Eigenschaften je nach den Prioritäten zu erreichen. Die anpassbaren Parameter umfassen die Hash-Kosten zur Erstellung der Signaturen, die Hash-Kosten zur Verifizierung der Signaturen, die sichere Wiederverwendbarkeit und die Größe der Signaturen. Olaoluwa sagte, dass die Parameter so eingestellt werden könnten, dass Signaturen bis zu 2 KB klein sein könnten, was im Vergleich zu den aktuellen Bitcoin-Signaturen von etwa 70 Bytes immer noch recht groß ist.
Schlussfolgerung
Wir haben kein starkes Verständnis für das Niveau des Quantenrisikos für ECDSA, noch haben wir konkrete Daten. Wir glauben, dass das von Bitcoin verwendete ECDSA-Schema voraussichtlich noch viele Jahrzehnte sicher bleibt. Daher könnte ein rationaler Ansatz sein, bis zu konkreten Beispielen der Fähigkeiten von Quantencomputern nichts zu unternehmen. Es könnte jedoch sinnvoll sein, darüber nachzudenken, was erforderlich wäre, um Bitcoin quantensicher zu machen. Der erste Schritt besteht darin, eine Möglichkeit zu schaffen, Bitcoin auf eine quantensichere Weise auszugeben, die ein hash-basiertes Signaturschema sein könnte. Unsere Ansicht ist, dass es wenig Sinn macht, einen Plan zur Einfrierung anfälliger Coins ernsthaft zu diskutieren, bis eine quantensichere Ausgabemöglichkeit zur Verfügung steht und weit verbreitet genutzt wird. Sollte eine quantensichere Ausgabemöglichkeit hinzugefügt und die Nutzerakzeptanz stark sein, wäre es sinnvoll, eine solche Diskussion zu führen.
Natürlich gibt es viele Probleme zu klären, wenn es darum geht, ein hash-basiertes Signaturschema hinzuzufügen. Wie können wir eine Akzeptanz bei wesentlich größeren Signaturgrößen erreichen, da diese Transaktionen erheblich teurer sind? Müssen wir die Blockgewicht-Ermäßigung und die Blockgrößenobergrenze erneut überprüfen? Alternativ könnten wir wirtschaftliche Akzeptanz durch Wert anstelle von Transaktions- oder UTXO-Zahl anstreben. Vielleicht könnten diese quantensicheren Verfahren zuerst von Einrichtungen übernommen werden, die Tausende von Bitcoin halten, wie ETF-Anbieter oder Bitcoin-Treasury-Unternehmen, die kaum jemals Transaktionen durchführen. Für diese Entitäten wäre die zusätzliche Transaktionsgebühr nicht signifikant. Einzelne Nutzer könnten ihre Ersparnisse in quantensicheren Ausgaben halten, was diese 2 KB großen Signaturen erfordert, während ihre alltäglichen Ausgaben möglicherweise quantenanfällig bleiben. Diese täglichen Ausgaben könnten relativ sicher gestaltet werden, indem P2WPKH-Ausgaben genutzt und die Wiederverwendung von Adressen vermieden wird, falls gewünscht. Dabei wird wieder Hashing als quantenbasierte Verteidigung verwendet, wobei die Nutzer nur während der Bestätigung der Transaktion gefährdet sind.
Sobald eine erhebliche wirtschaftliche Akzeptanz besteht, könnte es einfacher sein, über die nächsten Schritte zur Minderung der Quantenrisiken zu sprechen. Unserer Ansicht nach sollte der Weg nach vorne, sobald eine quantensichere Einlösungsmöglichkeit besteht, letztendlich von den wirtschaftlichen Nutzern vorgegeben werden. Wenn sie die quantensicheren Ausgaben nicht verwenden, bleibt dies ihre Entscheidung. Wenn die Akzeptanz stark ist, können wir möglicherweise über andere umstrittene Schritte sprechen, wie das Einfrieren von Coins, das Ändern der Blockgewichtgrenze, quantensichere Erholungsschemata für BIP-39 Seed-Phrasen oder welche Schritte auch immer als notwendig erachtet werden. Lassen wir die Inhaber entscheiden.
