Vitalik Buterin via de Vitalik Buterin-blog
Dit is een spiegel van het bericht op https://medium.com/@VitalikButerin/zk-snarks-onder-de-motorkap-b33151a013f6
Dit is het derde deel van een reeks artikelen waarin wordt uitgelegd hoe de technologie achter zk-SNARKs werkt; de voorgaande artikelen over kwadratische rekenprogramma's en elliptische curve-paren zijn verplichte lectuur, en dit artikel veronderstelt kennis van beide concepten. Er wordt ook aangenomen dat er basiskennis is over wat zk-SNARK's zijn en wat ze doen. Zie ook Het artikel van Christian Reitwiessner hier voor nog een technische introductie.
In de vorige artikelen hebben we het kwadratische rekenprogramma geïntroduceerd, een manier om elk rekenprobleem weer te geven met een polynomiale vergelijking die veel vatbaarder is voor verschillende vormen van wiskundig bedrog. We hebben ook elliptische curve-paren geïntroduceerd, die een zeer beperkte vorm van homomorfe codering in één richting mogelijk maken, waarmee u gelijkheidscontrole kunt uitvoeren. Nu gaan we beginnen waar we gebleven waren, en gebruiken we elliptische curveparen, samen met een paar andere wiskundige trucs, om een bewijzer in staat te stellen te bewijzen dat hij een oplossing kent voor een bepaalde QAP zonder iets anders te onthullen over de daadwerkelijke oplossing.
Dit artikel gaat in op de Pinokkio-protocol door Parno, Gentry, Howell en Raykova uit 2013 (vaak PGHR13 genoemd); er zijn een paar variaties op het basismechanisme, dus een in de praktijk geïmplementeerd zk-SNARK-schema kan enigszins anders werken, maar de basisprincipes zullen over het algemeen hetzelfde blijven.
Laten we om te beginnen eens kijken naar de belangrijkste cryptografische aanname die ten grondslag ligt aan de veiligheid van het mechanisme dat we gaan gebruiken: de *kennis-van-exponent* aanname.
Kortom, als je een paar punten � en � krijgt, waarbij �⋅�=�, en je krijgt een punt �, dan is het niet mogelijk om op �⋅� te komen, tenzij � op de een of andere manier “afgeleid” is van � dat je weet. Dit lijkt misschien intuïtief voor de hand liggend, maar deze aanname kan feitelijk niet worden afgeleid uit enige andere aanname (bijv. discrete loghardheid) die we gewoonlijk gebruiken bij het bewijzen van de veiligheid van op elliptische curven gebaseerde protocollen, en dus berusten zk-SNARK's in feite op een enigszins een wankeler fundament dan elliptische curve-cryptografie in het algemeen – hoewel het nog steeds stevig genoeg is dat de meeste cryptografen er geen problemen mee hebben.
Laten we nu eens kijken hoe dit kan worden gebruikt. Stel dat er een paar punten (�,�) uit de lucht valt, waarbij �⋅�=�, maar niemand weet wat de waarde van � is. Stel nu dat ik een paar punten (�,�) bedenk waarbij �⋅�=�. Vervolgens impliceert de KoE-aanname dat de enige manier waarop ik dat paar punten had kunnen maken was door � en � te nemen, en beide te vermenigvuldigen met een factor r die ik persoonlijk ken. Merk ook op dat dankzij de magie van elliptische curveparen, het controleren van �=�⋅� vereist eigenlijk geen kennis � – in plaats daarvan kunt u eenvoudig controleren of �(�,�)=�(�,�).
Laten we iets interessants doen. Stel dat er tien paar punten uit de lucht vallen: (�1,�1),(�2,�2)…(�10,�10). In alle gevallen geldt ��⋅�=��. Stel dat ik je dan een paar punten (�,�) geef waarbij �⋅�=�. Wat weet je nu? Je weet dat � een lineaire combinatie is �1⋅�1+�2⋅�2+…+�10⋅�10, waarvan ik de coëfficiënten �1,�2…�10 ken. Dat wil zeggen, de enige manier om tot een dergelijk paar punten (�,�) te komen, is door enkele veelvouden van �1,�2…�10 te nemen en deze bij elkaar op te tellen, en dezelfde berekening te maken met �1,�2… �10.
Merk op dat, gegeven een specifieke set van �1…�10 punten waarvoor u lineaire combinaties wilt controleren, u de bijbehorende �1…�10 punten niet daadwerkelijk kunt creëren zonder te weten wat � is, en als u dat wel weet � is, dan kun je een paar (�,�) maken waarbij �⋅�=� voor wat je maar wilt, zonder de moeite te nemen een lineaire combinatie te maken. Om dit te laten werken is het daarom absoluut noodzakelijk dat degene die deze punten creëert, betrouwbaar is en daadwerkelijk verwijdert zodra hij of zij de tien punten heeft gecreëerd. Dit is waar het concept van een “vertrouwde opstelling” vandaan komt.
Onthoud dat de oplossing voor een QAP een reeks polynomen (�,�,�) is zodat �(�)⋅�(�)−�(�)=�(�)⋅�(�), waarbij:
- � is een lineaire combinatie van een reeks polynomen {�1…��}
- � is de lineaire combinatie van {�1…��} met dezelfde coëfficiënten
- � is een lineaire combinatie van {�1…��} met dezelfde coëfficiënten
De verzamelingen {�1…��},{�1…��} en {�1…��} en de polynoom � maken deel uit van de probleemstelling.
In de meeste praktijkgevallen zijn �,� en � echter extreem groot; voor iets met vele duizenden circuitpoorten, zoals een hashfunctie, kunnen de polynomen (en de factoren voor de lineaire combinaties) vele duizenden termen hebben. Daarom gaan we, in plaats van dat de bewijzer de lineaire combinaties rechtstreeks levert, de truc gebruiken die we hierboven hebben geïntroduceerd om de bewijzer te laten bewijzen dat hij iets levert dat een lineaire combinatie is, maar zonder iets anders te onthullen.
Het is je misschien opgevallen dat de bovenstaande truc werkt op elliptische curvepunten, niet op polynomen. Wat er dus feitelijk gebeurt, is dat we de volgende waarden toevoegen aan de vertrouwde opstelling:
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
Je kunt t zien als een ‘geheim punt’ waarop de polynoom wordt geëvalueerd. � is een “generator” (een willekeurig elliptisch curvepunt dat is gespecificeerd als onderdeel van het protocol) en �,��,�� en �� zijn “giftig afval”, getallen die absoluut koste wat het kost moeten worden verwijderd, of anders wie ze heeft, kan valse proefdrukken maken. Als iemand je een paar punten �, � geeft zodat �⋅��=� (herinnering: we hebben �� niet nodig om dit te controleren, omdat we een koppelingscontrole kunnen doen), dan weet je dat wat ze doen u geeft is een lineaire combinatie van �� polynomen geëvalueerd op �.
Daarom moet de bewijzer tot dusver het volgende geven:
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
Merk op dat de bewijzer eigenlijk niet hoeft te weten (en niet zou moeten weten!) �,��,�� of �� om deze waarden te berekenen; in plaats daarvan zou de bewijzer deze waarden moeten kunnen berekenen, alleen op basis van de punten die we toevoegen aan de vertrouwde opstelling.
De volgende stap is ervoor te zorgen dat alle drie de lineaire combinaties dezelfde coëfficiënten hebben. Dit kunnen we doen door nog een set waarden toe te voegen aan de vertrouwde opstelling: �⋅(��(�)+��(�)+��(�))⋅�, waarbij � een ander getal is dat als “giftig” moet worden beschouwd. afval” en weggegooid zodra de vertrouwde installatie is voltooid. We kunnen de bewijzer dan een lineaire combinatie laten maken met deze waarden met dezelfde coëfficiënten, en dezelfde koppelingstruc als hierboven gebruiken om te verifiëren dat deze waarde overeenkomt met de opgegeven �+�+�.
Tenslotte moeten we bewijzen dat �⋅�−�=�⋅�. Dit doen we nogmaals met een koppelingscontrole:
�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))
Waarbij �ℎ=�⋅�(�). Als het verband tussen deze vergelijking en �⋅�−�=�⋅� niet logisch voor je is, ga dan terug en lees de artikel over paren.
We hebben hierboven gezien hoe je �,� en � omzet in elliptische curvepunten; � is slechts de generator (dat wil zeggen het elliptische curvepuntequivalent van nummer één). We kunnen �⋅�(�) toevoegen aan de vertrouwde configuratie. � is moeilijker; � is slechts een polynoom, en we voorspellen heel weinig van tevoren over wat de coëfficiënten ervan zullen zijn voor elke individuele QAP-oplossing. Daarom moeten we nog meer gegevens toevoegen aan de vertrouwde opstelling; specifiek de volgorde:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4….
In de vertrouwde opstelling van Zcash loopt de reeks hier op tot ongeveer 2 miljoen; dit is hoeveel machten van � je nodig hebt om ervoor te zorgen dat je altijd �(�) kunt berekenen, tenminste voor de specifieke QAP-instantie waar ze om geven. En daarmee kan de prover alle informatie aanleveren zodat de verificateur de laatste controle kan uitvoeren.
Er is nog een detail dat we moeten bespreken. Meestal willen we niet alleen in abstracto bewijzen dat er een oplossing bestaat voor een specifiek probleem; in plaats daarvan willen we de juistheid van een specifieke oplossing bewijzen (bijvoorbeeld bewijzen dat als je het woord ‘koe’ neemt en SHA3 het een miljoen keer hasht, het eindresultaat begint met 0x73064fe5), of dat er een oplossing bestaat als je de enkele parameters. In een cryptocurrency-instantie waarbij transactiebedragen en rekeningsaldi worden gecodeerd, wilt u bijvoorbeeld bewijzen dat u een decoderingssleutel k kent, zodat:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
de versleutelde old_balance
, tx_value
en new_balance
moeten publiekelijk worden gespecificeerd, aangezien dit de specifieke waarden zijn die we op dat specifieke moment willen verifiëren; alleen de decoderingssleutel mag verborgen zijn. Er zijn enkele kleine aanpassingen aan het protocol nodig om een “aangepaste verificatiesleutel” te creëren die overeenkomt met een specifieke beperking op de invoer.
Laten we nu een stapje terug doen. Allereerst is hier het verificatiealgoritme in zijn geheel, met dank aan Ben Sasson, Tromer, Virza en Chiesa:
De eerste regel gaat over parametrisering; in wezen kun je de functie ervan zien als het maken van een “aangepaste verificatiesleutel” voor het specifieke geval van het probleem waar enkele argumenten worden gespecificeerd. De tweede regel is de lineaire combinatiecontrole voor �,� en �; de derde regel is de controle of de lineaire combinaties dezelfde coëfficiënten hebben, en de vierde regel is de productcontrole �⋅�−�=�⋅�.
In totaal bestaat het verificatieproces uit een paar elliptische curvevermenigvuldigingen (één voor elke “openbare” invoervariabele) en vijf koppelingscontroles, waarvan er één een extra koppelingsvermenigvuldiging omvat. Het bewijs bevat acht elliptische curvepunten: elk een paar punten voor �(�),�(�) en �(�), een punt �� voor �⋅(�(�)+�(�)+�(� )), en een punt �ℎ voor �(�). Zeven van deze punten bevinden zich op de ��-curve (elk 32 bytes, omdat je de �-coördinaat tot een enkele bit kunt comprimeren), en in de Zcash-implementatie bevindt één punt (��) zich op de gedraaide curve in ��2 (64 bytes), dus de totale grootte van het bewijs is ~288 bytes.
De twee rekenkundig moeilijkste onderdelen van het maken van een bewijs zijn:
- Door (�⋅�−�)/� te delen krijg je � (algoritmen gebaseerd op de Snelle Fourier-transformatie kan dit doen in sub-kwadratische tijd, maar het is nog steeds behoorlijk rekenintensief)
- Vermenigvuldigingen en optellingen van de elliptische curve maken om de waarden �(�),�(�),�(�) en �(�) en hun overeenkomstige paren te creëren
De fundamentele reden waarom het maken van een bewijs zo moeilijk is, is het feit dat wat in de oorspronkelijke berekening een enkele binaire logische poort was, verandert in een bewerking die cryptografisch moet worden verwerkt via elliptische curve-bewerkingen als we er een nul-kennisbewijs van willen maken. . Dit feit, samen met de superlineariteit van snelle Fourier-transformaties, betekent dat het maken van bewijzen ongeveer 20 tot 40 seconden duurt voor een Zcash-transactie.
Een andere zeer belangrijke vraag is: kunnen we proberen de vertrouwde opzet een beetje… minder veeleisend te maken? Helaas kunnen we het niet volledig betrouwbaar maken; de KoE-aanname zelf sluit het maken van onafhankelijke paren (��,��⋅�) uit zonder te weten wat � is. We kunnen de veiligheid echter aanzienlijk vergroten door gebruik te maken van '-of-' meerpartijenberekeningen, dat wil zeggen door de vertrouwde opstelling tussen 'partijen' zo te construeren dat zolang ten minste één van de deelnemers zijn giftige afval heeft verwijderd, alles in orde is. .
Om een idee te krijgen van hoe je dit zou doen, is hier een eenvoudig algoritme om een bestaande set (�,�⋅�,�⋅�2,�⋅�3…) te nemen en je eigen geheim “toe te voegen” zodat je zowel je geheim als het vorige geheim (of de vorige reeks geheimen) nodig hebt om vals te spelen.
De uitvoerset is eenvoudigweg:
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…
Merk op dat je deze set kunt maken als je alleen de originele set en s kent, en dat de nieuwe set op dezelfde manier functioneert als de oude set, behalve dat je nu �⋅� als “giftig afval” gebruikt in plaats van �. Zolang jij en de persoon (of mensen) die de vorige set hebben gemaakt er niet in slagen om je giftige afval te verwijderen en later samen te spannen, is de set “veilig”.
Dit doen voor de volledige vertrouwde opstelling is een stuk moeilijker, omdat er meerdere waarden bij betrokken zijn en het algoritme in verschillende rondes tussen de partijen moet worden uitgevoerd. Het is een gebied van actief onderzoek om te zien of het meerpartijenberekeningsalgoritme verder kan worden vereenvoudigd en minder rondes nodig heeft of beter parallelleerbaar kan worden gemaakt, want hoe meer je dat kunt doen, hoe meer partijen het haalbaar wordt om op te nemen in de vertrouwde installatieprocedure. . Het is redelijk om in te zien waarom een vertrouwde opstelling tussen zes deelnemers die elkaar allemaal kennen en met elkaar samenwerken sommige mensen ongemakkelijk zou kunnen maken, maar een vertrouwde opstelling met duizenden deelnemers zou bijna niet te onderscheiden zijn van helemaal geen vertrouwen – en als je echt paranoïde bent , kunt u zelf instappen en deelnemen aan de installatieprocedure, en er zeker van zijn dat u uw waarde persoonlijk hebt verwijderd.
Een ander gebied van actief onderzoek is het gebruik van andere benaderingen die geen gebruik maken van combinaties en hetzelfde vertrouwde opstellingsparadigma om hetzelfde doel te bereiken; zien De recente presentatie van Eli ben Sasson voor één alternatief (maar wees gewaarschuwd, het is wiskundig minstens zo ingewikkeld als SNARKs!)
Speciale dank aan Ariel Gabizon en Christian Reitwiessner voor hun recensie.
- Door SEO aangedreven content en PR-distributie. Word vandaag nog versterkt.
- PlatoData.Network Verticale generatieve AI. Versterk jezelf. Toegang hier.
- PlatoAiStream. Web3-intelligentie. Kennis versterkt. Toegang hier.
- PlatoESG. carbon, CleanTech, Energie, Milieu, Zonne, Afvalbeheer. Toegang hier.
- Plato Gezondheid. Intelligentie op het gebied van biotech en klinische proeven. Toegang hier.
- BlockOffsets. Eigendom voor milieucompensatie moderniseren. Toegang hier.
- Bron: Plato data-intelligentie.