Zero-Knowledge Proofs: Czym są rozwiązania zk-STARK i jak działają?

1. Czym to jest?

System zk-STARK Proof of Reserves (PoR) wykorzystuje teorię STARK, czyli złożone rozwiązanie matematyczne. zk-STARK to skrót oznaczający: Skalowalny, przejrzysty argument o zerowej wiedzy (ang. Zero-Knowledge Scalable Transparent Argument of Knowledge), kryptograficzną technologię opartą na [pomyśle] Vitalika (https://vitalik.eth.limo/general/2022/11/19/proof_of_solvency.html) stworzoną w celu egzekwowania integralności i prywatności obliczeń na łańcuchach bloków. W tym artykule przedstawiona zostanie zasada działania i ogólna koncepcja matematyczna; jeśli chcesz dowiedzieć się więcej, zajrzyj [tutaj]: (https://medium.com/starkware/stark-math-the-journey-begins-51bd2b063c71) lub here.

Jak to działa?

Rysunek 1. Tabela realizacji i drzewo Merkle skonstruowane dla zk-STARK PoR

Etap 1: ograniczenia podczas tworzenia

W celu dowiedzenia bezpieczeństwa zapewnianego przez naszą giełdę, przedstawiamy trzy twierdzenia:

Twierdzenie 1: Prawidłowo zgromadziliśmy wartości dla każdego użytkownika, włączając w to wartość każdej kryptowaluty i wartość netto środków każdego użytkownika

Twierdzenie 2: Giełda nie sfałszowała wirtualnego użytkownika, którego wartość netto jest ujemna, aby zmniejszyć całkowite zobowiązanie giełdowe (Indywidualny użytkownik jest akceptowany wyłącznie wtedy, gdy jego wartość netto jest wyższa niż 0)

Twierdzenie 3: Giełda deklaruje całkowitą wartość dla każdego pojedynczego użytkownika, więc każdy użytkownik powinien mieć możliwość zweryfikowania włączenia swojej wartości netto do wartości całkowitej

Aby przetestować i zweryfikować powyższe twierdzenia, musimy zbudować ograniczenia, takie jak:

Twierdzenie 1: Ograniczenie salda całkowitego (Ograniczenie prawidłowego salda całkowitego)

uts: rozmiar śladu użytkownika, czyli liczba wierszy śladów zawartych w danych każdego użytkownika.

suma: całkowite saldo użytkownika

N: liczba użytkowników

Twierdzenie 2: Ograniczenie nieujemne (Ograniczenie dodatniego kapitału własnego netto)

Twierdzenie 3: Ograniczenie włączenia (Ograniczenie włączenia całego salda konta użytkownika)

Zgodnie z powyższymi ograniczeniami tworzymy tabelę śledzenia, aby móc zatwierdzić i zweryfikować salda całkowite i nieujemne metodami kontroli wyrywkowych. Oto sposób budowania tabeli śledzenia (na potrzeby prostego przykładu zastosowano liczbę 3 użytkowników, których maksymalna wartość USD jest mniejsza niż 4^6 = 4096):

1. Tworzymy tabelę z 32 wierszami i 5 kolumnami, a następnie wypełniamy jej wiersze wartościami i identyfikatorami użytkownika, gdzie k % 8 = 6, i . Każde 8 wierszy stanowi blok, a informacje o aktywach użytkownika są teraz dostępne  od tyłu każdego bloku. Pierwszy użytkownik otrzymuje wirtualne salda 0, możemy je zatem opublikować, aby udowodnić, że kumulacja wartości nie zaczyna się od wartości ujemnej.

2. Konsekwentnie gromadzimy wartości zasobów użytkownika i wprowadzamy wynik w  wierszy, gdzie k % 8 = 7, oraz w ostatnie wiersze każdego bloku

3. Utrzymujemy dolną granicę dzieląc całkowitą wartość każdego użytkownika przez 4 od od końca każdego bloku. Robimy to, aby wartość netto użytkownika nie była ujemna i sprawdzamy, czy pierwsze wiersze są zerowe dla każdego bloku. Jeśli któraś pozycja użytkownika wykaże ujemną wartość netto, pierwszy wiersz jego bloku nie będzie równy zeru, ponieważ wartość ujemna (-x) będzie równa (p - x) w ostatnim polu , co jest bardzo dużą dodatnią wartością.

4. Wprowadzamy losowe liczby dla każdego użytkownika i wypełniamy puste miejsca w tabeli 0

Etap 2: Rozszerzenie wielomianu niskiego stopnia Wykorzystując powyższe ograniczenia wielomianu, możemy otrzymać wielomian śladu obliczeniowego o długości uts * N. Ze względów bezpieczeństwa wykonujemy obliczenie wartości zadeklarowanej wielomianu na większej dziedzinie oceny, ze współczynnikiem amplifikacji domeny jako _współczynnikiem rozszerzenia.

W powyższym przypadku moglibyśmy obliczyć wielomian p(x) z I(x). Używając współczynnika_rozszerzenia 8, jesteśmy w stanie obliczyć kolejne 32(8-1)* punkty na p(x).

Ponieważ dwa różne wielomiany stopnia D będą dzielić pomiędzy siebie punkty w w maksymalnej liczbie D, przykładowa para wielomianów z prawidłowym wielomianem (który spełnia powyższe ograniczenia) i fałszywym wielomianem stopnia D (który nie spełnia powyższych ograniczeń ) podzieli maksymalnie punkty w liczbie D. Oznacza to, że fałszywy wielomian ma szansę  przejść losową kontrolę wyrywkową. Jeśli wykonamy kontrolę wyrywkową n razy, szansa zmniejszy się do .

Zaimplementowaliśmy domyślny współczynnik_rozszerzenia jako 16 oraz domyślny czas inspekcji próbkowania jako 16, poziom bezpieczeństwa będzie zatem wynosił 80 bitów.

Etap 3: wielomian zadeklarowany Obliczamy wartość skrótu śladu obliczeń i odpowiadającego salda użytkownika, identyfikator użytkownika oraz wartość odpowiedniego wielomianu ograniczenia dla każdego wiersza, a następnie generujemy drzewo Merkle. Pierwiastek Merkle'a to wartość zadeklarowana wielomianu.

Etap 4: generowanie dowodu próbkowania Wykorzystując pierwiastek Merkle jako losowe źródło, możemy dokonać próbkowania danych. Aby uniknąć wycieku danych dot. śledzenia obliczeń, podczas próbkowania unikamy danych o indeksie *k ** współczynnik_rozszerzenia i generujemy ścieżkę Merkle'a odpowiadającą indeksowi próbkowania.

Aby sprawdzić, czy zatwierdzony wielomian jest prawidłowy i spełnia ograniczenia wymienione w etapie 1, wykonujemy kontrole wyrywkowe. Jak określono w etapie 2, na prawdopodobieństwo powodzenia ingerencji lub manipulacji będą miały wpływ czasy kontroli wyrywkowych.

Etap 5: generowanie dowodu niskiego stopnia

Określenia prawdopodobieństwa ingerencji lub manipulacji można dokonać poprzez kontrolę wyrywkową. Istnieje jednak warunek, o którym wspomniano już w etapie 2, nakazujący uprzednie upewnienie się, że weryfikowany stopień wielomianu nie przekracza stopnia prawidłowego. Aby poprawić wydajność dowodową, łączymy liniowo wszystkie wielomiany z ograniczeniami w jeden i generujemy dla niego dowód niskiego stopnia. Współczynniki kombinacji są również generowane przy użyciu pierwiastka Merkle stanowiącego źródło losowe.

Przykładowo, chcąc udowodnić, że wartości p0(x), p1(x) i p2(x) mają nie więcej niż D stopni, możemy wygenerować 2 losowe współczynniki z pierwiastka Merkle'a wygenerowanego w etapie 3 i obliczyć wielomian liniowy l(x) jako:

k0 = hasz (pierwiastek + „0”)
k1 = hasz (pierwiastek + „1”)
l(x) = k0 * p0(x) + k1 * p1(x) + p2(x)

Jeśli możliwe jest udowodnienie, że l(x) ma stopień nie większy niż D, to prawdopodobieństwo, że stopień któregokolwiek z p0(x), p1(x) i p2(x) jest większy niż D, będzie bliskie 0

Etap 6: całkowita weryfikacja salda Najpierw weryfikujemy dowód niskiego stopnia wygenerowany w etapie 5.

Następnie przeprowadzana jest dalsza otwarta weryfikacja na próbkowanych danych wygenerowanych w etapie 4. Najpierw sprawdzamy, czy dane są zgodne z zaangażowaniem wielomianowym, a następnie, czy dane spełniają ograniczenia stworzone w etapie 1. Na koniec weryfikowane są współczynniki kombinacji wielomianu testowego niskiego stopnia.

Etap 7: generowanie dowodu włączenia użytkownika Aby udowodnić, że określony użytkownik jest uwzględniony w całkowitej kwocie żądanej przez giełdę, zapewniamy obliczony ślad, saldo, identyfikator oraz losową liczbę odpowiadającą indeksowi użytkownika. Udostępniamy również ścieżkę Merkle odpowiadającą tym danym.

Etap 8: weryfikacja dowodu włączenia przez użytkownika Użytkownik sprawdza swoje saldo, identyfikator, oblicza wartość skrótu danych odpowiadających jego indeksowi i weryfikuje wartość skrótu w węźle terminalnym drzewa Merkle, korzystając z podanej ścieżki Merkle.

2. Jak przeprowadzić samoweryfikację za pomocą opcji Proof of Reserves (PoR)?

2.1 Sprawdź ograniczenie włączenia zk-STARK

Teoria weryfikacji

Zgodnie z procedurą STARK obliczymy tabelę śledzenia wykonania wszystkich zasobów użytkownika, jak przedstawiono poniżej, i zaszyfrujemy informacje o każdym użytkowniku w formie tabeli śledzenia, która stanie się pozycją terminalną drzewa Merkle; następnie zatwierdzimy pozycje terminalne do pierwiastka Merkle, który zostanie opublikowany podczas każdego audytu PoR.

Aby sprawdzić, czy własne aktywa znajdują się w katalogu głównym, udostępnimy ścieżkę Merkle na potrzeby weryfikacji. Możesz najpierw obliczyć swoją pozycję terminalną, mieszając informacje o zasobach, a następnie sprawdzić, czy jest ona prawidłowa w publikowanym przez nas drzewie i pierwiastku Merkle.

Na przykład na rysunku 1 użytkownik o identyfikatorze id_k oblicza wartość hashk = hash("20" + "15" + "5" + "id_k" + "99821"), a pozostałe dane zaznaczone w czerwonej kwadratowej ramce będą weryfikacją ścieżki Merkle. Do przeprowadzenia tej weryfikacji użytkownikom udostępniono narzędzie typu open-source.

Ponieważ pozycje terminalne drzewa Merkle występują w formie haszy, żadne prywatne informacje nie zostaną ujawnione innym osobom.

Sposób weryfikacji:

1） Aby zweryfikować, czy saldo aktywów Twojego konta zostało uwzględnione jako wartość Merkle zk-STARK, zaloguj się na swoje konto OKX, „odwiedź stronę „Audyty”), aby wyświetlić ostatnie audyty, kliknij opcję „Szczegóły”, aby wyświetlić dane audytu.

2）Dane potrzebne do ręcznej weryfikacji możesz uzyskać klikając „Kopiuj dane”.

3）Po kliknięciu „Kopiuj dane”, otwórz edytor tekstu (np. notatnik), następnie wklej i zapisz ciąg znaków JSON jako plik. Plik musi kończyć się nazwą „_inclusion_proof.json.” Ciąg JSON zawiera saldo konta i snapshot ścieżki Merkle, a następnie zapisz plik w nowym folderze.

Tekst JSON pokazano poniżej:

{
"batch_inclusion_proof": {
"batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed",
„total_value": 138312291,
„BTC”: 2152907,
„ETH”: 909757,
„USDT”: 2319557,
"random_number": „e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac",
„merkle_path": [
"5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9",
"9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da",
"973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2",
"0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a",
"2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a",
"4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609",
"4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374",
"cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab",
"ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62",
"1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8",
"5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933",
"e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167"
]
},
"trunk_inclusion_proof": {
"trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290",
"batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
„total_value": 2007657936,
„BTC”: 18915744,
„ETH”: 21522734,
„USDT”: 21268768,
„random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164",
"merkle_path": [
"1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376",
"a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b",
"413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b",
"d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b",
"85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6",
"d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec",
"147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e",
"0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4",
"b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a",
"ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2",
"7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf",
"239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d",
„bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43”
]
}
}

4）Pobierz narzędzie weryfikacji OKX typu open-sourcezk-STARKValidator

5）Zapisz narzędzie do weryfikacji typu open-source od OKX zk-STARKValidatori plik ciągu JSON razem w nowym folderze wymienionym w etapie 3. W naszym przypadku: zamieszczamy narzędzie oraz plik danych w folderze Pobrane (Downloads), pod nazwą "proof-of-reserves", jak pokazano poniżej:

6）Otwórz program zk-STARKValidator, który automatycznie uruchomi plik JSON zapisany w folderze.

7）Sprawdź wynik

– Jeśli weryfikacja będzie pomyślna, pojawi się komunikat „Weryfikacja ograniczenia włączenia zakończona pomyślnie” (Inclusion constraint validation passed), zgodnie z poniższym przykładem:

– Jeśli weryfikacja będzie niepomyślna, pojawi się komunikat „Weryfikacja ograniczenia włączenia zakończona niepowodzeniem” (Inclusion constraint validation failed), zgodnie z poniższym przykładem:

<p><img src="https://www.okx.com/cdn/assets/plugins/announcements/contentful/15303691813261.jpg"</p>

2.2 Weryfikacja całkowitego salda zk-STARK i nieujemnego ograniczenia

Sposób weryfikacji:

Aby zweryfikować i udowodnić, że rzekomo posiadane aktywa są prawdziwe a żaden użytkownik nie ma ujemnego kapitału własnego netto, odwiedź stronę z naszymi plikami audytu” i pobierz z niej pliki „zk-STARK” zawarte w obszarze Raport o odpowiedzialności (Liability report), a następnie zapisz je w nowym folderze.

Po rozpakowaniu pobranego pliku pojawi się folder o nazwie „sum proof data”, który zawiera tysiące folderów oddziałów i jeden folder magistrali. Każdy folder zawiera dwa pliki JSON o nazwie „sum_proof.json” i „ssum_value.json”.

Pobierz narzędzie weryfikacji OKX typu open-sourcezk-STARKValidator

Zapisz narzędzie do weryfikacji typu open-source OKXzk-STARKValidator i folder „sum proof data” razem w nowo utworzonym folderze z etapu 1. W naszym przypadku: zamieszczamy narzędzie oraz plik danych w folderze Pobrane (Downloads), pod nazwą „proof-of-reserves”, jak pokazano poniżej:

Otwórz program zk-STARKValidator, który automatycznie uruchomi pliki „sum proof data” zapisane w folderze.

Sprawdź wynik

Jeśli weryfikacja zakończy się pomyślnie, zostanie wyświetlony wynik „Walidacja sumy całkowitej i ograniczenia nieujemnego zakończona pomyślnie” (Total sum and non-negative constraint validation passed):

Jeśli weryfikacja zakończy się niepowodzeniem, zostanie wyświetlony wynik „Walidacja sumy całkowitej i ograniczenia nieujemnego nie została zakończona pomyślnie” (Total sum and non-negative constraint validation failed):