Czym jest zk-STARK i jak działa?

Czym jest zk-STARK?

zk-STARK to kryptograficzny sposób udowadniania, że obliczenie zostało wykonane poprawnie, bez konieczności ponownego wykonywania całego obliczenia przez osobę sprawdzającą proof. Dzięki właściwości zero-knowledge niektóre dane używane w obliczeniu mogą dodatkowo pozostać ukryte.

Skrót oznacza Zero-Knowledge Scalable Transparent ARgument of Knowledge. Brzmi technicznie, ale jego elementy można łatwo wyjaśnić:

• Zero-Knowledge: można udowodnić, że coś jest prawdą, bez ujawniania stojących za tym tajnych informacji.
• Scalable: nawet przy dużych obliczeniach proof można sprawdzać stosunkowo wydajnie.
• Transparent: nie jest potrzebna trusted setup. Nie trzeba więc wcześniej przeprowadzać specjalnej konfiguracji, w której powstają tajne informacje, a następnie muszą zostać bezpiecznie zniszczone.
• Argument of Knowledge: poprawny proof pokazuje, że jego twórca dysponuje informacjami potrzebnymi do prawidłowego wykonania obliczenia. Dzięki temu niezwykle trudno jest po prostu sfałszować poprawny proof.

W krypto jest to szczególnie przydatne wtedy, gdy duże obliczenia są wykonywane poza blockchainem. System może na przykład przetwarzać wiele transakcji off-chain, a następnie wysłać jeden proof do blockchaina. Blockchain nie musi wtedy ponownie wykonywać każdego obliczenia, lecz sprawdza jedynie, czy dostarczony proof jest ważny.

Przykład: Załóżmy, że tysiące transakcji są przetwarzane poza Ethereum. Zamiast ponownie wykonywać wszystkie te transakcje na Ethereum, system może wygenerować jeden zk-STARK, który dowodzi, że cały pakiet został przetworzony zgodnie z zasadami. Ethereum musi następnie sprawdzić tylko ten proof.

Podstawy STARK-ów zostały opisane w 2018 roku przez Eli Ben-Sassona, Iddo Bentova, Yinona Horesha i Michaela Riabzeva. System został zaprojektowany tak, aby duże obliczenia można było sprawdzać wydajnie, bez trusted setup.

Najważniejsze informacje

• zk-STARK dowodzi, że obliczenie zostało wykonane poprawnie, bez ponownego wykonywania go w całości.
• Zero knowledge może ukrywać prywatne dane wejściowe, ale nie jest automatycznie obecne w każdym zastosowaniu STARK.
• STARK-i nie wymagają trusted setup z tajnymi parametrami.
• W rollupach wiele transakcji off-chain można sprawdzić na blockchainie za pomocą jednego validity proof.
• Technika może być używana zarówno do skalowania blockchaina, jak i do weryfikowalnych obliczeń poza krypto.

Jak działa zk-STARK?

zk-STARK zamienia duże obliczenie w formę, którą można znacznie wydajniej sprawdzić. Strona wykonująca obliczenie, czyli prover, tworzy następnie kryptograficzny proof. Verifier sprawdza ten proof bez ponownego wykonywania całego pierwotnego obliczenia.

Mówiąc prościej: prover wykonuje ciężką pracę obliczeniową, a verifier sprawdza za pomocą kilku kryptograficznych i matematycznych testów, czy wynik się zgadza.

W dużym uproszczeniu wygląda to tak:

1. Obliczenie zostaje zamienione na reguły matematyczne: Najpierw ustala się, jakim regułom musi odpowiadać każdy krok obliczenia. W STARK-ach często odbywa się to za pomocą tzw. Algebraic Intermediate Representation (AIR). Można to traktować jako matematyczny opis tego, co podczas obliczenia jest dozwolone, a co nie.

2. Prover zapisuje wszystkie kroki obliczeń: Prover wykonuje obliczenie i tworzy tzw. execution trace. Można to traktować jako dużą tabelę, w której zapisywane są kolejne kroki obliczenia.

3. Dane są utrwalane kryptograficznie: Prover przetwarza te dane matematycznie i utrwala je za pomocą kryptograficznych commitments, na przykład przy użyciu Merkle tree. Dzięki temu prover nie może później po prostu zmienić danych.

4. Verifier sprawdza wybraną część danych: Następnie przeprowadzane są kontrole w nieprzewidywalnych miejscach. Verifier sprawdza między innymi, czy dane zgadzają się z wcześniej zapisanymi commitments oraz czy przestrzegano matematycznych reguł obliczenia. STARK-i wykorzystują do tego między innymi technikę o nazwie FRI. Pozwala ona wydajnie sprawdzić, czy użyte funkcje matematyczne mają właściwą postać, bez osobnego kontrolowania wszystkich danych.

5. Proof zostaje zweryfikowany: Jeśli wszystkie kontrole zakończą się powodzeniem, verifier ma silną kryptograficzną pewność, że obliczenie zostało wykonane poprawnie. Nie trzeba przy tym ponownie wykonywać całego obliczenia. W przypadku użycia na blockchainie prover może wysłać końcowy proof do smart contractu. Taki kontrakt sprawdza proof i akceptuje nowy wynik tylko wtedy, gdy jest on ważny. StarkWare wykorzystuje na przykład on-chain verifiers na Ethereum do sprawdzania STARK-proofów.

Przykład: Załóżmy, że rollup przetwarza 1 000 transakcji poza Ethereum. Rollup wykonuje wszystkie obliczenia, a następnie tworzy jeden proof, który pokazuje, że transakcje zostały przetworzone zgodnie z zasadami. Ethereum nie musi potem ponownie wykonywać wszystkich 1 000 transakcji. Zamiast tego smart contract sprawdza proof. Jeśli jest on ważny, nowy stan rollupu może zostać zaakceptowany.

To sprawia, że zk-STARK-i są szczególnie interesujące z punktu widzenia skalowalności: dużo obliczeń może odbywać się poza blockchainem, a sam blockchain nadal może kryptograficznie sprawdzić, czy wynik jest poprawny.

Czym są zero-knowledge proofs?

Zero-knowledge proof pozwala udowodnić, że dane twierdzenie jest prawdziwe, bez ujawniania tajnych informacji stojących za tym twierdzeniem.

Mówiąc prościej: prover pokazuje verifierowi, że coś jest poprawne, bez konieczności udostępniania wszystkich danych źródłowych.

Zero-knowledge proof ma trzy ważne właściwości:

• Completeness: jeśli twierdzenie jest prawdziwe, a prover wszystko wykonuje poprawnie, verifier może zaakceptować proof.
• Soundness: ktoś, kto próbuje udowodnić nieprawdziwe twierdzenie, ma tylko znikomo małą szansę na powodzenie.
• Zero knowledge: verifier nie poznaje żadnych dodatkowych tajnych informacji poza tym, że twierdzenie jest prawdziwe.

Przykład: System może udowodnić, że pakiet transakcji został przetworzony zgodnie ze wszystkimi zasadami, bez ujawniania części prywatnych danych z tych transakcji.

W rollupie publiczne twierdzenie może na przykład brzmieć, że nowy state root wynika z ważnego zestawu transakcji. To, jakie dane pozostają ukryte, zależy od tego, jak zaprojektowano system proofów i samą aplikację.

Warto wiedzieć: validity proof nie zapewnia automatycznie prywatności. System może kryptograficznie udowodnić, że transakcje zostały przetworzone poprawnie, a mimo to same dane transakcyjne mogą pozostać publiczne. Aby zapewnić prywatność, właściwość zero-knowledge musi zostać świadomie wbudowana w system.

Jaka jest rola STARK-ów?

STARK-i to system proofów, dzięki któremu duże obliczenia można wydajnie udowodnić i sprawdzić bez trusted setup.

Właściwość zero-knowledge określa przy tym, jakie informacje mogą pozostać ukryte. Technika STARK zapewnia, że verifier może wydajnie sprawdzić, czy obliczenie zostało wykonane zgodnie z zasadami.

Ważną cechą STARK-ów jest to, że są transparent. Nie wymagają trusted setup, w którym wcześniej tworzy się tajne parametry kryptograficzne, a następnie trzeba je bezpiecznie zniszczyć. Zamiast tego system opiera się między innymi na publicznej losowości i kryptograficznych funkcjach hashujących.

STARK-i wykorzystują również techniki takie jak FRI, które pozwalają wydajnie sprawdzić, czy matematyczna struktura stojąca za proofem jest poprawna.

Termin Argument of Knowledge oznacza, że prover nie może po prostu stworzyć poprawnego proofu. Przy założeniach bezpieczeństwa systemu prover musi dysponować informacjami potrzebnymi do prawidłowego wykonania obliczenia.

Do czego używa się zk-STARK-ów?

zk-STARK-i wykorzystuje się przede wszystkim do wykonywania dużych obliczeń poza blockchainem, a następnie do udowodnienia jednym kryptograficznym proofem, że wynik jest poprawny. Ważnym zastosowaniem są tutaj validity rollups.

W takim rollupie wiele transakcji jest przetwarzanych poza warstwą bazową. Następnie do blockchaina wysyłany jest proof, który pokazuje, że nowy stan powstał ze starego zgodnie z zasadami.

Jest to wygodne, ponieważ warstwa bazowa nie musi ponownie wykonywać wszystkich obliczeń. Koszt jednego proofu można więc rozłożyć na dużą grupę transakcji.

Znanym przykładem jest StarkEx. System ten wykorzystuje STARK-proofy do przetwarzania dużych wolumenów transakcji w zastosowaniach takich jak handel, płatności, gry i NFT. Transakcje są grupowane, po czym tworzony jest proof, który smart contract na Ethereum sprawdza.

Technologia STARK może być używana także poza krypto. W zasadzie nadaje się do sytuacji, w których trzeba udowodnić, że duże obliczenie zostało wykonane poprawnie, bez konieczności ponownego wykonywania wszystkich obliczeń przez kontrolującego. Dzięki zero knowledge można przy tym ukryć również niektóre dane źródłowe.

Sam proof nie rozwiązuje jednak wszystkiego. W rollupach nadal ważne jest na przykład to, gdzie dostępne są dane transakcji. Ważny proof dowodzi, że obliczenie jest zgodne z ustalonymi zasadami, ale nie zapewnia automatycznie dostępności wszystkich danych.

Jakie blockchainy używają STARK-ów?

Najbardziej znanym przykładem sieci blockchain wykorzystującej STARK-proofy jest Starknet. Starknet to Layer 2 zbudowany na Ethereum, który przetwarza wiele transakcji poza Ethereum, a następnie wysyła STARK-proof do Ethereum.

Ethereum sprawdza ten proof, aby potwierdzić, że nowy stan Starknet został obliczony poprawnie. Dzięki temu Ethereum nie musi osobno ponownie wykonywać wszystkich transakcji zachodzących na Starknet.

Również StarkEx wykorzystuje STARK-proofy, ale StarkEx nie jest samodzielnym blockchainem. To rozwiązanie skalujące, które pozwala różnym aplikacjom krypto przetwarzać duże ilości transakcji poza Ethereum, a następnie kryptograficznie udowadniać, że obliczenia zostały wykonane poprawnie.

Samo Ethereum nie używa więc STARK-ów jako własnego mechanizmu konsensusu ani mechanizmu transakcyjnego. Sieć może jednak sprawdzać STARK-proofy dostarczane przez aplikacje i sieci Layer 2, takie jak Starknet.

Warto wiedzieć: użycie STARK-proofów nie oznacza automatycznie, że transakcje są prywatne. Starknet używa STARK validity proofs, aby udowodnić, że obliczenia zostały wykonane poprawnie, natomiast prywatność zero-knowledge to osobna właściwość.

Jakie są zalety zk-STARK-ów?

zk-STARK-i pozwalają sprawdzać duże obliczenia znacznie wydajniej niż wtedy, gdy każdy uczestnik musiałby wykonywać wszystkie obliczenia od nowa.

Najważniejsze zalety to:

• Brak trusted setup: STARK-i nie wymagają wcześniejszej ceremonii, podczas której tworzone są tajne informacje kryptograficzne, a następnie muszą zostać bezpiecznie zniszczone.
• Wydajna weryfikacja: verifier może sprawdzić duże obliczenie bez ponownego wykonywania każdego pojedynczego kroku.
• Przydatność w skalowaniu: jeden proof może potwierdzić poprawne wykonanie dużego pakietu transakcji, dzięki czemu blockchainy mogą przetwarzać więcej transakcji poza warstwą bazową.
• Możliwość zapewnienia prywatności: gdy zero knowledge jest wbudowane w system, niektóre prywatne dane mogą pozostać ukryte, a obliczenie nadal może być weryfikowalne.
• Bezpieczeństwo oparte na hashach: STARK-i opierają swoją warstwę proving na kryptograficznych funkcjach hashujących, a nie na parowaniach krzywych eliptycznych, które są używane w wielu klasycznych systemach SNARK.

Dzięki takiemu podejściu opartemu na hashach STARK-i są też często postrzegane jako lepiej przygotowane na przyszłość z silnymi komputerami kwantowymi. Znane algorytmy kwantowe stanowią bowiem większy problem dla wielu konstrukcji opartych na krzywych eliptycznych niż dla dobrze dobranych kryptograficznych funkcji hashujących.

Nie oznacza to jednak, że każda aplikacja wykorzystująca STARK-i jest automatycznie w pełni odporna na komputery kwantowe. Ważne pozostają także użyte funkcje hashujące, parametry, implementacja i inne elementy kryptograficzne systemu.

Jakie są ograniczenia zk-STARK-ów?

zk-STARK-i mają również wady. Przede wszystkim tworzenie proofu może wymagać dużej mocy obliczeniowej i pamięci. Ciężka praca więc nie znika, lecz zostaje przede wszystkim przeniesiona na provera.

Ponadto proofy STARK są zazwyczaj większe niż proofy wielu klasycznych systemów zk-SNARK. Może to oznaczać, że podczas weryfikacji proofu na blockchainie trzeba przetworzyć więcej danych.

Inne ograniczenia to:

• Złożoność techniczna: deweloperzy muszą poprawnie przekształcić obliczenia do formy, którą system proofów może sprawdzić.
• Koszt generowania proofów: tworzenie proofów może wymagać dużej mocy obliczeniowej, a więc generować koszty.
• Proof sprawdza tylko zapisane reguły: jeśli logika aplikacji zawiera błąd, ważny proof dowodzi jedynie, że te błędne reguły zostały poprawnie zastosowane.
• Prywatność nie jest automatyczna: system oparty na STARK-ach może używać validity proofs bez ukrywania danych transakcyjnych.

Krótko mówiąc: proof STARK może bardzo silnie dowodzić, że określone obliczenie zostało wykonane zgodnie z zapisanymi zasadami, ale nie może stwierdzić, czy same zasady zostały dobrze zaprojektowane.

Jaka jest różnica między zk-STARK-ami a zk-SNARK-ami?

zk-STARK-i i zk-SNARK-i mają ten sam ogólny cel: wydajnie udowodnić, że obliczenie zostało wykonane poprawnie, bez konieczności ponownego wykonywania całego obliczenia przez verifiera.

Najważniejsza różnica dotyczy techniki kryptograficznej użytej do osiągnięcia tego celu.

Jedną z ważnych zalet zk-SNARK-ów jest to, że w wielu systemach proofy mogą być bardzo małe. Dzięki temu są atrakcyjne wtedy, gdy ilość danych, które trzeba zweryfikować on-chain, powinna być jak najmniejsza.

zk-STARK-i mają zwykle większe proofy, ale nie wymagają trusted setup i opierają się na innych założeniach kryptograficznych. Dlatego są szczególnie atrakcyjne przy dużych obliczeniach i w zastosowaniach, w których ważna jest przejrzystość konfiguracji.

Warto jednak nie wrzucać wszystkich zk-SNARK-ów do jednego worka. zk-SNARK to nazwa zbiorcza dla kilku systemów proofów. Nie każdy SNARK używa tej samej kryptografii i nie każdy wariant wymaga tego samego rodzaju trusted setup.

W obu technikach obowiązuje też ta sama zasada: validity proof nie oznacza automatycznie prywatności. Zero knowledge musi być częścią konkretnego systemu proofów i danej aplikacji.

Podsumowanie

zk-STARK to technika kryptograficzna, dzięki której można udowodnić, że duże obliczenie zostało wykonane poprawnie, bez konieczności ponownego wykonywania całego obliczenia przez verifiera.

To sprawia, że zk-STARK-i są szczególnie interesujące dla skalowania blockchaina. Rollupy mogą przetwarzać duże ilości transakcji poza warstwą bazową, a następnie jednym proofem wykazać, że wynik jest poprawny.

Do najważniejszych zalet należą przejrzysta konstrukcja bez trusted setup oraz wydajna weryfikacja dużych obliczeń. W zamian trzeba liczyć się z większymi proofami, dużą ilością pracy obliczeniowej po stronie provera i złożonością techniczną.

zk-STARK-i są więc przede wszystkim sposobem na to, by duże obliczenia były wydajne i kryptograficznie weryfikowalne. Prywatność może być ich częścią, ale nie jest obecna automatycznie.