Napisali: Kang Shuiyue, dyrektor generalny Fox Tech; Meng Xuanji, główny naukowiec Fox Tech
Przedmowa
Technologia dowodu wiedzy zerowej w kryptografii jest szeroko stosowana w świecie web3, w tym w obliczeniach prywatności, zkRollup itp. Wśród nich FOAKS używany w projekcie FOX warstwy 2 jest algorytmem sprawdzającym o wiedzy zerowej. Wśród szeregu zastosowań wymienionych powyżej, istnieją dwie cechy, które są niezwykle ważne dla algorytmów dowodu z wiedzą zerową, a mianowicie wydajność i interaktywność algorytmu.
Znaczenie wydajności algorytmów jest oczywiste.Wydajne algorytmy mogą znacznie skrócić czas działania systemu, zmniejszając w ten sposób opóźnienia klienta i znacznie poprawiając doświadczenie użytkownika i wydajność.Jest to również ważny powód, dla którego FOAKS angażuje się w osiąganie liniowego czasu sprawdzania.
Z drugiej strony, z kryptograficznego punktu widzenia, projektowanie systemów dowodowych o wiedzy zerowej często opiera się na wielu rundach interakcji między osobami dowodzącymi i weryfikatorami. Na przykład w historii „jaskini wiedzy zerowej” użytej w wielu artykułach popularnonaukowych wprowadzających dowody wiedzy zerowej realizacja dowodu opiera się na wielu rundach interakcji związanych z przekazywaniem informacji pomiędzy Alibabą (weryfikatorem) a reporterami (weryfikatorami). Jednak w rzeczywistości w wielu scenariuszach aplikacji poleganie na interakcji spowoduje, że system przestanie być dostępny lub znacznie zwiększy opóźnienia. Podobnie jak w systemie zkRollup oczekujemy, że prover (czyli folder w FOX) będzie w stanie lokalnie wyliczyć poprawną wartość dowodu, bez konieczności interakcji z weryfikatorem.
Z tej perspektywy bardzo istotne jest pytanie, jak przekształcić interaktywny protokół dowodu z wiedzą zerową w protokół nieinteraktywny. W tym artykule przedstawimy proces FOX wykorzystujący klasyczną heurystykę Fiata-Shamira do generowania wyzwań w Brakedown w celu wdrożenia protokołów nieinteraktywnych.
Wyzwanie w dowodzie wiedzy zerowej
Algorytmy sprawdzające wiedzę zerową stały się niezwykle popularne wraz z rozprzestrzenianiem się aplikacji. W ostatnich latach narodziły się różne algorytmy, w tym FOAKS, Orion, zk-stark itp. Podstawowa logika dowodu tych algorytmów, a także wczesnego protokołu sigma w świecie kryptografii, polega na tym, że dowód (Prover) najpierw wysyła pewną wartość do weryfikatora (Verifier), a weryfikator generuje wyzwanie (Challenge) poprzez lokalne losowe liczby i wysyła je. Losowo wygenerowana wartość wyzwania jest wysyłana do sprawdzającego, który musi posiadać rzeczywistą wiedzę, aby udzielić odpowiedzi, która z dużym prawdopodobieństwem przejdzie weryfikator. Na przykład w jaskini wiedzy zerowej reporter rzucił monetą i powiedział Alibabie, czy ma wyjść z lewej, czy z prawej strony, co stanowi wyzwanie dla Alibaby. Jeśli naprawdę zna to zaklęcie, on może zdecydowanie wyjść z Go w wymaganym kierunku, w przeciwnym razie istnieje połowa szans na niepowodzenie.
Tutaj zauważamy, że wygenerowanie Wyzwania jest bardzo krytycznym krokiem. Ma dwa wymagania, losowe i nieprzewidywalne dla testera. Po pierwsze, losowość gwarantuje jego właściwości probabilistyczne. Po drugie, jeśli dowódca może przewidzieć wartość wyzwania, oznacza to, że bezpieczeństwo protokołu może zostać zniszczone bez wiedzy. Możemy kontynuować analogię, jeśli Alibaba będzie w stanie przewidzieć, po której stronie reporter go poprosi wyjdzie, on to zrobi. Nawet jeśli nie ma czaru, możesz wejść na tę stronę wcześniej, a wynik i tak będzie zgodny z umową.
Potrzebujemy więc sposobu, który umożliwi programowi sprawdzającemu wygenerowanie lokalnie takiej nieprzewidywalnej liczby losowej, a jednocześnie będzie można ją zweryfikować weryfikatorem, dzięki czemu będzie można zaimplementować protokół nieinteraktywny.
Funkcja skrótu
Nazwa funkcji skrótu może nie być nam obca. Niezależnie od tego, czy jest to problem matematyczny związany z eksploracją w protokole konsensusu Bitcoina POW, czy kompresją ilości danych, konstruowaniem kodu weryfikującego wiadomość itp., funkcja skrótu jest wszędzie. W różnych protokołach wymienionych powyżej w rzeczywistości wykorzystywane są różne właściwości funkcji skrótu.
W szczególności właściwości bezpiecznej funkcji skrótu obejmują następujące punkty:
Ściśliwość: deterministyczna funkcja skrótu może kompresować wiadomość o dowolnej długości do stałej długości.
Wydajność: Mając dane wejściowe x, łatwo jest obliczyć wynik h(x).
Odporność na kolizje: Mając dane wejściowe x1, trudno znaleźć inne wejście x2, x1x2, h(x1) = h(x2).
Należy zauważyć, że jeśli funkcja mieszająca spełnia odporność na kolizje, musi spełniać właściwość jednokierunkową, to znaczy, mając wynik y, trudno jest znaleźć x, które spełnia h(x) = y. W kryptografii nie jest możliwe skonstruowanie funkcji, która w teorii całkowicie spełnia właściwości jednokierunkowe, ale w praktycznych zastosowaniach funkcje skrótu można zasadniczo uważać za funkcje jednokierunkowe.
W ten sposób można stwierdzić, że wyżej wymienione zastosowania odpowiadają kilku różnym właściwościom funkcji skrótu. Jednocześnie mówimy, że funkcja skrótu odgrywa również bardzo ważną rolę w zapewnianiu losowości. Chociaż teoria kryptografii wymaga, aby A Nie da się obecnie skonstruować doskonałego generatora liczb losowych, ale w praktyce taką rolę może pełnić również funkcja mieszająca, co stanowi podstawę techniki heurystycznej Fiata-Shamira, którą przedstawimy później.
Heurystyka Fiata-Shamira
W rzeczywistości heurystyka Fiata-Shamira wykorzystuje funkcję skrótu do mieszania wcześniej wygenerowanego skryptu w celu uzyskania wartości, która jest używana jako wartość wyzwania.
Ponieważ funkcję skrótu H traktuje się jako funkcję losową, wyzwanie jest wybierane jednolicie losowo, niezależnie od publicznych informacji i zobowiązań sprawdzającego. Analiza bezpieczeństwa zakłada, że Alicja nie jest w stanie przewidzieć wyniku działania H i może go traktować jedynie jako wyrocznię. W tym przypadku prawdopodobieństwo, że Alicja odpowie poprawnie, nie przestrzegając protokołu (zwłaszcza, gdy nie zna niezbędnego sekretu) jest odwrotnie proporcjonalne do wielkości zakresu H.
Rysunek 1: Dowód nieinteraktywny z wykorzystaniem heurystyki Fiata-Shamira
Nieinteraktywne FOAKS
W tej sekcji szczegółowo demonstrujemy zastosowanie heurystyki Fiata-Shamira w protokole FOAKS, która jest używana głównie do generowania części wyzwania Brakedown w celu osiągnięcia nieinteraktywnego FOAKS.
Po pierwsze, widzimy, że wśród etapów generowania dowodów w Brakedown etapami, które należy zakwestionować, są „test przybliżenia” i część dowodowa drzewa Merkle (czytelnicy mogą zapoznać się z poprzednim artykułem „Zrozumienie zaangażowania wielomianowego Brak protokołu w FOAKS”). W pierwszym przypadku oryginalny proces polega na tym, że dowód potrzebuje losowego wektora wygenerowanego przez weryfikator. Proces obliczeń przedstawiono na poniższym rysunku:
Rysunek 2: Kontrole hamowania w nieinteraktywnym dowodzie FOAKS
Teraz używamy funkcji skrótu i pozwalamy, aby dowódca sam wygenerował ten losowy wektor.
Niech γ0=H(C1,R, r0,r1). Odpowiednio, w obliczeniach weryfikacyjnych weryfikatora należy również dodać ten etap obliczenia γ0. Zgodnie z tą strukturą można stwierdzić, że przed wygenerowaniem zobowiązania dowódca nie może z góry przewidzieć wartości wyzwania, więc nie może z góry „oszukiwać” na podstawie wartości wyzwania, czyli generowana jest odpowiadająca mu fałszywa wartość zobowiązania. Jednocześnie, zgodnie z hashem Losowość wyniku funkcji, ta wartość wyzwania również spełnia losowość.
Dla drugiego punktu niech Î =H(C1,R, r0,r1,c1,y1,cγ0,yγ0).
Używamy pseudokodu, aby zapewnić funkcje dowodowe i weryfikacyjne w zmodyfikowanym nieinteraktywnym zobowiązaniu wielomianowym Brakedown, które są również funkcjami używanymi w systemie FOAKS.
funkcja PC. Zatwierdź(ϕ):
Parse to macierz k × k. Dowódca lokalnie oblicza kod tensora kodujący C1, C2, C1 to macierz k × n, C2 to macierz n × n.
dla i ∈ [n] zrób
Oblicz korzeń drzewa Merkle'a Roott=Merkle.Commit(C2[:,i])
Oblicz pierwiastek drzewa Merkle'a R=Merkle.Commit([Root0,......Rootn-1]) i wyprowadź R jako zobowiązanie.
funkcja PC. Dowód(ϕ, X, R)
Dowódca generuje losowy wektor γ0 ∈ Fk poprzez obliczenie: γ0 =H(C1,R, r0,r1)
Bliskość:
Konsystencja:
Dowodzący wysyła c1,y1,cγ0,yγ0 do weryfikatora.
Prover oblicza wektor Î jako wyzwanie, w którym Î = H(C1,R, r0,r1,c1,y1,cγ0,yγ0)
dla idx ∈ Î zrób
Dowódca wysyła C1 [:,idx] i dowód drzewa Merkle'a dla Rootidx dla C2 [:,idx] w ramach R do weryfikatora
funkcja PC. VERIFY_EVAL(ΠX,X,y= ϕ (X),R)
Bliskość: ∀idx ∈ Î, Cγ0 [idx] == <γ0, C1[:,idx]> i Ec(yγ0) == Cγ0
Spójność: ∀idx ∈ Î, C1 [idx] == <γ0, C1[:,idx]> i Ec(y1) == C1
y==
∀idx ∈ Î, Ec ( C1[:,idx]) jest zgodne z ROOTidx, a dowód drzewa Merkle’a ROOTidx jest prawidłowy.
Wyjście akceptuje, jeśli wszystkie powyższe warunki są spełnione. W przeciwnym wypadku wyjście odrzuca.
Wniosek
Wiele algorytmów sprawdzających o wiedzy zerowej opiera się na interakcji między weryfikatorami i weryfikatorami na początku ich projektowania. Jednak ten interaktywny protokół sprawdzający nie nadaje się do stosowania w scenariuszach aplikacji, które wymagają wysokiej wydajności i wymagają dużych narzutów na komunikację sieciową, takich jak on-on-. ochrona prywatności danych w łańcuchu i zkRollup i tak dalej. Dzięki heurystyce Fiata-Shamira (Heurystyka) osoba dowodząca może lokalnie wygenerować „wyzwanie” z liczby losowej bez niszczenia bezpieczeństwa protokołu i może to zostać zweryfikowane przez osobę dowodzącą. Według tej metody FOAKS wdraża również dowody nieinteraktywne i aplikuje je do systemu.
Referencje
1. Fiat, Amos; Shamir, Adi (1987). „Jak udowodnić swoją wartość: praktyczne rozwiązania problemów identyfikacji i sygnatury”. Postępy w kryptologii — CRYPTO' 86. Notatki z wykładów z informatyki. Springer Berlin Heidelberg. 263: 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0.
2.https://www.cnblogs.com/zhuowangy2k/p/12246575.html