Technik › Wer hat gesendet?

Key Image

Der Fingerabdruck, den ein Output beim Ausgeben hinterlässt – genau einmal

Kurz gesagt

Das Key Image I = x·Hp(P), wobei P der Einmalschlüssel des Outputs und x sein privater Schlüssel ist. Für einen bestimmten Output ist das Key Image immer gleich, verrät aber nicht, um welchen Output es sich handelt. Das Netzwerk speichert alle Key Images und lehnt eine Transaktion mit einem wiederholten ab.

Das Problem der Doppelausgabe

Bei Bitcoin sind Doppelausgaben leicht zu erkennen: Jeder Input zeigt direkt auf den Output, den er ausgibt, und ein Node merkt sich den Output als ausgegeben (das UTXO-Set). Bei Monero zeigt ein Input auf 16 Outputs, und welcher echt ist, ist unbekannt. „Den ausgegebenen Output markieren“ ist also unmöglich. Wir brauchen eine Möglichkeit, eine Ausgabe zu markieren, ohne zu verraten, was ausgegeben wurde.

Die Lösung

I = x · Hp(P)

Warum das funktioniert:

Deterministisch. x und P sind für einen Output fest, also ist I eindeutig. Den Output erneut auszugeben heißt, dasselbe I zu veröffentlichen.
Nicht verknüpfbar. Um zu prüfen, ob I zu P passt, braucht man x: Ein Außenstehender sieht zwei „zufällige“ Punkte Hp(P) und I und kann die Verbindung nicht herstellen (ein Diffie-Hellman-Problem).
Nicht fälschbar. Die verknüpfbare Ringsignatur beweist, dass I aus demselben x berechnet wurde wie einer der Schlüssel im Ring.

Warum Hp(P) und nicht einfach G? Dann wäre I = x·G = P – das Key Image wäre gleich dem öffentlichen Schlüssel des Outputs, und die Ausgabe wäre sofort sichtbar. Hp liefert einen Punkt, dessen Logarithmus niemand kennt – eine „zweite Basis“, die für jeden Output einzigartig ist.

Die Untergruppenprüfung: der Fehler von 2017

Ed25519 hat 8-mal mehr Punkte als die Untergruppe von G. Addiert man zu I einen Punkt kleiner Ordnung T (mit 8·T = 0), erhält man einen anderen Punkt I' = I + T, und unter bestimmten Bedingungen war die Ringsignatur trotzdem gültig. Ein Output – bis zu 8 verschiedene Key Images – bis zu 8 Ausgaben. 2017 wurde dieser Fehler im ursprünglichen CryptoNote-Code gefunden; Monero behob ihn vor einer Ausnutzung, Bytecoin dagegen wurde ausgenutzt.

Die Korrektur: Der Node prüft, dass l·I = 0 gilt, also dass I in der richtigen Untergruppe liegt.

Key Images und View-only-Wallets

Um zu wissen, ob dein Output ausgegeben ist, berechnet die Wallet sein Key Image und sucht es auf der Blockchain. Dafür braucht sie x = Hs(8aR ‖ i) + b – also den Spend Key. Deshalb sieht eine View-only-Wallet keine Ausgaben und zeigt ein zu hohes Guthaben an. Der Ausweg ist, Key Images aus der vollständigen Wallet zu exportieren. Carrot fügt dafür einen eigenen Schlüssel hinzu.

Key Images in FCMP++

In FCMP++ bleibt das Key Image: L = x·Hp(O). Was sich ändert, ist, wie seine Verbindung zum Output bewiesen wird – statt eines Rings ein Mitgliedschaftsbeweis im Baum aller Outputs. Eine wichtige Folge: Alle bereits in RingCT-Transaktionen veröffentlichten Key Images behalten ihre Bedeutung – ein alter Output kann nach dem Umstieg nicht ein zweites Mal ausgegeben werden.