Curve Trees, Helios und Selene

Ein Merkle-Baum mit Punkten statt Hashes, in dem der Beweis eines Pfads nur Kilobytes braucht

Merkle-Baum zur Auffrischung

Ein Merkle-Baum hasht Daten paarweise (oder in Gruppen), dann die Hashes, bis zu einer einzigen Wurzel. Um zu beweisen, dass ein Element im Baum ist, zeigt man den Pfad – die Geschwister auf jeder Ebene. Der Pfad hat die Länge log n.

Wir müssen den Pfad aber ohne Preisgabe von Wissen beweisen – weder das Blatt noch die Geschwister zeigen. Das heißt, „einen Hash berechnen“ in einen arithmetischen Schaltkreis zu kodieren und den Schaltkreis zu beweisen. Gewöhnliche Hashes (Keccak, SHA) sind in solchen Schaltkreisen sehr teuer: Zehntausende Constraints pro Hash.

Die Idee der Curve Trees

Verwende ein Vektor-Pedersen-Commitment als „Hash“:

Für unseren Zweck ist das ein guter Hash (eine Kollision zu finden ist so schwer wie der diskrete Logarithmus), und in einem arithmetischen Schaltkreis ist er fast kostenlos – wenn die Zahlen xᵢ Skalare der Kurve sind, auf der die Gᵢ liegen.

Das Problem: Die Kinder sind Punkte auf der Kurve E₁, ihre Koordinaten sind also Elemente des Grundkörpers von E₁. Um sie als Skalare zu verwenden, brauchen wir eine Kurve E₂, deren Skalarkörper gleich dem Grundkörper von E₁ ist. Auf der nächsten Ebene umgekehrt. Ein solches Paar nennt man einen Zyklus von Kurven.

Helios und Selene

Für Monero wurde ein spezieller Zyklus gewählt, der an Ed25519 „verankert“ ist: Die Koordinaten von Ed25519-Punkten liegen im Körper F_p, p = 2²⁵⁵ − 19, und eine Kurve des Zyklus (Selene) hat genau dieses F_p als Skalarkörper. So lassen sich die Blätter (Koordinaten von O, I, C auf Ed25519) direkt auf Selene „hashen“, dann die Koordinaten der Selene-Punkte auf Helios und so weiter, abwechselnd.

Die Namen stammen von den griechischen Gottheiten der Sonne (Helios) und des Mondes (Selene): zwei Kurven, die einander „umkreisen“.

Wie der Pfad bewiesen wird

Für jede Ebene zeigt der Beweisende nicht den Elternpunkt selbst, sondern seine Rerandomisierung (den Punkt plus ein zufälliges Vielfaches eines anderen Generators) und beweist in einem Schaltkreis über der jeweiligen Kurve:

1. „Ich kenne die Kinder, von denen eines der rerandomisierte Punkt der vorherigen Ebene ist“;
2. „diese Kinder ergeben, kombiniert mit den Generatoren, den (rerandomisierten) Elternknoten“.

Um Kurvenoperationen im Schaltkreis effizient zu prüfen, werden Divisoren verwendet (die Technik von Liam Eagen): Statt einer schrittweisen Skalarmultiplikation wird eine Eigenschaft einer rationalen Funktion auf der Kurve bewiesen, was viel billiger ist. Siehe Generalized Bulletproofs und Divisoren.

Alle Ebenen über der einen Kurve werden durch einen Generalized Bulletproof bewiesen, die über der anderen durch einen zweiten. Das Ergebnis sind zwei Beweise, deren Größe mit der Tiefe des Baums wächst, also logarithmisch mit der Anzahl der Outputs.

Den Baum aktualisieren

Wenn ein Output die Sperre von 10 Blöcken hinter sich hat, fügt der Node ihn dem Baum hinzu und berechnet den Pfad zur Wurzel neu. Ein Vektor-Commitment lässt sich inkrementell aktualisieren: Ein Kind hinzuzufügen heißt, x·Gᵢ zum Elternknoten zu addieren, ohne die anderen neu zu berechnen. Bei einer Reorganisation der Chain werden Änderungen zurückgenommen.