Vad du behöver:
- en datavetenskaplig bakgrund
- grunderna i Ethereum
- grunderna i kalkylen (optimering av begränsningar)
Vad får du:
- grunderna i nollkännedom SNARK
- grunderna i Merkle-träd
- hur Ethereum kunde skala till tusentals transaktioner per sekund tack vare SNARK
SNARK: er tillåter en Prover att bevisa för en verifierare att hon / han har en lösning W på problemet F med delade / kända ingångar X, utan att avslöja W.
Att hitta lösningen på problemet kan kräva en enorm mängd beräkningskraft och minne.
Så verifieraren kan i princip vara 100% säker på att Prover har fungerat korrekt (och hittat en lösning), utan att varken göra jobbet själv för att kontrollera lösningen eller veta lösningen alls. Det är magiskt!
Processen har tre steg:
- INSTÄLLNING - Problemet F (som måste uttryckas som kvadratisk aritmetiskt program, se nedan) är förberedd för SNARK. Den här processen är mycket hög med minne och beräkningskrävande beroende på problemets komplexitet (→ Antalet ingångar och begränsningar → Dimensionen av matrisen för problemstillståndets begränsning). Spelaren som gör installationen (kan vara Verifieraren själv) måste lita på av alla parter, eftersom installationen från Setup används i nästa faser. Installationen görs vanligtvis med libsnark, ett C ++ -bibliotek som är den mest populära implementeringen för zkSNARKs.
- JÄSNING - Prover, som har en lösning W för problemet F med delade ingångar X (han / hon kanske använde enorma mängder CPU och minne för att hitta det!), Använder libsnark och utgången från Inställning fas för att skapa ett bevis 𝚷. Denna process är definitivt högt minne och datorintensiv (beroende på problemets komplexitet, som ovan). Storleken på utgången (dvs. beviset 𝚷) är istället kortfattad och konstant oberoende av problemets komplexitet. Prover måste lita på vem som har gjort installationsfasen, eftersom hon / han använder sin produktion ...
- KONTROLLERA - En verifierare - som ger inmatning utgången från installationsfasen, delade ingångar X och bevis 𝚷 - kontrollerar beviset. Om verifieringen är framgångsrik lyckades Prover bevisa för en verifierare att hon / han har hittat lösningen W på problemet F ... utan att avslöja W! Den trevliga delen är att inte bara beviset är kortfattat och alltid har samma längd .. verifieringsprocessen är snabb och inte minne / datorintensiv alls. Till skillnad från de två tidigare faserna ... kan verifieringen enkelt göras med en smartphone på millisekunder!
En bra sammanfattning (källa):
Hur kan detta hända? Det är Merlin magi! Om du vill få matematiken bakom detta, börja härifrån.
Hur kan jag förvandla min programvara till ett kvadratiskt aritmetiskt program?
Som nämnts ovan måste installationsfasens problem F vara ett kvadratiskt aritmetiskt program. Spelreglerna är tuffa:
- Din programvaras ingångar bör vara siffror. Konvertera dina saker (matriser, strängar, etc) till siffror. Det är trivialt.
- Ett "kvadratiskt begränsat system för ekvationer" betyder:
där x är din n-dimensionella vektor för dina ingångar, m är antalet begränsningar (dvs antalet ekvationer för ditt system), C är n-för-n-koefficienter Matrix och q är en n-dimensionell koefficientsvektor. Om du inte gillar matris och vektorer är här fallet n = 3 och m = 2 (3 ingångar, 2 begränsningar):
- Implementeringen är en aritmetisk krets, vilket innebär att resultatet blir Problemet löst (systemet är löst, dvs. alla polynomer är lika med 0) eller Problemet har inte lösts (alla andra fall). Med andra ord: "dessa ingångar är / är inte en av lösningarna på detta problem".
- C₁, C2393, ..., C𝚖, q₁, q₂, ..., q𝚖-koefficienter är systemets begränsningar. Det är i grund och botten vad som definierar din programvara. Ändra dem ... så får du en annan programvara! Att komma tillbaka till hur SNARK: er fungerar: C₁, C₂, ..., C𝚖, q₁, q₂, ..., q𝚖 är ingången till installationsfasen. Utmatningen från installationsfasen (som du behöver för att bevisa och verifiera) är därför strängt relaterad till de C₁, C5647, ..., C𝚖, q₁, q₂, ..., q𝚖 och fungerar bara för det problemet. Om du ändrar dem definierar du en annan programvara / problem och du måste köra installationsfasen igen! x₁, x₂, ..., x𝗇 är variablerna (dvs vad du måste gissa för att få ett systems lösning). Så när vi säger "Dear Prover, kan du vänligen hitta en hemlig lösning W för problem F med delade / offentliga ingångar X" menar vi till exempel "Dear Prover, kan du hitta värdena x₁, x₂, ..., x𝗇 som löser systemet med till exempel x₇ = XNUMX, x₅XNUMX₆ = XNUMX? ” Du kan göra vad du vill med alla x𝗇, med undantag för x₇ och x₅₂₆, som är begränsade till delade / offentliga ingångar.
Det är ett tufft liv men du kan överleva ... Om du behöver slingor kan du öppna dem som upprepar samma operation många gånger. Eller om du till exempel behöver x₁⁴ x₂⁵, definierar du en ny ingång x₃ = x₁⁴ x₂⁵ och använder x₃ i dina begränsningar. Det handlar om att lägga till variabler och begränsningar ... Även för ganska enkla programvaror är det lätt att nå hundratals miljoner eller miljarder inmatningar och begränsningar!
Vill veta mer? Läsa här.. Och kolla också in detta grundläggande code_to_r1cs.py från ethereum / research.
Vad är ett Merkle-träd?
En hashfunktion är en regel som kartlägger en ingång av godtycklig storlek till en utgång av fast storlek. Vi kan uppfinna en ganska värdelös hashfunktion "Förena de två första med de två sista bokstäverna" som förvandlar "Woody Allen" till "Woen" och "Paul McCartney" till "Paey".
Ett Merkle-träd är en datastruktur där varje förälder är hash för sina två söner. Överst hittar du roten, som är hashen för de två sönerna på nivå 1. Längst ner är varje blad hash av en extern ingång.
Med vår fiktion "Woody Allen" → "Woen"-hashfunktion:
När ett blad ändras sprids ändringen upp till roten. Om ANTHONY förändras, ändras också ANNY (blad), CENY och CECO (Root). Oavsett vilket blad som ändras ändras roten också.
Du behöver inte hela trädet för att beräkna roten igen. I vårt exempel, om ANTHONY förändras och du känner till både JACO och CECILY, kan du enkelt beräkna om roten även om du helt ignorerar JAMES, MARCO, JAES och MACO. För enorma träd sparar detta mycket tid!
Så vad?
Merkle-träd är bra för datakontroller. Vanligtvis: du vet vilken som är den giltiga roten, och du kontrollerar att de mottagna uppgifterna matchar den roten. Till exempel: en betrodd part som inte kan ge dig hela datauppsättningen med förnamn på människor på jorden (ingen tid, ingen bandbredd eller kanske hon / han inte har uppgifterna alls) ger dig bara roten (t.ex. ”CECO”). Efterord: du får miljontals förnamn, med hänvisning till bladnumret, av tusentals otillitna parter. Tja, eftersom du har rätt rot kan du kontrollera vem du kan lita på, vem som ger dig falska data ...
Merkle träd är en del av ditt liv också! När du laddar ner en 3 GB Torrent-fil är din fil uppdelad i miljoner små bitar. Hashen för varje bit lagras i ett blad. Eftersom du vet vilken som är den giltiga roten av trädet, kan du kontrollera om den är korrekt varje gång du får en bit av filen av någon. Om det inte är det, kan du be samma del till någon annan.
Du kan göra det även om du ännu inte har laddat ner hela trädet / alla löv: om du vet att roten är CECO och du litar på JACO ... när du får biten ANTHONY kan du verifiera den även om du inte har laddat ner ändå bitarna MARCO och JAMES.
Varför Merkle-träd är användbara i distribuerad huvudboksteknik är enkelt: du använder konsensusprotokoll (långsamt, dyrt) endast för att nå enighet om roten. Då kan nätverkets opålitliga noder effektivt och direkt dela data ... och kan sova säkert och ljud tack vare integritetskontroller med Root.
När Gud bad Ethereum att välja två superkrafter bland säkerhet, skalbarhet och decentralisering ... Ethereum offrade skalbarhet. Egentligen finns det inget starkt tak för "transaktioner per sekund": taket avser mängden gas i varje block - vilket är, förenkla, mängden operationer som jag kan göra i varje block. Denna gräns är 2 miljoner gas. Det kan betyda många "små" transaktioner (inga data kopplade till transaktionerna, inga operationer som ska utföras på den informationen) eller få stora transaktioner. Det är upp till Ethereums noder, som skickar in transaktioner, och till Ethereums gruvarbetare, som i blocket inkluderar de transaktioner som betalar mer.
Ett block bryts varje ~ 15 sekunder. Det betyder ~ 32 miljoner gas per minut, vilket definitivt inte räcker om vi vill att Ethereums dappar ska gå i mainstream.
Förresten: sluta med de tråkiga jämförelser mellan Ethereum och Visa. Ett centraliserat system kommer alltid vara snabbare än Ethereum ... genom design! De gör olika saker och du behöver dem i olika situationer. Om du inte behöver decentralisering och en förtroendelös miljö ... bör du naturligtvis välja Visa. Kortfattat: det faktum att din mixer snurrar snabbare än din tvättmaskin betyder inte att du kommer att rengöra byxorna i en mixer!
Låt oss sätta pusslet ihop! Föreställ dig att du kan "komprimera" många små transaktioner i en stor transaktion tack vare SNARK. Om gasen som används av denna stora transaktion är mindre än summan av gasen som spenderas av de små transaktionerna, betyder det att du sparar bensin.
Och att spara gas betyder:
- Användare som totalt sett spenderar mindre för transaktioner → Det här skulle vara ett tryck för hela ekosystemet
- Att kunna lägga mer saker i ett block → Ethereum snurrar snabbare än din mixer!
Hur fungerar det?
Det finns användare, en relayer (eller fler relayers) som sammanför transaktioner och ett smart kontrakt.
- Användare som är villiga att spela detta spel skickar sina Ether (eller tokens) till ett offentligt granskat smartkontrakt. För varje ny spelare skapas ett nytt blad i ett Merkle-träd. Bladet innehåller information om Ether-ägaren (hennes adress, som också är den allmänna nyckeln), mängden Ether och nonce (transaktionens räknare för det kontot, som är 0 när bladet läggs till)
- När A vill skicka Ether till B (de båda måste ha ett blad / konto i det smarta kontraktet) packar A en transaktion, som inkluderar adressen till frånkonto, till konto, nuncio av från kontot, mängd Ether som ska överföras och namnteckning av transaktionen (undertecknat med den privata nyckeln för ”från” -kontot, uppenbarligen). Hon / han skickar sedan den packade transaktionen till vidarebefordran.
- Reläet samlar alla transaktioner som mottagits i ett givet tidsfönster (t.ex. en timme), uppdaterar Merkle-trädet med de nya saldobeloppen och skapar ett SNARK-bevis som bevisar att alla signaturer och det nya Merkle-trädets rot är giltiga. Reläet skickar äntligen det nya tillståndet och beviset till det smarta kontraktet.
- Det smarta kontraktet validerar Proof on-chain. Om det är giltigt sparar det Merkle-trädroten i det nya tillståndet i det interna minnet av kontraktet.
I grund och botten visar Merkle-trädroten hela tillståndet för alla konton. Och du kan inte ändra dem (= stjäla pengar) om du inte kan bevisa giltigheten för de underskrifter vars transaktioner leder till det nya tillståndet sammanfattat av den nya roten du skickar in.
I ett nötskal: användare har supersnabba och nästan gratis transaktioner, som på Coinbase, utan att behöva lita på reläet, som inte kan göra någonting, till skillnad från på Coinbase, utan din signatur.
Det är en icke-förvarad sidokedja vars tillstånd sammanfattas av en Merkle-trädrot.
Låt oss ansluta det vi lärde oss ovan om SNARK med det vi just diskuterade om skalning. Det finns olika sätt att göra det. Jag jämför två recept: Vitalik's version och barryWhiteHat's version.
INSTÄLLNINGEN görs av ...
Killen som startar projektet, som också skapar det smarta kontraktet. Ju mer hörbar det är, desto bättre. Du bör lita på henne / det ... det är en betrodd installation!
Det smarta kontraktet sparar ...
2 Merkle roots (bytes32-värden): det första trädet innehåller kontonets adresser (offentliga signaturer), det andra kontots saldo och avdrag
PROVING görs av ...
Reläet
Reläet skickar till det smarta kontraktet ...
- de två Merkle-rötterna i den nya staten (adresserar träd och balanserar + nonces-träd)
- listan över transaktioner, utan underskrifter. ”Varje transaktion kostar 68 gas per byte. Därför kan vi för en regelbunden överföring förvänta oss att marginalkostnaden blir 68 * 3 (från) + 68 * 3 (till) + 68 * 1 (avgift) + 68 * 4 + 4 * 2 (belopp) + 68 * 2 (nonce) eller 892 gas ”
PROVING-processens kända ingångar är ...
- de två gamla staten Merkle rötter
- de två nya staten Merkle rötter
- transaktionslista
PROVING-processen bevisar att ...
Med tanke på
- de två gamla statliga Merkle-rötterna (redan lagrade i kontraktet)
- de två nya statliga Merkle-rötterna (skickas in den aggr. transaktionen)
- transaktionslistan (skickas i aggr. transaktion)
... reläet har giltiga signaturer för att flytta från tillstånd med 2 gamla rötter till stat med 2 nya rötter med dessa transaktioner.
VERIFIERING sker av ...
Det smarta kontraktet (kodat i soliditet, vyper, som du vill!)
VERIFIERING av processens kända ingångar är ...
Samma PROVINGs process kända input, helt klart ...!
Begränsar till skalbarhet
Varje aggregerad transaktion använder 650k gas för SNARK-verifiering (fast kostnad) plus ~ 900 gas av marginalkostnad per transaktion (Det kostar att skicka data!). Så genom att använda hela blocket kan reläen sammanställa högst:
som betyder ~ 544 tx per sekund
barryWhiteHat s version
INSTÄLLNINGEN görs av ...
Killen som startar projektet.
Det smarta kontraktet sparar ...
1 Merkle rot med den nuvarande staten. Varje blad är ett kontos tillstånd.
Vill skapa ett konto?
state = AccountState (pubkey, saldo, nonce)
state.index = self._tree.append (state.hash ())
PROVING görs av ...
Reläet
Reläet skickar till det smarta kontraktet ...
- bevis 𝚷
- den nya staten Merkle rot
- bevis 𝚷
PROVING-processens kända ingångar är ...
- den gamla staten Merkle roten
- den nya staten Merkle rot
PROVING-processen bevisar att ...
Med tanke på
- den gamla Merkle-roten (redan lagrad i kontraktet)
- den nya Merkle-roten (senti i aggr. transaktion)
... vidarebefordran har en lista över transaktioner med giltiga signaturer för att flytta från stat med gammal root till stat med ny root
VERIFIERING sker av ...
Det smarta kontraktet (kodat i soliditet, vyper, som du vill!)
VERIFIERING av processens kända ingångar är ...
Samma PROVINGs process kända input, helt klart ...!
Begränsar till skalbarhet
Reläet skickar inte transaktionsdata till det smarta kontraktet (vilket är kostsamt), så gränsen är faktiskt mängden gas som ska verifiera SNARK-beviset.
Nämner Howard Wu's arbete om att köra SNARKs PROVING-fas på distribuerade system, barryWhiteHat optimistiskt säger att det är möjligt att bekräfta 16666 transaktioner i en enorm SNARK (1 miljard begränsningar!).
barryWhiteHat också tänker det är möjligt att verifiera beviset 𝚷 på kedjan med 500k gas, vilket innebär att du kan sätta 16 SNARK (8 miljoner / 500 k) per block, vilket är ~ 1.07 SNARK per sekund ... vilket betyder ~ 17,832 XNUMX tx per sekund (16,666 1.07 * XNUMX).
Mot oändligheten och vidare
- Allt som glittrar är inte guld / 1. Mängden datorkraft och minne som du behöver i provningsfasen kan vara bokstavligen chockerande. Speciellt i barryWhiteHats version, där en del av komplexiteten flyttas utanför kedjan. Barry skriver "På en bärbar dator med 7 GB ram och 20 GB byte utrymme kämpar det för att samla 20 transaktioner per sekund". Tja, om målet är 17,832 XNUMX tx per sekund… LOL. Detta introducerar icke triviala parallella beräkningsutmaningar. Men om den genomsnittliga kostnaden för $ per transaktion är mycket billigare än det vanliga alternativet utan SNARK: ar ... är spelet värt ljuset.
- Allt som glittrar är inte guld / 2. Det finns en relevant problem med datatillgänglighet! Eftersom bara trädets rot är sparad i kontraktet måste du vara säker på att en hel version av trädet (eller, det är samma, hela transaktionshistoriken) alltid är tillgänglig. Om data inte är tillgängliga kan inte relayeraren, även med giltiga signerade transaktioner, göra någonting eftersom hon / han inte kan bevisa Old State → Transactions → New State.
- För att reläet ska vara tillförlitligt och Ethers i kontraktet ska ha samma värde som Ethers utanför (likviditetsproblem) ... användare bör kunna ta ut pengar från det smarta kontraktet när de vill utan att förlita sig på en (specifik) relä. Hur? Detta omfattas inte av detta 101 inlägg, men du kan läsa om detta i de bifogade länkarna.
- Vill du förstå mer om hur den nuvarande staten (adresser, balanser och brister) kan hanteras med ett Merkle-träd? Lägga till ett blad, uppdatera ett blad osv? Kolla upp detta bibliotek (testfil här.) som använder detta underliggande modul. Tack HarryR!
- Vill du ställa in din personliga Ethereum-SNARK-miljö? Låt oss börja utanför kedjan med C ++ (Setup, Proving, Verifying) här.. Sedan kan du flytta till Ethereum (glöm inte, bara verifieringen görs på kedjan!) Med Zokrates (repa, den dokumentation att komma igång med).
- Vad sägs om att använda RSA-ackumulatorer istället för Merkle-träd? Google “Rsa ackumulatorer ethereum” att börja…
Njut!
Twitter @marco_derossi
- 7
- Konto
- Alla
- bland
- tillgänglighet
- Grunderna
- Miljarder
- fall
- byta
- Kontroller
- coinbase
- databehandling
- Konsensus
- kontrakt
- Kostar
- Aktuella
- Nuvarande tillstånd
- DApps
- datum
- datauppsättning
- Decentralisering
- Dimensionera
- Distribuerad Ledger
- distribuerad ledgerteknik
- Miljö
- Eter
- ethereum
- EU
- EV
- fejka
- Slutligen
- Förnamn
- Fri
- fungera
- lek
- GAS
- GitHub
- Ge
- Gold
- god
- stor
- styra
- hash
- här.
- Hög
- historia
- Hur ser din drömresa ut
- hr
- HTTPS
- stor
- Hundratals
- ia
- index
- informationen
- IP
- IT
- Jobb
- Nyckel
- laptop
- Large
- leda
- Ledger
- Nivå
- LG
- Bibliotek
- Likviditet
- Lista
- Vanliga
- kartor
- Medium
- miljon
- gruvarbetare
- pengar
- månader
- Mest populär
- flytta
- namn
- nät
- noder
- nummer
- Verksamhet
- beställa
- Övriga
- ägaren
- Betala
- Personer
- Spelaren
- Populära
- kraft
- privat
- privat nyckel
- Program
- projektet
- bevis
- bevisar
- allmän
- Public Key
- resumé
- rsa
- regler
- rinnande
- säker
- sparande
- skalbarhet
- Skala
- skalning
- Vetenskap
- säkerhet
- in
- Dela
- delas
- Kort
- Enkelt
- Storlek
- sova
- smarta
- smart kontrakt
- smartphone
- So
- Mjukvara
- fasthet
- Lösningar
- LÖSA
- Utrymme
- Spendera
- starta
- igång
- Ange
- Stater
- framgångsrik
- system
- System
- Teknologi
- testa
- tid
- tokens
- topp
- torrent
- transaktion
- Transaktioner
- Litar
- Uppdateringar
- användare
- värde
- Verifiering
- visum
- W
- VEM
- ord
- Arbete
- fungerar
- värt
- X