Rekursive Beweise

Bei einem rekursiven Beweis bestätigt ein Beweis die Gültigkeit eines oder mehrerer anderer. Umgesetzt wird dies, indem der Verifikationsalgorithmus des Systems, der Verifier Circuit, in den Circuit kodiert wird, der selbst bewiesen wird. In jedem Schritt entsteht ein neuer Beweis, der bescheinigt, dass der letzte Berechnungsblock korrekt ist und der vorherige Beweis gültig war. Das Ergebnis ist ein einziger finaler Beweis konstanter Größe, der eine beliebig lange Berechnungskette abdeckt. Verwandte Konzepte sind Incrementally Verifiable Computation (IVC) und Proof-Carrying Data.

Es ist die Grundlage für massive Skalierung und Aggregation in Rollups: Tausende Transaktionen oder viele Einzelbeweise lassen sich zu einem einzigen komprimieren, der on-chain zu festen Kosten verifizierbar ist, und der Blockchain-Zustand behält eine konstante Größe. Moderne Akkumulations- oder Folding-Techniken verschieben den teuren Teil der Verifikation, das Öffnen des Polynom-Commitments, und akkumulieren ihn in einer einzigen Operation am Ende, was die Rekursion verbilligt.

Die Meilensteine veranschaulichen das. Halo (Bowe, Grigg und Hopwood, 2019) war das erste praktische Beispiel rekursiver Komposition ohne Trusted Setup. Nova (Kothapalli, Setty und Tzialla, CRYPTO 2022) führt IVC per Folding mit dem kleinsten Verifier Circuit der Literatur ein. Halo 2 von Zcash implementiert rekursive Komposition ohne Trusted Setup, und Mina Protocol hält dank Rekursion über sein System Pickles eine Chain konstanter Größe von rund 22 KB.