Technik › FCMP++

Input-Rerandomisierung

Wie man einen Output aus dem Baum ausgibt, ohne zu zeigen, welchen

Kurz gesagt

In FCMP++ ist ein Transaktions-Input kein Verweis auf einen Output, sondern eine „übermalte“ Kopie davon: Zu jedem Punkt des Outputs wird ein zufälliges Vielfaches eines eigenen Generators addiert. Die entstehenden Punkte sind von zufälligen nicht zu unterscheiden, aber der Ausgebende kennt die „Farbe“ und kann beweisen: (1) entfernt man sie, erhält man irgendein Blatt des Baums, und (2) er kennt den Schlüssel dieses Blatts.

Warum überhaupt rerandomisieren

Ein Mitgliedschaftsbeweis beweist die Aussage „Punkt X ist ein Blatt des Baums“. Veröffentlichen wir den Output O selbst, gibt es nichts mehr zu verbergen: Jeder sieht, welcher Output ausgegeben wird. Veröffentlichen wir nichts, gibt es nichts, woran man das Key Image und das Commitment des Betrags binden könnte. Wir brauchen den Mittelweg: etwas veröffentlichen, das mathematisch mit dem Output verbunden ist, wobei nur der Ausgebende die Verbindung sieht.

Dieser Trick ist die Rerandomisierung. In RingCT war ein ähnlicher Trick der Pseudo-Output C̃: dasselbe Betrags-Commitment, aber mit neuer Maske. FCMP++ wendet dieselbe Idee auf jeden Teil des Outputs an.

Woraus ein Blatt besteht

leaf = ( O.x, I.x, C.x ) x-Koordinaten von drei Ed25519-Punkten: der Output-Schlüssel O, der Key-Image-Generator I = Hp(O), das Commitment C

O und C kommen direkt aus dem Output auf der Chain; I berechnet der Node, wenn er den Output in den Baum aufnimmt. In den Baum kommen nur Koordinaten (Zahlen), nicht die Punkte selbst – so lassen sie sich auf der nächsten Ebene leichter „hashen“ (siehe Curve Trees).

Die Formeln der Rerandomisierung

Der Ausgebende wählt vier zufällige Skalare r_o, r_i, r_r_i, r_c und veröffentlicht:

Veröffentlicht	Formel	Was es verbirgt
Õ	`O + r_o·T`	welcher Output-Schlüssel ausgegeben wird
Ĩ	`I + r_i·U`	den Key-Image-Generator dieses Outputs
R	`r_i·V + r_r_i·T`	ein Commitment auf `r_i` – nötig, um Ĩ mit dem Key Image zu verknüpfen
C̃	`C + r_c·G`	welches Betrags-Commitment ausgegeben wird (wie der Pseudo-Output in RingCT)

T, U, V sind feste Generatoren, die durch Hashen auf einen Punkt entstehen; niemand kennt ihre Logarithmen bezüglich G oder untereinander. Das ist entscheidend: Kennte jemand T = t·G, könnte er eine Komponente in eine andere „ummalen“.

Was über diese Punkte bewiesen wird

Die Transaktion enthält zwei Beweise, die sich die Arbeit teilen:

Der Mitgliedschaftsbeweis (in einem arithmetischen Schaltkreis über Helios/Selene) beweist: Es gibt im Baum mit der Wurzel ρ ein Blatt (O, I, C), und es gibt r_o, r_i, r_r_i, r_c, sodass die veröffentlichten Õ, Ĩ, R, C̃ den Formeln oben folgen.
SA+L (außerhalb des Schaltkreises, auf Ed25519) beweist: Der Ausgebende kennt x, y mit Õ = x·G + (y + r_o)·T, und das Key Image ist L = x·I – nur anhand der veröffentlichten Õ, Ĩ, R.

Beachte: Der Mitgliedschaftsbeweis weiß nichts über Spend Keys, und SA+L weiß nichts über den Baum. Diese Trennung erlaubt es zum Beispiel, den Mitgliedschaftsbeweis an ein anderes Gerät zu delegieren, ohne ihm das Recht zum Ausgeben zu geben.

Warum das sicher ist

Verbergen: r_o·T ist ein zufälliger Punkt der Untergruppe, also ist Õ gleichverteilt, egal wie O aussieht. Õ mit Outputs zu vergleichen ist sinnlos – das Tool zeigt das.
Keine falschen Blätter: Um von einem ausgedachten Punkt „die Farbe zu entfernen“ und auf einem echten Blatt zu landen, müsste man einen diskreten Logarithmus zwischen Generatoren lösen.
Kein Austausch des Betrags: Die Bilanz wird auf C̃ geprüft, und der Mitgliedschaftsbeweis garantiert, dass sich C̃ vom echten C des Blatts nur um ein Vielfaches von G unterscheidet – der Betrag ist also derselbe.
Keine Doppelausgabe: L = x·I hängt nur vom Output ab, nicht von r; eine zweite Ausgabe ergibt dasselbe L.