A kezdő útmutató, amit szerettem volna néhány hónappal ezelőtt, mielőtt beleástam volna ezt a cuccot
Amire szüksége lesz:
- informatikai háttérrel
- az Ethereum alapjai
- a számítás alapjai (korlátok optimalizálása)
Mit kapsz:
- a nulla tudású SNARK-ok alapjai
- a Merkle fák alapjai
- hogyan tudná az Ethereum több ezer tranzakcióra skálázni másodpercenként a SNARK-oknak köszönhetően
A SNARK-ok lehetővé teszik a bizonyító számára, hogy bebizonyítsa az ellenőrzőnek, hogy van W megoldása az F problémára X megosztott/ismert bemenetekkel anélkül, hogy W felfedné.
A probléma megoldásának megtalálása hatalmas számítási teljesítményt és memóriát igényelhet.
Tehát a Verifier alapvetően 100%-ig biztos lehet benne, hogy a Prover megfelelően működött (és megtalálta a megoldást), úgy, hogy sem saját maga nem végzi el újra a munkát, hogy ellenőrizze a megoldást, és egyáltalán nem ismeri a megoldást. Ez varázslat!
A folyamat 3 lépésből áll:
- BEÁLLÍT — Az F feladat (amelyet másodfokú aritmetikai programmal kell kifejezni, lásd alább) a SNARK-okhoz készült. Ez a folyamat a probléma összetettségétől függően igen nagy memória- és számításigényes (→ A bemenetek és megszorítások száma → A megkötések kielégítési problémájának mátrixának dimenziója). A beállítást végző játékosban (lehet maga a Verifier) minden félnek megbíznia kell, mivel a beállítás kimenete a következő fázisokban kerül felhasználásra. A beállítás általában a segítségével történik libsnark, egy C++ könyvtár, amely a zkSNARK-ok legnépszerűbb megvalósítása.
- BIZONYÍTÁS – A Prover, akinek van egy W megoldása az F problémára X megosztott bemenetekkel (talán hatalmas mennyiségű CPU-t és memóriát költött, hogy megtalálja!), használja libsnark és a kimenete a felépítés fázisban a bizonyíték létrehozásához 𝚷. Ez a folyamat határozottan nagy memória- és számításigényes (a probléma összetettségétől függően, mint fent). A kimenet mérete (azaz bizonyíték 𝚷) ehelyett tömör és állandó, függetlenül a probléma összetettségétől. A Provernek bíznia kell abban, hogy ki végezte el a beállítási fázist, mivel ő használja a kimenetet…
- ELLENŐRZÉS — Egy ellenőrző – a beállítási fázis kimenetét, a megosztott X bemeneteket és a bizonyítást 𝚷 adja be bemenetként – ellenőrzi a bizonyítást. Ha a hitelesítés sikeres, a bizonyítónak sikerült bebizonyítania egy Ellenőrzőnek, hogy megtalálta a W megoldást az F… problémára anélkül, hogy felfedte volna W-t! Az a szép, hogy nem csak a Proof tömör és mindig egyforma hosszúságú..., hanem az ellenőrzési folyamat gyors és egyáltalán nem memória-/számításigényes. Ellentétben az előző két fázissal… az ellenőrzés egyszerűen, ezredmásodpercek alatt elvégezhető okostelefonnal!
Egy jó összefoglaló (forrás):
Hogyan történhet ez meg? Nos, ez Merlin varázslat! Ha a matematikát szeretnéd e mögött, innen indul.
Hogyan alakíthatom át a szoftveremet másodfokú aritmetikai programmá?
Ahogy fentebb említettük, a beállítási fázis F feladatának másodfokú aritmetikai programnak kell lennie. A játékszabályok szigorúak:
- A szoftver bemeneteinek számoknak kell lenniük. Alakítsa át dolgait (tömbök, karakterláncok stb.) számokká. Ez triviális.
- A „másodfokú egyenletrendszer” jelentése:
ahol x az Ön bemeneteinek n-dimenziós vektora, m a megszorítások száma (azaz a rendszer egyenleteinek száma), C az n-szer-együttható Mátrix és q egy n-dimenziós együtthatóvektor. Ha nem szereti a mátrixot és a vektorokat, itt van az n = 3 és m = 2 eset (3 bemenet, 2 megkötés):
- A megvalósítás egy aritmetikai áramkör, ami azt jelenti, hogy az eredmény az Probléma megoldódott (a rendszer meg van oldva, azaz minden polinom egyenlő 0-val) ill A probléma nem oldódott meg (az összes többi eset). Más szóval: „ezek a bemenetek a probléma megoldásai közé tartoznak/nem jelentenek”.
- A C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 együtthatók a rendszer kényszerei. Alapvetően ez határozza meg a szoftvert. Változtassa meg őket… és kap egy másik szoftvert! Visszatérve a SNARK-ok működésére: C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 a beállítási fázis bemenete. A beállítási fázis kimenete (amelyre szüksége van a bizonyításhoz és ellenőrzéshez) ezért szigorúan kapcsolódik a C₁, C₂, …, C𝚖, q₁, q₂, …, q🖤, és csak erre a problémára vonatkozik. Ha megváltoztatja őket, akkor egy másik szoftvert/problémát határoz meg, és újra kell futtatnia a telepítési fázist! x₁, x₂, …, x𝗇 a változók (azaz mit kell kitalálni egy rendszer megoldásához). Tehát amikor azt mondjuk, hogy „Kedves Prover, találna egy titkos megoldást W az F problémára megosztott/nyilvános X bemenetekkel”, akkor például „Kedves Prover, meg tudja találni azokat az x₁, x₂, …, x𝗇 értékeket, amelyek megoldják a rendszert ahol például x₇ = 2393, x₅₂₆ = 5647?” Azt csinálsz, amit akarsz az összes x₇-al, kivéve az x₇ és x₅₂₆ esetén, amelyek a megosztott/nyilvános bemenetekre vannak korlátozva.
Nehéz élet ez, de túl lehet élni… Ha hurkokra van szüksége, kibonthatja őket, többször megismételve ugyanazt a műveletet. Vagy ha például x1⁴ x₂⁵-ra van szüksége, akkor adjon meg egy új bemenetet, x₃ = x1⁴ x₂⁵, és használja az x3-at a megszorításokban. Az egész arról szól, hogy változókat és megszorításokat adjunk hozzá… Még a nagyon egyszerű szoftvereknél is könnyen elérhető több száz millió vagy milliárdnyi bemenet és korlát!
Többet szeretne tudni? Olvas itt. És nézd meg ezt az alapszintet is code_to_r1cs.py ethereumból/kutatásból.
Mi az a Merkle-fa?
A hash függvény egy olyan szabály, amely egy tetszőleges méretű bemenetet leképez egy rögzített méretű kimenetre. Feltalálhatnánk egy meglehetősen haszontalan hash-függvényt: „Össze össze az első kettőt az utolsó két betűvel”, amely a „Woody Allen”-t „Woen”-re, a „Paul McCartney”-t pedig „Paey”-re alakítja.
A Merkle-fa egy olyan adatstruktúra, amelyben minden szülő a két fia hash-je. A tetején található a Root, amely az 1. szint két fiának hashje. Alul minden levél egy külső bemenet hash-je.
A kitalált „Woody Allen” → „Woen” hash függvény segítségével:
Amikor egy levél megváltozik, a módosítás a gyökérig terjed. Ha az ANTHONY megváltozik, az ANNY (levél), a CENY és a CECO (gyökér) is megváltozik. Bármelyik levél megváltozik, a gyökér is megváltozik.
Nincs szükség a teljes fára a gyökér újraszámításához. Példánkban, ha ANTHONY megváltozik, és ismeri mind a JACO-t, mind a CECILY-t, akkor könnyen újraszámolhatja a gyökeret, még akkor is, ha teljesen figyelmen kívül hagyja JAMES-t, MARCO-t, JAES-t és MACO-t. Hatalmas fák esetén ez sok időt takarít meg!
És akkor mi van?
A Merkle fák kiválóan alkalmasak az adatok integritásának ellenőrzésére. Általában: tudja, melyik az érvényes Root, és ellenőrzi, hogy a kapott adatok egyeznek-e a Roottal. Például: egy megbízható fél, aki nem tudja megadni a Földön élő emberek keresztnevének teljes adatkészletét (nincs ideje, nincs sávszélessége, vagy esetleg egyáltalán nem rendelkezik adatokkal), csak a gyökeret adja meg (pl. „CECO”). Utószó: több millió keresztnevet kapsz, a levélszámra hivatkozva, több ezer megbízhatatlan féltől. Nos, mivel a megfelelő gyökérrel rendelkezik, ellenőrizheti, kire számíthat, ki ad meg hamis adatokat…
A Merkle fák is az életed részei! Amikor egy 3 GB-os Torrent fájlt tölt le, a fájl milliónyi kis darabra van felosztva. Minden darab hash-je egy levélben van tárolva. Mivel tudja, melyik a fa érvényes gyökere, minden alkalommal, amikor valakitől megkapja a fájl egy darabját, ellenőrizheti, hogy helyes-e. Ha nem, akkor megkérdezheti valaki mástól ugyanazt a részt.
Ezt akkor is megteheti, ha még nem töltötte le a teljes fát/az összes levelet: ha tudja, hogy a gyökér CECO, és megbízik a JACO-ban… amikor megkapja a darabot ANTHONY, akkor is ellenőrizheti, hogy még nem töltötte le mégis a darabok MARCO és JAMES.
Hogy miért hasznosak a Merkle fák az elosztott főkönyvi technológiában, az egyértelmű: a konszenzusprotokollokat (lassú, drága) csak a gyökérről való konszenzus eléréséhez használod. Ekkor a hálózat nem megbízható csomópontjai hatékonyan és közvetlenül megoszthatják az adatokat… és a gyökér integritás-ellenőrzéseinek köszönhetően épségben alhatnak.
Amikor Isten arra kérte az Ethereumot, hogy válasszon két szuperképességet a biztonság, a méretezhetőség és a decentralizáció közül… az Ethereum feláldozta a méretezhetőséget. Valójában nincs szigorú korlát a „másodpercenkénti tranzakciók” tekintetében: a felső határ az egyes blokkok gázmennyiségére vonatkozik – ami leegyszerűsítve azt jelenti, hogy az egyes blokkokban végrehajtható műveletek mennyisége. Ez a határ 2 millió gáz. Ez sok „apró” tranzakciót jelenthet (nincs adat csatolva a tranzakciókhoz, nem kell műveleteket végrehajtani azokon az adatokon) vagy néhány nagy tranzakciót. Ez az Ethereum csomópontjain múlik, amelyek tranzakciókat küldenek, és az Ethereum bányászaira, akik a blokkba foglalják azokat a tranzakciókat, amelyek többet fizetnek.
Egy blokkot bányásztak minden ~15 másodperc. Ez percenként ~32 millió gázt jelent, ami határozottan nem elég, ha azt akarjuk, hogy az Ethereum dappjai a mainstreambe kerüljenek.
Apropó: hagyja abba az unalmas összehasonlítást az Ethereum és a Visa között. Egy központosított rendszer lesz mindig Legyen gyorsabb, mint az Ethereum… tervezésileg! Különböző dolgokat csinálnak, és különböző helyzetekben van rájuk szüksége. Ha nincs szüksége decentralizációra és bizalommentes környezetre… természetesen a Visat válassza. Röviden: az, hogy a turmixgéped gyorsabban pörög, mint a mosógéped, nem jelenti azt, hogy turmixgépben fogod tisztítani a nadrágodat!
Rakjuk össze a puzzle-t! Képzelje el, hogy a SNARK-oknak köszönhetően sok apró tranzakciót egyetlen nagy tranzakcióba tömöríthet. Ha a nagy tranzakció során elköltött gáz kevesebb, mint az apró tranzakciók által elköltött gáz összege, az azt jelenti, hogy gázt takarít meg.
A gázmegtakarítás pedig azt jelenti:
- A felhasználók összességében kevesebbet költenek tranzakciókra → Ez az egész ökoszisztéma számára lökést jelentene
- Több cuccot tehetsz egy blokkba → Az Ethereum gyorsabban pörög, mint a turmixgéped!
Hogyan működik?
Vannak felhasználók, egy közvetítő (vagy több közvetítő), amely összesíti a tranzakciókat, és egy intelligens szerződés.
- Azok a felhasználók, akik hajlandóak játszani ezzel a játékkal, elküldik Etherüket (vagy tokeneiket) egy nyilvánosan ellenőrzött intelligens szerződésnek. Minden új játékos számára egy új levél jön létre a Merkle-fán. A levél információkat tartalmaz az Ether tulajdonosáról (címe, amely egyben a nyilvános kulcs is), az Ether mennyiségéről és a nonce-ről (az adott számla tranzakciószámlálója, amely 0 a levél hozzáadásakor)
- Amikor A Ethert akar küldeni B-nek (mindkettőjüknek levéllel/számlával kell rendelkeznie az intelligens szerződésben), A csomagol egy tranzakciót, amely tartalmazza a ból bőlszámla, a nak nek számla, a pápai követ a fiókból, a összeg Az átadandó éter és a aláírás a tranzakció (nyilvánvalóan a „feladó” fiók privát kulcsával aláírva). Ezután elküldi a csomagolt tranzakciót a közvetítőnek.
- A közvetítő összesíti az összes beérkezett tranzakciót egy adott időablakban (pl. egy óra), frissíti a Merkle fát az új egyenlegek összegével, és létrehoz egy SNARK igazolást, amely igazolja, hogy minden aláírás és az új Merkle fa gyökere érvényes. A közvetítő végül elküldi az új állapotot és a bizonyítékot az intelligens szerződésnek.
- Az intelligens szerződés érvényesíti a Proof on-chain-et. Ha érvényes, elmenti az Új állapot Merkle-fa gyökerét a szerződés belső memóriájába.
Alapvetően a Merkle-fa gyökere az összes fiók teljes állapotát ábrázolja. És nem tudod megváltoztatni (=pénzt lopni), hacsak nem tudod igazolni azoknak az aláírásoknak az érvényességét, amelyek tranzakciói a beküldött új gyökér által összefoglalt Új állapothoz vezetnek.
Dióhéjban: a felhasználók szupergyors és szinte ingyenes tranzakciókat hajthatnak végre, mint például a Coinbase-en, anélkül, hogy megbízniuk kellene a közvetítőben, aki a Coinbase-szal ellentétben nem tud semmit tenni az Ön aláírása nélkül.
Ez egy nem őrizetes oldallánc, amelynek állapotát egy Merkle-fa gyökér foglalja össze.
Kapcsoljuk össze a SNARK-okról fentebb tanultakat az imént a skálázásról tárgyaltakkal. Ennek különböző módjai vannak. Összehasonlítok 2 receptet: Vitalik receptjét változat és BarryWhiteHat változat.
A BEÁLLÍTÁST a…
A srác, aki elindítja a projektet, aki megalkotja az okosszerződést is. Minél jobban ellenőrizhető, annál jobb. Bíznia kell benne… ez a megbízható beállítás!
Az okos szerződés megmenti…
2 Merkle gyökér (bytes32 értékek): az első fa a számlák címeit (nyilvános aláírásokat), a második számlaegyenlegeket és nonces-eket tartalmazza
A BIZONYÍTÁST a…
A relé
A relé az intelligens szerződésnek küld…
- az új állam 2 Merkle gyökere (címfa és egyensúlyok+nonces fa)
- a tranzakciók listája, aláírás nélkül. „Minden tranzakció 68 gázba kerül bájtonként. Így normál átutalás esetén a határköltség 68 * 3 (tól) + 68 * 3 (ig) + 68 * 1 (díj) + 68 * 4 + 4 * 2 (összeg) + 68 * 2 (nonce), vagy 892 gáz”
A PROVING folyamat ismert bemenetei a…
- a 2 Régi állam Merkle gyökerei
- a 2 Új állam Merkle gyökerei
- tranzakciók listája
A BIZONYÍTÁSI folyamat bizonyítja, hogy…
Adott
- a 2 régi állam Merkle-gyökér (már a szerződésben tárolva)
- a 2 új állapotú Merkle-gyökér (összesített tranzakcióban elküldve)
- a tranzakciók listája (az összesített tranzakcióban elküldve)
… a közvetítőnek érvényes aláírása van ahhoz, hogy 2 régi gyökér állapotból 2 új gyökerű állapotba lépjen ezekkel a tranzakciókkal.
AZ ELLENŐRZÉST a…
Az okos szerződés (szilárdságba kódolva, vyper, ahogy tetszik!)
A VERIFYING folyamat ismert bemenetei a következők…
Ugyanaz a PROVING folyamat ismert bemenetei, egyértelműen…!
A méretezhetőség korlátai
Minden összesített tranzakció 650 XNUMX gázt használ a SNARK ellenőrzéséhez (rögzített költség) plusz ~900 gáz az határköltség tranzakciónként (Az adatküldés költsége!). Tehát a teljes blokk felhasználásával a közvetítő legfeljebb aggregálhatja:
ami azt jelenti ~544 tx másodpercenként
barryWhiteHat változat
A BEÁLLÍTÁST a…
A srác, aki elindítja a projektet.
Az okos szerződés megmenti…
1 Merkle gyökér a jelenlegi állapottal. Minden levél egy fiók kivonatolt állapota.
Szeretne teremt Fiók?
állapot = Számlaállapot (pubkey, balance, nonce)
állapot.index = self._tree.append(state.hash())
A BIZONYÍTÁST a…
A relé
A relé az intelligens szerződésnek küld…
- bizonyíték 𝚷
- az új állam Merkle gyökér
- bizonyíték 𝚷
A PROVING folyamat ismert bemenetei a…
- a régi állam Merkle gyökér
- az új állam Merkle gyökér
A BIZONYÍTÁSI folyamat bizonyítja, hogy…
Adott
- a régi Merkle gyökér (már a szerződésben tárolva)
- az Új Merkle gyökér (senti az aggr. tranzakcióban)
… a közvetítőnek van egy listája azokról a tranzakciókról, amelyek érvényes aláírással rendelkeznek, hogy átkerüljenek a régi gyökér állapotból az új gyökérrel rendelkező állapotba
AZ ELLENŐRZÉST a…
Az okos szerződés (szilárdságba kódolva, vyper, ahogy tetszik!)
A VERIFYING folyamat ismert bemenetei a következők…
Ugyanaz a PROVING folyamat ismert bemenetei, egyértelműen…!
A méretezhetőség korlátai
A közvetítő nem küldi el a tranzakciók adatait az intelligens szerződésnek (ami költséges), így a korlát valójában a SNARK-igazolás ellenőrzéséhez szükséges gázmennyiség.
Howard Wu-t említve munka a SNARK PROVING fázisának elosztott rendszereken való futtatásáról, a barryWhiteHat optimistán kijelenti, hogy egy hatalmas SNARK-ban (16666 milliárd korlát!) 1 tranzakciót lehet megerősíteni.
barryWhiteHat is szerint a láncon 500k gázzal ellenőrizhető a bizonyíték, ami azt jelenti, hogy blokkonként 16 SNARK-ot (8 millió/500k) rakhatsz, ami ~1.07 SNARK másodpercenként… ami ~17,832 XNUMX tx másodpercenként (16,666 1.07 * XNUMX).
A végtelenbe és tovább
- Minden, ami csillog, nem arany / 1. A bizonyítási fázisban szükséges számítási teljesítmény és memória mennyisége szó szerint sokkoló lehet. Különösen a barryWhiteHat verziójában, ahol a komplexitás egy része lekerül a láncról. – írja Barry „Egy 7 GB rammal és 20 GB swap tárhellyel rendelkező laptopon nehéz másodpercenként 20 tranzakciót összesíteni”. Nos, ha a cél 17,832 XNUMX tx másodpercenként… LOL. Ez nem triviális párhuzamos számítási kihívásokat vezet be. De ha az átlagos dolláros tranzakciónkénti költség sokkal olcsóbb, mint a hagyományos no-SNARKS opció… a játék megéri a gyertyát.
- Minden, ami csillog, nem arany / 2. Lényeges adatelérhetőségi probléma van! Mivel csak a fa gyökere kerül mentésre a szerződésben, biztosnak kell lennie abban, hogy a fa teljes verziója (vagy, ez ugyanaz, a teljes tranzakciós előzmény) mindig elérhető. Ha az adatok nem állnak rendelkezésre, a közvetítő még érvényes aláírt tranzakciókkal sem tehet semmit, mert nem tudja igazolni a Régi állapot → Tranzakciók → Új állapot menüpontot.
- Annak érdekében, hogy a közvetítő megbízhatatlan legyen, és a szerződésben szereplő éterek értéke megegyezzen a külső éterekkel (likviditási probléma)… a felhasználóknak lehetővé kell tenniük, hogy akkor vegyenek fel pénzt az intelligens szerződésből, amikor csak akarnak, anélkül, hogy egy (specifikus) közvetítőre támaszkodnának. Hogyan? Ez nem tartozik ennek a 101-es bejegyzésnek a körébe, de erről a mellékelt linkeken olvashatsz.
- Szeretne többet megtudni arról, hogyan kezelhető a jelenlegi állapot (címek, egyenlegek és semmiségek) egy Merkle-fával? Levél hozzáadása, levél frissítése stb? Nézze meg ezt a könyvtárat (teszt fájl itt), amely ezt a mögöttes elemet használja modul. Köszönöm HarryR!
- Szeretné beállítani személyes Ethereum-SNARKS környezetét? Kezdjük a láncon kívül a C++-szal (beállítás, bizonyítás, ellenőrzés) itt. Utána költözhetsz az Ethereumba (ne felejtsd el, csak az ellenőrzés történik láncon!) a Zokrates-el (repo, a dokumentáció a kezdéshez).
- Mit szólnál RSA akkumulátorokhoz a Merkle fák helyett? Google „rsa accumulators ethereum” kezdeni…
Enjoy!
Twitter @marco_derossi
- 7
- Fiók
- Minden termék
- között
- elérhetőség
- Alapjai
- Billió
- esetek
- változik
- Ellenőrzések
- coinbase
- számítástechnika
- megegyezés
- szerződés
- kiadások
- Jelenlegi
- Jelenlegi állapot
- DApps
- dátum
- adatkészlet
- Decentralizálás
- Dimenzió
- Elosztott könyvtár
- elosztott főkönyvi technológia
- Környezet
- Éter
- Ethereum
- EU
- EV
- hamisítvány
- Végül
- vezetéknév
- Ingyenes
- funkció
- játék
- GAS
- GitHub
- Giving
- Arany
- jó
- nagy
- útmutató
- hash
- itt
- Magas
- történelem
- Hogyan
- hr
- HTTPS
- hatalmas
- Több száz
- ia
- index
- információ
- IP
- IT
- Munka
- Kulcs
- hordozható számítógép
- nagy
- vezet
- Főkönyv
- szint
- LG
- könyvtár
- fizetőképesség
- Lista
- főáram
- Térképek
- közepes
- millió
- Miners
- pénz
- hónap
- Legnepszerubb
- mozog
- nevek
- hálózat
- csomópontok
- számok
- Művelet
- érdekében
- Más
- tulajdonos
- Fizet
- Emberek (People)
- játékos
- Népszerű
- hatalom
- magán
- magánkulcs
- Program
- program
- bizonyíték
- bizonyul
- nyilvános
- nyilvános kulcs
- újrafutóz
- rsa
- szabályok
- futás
- biztonságos
- megtakarítás
- skálázhatóság
- Skála
- skálázás
- Tudomány
- biztonság
- készlet
- Megosztás
- megosztott
- rövid
- Egyszerű
- Méret
- alvás
- okos
- okos szerződés
- okostelefon
- So
- szoftver
- szilárdság
- Megoldások
- SOLVE
- Hely
- Költési
- kezdet
- kezdődött
- Állami
- Államok
- sikeres
- rendszer
- Systems
- Technológia
- teszt
- idő
- tokenek
- felső
- özön
- tranzakció
- Tranzakciók
- Bízzon
- Frissítés
- Felhasználók
- érték
- Igazolás
- Visa
- W
- WHO
- szavak
- Munka
- művek
- érdemes
- X