Co będziesz potrzebował:
- wykształcenie informatyczne
- podstawy Ethereum
- podstawy rachunku różniczkowego (optymalizacja ograniczeń)
Co dostaniesz:
- podstawy SNARK-ów o zerowej wiedzy
- podstawy drzew Merkle
- jak Ethereum może skalować się do tysięcy transakcji na sekundę dzięki SNARKs
SNARK pozwala dowódcy udowodnić weryfikatorowi, że ma rozwiązanie W problemu F ze współdzielonymi / znanymi wejściami X, bez ujawniania W.
Znalezienie rozwiązania problemu może wymagać ogromnej ilości mocy obliczeniowej i pamięci.
Więc Weryfikator może być w zasadzie w 100% pewien, że Prover zadziałał poprawnie (i znalazł rozwiązanie), bez ponownego wykonywania pracy samodzielnie, aby sprawdzić rozwiązanie, ani nie znając go w ogóle. To magia!
Proces ma 3 kroki:
- USTAWIAĆ - Zadanie F (które należy wyrazić jako kwadratowy program arytmetyczny, patrz poniżej) jest przygotowane dla SNARK-ów. Proces ten wymaga bardzo dużej ilości pamięci i intensywności obliczeniowej w zależności od złożoności problemu (→ Liczba danych wejściowych i ograniczeń → Wymiar macierzy problemu spełnienia ograniczeń). Gracz, który przeprowadza przygotowania (może być samym Weryfikatorem), musi być zaufany przez wszystkie strony, ponieważ dane wyjściowe przygotowania są wykorzystywane w następnych fazach. Konfiguracja jest zwykle wykonywana za pomocą biblioteka, biblioteka C ++, która jest najpopularniejszą implementacją dla zkSNARKs.
- UDOWODNIA - Prover, który ma rozwiązanie W dla problemu F ze współdzielonymi wejściami X (być może wydał ogromne ilości procesora i pamięci, aby je znaleźć!), Używa biblioteka i dane wyjściowe ustawienie faza tworzenia dowodu 𝚷. Ten proces jest zdecydowanie wymagający dużej ilości pamięci i dużej mocy obliczeniowej (w zależności od złożoności problemu, jak wyżej). Rozmiar wyniku (tj. Dowodu 𝚷) jest zamiast tego zwięzły i niezmienny, niezależnie od złożoności problemu. Dowódca musi zaufać temu, kto wykonał fazę przygotowania, ponieważ wykorzystuje jej dane wyjściowe…
- WERYFIKACJA - A Weryfikator - podając jako wejście wyjście fazy Setup, wspólne wejścia X i dowód 𝚷 - sprawdza dowód. Jeśli weryfikacja zakończyła się powodzeniem, Dowódca zdołał udowodnić Weryfikatorowi, że znalazł rozwiązanie W problemu F… bez ujawniania W! Fajną częścią jest to, że nie tylko Proof jest zwięzły i ma zawsze tę samą długość…, proces weryfikacji jest szybki i nie wymaga dużej ilości pamięci / mocy obliczeniowej. W przeciwieństwie do dwóch poprzednich faz… weryfikację można łatwo przeprowadzić za pomocą smartfona w ciągu milisekund!
Dobre podsumowanie (źródło):
Jak to się stało? Cóż, to magia Merlina! Jeśli chcesz poznać matematykę, która za tym stoi, zacznij od tego miejsca.
Jak mogę przekształcić swoje oprogramowanie w program do arytmetyki kwadratowej?
Jak wspomniano powyżej, problem F fazy konfiguracji musi być kwadratowym programem arytmetycznym. Zasady gry są trudne:
- Dane wejściowe oprogramowania powinny być liczbami. Konwertuj swoje rzeczy (tablice, łańcuchy itp.) Na liczby. To trywialne.
- „Układ równań z ograniczeniami kwadratowymi” oznacza:
gdzie x to n-wymiarowy wektor twoich danych wejściowych, m to liczba ograniczeń (tj. liczba równań twojego systemu), C to n-wymiarowa macierz współczynników, a q to n-wymiarowy wektor współczynników. Jeśli nie lubisz macierzy i wektorów, oto przypadek n = 3 im = 2 (3 wejścia, 2 ograniczenia):
- Implementacja jest obwodem arytmetycznym, co oznacza, że wynik jest Problem rozwiązany (układ jest rozwiązany, tzn. wszystkie wielomiany są równe 0) lub Problem nie został rozwiązany (wszystkie inne przypadki). Innymi słowy: „te dane wejściowe są / nie są jednym z rozwiązań tego problemu”.
- Współczynniki C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 są ograniczeniami systemu. To jest w zasadzie to, co definiuje twoje oprogramowanie. Zmień je… a otrzymasz inne oprogramowanie! Wracając do sposobu działania SNARK: C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 są danymi wejściowymi fazy konfiguracji. Wynik fazy przygotowania (który jest potrzebny do sprawdzania i weryfikacji) jest zatem ściśle powiązany z tymi C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 i działa tylko dla tego problemu. Jeśli je zmienisz, definiujesz inne oprogramowanie / problem i musisz ponownie uruchomić fazę instalacji! x₁, x₂,…, x𝗇 to zmienne (tj. to, co musisz odgadnąć, aby uzyskać rozwiązanie systemowe). Więc kiedy mówimy „Szanowny dowódco, czy mógłbyś znaleźć tajne rozwiązanie W dla problemu F ze współdzielonymi / publicznymi danymi wejściowymi X”, mamy na myśli na przykład „Szanowny dowódco, czy możesz znaleźć wartości x₁, x₂,…, x𝗇, które rozwiązują system na przykład x₇ = 2393, x₅₂₆ = 5647? ” Możesz robić, co chcesz ze wszystkimi x𝗇, z wyjątkiem x₇ i x₅₂₆, które są ograniczone do wspólnych / publicznych wejść.
To ciężkie życie, ale możesz przeżyć… Jeśli potrzebujesz pętli, możesz je rozwinąć, powtarzając wielokrotnie tę samą operację. Lub jeśli potrzebujesz na przykład x₁⁴ x₂⁵, definiujesz nowe wejście x₃ = x₁⁴ x₂⁵ i używasz x₃ w swoich ograniczeniach. Chodzi o dodawanie zmiennych i ograniczeń… Nawet w przypadku całkiem prostego oprogramowania łatwo jest dotrzeć do setek milionów lub miliardów danych wejściowych i ograniczeń!
Chcieć wiedzieć więcej? Czytać tutaj. A także sprawdź ten podstawowy kod_do_r1cs.py z ethereum / research.
Co to jest drzewo Merkle?
Funkcja skrótu to reguła, która mapuje dane wejściowe o dowolnym rozmiarze na dane wyjściowe o stałym rozmiarze. Moglibyśmy wymyślić dość bezużyteczną funkcję skrótu „Połącz pierwsze dwie z ostatnimi dwiema literami”, która przekształci „Woody Allen” w „Woen”, a „Paul McCartney” w „Paey”.
Drzewo Merkle to struktura danych, w której każdy rodzic jest hashem swoich dwóch synów. U góry znajduje się Root, który jest skrótem dwóch synów poziomu 1. Na dole każdy liść jest hashem zewnętrznego wejścia.
Używając naszego słownika „Woody Allen” → „Woen”, funkcja skrótu:
Kiedy liść się zmienia, modyfikacja jest propagowana do korzenia. W przypadku zmiany ANTHONY zmieniają się również ANNY (liść), CENY i CECO (root). Niezależnie od tego, który liść się zmienia, zmienia się także korzeń.
Nie potrzebujesz całego drzewa, aby przeliczyć Root. W naszym przykładzie, jeśli ANTHONY się zmieni i znasz zarówno JACO, jak i CECILY, możesz łatwo ponownie obliczyć Root, nawet jeśli całkowicie zignorujesz JAMESA, MARCO, JAES i MACO. W przypadku dużych drzew oszczędza to dużo czasu!
Więc co?
Drzewa Merkle doskonale nadają się do sprawdzania integralności danych. Zwykle: wiesz, który jest prawidłowym rootem i sprawdzasz, czy otrzymane dane są zgodne z tym rootem. Na przykład: zaufana strona, która nie może podać Ci całego zestawu danych z imionami ludzi na Ziemi (nie ma czasu, nie ma przepustowości lub może w ogóle nie ma danych), daje Ci tylko Root (np. „CECO”). Posłowie: otrzymujesz miliony imion, wraz z numerem listu, przez tysiące niezaufanych osób. Cóż, ponieważ masz prawidłowy root, możesz sprawdzić, na kim możesz polegać, kto podaje fałszywe dane…
Drzewa Merkle też są częścią Twojego życia! Kiedy pobierasz plik Torrent o pojemności 3 GB, plik jest dzielony na miliony małych fragmentów. Skrót każdego kawałka jest przechowywany w liściu. Ponieważ wiesz, który jest prawidłowym korzeniem drzewa, za każdym razem, gdy otrzymasz od kogoś fragment pliku, możesz sprawdzić, czy jest poprawny. Jeśli tak nie jest, możesz poprosić kogoś innego o tę samą porcję.
Możesz to zrobić, nawet jeśli nie pobrałeś jeszcze całego drzewa / wszystkich liści: jeśli wiesz, że Root to CECO i ufasz JACO… kiedy otrzymasz fragment ANTHONY, możesz go zweryfikować, nawet jeśli nie pobrałeś jeszcze kawałki MARCO i JAMES.
Dlaczego drzewa Merkle są przydatne w technologii rozproszonej księgi, jest proste: używasz protokołów konsensusu (powolnych, drogich) tylko do osiągnięcia konsensusu w katalogu głównym. Wtedy niezaufane węzły sieci mogą wydajnie i bezpośrednio udostępniać dane… i mogą spać bezpiecznie dzięki sprawdzeniom integralności z Root.
Kiedy Bóg poprosił Ethereum o wybranie dwóch supermocy spośród bezpieczeństwa, skalowalności i decentralizacji… Ethereum poświęcił skalowalność. Właściwie nie ma mocnego ograniczenia „transakcji na sekundę”: limit dotyczy ilości gazu w każdym bloku - czyli, upraszczając, ilości operacji, które mogę wykonać w każdym bloku. Ten limit wynosi 2 milionów gazu. Może to oznaczać wiele „drobnych” transakcji (brak danych dołączonych do transakcji, brak operacji do wykonania na tych danych) lub kilka dużych transakcji. To zależy od węzłów Ethereum, które przesyłają transakcje, i od górników Ethereum, którzy uwzględniają w bloku transakcje, które płacą więcej.
Wydobywa się blok każdy ~ 15 sekund. Oznacza to ~ 32 miliony gazu na minutę, co zdecydowanie nie wystarczy, jeśli chcemy, aby dapsy Ethereum weszły do głównego nurtu.
Przy okazji: skończ z tymi żmudnymi porównaniami Ethereum i Visa. Scentralizowany system będzie zawsze bądź szybszy niż Ethereum… z założenia! Robią różne rzeczy i potrzebujesz ich w różnych sytuacjach. Jeśli nie potrzebujesz decentralizacji i środowiska pozbawionego zaufania… oczywiście powinieneś wybrać Visa. W skrócie: Fakt, że Twój blender obraca się szybciej niż pralka, nie oznacza, że wyczyścisz spodnie w blenderze!
Ułóżmy puzzle! Wyobraź sobie, że możesz „skompresować” wiele małych transakcji w jednej dużej transakcji dzięki SNARKs. Jeśli gaz wydany w ramach tej dużej transakcji jest mniejszy niż suma gazu wydanego w ramach drobnych transakcji, oznacza to, że oszczędzasz gaz.
A oszczędność gazu oznacza:
- Użytkownicy wydają mniej na transakcje ogółem → Byłby to impuls dla całego ekosystemu
- Możliwość umieszczenia większej ilości rzeczy w jednym bloku → Ethereum wiruje szybciej niż Twój blender!
Jak to działa?
Są użytkownicy, przekaźnik (lub więcej przekaźników), który agreguje transakcje i inteligentny kontrakt.
- Użytkownicy, którzy chcą grać w tę grę, wysyłają swój Ether (lub tokeny) do inteligentnego kontraktu podlegającego publicznie audytowi. Dla każdego nowego gracza tworzony jest nowy liść w drzewie Merkle. Liść zawiera informacje o właścicielu Eteru (jego / jego adresie, który jest jednocześnie kluczem publicznym), ilości Ether i nonce (licznik transakcji tego konta, który jest równy 0, gdy liść jest dodawany)
- Kiedy A chce wysłać Ether do B (obaj muszą mieć liść / konto w inteligentnym kontrakcie), A pakuje transakcję, która zawiera adres odkonto, plik do konto, plik nuncjusz konta źródłowego, plik ilość eteru do przeniesienia i podpis transakcji (oczywiście podpisanej kluczem prywatnym konta „od”). Następnie wysyła zapakowaną transakcję do przekaźnika.
- Przekaźnik agreguje wszystkie transakcje otrzymane w danym oknie czasowym (np. Jednej godzinie), aktualizuje drzewo Merkle o nowe kwoty sald i tworzy dowód SNARK, który udowadnia, że wszystkie podpisy i korzeń nowego drzewa Merkle są ważne. W końcu przekaźnik wysyła nowy stan i dowód do inteligentnej umowy.
- Inteligentny kontrakt weryfikuje dowód w łańcuchu. Jeśli jest poprawny, zapisuje korzeń drzewa Merkle stanu New w wewnętrznej pamięci kontraktu.
Zasadniczo korzeń drzewa Merkle przedstawia cały stan wszystkich kont. I nie możesz tego zmienić (= ukraść pieniądze), jeśli nie możesz udowodnić ważności podpisów, których transakcje prowadzą do stanu New podsumowanego przez nowy katalog główny, który przesyłasz.
Krótko mówiąc: użytkownicy mają superszybkie i prawie darmowe transakcje, jak na Coinbase, bez konieczności ufania przekaźnikowi, który nie może nic zrobić, inaczej niż na Coinbase, bez Twojego podpisu.
Jest to łańcuch boczny niezwiązany z opieką, którego stan podsumowuje korzeń drzewa Merkle.
Połączmy to, czego dowiedzieliśmy się powyżej o SNARK-ach, z tym, co właśnie omówiliśmy o skalowaniu. Można to zrobić na różne sposoby. Porównam 2 przepisy: Vitalika wersja i BarryWhiteHat's wersja.
KONFIGURACJĘ wykonuje…
Facet, który rozpoczyna projekt, który tworzy również inteligentny kontrakt. Im bardziej jest to audytowalne, tym lepiej. Powinieneś jej / jemu zaufać… to jest plik zaufana konfiguracja!
Inteligentna umowa oszczędza…
2 Merkle root (wartości bajtów32): pierwsze drzewo zawiera adresy rachunków (podpisy publiczne), drugie salda rachunków i wartości nonces
UDOWODNIENIE jest wykonywane przez…
Przekazujący
Przekaźnik wysyła do inteligentnego kontraktu…
- 2 korzenie Merkle nowego stanu (drzewo adresów i sald + drzewo nonces)
- lista transakcji bez podpisów. „Każda transakcja kosztuje 68 gazu za bajt. Stąd dla zwykłego przelewu możemy oczekiwać, że koszt krańcowy wyniesie 68 * 3 (od) + 68 * 3 (do) + 68 * 1 (opłata) + 68 * 4 + 4 * 2 (kwota) + 68 * 2 (nonce) lub 892 gas ”
SPRAWDZANIE znanych danych wejściowych procesu to…
- 2 korzenie Merkle ze starego stanu
- 2 korzenie Merkle w Nowym stanie
- lista transakcji
PROVING udowadnia, że…
Biorąc pod uwagę,
- 2 korzenie Merkle ze starego stanu (już zapisane w umowie)
- 2 korzenie Merkle New state (wysłane w transakcji aggr.)
- lista transakcji (przesłana w ramach transakcji zbiorczej)
… Przekaźnik ma ważne podpisy umożliwiające przejście ze stanu z 2 starymi korzeniami do stanu z 2 nowymi korzeniami z tymi transakcjami.
WERYFIKACJA jest wykonywana przez…
Inteligentna umowa (zakodowana solidnie, vyper, jak chcesz!)
WERYFIKACJA znane dane wejściowe procesu to…
Te same znane dane wejściowe procesu PROVING, oczywiście…!
Ograniczenia skalowalności
Każda zagregowana transakcja wykorzystuje 650 tys. Gazu do weryfikacji SNARK (łączne koszty) plus ~ 900 gazu koszt marginalny za transakcję (przesyłanie danych kosztuje!). Czyli używając całego bloku przekaźnik może co najwyżej agregować:
co znaczy ~ 544 tx na sekundę
barryWhiteHat's wersja
KONFIGURACJĘ wykonuje…
Facet, który rozpoczyna projekt.
Inteligentna umowa oszczędza…
1 Merkle root z aktualnym stanem. Każdy liść to zaszyfrowany stan konta.
Chcesz Stwórz konto?
state = AccountState (pubkey, balance, nonce)
state.index = self._tree.append (state.hash ())
UDOWODNIENIE jest wykonywane przez…
Przekazujący
Przekaźnik wysyła do inteligentnego kontraktu…
- dowód 𝚷
- katalog główny Merkle w stanie Nowy
- dowód 𝚷
SPRAWDZANIE znanych danych wejściowych procesu to…
- korzeń Merkle ze starego stanu
- katalog główny Merkle w stanie Nowy
PROVING udowadnia, że…
Biorąc pod uwagę,
- korzeń Old Merkle (już zapisany w umowie)
- root New Merkle (senti w transakcji aggr.)
… Przekaźnik ma listę transakcji z prawidłowymi podpisami do przejścia ze stanu ze starym rootem do stanu z nowym rootem
WERYFIKACJA jest wykonywana przez…
Inteligentna umowa (zakodowana solidnie, vyper, jak chcesz!)
WERYFIKACJA znane dane wejściowe procesu to…
Te same znane dane wejściowe procesu PROVING, oczywiście…!
Ograniczenia skalowalności
Przekaźnik nie wysyła danych transakcji do inteligentnego kontraktu (co jest kosztowne), więc limit to w rzeczywistości ilość gazu potrzebna do zweryfikowania dowodu SNARK.
Wspominając Howarda Wu praca o prowadzeniu fazy PROVING SNARK w systemach rozproszonych, barryWhiteHat optymistycznie stwierdza, że możliwe jest potwierdzenie 16666 transakcji w ogromnym SNARK-u (1 miliard ograniczeń!).
barryWhiteHat również myśli można zweryfikować dowód 𝚷 on-chain z gazem 500 tys., co oznacza, że można umieścić 16 SNARK (8 mln / 500 tys.) na blok, czyli ~ 1.07 SNARKs na sekundę… co oznacza ~ 17,832 XNUMX tx na sekundę (16,666 1.07 * XNUMX).
Do nieskończoności i dalej
- Nie wszystko złoto, co się świeci / 1. Ilość mocy obliczeniowej i pamięci potrzebnej w fazie sprawdzania może być dosłownie szokujące. Zwłaszcza w wersji barryWhiteHat, gdzie część złożoności jest odsunięta od łańcucha. pisze Barry „Na laptopie z 7 GB pamięci RAM i 20 GB przestrzeni wymiany ma problemy z zagregowaniem 20 transakcji na sekundę”. Cóż, jeśli celem jest 17,832 XNUMX tx na sekundę… LOL. To wprowadza nietrywialne wyzwania związane z obliczeniami równoległymi. Ale jeśli średni koszt transakcji w USD jest znacznie tańszy niż zwykła opcja bez SNARK-ów… gra jest warta świeczki.
- Nie wszystko złoto, co się świeci / 2. Istnieje istotny problem z dostępnością danych! Ponieważ w kontrakcie zapisywany jest tylko katalog główny drzewa, musisz mieć pewność, że cała wersja drzewa (lub to samo, cała historia transakcji) jest zawsze dostępna. Jeśli dane nie są dostępne, przekaźnik, nawet z ważnymi podpisanymi transakcjami, nie może nic zrobić, ponieważ nie może udowodnić starego stanu → transakcji → nowego stanu.
- Aby przekaźnik był pozbawiony zaufania, a Ether w umowie miał taką samą wartość eterów na zewnątrz (problem z płynnością)… użytkownicy powinni mieć możliwość wypłacania pieniędzy z inteligentnego kontraktu, kiedy chcą, bez polegania na (określonym) przekaźniku. W jaki sposób? To nie jest objęte tym postem 101, ale możesz o tym przeczytać w załączonych linkach.
- Chcesz dowiedzieć się więcej o tym, jak można obsłużyć aktualny stan (adresy, salda i wartości jednorazowe) za pomocą drzewa Merkle? Dodanie liścia, aktualizacja liścia itp.? Sprawdzić tę bibliotekę (plik testowy tutaj), który korzysta z tego instrumentu bazowego moduł. Dzięki HarryR!
- Chcesz skonfigurować swoje osobiste środowisko Ethereum-SNARKs? Zacznijmy od łańcucha z C ++ (konfiguracja, sprawdzanie, weryfikacja) tutaj. Następnie możesz przenieść się do Ethereum (nie zapominaj, że weryfikacja odbywa się tylko na łańcuchu!) Z Zokrates (repoThe dokumentacja na początek).
- Co powiesz na użycie akumulatorów RSA zamiast drzew Merkle? Google „Rsa akumulatory ethereum” zacząć…
Enjoy!
Twitter @marco_derossi
- 7
- Konto
- Wszystkie kategorie
- wśród
- dostępność
- Podstawy
- Miliard
- Etui
- zmiana
- Wykrywanie urządzeń szpiegujących
- coinbase
- computing
- Zgoda
- umowa
- Koszty:
- Aktualny
- Stan aktulany
- DApps
- dane
- zbiór danych
- Decentralizacja
- Wymiary
- Rozproszona księga
- rozproszona technologia księgi
- Środowisko
- Eter
- ethereum
- EU
- EV
- imitacja
- W końcu
- i terminów, a
- Darmowy
- funkcjonować
- gra
- GAS
- GitHub
- Dający
- Złoto
- dobry
- wspaniały
- poprowadzi
- haszysz
- tutaj
- Wysoki
- historia
- W jaki sposób
- hr
- HTTPS
- olbrzymi
- Setki
- ia
- wskaźnik
- Informacja
- IP
- IT
- Praca
- Klawisz
- laptopa
- duży
- prowadzić
- Księga główna
- poziom
- LG
- Biblioteka
- Płynność
- Lista
- Mainstream
- Mapy
- średni
- milion
- Górniczy
- pieniądze
- miesięcy
- Najbardziej popularne posty
- ruch
- Nazwy
- sieć
- węzły
- z naszej
- operacje
- zamówienie
- Inne
- właściciel
- Zapłacić
- Ludzie
- gracz
- Popularny
- power
- prywatny
- Klucz prywatny
- Program
- projekt
- dowód
- dowodzi
- publiczny
- Klucz publiczny
- podsumować
- RSA
- reguły
- bieganie
- "bezpiecznym"
- oszczędność
- Skalowalność
- Skala
- skalowaniem
- nauka
- bezpieczeństwo
- zestaw
- Share
- shared
- Short
- Prosty
- Rozmiar
- spać
- mądry
- inteligentna umowa
- smartphone
- So
- Tworzenie
- solidność
- Rozwiązania
- ROZWIĄZANIA
- Typ przestrzeni
- Spędzanie
- początek
- rozpoczęty
- Stan
- Zjednoczone
- udany
- system
- systemy
- Technologia
- test
- czas
- Żetony
- Top
- potok
- transakcja
- transakcje
- Zaufaj
- Nowości
- Użytkownicy
- wartość
- Weryfikacja
- wiza
- W
- KIM
- słowa
- Praca
- działa
- wartość
- X