Hvad skal du bruge:
- en datalogisk baggrund
- det grundlæggende i Ethereum
- det grundlæggende i calculus (begrænsningsoptimering)
Hvad får du:
- det grundlæggende i nul-viden SNARKs
- det grundlæggende i Merkle træer
- hvordan Ethereum kunne skalere til tusindvis af transaktioner i sekundet takket være SNARKs
SNARK'er giver en Beviser mulighed for at bevise over for en Verifikator, at hun/han har en løsning W på problemet F med delte/kendte input X, uden at afsløre W.
At finde løsningen på problemet kan kræve en enorm mængde regnekraft og hukommelse.
Så Verifieren kan grundlæggende være 100% sikker på, at Proveren har fungeret korrekt (og fundet en løsning), med hverken at gøre arbejdet igen for sig selv for at tjekke løsningen eller overhovedet at kende løsningen. Det er magi!
Processen har 3 trin:
- SETUP — Opgaven F (der skal udtrykkes som kvadratisk aritmetisk program, se nedenfor) er forberedt til SNARK'er. Denne proces er meget høj hukommelses- og computerintensiv afhængig af problemets kompleksitet (→ Antallet af input og begrænsninger → Dimensionen af matrixen af problemet med begrænsningstilfredshed). Den spiller, der laver opsætningen (kan være selve Verifikatoren) skal have tillid til af alle parter, da outputtet fra opsætningen bruges i de næste faser. Opsætningen udføres normalt vha libsnark, et C++-bibliotek, som er den mest populære implementering for zkSNARK'er.
- Beviser — Prover, som har en løsning W på problemet F med delte input X (måske har hun/han brugt enorme mængder CPU og hukommelse på at finde det!), bruger libsnark og outputtet af Opsætning fase for at skabe et bevis 𝚷. Denne proces er bestemt høj hukommelse og computerintensiv (afhængig af kompleksiteten af problemet, som ovenfor). Størrelsen af outputtet (dvs. bevis 𝚷) er i stedet kortfattet og konstant uafhængigt af problemets kompleksitet. Beviseren skal stole på, hvem der har udført opsætningsfasen, da hun/han bruger dens output...
- VERIFICERER — En verifikator — der som input giver output fra opsætningsfasen, delte input X og proof 𝚷 – kontrollerer beviset. Hvis verifikationen lykkes, lykkedes det Beviseren at bevise over for en Verifikator, at hun/han har fundet løsningen W på problemet F... uden at afsløre W! Den gode del er, at ikke kun beviset er kortfattet og altid har samme længde.., verifikationsprocessen er hurtig og slet ikke hukommelses-/computerkrævende. I modsætning til de to foregående faser... kan verifikationen nemt udføres med en smartphone på millisekunder!
En god opsummering (kilde):
Hvordan kan dette ske? Nå, det er Merlin-magi! Hvis du ønsker at få matematikken bag dette, start herfra.
Hvordan kan jeg transformere min software til et kvadratisk aritmetikprogram?
Som nævnt ovenfor skal opsætningsfasens problem F være et kvadratisk aritmetisk program. Spillereglerne er hårde:
- Din softwares input skal være tal. Konverter dine ting (arrays, strenge osv.) til tal. Det er trivielt.
- Et "kvadratisk begrænset system af ligninger" betyder:
hvor x er den n-dimensionelle vektor af dine input, m er antallet af begrænsninger (dvs. antallet af ligninger for dit system), C er n-for-n koefficienterne Matrix og q er en n-dimensional koefficientvektor. Hvis du ikke kan lide matrix og vektorer, her er tilfældet n = 3 og m = 2 (3 input, 2 begrænsninger):
- Implementeringen er et aritmetisk kredsløb, hvilket betyder, at resultatet er Problem løst (systemet er løst, dvs. alle polynomier er lig med 0) eller Problem ikke løst (alle de andre tilfælde). Med andre ord: "disse input er/er ikke en af løsningerne på dette problem".
- C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖-koefficienter er systemets begrænsninger. Det er dybest set, hvad der definerer din software. Skift dem... og du får en anden software! For at komme tilbage til, hvordan SNARK'er fungerer: C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 er input til opsætningsfasen. Outputtet fra opsætningsfasen (som du har brug for til at bevise og verificere) er derfor strengt relateret til disse C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 og fungerer kun for det problem. Hvis du ændrer dem, definerer du et andet software/problem, og du skal køre opsætningsfasen igen! x₁, x₂, …, x𝗇 er variablerne (dvs. hvad du skal gætte for at få et systems løsning). Så når vi siger "Kære Prover, kan du venligst finde en hemmelig løsning W for problem F med delte/offentlige input X" mener vi for eksempel "Kære Prover, kan du finde x₁, x₂, …, x𝗇 værdierne, der løser systemet med for eksempel x₇ = 2393, x₅₂₆ = 5647?" Du kan gøre, hvad du vil med alle x𝗇, undtagen x₇ og x₅₂₆, som er begrænset til de delte/offentlige input.
Det er et hårdt liv, men du kan overleve... Hvis du har brug for loops, kan du folde dem ud ved at gentage den samme operation mange gange. Eller hvis du for eksempel har brug for x₁⁴ x₂⁵, definerer du et nyt input x₃ = x₁⁴ x₂⁵ og bruger x₃ i dine begrænsninger. Det handler om at tilføje variabler og begrænsninger... Selv for ret simpel software er det nemt at nå hundreder af millioner eller milliarder af input og begrænsninger!
Vil du vide mere? Læs link.. Og tjek også denne grundlæggende code_to_r1cs.py fra ethereum/forskning.
Hvad er et Merkle-træ?
En hash-funktion er en regel, der kortlægger et input af vilkårlig størrelse til et output med fast størrelse. Vi kunne opfinde en ret ubrugelig hash-funktion "Sæt de første to sammen med de sidste to bogstaver", som forvandler "Woody Allen" til "Woen" og "Paul McCartney" til "Paey".
Et Merkle-træ er en datastruktur, hvor hver forælder er dens to sønners hash. Øverst finder du Roden, som er hashen af de to sønner på niveau 1. Nederst er hvert blad hash af en ekstern input.
Ved at bruge vores fiktive "Woody Allen" → "Woen" hash-funktion:
Når et blad ændres, forplantes modifikationen op til roden. Hvis ANTHONY ændrer sig, ændres også ANNY (blad), CENY og CECO (Root). Uanset hvilket blad der ændres, ændres roden også.
Du behøver ikke hele træet for at genberegne roden. I vores eksempel, hvis ANTHONY ændrer sig, og du kender både JACO og CECILY, kan du nemt genberegne Roden, selvom du fuldstændig ignorerer JAMES, MARCO, JAES og MACO. For store træer sparer dette meget tid!
Og hvad så?
Merkle-træer er fantastiske til kontrol af dataintegritet. Normalt: du ved, hvad der er den gyldige rod, og du tjekker, at de modtagne data matcher den rod. For eksempel: en betroet part, som ikke kan give dig hele datasættet af fornavnene på mennesker på Jorden (ingen tid, ingen båndbredde eller måske har hun/han slet ikke dataene) giver dig kun roden (f.eks. "CECO"). Efterord: du modtager millioner af fornavne, med henvisning til bladnummeret, af tusindvis af upålidelige parter. Nå, da du har den rigtige rod, kan du tjekke, hvem du kan stole på, hvem der giver dig falske data...
Merkle træer er også en del af dit liv! Når du downloader en 3GB Torrent-fil, er din fil opdelt i millioner af små bidder. Hashen af hver del gemmes i et blad. Da du ved, hvilken der er den gyldige rod af træet, kan du kontrollere, om den er korrekt, hver gang du modtager en del af filen af nogen. Hvis det ikke er det, kan du spørge den samme del til en anden.
Du kan gøre det, selvom du endnu ikke har downloadet hele træet/alle bladene: hvis du ved, at roden er CECO, og du stoler på JACO... når du modtager stykket ANTHONY, kan du bekræfte det, selvom du ikke har downloadet dog bidderne MARCO og JAMES.
Hvorfor Merkle-træer er nyttige i distribueret hovedbogsteknologi er ligetil: du bruger konsensusprotokoller (langsomme, dyre) kun for at nå konsensus om roden. Så kan netværkets upålidelige noder effektivt og direkte dele data... og kan sove trygt og godt takket være integritetstjek med roden.
Da Gud bad Ethereum om at vælge 2 supermagter blandt sikkerhed, skalerbarhed og decentralisering... Ethereum ofrede skalerbarhed. Faktisk er der ingen stærk grænse for "transaktioner pr. sekund": loftet vedrører mængden af gas i hver blok - hvilket forenklet er mængden af operationer, jeg kan udføre i hver blok. Denne grænse er 8 millioner gas. Det kan betyde mange "små" transaktioner (ingen data knyttet til transaktionerne, ingen operationer, der skal udføres på disse data) eller få store transaktioner. Det er op til Ethereums noder, som sender transaktioner, og til Ethereums minearbejdere, som inkluderer de transaktioner, der betaler mere i blokken.
En blok er udvundet hver ~15 sekunder. Det betyder ~32 millioner gas i minuttet, hvilket bestemt ikke er nok, hvis vi ønsker, at Ethereums dapps skal gå mainstream.
Forresten: stop med de kedelige sammenligninger mellem Ethereum og Visa. Et centraliseret system vil altid være hurtigere end Ethereum… ved design! De laver forskellige ting, og du har brug for dem i forskellige situationer. Hvis du ikke har brug for decentralisering og et miljø uden tillid... skal du selvfølgelig vælge Visa. Kort sagt: det faktum, at din blender roterer hurtigere end din vaskemaskine, betyder ikke, at du vil rense dine bukser i en blender!
Lad os lægge puslespillet sammen! Forestil dig, at du kunne "komprimere" mange små transaktioner i en stor transaktion takket være SNARK'er. Hvis den gas, der bruges ved denne store transaktion, er mindre end summen af den gas, der bruges af de små transaktioner, betyder det, at du sparer gas.
Og at spare på gas betyder:
- Brugere, der samlet set bruger mindre på transaktioner → Dette ville være et skub for hele økosystemet
- At kunne lægge flere ting i en blok → Ethereum snurrer hurtigere end din blender!
Hvordan virker det?
Der er brugere, en relayer (eller flere relayers), der samler transaktioner og en smart kontrakt.
- Brugere, der er villige til at spille dette spil, sender deres Ether (eller tokens) til en offentligt revideret smart kontrakt. For hver ny spiller oprettes et nyt blad i et Merkle-træ. Bladet indeholder oplysninger om Etherens ejer (hendes/hans adresse, som også er den offentlige nøgle), mængden af Ether og nonce (transaktionernes tæller på den konto, som er 0, når bladet tilføjes)
- Når A vil sende Ether til B (de skal begge have et blad/konto i den smarte kontrakt), pakker A en transaktion, som inkluderer adressen på frakonto, den til konto, den nuntius af fra-kontoen, den beløb af Ether, der skal overføres og signatur af transaktionen (underskrevet med den private nøgle til "fra"-kontoen, naturligvis). Hun/han sender derefter den pakkede transaktion til relæet.
- Relayeren aggregerer alle de modtagne transaktioner i et givent tidsvindue (f.eks. en time), opdaterer Merkle-træet med de nye saldi's beløb og skaber et SNARK-bevis, som beviser, at alle signaturer og det nye Merkle-træs rod er gyldige. Relæet sender endelig den nye tilstand og beviset til den smarte kontrakt.
- Den smarte kontrakt validerer Proof on-chain. Hvis det er gyldigt, gemmer det Merkle-træets rod fra den nye stat i kontraktens interne hukommelse.
Grundlæggende viser Merkle-træroden hele tilstanden af alle konti. Og du kan ikke ændre det (= stjæle penge), medmindre du kan bevise gyldigheden af de signaturer, hvis transaktioner fører til den nye tilstand opsummeret af den nye rod, du indsender.
Kort sagt: brugere har superhurtige og næsten gratis transaktioner, som på Coinbase, uden at de behøver at stole på relayeren, som ikke kan gøre noget, i modsætning til på Coinbase, uden din signatur.
Det er en ikke-frihedsberøvende sidekæde, hvis tilstand er opsummeret af en Merkle-trærod.
Lad os forbinde det, vi lærte ovenfor om SNARK'er, med det, vi lige har diskuteret om skalering. Der er forskellige måder at gøre det på. Jeg vil sammenligne 2 opskrifter: Vitaliks udgave og barryWhiteHats udgave.
OPSÆTNING er udført af...
Fyren, der starter projektet, som også laver den smarte kontrakt. Jo mere auditerbart det er, jo bedre. Du bør stole på hende/ham... det er en betroet opsætning!
Den smarte kontrakt sparer...
2 Merkle-rødder (bytes32-værdier): det første træ indeholder kontoadresser (offentlige signaturer), det andet kontos saldi og nonces
BEVISNING udføres af...
Relæet
Relæet sender til den smarte kontrakt...
- de 2 Merkle rødder af den nye stat (adresser træ og balancer+nonces træ)
- listen over transaktioner, uden underskrifter. "Hver transaktion koster 68 gas pr. byte. For en almindelig overførsel kan vi derfor forvente, at marginalomkostningerne er 68 * 3 (fra) + 68 * 3 (til) + 68 * 1 (gebyr) + 68 * 4 + 4 * 2 (beløb) + 68 * 2 (ikke) eller 892 gas"
PROVING processens kendte input er...
- de 2 gamle stats Merkle rødder
- de 2 Nye stat Merkle rødder
- transaktionsliste
PROVING-processen beviser, at...
I betragtning af
- de 2 gamle stats Merkle rødder (allerede gemt i kontrakten)
- de 2 Nye stats Merkle rødder (sendt i aggr. transaktionen)
- transaktionslisten (sendes i den samlede transaktion)
… relayeren har gyldige signaturer til at flytte fra tilstand med 2 gamle rødder til stat med 2 nye rødder med disse transaktioner.
VERIFIKATION udføres af...
Den smarte kontrakt (kodet i soliditet, vyper, som du vil!)
VERIFICERINGsprocessens kendte input er...
Den samme PROVING's proces kendte input, klart...!
Grænser for skalerbarhed
Hver aggregeret transaktion bruger 650 gas til SNARK-verifikation (faste omkostninger) plus ~900 gas af marginale omkostninger pr transaktion (Det koster at sende data!). Så ved at bruge hele blokken kan relæet højst aggregere:
hvilket betyder ~544 tx pr. sekund
barryWhiteHats udgave
OPSÆTNING er udført af...
Fyren, der starter projektet.
Den smarte kontrakt sparer...
1 Merkle rod med den nuværende stat. Hvert blad er en kontos hash-tilstand.
Ønsker du at skabe En konto?
state = AccountState(pubkey, balance, nonce)
state.index = self._tree.append(state.hash())
BEVISNING udføres af...
Relæet
Relæet sender til den smarte kontrakt...
- bevis 𝚷
- den nye stat Merkle-rod
- bevis 𝚷
PROVING processens kendte input er...
- den gamle stat Merkle-rod
- den nye stat Merkle-rod
PROVING-processen beviser, at...
I betragtning af
- den gamle Merkle-rod (allerede gemt i kontrakten)
- den nye Merkle-rod (senti i den aggr. transaktion)
… relayeren har en liste over transaktioner med gyldige signaturer for at flytte fra tilstand med gammel rod til tilstand med ny rod
VERIFIKATION udføres af...
Den smarte kontrakt (kodet i soliditet, vyper, som du vil!)
VERIFICERINGsprocessens kendte input er...
Den samme PROVING's proces kendte input, klart...!
Grænser for skalerbarhed
Relayeren sender ikke transaktionsdata til den smarte kontrakt (hvilket er dyrt), så grænsen er faktisk mængden af gas for at verificere SNARK-beviset.
Nævner Howard Wu's arbejde om at køre SNARKs PROVING fase på distribuerede systemer, barryWhiteHat optimistisk angiver, at det er muligt at bekræfte 16666 transaktioner i en enorm SNARK (1 milliard begrænsninger!).
barryWhiteHat også mener det er muligt at verificere bevis 𝚷 on-chain med 500k gas, hvilket betyder, at du kan sætte 16 SNARK'er (8 millioner/500k) pr. blok, hvilket er ~1.07 SNARKs pr. sekund... hvilket betyder ~17,832 tx pr. sekund (16,666 * 1.07).
Mod det uendelige univers
- Alt, der glimter, er ikke guld / 1. Mængden af computerkraft og hukommelse, som du har brug for i prøvefasen, kan bogstaveligt talt være chokerende. Især i barryWhiteHats version, hvor en del af kompleksiteten flyttes ud af kæden. skriver barry "På en bærbar computer med 7 GB ram og 20 GB swap-plads har det svært ved at samle 20 transaktioner i sekundet". Nå, hvis målet er 17,832 tx i sekundet... LOL. Dette introducerer ikke-trivielle parallelle beregningsudfordringer. Men hvis den gennemsnitlige $-pris pr. transaktion er langt billigere end den almindelige no-SNARKs-mulighed... er spillet stearinlys værd.
- Alt, der glimter, er ikke guld / 2. Der er et relevant datatilgængelighedsproblem! Da kun træets rod gemmes i kontrakten, skal du være sikker på, at en hel version af træet (eller, det er den samme, hele transaktionshistorikken) altid er tilgængelig. Hvis data ikke er tilgængelige, kan relæet, selv med gyldige signerede transaktioner, ikke gøre noget, fordi hun/han ikke kan bevise Gammel tilstand → Transaktioner → Ny tilstand.
- For at relayeren skal være tillidsløs, og Ethers i kontrakten skal have samme værdi af Ethers udenfor (likviditetsproblem)... skal brugere kunne hæve penge fra den smarte kontrakt, når de vil, uden at stole på en (specifik) relayer. Hvordan? Dette er ikke omfattet af dette 101-indlæg, men du kan læse om dette i de vedlagte links.
- Vil du forstå mere om, hvordan den nuværende tilstand (adresser, saldi og nonces) kan håndteres med et Merkle-træ? Tilføje et blad, opdatere et blad osv.? Tjek ud dette bibliotek (testfil link.) som bruger dette underliggende modul. Tak HarryR!
- Vil du opsætte dit personlige Ethereum-SNARKs miljø? Lad os starte uden for kæden med C++ (opsætning, bevis, verificering) link.. Så kan du flytte til Ethereum (glem ikke, kun verifikationen udføres på kæden!) med Zokrates (repo, dokumentation til at komme i gang med).
- Hvad med at bruge RSA-akkumulatorer i stedet for Merkle-træer? Google "rsa akkumulatorer ethereum" at begynde…
God fornøjelse!
Twitter @marco_derossi
- 7
- Konto
- Alle
- blandt
- tilgængelighed
- Grundlæggende
- Billion
- tilfælde
- lave om
- Kontrol
- coinbase
- computing
- Konsensus
- kontrakt
- Omkostninger
- Nuværende
- Nuværende tilstand
- DApps
- data
- datasæt
- decentralisering
- Dimension
- Distribueret Ledger
- distribueret ledger teknologi
- Miljø
- Ether
- ethereum
- EU
- EV
- falsk
- Endelig
- Fornavn
- Gratis
- funktion
- spil
- GAS
- GitHub
- Give
- Guld
- godt
- stor
- vejlede
- hash
- link.
- Høj
- historie
- Hvordan
- hr
- HTTPS
- kæmpe
- Hundreder
- ia
- indeks
- oplysninger
- IP
- IT
- Job
- Nøgle
- laptop
- stor
- føre
- Ledger
- Niveau
- LG
- Bibliotek
- Likviditet
- Liste
- Mainstream
- Maps
- medium
- million
- minearbejdere
- penge
- måned
- Mest Populære
- bevæge sig
- navne
- netværk
- noder
- numre
- Produktion
- ordrer
- Andet
- ejer
- Betal
- Mennesker
- spiller
- Populær
- magt
- private
- private nøgle
- Program
- projekt
- bevis
- beviser
- offentlige
- offentlig nøgle
- resumé
- rsa
- regler
- kører
- sikker
- besparelse
- Skalerbarhed
- Scale
- skalering
- Videnskab
- sikkerhed
- sæt
- Del
- delt
- Kort
- Simpelt
- Størrelse
- søvn
- Smart
- smart kontrakt
- smartphone
- So
- Software
- soliditet
- Løsninger
- SOLVE
- Space
- udgifterne
- starte
- påbegyndt
- Tilstand
- Stater
- vellykket
- systemet
- Systemer
- Teknologier
- prøve
- tid
- Tokens
- top
- Torrent
- transaktion
- Transaktioner
- Stol
- opdateringer
- brugere
- værdi
- Verifikation
- visum
- W
- WHO
- ord
- Arbejde
- virker
- værd
- X