Originaltitel: „So entwerfen Sie ein exquisites Beweisrekursionsschema“ Originalautor: Lin Yanxi, CTO von Fox Tech; Meng Xuanji, Chefwissenschaftler von Fox Tech Vorwort: Fast alle Probleme, die in den Spuren zkRollup und zkEVM auftreten, sind im Wesentlichen algorithmische Probleme. Der Hauptgrund, warum die ZKP-Hardwarebeschleunigung oft erwähnt wird, ist, dass aktuelle Algorithmen im Allgemeinen langsam sind. Um nicht in die peinliche Situation zu geraten: „Der Algorithmus reicht nicht aus, die Hardware macht das wett“, sollten wir das Problem algorithmisch lösen. Der Schlüssel zur Lösung dieses Problems liegt darin, ein exquisites Schema für den Wiederholungsnachweis zu entwerfen. Mit der kontinuierlichen Entwicklung intelligenter Verträge kommen nach und nach immer mehr Web3-Anwendungen auf den Markt, und das Transaktionsvolumen traditioneller Layer 1 wie Ethereum steigt rapide an und es kann jederzeit zu Überlastungen kommen. Wie eine höhere Effizienz erreicht und gleichzeitig die Sicherheit der Schicht 1 gewährleistet werden kann, ist zu einem dringenden Problem geworden, das gelöst werden muss. Für Ethereum verwendet zkRollup den Zero-Knowledge-Proof-Algorithmus als zugrunde liegende Komponente, um teure Berechnungen, die ursprünglich auf Layer 1 durchgeführt werden mussten, außerhalb der Kette zu verschieben und der Kette einen Beweis für die korrekte Ausführung zu liefern. Der Track umfasst hauptsächlich Projekte wie StarkWare, zkSync, Scroll und Fox Tech. Tatsächlich werden beim Entwurf von zkRollup sehr hohe Anforderungen an die Effizienz gestellt: Man hofft, dass der übermittelte Beweiswert klein genug ist, um die Berechnungslast von Schicht 1 zu reduzieren. Um eine ausreichend kleine Beweislänge zu erhalten, verbessern verschiedene zkRollup-Projekte Algorithmen und Architekturdesigns. Beispielsweise hat Fox seinen eigenen Beweisalgorithmus FOAKS entwickelt, der auf dem neuesten wissensfreien Beweisalgorithmus basiert, um eine optimale Beweiszeit und Beweislänge zu erhalten. Darüber hinaus besteht die trivialste Methode in der Phase der Beweisüberprüfung darin, Beweise linear zu generieren und diese nacheinander zu überprüfen. Um die Effizienz zu verbessern, denkt jeder zunächst daran, mehrere Beweise in einem Beweis zusammenzufassen, was allgemein als Beweisaggregation bezeichnet wird. Intuitiv gesehen ist die Überprüfung der von zkEVM generierten Beweise ein linearer Prozess, und der Prüfer muss nacheinander jeden generierten Beweiswert überprüfen. Allerdings ist die Effizienz dieser Verifizierungsmethode relativ gering und der Kommunikationsaufwand relativ groß. Für das zkRollup-Szenario bedeutet ein höherer Overhead auf der Verifiziererseite mehr Layer-1-Berechnungen, was auch zu höheren Gasgebühren führt.Schauen wir uns zunächst ein Beispiel an: Alice möchte der Welt beweisen, dass sie vom 1. bis 7. dieses Monats im Fox Park war. Dazu kann sie vom 1. bis 7. jeden Tag im Park ein Foto mit der Tageszeitung machen, und das Paket dieser 7 Fotos wird zum Beweis. Abbildung 1: Allgemeines Proof-Aggregationsschema: Das direkte Einlegen von 7 Fotos in einen Umschlag ist im intuitiven Sinne eine Proof-Aggregation. In tatsächlichen Situationen entspricht dies dem Zusammenfügen verschiedener Proofs und deren linearer Überprüfung Überprüfen Sie den ersten Beweis, dann den zweiten Beweis und die folgenden Beweise. Das Problem besteht darin, dass dieser Ansatz weder die Größe des Beweises noch den Zeitpunkt des Beweises ändert. Er hat den gleichen Effekt wie das Beweisen und Überprüfen einzeln. Wenn Sie eine Raumkomprimierung auf logarithmischer Ebene erreichen möchten, müssen Sie den unten erwähnten rekursiven Beweis (Proof Recursion) verwenden. Das von Halo2 und STARK verwendete rekursive Beweisschema. Um besser zu erklären, was ein rekursiver Beweis ist, kehren wir zum obigen Beispiel zurück. Alices 7 Fotos sind eigentlich 7 Beweise. Erwägen Sie nun, sie zusammenzuführen, damit Alice das Foto auf Nr. 1, das Foto mit der Zeitung von Nr. 2 auf Nr. 2 und das Foto von Nr. 2 und die Zeitung von Nr. 3 auf Nr. 3 aufnehmen kann . Foto. Analog dazu machte Alice das letzte Foto am 7. mit dem Foto vom 6. und die Zeitung am 7. Wenn andere Freunde das letzte Foto vom 7. sehen, können sie bestätigen, dass Alice zwischen dem 1. und 7. alle in den Park gegangen ist . Wie Sie sehen können, wurden die vorherigen sieben Beweisfotos zu einem komprimiert. Eine Schlüsseltechnik in diesem Prozess ist „Fotos enthalten Fotos“, was der rekursiven Verschachtelung vorheriger Fotos in nachfolgende Fotos entspricht. Das ist etwas anderes, als viele Fotos zusammenzustellen und dann ein Foto aufzunehmen. Der rekursive Beweistrick von zkRollup kann die Beweisgröße erheblich reduzieren. Insbesondere wird für jede Transaktion ein Beweis generiert. Wir gehen davon aus, dass die ursprüngliche Transaktionsberechnungsschaltung C0 ist, P0 der Korrektheitsnachweis von C0 ist, V0 der Berechnungsprozess zur Überprüfung von P0 ist und der Beweiser (Prover) auch V0 in das entsprechende The umwandelt Der Stromkreis wird mit C0' bezeichnet. Zu diesem Zeitpunkt können für den Beweisberechnungsprozess C1 einer anderen Transaktion die Schaltkreise C0' und C1 zusammengeführt werden. Sobald der Korrektheitsnachweis P1 des zusammengeführten Schaltkreises überprüft ist, entspricht dies der Überprüfung der beiden oben genannten Gleichzeitig wird die Korrektheit einer Transaktion erreicht, d. h. die Komprimierung wird erreicht.Wenn wir auf den obigen Prozess zurückblicken, können wir feststellen, dass das Prinzip der Komprimierung darin besteht, den Prozess der Verifizierung und des Beweises in eine Schaltung umzuwandeln und dann einen „Beweis des Beweises“ zu generieren kontinuierlich rekursiv sein, also auch rekursiver Beweis genannt. Abbildung 2: Das von Halo2 und Stark verwendete rekursive Beweisschema. Das von Halo2 und STARK verwendete Beweisrekursionsschema kann Beweise parallel generieren und mehrere Beweise zusammenführen, sodass die Richtigkeit mehrerer Transaktionsausführungen überprüft werden kann, während ein Beweiswert überprüft wird kann den Berechnungsaufwand komprimieren und die Effizienz des Systems erheblich verbessern. Eine solche Optimierung bleibt jedoch auf der Ebene über dem spezifischen Zero-Knowledge-Proof-Algorithmus. Um die Effizienz weiter zu verbessern, benötigen wir eine Optimierung und Innovation auf niedrigerer Ebene. Der von Fox entwickelte FOAKS-Algorithmus erreicht dies durch die Anwendung der rekursiven Idee innerhalb eines Beweises . An diesem Punkt angelangt. Das von FOAKS verwendete bewährte Rekursionsschema ist ein zkEVM-basiertes zkRollup-Projekt bei Fox Tech. In seinem Beweissystem wird auch die Technik des rekursiven Beweises verwendet, die Konnotation unterscheidet sich jedoch von der oben genannten rekursiven Methode. Der Hauptunterschied besteht darin, dass Fox die Idee der Rekursion innerhalb eines Beweises verwendet. Um die Kernidee des von Fox verwendeten rekursiven Beweises auszudrücken, die darin besteht, das zu beweisende Problem kontinuierlich zu reduzieren, bis das reduzierte Problem einfach genug ist, müssen wir ein weiteres Beispiel geben. Im obigen Beispiel hat Alice ein Foto gemacht, um zu beweisen, dass sie an einem bestimmten Tag in den Fox Park gegangen ist, also hat Bob verschiedene Vorschläge gemacht. Er glaubte, dass das Problem, zu beweisen, dass Alice in den Park gegangen ist, auf den Nachweis reduziert werden kann, dass Alices Handy dabei war Und der Beweis dieser Angelegenheit kann auf den Nachweis reduziert werden, dass sich Alices Mobiltelefon innerhalb des Parkbereichs befindet. Um zu beweisen, dass Alice im Park war, muss sie lediglich mit ihrem Telefon einen Standort senden, während sie im Park war. Auf diese Weise ändert sich die Größe des Proofs vom Originalfoto (sehr hochdimensionale Daten) zu dreidimensionalen Daten (Breitengrad, Längengrad und Zeit), wodurch effektiv Kosten gespart werden. Dieses Beispiel ist nicht ganz angemessen, da einige Leute vielleicht bezweifeln, dass die Tatsache, dass Alices Mobiltelefon im Fox Park war, nicht bedeutet, dass Alice selbst dort war, aber in tatsächlichen Situationen ist dieser Reduktionsprozess mathematisch streng.Insbesondere ist die Verwendung des rekursiven Beweises von Fox eine Rekursion auf Schaltungsebene. Bei der Durchführung eines wissensfreien Beweises schreiben wir das zu beweisende Problem in einen Schaltkreis und berechnen dann einige Gleichungen, die durch den Schaltkreis erfüllt werden müssen. Anstatt zu zeigen, dass diese Gleichungen erfüllt sind, schreiben wir diese Gleichungen erneut in Schaltkreise und so weiter, bis schließlich die Gleichung zum Beweis ihrer Erfüllung so einfach wird, dass wir sie leicht direkt beweisen können. Anhand dieses Prozesses können wir erkennen, dass dies eher der Bedeutung von „Rekursion“ entspricht. Es ist erwähnenswert, dass nicht alle Algorithmen diese rekursive Technik verwenden können. Es wird davon ausgegangen, dass jede Rekursion den Beweis mit einer Komplexität von O(n) in einen Beweis von O(f(n)) umwandelt, und die Berechnung der Rekursivität erfolgt Prozess selbst Die Komplexität beträgt O(g(n)), dann wird die gesamte Rechenkomplexität nach einer Rekursion zu O1(n)=O(f(n))+O(g(n)) und nach zwei Rekursionen zu O2 (n )=O(f(f(n)))+O(g(n))+O(g(f(n))), nach drei Malen ist es O3(n)=O(f(f( f(n)) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))),..., und so weiter. Daher ist es nur dann so, wenn f und g zwei Funktionen sind, die Ok(n) für ein bestimmtes k erfüllen. Schlussfolgerung Die Komplexität des Beweises war schon immer das Wichtigste In Zero-Knowledge-Proof-Anwendungen wird der Beweis der Komplexität immer wichtiger, da die zu beweisenden Dinge immer komplexer werden, insbesondere in riesigen ZK-Anwendungsszenarien wie zkEVM wird sich die Komplexität des Beweises auf die Leistung auswirken Die Benutzererfahrung hat einen entscheidenden Einfluss. Unter den vielen Methoden zur Reduzierung der Komplexität des endgültigen Beweises ist die Optimierung des Kernalgorithmus die wichtigste. Fox hat ein ausgeklügeltes rekursives Beweisschema basierend auf den modernsten Algorithmen entwickelt und diese Technologie verwendet, um die am besten geeignete Lösung zu erstellen für zkEVM. Es wird erwartet, dass der ZK-FOAKS-Algorithmus zum Leistungsführer in der zkRollup-Welt wird. Referenzen https://blog.csdn.net/weixin_44383880/article/details/126338813 https://blog.csdn.net/freedomhero/article/details/126727033 Dieser Artikel stammt aus einer Einsendung und gibt nicht die Ansichten von BlockBeats wieder