Nowy artykuł Vitalika: Możliwa przyszłość protokołu Ethereum – The Verge

W rzeczywistości potrzebujemy kilku lat, aby uzyskać dowód poprawności konsensusu Ethereum.

Oryginalny tytuł: „Possible futures of the Ethereum protocol, part 4: The Verge”

Autor: Vitalik Buterin

Tłumaczenie: Mensh, ChainCatcher

 

Szczególne podziękowania dla Justina Drake'a, Hsia-wei Wanp, Guillaume Ballet, Icinacio, Rosh Rudolfa, Lev Soukhanoy, Ryan Sean Adams i Uma Roy za opinie i recenzję.

Jedną z najsilniejszych funkcji blockchaina jest to, że każdy może uruchomić węzeł na swoim komputerze i zweryfikować poprawność blockchaina. Nawet jeśli 9596 węzłów uruchamiających konsensus łańcucha (PoW, PoS) natychmiast zgodzi się na zmianę zasad i zacznie produkować bloki według nowych zasad, każdy, kto uruchamia w pełni weryfikujący węzeł, odmówi akceptacji tego łańcucha. Emitenci monet, którzy nie należą do tej grupy spiskowców, automatycznie zgromadzą się wokół łańcucha, który nadal przestrzega starych zasad i będą go dalej rozwijać, a użytkownicy w pełni weryfikujący będą podążać za tym łańcuchem.

To kluczowa różnica między blockchainem a systemami scentralizowanymi. Jednak aby ta cecha była spełniona, uruchomienie w pełni weryfikującego węzła musi być rzeczywiście wykonalne dla wystarczająco dużej liczby osób. Dotyczy to zarówno walidatorów (ponieważ jeśli walidatorzy nie weryfikują łańcucha, nie przyczyniają się do egzekwowania zasad protokołu), jak i zwykłych użytkowników. Obecnie uruchomienie węzła na laptopie konsumenckim (w tym na laptopie używanym do pisania tego artykułu) jest możliwe, ale trudne. The Verge ma to zmienić, czyniąc koszt obliczeniowy pełnej weryfikacji łańcucha bardzo niski, tak aby każdy portfel mobilny, portfel przeglądarkowy, a nawet smartwatch domyślnie dokonywał weryfikacji.

Mapa drogowa The Verge 2023

Początkowo „Verge” odnosiło się do przeniesienia przechowywania stanu Ethereum do drzew Verkle — struktury drzewiastej umożliwiającej bardziej zwarte dowody, pozwalającej na bezstanową weryfikację bloków Ethereum. Węzeł może zweryfikować blok Ethereum bez przechowywania na swoim dysku żadnego stanu Ethereum (saldo kont, kod kontraktów, przestrzeń magazynowa...), kosztem kilku setek KB danych dowodowych i kilkuset milisekund dodatkowego czasu na weryfikację dowodu. Dziś Verge oznacza większą wizję, skupioną na osiągnięciu maksymalnej efektywności zasobów w weryfikacji łańcucha Ethereum, obejmującą nie tylko techniki bezstanowej weryfikacji, ale także użycie SNARK do weryfikacji całego wykonania Ethereum.

Oprócz długoterminowego skupienia na SNARK dla całego łańcucha, pojawił się nowy problem: czy drzewa Verkle są najlepszą technologią. Drzewa Verkle są podatne na ataki komputerów kwantowych, więc jeśli zamienimy obecne drzewa KECCAK Merkle Patricia na drzewa Verkle, w przyszłości będziemy musieli ponownie je wymienić. Samozastępowalną metodą dla drzew Merkle jest pominięcie gałęzi Merkle i użycie STARK, umieszczając je w drzewie binarnym. Historycznie, ze względu na koszty i złożoność techniczną, metoda ta była uznawana za niewykonalną. Jednak ostatnio widzimy, że Starkware na laptopie używającym ckcle STARKs dowodzi 1,7 miliona haszy Poseidon na sekundę, a dzięki technikom takim jak GKB czas dowodzenia dla bardziej „tradycyjnych” haszy również szybko się skraca. Dlatego w ciągu ostatniego roku „Verge” stało się bardziej otwarte i ma kilka możliwych ścieżek.

The Verge: kluczowe cele

• Bezstanowy klient: przestrzeń dyskowa wymagana dla w pełni weryfikującego klienta i węzła znacznikowego nie powinna przekraczać kilku GB.
• (Długoterminowo) Pełna weryfikacja łańcucha (konsensus i wykonanie) na smartwatchu. Pobierz trochę danych, zweryfikuj SNARK, gotowe.

W tym rozdziale

• Bezstanowy klient: Verkle czy STARKs
• Dowód poprawności wykonania EVM
• Dowód poprawności konsensusu

Bezstanowa weryfikacja: Verkle czy STARKs

Jaki problem chcemy rozwiązać?

Obecnie klient Ethereum musi przechowywać setki gigabajtów danych stanu, aby zweryfikować blok, a ilość ta rośnie co roku. Surowe dane stanu rosną o około 30GB rocznie, a pojedynczy klient musi przechowywać dodatkowe dane, aby efektywnie aktualizować trójki.

To ogranicza liczbę użytkowników mogących uruchomić w pełni weryfikujący węzeł Ethereum: chociaż duże dyski twarde zdolne do przechowywania całego stanu Ethereum, a nawet wielu lat historii, są powszechne, komputery kupowane domyślnie często mają tylko kilkaset GB przestrzeni. Rozmiar stanu powoduje także ogromne tarcia przy początkowej synchronizacji węzła: trzeba pobrać cały stan, co może zająć godziny lub dni. Powoduje to różne efekty łańcuchowe. Na przykład znacznie utrudnia walidatorom aktualizację konfiguracji węzła. Technicznie można to zrobić bez przestoju — uruchomić nowego klienta, poczekać na synchronizację, potem wyłączyć starego klienta i przenieść klucze — ale w praktyce jest to bardzo złożone technicznie.

Jak to działa?

Bezstanowa weryfikacja to technika pozwalająca węzłom weryfikować bloki bez posiadania całego stanu. Zamiast tego każdy blok zawiera świadectwo, które obejmuje: (i) wartości, kod, saldo, magazyn w określonych miejscach stanu, do których blok uzyska dostęp; (ii) kryptograficzny dowód poprawności tych wartości.

W praktyce wdrożenie bezstanowej weryfikacji wymaga zmiany struktury drzewa stanu Ethereum. Obecne drzewo Merkle Patricia jest bardzo nieprzyjazne dla jakiegokolwiek schematu kryptograficznego dowodzenia, zwłaszcza w najgorszym przypadku. Dotyczy to zarówno „surowych” gałęzi Merkle, jak i możliwości „opakowania” ich w STARK. Główna trudność wynika z kilku słabości MPT:

1. To drzewo szesnastkowe (każdy węzeł ma 16 dzieci). Oznacza to, że w drzewie o rozmiarze N dowód wymaga średnio 32*(16-1)*log16(N) = 120*log2(N) bajtów, czyli dla drzewa o 2^32 elementach około 3840 bajtów. W drzewie binarnym potrzeba tylko 32*(2-1)*log2(N) = 32*log2(N) bajtów, czyli około 1024 bajtów.

2. Kod nie jest objęty Merkle. Oznacza to, że aby udowodnić dostęp do kodu konta, trzeba dostarczyć cały kod, maksymalnie 24000 bajtów.

 

Możemy obliczyć najgorszy przypadek następująco:

30000000 gas / 2400 (koszt odczytu zimnego konta) * (5 * 488 + 24000) = 330000000 bajtów

Koszt gałęzi jest nieco niższy (używając 5*480 zamiast 8*480), ponieważ gdy jest wiele gałęzi, ich górne części się powtarzają. Mimo to ilość danych do pobrania w jednym slocie jest całkowicie nierealistyczna. Jeśli spróbujemy opakować to w STARK, napotkamy dwa problemy: (i) KECCAK jest stosunkowo nieprzyjazny dla STARK; (ii) 330MB danych oznacza, że musimy udowodnić 5 milionów wywołań funkcji rundy KECCAK, co może być nie do udowodnienia dla każdego sprzętu poza najmocniejszymi komputerami konsumenckimi, nawet jeśli uda się zoptymalizować dowodzenie KECCAK w STARK.

Jeśli bezpośrednio zastąpimy drzewo szesnastkowe drzewem binarnym i dodatkowo objęlibyśmy kod Merkle, najgorszy przypadek wynosiłby około 30000000/2400*32*(32-14+8) = 10400000 bajtów (14 to redukcja dla nadmiarowych bitów dla 2^14 gałęzi, a 8 to długość dowodu wejścia do liścia kodu). Warto zauważyć, że wymaga to zmiany kosztów gas, pobierając opłatę za dostęp do każdego bloku kodu; EIP-4762 robi to właśnie tak. 10,4 MB to znacznie lepiej, ale dla wielu węzłów to wciąż za dużo danych do pobrania w jednym slocie. Dlatego potrzebujemy mocniejszych technik. W tej dziedzinie są dwa wiodące rozwiązania: drzewa Verkle i STARKowane binarne drzewa haszujące.

Drzewa Verkle

Drzewa Verkle używają zobowiązań wektorowych opartych na krzywych eliptycznych do uzyskania krótszych dowodów. Kluczowe jest to, że niezależnie od szerokości drzewa, każda część dowodu odpowiadająca relacji rodzic-dziecko ma tylko 32 bajty. Jedynym ograniczeniem szerokości drzewa jest to, że zbyt szerokie drzewo obniża efektywność obliczeniową dowodu. Proponowana dla Ethereum szerokość to 256.

Zatem rozmiar pojedynczej gałęzi dowodu wynosi 32 - 1og256(N) = 4*log2(N) bajtów. Teoretyczny maksymalny rozmiar dowodu to około 30000000 / 2400 *32* (32 -14 + 8) / 8 = 130000 bajtów (ze względu na nierównomierny rozkład bloków stanu rzeczywisty wynik jest nieco inny, ale jako pierwsze przybliżenie jest poprawny).

Warto też zauważyć, że w powyższych przykładach ten „najgorszy przypadek” nie jest najgorszy: gorszy przypadek to atakujący celowo „kopiący” dwa adresy, tak by miały długi wspólny prefiks w drzewie i odczytujący dane z jednego z nich, co może podwoić długość gałęzi w najgorszym przypadku. Nawet wtedy najgorsza długość dowodu w drzewie Verkle to 2,6MB, co odpowiada obecnemu najgorszemu przypadkowi danych weryfikacyjnych.

Wykorzystaliśmy też tę obserwację do innej rzeczy: koszt dostępu do „sąsiadujących” przestrzeni magazynowych jest bardzo niski: czy to wiele bloków kodu tego samego kontraktu, czy sąsiadujące sloty magazynowe. EIP-4762 definiuje sąsiedztwo i pobiera tylko 200 gas za dostęp sąsiadujący. W takim przypadku najgorszy rozmiar dowodu to 30000000 / 200*32 - 4800800 bajtów, co nadal mieści się w granicach tolerancji. Jeśli dla bezpieczeństwa chcemy zmniejszyć tę wartość, możemy nieco zwiększyć opłatę za dostęp sąsiadujący.

STARKowane binarne drzewa haszujące

Zasada tej techniki jest prosta: tworzysz drzewo binarne, uzyskujesz maksymalnie 10,4 MB dowodu, dowodzisz wartości w bloku, a następnie zastępujesz dowód dowodem STARK. W ten sposób dowód zawiera tylko udowadniane dane plus 100-300kB stałego narzutu z faktycznego STARK.

Głównym wyzwaniem jest tutaj czas weryfikacji. Możemy przeprowadzić podobne obliczenia jak powyżej, tylko zamiast bajtów liczymy hasze. Blok 10,4 MB oznacza 330000 haszy. Jeśli dodamy możliwość atakującego „kopiącego” adresy o długim wspólnym prefiksie, w najgorszym przypadku będzie to około 660000 haszy. Jeśli możemy udowodnić 200 000 haszy na sekundę, nie ma problemu.

Na laptopach konsumenckich używających funkcji haszującej Poseidon te liczby są już osiągane, a Poseidon został zaprojektowany specjalnie pod kątem przyjazności dla STARK. Jednak system Poseidon jest jeszcze stosunkowo niedojrzały, więc wiele osób nie ufa jeszcze jego bezpieczeństwu. Są więc dwie realne ścieżki:

1. Szybko przeprowadzić szeroką analizę bezpieczeństwa Poseidon i dobrze go poznać, by wdrożyć na L1
2. Użyć bardziej „konserwatywnych” funkcji haszujących, takich jak SHA256 lub BLAKE

Jeśli chcemy udowodnić konserwatywne funkcje haszujące, STARK od Starkware w momencie pisania tego tekstu może udowodnić tylko 10-30k haszy na sekundę na laptopie konsumenckim. Jednak technologia STARK szybko się rozwija. Nawet dziś techniki oparte na GKR pokazują, że można osiągnąć 100-200k haszy na sekundę.

Przypadki użycia świadectw poza weryfikacją bloków

Poza weryfikacją bloków są trzy inne kluczowe przypadki użycia wymagające wydajniejszej bezstanowej weryfikacji:

• Pula pamięci: gdy transakcja jest rozgłaszana, węzły w sieci P2P muszą zweryfikować jej poprawność przed dalszym rozgłaszaniem. Obecnie weryfikacja obejmuje sprawdzenie podpisu, salda i poprawności prefiksu. W przyszłości (np. przy natywnym account abstraction, jak EIP-7701) może to obejmować uruchomienie kodu EVM, który uzyskuje dostęp do stanu. Jeśli węzeł jest bezstanowy, transakcja musi zawierać dowód dla obiektów stanu.
• Listy zawierania: to proponowana funkcja pozwalająca (prawdopodobnie mniejszym i mniej złożonym) walidatorom PoS wymusić zawarcie transakcji w następnym bloku, niezależnie od woli (być może większych i bardziej złożonych) budowniczych bloków. Osłabia to możliwość manipulowania blockchainem przez opóźnianie transakcji przez wpływowych. Wymaga to jednak, by walidatorzy mogli zweryfikować poprawność transakcji na liście zawierania.
• Lekkie klienty: jeśli chcemy, by użytkownicy uzyskiwali dostęp do łańcucha przez portfele (np. Metamask, Rainbow, Rabby), muszą uruchamiać lekkiego klienta (np. Helios). Moduł główny Helios dostarcza użytkownikowi zweryfikowany korzeń stanu. Aby uzyskać całkowicie bezpieczne doświadczenie, użytkownik musi mieć dowód dla każdego wywołania RPC (np. dla żądania call w Ethereum użytkownik musi udowodnić wszystkie stany odwiedzane podczas wywołania).

Wszystkie te przypadki mają wspólną cechę: wymagają wielu dowodów, ale każdy z nich jest mały. Dlatego dowód STARK nie ma dla nich sensu; najbardziej praktyczne jest użycie bezpośrednio gałęzi Merkle. Kolejną zaletą gałęzi Merkle jest możliwość aktualizacji: mając dowód dla obiektu stanu z korzeniem bloku B, po otrzymaniu podbloku B2 i jego świadectwa można zaktualizować dowód do korzenia B2. Dowody Verkle są natywnie aktualizowalne.

Powiązania z istniejącymi badaniami:

• Verkle trees
• Oryginalny artykuł Johna Kuszmaula o drzewach Verkle
• Starkware
• Poseidon2 paper
• Ajtai (alternatywna szybka funkcja haszująca oparta na twardości kratowej)
• Verkle.info

Co jeszcze można zrobić?

Pozostała główna praca to

1. Więcej analiz skutków EIP-4762 (zmiany kosztów gas w bezstanowym środowisku)

2. Więcej pracy nad ukończeniem i testowaniem programu przejściowego, który jest główną częścią złożoności każdej implementacji bezstanowej

3. Więcej analiz bezpieczeństwa dla Poseidon, Ajtai i innych „STARK-friendly” funkcji haszujących

4. Dalszy rozwój bardzo wydajnych protokołów STARK dla „konserwatywnych” (lub „tradycyjnych”) funkcji haszujących, np. podejścia oparte na Binius lub GKR.

Wkrótce zdecydujemy się na jedną z trzech opcji: (i) drzewa Verkle, (ii) STARK-friendly funkcje haszujące oraz (iii) konserwatywne funkcje haszujące. Ich cechy można podsumować w poniższej tabeli:

Poza tymi „głównymi liczbami” są też inne ważne kwestie:

• Kod drzew Verkle jest już dość dojrzały. Użycie jakiegokolwiek innego kodu poza Verkle opóźni wdrożenie, prawdopodobnie opóźni hard fork. To nie jest problem, zwłaszcza jeśli potrzebujemy dodatkowego czasu na analizę funkcji haszujących lub implementację walidatora, albo mamy inne ważne funkcje, które chcemy wcześniej włączyć do Ethereum.
• Aktualizacja korzenia stanu za pomocą haszy jest szybsza niż w drzewach Verkle. Oznacza to, że podejście oparte na haszach może skrócić czas synchronizacji pełnych węzłów.
• Drzewa Verkle mają ciekawe właściwości aktualizacji świadectw — dowody Verkle są aktualizowalne. Ta cecha jest przydatna dla mempool, list zawierania i innych przypadków, a także może pomóc w zwiększeniu efektywności implementacji: jeśli zaktualizowano obiekt stanu, można zaktualizować dowód na przedostatniej warstwie bez czytania ostatniej warstwy.
• Drzewa Verkle są trudniejsze do udowodnienia w SNARK. Jeśli chcemy zmniejszyć rozmiar dowodu do kilku tysięcy bajtów, dowody Verkle sprawiają pewne trudności. Wynika to z tego, że weryfikacja dowodu Verkle wprowadza wiele operacji 256-bitowych, co wymaga od systemu dowodzenia albo dużego narzutu, albo własnej wewnętrznej struktury z 256-bitowymi częściami dowodu Verkle. Dla samej bezstanowości to nie problem, ale powoduje dodatkowe trudności.

Jeśli chcemy uzyskać aktualizowalność dowodów Verkle w sposób odporny na kwanty i wystarczająco wydajny, inną możliwą ścieżką są drzewa Merkle oparte na kratowych funkcjach haszujących.

Jeśli w najgorszym przypadku efektywność systemu dowodzenia nie jest wystarczająca, możemy wykorzystać nieoczekiwane narzędzie, jakim jest wielowymiarowy gas: ustalenie osobnych limitów gas dla (i) calldata; (ii) obliczeń; (iii) dostępu do stanu oraz ewentualnie innych zasobów. Wielowymiarowy gas zwiększa złożoność, ale w zamian ściślej ogranicza stosunek między przypadkiem średnim a najgorszym. Dzięki temu teoretyczna maksymalna liczba gałęzi do udowodnienia może spaść z 12500 do np. 3000. To sprawia, że BLAKE3 nawet dziś (ledwo) wystarcza.

Wielowymiarowy gas pozwala na ograniczenia zasobów bloku bliższe ograniczeniom sprzętu

Innym nieoczekiwanym narzędziem jest opóźnienie obliczania korzenia stanu do slotu po bloku. Dzięki temu mamy całe 12 sekund na obliczenie korzenia stanu, co oznacza, że nawet w najbardziej ekstremalnych przypadkach 60000 haszy na sekundę wystarczy, co ponownie sprawia, że BLAKE3 ledwo spełnia wymagania.

Minusem tej metody jest zwiększenie opóźnienia lekkiego klienta o jeden slot, ale istnieją sprytne techniki, które mogą zredukować to opóźnienie do samego opóźnienia generowania dowodu. Na przykład dowód można rozgłaszać w sieci natychmiast po wygenerowaniu przez dowolny węzeł, bez czekania na kolejny blok.

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

Rozwiązanie problemu bezstanowości znacznie zwiększa trudność pojedynczego stakingu. Jeśli istnieją technologie obniżające minimalny balans dla pojedynczego stakingu, jak Orbit SSF lub strategie warstwy aplikacji, jak staking zespołowy, stanie się to bardziej wykonalne.

Jeśli jednocześnie wprowadzimy EOF, analiza wielowymiarowego gas stanie się łatwiejsza. Wynika to z tego, że główna złożoność wykonania wielowymiarowego gas pochodzi z obsługi wywołań podrzędnych, które nie przekazują całego gas rodzica, a EOF może po prostu uczynić takie wywołania nielegalnymi, czyniąc problem trywialnym (a natywne account abstraction zapewni protokolarne zastępstwo dla obecnych głównych przypadków częściowego gas).

Bezstanowa weryfikacja i wygasanie historii mają też ważną synergię. Obecnie klient musi przechowywać prawie 1TB danych historycznych; to wielokrotność danych stanu. Nawet jeśli klient jest bezstanowy, marzenie o niemal bezdyskowym kliencie nie spełni się, dopóki nie zdejmiemy z niego obowiązku przechowywania historii. Pierwszym krokiem jest EIP-4444, co oznacza przechowywanie danych historycznych w torrentach lub Portal Network.

Dowód poprawności wykonania EVM

Jaki problem chcemy rozwiązać?

Długoterminowy cel weryfikacji bloków Ethereum jest jasny — powinno być możliwe zweryfikowanie bloku Ethereum poprzez: (i) pobranie bloku lub nawet tylko niewielkiej części próbkowania dostępności danych z bloku; (ii) weryfikację małego dowodu poprawności bloku. To będzie operacja o bardzo niskim zużyciu zasobów, możliwa do wykonania na kliencie mobilnym, w portfelu przeglądarkowym, a nawet na innym łańcuchu (bez części dostępności danych).

Aby to osiągnąć, potrzebujemy SNARK lub STARK zarówno dla (i) warstwy konsensusu (czyli proof-of-stake), jak i (ii) warstwy wykonania (czyli EVM). Pierwsze z nich to wyzwanie samo w sobie i powinno być rozwiązywane wraz z dalszymi ulepszeniami warstwy konsensusu (np. dla single-slot finality). Drugie wymaga dowodu wykonania EVM.

Co to jest i jak działa?

Formalnie w specyfikacji Ethereum EVM jest zdefiniowane jako funkcja transformacji stanu: masz stan początkowy S, blok B, obliczasz stan końcowy S' = STF(S, B). Jeśli użytkownik korzysta z lekkiego klienta, nie posiada w całości S i S', a nawet E; zamiast tego ma korzeń stanu początkowego R, korzeń stanu końcowego R' i hash bloku H.

• Dane publiczne: korzeń stanu początkowego R, korzeń stanu końcowego R', hash bloku H
• Dane prywatne: ciało bloku B, obiekty w stanie odwiedzane przez blok Q, te same obiekty po wykonaniu Q', dowody stanu (np. gałęzie Merkle) P
• Twierdzenie 1: P jest ważnym dowodem, ż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 w Q, (ii) blok jest ważny, (iii) wynik to Q'
• Twierdzenie 3: Jeśli ponownie obliczysz nowy korzeń stanu z Q' i P, otrzymasz R'

Jeśli to istnieje, można mieć lekki klient w pełni weryfikujący wykonanie EVM Ethereum. To już bardzo obniża wymagania zasobowe klienta. Aby uzyskać naprawdę w pełni weryfikującego klienta Ethereum, trzeba zrobić to samo dla konsensusu.

Dowody poprawności wykonania EVM już istnieją i są szeroko stosowane na L2. Jednak aby były wykonalne na L1, potrzeba jeszcze dużo pracy.

Powiązania z istniejącymi badaniami?

• EFPSE ZK-EVM (wycofane, bo są lepsze opcje)
• Zeth, który kompiluje EVM do RISC-0 ZK-VM
• Projekt formalnej weryfikacji ZK-EVM

Co jeszcze można zrobić?

Obecnie dowody poprawności systemów księgowych mają dwa główne braki: bezpieczeństwo i czas weryfikacji.

Bezpieczny dowód poprawności musi gwarantować, że SNARK rzeczywiście weryfikuje obliczenia EVM i nie ma luk. Dwie główne techniki zwiększania bezpieczeństwa to multi-verifier i formalna weryfikacja. Multi-verifier oznacza wiele niezależnie napisanych implementacji dowodu poprawności, jak wiele klientów; jeśli blok zostanie udowodniony przez wystarczająco duży podzbiór tych implementacji, klient akceptuje blok. Formalna weryfikacja polega na użyciu narzędzi zwykle stosowanych do dowodzenia twierdzeń matematycznych, jak Lean4, by udowodnić, że dowód poprawności akceptuje tylko poprawne wykonanie specyfikacji EVM (np. EVM K semantics lub pythonowa specyfikacja EELS).

Wystarczająco szybki czas weryfikacji oznacza, że każdy blok Ethereum można zweryfikować w mniej niż 4 sekundy. Dziś jesteśmy daleko od tego celu, choć bliżej niż dwa lata temu. Aby to osiągnąć, musimy poczynić postępy w trzech kierunkach:

• Równoległość — obecnie najszybszy walidator EVM może udowodnić blok Ethereum średnio w 15 sekund. Osiąga to przez równoległość na setkach GPU, a następnie agregację wyników. Teoretycznie wiemy, jak zbudować walidator EVM, który udowodni obliczenia w czasie O(log(N)): jeden GPU wykonuje każdy krok, potem tworzy się „drzewo agregujące”:

Wdrożenie tego jest wyzwaniem. Nawet w najgorszym przypadku, gdy jedna bardzo duża transakcja zajmuje cały blok, podział obliczeń nie może być po prostu po transakcjach, ale musi być po opcode (EVM lub RISC-V). Kluczowym wyzwaniem jest zapewnienie spójności „pamięci” maszyny wirtualnej między różnymi częściami dowodu. Jeśli uda się wdrożyć takie dowody rekurencyjne, wiemy, że przynajmniej problem opóźnienia walidatora jest rozwiązany, nawet bez innych ulepszeń.

• Optymalizacja systemu dowodzenia — nowe systemy dowodzenia, jak Orion, Binius, GRK i inne, prawdopodobnie znów znacznie skrócą czas weryfikacji obliczeń ogólnego przeznaczenia.
• Zmiany kosztów gas w EVM — wiele rzeczy w EVM można zoptymalizować pod kątem dowodzenia, zwłaszcza w najgorszym przypadku. Jeśli atakujący może zbudować blok blokujący dowodzącego na 10 minut, to samo udowodnienie zwykłego bloku w 4 sekundy nie wystarczy. Potrzebne zmiany w EVM można podzielić na:
• Zmiany kosztów gas — jeśli operacja długo się dowodzi, nawet jeśli jest szybka obliczeniowo, powinna mieć wysoki koszt gas. EIP-7667 to propozycja rozwiązania najpoważniejszych problemów w tej dziedzinie: znacznie zwiększa koszt gas (tradycyjnych) funkcji haszujących, bo ich opcode i prekompilacje są stosunkowo tanie. By zrekompensować te podwyżki, można obniżyć koszt gas dla opcode EVM o niskim koszcie dowodu, zachowując średnią przepustowość.
• Zmiana struktur danych — poza zamianą drzewa stanu na bardziej przyjazne dla STARK, trzeba też zmienić listę transakcji, drzewo pokwitowań i inne kosztowne struktury. Propozycja Etana Kisslinga przenosząca transakcje i pokwitowania do SSZ to krok w tym kierunku.

Poza tym dwa narzędzia wspomniane w poprzedniej sekcji (wielowymiarowy gas i opóźniony korzeń stanu) też mogą tu pomóc. Jednak w przeciwieństwie do bezstanowej weryfikacji, tu oznacza to, że mamy już wystarczającą technologię do obecnych potrzeb, a nawet z tymi technikami pełna weryfikacja ZK-EVM wymaga więcej pracy — po prostu mniej pracy niż bez nich.

Nie wspomniano wyżej o sprzęcie dla dowodzących: użycie GPU, FPGA i ASIC do szybszego generowania dowodów. Fabric Cryptography, Cysic i Accseal to trzy firmy robiące postępy w tej dziedzinie. To bardzo cenne dla L2, ale raczej nie będzie decydujące dla L1, bo istnieje silne dążenie, by L1 pozostał wysoce zdecentralizowany, co oznacza, że generowanie dowodów musi być w zasięgu zwykłych użytkowników Ethereum, a nie zależeć od sprzętu jednej firmy. L2 mogą dokonywać bardziej agresywnych kompromisów.

W tych dziedzinach jest jeszcze wiele do zrobienia:

• Równoległość dowodzenia wymaga, by różne części systemu dowodzenia mogły „dzielić pamięć” (np. tablice look-up). Znamy techniki, ale trzeba je wdrożyć.
• Potrzebujemy więcej analiz, by znaleźć idealny zestaw zmian kosztów gas, minimalizujący czas weryfikacji w najgorszym przypadku.
• Potrzebujemy więcej pracy nad systemami dowodzenia

Możliwe kompromisy:

• Bezpieczeństwo vs. czas walidatora: wybór bardziej agresywnych funkcji haszujących, bardziej złożonych systemów dowodzenia lub bardziej agresywnych założeń bezpieczeństwa czy innych rozwiązań może skrócić czas walidatora.
• Decentralizacja vs. czas walidatora: społeczność musi uzgodnić „specyfikację” sprzętu dla walidatorów. Czy dopuszczamy, by walidatorami były duże podmioty? Czy chcemy, by high-endowy laptop konsumencki mógł zweryfikować blok Ethereum w 4 sekundy? A może coś pośredniego?
• Stopień łamania kompatybilności wstecznej: inne braki można zrekompensować bardziej agresywnymi zmianami kosztów gas, ale to może nieproporcjonalnie zwiększyć koszty niektórych aplikacji, zmuszając deweloperów do przepisywania i ponownego wdrażania kodu, by zachować opłacalność. Te narzędzia mają też własną złożoność i wady.

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

Kluczowe technologie potrzebne do dowodu poprawności EVM na L1 są w dużej mierze wspólne z dwoma innymi obszarami:

• Dowody poprawności na L2 (czyli „ZK rollup”)
• Bezstanowa metoda „STARK binary hash proof”

Po pomyślnym wdrożeniu dowodu poprawności na L1 możliwe będzie ostatecznie łatwe pojedyncze stakingowanie: nawet najsłabsze komputery (w tym telefony czy smartwatche) będą mogły stakować. To dodatkowo zwiększa wartość rozwiązywania innych ograniczeń pojedynczego stakingu (jak minimalny próg 32ETH).

Ponadto dowód poprawności EVM na L1 może znacznie zwiększyć limit gas na L1.

Dowód poprawności konsensusu

Jaki problem chcemy rozwiązać?

Jeśli chcemy w pełni zweryfikować blok Ethereum za pomocą SNARK, wykonanie EVM to nie jedyna część, którą musimy udowodnić. Musimy też udowodnić konsensus, czyli część systemu obsługującą depozyty, wypłaty, podpisy, aktualizacje sald walidatorów i inne elementy proof-of-stake Ethereum.

Konsensus jest znacznie prostszy niż EVM, ale wyzwaniem jest to, że nie mamy L2 EVM rollup, więc i tak większość pracy trzeba wykonać. Każda implementacja dowodu konsensusu Ethereum musi więc być „od zera”, choć sam system dowodzenia można współdzielić.

Co to jest i jak działa?

Beacon chain jest zdefiniowany jako funkcja transformacji stanu, podobnie jak EVM. Funkcja transformacji stanu składa się głównie z trzech części:

• ECADD (do weryfikacji podpisów BLS)
• Pairing (do weryfikacji podpisów BLS)
• SHA256 hash (do odczytu i aktualizacji stanu)

W każdym bloku musimy udowodnić 1-16 ECADD BLS12-381 dla każdego walidatora (może więcej, bo podpisy mogą być w kilku zestawach). Można to zredukować przez techniki precomputacji podzbiorów, więc można przyjąć, że na walidatora przypada jeden ECADD BLS12-381. Obecnie na slot jest 30000 podpisów walidatorów. W przyszłości, po wdrożeniu single-slot finality, liczba ta może się zmienić: jeśli pójdziemy „na siłę”, liczba walidatorów na slot może wzrosnąć do 1 miliona. Z kolei jeśli wdrożymy Orbit SSF, liczba walidatorów pozostanie na poziomie 32768 lub nawet spadnie do 8192.

Jak działa agregacja BLS: weryfikacja podpisu zbiorczego wymaga tylko jednego ECADD na uczestnika, a nie ECMUL. Ale 30000 ECADD to wciąż dużo do udowodnienia.

Jeśli chodzi o pairing, obecnie na slot jest maksymalnie 128 dowodów, więc trzeba zweryfikować 128 pairingów. Dzięki ElP-7549 i dalszym zmianom można to zredukować do 16 na slot. Pairingi są nieliczne, ale bardzo kosztowne: każdy pairing trwa (lub wymaga dowodu) tysiące razy dłużej niż ECADD.

Głównym wyzwaniem w dowodzeniu operacji BLS12-381 jest brak wygodnej krzywej o rzędzie równym rozmiarowi pola BLS12-381, co zwiększa narzut dla każdego systemu dowodzenia. Z drugiej strony proponowane dla Ethereum drzewa Verkle są zbudowane na krzywej Bandersnatch, co sprawia, że BLS12-381 jest natywną krzywą w systemie SNARK do dowodzenia gałęzi Verkle. Prosta implementacja może udowodnić 100 dodawań G1 na sekundę; by uzyskać wystarczającą szybkość dowodu, niemal na pewno potrzebne są sprytne techniki jak GKR.

Dla SHA256 najgorszy przypadek to blok zmiany epoki, gdy cały skrócony balans walidatorów i wiele sald jest aktualizowanych. Skrócony balans walidatora to tylko jeden bajt, więc 1MB danych jest ponownie haszowane. To 32768 wywołań SHA256. Jeśli tysiąc walidatorów przekroczy próg, trzeba zaktualizować rekordy walidatorów, co oznacza tysiąc gałęzi Merkle, czyli może 10 tysięcy haszy. Mechanizm tasowania wymaga 90 bitów na walidatora (czyli 11MB danych), ale można to policzyć w dowolnym momencie epoki. W single-slot finality liczby te mogą się zmieniać. Tasowanie może być zbędne, choć Orbit może częściowo je przywrócić.

Kolejnym wyzwaniem jest konieczność ponownego pobrania całego stanu walidatorów, w tym kluczy publicznych, by zweryfikować blok. Dla 1 miliona walidatorów samo pobranie kluczy publicznych to 48 milionów bajtów plus gałęzie Merkle. To wymaga milionów haszy na epokę. Jeśli musimy udowodnić poprawność PoS, realnym podejściem jest pewna forma inkrementalnych obliczeń weryfikowalnych: przechowywanie w systemie dowodzenia osobnej struktury danych zoptymalizowanej pod szybkie wyszukiwanie i dowodzenie aktualizacji tej struktury.

Podsumowując, wyzwań jest wiele. By najefektywniej im sprostać, prawdopodobnie potrzebna będzie głęboka przebudowa beacon chain, co może nastąpić równolegle z przejściem na single-slot finality. Taka przebudowa może obejmować:

• Zmiana funkcji haszującej: obecnie używamy „pełnej” SHA256, więc przez padding każde wywołanie to dwa wywołania funkcji kompresji. Przejście na SHA256 compression daje co najmniej 2x zysk. Przejście na Poseidon może dać 100x zysk, całkowicie rozwiązując problem haszowania (przynajmniej dla haszy): przy 1,7 miliona haszy na sekundę (54MB), nawet milion rekordów walidatorów można „przeczytać” do dowodu w kilka sekund.
• Jeśli Orbit, to bezpośrednie przechowywanie przetasowanych rekordów walidatorów: jeśli wybieramy określoną liczbę walidatorów (np. 8192 lub 32768) jako komitet na slot, umieszczamy ich rekordy obok siebie w stanie, co pozwala szybko wczytać wszystkie klucze publiczne do dowodu. To także pozwala na efektywne aktualizacje sald.
• Agregacja podpisów: każda wydajna agregacja podpisów będzie wymagać dowodów rekurencyjnych, gdzie różne węzły sieci dowodzą podzbiorów podpisów. To naturalnie rozkłada pracę dowodzenia na wiele węzłów, znacznie zmniejszając obciążenie „ostatecznego dowodzącego”.
• Inne schematy podpisów: dla podpisów Lamport+Merkle potrzeba 256+32 haszy na podpis; razy 32768 podpisujących daje 9437184 haszy. Po optymalizacji schematu można to jeszcze poprawić przez mały stały czynnik. Używając Poseidon, można to udowodnić w jednym slocie. W praktyce rekurencyjna agregacja będzie szybsza.

Powiązania z istniejącymi badaniami?

• Succinct Ethereum consensus proofs (tylko dla sync committee)
• Succinct Helios in SP1
• Succinct BLS12-381 precompile
• Weryfikacja podpisów zbiorczych BLS na Halo2

Co jeszcze trzeba zrobić, jakie kompromisy?

W rzeczywistości potrzebujemy kilku lat, aby uzyskać dowód poprawności konsensusu Ethereum. To mniej więcej tyle samo, ile potrzeba na wdrożenie single-slot finality, Orbit, zmianę algorytmu podpisu i analizę bezpieczeństwa, która da wystarczającą pewność, by użyć „agresywnych” funkcji haszujących jak Poseidon. Najrozsądniej jest więc rozwiązać te inne problemy, mając na uwadze przyjazność dla STARK.

Główne kompromisy będą prawdopodobnie dotyczyć kolejności działań, między bardziej stopniowym podejściem do reformy warstwy konsensusu Ethereum a bardziej radykalnym „zmień wiele naraz”. Dla EVM podejście stopniowe jest rozsądne, bo minimalizuje zakłócenia kompatybilności wstecznej. Dla warstwy konsensusu wpływ na kompatybilność wsteczną jest mniejszy, a pełniejsze przemyślenie szczegółów konstrukcji beacon chain pod kątem optymalizacji pod SNARK może być korzystne.

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

Przy długoterminowej przebudowie PoS Ethereum przyjazność dla STARK musi być kluczowym czynnikiem, zwłaszcza dla single-slot finality, Orbit, zmian schematu podpisu i agregacji podpisów.