zk-SNARK: zwięzłe nieinteraktywne argumenty

zk-SNARK (Zero-Knowledge Succinct Non-interactive ARgument of Knowledge) to dowód, który: (1) zapewnia wiedzę zerową, (2) jest zwarty (mały dowód i szybka weryfikacja niezależnie od rozmiaru obliczeń), (3) jest nieinteraktywny (pojedynczy ciąg dowodu).

Protokoły Sigma sprawdzają się w przypadku prostych twierdzeń (znajomość logarytmu dyskretnego). W przypadku złożonych obliczeń — „poprawnie wykonano tę funkcję na prywatnych danych wejściowych” — potrzebujemy uniwersalnego systemu dowodów. SNARK pozwala udowodnić dowolne obliczenia przy stałym czasie weryfikacji O(1).

Najpierw obliczenia wyraża się jako obwód arytmetyczny: skierowany graf acykliczny bramek dodawania i mnożenia nad ciałem skończonym. Przykład: udowodnienie znajomości x takiego, że x^3 + x + 5 = 35, bez ujawniania, że x=3. Obwód ma około 5 bramek.

Obwód arytmetyczny przekształca się w R1CS: zbiór ograniczeń (A*z)*(B*z) = C*z, gdzie z jest wektorem wszystkich wartości przewodów. Każda bramka mnożenia staje się jednym ograniczeniem. Dowodzący musi znaleźć z spełniające wszystkie ograniczenia, nie ujawniając prywatnych przewodów.

R1CS przekształca się w QAP: wielomiany A(x), B(x), C(x) takie, że A(x)*B(x)-C(x) jest podzielne przez wielomian docelowy t(x) wtedy i tylko wtedy, gdy ograniczenia są spełnione. Dowodzący pokazuje, że zna wielomianowy iloraz H(x), nie ujawniając świadka.

Groth16 (2016) to najbardziej wydajny uniwersalny SNARK. Po zaufanej konfiguracji (generowaniu CRS) dowodzący tworzy dowód z 3 elementów grupy (około 192 bajtów dla BLS12-381). Weryfikacja obejmuje 3 operacje parowania. Rozmiar dowodu jest stały niezależnie od rozmiaru obwodu.

Groth16 wymaga zaufanej konfiguracji dla każdego obwodu: należy wylosować toxic waste (losowy sekret), obliczyć Common Reference String, a następnie zniszczyć toxic waste. Jeśli sekret przetrwa, atakujący może fałszować dowody. Ceremonie wielostronne (Powers of Tau) rozpraszają zaufanie.

PLONK (2019) używa uniwersalnej zaufanej konfiguracji: jedna ceremonia działa dla wszystkich obwodów do określonego limitu rozmiaru. Nie jest potrzebna konfiguracja dla każdego obwodu. Kompromis polega na nieco większych dowodach niż w Groth16. Stosowany w implementacjach ZK-EVM (Polygon Hermez, zkSync Era).

STARK (Scalable Transparent ARguments of Knowledge) nie wymaga zaufanej konfiguracji i używa funkcji skrótu (bezpieczeństwo postkwantowe). Kompromisem są większe dowody (dziesiątki kilobajtów zamiast 200 bajtów). Stosowany w StarkWare/StarkNet oraz w języku Cairo. SNARK zapewnia mniejsze dowody, a STARK — bezpieczeństwo kwantowe.

Groth16 używa parowań dwuliniowych: e: G1 × G2 → GT, gdzie e(a*P, b*Q) = e(P,Q)^{ab}. Umożliwia to sprawdzanie tożsamości wielomianowych w wykładniku bez ujawniania wartości. Krzywa BLS12-381 jest zoptymalizowana pod kątem wydajnych parowań Groth16.

Czas generowania dowodu Groth16 dla obwodu z 10^6 bramek wynosi około 10 sekund na nowoczesnym procesorze. Weryfikacja trwa około 1 ms. Ta asymetria jest zamierzona: dowodzący, który wykonał kosztowne obliczenia, wykonuje pracę, a weryfikator (węzeł blockchaina) wykonuje niemal zerową ilość obliczeń.

Jaka jest główna wada Groth16 w porównaniu z PLONK?

zk-SNARK umożliwia udowadnianie dowolnych obliczeń za pomocą dowodów o stałym rozmiarze. Potok wygląda następująco: obliczenia → obwód arytmetyczny → R1CS → QAP → dowód SNARK. Groth16 jest najbardziej wydajny, ale wymaga zaufanej konfiguracji dla każdego obwodu; PLONK używa konfiguracji uniwersalnej. Dalej: zastosowania ZKP w blockchainach.