De beginnershandleiding die ik een paar maanden geleden leuk had gevonden voordat ik me in dit spul verdiepte
Wat je nodig hebt:
- een computerwetenschappelijke achtergrond
- de basis van Ethereum
- de basis van calculus (optimalisatie van beperkingen)
Wat krijg je:
- de basis van zero-knowledge SNARKs
- de basis van Merkle-bomen
- hoe Ethereum dankzij SNARKs kon opschalen naar duizenden transacties per seconde
SNARKs stellen een proefpersoon in staat om aan een verificateur te bewijzen dat zij / hij een oplossing W heeft voor het probleem F met gedeelde / bekende invoer X, zonder W.
Het vinden van de oplossing voor het probleem kan een enorme hoeveelheid rekenkracht en geheugen vergen.
Dus de Verifier kan er in principe 100% zeker van zijn dat de Prover goed heeft gewerkt (en een oplossing heeft gevonden), zonder de klus zelf te herhalen om de oplossing te controleren, noch de oplossing te kennen. Het is magie!
Het proces bestaat uit 3 stappen:
- ORGANISATIE - Het probleem F (dat moet worden uitgedrukt als een kwadratisch rekenprogramma, zie hieronder) is voorbereid voor SNARKs. Dit proces vergt zeer veel geheugen en computerintensief, afhankelijk van de complexiteit van het probleem (→ het aantal inputs en beperkingen → de dimensie van de matrix van het probleem van tevredenheid met beperkingen). De speler die de Setup doet (kan de Verifier zelf zijn) moet door alle partijen worden vertrouwd, aangezien de output van de Setup wordt gebruikt in de volgende fasen. De installatie wordt meestal gedaan met libsnark, een C ++ -bibliotheek die de meest populaire implementatie is voor zkSNARKs.
- RIJZEN - De Prover, die een oplossing W heeft voor het probleem F met gedeelde ingangen X (misschien heeft hij / zij enorme hoeveelheden CPU en geheugen uitgegeven om het te vinden!), Gebruikt libsnark en de output van de Setup fase om een bewijs te creëren 𝚷. Dit proces vergt beslist veel geheugen en computerintensief (afhankelijk van de complexiteit van het probleem, zoals hierboven). De omvang van de output (dwz bewijs 𝚷) is daarentegen beknopt en constant, onafhankelijk van de complexiteit van het probleem. De proefpersoon moet vertrouwen wie de installatiefase heeft gedaan, aangezien hij / zij de output ervan gebruikt ...
- VERIFICEREN - Een verificateur - die als input de output van de setup-fase, gedeelde inputs X en bewijs 𝚷 geeft - controleert het bewijs. Als de verificatie slaagt, slaagde de proefpersoon erin om aan een verificateur te bewijzen dat hij / zij de oplossing W heeft gevonden voor het probleem F… zonder W te onthullen! Het leuke is dat niet alleen het bewijs beknopt is en altijd dezelfde lengte heeft .., het verificatieproces is snel en helemaal niet geheugen / rekenintensief. In tegenstelling tot de twee voorgaande fasen ... kan de verificatie eenvoudig worden uitgevoerd met een smartphone in milliseconden!
Een goede samenvatting ((bron)):
Hoe kan dit gebeuren? Nou, het is Merlijn-magie! Als je de wiskunde hierachter wilt begrijpen, begin vanaf hier.
Hoe kan ik mijn software omzetten in een kwadratisch rekenprogramma?
Zoals hierboven vermeld, moet het probleem F van de installatiefase een kwadratisch rekenprogramma zijn. Regels van het spel zijn moeilijk:
- De invoer van uw software moet uit cijfers bestaan. Converteer uw spullen (arrays, strings, enz.) Naar getallen. Dat is triviaal.
- Een "kwadratisch beperkt stelsel van vergelijkingen" betekent:
waarbij x de n-dimensionale vector van uw invoer is, m het aantal beperkingen (dwz het aantal vergelijkingen van uw systeem), C de n-bij-n coëfficiënten Matrix is en q een n-dimensionale coëfficiëntenvector. Als je niet van matrix en vectoren houdt, is hier het geval n = 3 en m = 2 (3 ingangen, 2 beperkingen):
- De implementatie is een rekenkundig circuit, wat betekent dat de uitkomst is Probleem opgelost (het systeem is opgelost, dwz alle polynomen zijn gelijk aan 0) of Probleem niet opgelost (alle andere gevallen). Met andere woorden: "deze inputs zijn / zijn niet een van de oplossingen voor dit probleem".
- C₁, C₂, ..., C𝚖, q₁, q₂, ..., q𝚖-coëfficiënten zijn de beperkingen van het systeem. Dit is in feite wat uw software definieert. Verander ze ... en je krijgt een andere software! Terugkomend op hoe SNARKs werken: C₁, C₂, ..., C𝚖, q₁, q₂, ..., q𝚖 zijn de input van de Setup-fase. De output van de Setup-fase (die je nodig hebt voor Proving and Verifiëren) is daarom strikt gerelateerd aan die C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 en werkt alleen voor dat probleem. Als u ze wijzigt, definieert u een andere software / een ander probleem en moet u de installatiefase opnieuw uitvoeren! x₁, x₂,…, x𝗇 zijn de variabelen (dwz wat u moet raden om de oplossing van een systeem te krijgen). Dus als we zeggen "Beste proefpersoon, kun je alstublieft een geheime oplossing W vinden voor probleem F met gedeelde / openbare ingangen X", dan bedoelen we bijvoorbeeld "Beste proefpersoon, kun je de x₁, x₂, ..., x𝗇 waarden vinden die het systeem oplossen met bijvoorbeeld x₇ = 2393, x₅₂₆ = 5647? " U kunt doen wat u wilt met alle x𝗇, behalve x₇ en x₅₂₆, die zijn beperkt tot de gedeelde / openbare invoer.
Het is een zwaar leven, maar je kunt het overleven ... Als je lussen nodig hebt, kun je ze uitvouwen door dezelfde operatie meerdere keren te herhalen. Of als je bijvoorbeeld x₁⁴ x₂⁵ nodig hebt, definieer je een nieuwe invoer x₃ = x₁⁴ x₂⁵ en gebruik je x₃ in je constraints. Het draait allemaal om het toevoegen van variabelen en beperkingen ... Zelfs voor vrij eenvoudige software is het gemakkelijk om honderden miljoenen of miljarden invoer en beperkingen te bereiken!
Wil meer weten? Lezen hier. En bekijk ook deze basic code_to_r1cs.py van ethereum / onderzoek.
Wat is een Merkle-boom?
Een hash-functie is een regel die een invoer van willekeurige grootte toewijst aan een uitvoer met een vaste grootte. We zouden een vrij nutteloze hash-functie kunnen bedenken "Voeg de eerste twee samen met de laatste twee letters" die "Woody Allen" omzet in "Woen" en "Paul McCartney" in "Paey".
Een Merkle-boom is een datastructuur waarin elke ouder de hasj is van zijn twee zonen. Bovenaan vind je de Root, de hash van de twee zonen van niveau 1. Onderaan is elk blad de hash van een externe input.
Gebruikmakend van onze fictieve "Woody Allen" → "Woen" hash-functie:
Wanneer een blad verandert, wordt de wijziging tot aan de wortel gepropageerd. Als ANTHONY verandert, veranderen ook ANNY (blad), CENY en CECO (Root). Welk blad ook verandert, de wortel verandert ook.
U hebt niet de hele boom nodig om de wortel opnieuw te berekenen. In ons voorbeeld, als ANTHONY verandert en je zowel JACO als CECILY kent, kun je de Root gemakkelijk herberekenen, zelfs als je JAMES, MARCO, JAES en MACO volledig negeert. Voor enorme bomen scheelt dit veel tijd!
So what?
Merkle-bomen zijn geweldig voor controles van de gegevensintegriteit. Meestal: u weet wat de geldige root is en u controleert of de ontvangen gegevens overeenkomen met die root. Bijvoorbeeld: een vertrouwde partij die je niet de volledige dataset van de voornamen van mensen op aarde kan geven (geen tijd, geen bandbreedte of misschien heeft zij / hij helemaal geen data) geeft je alleen de root (bijv. "CECO"). Nawoord: u krijgt miljoenen voornamen, met verwijzing naar het bladnummer, door duizenden niet-vertrouwde partijen. Welnu, aangezien u de juiste root heeft, kunt u controleren op wie u kunt vertrouwen, op wie u nepgegevens ontvangt ...
Merkle-bomen maken ook deel uit van uw leven! Wanneer u een Torrent-bestand van 3 GB downloadt, wordt uw bestand opgedeeld in miljoenen kleine stukjes. De hasj van elke brok wordt in een blad bewaard. Omdat u weet wat de geldige root van de stamboom is, kunt u elke keer dat u een deel van het bestand door iemand ontvangt, controleren of het correct is. Als dat niet het geval is, kunt u hetzelfde stuk aan iemand anders vragen.
Je kunt dat zelfs doen als je de hele boom / alle bladeren nog niet hebt gedownload: als je weet dat de root CECO is en je vertrouwt JACO ... als je het stuk ANTHONY ontvangt, kun je het verifiëren, zelfs als je het nog niet hebt gedownload maar de brokken MARCO en JAMES.
Waarom Merkle-bomen nuttig zijn in gedistribueerde grootboektechnologie is eenvoudig: u gebruikt alleen consensusprotocollen (langzaam, duur) om consensus te bereiken over de root. Dan kunnen de niet-vertrouwde knooppunten van het netwerk efficiënt en direct gegevens delen… en kunnen ze veilig slapen dankzij integriteitscontroles met de Root.
Toen God Ethereum vroeg om 2 superkrachten te kiezen: beveiliging, schaalbaarheid en decentralisatie ... offerde Ethereum schaalbaarheid op. Eigenlijk is er geen sterke limiet voor "transacties per seconde": de limiet betreft de hoeveelheid gas van elk blok - dat wil zeggen, vereenvoudigd, het aantal bewerkingen dat ik in elk blok kan uitvoeren. Deze limiet is 8 miljoen gas. Dat kan veel 'kleine' transacties betekenen (geen gegevens die aan de transacties zijn gekoppeld, geen bewerkingen die op die gegevens moeten worden uitgevoerd) of enkele grote transacties. Het is aan de knooppunten van Ethereum, die transacties indienen, en aan de mijnwerkers van Ethereum, die in het blok de transacties opnemen die meer betalen.
Een blok wordt gedolven elk ~ 15 seconden. Dat betekent ~ 32 miljoen gas per minuut, wat absoluut niet genoeg is als we willen dat Ethereum's dapps mainstream worden.
Trouwens: stop met die vervelende vergelijkingen tussen Ethereum en Visa. Een gecentraliseerd systeem zal dat wel doen altijd sneller zijn dan Ethereum… door ontwerp! Ze doen verschillende dingen en je hebt ze nodig in verschillende situaties. Als u geen decentralisatie en een omgeving zonder vertrouwen nodig heeft ... kiest u natuurlijk Visa. Kortom: het feit dat je blender sneller draait dan je wasmachine betekent niet dat je je broek ook in een blender reinigt!
Laten we de puzzel in elkaar zetten! Stel u voor dat u dankzij SNARKs vele kleine transacties in één grote transactie zou kunnen 'comprimeren'. Als het gas dat door deze grote transactie wordt uitgegeven, minder is dan de som van het gas dat door de kleine transacties wordt uitgegeven, betekent dat dat u gas bespaart.
En gas besparen betekent:
- Gebruikers geven over het algemeen minder uit aan transacties → Dit zou een zetje zijn voor het hele ecosysteem
- Meer spullen in een blok kunnen stoppen → Ethereum draait sneller dan je blender!
Hoe werkt het?
Er zijn gebruikers, een relayer (of meer relayers) die transacties samenvoegt en een slim contract.
- Gebruikers die deze game willen spelen, sturen hun Ether (of tokens) naar een openbaar gecontroleerd smart contract. Voor elke nieuwe speler wordt een nieuw blad in een Merkle-boom gemaakt. Het blad bevat informatie over de eigenaar van de Ether (zijn / haar adres, dat ook de openbare sleutel is), de hoeveelheid Ether en nonce (de transactieteller van dat account, wat 0 is wanneer het blad wordt toegevoegd)
- Wanneer A Ether naar B wil sturen (ze hebben allebei een blad / account nodig in het slimme contract), pakt A een transactie in, die het adres van de oppompen vanaccount, het naar account, het nuntius van de van-rekening, de bedragen van over te dragen Ether en de handtekening van de transactie (uiteraard ondertekend met de privésleutel van de rekening "van"). Hij / zij stuurt vervolgens de verpakte transactie naar de relayer.
- De relayer verzamelt alle transacties die zijn ontvangen in een bepaald tijdvenster (bijv. Een uur), werkt de Merkle-boom bij met de bedragen van de nieuwe saldi en creëert een SNARK-bewijs dat bewijst dat alle handtekeningen en de wortel van de nieuwe Merkle-boom geldig zijn. De relayer stuurt eindelijk de nieuwe staat en het bewijs naar het slimme contract.
- Het slimme contract valideert de Proof on-chain. Als het geldig is, wordt de Merkle-boomwortel van de nieuwe staat opgeslagen in het interne geheugen van het contract.
Kortom, de Merkle-boomwortel geeft de volledige staat van alle accounts weer. En je kunt het niet veranderen (= geld stelen), tenzij je de geldigheid kunt bewijzen van de handtekeningen waarvan de transacties naar de nieuwe staat leiden, samengevat door de nieuwe root die je indient.
In een notendop: gebruikers hebben supersnelle en bijna gratis transacties, zoals op Coinbase, zonder de relayer te hoeven vertrouwen, die niets kan doen, in tegenstelling tot Coinbase, zonder uw handtekening.
Het is een niet-bewarende zijketen waarvan de toestand wordt samengevat door een Merkle-boomwortel.
Laten we wat we hierboven hebben geleerd over SNARKs in verband brengen met wat we zojuist hebben besproken over schalen. Er zijn verschillende manieren om dat te doen. Ik vergelijk 2 recepten: Vitalik's versie en barryWhiteHat's versie.
De SETUP wordt gedaan door ...
De man die het project start, die ook het slimme contract maakt. Hoe beter het is, hoe beter. Je moet hem / haar vertrouwen ... het is een vertrouwde installatie!
Het slimme contract bespaart ...
2 Merkle-roots (bytes32-waarden): de eerste boom bevat de adressen van de rekeningen (openbare handtekeningen), de saldi en nonces van de tweede rekeningen
RIJZEN wordt gedaan door ...
De relayer
De relayer stuurt naar het slimme contract ...
- de 2 Merkle-wortels van de nieuwe staat (adressenboom en balansen + noncesboom)
- de lijst met transacties, zonder handtekeningen. “Elke transactie kost 68 gas per byte. Daarom kunnen we voor een reguliere overboeking verwachten dat de marginale kosten 68 * 3 (vanaf) + 68 * 3 (tot) + 68 * 1 (vergoeding) + 68 * 4 + 4 * 2 (bedrag) + 68 * 2 zijn (nonce), of 892 gas "
BEWIJZEN van de bekende inputs van het proces zijn ...
- de 2 Old State Merkle-wortels
- de 2 wortels van de nieuwe staat Merkle
- transacties lijst
PROVING proces bewijst dat ...
Gegeven
- de 2 Old State Merkle-wortels (al opgeslagen in het contract)
- de 2 wortels van de nieuwe staat Merkle (verzonden in de aggr. transactie)
- de transactielijst (verzonden in de aggr. transactie)
… De relayer heeft geldige handtekeningen om met die transacties van staat met 2 oude wortels naar staat met 2 nieuwe wortels te gaan.
VERIFYING wordt gedaan door ...
Het slimme contract (gecodeerd in degelijkheid, vyper, zoals je wilt!)
De bekende invoer van het VERIFYING-proces is ...
Hetzelfde PROVING's proces bekende inputs, duidelijk…!
Grenzen aan schaalbaarheid
Elke geaggregeerde transactie gebruikt 650 gas voor SNARK-verificatie (vaste kosten) plus ~ 900 gas marginale kosten per transactie (het kost om gegevens te verzenden!). Dus door het hele blok te gebruiken, kan de relayer maximaal:
wat betekent ~ 544 tx per seconde
barryWhiteHat's versie
De SETUP wordt gedaan door ...
De man die het project start.
Het slimme contract bespaart ...
1 Merkle-wortel met de huidige staat. Elk blad is de gehashte status van een account.
Willen en je merk te creëren een account?
state = AccountState (pubkey, saldo, nonce)
state.index = self._tree.append (state.hash ())
RIJZEN wordt gedaan door ...
De relayer
De relayer stuurt naar het slimme contract ...
- bewijs 𝚷
- de nieuwe staat Merkle-wortel
- bewijs 𝚷
BEWIJZEN van de bekende inputs van het proces zijn ...
- de oude staat Merkle-wortel
- de nieuwe staat Merkle-wortel
PROVING proces bewijst dat ...
Gegeven
- de oude Merkle-wortel (al opgeslagen in het contract)
- de nieuwe Merkle-root (senti in de aggr. transactie)
… De relayer heeft een lijst met transacties met geldige handtekeningen om van staat met oude root naar staat met nieuwe root te gaan
VERIFYING wordt gedaan door ...
Het slimme contract (gecodeerd in degelijkheid, vyper, zoals je wilt!)
De bekende invoer van het VERIFYING-proces is ...
Hetzelfde PROVING's proces bekende inputs, duidelijk…!
Grenzen aan schaalbaarheid
De relayer stuurt geen transactiegegevens naar het slimme contract (wat duur is), dus de limiet is eigenlijk de hoeveelheid gas om het SNARK-bewijs te verifiëren.
Hij noemt Howard Wu's werk over het uitvoeren van SNARK's PROVING-fase op gedistribueerde systemen, barryWhiteHat optimistisch stelt dat het mogelijk is om 16666 transacties te bevestigen in een enorme SNARK (1 miljard beperkingen!).
barryWhiteHat ook denkt het is mogelijk om bewijs 𝚷 on-chain te verifiëren met 500k gas, wat betekent dat je 16 SNARKs (8 miljoen / 500k) per blok kunt plaatsen, wat ~ 1.07 SNARKs per seconde… wat ~ 17,832 tx per seconde betekent (16,666 * 1.07).
Tot de oneindigheid en verder
- Het enige dat blinkt is geen goud / 1. De hoeveelheid rekenkracht en geheugen die je nodig hebt in de Proving-fase kan letterlijk schokkend zijn. Vooral in de versie van barryWhiteHat, waar een deel van de complexiteit van de keten wordt gehaald. barry schrijft "Op een laptop met 7 GB werkgeheugen en 20 GB swapruimte heeft het moeite om 20 transacties per seconde te verzamelen". Als het doel 17,832 tx per seconde is ... LOL. Dit introduceert niet-triviale parallelle rekenuitdagingen. Maar als de gemiddelde $ kosten per transactie veel goedkoper zijn dan de gewone no-SNARKs-optie ... is het spel de kaars waard.
- Het enige dat blinkt is geen goud / 2. Er is een relevant probleem met de beschikbaarheid van gegevens! Omdat alleen de root van de boom in het contract wordt opgeslagen, moet u er zeker van zijn dat er altijd een volledige versie van de boom (of, het is hetzelfde, de volledige transactiegeschiedenis) beschikbaar is. Als er geen gegevens beschikbaar zijn, kan de relayer, zelfs met geldige ondertekende transacties, niets doen omdat hij / zij de oude staat → transacties → nieuwe staat niet kan bewijzen.
- Om ervoor te zorgen dat de relayer betrouwbaar is en Ethers in het contract dezelfde waarde van Ethers buiten het contract heeft (liquiditeitsprobleem) ... moeten gebruikers in staat zijn om geld uit het smart contract op te nemen wanneer ze dat willen, zonder te vertrouwen op een (specifieke) relayer. Hoe? Dit valt niet onder dit 101-bericht, maar je kunt hierover lezen in de bijgevoegde links.
- Wilt u meer weten over hoe de huidige staat (adressen, saldi en nonces) kan worden afgehandeld met een Merkle-boom? Een blad toevoegen, een blad bijwerken, enz.? Uitchecken deze bibliotheek (testbestand hier) die deze onderliggende waarde gebruikt module. Bedankt HarryR!
- Wilt u uw persoonlijke Ethereum-SNARKs-omgeving opzetten? Laten we off-chain beginnen met C ++ (instellen, testen, verifiëren) hier. Dan kun je naar Ethereum gaan (vergeet niet, alleen de verificatie gebeurt on-chain!) Met Zokrates (repo documentatie om mee te beginnen).
- Hoe zit het met het gebruik van RSA-accumulatoren in plaats van Merkle-bomen? Google "Rsa accumulators ethereum" beginnen…
Geniet!
Twitter @marco_derossi
- 7
- Account
- Alles
- onder
- beschikbaarheid
- De Basis
- Miljard
- gevallen
- verandering
- Controles
- coinbase
- computergebruik
- Overeenstemming
- contract
- Kosten
- Actueel
- Huidige toestand
- DApps
- gegevens
- gegevensset
- Decentralisatie
- Afmeting
- Gedistribueerd grootboek
- gedistribueerde grootboektechnologie
- Milieu
- Ether
- ethereum
- EU
- EV
- nep
- Tot slot
- Voornaam*
- Gratis
- functie
- spel
- GAS
- GitHub
- Vrijgevigheid
- Tijdloos goud
- goed
- Kopen Google Reviews
- groot
- gids
- hachee
- hier
- Hoge
- geschiedenis
- Hoe
- hr
- HTTPS
- reusachtig
- Honderden
- ia
- index
- informatie
- IP
- IT
- Jobomschrijving:
- sleutel
- laptop
- Groot
- leiden
- Grootboek
- Niveau
- LG
- Bibliotheek
- Liquiditeit
- Lijst
- Hoofdstroom
- Maps
- Medium
- miljoen
- Mijnwerkers
- geld
- maanden
- Meest populair
- beweging
- namen
- netwerk
- knooppunten
- nummers
- Operations
- bestellen
- Overige
- eigenaar
- Betaal
- Mensen
- speler
- Populair
- energie
- privaat
- private Key
- Programma
- project
- bewijs
- bewijst
- publiek
- public Key
- samenvatting
- rsa
- reglement
- lopend
- veilig
- besparing
- Schaalbaarheid
- Scale
- scaling
- Wetenschap
- veiligheid
- reeks
- Delen
- gedeeld
- Bermuda's
- Eenvoudig
- Maat
- slaap
- slim
- slim contract
- smartphone
- So
- Software
- stevigheid
- Oplossingen
- OPLOSSEN
- Tussenruimte
- Uitgaven
- begin
- gestart
- Land
- Staten
- geslaagd
- system
- Systems
- Technologie
- proef
- niet de tijd of
- tokens
- top
- stortvloed
- transactie
- Transacties
- Trust
- updates
- gebruikers
- waarde
- Verificatie
- visum
- W
- WIE
- woorden
- Mijn werk
- Bedrijven
- waard
- X