Tytuł oryginalny: „Jak zaprojektować znakomity schemat rekurencji dowodowej” Autor oryginalny: Lin Yanxi, dyrektor ds. technologii w Fox Tech; Meng Xuanji, główny naukowiec w Fox Tech Przedmowa: Prawie wszystkie problemy napotykane w ścieżkach zkRollup i zkEVM, a wśród nich są: zasadniczo problemy algorytmiczne. Głównym powodem, dla którego często wspomina się o akceleracji sprzętowej ZKP, jest to, że obecne algorytmy są generalnie powolne. Aby nie wpaść w kłopotliwą sytuację „algorytm to za mało, sprzęt to wynagrodzi”, powinniśmy rozwiązać problem algorytmicznie. Zaprojektowanie doskonałego schematu zabezpieczenia przed powtarzaniem się jest kluczem do rozwiązania tego problemu. Wraz z ciągłym rozwojem inteligentnych kontraktów stopniowo pojawia się coraz więcej aplikacji web3, a wolumen transakcji w tradycyjnej warstwie 1, takiej jak Ethereum, szybko rośnie, a przeciążenia mogą wystąpić w dowolnym momencie. Jak uzyskać wyższą wydajność przy jednoczesnym zapewnieniu bezpieczeństwa zapewnianego przez warstwę 1, stało się pilnym problemem wymagającym rozwiązania. W przypadku Ethereum zkRollup wykorzystuje algorytm dowodu o wiedzy zerowej jako podstawowy komponent do przenoszenia kosztownych obliczeń, które pierwotnie musiały zostać wykonane na warstwie 1 poza łańcuchem, i dostarczania dowodu poprawności wykonania do łańcucha. Na utworze znajdują się głównie projekty takie jak StarkWare, zkSync, Scroll i Fox Tech. Tak naprawdę w projekcie zkRollup stawiane są bardzo wysokie wymagania dotyczące wydajności: oczekuje się, że przesłana wartość dowodu będzie wystarczająco mała, aby zmniejszyć obciążenie obliczeniowe Warstwy 1. Aby uzyskać wystarczająco małą długość dowodu, różne projekty zkRollup udoskonalają algorytmy i projekty architektury. Na przykład Fox opracował własny algorytm dowodu FOAKS w oparciu o najnowszy algorytm dowodu o wiedzy zerowej w celu uzyskania optymalnego czasu i długości dowodu. Dodatkowo na etapie weryfikacji dowodu najbardziej banalną metodą jest liniowe generowanie dowodów i ich sekwencyjna weryfikacja. Aby zwiększyć wydajność, pierwszą rzeczą, o której wszyscy myślą, jest połączenie wielu dowodów w jeden dowód, co jest powszechnie określane jako agregacja dowodów (agregacja dowodów). Intuicyjnie mówiąc, weryfikacja dowodów wygenerowanych przez zkEVM jest procesem liniowym, a weryfikator (Weryfikator) musi po kolei weryfikować każdą wygenerowaną wartość dowodu. Jednakże wydajność tej metody weryfikacji jest stosunkowo niska, a narzut komunikacyjny stosunkowo duży. W przypadku scenariusza zkRollup wyższy narzut po stronie weryfikatora oznacza więcej obliczeń w warstwie 1, co również będzie prowadzić do wyższych opłat za gaz.Spójrzmy najpierw na przykład: Alicja chce udowodnić światu, że była w Fox Park od 1 do 7 tego miesiąca. W tym celu może codziennie od 1 do 7 dnia robić w parku zdjęcie z gazetą z danego dnia, a pakiet tych 7 zdjęć stanie się dowodem. Rysunek 1: Ogólny schemat agregacji dowodów W powyższym przykładzie umieszczenie 7 zdjęć bezpośrednio w kopercie jest agregacją dowodów w intuicyjnym sensie, w rzeczywistości oznacza to połączenie ze sobą różnych dowodów i weryfikację ich liniowo, czyli najpierw Sprawdź pierwszy dowód, następnie drugi dowód i kolejne dowody. Problem w tym, że to podejście nie zmieni ani rozmiaru dowodu, ani czasu jego wykonania. Daje taki sam efekt, jak dowodzenie i weryfikacja jedno po drugim. Jeśli chcesz osiągnąć kompresję przestrzeni na poziomie logarytmicznym, musisz użyć dowodu rekurencyjnego (Rekursja dowodu) wspomnianego poniżej. Schemat dowodu rekurencyjnego stosowany w Halo2 i STARK Aby lepiej wyjaśnić, czym jest dowód rekurencyjny, wróćmy do powyższego przykładu. 7 zdjęć Alicji to tak naprawdę 7 dowodów. Teraz rozważ połączenie ich, tak aby Alicja mogła zrobić zdjęcie nr 1, zrobić zdjęcie z gazetą nr 2 w nr 2 i zrobić zdjęcie nr 2 i gazetę nr 3 w nr 3 zdjęcie. Analogicznie, Alicja zrobiła ostatnie zdjęcie 7-go ze zdjęciem 6-go, a gazetę 7-go. Kiedy inni przyjaciele zobaczą ostatnie zdjęcie 7-go, mogą potwierdzić, że między 1-ym a 7-mym Alicja poszła do parku. . Jak widać, siedem poprzednich zdjęć próbnych zostało skompresowanych w jedno. Kluczową techniką w tym procesie są „zdjęcia zawierające zdjęcia”, co jest równoznaczne z rekurencyjnym zagnieżdżaniem poprzednich zdjęć w kolejnych. Różni się to od złożenia wielu zdjęć i zrobienia jednego zdjęcia. Sztuczka rekurencyjnego dowodu zkRollup może znacznie zmniejszyć rozmiar dowodu. W szczególności każda transakcja wygeneruje dowód. Zakładamy, że pierwotny obwód obliczania transakcji to C0, P0 jest dowodem poprawności C0, V0 jest procesem obliczeniowym sprawdzającym P0, a dowód (Prover) również konwertuje V0 na odpowiedni The. obwód jest oznaczony jako C0'. W tym momencie, dla procesu obliczenia dowodu C1 innej transakcji, można połączyć obwody C0' i C1. W ten sposób, po zweryfikowaniu dowodu poprawności P1 łączonego obwodu, jest to równoznaczne z weryfikacją dwóch powyższych w punkcie. w tym samym czasie zostaje osiągnięta poprawność transakcji, czyli kompresja.Patrząc wstecz na powyższy proces, możemy stwierdzić, że zasada kompresji polega na przekształceniu procesu weryfikacji i dowodu w obwód, a następnie wygenerowaniu „dowodu dowodu”. Zatem z tej perspektywy jest to operacja, która może być w sposób ciągły rekurencyjny, nazywany także dowodem rekurencyjnym. Rysunek 2: Schemat dowodu rekurencyjnego stosowany w Halo2 i Stark Schemat Proof Recursion używany w Halo2 i STARK może generować dowody równolegle i łączyć wiele dowodów, dzięki czemu można zweryfikować poprawność wielu realizacji transakcji podczas weryfikacji jednej wartości dowodu może skompresować narzut obliczeniowy i znacznie poprawić wydajność systemu. Jednak taka optymalizacja nadal pozostaje na poziomie powyżej specyficznego algorytmu dowodu o wiedzy zerowej. Aby jeszcze bardziej poprawić wydajność, potrzebujemy optymalizacji i innowacji na niższym poziomie. Algorytm FOAKS zaprojektowany przez Foxa robi to poprzez zastosowanie idei rekurencyjnej wewnątrz dowodu Dotarłem do tego punktu. Sprawdzony schemat rekurencji używany przez FOAKS to projekt zkRollup oparty na zkEVM w Fox Tech. W swoim systemie dowodowym wykorzystuje również technikę dowodu rekurencyjnego, ale konotacja różni się od wspomnianej powyżej metody rekurencyjnej. Główna różnica polega na tym, że Fox wykorzystuje ideę rekurencji wewnątrz dowodu. Aby wyrazić podstawową ideę dowodu rekurencyjnego stosowanego przez Foxa, która polega na ciągłym ograniczaniu udowadnianego problemu, aż zredukowany problem stanie się wystarczająco prosty, musimy podać inny przykład. W powyższym przykładzie Alicja zrobiła zdjęcie, aby udowodnić, że pewnego dnia poszła do Fox Park, więc Bob przedstawił różne sugestie. Uważał, że problem udowodnienia, że ​​Alicja poszła do parku, można sprowadzić do udowodnienia, że ​​Alicja ma telefon komórkowy telefon poszedł do parku, a udowodnienie tej sprawy sprowadza się do udowodnienia, że ​​telefon komórkowy Alicji znajduje się na terenie parku. Aby więc udowodnić, że Alicja była w parku, musi jedynie wysłać lokalizację za pomocą telefonu, gdy była w parku. W ten sposób wielkość dowodu zmienia się z oryginalnego zdjęcia (dane o bardzo dużych wymiarach) na dane trójwymiarowe (szerokość, długość i czas geograficzny), skutecznie oszczędzając koszty. Ten przykład nie jest do końca trafny, ponieważ niektórzy mogą kwestionować fakt, że telefon komórkowy Alicji był w Fox Park, nie oznacza, że ​​sama Alicja tam była, ale w rzeczywistych sytuacjach proces redukcji jest matematycznie rygorystyczny.W szczególności dowód rekurencyjny Foxa jest rekurencją na poziomie obwodu. Wykonując dowód z wiedzą zerową, zapiszemy problem do udowodnienia w obwodzie, a następnie obliczymy kilka równań, które należy spełnić w obwodzie. Zamiast pokazywać, że te równania są spełnione, zapisujemy je ponownie w obwody i tak dalej, aż w końcu równanie udowadniające, że są spełnione, stanie się na tyle proste, że będziemy mogli to łatwo udowodnić bezpośrednio. Z tego procesu widzimy, że jest to bliższe znaczeniu „rekurencji”. Warto wspomnieć, że nie wszystkie algorytmy potrafią zastosować tę technikę rekurencyjną. Zakłada się, że każda rekurencja zamieni dowód o złożoności O(n) w dowód O(f(n)) oraz obliczenie samego procesu rekurencyjnego. Złożoność wynosi O(g(n)). Po jednej rekurencji całkowita złożoność obliczeniowa wynosi O1(n)=O(f(n))+O(g(n)). Po dwóch rekurencjach staje się O2(n )=O(f(f(n)))+O(g(n))+O(g(f(n))), po trzykrotności otrzymujemy O3(n)=O(f(f(f( n)) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))),..., i tak dalej. Zatem tylko wtedy, gdy f i g są dwiema funkcjami odpowiadającymi cechom algorytmu, które spełniają Ok(n) dla pewnego k. Rysunek 3: Schemat dowodu rekurencyjnego stosowany przez ZK-FOAKS. Wniosek Najważniejsza zawsze była złożoność dowodu w aplikacjach dowodowych o wiedzy zerowej Jednym z kluczy jest to, że złożoność dowodu będzie coraz ważniejsza, w miarę jak elementy podlegające udowodnieniu staną się coraz bardziej złożone, szczególnie w przypadku gigantycznych scenariuszy aplikacji ZK, takich jak zkEVM, złożoność dowodu będzie miała. ogromny wpływ na wydajność i wydajność produktu Decydujący wpływ ma doświadczenie użytkownika. Spośród wielu metod zmniejszających złożoność ostatecznego dowodu najważniejsza jest optymalizacja algorytmu rdzenia. Firma Fox zaprojektowała genialny schemat dowodu rekurencyjnego w oparciu o najnowocześniejsze algorytmy i wykorzystała tę technologię do stworzenia rozwiązania, które jest skuteczne. najbardziej odpowiedni dla zkEVM Oczekuje się, że algorytm ZK-FOAKS stanie się liderem wydajności w świecie zkRollup. Referencje https://blog.csdn.net/weixin_44383880/article/details/126338813 https://blog.csdn.net/freedomhero/article/details/126727033 Ten artykuł pochodzi z przesłanego zgłoszenia i nie reprezentuje poglądów BlockBeats