Was ist Rekursion?

Rekursion wird am häufigsten in den Bereichen Mathematik, Statistik und Informatik verwendet, findet aber auch in einer Reihe anderer Disziplinen, einschließlich Linguistik und Logik, sowie in realen Anwendungen künstlicher Intelligenz und Spiele breite Anwendung.

Unter Rekursion versteht man den Fall, dass eine Funktion sich selbst direkt oder indirekt in einer oder mehreren kreisförmigen Schleifen aufruft.

Rekursion kann verwendet werden, um die Genauigkeit der Berechnung zu verbessern und die insgesamt erforderliche Rechenlast zu reduzieren. Durch die Zerlegung eines größeren, komplexeren Problems in kleinere Teile, auch bekannt als „Teile und herrsche“, ermöglicht die Rekursion eine schnellere und praktikablere Lösung der Aufgabe. Ein wesentliches Merkmal besteht darin, dass die Funktion sich selbst wiederholt nacheinander aufruft, um eine Rekursion zu erreichen, die anhand von Basisfällen und rekursiven Schritten definiert wird.

Der Basisfall bezieht sich auf die einfachste Instanz eines Problems mit allen Eingaben, die die Ausgabe berechnen würden. Rekursive Schritte rufen dieselbe Funktion auf, aber die Eingaben nehmen an Größe und/oder Komplexität ab.

Sowohl iterative als auch rekursive Algorithmen zerlegen Probleme in kleinere, erstere erfordern jedoch eine explizite Steuerlogik, um die Reihenfolge der Algorithmen zu verwalten. Die Reihenfolge einer rekursiven Funktion wird durch das Zusammenspiel der Vektordaten und der rekursiven Funktion bestimmt. Dies bietet eine größere Flexibilität im Umgang mit Datenstrukturen, die nicht explizit im Voraus definiert werden können.

Wie wird Rekursion auf die Blockchain-Technologie angewendet?

Rekursion ist eine Methode zum Generieren von Beweisen auf der Blockchain. Es bedient jetzt mehrere Produktionssysteme im Ethereum-Mainnet. Beispielsweise verwendet Arbitrum einen rekursiven Bisektionsalgorithmus für seinen Streitbeilegungsprozess, während StarkWare und zkSync beide Rekursion verwenden, um verbesserte Skalierungsmöglichkeiten zu erreichen.

Ohne rekursive Technologie gibt es eine Obergrenze für Transaktionen, die in einen Beweis passen könnten, die durch die Rechenkapazität eines einzelnen Blocks bestimmt wird. Mit der Rekursion kann ein einzelner Beweis aus mehreren verifizierten Beweisen generiert werden, die Hunderttausende zugrunde liegender Transaktionen enthalten. Mit anderen Worten: Wir können jetzt viel mehr Transaktionen in einem einzigen Beweis verarbeiten, was auch als rekursive Skalierung bezeichnet wird.

Die Anwendung der rekursiven Technologie für wissensfreie Beweise ist besonders wichtig, da sie als entscheidender Teil der Lösung für die Skalierbarkeit der Blockchain gilt. Nehmen wir als Beispiel StarkNet von StarkWare, eine der führenden zk-Rollup-Skalierungslösungen auf Ethereum: SHARP (SHARed Prover) nimmt Transaktionen von separaten Anwendungen auf StarkNet auf, um sie zu stapeln und zu einem ZK-STARK-Proof (oder einfach nur STARK-Proof) zu komprimieren. Anschließend übergibt der Prüfer den Beweis an den Verifizierer. Letzterer hat die Aufgabe, die Zustandsänderung auf Schicht 1 zu verifizieren und zu registrieren. Es gibt Einschränkungen, wer Prüfer sein kann, basierend auf den erforderlichen Rechenressourcen.

Fügen wir nun eine Rekursion in das Bild ein. Mehrere Transaktionen (oder Kontoauszüge) werden an SHARP gesendet und parallel nachgewiesen. Jeder Beweis wird dann von einem STARK-Prüfer validiert. Nach der Verifizierung werden sie durch eine Recursive Verifier-Anweisung erneut zusammengeführt. Dieser Vorgang kann sich wiederholen, bis ein endgültiger Beweis auf Ebene 1 an einen Solidity-Verifier-Smart-Vertrag übermittelt wird. Dieser Beweis bescheinigt somit alle Originalaussagen und ermöglicht die Verarbeitung mehrerer On-Chain-Transaktionen in einem einzigen Beweis. Theoretisch kann die rekursive Schleife unbegrenzt wiederholt werden, was die Möglichkeit einer „Hyperskalierung“ ermöglicht.

Die Rekursion erschließt daher das Potenzial der Roll-up-Technologie und der Layer-2-Skalierung weiter.

Vorteile der Rekursion

Zu den Vorteilen der Rekursion für Gültigkeitsnachweise gehören niedrigere Gaskosten durch geringere Kosten pro Transaktion aufgrund der „Komprimierung“ mehrerer Beweise zu einem. Dadurch können mehr Transaktionen in einem einzigen an L1 übermittelten Nachweis aufgeteilt werden, wodurch sich die Gaskosten pro Transaktion amortisieren. Auch die Rechenressourcenbarriere, die die Beweisgröße begrenzte, stellt keine Einschränkung mehr dar, da keine Notwendigkeit besteht, extrem große Aussagen auf einmal zu beweisen.

Dies führt auch zu einer geringeren Latenz. Anweisungen (die kleinere Transaktionen enthalten) können parallel bewiesen werden und müssen nicht auf den Eingang anderer Transaktionen warten. Prüfer müssen keine großen Berechnungen mehr außerhalb der Kette durchführen, und daher sind die Hürden, ein Prüfer zu werden, gesunken, was einen Anreiz für eine dezentrale Lösung darstellt Netzwerk von Prüfern, um die Verarbeitungskapazität des Netzwerks zu steigern.

Darüber hinaus können Benutzer von der „logarithmischen Komprimierung“ mit STARK profitieren, bei der der Beweis einer Aussage T-Zeit und die Überprüfung des Beweises etwa log(T)-Zeit benötigt. Die logarithmische Komprimierung ist wichtig, da die Überprüfung eines Beweises, der zwei Beweise für die korrekte Ausführung enthält, log(2log(T))-Schritte erfordert. Mit anderen Worten: Die Latenz zur Erstellung und Validierung rekursiver Beweise verringert sich auf einer logarithmischen Skala.

Durch Rekursion haben Plattformen und Anwendungen die Möglichkeit, ihre Kosten und Leistung weiter zu skalieren.

Verwendungsmöglichkeiten der Rekursion über Schicht 2 hinaus

Die Rekursion schafft die Voraussetzungen für Anwendungsfälle der Schicht 3. Bisher lag der Schwerpunkt auf der Verwendung von Rekursion zur Generierung von Beweisen auf Schicht 2, die sich letztendlich auf Schicht 1 niederlassen. Eine neue Schicht eröffnet jedoch auch die Möglichkeit, Transaktionsnachweise von Schicht 3 an Schicht 2 zu übermitteln, wo die Ausführung auf der obersten Schicht erfolgt , und der Beweis wird schließlich auf Schicht 2 verifiziert, was weitere Leistungsoptimierungen und Kostenvorteile ermöglichen kann. Die Interaktionen zwischen Schicht 3 und Schicht 2 sind analog zu Schicht 2 und Schicht 1, wobei die gesamte Transaktionsintegrität und -sicherheit gewahrt bleibt.

Insbesondere private Layer-3-Netzwerke sind in hohem Maße anpassbar, sodass Protokolle ihre eigenen Betriebsparameter festlegen können, z. B. die Festlegung der Transaktionsstapelgröße, um Transaktionskosten und -geschwindigkeit in Einklang zu bringen, oder die Implementierung von Funktionen zum Schutz der Privatsphäre. Die maßgeschneiderte Qualität von Layer 3 für verschiedene Anwendungsfälle sowie die verbesserten Verarbeitungsfunktionen durch Rekursion ermöglichen sowohl ein individuelles Kettenerlebnis als auch die Gewährleistung, dass die Tools zur Leistungs- und Kostenoptimierung leicht verfügbar sind. Die Vorteile von Layer 3 sind Hyperskalierbarkeit aufgrund der Nutzung des multiplikativen Effekts rekursiver Prüfung, Datenschutz und verbesserte Interoperabilität zwischen Layer 2 und Layer 3.

Mit der Zeit werden weitere Anwendungsfälle und Vorteile der Rekursion bei der Blockchain-Entwicklung realisiert. Durch die Freischaltung des Prozesses der Parallelisierung wird eine Hyperskalierung möglich, wodurch die Latenz verbessert und gleichzeitig die Gasgebühren gesenkt werden.

Autor

Jane Ma, Mitbegründerin und Co-Projektleiterin von zkLend, einem auf StarkNet basierenden L2-Geldmarktprotokoll, das die Skalierbarkeit von zk-Rollup, überlegene Transaktionsgeschwindigkeit und Kosteneinsparungen mit der Sicherheit von Ethereum kombiniert. Das Protokoll bietet eine doppelte Lösung: eine erlaubnis- und konformitätsorientierte Lösung für institutionelle Kunden und einen erlaubnisfreien Dienst für DeFi-Benutzer – und das alles ohne Einbußen bei der Dezentralisierung.