Pomiar wydajności SNARK: frontendy, backendy i przyszłość

SNARK (Succinct Non-interactive Arguments of Knowledge) to ważny prymityw kryptograficzny do znajdowania aplikacji do skalowalności łańcucha bloków (np. Rollupy L2) i prywatności. SNARKs pozwalają komuś udowodnić nieufnemu weryfikatorowi V (np. blockchain Ethereum), że znają pewne dane (np. partię ważnych transakcji). Naiwnym sposobem na udowodnienie tego byłoby wysłanie danych do: V, który może następnie bezpośrednio sprawdzić jego ważność. SNARK osiąga to samo, ale przy lepszych kosztach, aby V. W szczególności dowód SNARK powinien być krótszy niż dowód naiwny zawierający same dane. (Więcej szczegółów w szkicu mojego podręcznika, Dowody, argumenty i wiedza zerowa. Aby zapoznać się z wprowadzeniem do SNARKs, zobacz Sarah Meicklejohn presentation w krypto a16z Letnia seria badawcza.)

Koszty weryfikacji SNARK mogą się różnić, ale są dobrze rozumiane i często całkiem dobre. Na przykład, PlonK dowody kosztują około Gaz 290,000 do weryfikacji na Ethereum, podczas gdy dowody StarkWare kosztują około 5 milionów gazu. SNARKs mają potencjalnie zastosowanie w różnych ustawieniach, nawet poza łańcuchami bloków — na przykład umożliwiając korzystanie z szybkich, ale niezaufanych serwery i sprzęt komputerowy. 

Ale ponieważ weryfikacja SNARK jest zazwyczaj tania, głównymi wyznacznikami stosowalności są koszty dowodzenia SNARK P. W tym poście wyjaśniam, jak oszacować te koszty, aby określić, kiedy uzasadnione jest korzystanie z SNARK i jak SNARKs może się poprawić w przyszłości. Warto zauważyć, że jest to szybko zmieniająca się przestrzeń, a kilka projektów omówionych w tym poście aktywnie poprawia swoją wydajność.

Ale najpierw: jak wdrażane są SNARK

We wdrożeniu SNARK programista zazwyczaj pisze program komputerowy ψ który przyjmuje jako dane wejściowe w że dowódca twierdzi, że wie (w oznacza świadek) i sprawdza, czy w jest ważna. Na przykład w zestawieniach program sprawdzi, czy wszystkie transakcje w są podpisane cyfrowo, nie powodują spadku salda kont poniżej zera i tak dalej. Program ψ jest następnie podawany przez a Nakładka SNARK który kompiluje go do formatu, który jest bardziej podatny na zastosowanie technologii SNARK. Ten format przyjazny dla SNARK nazywa się an pośrednia reprezentacja (IŚĆ). 

Zazwyczaj IR jest pewnego rodzaju instancją spełnialności obwodu, która jest równoważna . Oznacza to, że obwód C przyjmuje jako dane wejściowe w, a także kilka dodatkowych danych wejściowych zwykle nazywanych „porada niedeterministyczna” i działa ψ on w. Wprowadzone porady służą do pomocy C biegać ψ, zachowując C mały. Na przykład za każdym razem ψ dzieli dwie liczby x i y, iloraz q i reszta r może być udzielana jako porada dla C, C mogę to po prostu sprawdzić x = qy + r. Ten czek jest tańszy niż robienie C uruchom algorytm dzielenia, aby obliczyć q i r od zera.

Wreszcie, SNARK dla spełnialności obwodu jest stosowany do C. To się nazywa Zaplecze SNARK. W przypadku kilku wysoce ustrukturyzowanych problemów, takich jak: mnożenie macierzy, zwoje, kilka problemów z wykresami, istnieją znane SNARK, które unikają tego paradygmatu frontend/backend, a tym samym osiągają znacznie szybsze sprawdzanie. Ale ten post koncentruje się na SNARKach ogólnego przeznaczenia.

Jak zobaczymy, koszty testera backendu SNARK rosną wraz z C„s rozmiar. Konserwacja C małe może być wyzwaniem, ponieważ obwody są niezwykle ograniczonym formatem, w którym można wyrazić obliczenia. Składają się z bramy, połączony przez przewody. Każda brama g jest karmiony pewnymi wartościami i stosuje a początku. prosta funkcja do tych wartości. Wynik jest następnie podawany do bramek „dolnych” za pośrednictwem przewodów wychodzących z g.

Skalowalność SNARK: Ile czasu to naprawdę zajmuje?

Kluczowe pytanie brzmi: Ile więcej czasu zajmuje tester SNARK w stosunku do zwykłego ponownego wykonania? ψ na dane? Odpowiedź brzmi: udowodnione koszty ogólne SNARKA, w stosunku do bezpośrednia kontrola świadka. To ostatnie wyrażenie odnosi się do faktu, że w naiwnym dowodzie, w którym: P wysyła w do V, V Kontrole wważność przez wykonanie ψ na nim. 

Przydatne jest rozbicie narzutu na narzędzie do sprawdzania na „narzuty frontendowe” i „narzuty operacyjne backendowe”. Jeśli oceniasz obwód C brama po bramie to F razy droższe niż bieganie ψ, wtedy mówimy, że obciążenie frontendu to F. Jeśli zastosujesz backendową wersję próbną do C is B razy droższe niż ocena C brama po bramie, wtedy mówimy, że obciążenie zaplecza jest B. Całkowity koszt udowodnienia to produkt, F·B. Ten multiplikatywny narzut może być znaczny, nawet jeśli: F i B są indywidualnie skromne. 

W praktyce, F i B oba mogą być z grubsza 1000 lub większe. Oznacza to, że całkowity koszt dowodu w stosunku do bezpośredniego sprawdzania świadków może wynosić od 1 do 10 milionów lub więcej. Program, który działa na laptopie tylko przez jedną sekundę, może łatwo doprowadzić do narzędzia SNARK wymagającego dziesiątek lub setek dni obliczeniowych (jednowątkowych). Na szczęście ta praca jest zazwyczaj możliwa do zrównoleglenia w różnym stopniu (w zależności od SNARK). 

Podsumowując, jeśli chcesz dziś używać SNARKA w aplikacji, to jedna z trzech rzeczy musi być prawdziwa:

1. Bezpośrednie sprawdzanie świadka trwa znacznie mniej niż jedną sekundę na laptopie.
2. Bezpośrednie sprawdzanie świadków jest szczególnie podatne na reprezentację w obwodzie, więc narzuty na frontend są niewielkie.
3. Chcesz poczekać kilka dni na zakończenie działania programu SNARK i/lub zapłacić za ogromne zasoby obliczeń równoległych.

TPozostała część tego postu wyjaśnia, skąd biorą się narzuty frontendowe i backendowe oraz jak oceniam je dla różnych SNARK-ów. Następnie zajmiemy się perspektywami poprawy. 

Oddzielenie frontendów i backendów

Całkowite oddzielenie frontendów od backendów może być trudne, ponieważ różne backendy obsługują różne rodzaje obwodów. W związku z tym nakładki mogą się różnić w zależności od zaplecza, z którym mają się komunikować.

Backendy SNARK generalnie obsługują tak zwane obwody arytmetyczne, co oznacza, że ​​wejścia do obwodów są elementami pewnego skończonego pola, a bramki obwodu wykonują dodawanie i mnożenie dwóch elementów pola. Obwody te z grubsza odpowiadają prostym programom komputerowym (bez rozgałęzień, instrukcji warunkowych itd.), które mają charakter algebraiczny — to znaczy, że ich pierwotnym typem danych są elementy pola. 

Większość backendów faktycznie obsługuje uogólnienie obwodów arytmetycznych, często nazywanych instancjami Rank-1 Constraint Satisfaction (R1CS). Z godnym uwagi wyjątkiem Groth16 i jego poprzednicy, te SNARK mogą być również wykonane do obsługi innych IR. Na przykład StarkWare używa czegoś, co nazywa się Algebraic Intermediate Representation (AIR), co jest również podobne do pojęcia o nazwie Arytmetyzacja PlonKish które mogą być obsługiwane przez PlonK i inne backendy. Zdolność niektórych backendów do obsługi bardziej ogólnych IR może zmniejszyć obciążenie frontendów, które generują te IR. 

Backendy różnią się również pod względem skończonych pól, które natywnie obsługują. Omówię to dalej w następnej sekcji.

Różne podejścia do frontendów

Niektóre (bardzo specjalne) programy komputerowe naturalnie odpowiadają obwodom arytmetycznym. Jednym z przykładów jest program komputerowy, który wykonuje naiwne mnożenie macierzy na jakimś polu. Ale większość programów komputerowych nie jest ani liniowa, ani algebraiczna. Często zawierają instrukcje warunkowe, operacje, takie jak dzielenie liczb całkowitych lub arytmetyka zmiennoprzecinkowa, które w naturalny sposób nie odpowiadają arytmetyce pól skończonych i nie tylko. W takich przypadkach obciążenie frontendu będzie znaczne. 

Jednym z popularnych podejść frontendowych jest tworzenie obwodów, które zasadniczo wykonują krok po kroku prosty procesor, zwany także maszyną wirtualną (VM). Projektanci frontend określają zestaw „prymitywnych operacji” analogicznych do instrukcji montażu dla rzeczywistych procesorów komputerowych. Deweloperzy, którzy chcą używać frontendu, będą albo pisać „programy sprawdzające świadków” bezpośrednio w języku asemblerowym, albo w jakimś języku wyższego poziomu, takim jak Solidity, i automatycznie skompilują swoje programy do kodu asemblerowego. 

Na przykład StarkWare Kair jest bardzo ograniczonym językiem asemblerowym, w którym instrukcje asemblerowe z grubsza pozwalają na dodawanie i mnożenie przez skończone pole, wywoływanie funkcji oraz odczyt i zapis do niezmiennej (tj. jednokrotnego zapisu) pamięci. Cairo VM jest architekturą von Neumanna, co oznacza, że ​​obwody produkowane przez nakładkę zasadniczo przyjmują program Cairo jako publiczne wejście i „uruchamiają” program na świadku. Językiem Cairo jest Turing Complete — pomimo ograniczonego zestawu instrukcji może symulować bardziej standardowe architektury, chociaż może to być kosztowne. Nakładka Cairo zmienia uruchamianie programów w Kairze T prymitywne instrukcje dotyczące tego, co nazywa się „stopień-2 POWIETRZE z T wiersze i około 50 kolumny”. Co dokładnie to oznacza nie jest ważne dla tego stanowiska, ale w przypadku testerów SNARK odpowiada to obwodom z od 50 do 100 bramek dla każdego z T kroki procesora w Kairze. 

RYZYKO Zero ma podobne podejście do Kairu, ale z maszyną wirtualną jest tzw Architektura RISC-V, architektura typu open source z bogatym ekosystemem oprogramowania, która zyskuje na popularności. Jako bardzo prosty zestaw instrukcji, zaprojektowanie wydajnego frontendu SNARK, który go obsługuje, może być stosunkowo wykonalne (przynajmniej w odniesieniu do skomplikowanych architektur, takich jak x86 lub ARM). Od maja RISC Zero obraca programy wykonywania T prymitywne instrukcje RISC-V do AIR stopnia-5 z 3T wiersze i 160 kolumny. Odpowiada to obwodom z co najmniej 500 bramek na krok procesora RISC-V. Dalsze ulepszenia są przewidywane w najbliższej przyszłości.

Różne projekty zkEVM (np. zkSync 2.0, Scroll, zkEVM firmy Polygon) przyjmują maszynę wirtualną jako (tak) maszynę wirtualną Ethereum. Proces przekształcania każdej instrukcji EVM w równoważny „gadżet” (tj. zoptymalizowany obwód implementujący instrukcję) jest znacznie bardziej skomplikowany niż w przypadku prostszych architektur Cairo i RISC-V. Z tego i innych powodów, niektóre projekty zkEVM nie implementują bezpośrednio zestawu instrukcji EVM, ale raczej kompilują wysokopoziomowe programy Solidity do innych języków asemblerowych przed zamianą ich w obwody. Wyniki wydajności z tych projektów są w toku.

Projekty „emulatorów procesora”, takie jak RISC-V i Cairo, tworzą pojedynczy obwód, który może obsługiwać wszystkie programy w skojarzonym języku asemblerowym. Alternatywne podejścia są „podobne do ASIC”, tworząc różne obwody dla różnych programów. To podejście podobne do ASIC może dawać mniejsze obwody dla niektórych programów, zwłaszcza gdy instrukcja asemblera, którą program wykonuje w każdym kroku czasowym, nie zależy od danych wejściowych programu. Na przykład, może potencjalnie całkowicie uniknąć narzutu na frontend dla programów prostych, takich jak naiwne mnożenie macierzy. Ale podejście ASIC wydaje się również bardzo ograniczone; o ile wiem, nie wiadomo, jak go używać do obsługi pętli bez z góry określonych granic iteracji. 

Ostatni składnik narzutu frontendu wynika z faktu, że wszystkie SNARK używają obwodów, które działają na polach skończonych. Procesor w twoim laptopie może pomnożyć lub dodać dwie liczby całkowite za pomocą pojedynczej instrukcji maszynowej. Jeśli frontend wyprowadza obwód w polu o wystarczająco dużej charakterystyce, może zasadniczo symulować to mnożenie lub dodawanie poprzez odpowiednią operację pola. Jednak implementacja operacji na polu na rzeczywistym procesorze wymaga zwykle wielu instrukcji maszynowych (chociaż niektóre nowoczesne procesory mają natywną obsługę niektórych pól). 

Niektóre backendy SNARK umożliwiają bardziej elastyczne wybory pól niż inne. Na przykład, jeśli backend korzysta z grupy kryptograficznej G, pole obwodu musi odpowiadać liczbie elementów w G, co może być ograniczeniem. Ponadto nie wszystkie pola obsługują praktyczne algorytmy FFT. 

Jest tylko jeden zaimplementowany SNARK, Awaria, który natywnie obsługuje obliczenia na dowolnych (wystarczająco dużych) polach. Wraz z jego potomkowie, ma najszybszą znaną wydajność konkretnych testerów, nawet w dziedzinach obsługiwanych przez inne SNARK, ale jego dowody są obecnie zbyt duże dla wielu aplikacji blockchain. Ostatnia praca stara się poprawić rozmiar dowodu, ale dowodzący jest asymptotycznie wolniejszy i tam wydaje się być bariery do praktyczności.

Niektóre projekty wybrały pracę nad polami ze szczególnie szybką arytmetyką. Na przykład, Plonky2 a inne stosują pole charakterystyki 2⁶⁴ - 2³² + 1, ponieważ arytmetykę w tej dziedzinie można zaimplementować kilka razy szybciej niż w polach o mniejszej strukturze. Jednak użycie tak małej charakterystyki może prowadzić do problemów z wydajnym przedstawianiem arytmetyki liczb całkowitych za pomocą operacji na polach (np. mnożenie dwóch 32-bitowych liczb całkowitych bez znaku może dać wynik większy niż charakterystyka pola). 

 Ale bez względu na wszystko, aby wszystkie popularne dziś SNARKI osiągnęły 128 bitów bezpieczeństwa (bez znaczącego wzrostu kosztów weryfikacji), muszą pracować na polu o rozmiarze większym niż 2¹²⁸. O ile wiem, oznacza to, że każda operacja na polu będzie wymagała co najmniej około dziesięciu 64-bitowych mnożeń maszynowych i znacznie więcej operacji dodawania i operacji bitowych. Dlatego należy wziąć pod uwagę co najmniej rząd wielkości narzutu ze względu na potrzebę obwodów, które działają na polach skończonych. 

Podsumowując, istniejące frontendy, które wykorzystują abstrakcję maszyny wirtualnej, tworzą obwody z bramkami 100x do 1000x na krok maszyny wirtualnej i prawdopodobnie więcej dla bardziej skomplikowanych maszyn wirtualnych. Co więcej, arytmetyka pól skończonych jest co najmniej 10 razy wolniejsza niż analogiczne instrukcje na nowoczesnych procesorach (z możliwymi wyjątkami, jeśli procesor ma wbudowaną obsługę niektórych pól). „Podejście frontendowe ASIC” może zmniejszyć niektóre z tych kosztów ogólnych, ale obecnie jest ograniczone pod względem rodzajów programów, które może obsługiwać.

Jakie są wąskie gardła zaplecza?

SNARK dla spełnialności obwodu są zazwyczaj projektowane przez połączenie teoretycznie bezpiecznego protokołu informacji o nazwie „wielomian IOP” z protokołem kryptograficznym zwanym „wielomianowy schemat zobowiązań”. W większości przypadków konkretnym wąskim gardłem dla dowodzącego jest wielomianowy schemat zobowiązań. W szczególności, te SNARKs mają kryptograficznie przypisanie dowodzącego do jednego lub więcej wielomianów, których stopień jest (co najmniej) |C|, liczba bramek w obwodzie C. 

Z kolei konkretne wąskie gardło w wielomianowym schemacie zaangażowania będzie zależeć od zastosowanego schematu i wielkości obwodu. Ale zawsze będzie to jedna z trzech następujących operacji: obliczanie FFT, potęgowanie w grupie kryptograficznej lub merkle-hashing. Hashowanie Merkle jest zwykle wąskim gardłem tylko wtedy, gdy obwód jest mały, więc nie będziemy o tym dalej dyskutować. 

Zobowiązania wielomianowe oparte na logarytmie dyskretnym

W zobowiązaniach wielomianowych opartych na twardości problemu dyskretnego logarytmu w grupie kryptograficznej G (KZG, Kuloodporne, Dory, Góralek-zobowiązanie), dowód musi obliczyć a Zaangażowanie wektorów Pedersena do współczynników wielomianu. Wiąże się to z wielokrotną potęgą o wielkości równej stopniowi wielomianu. W SNARKach ten stopień jest zwykle wielkością |C| obwodu C.

Zrobione naiwnie, wielokrotne potęgowanie rozmiaru |C| wymaga około 1.5·|C|·log |G| ≈ 400·|C| operacje grupowe, gdzie |G| oznacza liczbę elementów w grupie G. Istnieje jednak podejście, zwane algorytmem Pippengera, które może zmniejszyć to o współczynnik mniej więcej log |C|. Do dużych obwodów (powiedzmy |C| ≥ 225), ten dziennik |C| współczynnik może konkretnie wynosić 25 lub więcej, co oznacza, że ​​w przypadku dużych obwodów oczekujemy, że zaangażowanie wektora Pedersena może być obliczalne przy nieco ponad 10·|C| operacje grupowe. Każda operacja grupowa jest z kolei (jako bardzo trudne zadanie) około 10 razy wolniejsza niż operacja skończonego pola. SNARKi korzystające z tych zobowiązań wielomianowych są tak samo drogie dla P jak około 100·|C| operacje polowe. 

Niestety, istniejące SNARK mają dodatkowe koszty ogólne oprócz powyższego współczynnika 100x. Na przykład:

• Spartaninudowadniający, który korzysta z wielomianu wielomianowego góralka, musi zrobić |C|^½ wiele wielokrotnych potęg, każdy o wielkości |C|^½, osłabiając przyspieszenie algorytmu Pippengera mniej więcej dwa razy. 
• In Groth16, P musi pracować nad grupą przyjazną do łączenia w pary, której działania są zazwyczaj co najmniej 2 razy wolniejsze niż w przypadku grup, które nie są przyjazne dla par. P musi również wykonać 3 wielokrotne potęgowanie zamiast 1. Łącznie, powoduje to przynajmniej dodatkowe spowolnienie o współczynnik 6 w stosunku do 100·|C| oszacowanie powyżej. 
• Marlin i PlonK wymagają również parowania, a ich dowodnicy zobowiązują się do znacznie więcej niż 3 wielomianów. 
• Dla każdego SNARKA, który używa Kuloodporne (na przykład, Halo2, który jest z grubsza PlonK, ale z zobowiązaniami Bulletproofs, a nie wielomianowymi KZG), tester musi obliczyć logarytmicznie wiele wielowykładnic podczas fazy „otwierania” schematu zobowiązań, a to w dużej mierze wymazuje wszelkie przyspieszenie Pippengera. 

Podsumowując, znane SNARK używające zobowiązań wektorowych Pedersena wydają się mieć obciążenie zaplecza wynoszące co najmniej 200x i do 1000x lub więcej. 

Inne zobowiązania wielomianowe

Dla SNARK używających innych zobowiązań wielomianowych (takich jak Piątek i Ligero-zobowiązanie), wąskim gardłem jest to, że tester musi wykonać duże FFT. Na przykład w 2 stopniach AIR produkowanych przez Cairo (z 51 kolumnami i T wierszy, jeden na krok procesora Cairo), wdrożony program do sprawdzania StarkWare wykonuje co najmniej 2 FFT na kolumnę o długości między 16 ·T i 32 ·T. Stałe 16 i 32 zależą od wewnętrznych parametrów FRI określonych przez StarkWare i można je zmniejszyć — ale kosztem zwiększonych kosztów weryfikacji. 

Optymistycznie FFT o długości 32·T trwa około 64·T·dziennik (32T) mnożenia pól. Oznacza to, że nawet dla stosunkowo małych wartości T (na przykład, T ≥ 2²⁰), liczba operacji polowych na kolumnę wynosi co najmniej 64·25·T= 1600·T. Wydaje się więc, że obciążenie zaplecza wynosi co najmniej tysiące. Co więcej, możliwe jest, że duże FFT są jeszcze bardziej ograniczane przez przepustowość pamięci niż przez operacje w terenie. 

W niektórych kontekstach obciążenie zaplecza SNARK, które wykonują duże FFT, można złagodzić za pomocą techniki zwanej agregacją dowodów. W przypadku podsumowań oznaczałoby to, że P (usługa rollup) dzieli dużą partię transakcji na, powiedzmy, 10 mniejszych partii. Dla każdej małej partii i, P produkuje dowód SNARK πi ważności partii. Ale P nie wysyła tych dowodów do Ethereum, ponieważ doprowadziłoby to do prawie 10-krotnego wzrostu kosztów gazu. Zamiast tego SNARK jest ponownie stosowany, tym razem w celu uzyskania dowodu π ustalanie tego P wie π₁ ...,π₁₀. To znaczy świadek, który… P twierdzi, że zna dziesięć dowodów π₁,…,π₁₀, a bezpośrednia kontrola świadka stosuje procedurę weryfikacji SNARK do każdego z dowodów. Ten pojedynczy dowód π jest wysłana do Ethereum. 

W zobowiązaniach wielomianowych, takich jak FRI i Ligero-commit, istnieje silne napięcie między: P czas i V koszty, z wewnętrznymi parametrami działającymi jak pokrętło, które może wymieniać jeden na drugi. Odkąd π₁ ,…,π₁₀ nie są wysyłane do Ethereum, pokrętło można dostroić więc te dowody są duże, a ich produkcja jest szybsza. Tylko w końcowym zastosowaniu SNARK, do agregacji π₁ ,…,π₁₀ w jeden dowód π, czy schemat zobowiązań musi być skonfigurowany, aby zapewnić mały dowód. 

StarkWare planuje wdrożyć agregację dowodów niebawem. Na tym skupiają się również projekty takie jak: Plonky2.

Jakie są inne wąskie gardła skalowalności SNARK?

Ten post skupił się na dowodzie czas, ale inne koszty sprawdzania mogą być również wąskimi gardłami skalowalności. Na przykład, dla wielu backendów SNARK, weryfikator musi przechowywać kilka elementów pola dla każdej bramki w C, a ten koszt miejsca może być ogromny. Na przykład program ψ uruchomienie w ciągu jednej sekundy na laptopie może wykonać około miliarda prymitywnych operacji na nowoczesnym procesorze. Jak widzieliśmy, generalnie należy się spodziewać C wymagać znacznie ponad 100 bramek na taką operację. Oznacza to 100 miliardów bramek, co w zależności od SNARKA może oznaczać dziesiątki lub setki terabajtów przestrzeni dla P. 

Inny przykład: wiele popularnych SNARK (np. PlonK, Marlin, Groth16) wymagają skomplikowanej „ceremonii zaufanej konfiguracji” w celu wygenerowania ustrukturyzowanego „klucza udowadniającego”, które muszą być przechowywane przez dozorcę. O ile wiem, największa taka uroczystość wygenerował klucz udowadniający zdolny do obsługi obwodów z około 2²⁸≈250 milionów bram. Klucz udowadniający ma rozmiar kilkudziesięciu gigabajtów. 

W kontekstach, w których agregacja dowodów jest możliwa, te wąskie gardła można znacznie złagodzić. 

Patrząc w przyszłość: perspektywy na bardziej skalowalne SNARK

Koszty ogólne zarówno frontendu, jak i backendu mogą wynosić co najmniej trzy rzędy wielkości. Czy możemy oczekiwać, że w najbliższej przyszłości znacznie się zmniejszą? 

Myślę, że tak — do pewnego momentu. Po pierwsze, najszybsze obecnie backendy (np. Spartanin i Awariai inne SNARKI, które łączą protokół sprawdzania sumy z zobowiązaniami wielomianowymi) mają duże dowody — zwykle pierwiastek kwadratowy z rozmiaru obwodu — więc ludzie tak naprawdę ich nie używają. Spodziewam się, że w niedalekiej przyszłości rozmiar dowodu i czas weryfikatora zostaną znacząco zmniejszone dzięki kompozycji o głębokości pierwszej z małymi dowodami SNARK. Podobnie jak w przypadku agregacji dowodów, oznacza to, że dowodzący najpierw wygeneruje dowód SNARK π z „szybkim sprawdzaniem, dużym dowodem” SNARK, ale nie wysyłaj π do V. Raczej, P użyłby małego dowodu SNARK do wyprodukowania dowodu π" że to wie π, i wyślij π" do V. Mogłoby to zmniejszyć o rząd wielkości narzuty zaplecza popularnych obecnie SNARK-ów. 

Po drugie, może pomóc przyspieszenie sprzętowe. Bardzo ogólna zasada jest taka, że ​​procesory graficzne mogą kupić 10-krotne przyspieszenie w stosunku do procesorów, a ASIC 10-krotne przyspieszenie w stosunku do GPU. Mam jednak na tym froncie trzy obawy. Po pierwsze, duże FFT mogą być ograniczane przez przepustowość pamięci, a nie przez operacje w terenie, więc SNARK, który wykonuje takie FFT, może zauważyć ograniczone przyspieszenie ze specjalistycznego sprzętu. Po drugie, podczas gdy ten post koncentrował się na wąskim gardle zaangażowania wielomianowego, wiele SNARK wymaga od testera wykonania innych operacji, które są tylko nieznacznie tańsze. Tak więc przełamując wąskie gardło zaangażowania wielomianowego (np. przyspieszenie wielokrotnych potęg w SNARK opartych na dyskretnych logach) może pozostawić nową operację wąskiego gardła, która nie jest znacznie lepsza niż stara. (Na przykład SNARKs, w tym Groth16, Marlin i PlonK, mają również sprawdzone metody FFT, oprócz wielokrotnych wykładników.) Wreszcie, pola i krzywe eliptyczne, które prowadzą do najbardziej wydajnych SNARK-ów, mogą przez jakiś czas ewoluować, co może stwarzać wyzwania dla przyspieszenia opartego na ASIC.

Jeśli chodzi o frontend, możemy coraz częściej odkrywać, że podejście „emulatora procesora” w projektach takich jak Cairo, RISC Zero, zkEVM i inne w rzeczywistości skaluje się dość dobrze (pod względem wydajności) ze złożonością zestawów instrukcji procesora. Rzeczywiście, taka jest właśnie nadzieja różnych projektów zkEVM. Może to oznaczać, że podczas gdy obciążenie frontendu pozostaje trzy rzędy wielkości lub więcej, frontendy potrafią obsługiwać maszyny wirtualne, które w coraz większym stopniu pasują do rzeczywistych architektur procesorów. Równoważną obawą jest to, że frontendy mogą stać się skomplikowane i trudne do audytu, ponieważ mnożą się ręcznie kodowane gadżety wdrażające coraz bardziej skomplikowane instrukcje. Formalne metody weryfikacji prawdopodobnie odegrają ważną rolę w rozwiązaniu tego problemu. 

Wreszcie, przynajmniej w zastosowaniach blockchain, może się okazać, że większość inteligentnych kontraktów pojawiających się na wolności używa przede wszystkim prostych instrukcji przyjaznych SNARK. Może to w praktyce zapewnić niskie koszty frontendu, zachowując jednocześnie ogólność i lepsze wrażenia programisty, które zapewnia obsługa języków programowania wysokiego poziomu, takich jak Solidity i bogate zestawy instrukcji, w tym te z EVM. 

***

Justin Talar is profesor nadzwyczajny na Uniwersytecie Georgetown. Przed dołączeniem do Georgetown spędził dwa lata jako naukowiec w Yahoo Labs w Nowym Jorku, przed czym był pracownikiem naukowym w Instytut Simonsa Teorii Informatyki na Uniwersytecie Kalifornijskim w Berkeley. 

***

Podziękowania: Jestem wdzięczny Elena Burger za zaproponowanie tematu tego postu oraz za Arasu Arun, Józefa Bonneau, Sama Ragsdale'a za wnikliwe komentarze. Specjalne podziękowania również dla mojego redaktora, Tim Sullivan.

***

Wyrażone tutaj poglądy są poglądami poszczególnych cytowanych pracowników AH Capital Management, LLC („a16z”) i nie są poglądami a16z ani jej podmiotów stowarzyszonych. Niektóre informacje w nim zawarte zostały pozyskane ze źródeł zewnętrznych, w tym od spółek portfelowych funduszy zarządzanych przez a16z. Chociaż pochodzi ze źródeł uważanych za wiarygodne, a16z nie zweryfikowała niezależnie takich informacji i nie składa żadnych oświadczeń dotyczących trwałej dokładności informacji lub ich adekwatności w danej sytuacji. Ponadto treści te mogą zawierać reklamy osób trzecich; a16z nie przeglądał takich reklam i nie popiera żadnych zawartych w nich treści reklamowych.

Te treści są udostępniane wyłącznie w celach informacyjnych i nie należy ich traktować jako porady prawnej, biznesowej, inwestycyjnej lub podatkowej. Powinieneś skonsultować się w tych sprawach z własnymi doradcami. Odniesienia do jakichkolwiek papierów wartościowych lub aktywów cyfrowych służą wyłącznie celom ilustracyjnym i nie stanowią rekomendacji inwestycyjnej ani oferty świadczenia usług doradztwa inwestycyjnego. Ponadto treść ta nie jest skierowana ani przeznaczona do użytku przez jakichkolwiek inwestorów lub potencjalnych inwestorów iw żadnym wypadku nie można na nich polegać przy podejmowaniu decyzji o zainwestowaniu w jakikolwiek fundusz zarządzany przez a16z. (Oferta inwestycji w fundusz a16z zostanie złożona wyłącznie na podstawie memorandum dotyczącego oferty prywatnej, umowy subskrypcyjnej i innej odpowiedniej dokumentacji takiego funduszu i należy ją przeczytać w całości.) Wszelkie inwestycje lub spółki portfelowe wymienione, wymienione lub opisane nie są reprezentatywne dla wszystkich inwestycji w pojazdy zarządzane przez a16z i nie można zapewnić, że inwestycje będą opłacalne lub że inne inwestycje dokonane w przyszłości będą miały podobne cechy lub wyniki. Lista inwestycji dokonanych przez fundusze zarządzane przez Andreessena Horowitza (z wyłączeniem inwestycji, w przypadku których emitent nie wyraził zgody na publiczne ujawnienie przez a16z oraz niezapowiedzianych inwestycji w aktywa cyfrowe będące w obrocie publicznym) jest dostępna pod adresem https://a16z.com/investments /.

Wykresy i wykresy zamieszczone w niniejszym dokumencie służą wyłącznie celom informacyjnym i nie należy na nich polegać przy podejmowaniu jakichkolwiek decyzji inwestycyjnych. Wyniki osiągnięte w przeszłości nie wskazują na przyszłe wyniki. Treść mówi dopiero od wskazanej daty. Wszelkie prognozy, szacunki, prognozy, cele, perspektywy i/lub opinie wyrażone w tych materiałach mogą ulec zmianie bez powiadomienia i mogą się różnić lub być sprzeczne z opiniami wyrażanymi przez innych. Dodatkowe ważne informacje można znaleźć na stronie https://a16z.com/disclosures.