# Rekursion und Abwicklung

> Wie aus einem Basisbeweis aus Hunderten von Shards ein einziger Groth16-Beweis wird, den ein Contract prüft. Apogee beim Beweisen seines eigenen Verifiers, die Tapes, die das günstig machen, das über einen Baum verkettete Transkript und Pairings, die gefaltet werden, bis nur eines übrig bleibt.

Ein Basisbeweis eines Ethereum-Blocks besteht aus 207 Shard-Beweisen: 14,5 MB, jeder Shard ein GKR-Beweis mit seinen Commitments und einer Mercury-Öffnung, die in einer Pairing-Prüfung endet. Ein Contract kann nichts davon direkt prüfen. Die Rekursion komprimiert ihn, und die Art, wie sie das tut, ist nach der GKR-Engine selbst die folgenreichste Designentscheidung.

## Der Basisbeweis bleibt unberührt

Die erste Entscheidung betrifft das, was die Rekursion *nicht* tut. Kein Basisschlüssel, keine Basisaussage und kein Basisbeweis ändert sich, um die Rekursion möglich zu machen: Ein Blatt verifiziert Basis-Shards genau so, wie es ein nativer Verifier täte. Alles, was die Rekursion braucht, wird oberhalb des Basisbeweises hinzugefügt, nie in ihm. Ein Block lässt sich aus denselben Bytes nativ verifizieren, rekursiv verarbeiten oder beides.

## Apogee beweist seinen eigenen Verifier

Ein **Knoten** des Baums ist Apogee beim Beweisen eines Verifier-Programms. Ein **Blatt** verifiziert eine Reihe aufeinanderfolgender Basis-Shards, von `from` bis `to`; ein innerer **Knoten** verifiziert zwei bis vier Kinder, jedes ein vollständiger Beweis eines Blatt- oder Knotenprogramms; die **Wurzel** deckt jeden Basis-Shard ab. Jeder Knoten wird von demselben Streaming-Prover bewiesen wie ein Basisblock.

Den Rust-Verifier als RISC-V-Befehle auszuführen würde funktionieren und ergab gemessen 3,0 Milliarden Zyklen für die 207 Shards eines Blocks: das Fünfzehnfache des Blocks selbst. Deshalb laufen Knoten stattdessen in einem **Rekursionsformat**.

## Das Rekursionsformat

Eine Aussage ist genau dann im Rekursionsformat, wenn ihr Programm Körperfamilien deklariert. Das Format fügt einen Adressraum und vier Koprozessor-Familien darauf hinzu, die alle über das gewöhnliche Delegations-ABI aufgerufen werden, und ändert sonst nichts:

| Familie | Eine Zeile ist |
| --- | --- |
| `FIELD_WINDOWS` | eine **Körperzelle**: eine Speicherzelle, die ein ganzes `Fr`-Element enthält, in derselben Speicher-Multimenge wie der RAM |
| `FR_OP` | eine Körperoperation über Zellen: Multiplizieren, Addieren, Subtrahieren, Multiply-Accumulate, Invertieren, Assert-Equal und Schritte zum Aufbau von Konstanten |
| `P2_FIELD` | ein Poseidon2-Duplex-Schritt über Zellen; ein Transkript läuft also mit einer Zeile pro Permutation |
| `FIELD_IO` | acht RAM-Wörter in eine Zelle oder eine Zelle zurück in acht Wörter |
| `FQ_OP` | eine Operation im Basiskörper von BN254, wobei ein Element aus vier Zellen mit 64-Bit-Limbs besteht; Kurvenarithmetik läuft also mit einer Zeile pro Körperoperation |

Zwei weitere Änderungen machen einen Rekursions-Shard für seinen Elternknoten günstiger zu verifizieren. Seine Speicher- und Witness-Spalten werden als **Stapel** von bis zu `2^24` Auswertungen committet; ein Elternknoten faltet also eine Handvoll Punkte statt Hunderter. Und eine Rekursionsanfrage schreibt ihre Frame-Basis hinter das Ende des Frames vorgerückt zurück; direkt hintereinander liegende Frames werden also als direkt aufeinanderfolgende `ecall`s abgespielt, eine Zeile pro Aufruf.

## Tapes

Die Prüfungen eines Shards haben für seine Familie und Höhe eine feste Form. Deshalb kompiliert der Host sie einmal in ein **Tape**: eine lineare Liste von Koprozessor-Aufrufen über absoluten Zellen, in der nichts abhängig von einem Wert verzweigt. Das Tape eines Shards besteht aus den Schritten des nativen Verifiers für diesen Shard, Aufruf für Aufruf: das Shard-Transkript, der GKR-Rückwärtsdurchlauf, die Lookup- und Wurzelprüfungen und die zwölf Skalare der Mercury-Öffnung. Jede Prüfung ist ein Assert-Equal.

Die Tapes, Faltungsvorlagen und Konstanten jedes Rekursionsprogramms werden zur Compile-Zeit vom Verifier-Crate selbst gebaut und in den schreibgeschützten Daten des Programms abgelegt. Die Programmidentität bindet daher jedes Tape, das das Programm abspielt: Zu beweisen, dass ein Knoten sein Programm ausgeführt hat, heißt zu beweisen, dass er genau diese Prüfungen ausgeführt hat.

## Ein über den Baum verkettetes Transkript

Das globale Transkript der Basisaussage ist ein einziger Sponge über die gesamte Aussage. Der Baum teilt es auf, ohne es zu verändern. Der Knoten, der Shard 0 hält, führt das Präfix aus, bis einschließlich des Digests der öffentlichen Eingabe; jeder Knoten absorbiert die Speicher-Commitments seiner eigenen Shards und setzt dabei an dem Zustand an, den sein Vorgänger hinterlassen hat; der Knoten, der den letzten Shard hält, führt das Suffix aus und zieht die Speicher-Challenges, die jeder Knoten als Behauptungen übernommen hatte. Das Journal eines Knotens hält den Zustand der Kette an beiden Enden seines Bereichs fest, und ein Elternknoten verlangt, dass die Zustände seiner Kinder aneinander anschließen.

Ein Knoten gleicht seine Kinder außerdem miteinander ab: Exit-Status 0, eine einzige Basisaussage (ihre Form, ihr Digest, ihre Challenges, der Digest von Eingabe und Journal, ihr Exit-Status und ihre Shard-Zahl), aneinandergrenzende Shard-Bereiche, aneinander anschließende Kettenzustände, Zeitfenster in Reihenfolge über die Naht hinweg und die Identitäten der Rekursionsprogramme. Ein Knoten, der eine ganze Aussage hält, führt das Speicherargument aus.

## Die Pairings falten

Kein Knoten berechnet ein Pairing. Die Mercury-Prüfung jedes Shards wird als zwölf Einträge `(side, scalar, point)` aufgeschoben; nach dem Tape des Shards absorbiert das eigene Transkript des Knotens den Endzustand des Shard-Transkripts und zieht Gewichte, und jeder Eintrag wird gewichtet in ein einziges laufendes Punktepaar `(A, B)` addiert, das die Behauptung `e(A, [1]_2) = e(B, [x]_2)` darstellt. Die Batch-Prüfung, die das kombinierte Commitment eines Shards an seine Spalten bindet, wird daneben gefaltet. Punkte, die alle Shards einer Familie teilen, etwa `[1]_1` und die Setup-Commitments, sammeln je einen Skalar an und gehen einmal ein. Das `(A, B)` eines Kindes geht unter einem Gewicht ein, das nach seinem gesamten Journal gezogen wird.

Jede Seite ist eine einzige Multi-Skalar-Multiplikation auf `FQ_OP`, ausgeführt als statische Vorlage: Pippenger mit 8-Bit-Ziffern über GLV-Hälften, für jeden Punkt erzwungen, dass er auf der Kurve liegt, jeder Schritt im Voraus festgelegt. Ein Punkt kostet etwa 400 `FQ_OP`-Aufrufe.

An der Wurzel ist der gesamte Inhalt des Baums zusammengefallen: jeder Basis-Shard verifiziert, das Transkript von Anfang bis Ende ausgeführt, das Speicherargument geführt und jede Öffnung in eine einzige Pairing-Behauptung gefaltet. Übrig bleiben diese Behauptung und zwei Programmidentitäten.

## Der Decider

Die Wurzel ist immer noch ein GKR-Beweis und einige Hundert Punkte, was ein Contract nicht prüfen kann. Der **Decider** ist ein Groth16-Schaltkreis, der das Knotenverfahren über einem einzigen Kind, der Wurzel, ausführt, und zwar über einen Treiber, der Rank-1-Constraints statt Koprozessor-Aufrufen schreibt, und der das Journal der Wurzel an den gesamten Bereich der Basis-Shards bindet. Er faltet nichts: Jeder Punkt, den die Wurzel dem finalen Pairing schuldet, wird mit seinem Skalar zu einem **gebundenen Wire**, einem Wert, den der Verifier besitzt, im Beweis unter einer fünften Falltür committet, statt als öffentliche Eingabe übergeben zu werden. Dasselbe gilt für die beiden Identitäten, den Exit-Status der Basisaussage sowie die öffentliche Eingabe und das Journal der Basisaussage, Byte für Byte.

Das Groth16 von Apogee weicht in drei Punkten vom Lehrbuch ab: das Commitment auf die gebundenen Wires, keine Verblindung und ein Beweisschlüssel über der Lagrange-Basis, die die Powers-of-Tau-Zeremonie bereits veröffentlicht. Sein Schlüssel stammt aus einer zweiphasigen Zeremonie: Phase 1 ist dieselbe Zeremoniedatei, auf der die Commitments beruhen; Phase 2 gehört allein dem Schaltkreis, wobei die Beiträge zu `α` und `β` abgeschlossen sind, bevor irgendein Beitrag zu `γ`, `δ` und `η` erfolgt, eine Reihenfolge, die selbst Teil der Soundness ist.

`ApogeeVerifier.sol` rekonstruiert die gebundenen Werte aus den Calldata, prüft die Groth16-Gleichung, faltet die Punkte beider Seiten mit `ecMul` und `ecAdd`, was zugleich erzwingt, dass jeder Punkt auf der Kurve liegt, und prüft das eine verbleibende Pairing. Sein Konstruktor legt den Schlüssel, die beiden G2-Punkte der Zeremonie und die Identitäten der beiden Rekursionsprogramme fest. Ein Deployment bedient ein einziges Basisprogramm, eine einzige Wurzelform und feste Längen der öffentlichen Werte.

## Gemessen

Block 257.510, der Baum auf einer Maschine mit 32 CPUs, Zeremonie und Decider auf einem Laptop mit 18 Kernen:

| | |
| --- | --- |
| Basisbeweis | 207 Shards, 14,5 MB, 2.481 s |
| Baum | 4 Blätter aus höchstens 64 Basis-Shards und eine Wurzel: insgesamt 116 Shards |
| Blätter, vier gleichzeitig | 21, 24, 23 und 27 Shards; 2.157 s; Spitze 92 GiB |
| Wurzel | 21 Shards, 460 s, 1,03 MB |
| Decider | 7.896.686 Constraints; Beweis in 18,5 s und 6,1 GB |
| Contract | 358 Punkte; 3.620.026 gas; 34.980 Byte Calldata |

Die Spezifikation: [Rekursion und Decider](https://apogee.gweb3networks.com/docs/auditors/spec/recursion). Selbst ausführen: [On-Chain abwickeln](https://apogee.gweb3networks.com/docs/launch/on-chain).