Technik › Wie viel?

Pedersen-Commitments

Wie man Beträge addiert, die niemand sieht, und prüft, dass die Bilanz stimmt

Kurz gesagt

Ein Betrag v wird im Punkt C = y·G + v·H versteckt, wobei y eine zufällige „Maske“ ist. Commitments lassen sich addieren: Die Summe der Commitments ist ein Commitment auf die Summe der Beträge. Das Netzwerk prüft, dass Σ inputs − Σ outputs − fee·H ein Commitment auf null ist, ohne einen einzigen Betrag zu erfahren.

Was ein Commitment ist

Ein Commitment ist ein „versiegelter Umschlag mit einer Zahl“. Es hat zwei Eigenschaften:

  • Verbergend (Hiding): Aus dem Umschlag lässt sich die Zahl nicht ablesen.
  • Bindend (Binding): Man kann den Umschlag nicht als eine andere Zahl öffnen.

Ein Pedersen-Commitment auf einer elliptischen Kurve:

C = y·G + v·H v – Betrag in atomaren Einheiten (1 XMR = 10¹² Einheiten), y – zufälliger Blinding-Faktor, G und H – zwei unabhängige Punkte

Ohne die Maske y hätten wir C = v·H, und der Betrag ließe sich leicht durch Ausprobieren finden (so viele Beträge gibt es nicht). Die Maske macht C ununterscheidbar von einem zufälligen Punkt.

Warum der zweite Generator H wichtig ist

H entsteht, indem man G auf einen Punkt hasht, deshalb kennt niemand ein k mit H = k·G. Kennte jemand k, könnte er ein Commitment „neu öffnen“: y·G + v·H = (y + k(v − v'))·G + v'·H – und Geld aus dem Nichts drucken. Genau auf der Unkenntnis von k beruht die Bindung.

Homomorphie: blind addieren

C₁ + C₂ = (y₁ + y₂)·G + (v₁ + v₂)·H

Die Summe zweier Umschläge ist ein Umschlag mit der Summe. So kann das Netzwerk die Erhaltung prüfen:

C_in (5 XMR)Betrag verborgen = C_out1 (3 XMR)an Empfänger + C_out2 (1,99)Wechselgeld + 0.01·HGebühr C_in − C_out1 − C_out2 − fee·H = (y_in − y₁ − y₂)·G + 0·H → ein Commitment auf null: ein Punkt der Form z·G

Bleibt zu beweisen, dass die Differenz wirklich die Form z·G hat (und nicht z·G + etwas·H). Es genügt, mit ihr als öffentlichem Schlüssel zu signieren: Die Signatur gelingt nur, wenn man z kennt und es keinen H-Anteil gibt. Die Gebühr ist öffentlich, ihr Commitment ist also einfach fee·H ohne Maske.

Pseudo-Outputs: wie das mit Ringen funktioniert

Es gibt einen Haken: Der Input ist ein Ring aus 16 Outputs, und wir können nicht sagen, wessen Commitment das echte ist. Die Lösung von RingCT ist das Pseudo-Output-Commitment C̃:

  1. für jeden Input erstellt der Sender ein neues Commitment C̃ = y'·G + v·H mit demselben Betrag, aber einer neuen Maske;
  2. die Masken werden so gewählt, dass Σ C̃ = Σ C_out + fee·H genau gilt (die Bilanz wird mit den Pseudo-Outputs geprüft);
  3. in CLSAG wird für jedes Ringmitglied bewiesen, dass C_i − C̃ für das echte Mitglied ein Commitment auf null ist: C_π − C̃ = (y − y')·G.

So beweist die Ringsignatur gleichzeitig den Besitz des Outputs und dass der Betrag des Pseudo-Outputs dem des echten Inputs entspricht.

Wie der Empfänger Betrag und Maske erfährt

Sender und Empfänger teilen das Geheimnis Hs(8rA ‖ i) (siehe Einmal-Adressen). Daraus leiten sie ab:

y = Hs( "commitment_mask" ‖ Hs(8rA ‖ i) )
amount_enc = v ⊕ Keccak( "amount" ‖ Hs(8rA ‖ i) )[0..8]

Der verschlüsselte Betrag (8 Bytes) steht in der Transaktion. Der Empfänger entschlüsselt v, berechnet y und prüft, dass y·G + v·H mit C auf der Blockchain übereinstimmt.

Was verhindert einen negativen Betrag?

Alle Arithmetik läuft modulo l. „−1“ ist l − 1, eine riesige Zahl. Man könnte einen Output über 1000 XMR und einen über „−999 XMR“ erstellen, die Bilanz würde stimmen, und 999 XMR entstünden aus dem Nichts. Commitments sehen das nicht. Deshalb kommt jeder Output mit einem Range Proof.