Kaj boste potrebovali:
- ozadje računalništva
- osnove Ethereuma
- osnove računanja (optimizacija omejitev)
Kaj boste dobili:
- osnove SNARK brez znanja
- osnove Merklovih dreves
- kako bi lahko Ethereum dosegel na tisoče transakcij na sekundo zahvaljujoč SNARK-om
SNARK-ji omogočajo dokazovalcu, da preveritelju dokaže, da ima rešitev W za problem F s skupnimi/znanimi vhodi X, ne da bi razkril W.
Iskanje rešitve problema bi lahko zahtevalo ogromno računalniške moči in pomnilnika.
Tako je lahko preverjalnik v bistvu 100 % prepričan, da je preverjalnik pravilno deloval (in našel rešitev), pri čemer niti sama ne bi ponovno opravila dela, da bi preverila rešitve, niti rešitve sploh ne pozna. To je čarovnija!
Postopek ima 3 korake:
- NASTAVITI — Problem F (ki ga je treba izraziti kot kvadratni aritmetični program, glej spodaj) je pripravljen za SNARK. Ta proces je zelo pomnilniško in računalniško intenziven, odvisno od kompleksnosti problema (→ število vhodov in omejitev → dimenzija matrike problema zadovoljevanja omejitev). Vse strani morajo zaupati igralcu, ki izvede nastavitev (lahko sam preveritelj), saj se izhod namestitve uporabi v naslednjih fazah. Nastavitev se običajno izvede z uporabo libsnark, knjižnica C++, ki je najbolj priljubljena izvedba za zkSNARK.
- DOKAZA — Preizkuševalec, ki ima rešitev W za problem F s skupnimi vhodi X (morda je porabil/-a ogromno CPE-ja in pomnilnika, da jo je našel!), uporablja libsnark in rezultat Setup faza za ustvarjanje dokaza 𝚷. Ta postopek je vsekakor zelo pomnilniški in računalniško intenziven (odvisno od kompleksnosti problema, kot zgoraj). Velikost izhoda (tj. dokaz 𝚷) je namesto tega jedrnata in konstantna neodvisno od kompleksnosti problema. Preizkuševalec mora zaupati, kdo je izvedel fazo nastavitve, saj ona/on uporablja njen rezultat ...
- PREVERJANJE — Preverjevalnik — daje kot vhod izhod faze nastavitve, skupne vnose X in dokazilo 𝚷 – preverja dokazilo. Če je preverjanje uspešno, je dokazovalcu uspelo dokazati preveritelju, da je našel/našla rešitev W za problem F… brez razkritja W! Lep del je, da ni samo dokaz jedrnat in ima vedno enako dolžino.., postopek preverjanja je hiter in sploh ne zahteva pomnilnika/računalništva. Za razliko od prejšnjih dveh faz…preverjanje lahko preprosto opravite s pametnim telefonom v milisekundah!
Dober povzetek (vir):
Kako se to lahko zgodi? No, to je Merlinova čarovnija! Če želite izvedeti matematiko za tem, začni od tu.
Kako lahko svojo programsko opremo pretvorim v program za kvadratno aritmetiko?
Kot je navedeno zgoraj, mora biti problem F faze nastavitve kvadratni aritmetični program. Pravila igre so stroga:
- Vhodi vaše programske opreme morajo biti številke. Pretvorite svoje stvari (matrike, nize itd.) v števila. To je trivialno.
- "Kvadratno omejen sistem enačb" pomeni:
kjer je x n-dimenzionalni vektor vaših vnosov, m je število omejitev (tj. število enačb vašega sistema), C je n-z-n matrika koeficientov in q je n-dimenzionalni vektor koeficientov. Če ne marate matrike in vektorjev, je tukaj primer n = 3 in m = 2 (3 vhodi, 2 omejitvi):
- Izvedba je aritmetično vezje, kar pomeni, da je rezultat Problem rešen (sistem je rešen, tj. vsi polinomi so enaki 0) oz Problem ni rešen (vsi ostali primeri). Z drugimi besedami: "ti vložki so/niso ena od rešitev tega problema".
- Koeficienti C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 so omejitve sistema. To je v bistvu tisto, kar definira vašo programsko opremo. Spremenite jih ... in dobili boste drugo programsko opremo! Če se vrnemo k delovanju SNARK-jev: C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 so vhodni podatki faze nastavitve. Izhod faze nastavitve (ki jo potrebujete za dokazovanje in preverjanje) je torej strogo povezan s temi C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 in deluje samo za to težavo. Če jih spremenite, definirate drugo programsko opremo/težavo in morate znova zagnati fazo namestitve! x₁, x₂, …, x𝗇 so spremenljivke (tj. kaj morate uganiti, da dobite rešitev sistema). Torej, ko rečemo "Dragi dokazovalnik, ali lahko poiščeš skrivno rešitev W za problem F z deljenimi/javnimi vnosi X", mislimo na primer "Dragi dokazovalnik, ali lahko najdeš vrednosti x₁, x₂, …, x𝗇, ki rešujejo sistem pri čemer je na primer x₇ = 2393, x₅₂₆ = 5647?« Z vsemi x𝗇 lahko počnete, kar želite, razen z x₇ in x₅₂₆, ki sta omejena na skupne/javne vnose.
Življenje je težko, a lahko preživiš ... Če potrebuješ zanke, jih lahko razgrneš tako, da večkrat ponoviš isto operacijo. Če pa potrebujete na primer x₁⁴ x₂⁵, definirate nov vnos x₃ = x₁XNUMX x₂⁵ in uporabite x₃ v svojih omejitvah. Vse je v dodajanju spremenljivk in omejitev ... Celo za precej preprosto programsko opremo je enostavno doseči na stotine milijonov ali milijard vnosov in omejitev!
Želite izvedeti več? Preberi tukaj. In preverite tudi to osnovno code_to_r1cs.py iz ethereuma/raziskave.
Kaj je Merklovo drevo?
Zgoščevalna funkcija je pravilo, ki preslika vnos poljubne velikosti v izhod fiksne velikosti. Lahko bi izumili precej neuporabno zgoščevalno funkcijo »Združi prvi dve z zadnjima dvema črkama«, ki pretvori »Woody Allen« v »Woen« in »Paul McCartney« v »Paey«.
Merklovo drevo je podatkovna struktura, kjer je vsak starš zgoščena vrednost svojih dveh sinov. Na vrhu najdete koren, ki je zgoščena vrednost dveh sinov ravni 1. Na dnu je vsak list zgoščena vrednost zunanjega vnosa.
Uporaba naše izmišljene zgoščevalne funkcije "Woody Allen"→"Woen":
Ko se list spremeni, se sprememba razširi do korenine. Če se spremeni ANTHONY, se spremenijo tudi ANNY (list), CENY in CECO (Koren). Kateri list se spremeni, spremeni se tudi koren.
Za ponovni izračun korena ne potrebujete celotnega drevesa. V našem primeru, če se ANTHONY spremeni in poznate tako JACO kot CECILY, lahko preprosto znova izračunate koren, tudi če popolnoma zanemarite JAMES, MARCO, JAES in MACO. Pri ogromnih drevesih to prihrani veliko časa!
Pa kaj?
Drevesa Merkle so odlična za preverjanje celovitosti podatkov. Običajno: veste, kateri je veljavni koren, in preverite, ali se prejeti podatki ujemajo s tem korenom. Na primer: zaupanja vredna oseba, ki vam ne more dati celotnega nabora podatkov imen ljudi na Zemlji (ni časa, ni pasovne širine ali morda sploh nima podatkov), vam da samo koren (npr. »CECO«). Pogovor: od tisočev nezaupljivih strank prejmete na milijone imen, ki se nanašajo na številko lista. No, ker imate pravilen Root, lahko preverite, na koga se lahko zanesete, kdo vam daje lažne podatke ...
Tudi drevesa Merkle so del vašega življenja! Ko prenašate datoteko Torrent s 3 GB, je vaša datoteka razdeljena na milijone majhnih kosov. Zgoščena vrednost vsakega kosa je shranjena v listu. Ker veste, kateri je veljavni koren drevesa, lahko vsakič, ko nekdo prejmete kos datoteke, preverite, ali je pravilen. Če ni, lahko isti kos zaprosite za koga drugega.
To lahko storite tudi, če še niste prenesli celotnega drevesa/vseh listov: če veste, da je Root CECO in zaupate JACO ... ko prejmete kos ANTHONY, ga lahko preverite, tudi če niste prenesli še kosi MARCO in JAMES.
Zakaj so drevesa Merkle uporabna v tehnologiji porazdeljene knjige je preprosto: protokole soglasja (počasne, drage) uporabljate samo za doseganje soglasja o korenu. Nato lahko vozlišča omrežja, ki jim ni zaupanja, učinkovito in neposredno izmenjujejo podatke ... in lahko varno spijo zahvaljujoč preverjanju integritete s korenom.
Ko je Bog prosil Ethereum, naj izbere 2 velesili med varnostjo, razširljivostjo in decentralizacijo ... je Ethereum žrtvoval razširljivost. Pravzaprav ni stroge omejitve za "transakcije na sekundo": zgornja meja se nanaša na količino plina vsakega bloka - kar je, poenostavljeno, količina operacij, ki jih lahko opravim v vsakem bloku. Ta omejitev je 8 milijonov plina. To lahko pomeni veliko "drobnih" transakcij (brez podatkov, priloženih transakcijam, nobenih operacij, ki jih je treba izvesti na teh podatkih) ali malo velikih transakcij. Odvisno je od vozlišč Ethereum, ki pošiljajo transakcije, in od rudarjev Ethereuma, ki v blok vključijo transakcije, ki plačajo več.
Blok je izkopan vsak ~15 sekund. To pomeni približno 32 milijonov plina na minuto, kar je vsekakor premalo, če želimo, da Ethereumove dapps postanejo mainstream.
Mimogrede: nehaj s tistimi dolgočasnimi primerjavami med Ethereumom in Viso. Centraliziran sistem bo vedno biti hitrejši od Ethereuma ... po zasnovi! Delajo različne stvari in potrebujete jih v različnih situacijah. Če ne potrebujete decentralizacije in okolja brez zaupanja … seveda morate izbrati Viso. V kratkem: dejstvo, da se vaš blender vrti hitreje kot vaš pralni stroj, še ne pomeni, da boste hlače prali v blenderju!
Sestavimo sestavljanko! Predstavljajte si, da bi lahko "stisnili" veliko drobnih transakcij v eno veliko transakcijo zahvaljujoč SNARK-om. Če je plin, porabljen za to veliko transakcijo, manjši od vsote plina, porabljenega za majhne transakcije, to pomeni, da prihranite plin.
In varčevanje s plinom pomeni:
- Uporabniki na splošno porabijo manj za transakcije → To bi bil zagon za celoten ekosistem
- Biti sposoben dati več stvari v blok → Ethereum se vrti hitreje kot vaš mešalnik!
Kako deluje?
Obstajajo uporabniki, posrednik (ali več posrednikov), ki združuje transakcije, in pametna pogodba.
- Uporabniki, ki želijo igrati to igro, pošljejo svoj eter (ali žetone) v javno revidirano pametno pogodbo. Za vsakega novega igralca se ustvari nov list v drevesu Merkle. List vključuje informacije o lastniku etra (njen/njegov naslov, ki je tudi javni ključ), količino etra in nonce (števec transakcij tega računa, ki je 0, ko je list dodan)
- Ko A želi poslati Ether B-ju (oba morata imeti list/račun v pametni pogodbi), A zapakira transakcijo, ki vključuje naslov izračun, do račun, nuncij od iz računa, the znesek etra za prenos in Podpis transakcije (očitno podpisano z zasebnim ključem računa »od«). Nato pošlje zapakirano transakcijo posredovalniku.
- Posrednik združi vse transakcije, prejete v danem časovnem oknu (npr. eno uro), posodobi drevo Merkle z novimi zneski stanj in ustvari dokaz SNARK, ki dokazuje, da so vsi podpisi in koren novega drevesa Merkle veljavni. Posrednik končno pošlje novo stanje in dokaz v pametno pogodbo.
- Pametna pogodba potrjuje Proof on-chain. Če je veljavna, shrani koren drevesa Merkle novega stanja v notranji pomnilnik pogodbe.
V bistvu koren drevesa Merkle prikazuje celotno stanje vseh računov. In ne morete ga spremeniti (= ukrasti denarja), razen če lahko dokažete veljavnost podpisov, katerih transakcije vodijo do novega stanja, povzetega z novim korenom, ki ga pošiljate.
Na kratko: uporabniki imajo super hitre in skoraj brezplačne transakcije, kot na Coinbase, ne da bi morali zaupati posredniku, ki za razliko od Coinbase ne more storiti ničesar brez vašega podpisa.
To je stranska veriga brez skrbništva, katere stanje je povzeto s korenino drevesa Merkle.
Povežimo, kar smo se naučili zgoraj o SNARK-ih, s tem, kar smo pravkar razpravljali o skaliranju. Obstajajo različni načini za to. Primerjal bom 2 recepta: Vitalikov različica in barryja WhiteHata različica.
NASTAVITEV izvede …
Tip, ki začne projekt, ki tudi ustvari pametno pogodbo. Bolj kot ga je mogoče preveriti, tem bolje. Moral bi ji/mu zaupati ... to je a zaupanja vredna namestitev!
Pametna pogodba prihrani ...
2 korena Merkle (vrednosti bytes32): prvo drevo vsebuje naslove računov (javni podpisi), drugo stanje računov in nonce
DOKAZOVANJE izvaja…
Posrednik
Posrednik pošlje pametni pogodbi ...
- 2 korenini Merkle Novega stanja (drevo naslovov in ravnotežja+nonces drevo)
- seznam transakcij, brez podpisov. »Vsaka transakcija stane 68 plinov na bajt. Zato lahko za običajni prenos pričakujemo, da bodo mejni stroški 68 * 3 (od) + 68 * 3 (do) + 68 * 1 (provizija) + 68 * 4 + 4 * 2 (znesek) + 68 * 2 (enkrat) ali 892 plin"
Znani vložki postopka PROVING so ...
- 2 starodržavnih korenin Merkle
- 2 New State Merkle roots
- seznam transakcij
Postopek DOKAZOVANJA dokazuje, da ...
Danes
- 2 stari državni korenini Merkle (že shranjeni v pogodbi)
- 2 New State Merkle roots (poslano v skupni transakciji)
- seznam transakcij (poslan v skupni transakciji)
… ima posrednik veljavne podpise za prehod iz stanja z 2 starima korenoma v stanje z 2 novima korenoma s temi transakcijami.
PREVERJANJE opravi …
Pametna pogodba (kodirana v solidity, vyper, kakor želite!)
Znani vnosi postopka PREVERJANJA so ...
Isti znani vložki postopka PROVING, jasno ...!
Omejitve razširljivosti
Vsaka združena transakcija uporablja 650k plina za preverjanje SNARK (fiksni stroški) plus ~900 plina mejni stroški na transakcijo (Pošiljanje podatkov stane!). Torej z uporabo celotnega bloka lahko posrednik združi največ:
kar pomeni ~544 tx na sekundo
BarryWhiteHat's različica
NASTAVITEV izvede …
Tip, ki začne projekt.
Pametna pogodba prihrani ...
1 koren Merkle s trenutnim stanjem. Vsak list je zgoščeno stanje računa.
Želite ustvarjajo račun?
stanje = Stanje računa (pubkey, stanje, nonce)
state.index = self._tree.append(state.hash())
DOKAZOVANJE izvaja…
Posrednik
Posrednik pošlje pametni pogodbi ...
- dokaz 𝚷
- New State Merkle root
- dokaz 𝚷
Znani vložki postopka PROVING so ...
- starodržavni koren Merkle
- New State Merkle root
Postopek DOKAZOVANJA dokazuje, da ...
Danes
- koren starega Merkla (že shranjen v pogodbi)
- koren New Merkle (senti v agr. transakciji)
… ima posrednik seznam transakcij z veljavnimi podpisi za premik iz stanja s starim korenom v stanje z novim korenom
PREVERJANJE opravi …
Pametna pogodba (kodirana v solidity, vyper, kakor želite!)
Znani vnosi postopka PREVERJANJA so ...
Isti znani vložki postopka PROVING, jasno ...!
Omejitve razširljivosti
Posrednik ne pošilja podatkov o transakcijah v pametno pogodbo (kar je drago), zato je omejitev dejansko količina plina za preverjanje dokazila SNARK.
Če omenimo Howarda Wuja delo o izvajanju SNARK-ove faze PROVING na porazdeljenih sistemih, barryWhiteHat optimistično navaja, da je mogoče potrditi 16666 transakcij v ogromnem SNARK (1 milijarda omejitev!).
tudi barryWhiteHat meni možno je preveriti dokaz 𝚷 v verigi s plinom 500k, kar pomeni, da lahko postavite 16 SNARK-ov (8 milijonov/500k) na blok, kar je ~1.07 SNARKs na sekundo ... kar pomeni ~17,832 tx na sekundo (16,666 * 1.07).
V neskončnost in naprej
- Ni vse zlato, kar se sveti / 1. Količina računalniške moči in pomnilnika, ki ju potrebujete v fazi dokazovanja, je lahko dobesedno šokantna. Še posebej v različici barryWhiteHat, kjer je del zapletenosti premaknjen izven verige. piše barry "Na prenosniku s 7 GB RAM-a in 20 GB prostora za izmenjavo se težko združi 20 transakcij na sekundo". No, če je cilj 17,832 tx na sekundo ... LOL. To uvaja netrivialne izzive vzporednega računanja. Če pa je povprečni strošek $ na transakcijo veliko cenejši od običajne možnosti brez SNARK-ov ... je igra vredna sveče.
- Ni vse zlato, kar se sveti / 2. Obstaja pomembna težava z razpoložljivostjo podatkov! Ker je v pogodbi shranjen samo koren drevesa, morate biti prepričani, da je celotna različica drevesa (ali, kar je enako, celotna zgodovina transakcij) vedno na voljo. Če podatki niso na voljo, posrednik, tudi z veljavno podpisanimi transakcijami, ne more storiti ničesar, ker ne more dokazati Staro stanje → Transakcije → Novo stanje.
- Da bi bil posrednik nezaupljiv in bi imeli Etherji v pogodbi enako vrednost Etherjev zunaj (problem z likvidnostjo) ... bi morali imeti uporabniki možnost dvigniti denar iz pametne pogodbe, kadar želijo, ne da bi se zanašali na (specifičnega) posrednika. kako To ni v okviru tega 101 prispevka, si pa o tem lahko preberete na priloženih povezavah.
- Ali želite izvedeti več o tem, kako je mogoče obravnavati trenutno stanje (naslove, stanja in nonce) z drevesom Merkle? Dodajanje lista, posodabljanje lista itd.? Preveri tej knjižnici (testna datoteka tukaj), ki uporablja to podlago modul. Hvala HarryR!
- Želite nastaviti svoje osebno okolje Ethereum-SNARK? Začnimo zunaj verige s C++ (nastavitev, dokazovanje, preverjanje) tukaj. Nato se lahko premaknete na Ethereum (ne pozabite, samo preverjanje poteka v verigi!) z Zokrates (repoje dokumentacijo za začetek).
- Kaj pa uporaba akumulatorjev RSA namesto dreves Merkle? Google “rsa akumulatorji ethereum” začeti…
Uživajte!
Twitter @marco_derossi
- 7
- Račun
- vsi
- med
- razpoložljivost
- Osnove
- Billion
- primeri
- spremenite
- Pregledi
- coinbase
- računalništvo
- Soglasje
- Naročilo
- stroški
- Trenutna
- Trenutno stanje
- DApps
- datum
- nabor podatkov
- decentralizacija
- Dimenzije
- Distribuirana knjiga
- porazdeljena tehnologija knjige
- okolje
- Eter
- ethereum
- EU
- EV
- ponaredek
- končno
- prva
- brezplačno
- funkcija
- igra
- GAS
- GitHub
- Giving
- Gold
- dobro
- veliko
- vodi
- hash
- tukaj
- visoka
- zgodovina
- Kako
- hr
- HTTPS
- velika
- Stotine
- ia
- Indeks
- Podatki
- IP
- IT
- Job
- Ključne
- laptop
- velika
- vodi
- Ledger
- Stopnja
- LG
- Knjižnica
- likvidnostno
- Seznam
- Mainstream
- Zemljevidi
- srednje
- milijonov
- Rudarji
- Denar
- mesecev
- Najbolj popularni
- premikanje
- Imena
- mreža
- vozlišča
- številke
- operacije
- Da
- Ostalo
- Lastnik
- Plačajte
- ljudje
- predvajalnik
- Popular
- moč
- zasebna
- zasebni ključ
- Program
- Projekt
- dokazilo
- dokazuje
- javnega
- javni ključ
- Rekapitulacija
- RSA
- pravila
- tek
- varna
- shranjevanje
- Prilagodljivost
- Lestvica
- skaliranje
- Znanost
- varnost
- nastavite
- Delite s prijatelji, znanci, družino in partnerji :-)
- deli
- Kratke Hlače
- Enostavno
- Velikosti
- spanje
- pametna
- pametna pogodba
- pametni telefon
- So
- Software
- trdnost
- rešitve
- SOLVE
- Vesolje
- Poraba
- Začetek
- začel
- Država
- Države
- uspešno
- sistem
- sistemi
- Tehnologija
- Test
- čas
- Boni
- vrh
- torrent
- transakcija
- Transakcije
- Zaupajte
- posodobitve
- Uporabniki
- vrednost
- Preverjanje
- Visa
- W
- WHO
- besede
- delo
- deluje
- vredno
- X