Ce veți avea nevoie:
- cunoștințe de informatică
- elementele de bază ale Ethereum
- elementele de bază ale calculului (optimizarea constrângerilor)
Ce veți obține:
- elementele de bază ale SNARK-urilor cu cunoștințe zero
- elementele de bază ale arborilor Merkle
- cum s-ar putea scala Ethereum la mii de tranzacții pe secundă datorită SNARK-urilor
SNARK-urile permit unui doveditor să demonstreze unui verificator că are o soluție W la problema F cu intrări comune/cunoscute X, fără a dezvălui W.
Găsirea soluției la problemă ar putea necesita o cantitate uriașă de putere de calcul și memorie.
Deci, verificatorul poate fi practic 100% sigur că Prover-ul a funcționat corect (și a găsit o soluție), fără să-și refacă treaba singur/el însuși pentru a verifica soluția și nici să cunoască soluția deloc. E magic!
Procesul are 3 etape:
- SETUP — Problema F (care trebuie exprimată ca program aritmetic pătratic, vezi mai jos) este pregătită pentru SNARK. Acest proces necesită o memorie foarte mare și un calcul intensiv în funcție de complexitatea problemei (→ Numărul de intrări și constrângeri → Dimensiunea matricei problemei de satisfacere a constrângerilor). Jucătorul care face Configurarea (ar putea fi Verificatorul însuși) trebuie să aibă încredere de către toate părțile, deoarece rezultatul Configurației este utilizat în fazele următoare. Configurarea se face de obicei folosind libsnark, o bibliotecă C++ care este cea mai populară implementare pentru zkSNARK.
- Dovedind — Proverul, care are o soluție W pentru problema F cu intrări partajate X (poate că a cheltuit cantități uriașe de CPU și memorie pentru a o găsi!), folosește libsnark iar ieșirea lui Configurarea faza de a crea o dovadă 𝚷. Acest proces este cu siguranță mare de memorie și de calcul intensiv (în funcție de complexitatea problemei, ca mai sus). Mărimea rezultatului (adică dovada 𝚷) este în schimb succint și constant, independent de complexitatea problemei. Proverul trebuie să aibă încredere cine a făcut faza de configurare, deoarece folosește rezultatul acesteia...
- VERIFICAREA — Un verificator — dând ca intrare ieșirea fazei de configurare, intrările partajate X și dovada 𝚷 – verifică dovada. Dacă verificarea este reușită, Dovatorul a reușit să demonstreze unui Verificator că a găsit soluția W la problema F... fără a dezvălui W! Partea plăcută este că nu numai că Proof este succint și are întotdeauna aceeași lungime..., procesul de verificare este rapid și nu necesită deloc memorie/calcul. Spre deosebire de cele două faze anterioare... verificarea se poate face cu ușurință cu un smartphone în milisecunde!
O recapitulare bună (sursă):
Cum se poate întâmpla asta? Ei bine, este magia lui Merlin! Dacă vrei să obții matematica din spatele asta, începe de aici.
Cum îmi pot transforma software-ul într-un program de aritmetică pătratică?
După cum am menționat mai sus, problema F a fazei de configurare trebuie să fie un program aritmetic pătratic. Regulile jocului sunt dure:
- Intrările software-ului dvs. ar trebui să fie numere. Transformați lucrurile (matrice, șiruri de caractere etc.) în numere. Asta e banal.
- Un „sistem de ecuații cu restricții pătratice” înseamnă:
unde x este vectorul n-dimensional al intrărilor dvs., m este numărul de constrângeri (adică numărul de ecuații ale sistemului dvs.), C este matricea de n-cu-n coeficienți și q este un vector de coeficienți n-dimensional. Dacă nu vă plac matricea și vectorii, iată cazul n = 3 și m = 2 (3 intrări, 2 constrângeri):
- Implementarea este un circuit aritmetic, ceea ce înseamnă că rezultatul este Problema rezolvata (sistemul este rezolvat, adică toate polinoamele sunt egale cu 0) sau Problema nerezolvată (toate celelalte cazuri). Cu alte cuvinte: „aceste intrări sunt/nu sunt una dintre soluțiile la această problemă”.
- Coeficienții C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 sunt constrângerile sistemului. Acesta este practic ceea ce definește software-ul tău. Schimbați-le... și veți primi un alt software! Revenind la modul în care funcționează SNARK-urile: C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 sunt intrarea fazei de configurare. Ieșirea fazei de configurare (de care aveți nevoie pentru demonstrare și verificare) este, prin urmare, strict legată de acele C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 și funcționează numai pentru acea problemă. Dacă le schimbați, definiți un alt software/problemă și trebuie să rulați din nou faza de configurare! x₁, x₂, …, x𝗇 sunt variabilele (adică ceea ce trebuie să ghiciți pentru a obține soluția unui sistem). Așadar, când spunem „Stimate doveditor, ai putea te rog să găsești o soluție secretă W pentru problema F cu intrări partajate/publice X” ne referim, de exemplu, „Dragă demonstrator, poți găsi valorile x₁, x₂, …, x𝗇 care rezolvă sistemul cu, de exemplu, x₇ = 2393, x₅₂₆ = 5647?” Puteți face ceea ce doriți cu toate x𝗇, cu excepția x₇ și x₅₂₆, care sunt limitate la intrările partajate/publice.
Este o viață grea, dar poți supraviețui... Dacă ai nevoie de bucle, le poți desfășura repetând aceeași operațiune de mai multe ori. Sau dacă aveți nevoie, de exemplu, de x₁⁴ x₂⁵, definiți o nouă intrare x₃ = x₁⁴ x₂⁵ și utilizați x₃ în constrângerile dvs. Totul este să adăugați variabile și constrângeri... Chiar și pentru software-uri destul de simple, este ușor să ajungeți la sute de milioane sau miliarde de intrări și constrângeri!
Vrei să afli mai multe? Citit aici. Și, de asemenea, verificați acest element de bază code_to_r1cs.py din ethereum/cercetare.
Ce este un copac Merkle?
O funcție hash este o regulă care mapează o intrare de dimensiune arbitrară la o ieșire de dimensiune fixă. Am putea inventa o funcție hash destul de inutilă „Concatenează primele două cu ultimele două litere” care transformă „Woody Allen” în „Woen” și „Paul McCartney” în „Paey”.
Un arbore Merkle este o structură de date în care fiecare părinte este hash-ul celor doi fii ai săi. În partea de sus găsiți Rădăcina, care este hash-ul celor doi fii ai nivelului 1. În partea de jos, fiecare frunză este hash-ul unei intrări externe.
Folosind funcția hash „Woody Allen” → „Woen”:
Când o frunză se schimbă, modificarea este propagată până la rădăcină. Dacă ANTHONY se schimbă, se schimbă și ANNY (frunză), CENY și CECO (rădăcină). Oricare se schimbă frunza, se schimbă și rădăcina.
Nu aveți nevoie de întregul arbore pentru a recalcula Rădăcina. În exemplul nostru, dacă ANTHONY se schimbă și cunoști atât JACO, cât și CECILY, poți recalcula cu ușurință Rădăcina chiar dacă ignori complet JAMES, MARCO, JAES și MACO. Pentru copacii uriași, acest lucru economisește mult timp!
Deci, ce?
Arborii Merkle sunt grozavi pentru verificările integrității datelor. De obicei: știi care este rădăcina validă și verifici dacă datele primite se potrivesc cu acea rădăcină. De exemplu: o parte de încredere care nu vă poate oferi întregul set de date cu prenumele oamenilor de pe Pământ (fără timp, fără lățime de bandă sau poate că nu are deloc datele) vă oferă doar rădăcina (de ex. „CECO”). Postfață: primești milioane de prenume, cu referire la numărul foii, de la mii de părți neîncrezătoare. Ei bine, din moment ce aveți rădăcina corectă, puteți verifica pe cine vă puteți baza, cine vă oferă date false...
Copacii Merkle fac și parte din viața ta! Când descărcați un fișier Torrent de 3 GB, fișierul dvs. este împărțit în milioane de bucăți mici. Hașul fiecărei bucăți este depozitat într-o frunză. Deoarece știți care este rădăcina validă a arborelui, de fiecare dată când primiți o bucată din fișier de către cineva, puteți verifica dacă este corect. Dacă nu este, puteți cere aceeași bucată altcuiva.
Poți face asta chiar dacă nu ai descărcat încă întregul arbore/toate frunzele: dacă știi că Rădăcina este CECO și ai încredere în JACO… când primești bucățica ANTHONY poți să o verifici chiar dacă nu ai descărcat totuși bucățile MARCO și JAMES.
De ce arborii Merkle sunt utili în tehnologia registrului distribuit este simplu: utilizați protocoale de consens (lent, costisitor) doar pentru a ajunge la un consens asupra rădăcinii. Apoi nodurile de încredere ale rețelei pot partaja eficient și direct date... și pot dormi în siguranță datorită verificărilor de integritate cu Root.
Când Dumnezeu i-a cerut lui Ethereum să aleagă 2 superputeri dintre Securitate, Scalabilitate și Descentralizare... Ethereum a sacrificat Scalabilitatea. De fapt, nu există un plafon puternic pentru „tranzacțiile pe secundă”: plafonul se referă la cantitatea de gaz din fiecare bloc - și anume, simplificând, cantitatea de operațiuni pe care le pot face în fiecare bloc. Această limită este de 8 milioane de gaz. Asta ar putea însemna multe tranzacții „minute” (nicio date atașate la tranzacții, nicio operațiune care să fie executată pe acele date) sau puține tranzacții mari. Depinde de nodurile Ethereum, care depun tranzacții, și de minerii Ethereum, care includ în bloc tranzacțiile care plătesc mai mult.
Un bloc este minat fiecare ~15 secunde. Asta înseamnă ~ 32 de milioane de gaz pe minut, ceea ce cu siguranță nu este suficient dacă dorim ca aplicațiile Ethereum să devină mainstream.
Apropo: încetează cu acele comparații plictisitoare dintre Ethereum și Visa. Un sistem centralizat va mereu fii mai rapid decât Ethereum... prin design! Ei fac lucruri diferite și ai nevoie de ele în diferite situații. Dacă nu aveți nevoie de descentralizare și de un mediu fără încredere... bineînțeles că ar trebui să alegeți Visa. În scurt: Faptul ca blenderul tau se invarte mai repede decat masina ta de spalat nu inseamna ca iti vei curata pantalonii intr-un blender!
Să punem puzzle-ul împreună! Imaginați-vă că puteți „comprima” multe tranzacții mici într-o singură tranzacție mare datorită SNARK-urilor. Dacă gazul cheltuit prin această tranzacție mare este mai mic decât suma gazului cheltuit prin tranzacțiile mici, înseamnă că economisiți gaz.
Și economisirea gazelor înseamnă:
- Utilizatorii cheltuiesc mai puțin pentru tranzacții în general → Aceasta ar fi un impuls pentru întregul ecosistem
- A fi capabil să pună mai multe lucruri într-un bloc → Ethereum se învârte mai repede decât blenderul tău!
Cum functioneaza?
Există utilizatori, un relee (sau mai multe releere) care agregă tranzacții și un contract inteligent.
- Utilizatorii care doresc să joace acest joc își trimit Ether-ul (sau jetoanele) la un contract inteligent auditat public. Pentru fiecare jucător nou este creată o nouă frunză într-un arbore Merkle. Frunza include informații despre proprietarul Etherului (adresa ei, care este și cheia publică), cantitatea de Ether și nonce (contorul de tranzacții al acelui cont, care este 0 când se adaugă frunza)
- Când A vrea să trimită Ether către B (amândoi trebuie să aibă o frunză/un cont în contractul inteligent), A împachetează o tranzacție, care include adresa dincont, la cont, nunțiu din contul de la sumă de Eter care urmează să fie transferat și semnătură a tranzacției (semnată cu cheia privată a contului „de la”, evident). Ea/ea trimite apoi tranzacția împachetată către relayer.
- Releerul adună toate tranzacțiile primite într-o fereastră de timp dată (de ex. o oră), actualizează arborele Merkle cu sumele noilor solduri și creează o dovadă SNARK care demonstrează că toate semnăturile și rădăcina noului arbore Merkle sunt valide. Releerul trimite în sfârșit noua stare și dovada către contractul inteligent.
- Contractul inteligent validează Proof în lanț. Dacă este valid, salvează rădăcina arborelui Merkle a stării New în memoria internă a contractului.
Practic, rădăcina arborelui Merkle descrie întreaga stare a tuturor conturilor. Și nu-l poți schimba (= fura bani) decât dacă poți dovedi validitatea semnăturilor ale căror tranzacții duc la starea Nouă rezumată de noua rădăcină pe care o trimiți.
Pe scurt: utilizatorii au tranzacții super rapide și aproape gratuite, ca pe Coinbase, fără a avea nevoie să aibă încredere în relayer, care nu poate face nimic, spre deosebire de Coinbase, fără semnătura ta.
Este un lanț lateral fără custodie a cărui stare este rezumată de o rădăcină de arbore Merkle.
Să conectăm ceea ce am învățat mai sus despre SNARK-uri cu ceea ce tocmai am discutat despre scalare. Există diferite moduri de a face asta. Voi compara 2 retete: Vitalik's versiune și a lui BarryWhiteHat versiune.
SETUP se face de...
Tipul care începe proiectul, care creează și contractul inteligent. Cu cât este mai auditabil, cu atât mai bine. Ar trebui să ai încredere în ea/el... este a configurare de încredere!
Contractul inteligent salvează...
2 rădăcini Merkle (valori bytes32): primul arbore conține adresele conturilor (semnături publice), al doilea solduri și non-uri ale conturilor
DOVAREA se face de...
Releerul
Releerul trimite la contractul inteligent...
- cele 2 rădăcini Merkle ale Noului stat (se adresează arborelui și arborelui soldurilor + arborelui noces)
- lista tranzacțiilor, fără semnături. „Fiecare tranzacție costă 68 de gaze pe octet. Prin urmare, pentru un transfer obișnuit, ne putem aștepta ca costul marginal să fie 68 * 3 (de la) + 68 * 3 (până la) + 68 * 1 (taxă) + 68 * 4 + 4 * 2 (sumă) + 68 * 2 (nu o dată), sau 892 de gaz”
Intrările cunoscute ale procesului PROVING sunt...
- cele 2 rădăcini Merkle de stat vechi
- cele 2 rădăcini Merkle New State
- lista de tranzactii
Procesul PROVING demonstrează că...
Dat
- cele 2 rădăcini Merkle de stat vechi (deja stocate în contract)
- cele 2 rădăcini Merkle de stare nouă (trimise în tranzacția agr.)
- lista de tranzacții (trimisă în tranzacția agr.)
… Releerul are semnături valide pentru a trece de la statul cu 2 rădăcini vechi la un stat cu 2 rădăcini noi cu acele tranzacții.
VERIFICAREA se face de...
Contractul inteligent (codat în soliditate, vyper, după cum doriți!)
VERIFICAREA intrărilor cunoscute ale procesului sunt...
Același proces PROVING a cunoscut intrările, în mod clar...!
Limite ale scalabilității
Fiecare tranzacție agregată utilizează 650k gaz pentru verificarea SNARK (Costul fix) plus ~900 gaz de costul marginal pe tranzacție (Costă trimiterea datelor!). Deci, folosind întregul bloc, releul poate agrega cel mult:
care înseamnă ~544 tx pe secundă
barryWhiteHat's versiune
SETUP se face de...
Tipul care începe proiectul.
Contractul inteligent salvează...
1 rădăcină Merkle cu starea curentă. Fiecare frunză este starea hashing a unui cont.
Vrei sa crea un cont?
stat = AccountState(cheie pub, sold, nonce)
state.index = self._tree.append(state.hash())
DOVAREA se face de...
Releerul
Releerul trimite la contractul inteligent...
- dovada 𝚷
- rădăcina Merkle New State
- dovada 𝚷
Intrările cunoscute ale procesului PROVING sunt...
- rădăcina Merkle de stat vechi
- rădăcina Merkle New State
Procesul PROVING demonstrează că...
Dat
- rădăcina Old Merkle (deja stocată în contract)
- rădăcina New Merkle (senti în tranzacția agr.)
… relaerul are o listă de tranzacții cu semnături valide pentru a trece de la starea cu rădăcină veche la starea cu rădăcină nouă
VERIFICAREA se face de...
Contractul inteligent (codat în soliditate, vyper, după cum doriți!)
VERIFICAREA intrărilor cunoscute ale procesului sunt...
Același proces PROVING a cunoscut intrările, în mod clar...!
Limite ale scalabilității
Releerul nu trimite datele tranzacțiilor către contractul inteligent (care este costisitor), așa că limita este de fapt cantitatea de gaz pentru a verifica dovada SNARK.
Menționând-o pe Howard Wu muncă despre rularea fazei PROVING a SNARK pe sisteme distribuite, barryWhiteHat optimist afirmă că este posibil să se confirme 16666 de tranzacții într-un SNARK uriaș (constrângeri de 1 miliard!).
barryWhiteHat, de asemenea crede este posibil să verificați dovada 𝚷 în lanț cu 500k gaz, ceea ce înseamnă că puteți pune 16 SNARK-uri (8 milioane/500k) pe bloc, ceea ce este ~1.07 SNARK-uri pe secundă... ceea ce înseamnă ~17,832 tx pe secundă (16,666 * 1.07).
La infinit și dincolo de
- Tot ceea ce strălucește nu este aur / 1. Cantitatea de putere de calcul și memorie de care aveți nevoie în faza de Proving poate fi literalmente șocantă. Mai ales în versiunea lui barryWhiteHat, unde o parte a complexității este mutată în afara lanțului. scrie barry „Pe un laptop cu 7 GB de memorie RAM și 20 GB de spațiu de schimb, se luptă să cumpere 20 de tranzacții pe secundă”. Ei bine, dacă obiectivul este 17,832 tx pe secundă... LOL. Acest lucru introduce provocări non-triviale de calcul paralel. Dar dacă costul mediu în dolari pe tranzacție este mult mai ieftin decât opțiunea obișnuită fără SNARK... jocul merită lumânarea.
- Tot ce strălucește nu este aur / 2. Există o problemă relevantă privind disponibilitatea datelor! Deoarece doar rădăcina arborelui este salvată în contract, trebuie să fii sigur că o versiune întreagă a arborelui (sau, la fel, întregul istoric al tranzacțiilor) este întotdeauna disponibilă. Dacă datele nu sunt disponibile, relatorul, chiar și cu tranzacții valide semnate, nu poate face nimic pentru că nu poate dovedi starea veche → tranzacții → stare nouă.
- Pentru ca relaerul să nu aibă încredere și Etherii din contract să aibă aceeași valoare a Etherilor în afara (problema de lichiditate)... utilizatorii ar trebui să poată retrage bani din contractul inteligent atunci când doresc, fără a se baza pe un releer (specific). Cum? Acest lucru nu intră în domeniul de aplicare al acestei postări 101, dar puteți citi despre acest lucru în linkurile atașate.
- Doriți să înțelegeți mai multe despre cum poate fi gestionat statul actual (adrese, solduri și non-uri) cu un arbore Merkle? Adăugarea unei frunze, actualizarea unei frunze etc? Verifică această bibliotecă (fișier de test aici) care utilizează acest suport modul. Mulțumesc HarryR!
- Doriți să vă configurați mediul personal Ethereum-SNARKs? Să începem în afara lanțului cu C++ (Configurare, Demonstrare, Verificare) aici. Apoi te poți muta la Ethereum (nu uita, doar Verificarea se face în lanț!) cu Zokrates (repo, documentație pentru a începe).
- Ce zici de a folosi acumulatori RSA în loc de arbori Merkle? Google „acumulatoare rsa ethereum” a începe…
Bucurați-vă!
Twitter @marco_derossi
- 7
- Cont
- TOATE
- printre
- disponibilitate
- Noțiuni de bază
- Miliard
- cazuri
- Schimbare
- Verificări
- coinbase
- tehnica de calcul
- Consens
- contract
- Cheltuieli
- Curent
- Starea curenta
- DApps
- de date
- set de date
- Descentralizare
- Dimensiune
- Ledger distribuit
- tehnologie distribuită
- Mediu inconjurator
- Eter
- ethereum
- EU
- EV
- fals
- În cele din urmă
- First
- Gratuit
- funcţie
- joc
- GAS
- GitHub
- Oferirea
- Aur
- bine
- mare
- ghida
- hașiș
- aici
- Înalt
- istorie
- Cum
- hr
- HTTPS
- mare
- sute
- ia
- index
- informații
- IP
- IT
- Loc de munca
- Cheie
- laptop
- mare
- conduce
- carte mare
- Nivel
- LG
- Bibliotecă
- Lichiditate
- Listă
- Mainstream
- Harta
- mediu
- milion
- minerii
- bani
- luni
- Cel mai popular
- muta
- nume
- reţea
- noduri
- numere
- Operațiuni
- comandă
- Altele
- proprietar
- Plătește
- oameni
- player
- Popular
- putere
- privat
- cheie privată
- Program
- proiect
- dovadă
- dovedește
- public
- Cheia publică
- recapitula
- rsa
- norme
- funcţionare
- sigur
- economisire
- scalabilitate
- Scară
- scalare
- Ştiinţă
- securitate
- set
- Distribuie
- comun
- Pantaloni scurți
- simplu
- Mărimea
- dormi
- inteligent
- contract inteligent
- smartphone
- So
- Software
- soliditate
- soluţii
- REZOLVAREA
- Spaţiu
- Cheltuire
- Începe
- început
- Stat
- Statele
- de succes
- sistem
- sisteme
- Tehnologia
- test
- timp
- indicativele
- top
- Torent
- tranzacție
- Tranzacții
- Încredere
- actualizări
- utilizatorii
- valoare
- Verificare
- are drept scop
- W
- OMS
- cuvinte
- Apartamente
- fabrică
- valoare
- X