1. Wprowadzenie
ZK-SNARK to kryptograficzny system dowodowy, który pozwala podmiotowi udowodnić, że coś jest prawdą, bez ujawniania innych informacji.
ZK-SNARK są przydatne w wielu zastosowaniach i dziedzinach, takich jak blockchain i weryfikowalne obliczenia. W ZK-Rollups wykorzystywana jest jedna godna uwagi aplikacja typu blockchain.
ZK-Rollupy to łańcuchy bloków drugiej warstwy zbudowane na innych łańcuchach bloków (takich jak Ethereum), które wykorzystują ZK-SNARK (lub inne systemy dowodów kryptograficznych) w celu udowodnienia ważności przejść między stanami. Oznacza to, że za każdym razem, gdy wykonywana jest nowa aktualizacja sieci (dodawana jest nowa paczka transakcji), obliczany jest nowy stan sieci i generowany jest dowód ważności tego stanu. Rzecz w tym, że do wygenerowania tego dowodu potrzebny jest tylko jeden podmiot i każdy może wtedy zaufać jego wiarygodności.
Pożądane właściwości zapewniane przez ZK-Rollups to zazwyczaj (i) skalowalność i/lub (ii) ochrona prywatności. ZK-Rollupy są czasami nazywane rollupami efektywności, gdy wymagana jest jedynie skalowalność.
Aby obliczyć dowody w ZK-Rollupach zaprojektowanych w celu rozszerzenia EVM Ethereum, można zastosować ZK-EVM. Ściśle zdefiniowany, ZK-EVM to zbiór programów (obwodów) kryptograficznych odpowiedzialnych za generowanie dowodów o wiedzy zerowej (ZKP), chociaż czasami potocznie odnosi się także do całości uniwersalnych ZK-Rollupów obsługujących EVM.
2. Definicja ZK-SNARK
SNARK jest zwięzłym dowodem na to, że dane stwierdzenie jest prawdziwe. Formalnie demonstruje znajomość ścieżki wykonania algorytmu, która daje prawidłowe rozwiązanie określonego problemu. Raczej demonstruje wiedzę o niepublicznych i niestałych wartościach, które wykonują śledzenie. Wartości te jako całość często nazywane są świadkami. Elementy świadka, czyli części danych wejściowych algorytmu, stanowią niezależnych świadków, ponieważ istnieją przed wykonaniem algorytmu i nie są zdeterminowane przez inne elementy śladu wykonania. Publiczna, niestała wartość śladu wykonania, która określa wystąpienie problemu rozwiązywanego przez algorytm, nazywana jest instrukcją publiczną.
ZK-SNARK oznacza zwięzły, nieinteraktywny argument wiedzy o zerowej wiedzy.
S – Prostota
Prostota - dowód jest „krótki”, a czas weryfikacji „szybki”:
„Krótki” dowód oznacza, że wielkość dowodu jest subliniowa w stosunku do wielkości świadka.
„Szybki” czas weryfikacji oznacza, że czas działania weryfikatora powinien (i) być subliniowy w zależności od wielkości świadka oraz (ii) liniowy w przypadku twierdzenia publicznego.
Ale tak naprawdę chcemy, żeby był to nie tylko „zwięzły”, ale także „poziom wielomianu logarytmicznego”.
Oznacza to, że rozmiar dowodu i czas weryfikacji są prawie niezależne od wielkości świadka.
Udowodnić, że wielkość π nie powinna rosnąć szybciej niż pewna stała wielokrotność kwadratu logarytmu wielkości świadka w (dla dostatecznie dużego w):
Rozmiar dowodu zależy od konkretnego protokołu ZK-SNARK. W przypadku Plonky2 jest to O(log^2(|w|)), ale to „najgorszy” przypadek. Przykładowo dla klasycznego PLONKA i Groth16 wielkość dowodu wynosi O(1), co jest wartością stałą.
Czas weryfikacji t_v powinien być nie większy niż kilka stałych razy kwadrat logarytmu świadka w i liniowy w rozmiarze publicznej deklaracji x (x i w są wystarczająco duże, gdy tylko jedno z nich zmienia swój rozmiar).
N – Nieinteraktywny – Generowanie dowodu odbywa się bez otrzymania jakichkolwiek danych od weryfikatora.
ARK – Knowledge Proof – podobny do zwykłych dowodów, ale dźwięk sprawdza się tylko w przypadku dowodów ograniczonych wielomianowo, podczas gdy w dowodach dźwięk sprawdza się w przypadku dowodów nieograniczonych obliczeniowo. Pojęcie dźwięku omówimy w następnej sekcji.
ZK - Wiedza zerowa - Brak ujawnienia świadka.
3. Właściwości ZK-SNARK
ZK-SNARK mają trzy główne właściwości, jak opisano poniżej:
Kompletność: Jeśli osoba dowodząca zna prawidłową trajektorię wykonania algorytmu, weryfikator musi wierzyć, że osoba dowodząca posiada tę wiedzę.
Rzetelność wiedzy: Jeśli osoba dowodząca faktycznie nie zna prawidłowej trajektorii wykonania, nie może przekonać weryfikatora, że ją zna, ale istnieje bardzo małe prawdopodobieństwo.
Wiedza zerowa: weryfikator nie wie nic o trajektorii wykonania poza tym, że jest ona poprawna.
4.System dowódowy PLONKish ZK-SNARK
4.1 Wprowadzenie do PLONKish ZK-SNARK i ich funkcji
Aby zastosować się do określonego algorytmu, system dowodowy ZK-SNARK musi znać układ równań na ciele skończonym. Równania te opisują zależność pomiędzy wartościami w tabeli trajektorii wykonania algorytmu (tzw struktura danych przechowująca trajektorię wykonania), aby zapewnić integralność obliczeń. Język używany do wyrażania tego układu równań (zwanego także układem ograniczeń) nazywa się arytmetyką.
System dowodowy PLONKish ZK-SNARK wykorzystuje arytmetykę o większej mocy wyrazu niż starsze systemy dowodowe. Pierwszy pozwala na zastosowanie równań układu więzów o postaci dowolnego wielomianu na zmiennych ograniczających, podczas gdy w przypadku starszych układów dowodowych (tj. układów opartych na R1CS) równania te miały postać wielomianów liniowych i kwadratowych. Cecha ta sprawia, że system dowódowy PLONKish ZK-SNARK pozytywnie wpływa na wydajność obliczeniową udowadniającego i ułatwia jego zastosowanie do różnych algorytmów. Dlatego w ostatnich latach pojawiło się wiele systemów dowódczych PLONKish ZK-SNARK, takich jak klasyczny PLONK, Halo2, Kimchi, Plonky2, HyperPlonk itp.
W Taiko stosujemy wariant systemu dowodowego Halo2 oparty na schemacie zobowiązań wielomianowych KZG.
System dowódowy PLONKish ZK-SNARK składa się z trzech elementów:
4.2 Plan zobowiązań
Schemat obietnicy umożliwia osobie zatwierdzającej opublikowanie wartości zwanej obietnicą, która wiąże osobę zatwierdzającą z wiadomością bez ujawniania samej wiadomości. Osoba zatwierdzająca może następnie otworzyć zobowiązanie i udostępnić zatwierdzony komunikat lub jego część weryfikatorowi, który może sprawdzić, czy ujawnione informacje są zgodne ze zobowiązaniem.
Różni autorzy opisują różną liczbę algorytmów tworzących schemat zobowiązań. Należy jednak wspomnieć o co najmniej czterech z tych algorytmów:
Konfiguracja: pobiera pewne parametry początkowe jako dane wejściowe i generuje parametry konfiguracji. Ustawienia określają (i) do czego się zobowiązujemy (np. w przypadku schematu zaangażowania wielomianu jednoargumentowego określamy dziedzinę współczynników i maksymalny stopień wielomianu, do którego się zobowiązujemy) oraz (ii) poziom bezpieczeństwa w bitach. Możemy po prostu zdefiniować poziom bezpieczeństwa w następujący sposób: Jeśli złamanie systemu szyfrującego zajmuje O(2^n) czasu, wówczas poziom bezpieczeństwa systemu szyfrującego wynosi n bitów.
Obietnica: Obietnica generująca komunikaty na podstawie ustawionych parametrów.
Otwarcie częściowe: Generuje dowód częściowego otwarcia specyficzny dla wybranej części wiadomości (np. wartość zatwierdzonego wielomianu jednoargumentowego dla jakiegoś parametru) oraz ustawia parametry.
Walidacja: Użyj częściowo otwartego poświadczenia i ustaw parametry, aby sprawdzić, czy informacje ujawnione przez moduł sprawdzający są określoną częścią komunikatu odpowiadającą określonemu zobowiązaniu.
*W przypadku niektórych schematów zatwierdzania algorytmy „konfiguracji” i „otwierania” mogą nie istnieć (na przykład podczas używania funkcji skrótu do zatwierdzania dużych wartości).
Plan zobowiązań powinien posiadać następujące cechy:
Wiązanie: gdy dowódca zatwierdzi konkretną wiadomość, zostanie powiązany z wiadomością, do której się zobowiązał;
Ukrywanie: Obietnica nieujawniania żadnych informacji na temat wiadomości. Ukrywanie może być doskonałe, tj. dowód częściowo otwarty nie ujawnia żadnych informacji o niezapytanej części komunikatu (np. zobowiązanie KZG) lub niedoskonały, tj. dowód częściowo otwarty ujawnia część ww. informacji (np. oparty na FRI zobowiązanie wielomianowe).
Schematy zobowiązań można podzielić na kilka typów w zależności od obiektu docelowego: zobowiązanie jednoelementowe; zobowiązanie oparte na wektorze;
Schematy zobowiązań wielomianowych są jedynym typem bezpośrednio stosowanym w systemie dowódowym PLONKish ZK-SNARK. Dla powyższych systemów dowodowych (takich jak klasyczny PLONK, Halo2, Kimchi, Plonky2 itp.) bardzo ważny jest schemat zobowiązań wielomianowych jednowymiarowych. Jednakże obecnie dostępnych jest kilka nowych metod PLONKish ZK-SNARK opartych na wieloliniowych schematach zobowiązań wielomianowych (np. HyperPlonk).
4.3 Interaktywny dowód Oracle
Interaktywny dowód wyroczni to dowód interaktywny, w którym weryfikator ma „dostęp do wyroczni”, aby uzyskać komunikaty dowodzącego, może odpytywać je w sposób probabilistyczny i nie musi czytać całych komunikatów weryfikatora.
4.4 Heurystyka Fiata-Shamira
Heurystyka Fiata-Shamira umożliwia przekształcenie interaktywnych argumentów (publicznych monet) w argumenty nieinteraktywne. Intuicyjnie pomysł polega na zastąpieniu losowego wyzwania walidatora hashem poprzedniej wiadomości, ale szczegóły są generalnie nieokreślone.
*Public Coin Protocol to protokół, w którym walidatory wysyłają wyłącznie elementy losowe.
4.5 Zasada działania systemu dowódowego ZK-SNARK typu PLONK
W systemie dowodowym ZK-SNARK do udowodnienia wiedzy świadka wykorzystywana jest zmodyfikowana interaktywna metoda dowodowa Oracle, która wykorzystuje zobowiązania wielomianowe, aby zapewnić Oracle dostęp do wiadomości osoby dowodzącej i czyni ją wolną od interakcji poprzez heurystykę Fiata-Shamira. W tej sekcji szczegółowo wyjaśnimy działanie danego konstruktora.
Przypomnijmy, że zastosowanie systemu dowodowego ZK-SNARK do algorytmu wymaga zbudowania odpowiedniego systemu ograniczeń. Aby móc go zbudować, definiujemy strukturę tabeli śledzenia wykonania algorytmu i znajdujące się w niej wartości stałe. Terminu „obwód” używamy w odniesieniu do złożonej struktury tabeli śledzenia wykonania, wypełnionej wyłącznie stałymi i odpowiednim systemem ograniczeń. Aby wygenerować dowód ZK-SNARK dla instancji wykonania algorytmu, należy zsyntetyzować dla niego instancję obwodu, która będzie odpowiadającą instancją obwodu algorytmu i tablicy śledzenia wykonania (tj. tabeli określającej stałe, świadki, i wartości deklaracji publicznych) kombinacja.
Rozważmy strukturę tabeli śledzącej wykorzystywanej przez system sprawdzający ZK-SNARK typu PLONK. Wszystkie kolumny w takiej tabeli należą do jednego z trzech typów, które nazywamy zgodnie z terminologią stosowaną w Halo2 i opisujemy następująco:
Kolumny stałe - ich komórki zawierają stałe z tabeli śledzenia wykonania;
Kolumna Instancja - służy do przechowywania wartości deklaracji publicznych;
Kolumna sugestii - w której przechowywane są wszystkie dane świadków (w tym wartości niezależnych świadków i obliczone tajne wyniki).
Podsumowując, zauważamy, co następuje:
Tabela śledzenia wykonania (typ PLONKish) = stałe kolumny + kolumny instancji + kolumny sugestii; obwód = tabela śledzenia wykonania zawierająca tylko stałe + system ograniczeń instancja obwodu = obwód + świadkowie w jego tabeli + publiczne deklaracje w swojej tabeli; oświadczenie publiczne, wartość niezależnego świadka) → Instancja obwodu Zastosuj system dowodowy ZK-SNARK do określonego algorytmu = opisz obwód + zdefiniuj proces syntezy.
Dlaczego termin „obwód” jest powszechnie używany w tym kontekście? Początkowo, gdy dostępne były tylko systemy dowódcze ZK-SNARK oparte na R1CS, wygodnie było przedstawić układ ograniczeń w postaci obwodu arytmetycznego, którego wyjście musi wynosić zero. Uważamy, że w kontekście PLONSKICH SNARK-ów termin „obwód” jest używany ze względów historycznych. Tak czy inaczej, przyjrzyjmy się pokrótce układowi arytmetycznemu stosowanemu w starszych wersjach ZK-SNARK.
Obwód arytmetyczny dla SNARK opartych na R1CS definiuje n-zmienny wielomian w ciele skończonym i ma schemat oceny. Początkowo jest on reprezentowany jako skierowany graf acykliczny (DAG):
Obejmuje:
Publiczne wejście x, używane do określenia wartości deklaracji publicznej;
Tajne wejście w, używane do określenia wartości niezależnego świadka;
Bramki arytmetyczne do określania dodawania i mnożenia po ciałach skończonych.
Spójrzmy na przykład obwodu arytmetycznego nad ciałem liczb wymiernych.
Zaczynamy od dołu i pracujemy z najniższymi bramkami na schemacie, czyli (2 x 4 = 8) i (4 + 11 = 15), zapisując te wartości jako wartości pośrednie;
Następnie przechodzimy o jeden wiersz w górę (do drugiego wiersza) i obliczamy sumę dwóch wartości pośrednich (które uzyskaliśmy w poprzednim etapie), czyli (8 + 15 = 23);
Ponieważ mamy tylko trzy bramy i przeszliśmy przez wszystkie, naszym ostatecznym wynikiem jest 23.
Po tym, jak system dowódowy PLONKish ZK-SNARK zsyntetyzuje instancję obwodu, kolumny tabeli śledzenia wykonania każdej instancji są kodowane jako wielomiany w polach skończonych w następujący sposób. Załóżmy, że C_j(x) jest wielomianem opisującym kolumnę j, a ω jest pierwiastkiem pierwotnym 2^k-th, gdzie k jest wybrane w taki sposób, że 2^k jest nieco większe niż początkowa wysokość instancji tabeli. Instancja tabeli jest zapełniana losowymi wierszami (tylko niezerowymi komórkami w sugerowanych kolumnach), aby zawierać 2^k wierszy, a C_j(ω^i) jest ustawiane na wartość i-tego wiersza j-tego kolumna danej instancji tabeli. Rola dopełnienia atrybutów o wiedzy zerowej zostanie wyjaśniona później.
Stwierdzenie „ω jest pierwiastkiem pierwotnym 2^k-th” oznacza, że ω^(2^k) = 1, a dla dowolnej dodatniej liczby całkowitej t mniejszej niż 2^k mamy ω^t ≠ 1.
Układ więzów przekształca się w postać równania wielomianowego, zastępując zawarte w nim zmienne odpowiednimi wielomianami uzyskanymi z wielomianów kolumnowych, podstawiając „x razy ω podniesione do pewnej potęgi” zamiast x.
Rozważmy na przykład równanie układu więzów s(i) * (a(i) * b(i) - c(i+1)) = 0. Oznacza to, że jeśli s(i) jest niezerowe, to a(i) * b(i) musi równać się c(i+1). Tutaj a, b i c to sugerowane kolumny, s to stała kolumna, a i to bieżący numer wiersza.
To ograniczenie można zastosować do wszystkich 2^k wierszy w następujący sposób. Niech S(x), A(x), B(x) i C(x) będą wielomianami odpowiednio w kolumnach a, b, c i s. Dlatego mamy nadzieję:
Oznacza to, że wszystkie elementy w tym zbiorze muszą być pierwiastkami S(x) * (A(x) * B(x) - C(x * ω)). Dlatego wielomian ten musi być podzielny przez:
Ponieważ ω jest pierwiastkiem pierwotnym rzędu 2^k.
Z(x) = x^(2^k) - 1 nazywa się „wielomianem zanikającym”, ponieważ wynosi 0 dla wszystkich x będących elementami cyklicznej grupy multiplikatywnej generowanej przez ω. Dlatego S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 oznacza, że powyższe ograniczenia obowiązują dla wszystkich 2^k wierszy.
Załóżmy, że P_0(x), P_1(x), ... , P_m(x) są ograniczeniami zastosowanymi do wszystkich 2^k wierszy i są zgodne z rozważanym wielomianem S(x) * (A(x) * B(x) powyżej ) - C(x * ω)) ma podobną postać. Jeżeli α zostanie wybrane przez weryfikatora losowo z ciała skończonego, to
Oznacza to, że z niezwykle dużym prawdopodobieństwem wszystkie te ograniczenia są spełnione dla wszystkich 2^k wierszy. To równanie oznacza, że możemy znaleźć ilorazowy wielomian T(x) taki, że
Aby zatem weryfikator mógł uwierzyć, że dowódca zna zawartość tablicy śledzenia wykonania, która z bardzo dużym prawdopodobieństwem spełnia wszystkie m ograniczeń, wystarczy jedynie wykazać, że dla losowo wybranego α dowód ma wystąpienia P_0 (x), P_1(x ),..., sugerowane wielomiany kolumnowe i wielomiany ilorazowe T(x) w P_m(x) spełniają to równanie wielomianowe. Weryfikator może to zrobić prosząc dowódcę o znalezienie wartości danego wielomianu w losowo wybranym przez weryfikatora punkcie spośród punktów niebędących pierwiastkiem ζ Z(x) i ocenę obu stron tego równania w tym punkcie ζ Uważam, że dowódca prawdopodobnie zna te wielomiany. Metodę tę można udowodnić za pomocą lematu Schwartza-Zippela.
Aby generowanie dowodu nie było interaktywne, wszystkie wartości losowe wygenerowane przez weryfikator w wersji interaktywnej należy uzyskać za pomocą heurystyki Fiata-Shamira.
Aby powiązać dowód z jego propozycją wielomianu i wielomianem ilorazowym T(x), stosuje się schemat zobowiązań wielomianowych. Dowód podejmuje zobowiązania na tych wielomianach, otwiera te zobowiązania w ζ (lub na ζ * ω^q, jeśli jakieś ograniczenie wpływa na wiersze i oraz i + q) i tworzy dowód, który zawiera (I) te zobowiązania, (II) Wartość wielomianu w ζ (lub powyżej ζ * ω^q, jeśli to konieczne) i (III) odpowiedni otwarty dowód. Właściwie, aby skrócić dowód, należy zastosować otwarcie wielokrotne, czyli wygenerować mały dowód dla wartości wszystkich punktów wielomianu. Dlatego dowód jest zwięzły.
Aby spełnić właściwość wiedzy zerowej, losowo wybrane wiersze przez dowód są dołączane do instancji tabeli śledzenia wykonania, tworząc jej wysokość 2^k wierszy. Te wiersze zawierają tylko niezerowe komórki w kolumnie sugestii, ponieważ tylko kolumna sugestii zawiera dane, które chcemy ukryć. Zrób to przed skonstruowaniem wielomianów kolumny propozycji, tak aby liczba par „wartość parametru” ujawnionych w okresie otwarcia zobowiązania była mniejsza niż liczba losowo dodanych par dla każdego wielomianu. Dlatego dla każdego wielomianu kolumny propozycji ilość informacji wymaganych do jego odzyskania po otwarciu zobowiązania jest większa niż ilość informacji świadka. Taka sytuacja skutkuje zerową wiedzą.
W fazie wstępnego przetwarzania wszystkie instancje obwodu wykonawczego wykonują niektóre z tych samych obliczeń, w tym konfigurują i obliczają wielomiany stałokolumnowe oraz ich zobowiązania dla schematu zobowiązań wielomianowych. Część danych uzyskanych w wyniku tych obliczeń jest wykorzystywana przez weryfikatora i często nazywana jest kluczem weryfikacji. Podobnie można zdefiniować pojęcie klucza potwierdzającego. Podstawowy schemat zobowiązań wielomianowych określa, czy ustawienia zaufania są dokonywane w fazie wstępnego przetwarzania.