Autor: założyciel Ethereum Vitalik; kompilacja: Deng Tong, Golden Finance

Uwaga: Ten artykuł jest częścią serii artykułów założyciela Ethereum Vitalika pt. 'Przyszłość rozwoju protokołu Ethereum', część czwarta 'Możliwe przyszłości protokołu Ethereum, część 4: The Verge'. Część trzecia to 'Vitalik: Kluczowe cele etapu The Scourge Ethereum', część druga to 'Vitalik: Jak powinien rozwijać się protokół Ethereum na etapie The Surge', a część pierwsza to 'Jakie są możliwości poprawy Ethereum PoS'. Poniżej znajduje się pełny tekst czwartej części:

Szczególne podziękowania dla Justina Drake'a, Hsiao-wei Wanga, Guillaume'a Balleta, Ignacio, Josha Rudolfa, Leva Soukhanova, Ryana Seana Adamsa i Umy Roy za ich opinie i przeglądy.

Jedną z najsilniejszych cech blockchaina jest to, że każdy może uruchomić węzeł na swoim komputerze i zweryfikować, czy łańcuch jest poprawny. Nawet jeśli 95% węzłów, które uruchamiają konsensus na łańcuchu (PoW, PoS...) natychmiast zgodzą się na zmianę zasad i zaczną produkować bloki zgodnie z nowymi zasadami, każdy, kto uruchamia w pełni zweryfikowany węzeł, odmówi zaakceptowania tego łańcucha. Interesariusze, którzy nie należą do tej grupy, automatycznie zbiorą się i będą kontynuować budowę łańcucha, który nadal będzie podążał zgodnie ze starymi zasadami, a użytkownicy w pełni zweryfikowani będą podążać za tym łańcuchem.

To kluczowa różnica między blockchainem a systemami scentralizowanymi. Jednak aby zachować tę cechę, uruchomienie w pełni zweryfikowanego węzła musi być realne dla krytycznej liczby osób. Dotyczy to zarówno stakerów (jak gdyby stakerzy nie weryfikowali łańcucha, w rzeczywistości nie przyczyniają się do egzekwowania zasad protokołu), jak i zwykłych użytkowników. Obecnie można uruchomić węzeł na laptopach klasy konsumenckiej (w tym laptopie, na którym piszę ten tekst), ale jest to trudne. The Verge ma na celu zmianę tej sytuacji, aby koszty obliczeniowe w pełni zweryfikowanego łańcucha były tak niskie, że każdy portfel mobilny, portfel przeglądarki, a nawet smartwatch mógłby to robić domyślnie.

The Verge, mapa drogowa 2023.

Początkowo 'Verge' odnosił się do pomysłu przeniesienia przechowywania stanu Ethereum do drzewa Verkle - ta struktura drzewa pozwala na bardziej zwarty dowód, umożliwiając weryfikację bloków Ethereum bez stanu. Węzły mogą weryfikować bloki Ethereum bez posiadania jakiegokolwiek stanu Ethereum (bilansów kont, kodów kontraktów, pamięci...) na swoim dysku twardym, ale kosztem danych dowodowych rzędu setek kilobajtów i dodatkowego czasu na weryfikację dowodów wynoszącego kilka setek milisekund. Dziś Verge reprezentuje większą wizję, skoncentrowaną na osiągnięciu maksymalnej efektywności zasobowej weryfikacji łańcucha Ethereum, która obejmuje nie tylko techniki weryfikacji bezstanu, ale także użycie SNARK do weryfikacji wszystkich działań Ethereum.

Oprócz długoterminowego skupienia się na weryfikacji SNARK całego łańcucha, innym nowym problemem jest to, czy drzewo Verkle jest najlepszą technologią. Drzewo Verkle jest podatne na ataki kwantowe, więc jeśli zastąpimy aktualne drzewa Merkle Patricia KECCAK drzewem Verkle, wkrótce będziemy musieli ponownie zastąpić te drzewa. Naturalnym zastąpieniem drzew Merkle jest bezpośrednie przejście na użycie gałęzi Merkle STARK w drzewie binarnym. Historycznie było to uznawane za niepraktyczne z powodu nadwyżek i złożoności technicznej. Niemniej jednak ostatnio widzieliśmy, że Starkware udowodniło 1.7 miliona haszy Poseidona na laptopach z Circle STARK na sekundę, a dzięki technologiom takim jak GKR, czasy dowodzenia dla bardziej 'tradycyjnych' funkcji haszujących również szybko się skracają.

W ciągu ostatniego roku Verge stał się znacznie bardziej otwarty i istnieje wiele możliwości.

The Verge: kluczowe cele

  • Klient bezstanu: w pełni zweryfikowany klient i węzeł stakujący nie potrzebują więcej niż kilka GB przestrzeni dyskowej.

  • (długoterminowo) pełna weryfikacja łańcucha na smartwatchu (konsensus i wykonanie). Pobierz dane, zweryfikuj SNARK, gotowe.

W artykule skupiamy się na następujących kwestiach:

  • Weryfikacja bezstanu: Verkle lub STARKs

  • Dowód ważności wykonania EVM

  • Dowód ważności konsensusu

Weryfikacja bezstanu: Verkle lub STARKs

Jakie problemy chcemy rozwiązać?

Obecnie klienci Ethereum muszą przechowywać setki GB danych stanu, aby zweryfikować blok, a ta liczba rośnie każdego roku. Początkowe dane stanu rosną o około 30 GB rocznie, a poszczególne klienci muszą przechowywać dodatkowe dane oprócz skutecznych aktualizacji trie.

To zmniejsza liczbę użytkowników, którzy mogą uruchomić w pełni zweryfikowane węzły Ethereum: chociaż dyski twarde są wystarczająco duże, aby przechować cały stan Ethereum, a nawet wieloletnie historie, komputery, które ludzie domyślnie kupują, często mają tylko kilka setek gigabajtów przestrzeni dyskowej. Rozmiar stanu również wprowadza wiele problemów do procesu początkowego uruchamiania węzła: węzeł musi pobrać cały stan, co może zająć godziny lub dni. To generuje różne efekty kaskadowe. Na przykład, to utrudnia stakerom aktualizację ich ustawień stakowania. Technicznie można to zrobić bez wyłączania - uruchomić nowego klienta, poczekać na jego synchronizację, a następnie zamknąć starego klienta i przenieść klucz - ale w praktyce jest to technicznie skomplikowane.

Co to jest i jak to działa?

Weryfikacja bezstanu to technika, która pozwala węzłom na weryfikację bloków bez posiadania pełnego stanu. Zamiast tego każdy blok jest powiązany z świadkiem, który zawiera (i) wartości w określonych lokalizacjach w stanie, do którego blok uzyskuje dostęp (np. kod, bilanse, pamięć), oraz (ii) kryptograficzny dowód, że te wartości są poprawne.

Praktyczna implementacja weryfikacji bezstanu wymaga zmiany struktury drzewa stanu Ethereum. Dzieje się tak, ponieważ aktualne drzewo Merkle Patricia jest niezwykle nieprzyjazne dla realizacji jakiegokolwiek schematu dowodu kryptograficznego, zwłaszcza w najgorszym przypadku. Zarówno 'surowa' gałąź Merkle, jak i możliwość 'opakowania' gałęzi Merkle w STARK są problematyczne. Główne trudności wynikają z dwóch słabości MPT:

  • To jest drzewo sześciokrotne (tj. każdy węzeł ma 16 dzieci). Oznacza to, że średnio dowód w drzewie o rozmiarze N ma 32*(16-1)*log16(N) = 120*log2(N) bajtów, co odpowiada około 3840 bajtów w drzewie o 232 elementach. Dla drzewa binarnego potrzeba tylko 32*(2-1)*log2(N) = 32*log2(N) bajtów, co odpowiada około 1024 bajtów.

  • Ten kod nie jest merkle'owany. To oznacza, że dostęp do kodu konta wymaga dostarczenia pełnego kodu o maksymalnej długości 24000 bajtów.

Możemy obliczyć najgorszy przypadek w następujący sposób:

30,000,000 gazu / 2,400 (koszt odczytu 'zimnych' kont) * (5 * 480 + 24,000) = 330,000,000 bajtów

Koszt gałęzi nieco spadł (5*480 zamiast 8*480), ponieważ przy dużej liczbie gałęzi, wierzchołki gałęzi będą się powtarzać. Ale nawet w tym przypadku ilość danych do pobrania w jednym slocie jest całkowicie nierealna. Jeśli spróbujemy to opakować w STARK, natkniemy się na dwa problemy: (i) KECCAK jest stosunkowo nieprzyjazny dla STARK, (ii) 330 MB danych oznacza, że musimy udowodnić 5 milionów wywołań funkcji okrągłych KECCAK, co jest sposobem, nawet jeśli możemy sprawić, że dowody STARK będą bardziej efektywne dla KECCAK, to poza najsilniejszym sprzętem do użytku domowego, wiele rzeczy nie może być udowodnionych na całym sprzęcie.

Jeśli tylko zamienimy drzewo sześciokrotne na drzewo binarne, a następnie dodamy merkle'owanie kodu, to w najgorszym przypadku zmienia się to na około 30,000,000 / 2,400 * 32 * (32 - 14 + 8) = 10,400,000 bajtów ~214 gałęzi, gdzie 8 to długość wchodząca do liścia dowodu. Należy zauważyć, że wymaga to zmiany kosztu gazu, aby nałożyć opłatę za dostęp do każdego pojedynczego bloku kodu; EIP-4762 to zrobił. 10.4 MB jest już znacznie lepsze, ale dla wielu węzłów pobranie danych w jednym slocie wciąż jest zbyt duże. Musimy więc wprowadzić bardziej zaawansowane technologie. W tym celu istnieją dwie główne rozwiązania: drzewo Verkle i zhakowane binarne drzewo haszujące.

Drzewo Verkle

Drzewo Verkle wykorzystuje wektory zobowiązań oparte na krzywych eliptycznych, aby uzyskać krótsze dowody. Kluczowe jest to, że niezależnie od szerokości drzewa, fragmenty dowodu odpowiadające każdemu rodzicowi i dziecku mają tylko 32 bajty. Jedynym ograniczeniem szerokości drzewa jest to, że jeśli drzewo jest zbyt szerokie, wydajność obliczeń dowodów spada. Zalecana szerokość implementacji Ethereum wynosi 256.

W związku z tym rozmiar pojedynczej gałęzi w dowodzie zmienia się na 32*log256(N) = 4*log2(N) bajtów. Teoretyczny maksymalny rozmiar dowodu wynosi około 30,000,000/2,400*32*(32-14+8)/8 = 1,300,000 bajtów (ze względu na nierównomierne rozkłady bloków stanu, obliczenia matematyczne w praktyce różnią się nieco, ale to jest dobre jako pierwsze oszacowanie).

Jako dodatkowe ostrzeżenie należy pamiętać, że w wszystkich powyższych przykładach 'najgorszy przypadek' nie jest najgorszym przypadkiem: gorsze przypadki to atakujący, który celowo 'wydobywa' dwa adresy, aby mieć długi wspólny prefiks w drzewie, a następnie odczytuje z jednego z nich, co może wydłużyć długość gałęzi w najgorszym przypadku o około 2 razy. Ale nawet z takim ostrzeżeniem, drzewo Verkle pozwala nam uzyskać około 2.6 MB dowodu w najgorszym przypadku, co mniej więcej odpowiada dzisiejszym wartościom danych wywołania w najgorszym przypadku.

Wykorzystujemy to ostrzeżenie, aby zrobić jeszcze jedną rzecz: uczyniliśmy dostęp do sąsiednich pamięci bardzo tanim: wiele bloków kodu tego samego kontraktu lub sąsiadujących slotów pamięci. EIP-4762 definiuje sąsiedztwo, a dostęp sąsiedni kosztuje tylko 200 gazu. W przypadku dostępu sąsiedniego maksymalny rozmiar dowodu zmienia się na 30,000,000/200*32 = 4,800,800 bajtów, co nadal mieści się w tolerancji. Jeśli dla bezpieczeństwa chcemy obniżyć tę wartość, możemy nieco zwiększyć koszt dostępu sąsiedniego.

Zaznaczone drzewo haszujące binarne

Technologia tutaj jest bardzo niewyraźna: tworzysz drzewo binarne, przyjmując maksymalny dowód o rozmiarze 10.4 MB wartości, które musisz udowodnić w bloku, a następnie zastępujesz ten dowód STARK. To pozwala nam odkryć, że dowód sam w sobie zawiera tylko dane udowodnione, plus około 100-300 kB stałych kosztów rzeczywistego STARK.

Główne wyzwanie tutaj to czas dowodu. Możemy przeprowadzić zasadniczo te same obliczenia, tylko że nie obliczamy bajtów, a haszy. Blok o rozmiarze 10.4 MB oznacza 330,000 haszy. Jeśli dodamy możliwość, że atakujący 'wydobywa' adresy w drzewie z długim wspólnym prefiksem, to prawdziwie najgorszy przypadek zmienia się na około 660,000 haszy. Dlatego jeśli będziemy w stanie udowodnić około 200,000 haszy na sekundę, to nie będzie problemu.

Te liczby zostały już osiągnięte na konsumpcyjnych laptopach z funkcją haszującą Poseidon, która została specjalnie zaprojektowana dla przyjazności STARK. Niemniej jednak Poseidon jest stosunkowo niedojrzały, więc wiele osób wciąż nie ufa jego bezpieczeństwu. W związku z tym istnieją dwie realistyczne drogi do przodu:

  • Szybkie przeprowadzenie licznych analiz bezpieczeństwa Poseidona i zapoznanie się z nim, aby go wdrożyć w L1.

  • Używanie bardziej 'zachowawczych' funkcji haszujących, takich jak SHA256 lub BLAKE.

W momencie pisania tego tekstu, dowódca STARK Starkware może udowodnić zachowawcze funkcje haszujące tylko na konsumpcyjnych laptopach, co oznacza około 10-30 tys. haszy na sekundę. Niemniej jednak technologia STARK szybko się rozwija. Nawet dzisiaj technologie oparte na GKR pokazują obiecujące możliwości zwiększenia tej liczby do około 100-200 tys.

Oprócz weryfikacji bloków są również inne przypadki użycia świadków.

Oprócz weryfikacji bloków są również inne kluczowe przypadki użycia mogące umożliwić bardziej wydajną weryfikację bezstanu:

  • Pula pamięci: gdy transakcje są nadawane, węzły w sieci p2p muszą zweryfikować ważność transakcji przed ich ponownym nadawaniem. Dziś weryfikacja obejmuje nie tylko sprawdzenie podpisu, ale także sprawdzenie, czy bilans jest wystarczający i czy liczba losowa jest poprawna. W przyszłości (np. używając natywnej abstrakcji konta, takiej jak EIP-7701), może to obejmować uruchomienie pewnego kodu EVM, który wykonuje pewne operacje dostępu do stanu. Jeśli węzeł jest bezstanu, transakcja będzie wymagać dowodu stanu obiektu.

  • Lista zawierająca: to proponowana funkcja, która pozwala (być może małym i prostym) walidatorom proof-of-stake wymusić, aby następny blok zawierał transakcje, niezależnie od (możliwe, że dużych i skomplikowanych) chęci budowniczego bloku. To zmniejszy zdolność potężnych uczestników do manipulowania blockchainem poprzez opóźnianie transakcji. Niemniej jednak to wymaga, aby walidatorzy mieli sposób na weryfikację ważności transakcji na liście zawierającej.

  • Lekki klient: Jeśli chcemy, aby użytkownicy uzyskiwali dostęp do łańcucha przez portfel (np. Metamask, Rainbow, Rabby...), nie ufając scentralizowanym uczestnikom, będą musieli uruchomić lekki klient (np. Helios). Główny moduł Helios zapewnia użytkownikom zweryfikowany korzeń stanu. Niemniej jednak, aby uzyskać całkowicie zaufany doświadczenie, użytkownicy muszą dostarczyć dowód dla każdego pojedynczego wywołania RPC, które wykonują (np. dla żądania eth_call, użytkownicy muszą mieć dowód dla wszystkich stanów, do których mają dostęp podczas wywołania);

Wspólnym punktem dla wszystkich tych zastosowań jest to, że wymagają one znacznej ilości dowodów, ale każdy dowód jest mały. Dlatego dowody STARK są dla nich w rzeczywistości niepraktyczne; zamiast tego, bezpośrednie użycie gałęzi Merkle jest bardziej realistyczne. Inną zaletą gałęzi Merkle jest to, że są one aktualizowalne: mając dowód obiektu stanu X z korzeniem bloku B, jeśli otrzymasz podblok B2 z jego świadkiem, możesz zaktualizować ten dowód, aby miał korzeń z bloku B2. Dowody Verkle same w sobie są również aktualizowalne.

Jakie są powiązania z istniejącymi badaniami?

Drzewo Verkle: https://vitalik.eth.limo/general/2021/06/18/verkle.html

Oryginalny artykuł na temat drzew Verkle autorstwa Johna Kuszmaula: https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf

Dane dowodowe Starkware: https://x.com/StarkWareLtd/status/1807776563188162562

Artykuł Poseidon2: https://eprint.iacr.org/2023/323

Ajtai (alternatywny szybki haszujący funkcja oparta na trudności kratowej): https://www.wisdom.weizmann.ac.il/~oded/COL/cfh.pdf

Verkle.info: https://verkle.info/

Co jeszcze trzeba zrobić, co trzeba zrównoważyć?

Główne prace do wykonania to:

  • Więcej analiz konsekwencji EIP-4762 (zmiany kosztów gazu bezstanu)

  • Więcej pracy wykonane i przetestowane programy przejściowe, co stanowi dużą część złożoności każdego EIP bezstanu

  • Więcej analizy bezpieczeństwa dotyczącej funkcji haszujących Poseidon, Ajtai i innych 'przyjaznych STARK' funkcji haszujących

  • Dalszy rozwój ultraefektywnych protokołów STARK dla 'zachowawczych' (lub 'tradycyjnych') funkcji haszujących, takich jak koncepcje oparte na Binius lub GKR.

Wkrótce podejmiemy decyzję, który z następujących trzech punktów wyboru zostanie wybrany: (i) drzewo Verkle, (ii) przyjazne dla STARK funkcje haszujące oraz (iii) zachowawcze funkcje haszujące. Ich właściwości można w dużej mierze podsumować w następującej tabeli:

Oprócz tych 'liczb nagłówkowych' istnieje kilka innych ważnych czynników do rozważenia:

  • Obecnie kod drzewa Verkle jest już dość dojrzały. Używanie czegokolwiek innego niż Verkle w rzeczywistości opóźni wdrożenie, prawdopodobnie poprzez twardy fork. Może to nie być problem, szczególnie jeśli i tak potrzebujemy dodatkowego czasu na analizę funkcji haszujących lub implementację dowodzących, i jeśli mamy inne ważne funkcje, które chcemy jak najszybciej włączyć do Ethereum.

  • Aktualizowanie korzenia stanu z hasza jest szybsze niż używanie drzewa Verkle. Oznacza to, że podejście oparte na haszach może skrócić czas synchronizacji pełnego węzła.

  • Drzewo Verkle ma interesujące właściwości aktualizacji świadków - świadectwa Verkle są aktualizowalne. Ta właściwość jest przydatna dla puli pamięci, list zawierających i innych zastosowań, a także może pomóc w zwiększeniu efektywności implementacji: jeśli zaktualizujesz obiekt stanu, możesz zaktualizować świadectwo przedostatniego poziomu, nawet nie odczytując ostatniego poziomu.

  • Drzewo Verkle jest trudniejsze do udowodnienia za pomocą SNARK. Jeśli chcemy zmniejszyć rozmiar dowodu do kilku tysięcy bajtów, dowody Verkle stają się problematyczne. Dzieje się tak, ponieważ weryfikacja dowodów Verkle wprowadza dużą ilość operacji 256-bitowych, co wymaga, aby system dowodowy miał dużą wydajność lub miał własną niestandardową strukturę wewnętrzną zawierającą 256-bitowe części dla dowodów Verkle.

Jeśli chcemy, aby aktualizacja świadków Verkle była w sposób kwantowo bezpieczny i stosunkowo wydajny, inną możliwą drogą jest w oparciu o drzewo Merkle oparte na siatce.

Jeśli system dowodowy nie jest wystarczająco skuteczny w najgorszym przypadku, możemy zastosować innego 'królika wyciągniętego z kapelusza', aby zrekompensować tę niedostateczność, a mianowicie wielowymiarowy gaz: osobne limity gazu dla (i) calldata, (ii) obliczeń, (iii) dostępu do stanu oraz ewentualnie innych różnych zasobów. Wielowymiarowy gaz zwiększa złożoność, ale w zamian bardziej rygorystycznie ogranicza stosunek między średnim przypadkiem a najgorszym przypadkiem. W przypadku wielowymiarowego gazu teoretyczna maksymalna liczba gałęzi, które trzeba udowodnić, może zmniejszyć się z 30,000,000 / 2400 = 12,500 do 3000. To sprawiłoby, że BLAKE3 (na styk) byłoby wystarczające, nawet dzisiaj, bez dalszych usprawnień dowodów.

Wielowymiarowy gaz pozwala ograniczeniom zasobów bloków bardziej zbliżyć się do ograniczeń zasobów sprzętowych.

Kolejnym 'królikiem wyciągniętym z kapelusza' jest propozycja opóźnienia obliczenia korzenia stanu do slotu po bloku. To da nam całe 12 sekund na obliczenie korzenia stanu, co oznacza, że nawet w najskrajniejszych przypadkach wystarczy około 60,000 haszy/sekundę czas dowodu, co ponownie stawia nas na granicy wystarczającej dla BLAKE3.

Wadą tego podejścia jest to, że zwiększa to opóźnienie lekko klienta o jeden okres, chociaż technologia ma mądrzejsze wersje, które mogą zredukować to opóźnienie do samego opóźnienia generowania dowodu. Na przykład, jakikolwiek węzeł generujący dowód może rozgłaszać ten dowód w sieci, zamiast czekać na następny blok.

Jak to współdziała z innymi częściami mapy drogowej?

Rozwiązanie problemu braku stanu znacznie zwiększa wygodę samodzielnego stakowania. Jeśli możliwe będzie obniżenie minimalnego salda dla samodzielnego stakowania (np. Orbit SSF lub strategie na poziomie aplikacji, takie jak staking w grupach), stanie się to bardziej wartościowe.

Jeśli wprowadzenie EOF, wielowymiarowy gaz stanie się łatwiejszy. Dzieje się tak, ponieważ jedną z kluczowych złożoności wielowymiarowego gazu używanego do wykonania jest zajmowanie się podwywołaniami, które nie przekazują pełnego gazu rodzica, podczas gdy EOF po prostu czyni takie podwywołania nielegalnymi (a natywna abstrakcja konta zapewni alternatywne protokoły dla głównych zastosowań podwywołań gazu w czasie bieżącym).

Inną ważną synergii jest współpraca weryfikacji bezstanu i historycznej wygaszenia danych. Obecnie klienci muszą przechowywać blisko TB danych historycznych; te dane są kilka razy większe niż dane krajowe. Nawet jeżeli klient byłby bezpaństwowy, chyba że zdołamy również złagodzić odpowiedzialność klienta za przechowywanie historii, marzenie o kliencie prawie bez pamięci nie może być zrealizowane. Pierwszym krokiem w tym kierunku jest EIP-4444, co również oznacza przechowywanie danych historycznych w sieci torrent lub w Portalu.

Dowód ważności wykonania EVM

Jakie problemy chcemy rozwiązać?

Długoterminowy cel weryfikacji bloków Ethereum jest jasny: powinieneś być w stanie zweryfikować blok Ethereum, (i) pobierając ten blok, a może nawet pobierając tylko małą część tego bloku i przeprowadzając próbę dostępności danych, oraz (ii) weryfikując niewielką część dowodów, że blok jest ważny. To będzie operacja zużywająca bardzo mało zasobów, która może być wykonana na mobilnym kliencie, portfelu przeglądarki, a nawet (bez części dostępności danych) na innym łańcuchu.

Aby to osiągnąć, trzeba mieć (i) warstwę konsensusu (tj. proof-of-stake) oraz (ii) warstwę wykonania (tj. EVM) dowody SNARK lub STARK. Pierwsza sama w sobie stanowi wyzwanie, które powinno być rozwiązane w trakcie dalszych usprawnień warstwy konsensusu (np. ostateczności jednolufowej). Druga wymaga dowodów wykonania EVM.

Co to jest i jak to działa?

Formalnie, w specyfikacji Ethereum, EVM definiowane jest jako funkcja przejścia stanu: masz pewien stan początkowy S, blok B, i obliczasz stan końcowy S' = STF(S, B). Jeśli użytkownik korzysta z lekkiego klienta, nie ma S i S', nawet nie ma pełnego B; zamiast tego mają korzeń stanu początkowego R, korzeń stanu końcowego R' oraz hasz bloku H. Pełne zdanie, które trzeba udowodnić, to mniej więcej:

  • Wspólne dane wejściowe: korzeń stanu początkowego R, korzeń stanu końcowego R', hasz bloku H.

  • Prywatne dane wejściowe: obiekt w stanie bloków B i Q, ten sam obiekt po wykonaniu bloku Q', dowód stanu (np. gałąź Merkle) P.

  • Twierdzenie 1: P jest ważnym dowodem na to, że Q zawiera pewne części stanu reprezentowanego przez R.

  • Twierdzenie 2: Jeśli uruchomisz STF na Q, (i) wykonanie uzyskuje dostęp tylko do obiektów wewnętrznych Q, (ii) blok jest ważny, a (iii) wynik to Q'.

  • Twierdzenie 3: Jeśli przeliczysz nowy korzeń stanu używając informacji z Q' i P, otrzymasz R'.

Jeśli istnieje, możesz mieć lekki klient, który może w pełni zweryfikować wykonanie EVM Ethereum. To sprawia, że zasoby klienta są już całkiem małe. Aby uzyskać naprawdę w pełni zweryfikowany klient Ethereum, musisz zrobić to samo dla strony konsensusu.

Implementacja dowodów ważności wykonania EVM już istnieje i jest szeroko stosowana przez L2. Jednak aby dowody ważności EVM były stosowane na L1, jest wiele pracy do zrobienia.

Jakie są powiązania z istniejącymi badaniami?

EC PSE ZK-EVM (już nieaktualne, ponieważ istnieją lepsze opcje): https://github.com/privacy-scaling-explorations/zkevm-Circuits

Zeth, który działa na zasadzie kompilacji EVM do RISC-0 ZK-VM: https://github.com/risc0/zeth

Projekt formalnej weryfikacji ZK-EVM: https://verified-zkevm.org/

Co jeszcze trzeba zrobić, co trzeba zrównoważyć?

Obecnie dowód ważności EVM nie jest wystarczająco adekwatny w dwóch aspektach: bezpieczeństwa i czasu dowodzenia.

Dowód bezpieczeństwa wymaga zapewnienia, że SNARK faktycznie weryfikuje obliczenia EVM i że nie zawiera błędów. Dwie główne techniki zwiększające bezpieczeństwo to wielokrotni dowodzący oraz weryfikacja formalna. Wielu dowodzących oznacza posiadanie wielu niezależnie napisanych implementacji dowodów ważności, tak jak jest wiele klientów, i jeśli wystarczająco duży podzbiór tych implementacji udowodni jakiś blok, to pozwoli klientowi zaakceptować ten blok. Weryfikacja formalna polega na użyciu narzędzi często używanych do dowodzenia twierdzeń matematycznych (np. Lean4), aby udowodnić, że dowody ważności akceptują tylko poprawne wykonania wejść zgodnych z EVM napisanym w Pythonie.

Dostatecznie szybki czas dowodu oznacza, że każdy blok Ethereum można udowodnić w mniej niż 4 sekundy. Dziś jesteśmy daleko od tego celu, chociaż jesteśmy znacznie bliżej niż dwa lata temu. Aby to osiągnąć, musimy zrobić postępy w trzech obszarach:

  • Równoległość — najszybsze dziś dowody EVM mogą udowodnić średni blok Ethereum w około 15 sekund. Osiąga się to przez równoległe przetwarzanie w setkach GPU, a następnie agregowanie ich pracy. Teoretycznie dokładnie wiemy, jak stworzyć dowód EVM, który może udowodnić obliczenia w O(log(N)) czasu: pozwól jednemu GPU wykonać każdy krok, a następnie przeprowadź 'drzewo agregacji':

Wdrożenie tego napotka wyzwania. Nawet w najgorszym przypadku (tj. bardzo duże transakcje zajmujące cały blok) obliczenia nie mogą być dzielone według transakcji; muszą być wykonywane według każdego kodu operacyjnego (EVM lub dolnego VM, takiego jak RISC-V). Kluczowym wyzwaniem implementacyjnym, które czyni to nieco trudnym, jest zapewnienie, że 'pamięć' VM jest spójna między różnymi częściami dowodu. Niemniej jednak, jeśli możemy przeprowadzić takie dowody rekurencyjne, wiemy, że przynajmniej problem opóźnienia dowodzącego został rozwiązany, nawet jeśli nie ma żadnych ulepszeń w innych obszarach.

  • Optymalizacja systemu dowodowego — nowe systemy dowodowe, takie jak Orion, Binius, GKR, mogą ponownie znacznie zmniejszyć czasy dowodzenia dla ogólnych obliczeń.

  • Koszty gazu EVM są inne w przypadku innych zmian — wiele rzeczy w EVM można zoptymalizować, aby były bardziej przyjazne dla dowodzących, zwłaszcza w najgorszym przypadku. Jeśli atakujący mógłby zbudować blok, który zajmie dowodzącemu dziesięć minut, to tylko udowodnienie średniego bloku Ethereum w 4 sekundy nie wystarczy. Wymagane zmiany w EVM można zasadniczo podzielić na dwie kategorie:

  • Zmiany kosztów gazu — jeśli operacja zajmuje dużo czasu na udowodnienie, to nawet jeśli szybkość obliczeń jest stosunkowo wysoka, powinna mieć wyższy koszt gazu. EIP-7667 to proponowany EIP, który zajmuje się najpoważniejszymi problemami w tej dziedzinie: znacząco zwiększa koszty gazu dla (tradycyjnych) funkcji haszujących, które są relatywnie tanimi kodami operacyjnymi i wstępnie skompilowanymi. Aby zrekompensować ten wzrost kosztów gazu, możemy obniżyć koszty gazu dla relatywnie tanich kodów operacyjnych EVM, aby zachować tę samą średnią przepustowość.

  • Zastąpienie struktury danych — poza zastąpieniem drzewa stanu bardziej odpowiednimi alternatywami, musimy również zastąpić listy transakcji, drzewa recepty i inne struktury, które mają wysokie koszty dowodowe. EIP Ethana Kisslinga przesuwa struktury transakcji i recepty do SSZ ([1] [2] [3]), co jest krokiem w tym kierunku.

Oprócz tego, co wspomniano w poprzedniej sekcji, dwa 'króliki wyciągnięte z kapelusza' (wielowymiarowy gaz i opóźniony korzeń stanu) mogą również pomóc w tej sprawie. Warto jednak zauważyć, że w przeciwieństwie do weryfikacji bezstanu, weryfikacja bezstanu oznacza, że mamy wystarczająco dużo technologii, aby zrealizować to, co potrzebujemy dzisiaj, nawet korzystając z tych technologii, pełna weryfikacja ZK-EVM będzie wymagała dodatkowej pracy — po prostu potrzebuje mniej pracy.

Jedną z rzeczy, które nie zostały wspomniane powyżej, jest sprzęt do dowodzenia: generowanie dowodów szybciej za pomocą GPU, FPGA i ASIC. Fabric Cryptography, Cysic i Accseal to pioniery tych trzech firm. Jest to bardzo cenne dla warstwy 2, ale mało prawdopodobne, by stało się decydującym czynnikiem dla warstwy 1, ponieważ silnie dąży się do zachowania wysokiej decentralizacji warstwy 1, co oznacza, że generowanie dowodów musi mieścić się w zakresie możliwości dość dużego podzbioru użytkowników Ethereum, bez napotkania wąskiego gardła ze strony pojedynczej firmy zajmującej się sprzętem. Warstwa 2 może podejmować bardziej radykalne decyzje.

W tych obszarach jest jeszcze wiele do zrobienia:

  • Dowody równoległe wymagają systemu dowodowego, w którym różne części dowodu mogą „dzielić pamięć” (np. tablice przeszukiwania). Znamy technologie, które to umożliwiają, ale wymagają one implementacji.

  • Potrzebujemy więcej analiz, aby znaleźć idealny zestaw zmian kosztów gazu, aby zminimalizować czas dowodzenia w najgorszym przypadku.

  • Musimy wykonać więcej pracy nad systemem dowodowym.

Możliwe tu kompromisy to:

  • Bezpieczeństwo a czas dowodzącego: użycie silnych funkcji haszujących, systemów dowodowych z bardziej złożonymi lub bardziej aktywnymi założeniami bezpieczeństwa lub innych wyborów projektowych, może zredukować czas dowodzącego.

  • Decentralizacja a czas dowodzącego: społeczność musi uzgodnić 'specyfikację' sprzętu dowodzącego, którego chce. Czy wymóg, aby dowodzący był dużą instytucją, jest akceptowalny? Czy chcemy, aby wysokiej klasy laptopy konsumenckie mogły udowodnić blok Ethereum w 4 sekundy? Coś pomiędzy tymi dwoma skrajnościami?

  • Stopień naruszenia zgodności wstecznej: niedociągnięcia w innych obszarach mogą być naprawione przez dokonanie bardziej agresywnych zmian kosztów gazu, ale to bardziej prawdopodobnie nieproporcjonalnie zwiększy koszty niektórych aplikacji i zmusi deweloperów do przepisania i ponownego wdrożenia kodu, aby pozostać opłacalnym. Również 'królik w kapeluszu' ma swoje własne złożoności i wady.

Jak to współdziała z innymi częściami mapy drogowej?

Kluczowe technologie potrzebne do implementacji dowodów ważności EVM na poziomie 1 są w dużej mierze dzielone z innymi dwoma obszarami:

  • Dowody ważności warstwy 2 (tj. 'ZK rollups')

  • Bezstanowa metoda 'dowodu haszującego STARK'

Sukces w implementacji dowodów ważności na poziomie 1 może umożliwić łatwe samodzielne stakowanie: nawet najsłabsze komputery (w tym telefony komórkowe czy smartwatche) będą mogły stakować. To dodatkowo zwiększa wartość rozwiązania innych ograniczeń związanych z samodzielnym stakowaniem (np. minimalne 32 ETH).

Dodatkowo, dowód ważności EVM w L1 może znacząco zwiększyć limity gazowe L1.

Dowód ważności konsensusu

Jakie problemy chcemy rozwiązać?

Jeśli chcemy być w stanie w pełni zweryfikować bloki Ethereum za pomocą SNARK, to wykonanie EVM nie jest jedyną częścią, którą musimy udowodnić. Musimy również udowodnić konsensus: część systemu zajmująca się przetwarzaniem depozytów, wypłat, podpisów, aktualizacji sald walidatorów oraz innymi elementami części proof-of-stake Ethereum.

Konsensus jest znacznie prostszy niż EVM, ale stoi przed wyzwaniem, że nie mamy podsumowania EVM na warstwie 2, co jest powodem, dla którego większość pracy i tak musi zostać wykonana. W związku z tym jakiekolwiek wdrożenie dowodzenia konsensusu Ethereum musi być realizowane 'od zera', chociaż sam system dowodzenia może być budowany na wspólnej pracy.

Co to jest i jak to działa?

Łańcuch beacon jest definiowany jako funkcja przejścia stanu, tak jak EVM. Funkcja przejścia stanu jest określona przez trzy czynniki:

  • ECADD (do weryfikacji podpisów BLS)

  • Parowanie (do weryfikacji podpisów BLS)

  • Funkcja haszująca SHA256 (do odczytu i aktualizacji stanu)

W każdym bloku musimy udowodnić 1-16 operacji ECADD BLS12-381 dla każdego walidatora (może być ich więcej, ponieważ podpisy mogą być zawarte w wielu agregacjach). Można to zrekompensować za pomocą techniki wstępnego obliczenia podzbioru, więc możemy powiedzieć, że każdy walidator to jeden ECADD BLS12-381. Obecnie w każdym okresie jest około 30,000 walidatorów podpisujących. W przyszłości, dla ostateczności jednolufowej, może to zmienić się w dowolnym kierunku (zobacz instrukcje tutaj): jeśli podejmiemy 'silową' strategię, liczba walidatorów w każdym slocie może wzrosnąć do miliona. Z drugiej strony, używając Orbit SSF, pozostanie na poziomie 32,768, a nawet zmniejszy się do 8,1.

Jak działa agregacja BLS. Weryfikacja agregowanych podpisów wymaga jedynie ECADD od każdego uczestnika, a nie ECMUL. Ale 30,000 ECADD to wciąż dużo do udowodnienia.

Dla parowania, obecnie w każdym slocie może być maksymalnie 128 dowodów, co oznacza, że trzeba zweryfikować 128 par. Dzięki EIP-7549 i dalszym zmianom, może to zostać zredukowane do 16 par w każdym slocie. Liczba par jest niewielka, ale koszty są ogromne: czas działania (lub dowodzenia) każdej pary jest tysiące razy dłuższy niż ECADD.

Głównym wyzwaniem w dowodzeniu operacji BLS12-381 jest brak wygodnej krzywej, której rząd byłby równy rozmiarowi pola BLS12-381, co wprowadza znaczną nadwyżkę dla każdego systemu dowodowego. Z drugiej strony, drzewo Verkle zaproponowane dla Ethereum jest zbudowane na krzywej Bandersnatch, co czyni BLS12-381 naturalną krzywą w systemach SNARK używaną do dowodzenia gałęzi Verkle. Stosunkowo prosta implementacja może dostarczyć około 100 G1 dodanych na sekundę; prawie na pewno będzie potrzebne coś mądrego, jak GKR, aby udowodnić wystarczająco szybko.

Dla wartości haszującej SHA256, najgorszy przypadek dotyczy bloków przejściowych epok, w których cała krótka drzewo bilansów walidatorów oraz wiele bilansów walidatorów ulegają aktualizacji. Krótkie drzewo bilansów walidatorów ma tylko jeden bajt na walidatora, więc około 1 MB danych będzie ponownie haszowanych. To odpowiada 32,768 wywołaniom SHA256. Jeśli saldo tysiąca walidatorów jest poniżej lub powyżej progu, należy zaktualizować ważne salda w rekordzie walidatora, co odpowiada tysiącom gałęzi Merkle, co oznacza, że może to być również 10,000 haszy. Mechanizm mieszania wymaga 90 bitów na walidatora (więc wymaga 11 MB danych), ale można to obliczyć w dowolnym momencie procesu epok. Dla ostateczności jednolufowej liczby te mogą ponownie wzrosnąć lub zmaleć w zależności od szczegółów. Mieszanie staje się niepotrzebne, chociaż tory mogą w pewnym stopniu przywrócić potrzebę mieszania.

Kolejnym wyzwaniem jest potrzeba odczytania stanu wszystkich walidatorów (w tym kluczy publicznych), aby zweryfikować blok. Dla miliona walidatorów, wraz z gałęzią Merkle, odczytanie klucza publicznego wymaga 48 milionów bajtów. Wymaga to milionów haszy na każdy okres. Jeśli dzisiaj musimy udowodnić weryfikację proof-of-stake, to realistycznym podejściem byłoby pewna forma inkrementalnego obliczenia weryfikowalnego: przechowywanie oddzielnej struktury danych w systemie dowodowym, która jest zoptymalizowana do efektywnego wyszukiwania i oferuje aktualizacje tej struktury.

Podsumowując, istnieje wiele wyzwań.

Aby najskuteczniej rozwiązać te wyzwania, prawdopodobnie będzie potrzebne głębokie przeprojektowanie łańcucha beacon, co może wystąpić równocześnie z przejściem na jednolufową ostateczność. Ta przeprojektowanie może obejmować:

  • Zmiana funkcji haszującej: obecnie używana jest 'pełna' funkcja haszująca SHA256, co oznacza, że z powodu dopełnienia każde wywołanie odpowiada dwóm wywołaniom podstawowej funkcji kompresji. Przynajmniej możemy uzyskać 2-krotny zysk, przełączając się na funkcję kompresji SHA256. Jeśli przejdziemy na Poseidon, możemy uzyskać około 100-krotne zyski, co może całkowicie rozwiązać wszystkie nasze problemy (przynajmniej dla hasza): 1.7 miliona haszy na sekundę (54 MB), a nawet można 'przeczytać milion rekordów walidatorów' w ciągu kilku sekund.

  • Jeśli chodzi o Orbit, bezpośrednio przechowuj pomieszane rekordy walidatorów: jeśli wybierzesz określoną liczbę walidatorów (np. 8,192 lub 32,768) jako komitet dla danego slotu, umieść je bezpośrednio w sąsiadujących stanach, aby zminimalizować ilość haszy do odczytania wszystkich kluczy publicznych walidatorów w dowodzie. To również pozwoli efektywnie przeprowadzić wszystkie aktualizacje sald.

  • Agregacja podpisów: każdy wysoko wydajny system agregacji podpisów w rzeczywistości będzie wiązał się z jakimś rodzajem dowodu rekurencyjnego, gdzie pośredni dowód podzbioru podpisów będzie generowany przez różne węzły w sieci. To naturalnie rozprasza obciążenie dowodowe na wiele węzłów w sieci, co znacznie zmniejsza obciążenie 'ostatecznego dowodzącego'.

  • Inne schematy podpisów: dla podpisów Lamporta+Merkle potrzebujemy 256+32 haszy do weryfikacji podpisu; pomnożone przez 32,768 podpisujących daje 9,437,184 haszy. Optymalizacja schematów podpisów może to jeszcze poprawić przez mały czynnik stały. Jeśli użyjemy Poseidona, to w zakresie dowodów w pojedynczym slocie.

Jakie są powiązania z istniejącymi badaniami?

Zwięzły dowód konsensusu Ethereum (tylko dla komitetu synchronizacji): https://github.com/succinctlabs/eth-proof-of-consensus

Zwięzły, Helios w SP1: https://github.com/succinctlabs/sp1-helios

Zwięzły BLS12-381 prekompilat: https://blog.succinct.xyz/succinctshipsprecompiles/

Weryfikacja podpisów agregowanych BLS oparta na Halo2: https://ethresear.ch/t/zkpos-with-halo2-pairing-for-verifying-aggregate-bls-signatures/14671

Co jeszcze trzeba zrobić, co trzeba zrównoważyć?

W rzeczywistości potrzebujemy wielu lat, aby uzyskać dowód ważności konsensusu Ethereum. To mniej więcej odpowiada czasowi, który potrzebujemy na implementację ostateczności jednolufowej, torów, zmian algorytmu podpisu oraz potencjalnych analiz bezpieczeństwa, aby mieć wystarczającą pewność co do użycia 'agresywnej' funkcji haszującej, takiej jak Poseidon. Dlatego rozwiązywanie tych innych problemów ma największy sens i należy pamiętać o przyjazności STARK podczas wykonywania tych prac.

Główne kompromisy będą prawdopodobnie polegały na kolejności działań, między bardziej stopniowym podejściem do reformy warstwy konsensusu Ethereum a bardziej radykalnym 'wprowadzeniem wielu zmian jednocześnie'. Dla EVM podejście stopniowe ma sens, ponieważ minimalizuje zniszczenie zgodności wstecznej. W przypadku warstwy konsensusu problemy z zgodnością wsteczną są mniejsze, a lepiej jest szeroko przemyśleć różne szczegóły dotyczące budowy łańcucha beacon, aby jak najlepiej zoptymalizować przyjazność STARK.

Jak to współdziała z innymi częściami mapy drogowej?

Przyjazność STARK powinna stać się głównym punktem długoterminowego przeprojektowania konsensusu proof-of-stake Ethereum, w szczególności ostateczności jednolufowej, Orbit, zmiany schematu podpisów i agregacji podpisów.