Vitalik Buterin przez Blog Vitalika Buterina
To jest lustrzane odbicie postu pod adresem https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
To trzecia część serii artykułów wyjaśniających, jak działa technologia stojąca za zk-SNARK; poprzednie artykuły nt kwadratowe programy arytmetyczne i parowanie krzywych eliptycznych są lekturą obowiązkową, a w tym artykule założono znajomość obu koncepcji. Zakłada się również podstawową wiedzę na temat tego, czym są zk-SNARK i do czego służą. Zobacz też Artykuł Christiana Reitwiessnera tutaj na kolejne wprowadzenie techniczne.
W poprzednich artykułach przedstawiliśmy program arytmetyki kwadratowej, sposób przedstawiania dowolnego problemu obliczeniowego za pomocą równania wielomianowego, który jest znacznie bardziej podatny na różne formy matematycznych oszustw. Wprowadziliśmy także pary krzywych eliptycznych, które umożliwiają bardzo ograniczoną formę jednokierunkowego szyfrowania homomorficznego, która umożliwia sprawdzanie równości. Teraz zaczniemy od miejsca, w którym skończyliśmy i użyjemy parowania krzywych eliptycznych wraz z kilkoma innymi sztuczkami matematycznymi, aby umożliwić dowodzącemu udowodnienie, że zna rozwiązanie dla konkretnego QAP, bez ujawniania czegokolwiek więcej na temat rzeczywiste rozwiązanie.
W tym artykule skupimy się na Protokół Pinokia autorzy: Parno, Gentry, Howell i Raykova z 2013 r. (często nazywani PGHR13); istnieje kilka odmian podstawowego mechanizmu, więc wdrożony w praktyce schemat zk-SNARK może działać nieco inaczej, ale podstawowe zasady generalnie pozostaną takie same.
Na początek przejdźmy do kluczowego założenia kryptograficznego leżącego u podstaw bezpieczeństwa mechanizmu, z którego będziemy korzystać: *wiedza-wykładnika* założenie.
Zasadniczo, jeśli otrzymasz parę punktów � i �, gdzie �⋅�=�, i otrzymasz punkt �, to nie jest możliwe wymyślenie �⋅�, chyba że � jest w jakiś sposób „wyprowadzone” z � że wiesz. Może się to wydawać intuicyjnie oczywiste, ale założenia tego w rzeczywistości nie można wyprowadzić z żadnego innego założenia (np. logarytmu dyskretnego twardości), którego zwykle używamy, dowodząc bezpieczeństwa protokołów opartych na krzywych eliptycznych, a zatem zk-SNARK w rzeczywistości opierają się na pewnym bardziej chwiejne podstawy niż ogólniej kryptografia krzywych eliptycznych – choć nadal jest na tyle solidna, że większość kryptografów nie ma z tym problemu.
Przejdźmy teraz do tego, jak można to wykorzystać. Załóżmy, że para punktów (�,�) spada z nieba, gdzie �⋅�=�, ale nikt nie wie, jaka jest wartość �. Załóżmy teraz, że znajduję parę punktów (�,�), gdzie �⋅�=�. Następnie założenie KoE implikuje, że jedynym sposobem, w jaki mogłem utworzyć tę parę punktów, było wzięcie � i � i pomnożenie obu przez pewien współczynnik r które znam osobiście. Zauważ też, że dzięki magii parowania krzywych eliptycznych sprawdzamy, czy �=�⋅� właściwie nie wymaga wiedzy � – zamiast tego możesz po prostu sprawdzić, czy �(�,�)=�(�,�).
Zajmijmy się czymś ciekawszym. Załóżmy, że mamy dziesięć par punktów spadających z nieba: (�1,�1),(�2,�2)…(�10,�10). We wszystkich przypadkach ��⋅�=��. Załóżmy, że podam ci parę punktów (�,�), gdzie �⋅�=�. Co teraz wiesz? Wiesz, że � jest kombinacją liniową �1⋅�1+�2⋅�2+…+�10⋅�10, gdzie znam współczynniki �1,�2…�10. Oznacza to, że jedynym sposobem uzyskania takiej pary punktów (�,�) jest wzięcie wielokrotności �1,�2…�10, dodanie ich do siebie i wykonanie tych samych obliczeń z �1,�2… �10.
Zauważ, że biorąc pod uwagę dowolny konkretny zestaw �1…�10 punktów, dla których możesz chcieć sprawdzić kombinacje liniowe, w rzeczywistości nie możesz utworzyć towarzyszących �1…�10 punktów, nie wiedząc, czym jest �, a jeśli wiesz, co � oznacza, że możesz utworzyć parę (�,�), gdzie �⋅�=� dla dowolnego � chcesz, bez zawracania sobie głowy tworzeniem kombinacji liniowej. Dlatego też, aby to zadziałało, absolutnie konieczne jest, aby osoba tworząca te punkty była godna zaufania i faktycznie je usunęła – kiedy już utworzyła dziesięć punktów. Stąd pochodzi koncepcja „zaufanej konfiguracji”..
Pamiętaj, że rozwiązaniem QAP jest zbiór wielomianów (�,�,�) takich, że �(�)⋅�(�)−�(�)=�(�)⋅�(�), gdzie:
- � jest kombinacją liniową zbioru wielomianów {�1…��}
- � jest kombinacją liniową {�1…��} z tymi samymi współczynnikami
- � jest kombinacją liniową {�1…��} z tymi samymi współczynnikami
Zbiory {�1…��},{�1…��} i {�1…��} oraz wielomian � są częścią opisu problemu.
Jednak w większości rzeczywistych przypadków �,� i � są niezwykle duże; w przypadku czegoś z wieloma tysiącami bramek obwodów, jak funkcja mieszająca, wielomiany (i współczynniki kombinacji liniowych) mogą mieć wiele tysięcy terminów. Dlatego zamiast prosić dowódcę o bezpośrednie podanie kombinacji liniowych, użyjemy sztuczki, którą przedstawiliśmy powyżej, aby dowód udowodnił, że podaje coś, co jest kombinacją liniową, ale bez ujawniania czegokolwiek innego.
Być może zauważyłeś, że powyższa sztuczka działa na punktach krzywych eliptycznych, a nie na wielomianach. Dlatego w rzeczywistości dodajemy następujące wartości do zaufanej konfiguracji:
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
Można myśleć o t jako o „tajnym punkcie”, w którym obliczany jest wielomian. � to „generator” (jakiś przypadkowy punkt krzywej eliptycznej określony w protokole), a �,��,�� i �� to „odpady toksyczne”, liczby, które należy bezwzględnie usunąć za wszelką cenę, w przeciwnym razie ktokolwiek je posiada, będzie mógł wykonać fałszywe dowody. Teraz, jeśli ktoś da ci parę punktów �, � taką, że �⋅��=� (przypomnienie: nie potrzebujemy ��, aby to sprawdzić, ponieważ możemy sprawdzić parowanie), to wiesz, że to, co co dajesz, jest liniową kombinacją �� wielomianów obliczonych w �.
Zatem na razie dowód musi dać:
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
Zauważ, że osoba dowodząca tak naprawdę nie musi znać (i nie powinna wiedzieć!) �,��,�� ani ��, aby obliczyć te wartości; raczej dowódca powinien być w stanie obliczyć te wartości tylko na podstawie punktów, które dodajemy do zaufanej konfiguracji.
Następnym krokiem jest upewnienie się, że wszystkie trzy kombinacje liniowe mają te same współczynniki. Możemy to zrobić dodając kolejny zestaw wartości do zaufanej konfiguracji: �⋅(��(�)+��(�)+��(�))⋅�, gdzie � to kolejna liczba, którą należy uznać za „toksyczną” waste” i wyrzucić zaraz po zakończeniu zaufanej konfiguracji. Następnie możemy poprosić dowódcę o utworzenie kombinacji liniowej z tych wartości o tych samych współczynnikach i zastosować tę samą sztuczkę parowania, co powyżej, aby sprawdzić, czy ta wartość pasuje do podanego �+�+�.
Na koniec musimy udowodnić, że �⋅�−�=�⋅�. Robimy to jeszcze raz, sprawdzając parowanie:
�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))
Gdzie �ℎ=�⋅�(�). Jeśli związek pomiędzy tym równaniem a �⋅�−�=�⋅� nie ma dla ciebie sensu, wróć i przeczytaj artykuł o parach.
Widzieliśmy powyżej, jak przekształcić �,� i � w punkty krzywej eliptycznej; � to po prostu generator (tj. odpowiednik liczby jeden na krzywej eliptycznej). Możemy dodać �⋅�(�) do zaufanej konfiguracji. � jest trudniejsze; � jest po prostu wielomianem i niewiele z wyprzedzeniem przewidujemy, jakie będą jego współczynniki dla każdego indywidualnego rozwiązania QAP. Dlatego musimy dodać jeszcze więcej danych do zaufanej konfiguracji; konkretnie kolejność:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4….
W zaufanej konfiguracji Zcash sekwencja sięga około 2 milionów; tyle potęg � musisz mieć pewność, że zawsze będziesz w stanie obliczyć �(�), przynajmniej dla konkretnej instancji QAP, na której im zależy. Dzięki temu weryfikator może dostarczyć weryfikatorowi wszystkich informacji umożliwiających dokonanie ostatecznej kontroli.
Jest jeszcze jeden szczegół, który musimy omówić. W większości przypadków nie chcemy po prostu abstrakcyjnie udowodnić, że istnieje rozwiązanie jakiegoś konkretnego problemu; raczej chcemy udowodnić albo poprawność jakiegoś konkretnego rozwiązania (np. udowodnić, że jeśli weźmiesz słowo „krowa” i zahaszujesz je SHA3 milion razy, końcowy wynik zacznie się od 0x73064fe5), albo że rozwiązanie istnieje, jeśli ograniczysz niektóre parametry. Na przykład w przypadku kryptowaluty, w której kwoty transakcji i salda kont są szyfrowane, chcesz udowodnić, że znasz klucz deszyfrujący k, taki jak:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
Zaszyfrowany old_balance
, tx_value
i new_balance
należy podać publicznie, ponieważ są to konkretne wartości, które w tym konkretnym momencie chcemy zweryfikować; tylko klucz deszyfrujący powinien być ukryty. Konieczne są pewne drobne modyfikacje protokołu, aby utworzyć „niestandardowy klucz weryfikacyjny”, który odpowiada pewnym konkretnym ograniczeniom dotyczącym danych wejściowych.
A teraz cofnijmy się trochę. Po pierwsze, oto cały algorytm weryfikacji, dzięki uprzejmości bena Sasson, Tromer, Virza i Chiesa:
Pierwsza linia dotyczy parametryzacji; zasadniczo można myśleć o jego funkcji jako o tworzeniu „niestandardowego klucza weryfikacyjnego” dla konkretnego przypadku problemu gdzie określone są niektóre argumenty. Druga linia to sprawdzenie kombinacji liniowej dla �,� i �; trzecia linia to sprawdzenie, czy kombinacje liniowe mają te same współczynniki, a czwarta linia to sprawdzenie iloczynu �⋅�−�=�⋅�.
W sumie proces weryfikacji składa się z kilku mnożeń krzywej eliptycznej (po jednym dla każdej „publicznej” zmiennej wejściowej) i pięciu kontroli parowania, z których jedno obejmuje dodatkowe mnożenie par. Dowód zawiera osiem punktów krzywej eliptycznej: po parę punktów dla �(�),�(�) i �(�), punkt �� dla �⋅(�(�)+�(�)+�(� )) i punkt �ℎ dla �(�). Siedem z tych punktów leży na krzywej �� (po 32 bajty każdy, ponieważ współrzędną � można skompresować do jednego bitu), a w implementacji Zcash jeden punkt (��) znajduje się na skręconej krzywej w ��2 (64 bajtów), więc całkowity rozmiar dowodu wynosi ~288 bajtów.
Dwie najtrudniejsze obliczeniowo części tworzenia dowodu to:
- Dzielenie (�⋅�−�)/� w celu uzyskania � (algorytmy oparte na Szybka transformata Fouriera można to zrobić w czasie subkwadratowym, ale nadal jest to dość wymagające obliczeniowo)
- Wykonywanie mnożenia i dodawania krzywej eliptycznej w celu utworzenia wartości �(�),�(�),�(�) i �(�) oraz odpowiadających im par
Podstawowym powodem, dla którego stworzenie dowodu jest tak trudne, jest fakt, że to, co w pierwotnym obliczeniu było pojedynczą binarną bramką logiczną, zamienia się w operację, która musi zostać przetworzona kryptograficznie za pomocą operacji na krzywych eliptycznych, jeśli chcemy z tego zrobić dowód o wiedzy zerowej . Fakt ten, w połączeniu z superliniowością szybkich transformat Fouriera, oznacza, że utworzenie dowodu zajmuje około 20–40 sekund w przypadku transakcji Zcash.
Kolejnym bardzo ważnym pytaniem jest: czy możemy spróbować uczynić zaufaną konfigurację trochę… mniej wymagającą zaufania? Niestety nie możemy uczynić go całkowicie pozbawionym zaufania; samo założenie KoE wyklucza tworzenie niezależnych par (��,��⋅�) bez wiedzy, czym jest �. Możemy jednak znacznie zwiększyć bezpieczeństwo, stosując obliczenia wielostronne „z” – to znaczy konstruując zaufaną konfigurację między stronami w taki sposób, że dopóki przynajmniej jeden z uczestników usunął swoje toksyczne odpady, wszystko jest w porządku .
Aby mieć pojęcie, jak to zrobić, oto prosty algorytm wzięcia istniejącego zestawu (�,�⋅�,�⋅�2,�⋅�3…) i „dodania” własnego sekretu tak więc do oszukiwania potrzebny jest zarówno Twój sekret, jak i poprzedni sekret (lub poprzedni zestaw sekretów).
Zestaw wyjściowy to po prostu:
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…
Pamiętaj, że możesz wyprodukować ten zestaw, znając tylko oryginalny zestaw i s, a nowy zestaw działa w taki sam sposób jak stary zestaw, z tą różnicą, że teraz używasz �⋅� jako „odpadu toksycznego” zamiast �. Dopóki ty i osoba (lub osoby), która stworzyła poprzedni zestaw, nie usuniecie toksycznych odpadów i później nie dojdziecie do zmowy, zestaw jest „bezpieczny”.
Wykonanie tej czynności w przypadku pełnej zaufanej konfiguracji jest nieco trudniejsze, ponieważ wiąże się to z kilkoma wartościami, a algorytm musi zostać wykonany pomiędzy stronami w kilku rundach. Jest to obszar aktywnych badań mających na celu sprawdzenie, czy algorytm obliczeń wielostronnych można jeszcze bardziej uprościć i sprawić, że będzie wymagał mniejszej liczby rund lub będzie bardziej zrównoleglony, ponieważ im więcej możesz to zrobić, tym więcej stron będzie można włączyć do procedury zaufanej konfiguracji . Rozsądnie jest zrozumieć, dlaczego zaufana konfiguracja składająca się z sześciu uczestników, którzy znają się i współpracują ze sobą, może sprawić, że niektórzy ludzie poczują się niekomfortowo, ale zaufana konfiguracja z tysiącami uczestników będzie prawie nie do odróżnienia od całkowitego braku zaufania – a jeśli naprawdę masz paranoję , możesz samodzielnie wejść i wziąć udział w procedurze konfiguracji i mieć pewność, że osobiście usunąłeś swoją wartość.
Innym obszarem aktywnych badań jest zastosowanie innych podejść, które nie wykorzystują parowania i tego samego paradygmatu zaufanej konfiguracji, aby osiągnąć ten sam cel; Widzieć Niedawna prezentacja Eli ben Sassona dla jednej alternatywy (choć ostrzegam, jest co najmniej tak samo skomplikowana matematycznie jak SNARK!)
Specjalne podziękowania dla Ariela Gabizona i Christiana Reitwiessnera za recenzję.
- Dystrybucja treści i PR oparta na SEO. Uzyskaj wzmocnienie już dziś.
- PlatoData.Network Pionowe generatywne AI. Wzmocnij się. Dostęp tutaj.
- PlatoAiStream. Inteligencja Web3. Wiedza wzmocniona. Dostęp tutaj.
- PlatonESG. Węgiel Czysta technologia, Energia, Środowisko, Słoneczny, Gospodarowanie odpadami. Dostęp tutaj.
- Platon Zdrowie. Inteligencja w zakresie biotechnologii i badań klinicznych. Dostęp tutaj.
- Przesunięcia bloków. Modernizacja własności offsetu środowiskowego. Dostęp tutaj.
- Źródło: Inteligencja danych Platona.