Hva du trenger:
- en informatisk bakgrunn
- det grunnleggende om Ethereum
- grunnleggende beregning (begrensning optimalisering)
Hva du får:
- det grunnleggende om SNARKs med null kunnskap
- det grunnleggende om Merkle-trær
- hvordan Ethereum kunne skalere til tusenvis av transaksjoner per sekund takket være SNARKs
SNARKs tillater en Beviser å bevise for en Verifier at hun / han har en løsning W på problemet F med delte / kjente innganger X, uten å avsløre W.
Å finne løsningen på problemet kan kreve en enorm mengde beregningskraft og minne.
Så Verifier kan i utgangspunktet være 100% sikker på at Prover har fungert ordentlig (og funnet en løsning), med verken å gjøre jobben på egen hånd for å sjekke løsningen eller vite noe om løsningen i det hele tatt. Det er magisk!
Prosessen har tre trinn:
- OPPSETT - Problemet F (som må uttrykkes som kvadratisk regningsprogram, se nedenfor) er forberedt på SNARK. Denne prosessen er veldig høyt minne og databehandlingsintensiv, avhengig av problemets kompleksitet (→ Antall innganger og begrensninger → Dimensjonen til matrisen til problemet med begrensningstilfredshet). Spilleren som gjør oppsettet (kan være selve bekrefteren) må være klarert av alle parter, siden utdataene fra oppsettet brukes i de neste fasene. Oppsettet gjøres vanligvis ved hjelp av libsnark, et C ++ bibliotek som er den mest populære implementeringen for zkSNARKs.
- VISER - Beviseren, som har en løsning W for problemet F med delte innganger X (kanskje hun / han brukte enorme mengder CPU og minne på å finne det!), Bruker libsnark og utdata fra Oppsett fase for å lage et bevis 𝚷. Denne prosessen er absolutt høyt minne og databehandlingskrevende (avhengig av problemets kompleksitet, som ovenfor). Størrelsen på utgangen (dvs. bevis proof) er i stedet kortfattet og konstant uavhengig av problemets kompleksitet. Beviseren må stole på hvem som har gjort installasjonsfasen, siden hun / han bruker utdataene ...
- VERIFISERING - En verifier - som inngang gir utgangen fra oppsettfasen, delte innganger X og proof checks - sjekker beviset. Hvis verifiseringen er vellykket, klarte beviseren å bevise overfor en verifiser at hun / han har funnet løsningen W på problemet F ... uten å avsløre W! Den fine delen er at ikke bare beviset er kortfattet og alltid har samme lengde .., bekreftelsesprosessen er rask og ikke minne- / databehandlingskrevende i det hele tatt. I motsetning til de to foregående fasene ... bekreftelsen kan enkelt gjøres med en smarttelefon i millisekunder!
En god oppsummering (kilde):
Hvordan kan dette skje? Vel, det er Merlin-magi! Hvis du vil ha matematikken bak dette, start herfra.
Hvordan kan jeg forvandle programvaren min til et kvadratisk regneprogram?
Som nevnt ovenfor, må oppsettfasens problem F være et kvadratisk regningsprogram. Spillereglene er tøffe:
- Programvarens innganger skal være tall. Konverter ting (matriser, strenger osv.) Til tall. Det er trivielt.
- Et "kvadratisk begrenset ligningssystem" betyr:
hvor x er den n-dimensjonale vektoren til inngangene dine, m er antall begrensninger (dvs. antall ligninger for systemet ditt), C er n-av-n-koeffisientmatrisen og q er en n-dimensjonal koeffisientvektor. Hvis du ikke liker matrise og vektorer, er her n = 3 og m = 2 tilfelle (3 innganger, 2 begrensninger):
- Implementeringen er en aritmetisk krets, som betyr at resultatet blir Problemet løst (systemet er løst, dvs. at alle polynomer er lik 0) eller Problemet ikke løst (alle de andre sakene). Med andre ord: “disse inngangene er / er ikke en av løsningene på dette problemet”.
- C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 koeffisienter er systemets begrensninger. Dette er i utgangspunktet det som definerer programvaren din. Endre dem ... og du får en annen programvare! Å komme tilbake til hvordan SNARK fungerer: C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 er inngangen til installasjonsfasen. Produksjonen fra installasjonsfasen (som du trenger for å bevise og verifisere) er derfor strengt relatert til disse C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 og fungerer bare for det problemet. Hvis du endrer dem, definerer du en annen programvare / et problem, og du må kjøre installasjonsfasen på nytt! x₁, x₂,…, x𝗇 er variablene (dvs. hva du må gjette for å få et systems løsning). Så når vi sier "Kjære Prover, kan du finne en hemmelig løsning W for problem F med delte / offentlige innganger X", mener vi for eksempel "Kjære Prover, kan du finne x₁, x₂,…, x𝗇 verdiene som løser systemet med for eksempel x₇ = 2393, x₅₂₆ = 5647? ” Du kan gjøre hva du vil med alle x𝗇, bortsett fra x₇ og x₅₂₆, som er begrenset til delte / offentlige innganger.
Det er et tøft liv, men du kan overleve ... Hvis du trenger løkker, kan du brette dem ut og gjenta samme operasjon mange ganger. Eller hvis du trenger for eksempel x₁⁴ x₂⁵, definerer du en ny inngang x₃ = x₁⁴ x₂⁵ og bruker x₃ i dine begrensninger. Det handler om å legge til variabler og begrensninger ... Selv for ganske enkle programvare er det lett å nå hundrevis av millioner eller milliarder av innganger og begrensninger!
Vil du vite mer? Lese her.. Og sjekk også ut dette grunnleggende code_to_r1cs.py fra ethereum / forskning.
Hva er et Merkle-tre?
En hash-funksjon er en regel som tilordner en inngang av vilkårlig størrelse til en utgang med fast størrelse. Vi kunne finne på en ganske ubrukelig hash-funksjon “Sammenslett de to første med de to siste bokstavene” som forvandler “Woody Allen” til “Woen” og “Paul McCartney” til “Paey”.
Et Merkle-tre er en datastruktur der hver forelder er hasjen til sine to sønner. Øverst finner du roten, som er hasjen til de to sønnene på nivå 1. Nederst er hvert blad hasjen til en ekstern inngang.
Ved hjelp av vår ordbok "Woody Allen" → "Woen" hash-funksjon:
Når et blad endres, forplantes modifikasjonen opp til roten. Hvis ANTHONY endres, endres også ANNY (blad), CENY og CECO (Root). Uansett hvilket blad som endres, endres også roten.
Du trenger ikke hele treet for å beregne roten på nytt. I vårt eksempel, hvis ANTHONY endres og du kjenner både JACO og CECILY, kan du enkelt beregne roten på nytt selv om du fullstendig ignorerer JAMES, MARCO, JAES og MACO. For store trær sparer dette mye tid!
Så hva?
Merkle trær er gode for dataintegritetskontroller. Vanligvis: du vet hvilken som er gyldig rot, og du sjekker at mottatte data samsvarer med roten. For eksempel: en klarert part som ikke kan gi deg hele datasettet med fornavnene til mennesker på jorden (ingen tid, ingen båndbredde eller kanskje hun / han ikke har dataene i det hele tatt) gir deg bare roten (f.eks. “CECO”). Etterord: du mottar millioner av fornavn, med henvisning til bladnummeret, av tusenvis av ikke-tillit. Vel, siden du har riktig rot, kan du sjekke hvem du kan stole på, hvem som gir deg falske data ...
Merkle trær er også en del av livet ditt! Når du laster ned en 3 GB Torrent-fil, er filen din delt inn i millioner av små biter. Hashen til hver del lagres i et blad. Siden du vet hvilken som er den gyldige roten til treet, kan du sjekke om den er riktig hver gang du mottar en del av filen av noen. Hvis det ikke er det, kan du be den samme delen til noen andre.
Du kan gjøre det selv om du ennå ikke har lastet ned hele treet / alle bladene: hvis du vet at roten er CECO og du stoler på JACO ... når du mottar klumpen ANTHONY, kan du bekrefte det selv om du ikke har lastet ned ennå biter MARCO og JAMES.
Hvorfor Merkle-trær er nyttige i distribuert hovedboksteknologi er grei: du bruker konsensusprotokoller (sakte, dyre) bare for å oppnå konsensus om roten. Da kan de upålitelige nodene i nettverket effektivt og direkte dele data ... og kan sove trygt og lyd takket være integritetskontroller med roten.
Da Gud ba Ethereum velge 2 superkrefter blant sikkerhet, skalerbarhet og desentralisering ... Ethereum ofret skalerbarhet. Egentlig er det ikke noe sterkt tak på "transaksjoner per sekund": taket gjelder mengden gass i hver blokk - som forenkler mengden operasjoner jeg kan gjøre i hver blokk. Denne grensen er 8 millioner gass. Det kan bety mange "små" transaksjoner (ingen data knyttet til transaksjonene, ingen operasjoner som skal utføres på disse dataene) eller få store transaksjoner. Det er opp til Ethereums noder som sender inn transaksjoner, og Ethereums gruvearbeidere som inkluderer transaksjoner som betaler mer i blokken.
En blokk utvinnes hver ~ 15 sekunder. Det betyr ~ 32 millioner gass per minutt, noe som definitivt ikke er nok hvis vi vil at Ethereums dapps skal gå mainstream.
Forresten: stopp med de kjedelige sammenligningene mellom Ethereum og Visa. Et sentralisert system vil alltid være raskere enn Ethereum ... av design! De gjør forskjellige ting, og du trenger dem i forskjellige situasjoner. Hvis du ikke trenger desentralisering og et tillitsfritt miljø ... bør du selvfølgelig velge Visa. Kort oppsummert: det faktum at blenderen din snurrer raskere enn vaskemaskinen din, betyr ikke at du vil rengjøre buksene i en blender!
La oss sette puslespillet sammen! Tenk deg at du kan "komprimere" mange små transaksjoner i en stor transaksjon takket være SNARKs. Hvis gassen som brukes av denne store transaksjonen er mindre enn summen av gassen som brukes av de små transaksjonene, betyr det at du sparer gass.
Og å spare gass betyr:
- Brukere bruker mindre på transaksjoner generelt → Dette vil være et press for hele økosystemet
- Å kunne sette flere ting i en blokk → Ethereum snurrer raskere enn blenderen din!
Hvordan virker det?
Det er brukere, et videresending (eller flere videresendere) som samler transaksjoner og en smart kontrakt.
- Brukere som er villige til å spille dette spillet, sender Ether (eller tokens) til en offentlig revidert smart kontrakt. For hver nye spiller skapes et nytt blad i et Merkle-tre. Bladet inneholder informasjon om Ether-eieren (hans / hans adresse, som også er den offentlige nøkkelen), mengden Ether og nonce (transaksjonenes teller for kontoen, som er 0 når bladet legges til)
- Når A ønsker å sende Ether til B (begge må ha et blad / konto i den smarte kontrakten), pakker A en transaksjon, som inkluderer adressen til frakonto, den til konto, den nuncio av fra-kontoen, den beløp av Ether som skal overføres og signatur av transaksjonen (åpenbart signert med den private nøkkelen til "fra" -kontoen). Hun / han sender deretter den fullpakkete transaksjonen til videresendingen.
- Videresendingen samler alle transaksjonene som mottas i et gitt tidsvindu (f.eks. En time), oppdaterer Merkle-treet med de nye saldoenes beløp og lager et SNARK-bevis som beviser at alle signaturer og det nye Merkle-treets rot er gyldige. Videresendingen sender endelig den nye staten og beviset til den smarte kontrakten.
- Den smarte kontrakten validerer Proof on-chain. Hvis den er gyldig, lagrer den den nye staten Merkle-træroten i kontraktens interne minne.
I utgangspunktet viser Merkle-treroten hele tilstanden til alle regnskapene. Og du kan ikke endre det (= stjele penger) med mindre du kan bevise gyldigheten av signaturene hvis transaksjoner fører til den nye tilstanden oppsummert av den nye roten du sender inn.
I et nøtteskall: brukere har super raske og nesten gratis transaksjoner, som på Coinbase, uten å måtte stole på relayeren, som ikke kan gjøre noe, i motsetning til på Coinbase, uten signaturen din.
Det er en ikke-varetekt sidekjede hvis tilstand er oppsummert av en Merkle-trerot.
La oss koble det vi lærte ovenfor om SNARKs, med det vi nettopp diskuterte om skalering. Det er forskjellige måter å gjøre det på. Jeg skal sammenligne 2 oppskrifter: Vitaliks versjon og barryWhiteHat's versjon.
INNSTILLINGEN gjøres av ...
Fyren som starter prosjektet, som også lager den smarte kontrakten. Jo mer kontrollerbar det er, jo bedre. Du bør stole på henne / ham ... det er en klarert oppsett!
Den smarte kontrakten sparer ...
2 Merkle-røtter (bytes32-verdier): det første treet inneholder kontoenes adresser (offentlige signaturer), den andre kontoenes saldoer og nonces
PROVING gjøres av ...
Videresendingen
Videresendingen sender til den smarte kontrakten ...
- de 2 Merkle-røttene til den nye staten (adresserer treet og balanserer + nonces-treet)
- listen over transaksjoner, uten underskrifter. “Hver transaksjon koster 68 gass per byte. Derfor kan vi for en vanlig overføring forvente at marginalkostnaden vil være 68 * 3 (fra) + 68 * 3 (til) + 68 * 1 (avgift) + 68 * 4 + 4 * 2 (beløp) + 68 * 2 (nonce), eller 892 gass ”
PROVING-prosessens kjente innganger er ...
- de 2 gamle statlige Merkle-røttene
- de 2 nye statlige Merkle-røttene
- transaksjonsliste
PROVING-prosessen beviser at ...
Gitt
- de to gamle statlige Merkle-røttene (allerede lagret i kontrakten)
- de 2 nye statlige Merkle-røttene (sendt i aggr. transaksjonen)
- transaksjonslisten (sendt i aggr. transaksjonen)
... videresenderen har gyldige signaturer for å flytte fra stat med to gamle røtter til tilstand med 2 nye røtter med disse transaksjonene.
VERIFYING gjøres av ...
Den smarte kontrakten (kodet i soliditet, vyper, som du vil!)
VERIFYING-prosessens kjente innganger er ...
Den samme PROVINGs prosess kjente innganger, helt klart ...!
Grenser til skalerbarhet
Hver samlede transaksjon bruker 650 XNUMX gass for SNARK-bekreftelse (faste kostnader) pluss ~ 900 gass på marginalkostnaden per transaksjon (Det koster å sende data!). Så ved å bruke hele blokken kan relayeren samlet sett maksimalt:
som betyr ~ 544 tx per sekund
barryWhiteHat's versjon
INNSTILLINGEN gjøres av ...
Fyren som starter prosjektet.
Den smarte kontrakten sparer ...
1 Merkle-rot med den nåværende staten. Hvert blad er den hashede tilstanden til en konto.
Lyst til å skape en konto?
state = AccountState (pubkey, balance, nonce)
state.index = self._tree.append (state.hash ())
PROVING gjøres av ...
Videresendingen
Videresendingen sender til den smarte kontrakten ...
- bevis 𝚷
- den nye staten Merkle-roten
- bevis 𝚷
PROVING-prosessens kjente innganger er ...
- den gamle statens Merkle-rot
- den nye staten Merkle-roten
PROVING-prosessen beviser at ...
Gitt
- den gamle Merkle-roten (allerede lagret i kontrakten)
- den nye Merkle-roten (senti i aggr. transaksjonen)
... videresenderen har en liste over transaksjoner med gyldige signaturer for å flytte fra tilstand med gammel rot til tilstand med ny rot
VERIFYING gjøres av ...
Den smarte kontrakten (kodet i soliditet, vyper, som du vil!)
VERIFYING-prosessens kjente innganger er ...
Den samme PROVINGs prosess kjente innganger, helt klart ...!
Grenser til skalerbarhet
Videresendingen sender ikke transaksjonsdata til den smarte kontrakten (som er kostbar), så grensen er faktisk mengden gass for å verifisere SNARK-beviset.
Nevner Howard Wu's arbeid om å kjøre SNARKs PROVING-fase på distribuerte systemer, barryWhiteHat optimistisk sier at det er mulig å bekrefte 16666 transaksjoner i en enorm SNARK (1 milliard begrensninger!).
barryWhiteHat også mener det er mulig å verifisere bevis 𝚷 on-chain med 500k gass, noe som betyr at du kan sette 16 SNARKs (8 millioner / 500k) per blokk, som er ~ 1.07 SNARKs per sekunder ... som betyr ~ 17,832 tx per sekund (16,666 * 1.07).
Til evigheten og forbi
- Alt som glitrer er ikke gull / 1. Mengden datakraft og minne du trenger i bevisingsfasen, kan være bokstavelig talt sjokkerende. Spesielt i barryWhiteHats versjon, der en del av kompleksiteten flyttes utenfor kjeden. skriver barry “På en bærbar PC med 7 GB ram og 20 GB bytterom sliter det med å samle 20 transaksjoner per sekund”. Vel, hvis målet er 17,832 XNUMX tx per sekund ... LOL. Dette introduserer ikke trivielle parallelle beregningsutfordringer. Men hvis den gjennomsnittlige $ kostnaden per transaksjon er langt billigere enn det vanlige alternativet no-SNARKs ... er spillet verdt lyset.
- Alt som glitrer er ikke gull / 2. Det er et relevant problem med datatilgjengelighet! Siden bare treets rot er lagret i kontrakten, må du være sikker på at en hel versjon av treet (eller, det er det samme, hele transaksjonshistorikken) alltid er tilgjengelig. Hvis data ikke er tilgjengelig, kan ikke videresendingen, selv med gyldige signerte transaksjoner, gjøre noe fordi hun / han ikke kan bevise Old State → Transactions → New State.
- For at relayeren skal være pålitelig og Ethers i kontrakten skal ha samme verdi av Ethers utenfor (likviditetsproblem) ... bør brukere kunne ta ut penger fra den smarte kontrakten når de vil, uten å stole på et (spesifikt) relay. Hvordan? Dette er ikke innenfor omfanget av dette 101-innlegget, men du kan lese om dette i vedlagte lenker.
- Vil du forstå mer om hvordan den nåværende staten (adresser, saldoer og nonces) kan håndteres med et Merkle-tre? Legge til et blad, oppdatere et blad, etc? Sjekk ut dette biblioteket (testfil her.) som bruker dette underliggende moduler. Takk HarryR!
- Vil du sette opp ditt personlige Ethereum-SNARK-miljø? La oss starte off-chain med C ++ (Setup, Proving, Verifying) her.. Deretter kan du flytte til Ethereum (ikke glem, bare bekreftelsen gjøres i kjeden!) Med Zokrates (repoden dokumentasjon å komme i gang med).
- Hva med å bruke RSA-akkumulatorer i stedet for Merkle-trær? Google “Rsa akkumulatorer ethereum” å starte…
Nyt!
Twitter @marco_derossi
- 7
- Logg inn
- Alle
- blant
- tilgjengelighet
- Grunnleggende
- Milliarder
- saker
- endring
- Sjekker
- coinbase
- databehandling
- Konsensus
- kontrakt
- Kostnader
- Gjeldende
- Nåværende situasjon
- DApps
- dato
- datasett
- desentralisering
- Dimensjon
- Distribuert Ledger
- distribuert ledgerteknologi
- Miljø
- Eter
- ethereum
- EU
- EV
- forfalskning
- Endelig
- Først
- Gratis
- funksjon
- spill
- GAS
- GitHub
- Giving
- Gull
- god
- flott
- veilede
- hash
- her.
- Høy
- historie
- Hvordan
- hr
- HTTPS
- stort
- Hundrevis
- ia
- indeks
- informasjon
- IP
- IT
- Jobb
- nøkkel
- laptop
- stor
- føre
- Ledger
- Nivå
- LG
- Bibliotek
- Likviditet
- Liste
- Mainstream
- Kart
- medium
- millioner
- Miners
- penger
- måneder
- Mest populær
- flytte
- navn
- nettverk
- noder
- tall
- Drift
- rekkefølge
- Annen
- eieren
- Betale
- Ansatte
- spiller
- Populær
- makt
- privat
- private Key
- program
- prosjekt
- bevis
- beviser
- offentlig
- offentlig Key
- oppsummering
- rsa
- regler
- rennende
- trygge
- besparende
- skalerbarhet
- Skala
- skalering
- Vitenskap
- sikkerhet
- sett
- Del
- delt
- Kort
- Enkelt
- Størrelse
- sove
- Smart
- smart kontrakt
- smarttelefon
- So
- Software
- soliditet
- Solutions
- LØSE
- Rom
- utgifter
- Begynn
- startet
- Tilstand
- Stater
- vellykket
- system
- Systemer
- Teknologi
- test
- tid
- tokens
- topp
- Torrent
- Transaksjonen
- Transaksjoner
- Stol
- oppdateringer
- Brukere
- verdi
- Verifisering
- Visa
- W
- HVEM
- ord
- Arbeid
- virker
- verdt
- X