Generalized Bulletproofs und Divisoren

Worauf der Beweis des Baumpfads beruht – ohne Trusted Setup

Was ein „arithmetischer Schaltkreis“ ist

Jede Berechnung lässt sich in elementare Schritte „zwei Zahlen multiplizieren“ und „mit Koeffizienten addieren“ in einem endlichen Körper zerlegen. Eine Menge solcher Schritte ist ein arithmetischer Schaltkreis. Ein Zero-Knowledge-Beweis zeigt „Ich kenne Werte für alle Leitungen des Schaltkreises, sodass alle Gleichungen gelten“, ohne die Werte preiszugeben.

Bei Bulletproofs ist der Schaltkreis einfach und fest: „Diese 64 Zahlen sind Bits, und ihre Summe ergibt den Betrag.“ Bei FCMP++ ist er komplexer: Auf jeder Ebene des Baums muss geprüft werden, dass das gewählte Kind unter den Kindern des Knotens ist und dass der Knoten korrekt aus ihnen berechnet wurde.

Generalized Bulletproofs

Gewöhnliche Bulletproofs nehmen einzelne Pedersen-Commitments als Eingabe. Generalized Bulletproofs (Eagen, Kamp, Parker u. a.) erlauben, Vektor-Commitments in den Schaltkreis einzuspeisen – ein Punkt legt viele Zahlen auf einmal fest. Genau das braucht der Baum: Der „Hash“ eines Knotens ist ein Vektor-Commitment auf die Koordinaten seiner Kinder (siehe Curve Trees). Der Schaltkreis erhält den Knoten als Eingabe und kann Aussagen über seinen Inhalt treffen.

Dieselben Eigenschaften wie bei Bulletproofs:

• kein Trusted Setup;
• die Beweisgröße wächst logarithmisch mit der Größe des Schaltkreises;
• die Prüfung ist linear in der Größe des Schaltkreises, lässt sich aber gut bündeln – viele Beweise zusammen zu prüfen ist billiger als einzeln.

Das Problem: Skalarmultiplikation im Schaltkreis

Die Rerandomisierung erfordert, im Schaltkreis etwas wie Õ = O + r_o·T zu prüfen. Einen Punkt „frontal“ mit einem 255-Bit-Skalar zu multiplizieren heißt Hunderte Punktverdopplungen und -additionen, jede mit mehreren Körpermultiplikationen. Das sind Tausende Constraints pro Operation, und der Beweis würde riesig.

Divisoren: prüfen statt rechnen

Die Idee von Liam Eagen („Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity“): Um sicherzustellen, dass die Punkte P₁ … Pₙ sich zu null addieren, muss man sie nicht addieren. Es genügt, eine rationale Funktion f auf der Kurve vorzulegen, deren Nullstellen genau in diesen Punkten liegen (ihr Divisor), und eine algebraische Identität an einem zufälligen Punkt zu prüfen (einer Challenge des Prüfers).

Die Multiplikation r·T wird als Summe Σ bᵢ·(2ⁱ·T) über die Bits von r geschrieben, also als Summe von Punkten – und mit einem Divisor geprüft. Die Zahl der Constraints sinkt etwa um eine Größenordnung.

Zwei Schaltkreise – zwei Kurven

Die Ebenen des Baums wechseln zwischen Selene und Helios. Die Arithmetik jeder Ebene ist im Körper einer der Kurven natürlich, daher besteht der Mitgliedschaftsbeweis aus zwei Generalized Bulletproofs: einer über Selene (Selene-Ebenen und die Prüfung der Rerandomisierung des Blatts, dessen Koordinaten Elemente des Ed25519-Körpers sind), der andere über Helios. Sie sind über gemeinsame rerandomisierte Knoten verbunden.

Größe und Kosten

Die Beweisgröße hängt von der Tiefe des Baums und der Breite der Knoten ab. Bei Hunderten Millionen Outputs und Knoten mit Dutzenden Kindern beträgt die Tiefe nur wenige Ebenen. Grob gesagt braucht ein FCMP++-Input einige Kilobyte, und die Prüfung ist eine Größenordnung teurer als bei CLSAG; die Entwickler optimieren beides weiter (Batch-Verifikation, Beweise für mehrere Inputs). Genaue Zahlen stehen in den Benchmark-Berichten zum Release.