Ringsignaturen

Wie man beweist: "Mir gehört einer dieser Schlüssel", ohne zu sagen, welcher

Zuerst – eine einfache Schnorr-Signatur

Um Ringe zu verstehen, sieh dir zuerst an, wie man die Kenntnis eines Schlüssels x für P = x·G beweist:

1. Der Unterzeichner wählt ein zufälliges α und berechnet α·G.
2. Er berechnet die Challenge c = Hs(message ‖ α·G).
3. Er berechnet die Antwort s = α − c·x. Die Signatur ist (c, s).
4. Der Prüfer rekonstruiert s·G + c·P = (α − cx)·G + c·x·G = α·G und prüft, dass Hs(message ‖ α·G) = c.

Ohne x zu kennen, findet man kein s für ein gegebenes c: c hängt von α·G ab, das festgelegt sein muss, bevor man c erfährt.

Die Ring-Idee: die Kette der Challenges schließen

Jetzt haben wir n öffentliche Schlüssel P₀ … Pₙ₋₁ und kennen den Schlüssel nur zu einem, sagen wir Pπ. Der Trick: Jede Challenge wird aus dem vorherigen Glied berechnet, und die Kette schließt sich zu einem Ring.

1. An der Position π des echten Schlüssels nimm ein zufälliges α und berechne die nächste Challenge: c_{π+1} = Hs(m ‖ α·G).
2. Wähle für jeden folgenden (fremden) Schlüssel ein zufälliges sᵢ und berechne c_{i+1} = Hs(m ‖ sᵢ·G + cᵢ·Pᵢ). Geh so einmal um den Ring.
3. Zurück bei π kennst du jetzt c_π. Damit sich der Ring schließt, muss s_π·G + c_π·P_π = α·G gelten, also s_π = α − c_π·x. Das lässt sich nur mit Kenntnis von x berechnen.
4. Signatur: (c₀, s₀, s₁, …, sₙ₋₁).

Der Prüfer beginnt bei c₀, durchläuft jedes Glied mit derselben Formel und prüft, dass er wieder beim selben c₀ ankommt. Alle Glieder sehen gleich aus – an der Signatur erkennt man nicht, wo das „Schließen“ stattfand.

Verknüpfbarkeit: LSAG

Eine einfache Ringsignatur verhindert nicht, dass derselbe Output in verschiedenen Ringen zweimal ausgegeben wird. Deshalb verwendet Monero eine verknüpfbare Signatur: Der Unterzeichner veröffentlicht ein Key Image I = x·Hp(P_π) und beweist in jedem Glied zusätzlich, dass dasselbe x I und Hp(Pᵢ) verbindet:

Zwei Verwendungen desselben Schlüssels ergeben dasselbe I – und das Netzwerk lehnt die zweite Ausgabe ab.

MLSAG → CLSAG

In RingCT muss man pro Ringmitglied nicht eine, sondern zwei Aussagen beweisen: die Kenntnis des Output-Schlüssels und dass die Differenz der Commitments ein Commitment auf null ist (siehe RingCT). Anfangs (2017) geschah das mit MLSAG – im Grunde zwei zusammengeklebte Ringe: zwei s-Werte pro Ringmitglied.

Im Oktober 2020 (Hard Fork v13) wurde es durch CLSAG (Concise LSAG) ersetzt: Die zwei Schlüssel einer Position werden über eine zufällige Linearkombination mit Hash-Koeffizienten zu einem zusammengefasst. Ein s pro Ringmitglied. Die Signatur wurde etwa 25 % kleiner und schneller zu prüfen.

Geschichte der Ringgröße

Warum fest? Würde jeder seine eigene wählen, wäre eine ungewöhnliche Ringgröße ein Fingerabdruck der Wallet.

Warum nicht 1000?

Größe und Prüfzeit von CLSAG wachsen linear mit der Ringgröße. Ein Ring mit 1000 Mitgliedern bedeutet ~32 KB pro Input und eine Node-Synchronisation, die Dutzende Male langsamer ist. Schemata mit logarithmischer Größe (Triptych, Arcturus, Seraphis) wurden erforscht, aber am Ende wählte Monero die radikale Variante – FCMP++, bei der der „Ring“ die ganze Blockchain ist.