Vitalik Buterin kautta Vitalik Buterin blogi
Tämä on peili postista osoitteessa https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
Tämä on kolmas osa artikkelisarjasta, jossa selitetään, miten zk-SNARKien taustalla oleva tekniikka toimii; aiemmat artikkelit aiheesta asteen aritmeettiset ohjelmat ja elliptisten käyrien parit ovat pakollista lukemista, ja tämä artikkeli olettaa molempien käsitteiden tuntemista. Oletetaan myös perustiedot siitä, mitä zk-SNARKit ovat ja mitä ne tekevät. Katso myös Christian Reitwiessnerin artikkeli täällä toiseen tekniseen esittelyyn.
Aiemmissa artikkeleissa esittelimme toisen asteen aritmeettisen ohjelman, tavan esittää mikä tahansa laskennallinen ongelma polynomiyhtälöllä, joka soveltuu paljon paremmin erilaisiin matemaattisiin temppuihin. Otimme myös käyttöön elliptisiä käyräpareja, jotka mahdollistavat hyvin rajallisen yksisuuntaisen homomorfisen salauksen, jonka avulla voit tehdä tasa-arvon tarkistuksen. Aloitamme nyt siitä, mihin jäimme, ja käytämme elliptisiä käyräpareja yhdessä muutaman muun matemaattisen tempun kanssa, jotta todistaja voi todistaa tietävänsä ratkaisun tietylle QAP:lle paljastamatta mitään muuta. todellinen ratkaisu.
Tämä artikkeli keskittyy Pinocchio protokolla Parno, Gentry, Howell ja Raykova vuodesta 2013 (kutsutaan usein nimellä PGHR13); perusmekanismissa on muutamia variaatioita, joten käytännössä toteutettu zk-SNARK-malli voi toimia hieman eri tavalla, mutta perusperiaatteet pysyvät yleensä samoina.
Mennään aluksi käytettävän mekanismin turvallisuuden taustalla olevaan keskeiseen kryptografiseen oletukseen: *eksponenttitieto*oletus.
Periaatteessa, jos saat pisteparin � ja �, jossa �⋅�=� ja saat pisteen �, �⋅� ei ole mahdollista keksiä, ellei � ole "johdettu" jostain � että tiedät. Tämä saattaa tuntua intuitiivisesti ilmeiseltä, mutta tätä olettamusta ei itse asiassa voida johtaa mistään muusta oletuksesta (esim. diskreetin logarin kovuus), jota yleensä käytämme todistaessamme elliptiseen käyrään perustuvien protokollien turvallisuutta, joten zk-SNARKit perustuvat itse asiassa jossain määrin horjuvampi perusta kuin elliptisen käyrän salakirjoitus yleisemmin – vaikka se on silti tarpeeksi tukeva, jotta useimmat kryptografit ovat kunnossa sen kanssa.
Mennään nyt siihen, miten tätä voidaan käyttää. Oletetaan, että pistepari (�,�) putoaa taivaalta, missä �⋅�=�, mutta kukaan ei tiedä, mikä pisteen � arvo on. Oletetaan nyt, että keksin pisteparin (�,�), jossa �⋅�=�. Sitten KoE-oletus viittaa siihen, että ainoa tapa, jolla olisin voinut tehdä tuon pisteparin, oli ottamalla � ja � ja kertomalla molemmat jollakin kertoimella r jonka tunnen henkilökohtaisesti. Huomaa myös, että elliptisten käyrien parien taian ansiosta voit tarkistaa, että �=�⋅� ei varsinaisesti vaadi tietää � – sen sijaan voit yksinkertaisesti tarkistaa, onko �(�,�)=�(�,�).
Tehdään jotain mielenkiintoisempaa. Oletetaan, että meillä on kymmenen pisteparia, jotka putoavat taivaalta: (�1,�1),(�2,�2)…(�10,�10). Kaikissa tapauksissa ��⋅�=��. Oletetaan, että annan sinulle sitten pisteparin (�,�), jossa �⋅�=�. Mitä sinä nyt tiedät? Tiedät, että � on jokin lineaarinen yhdistelmä �1⋅�1+�2⋅�2+…+�10⋅�10, jossa tiedän kertoimet �1,�2…�10. Toisin sanoen, ainoa tapa saada tällainen pistepari (�,�) on ottaa luvun �1,�2…�10 kerrannaisia ja laskea ne yhteen ja tehdä sama laskelma �1,�2… �10.
Huomaa, että kun otetaan huomioon mikä tahansa tietty �1…�10 pisteen joukko, jonka lineaarisia yhdistelmiä kannattaa tarkistaa, et voi itse asiassa luoda mukana olevia �1…�10 pistettä tietämättä mitä � on, ja jos tiedät mitä � on sitten voit luoda parin (�,�), jossa �⋅�=� mitä tahansa � haluat, vaivautumatta luomaan lineaarista yhdistelmää. Siksi, jotta tämä toimisi, on ehdottoman välttämätöntä, että pisteiden luoja on luotettava ja todella poistaa � luotuaan kymmenen pistettä. Tästä tulee "luotetun asennuksen" käsite.
Muista, että QAP:n ratkaisu on joukko polynomeja (�,�,�) siten, että �(�)⋅�(�)−�(�)=�(�)⋅�(�), missä:
- � on lineaarinen yhdistelmä polynomien joukosta {�1…��}
- � on lineaarinen yhdistelmä arvoista {�1…��} samoilla kertoimilla
- � on lineaarinen yhdistelmä arvoista {�1…��} samoilla kertoimilla
Joukkot {�1…��},{�1…��} ja {�1…��} sekä polynomi � ovat osa ongelman lausetta.
Useimmissa todellisissa tapauksissa �,� ja � ovat kuitenkin erittäin suuria; Jos kyseessä on useita tuhansia piiriportteja, kuten hajautusfunktio, polynomeilla (ja lineaaristen yhdistelmien tekijöillä) voi olla useita tuhansia termejä. Siksi sen sijaan, että todistaja tarjoaisi lineaariset yhdistelmät suoraan, aiomme käyttää yllä esittämäämme temppua saadaksemme todistajan todistamaan, että he tarjoavat jotain, joka on lineaarinen yhdistelmä, mutta paljastamatta mitään muuta.
Olet ehkä huomannut, että yllä oleva temppu toimii elliptisen käyrän pisteissä, ei polynomeissa. Näin ollen tosiasiallisesti tapahtuu, että lisäämme seuraavat arvot luotettuun asetukseen:
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
Voit ajatella t:tä "salapisteenä", jossa polynomi arvioidaan. � on "generaattori" (jokin satunnainen elliptisen käyrän piste, joka on määritelty osana protokollaa) ja �,��,�� ja �� ovat "myrkyllistä jätettä", numeroita, jotka on ehdottomasti poistettava hinnalla millä hyvänsä, tai muuten kuka tahansa voi tehdä väärennettyjä todisteita. Jos joku antaa sinulle pisteparin �, � siten, että �⋅��=� (muistutus: meidän ei tarvitse �� tarkistaa tätä, koska voimme tehdä pariliitostarkistuksen), tiedät, että mitä he jotka antavat sinulle on lineaarinen yhdistelmä �� polynomista, jotka on arvioitu arvolla �.
Toistaiseksi todistajan on siis annettava:
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
Huomaa, että todistajan ei itse asiassa tarvitse tietää (eikä sen pitäisi tietää!) �,��,�� tai �� näiden arvojen laskemiseksi; Todistajan pitäisi pikemminkin pystyä laskemaan nämä arvot vain niistä pisteistä, jotka lisäämme luotettuun asetukseen.
Seuraava askel on varmistaa, että kaikilla kolmella lineaariyhdistelmällä on samat kertoimet. Tämän voimme tehdä lisäämällä luotettuun asetukseen toisen arvojoukon: �⋅(��(�)+��(�)+��(�))⋅�, missä � on toinen luku, jota tulisi pitää "myrkyllisenä". jäte” ja hylätään heti, kun luotettava asennus on valmis. Voimme sitten pyytää todistajaa luomaan lineaarisen yhdistelmän näillä arvoilla samoilla kertoimilla ja käyttää samaa paritustemppua kuin yllä varmistaaksemme, että tämä arvo vastaa annettua �+�+�.
Lopuksi meidän on todistettava, että �⋅�−�=�⋅�. Teemme tämän jälleen pariliitostarkistuksella:
�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))
Missä �ℎ=�⋅�(�). Jos tämän yhtälön ja �⋅�−�=�⋅� välinen yhteys ei ole mielestäsi järkevä, palaa takaisin ja lue artikkeli parisuhteista.
Näimme edellä, kuinka �,� ja � muunnetaan elliptisen käyrän pisteiksi; � on vain generaattori (eli elliptisen käyrän piste, joka vastaa numeroa yksi). Voimme lisätä �⋅�(�) luotettuun asetukseen. � on vaikeampaa; � on vain polynomi, ja ennustamme hyvin vähän etukäteen, mitkä sen kertoimet ovat kullekin yksittäiselle QAP-ratkaisulle. Siksi meidän on lisättävä vielä enemmän tietoja luotettuun asetukseen; erityisesti sarja:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4….
Zcashin luotetussa asennuksessa sekvenssi nousee noin 2 miljoonaan; tämä on kuinka monta potenssia � tarvitset varmistaaksesi, että pystyt aina laskemaan �(�), ainakin niille tietylle QAP-esiintymälle, josta he välittävät. Ja sen avulla todistaja voi toimittaa kaikki tiedot todentajalle lopullisen tarkistuksen tekemistä varten.
On vielä yksi yksityiskohta, josta meidän on keskusteltava. Useimmiten emme halua vain todistaa abstraktisti, että jollekin tietylle ongelmalle on olemassa ratkaisu; sen sijaan haluamme todistaa joko jonkin tietyn ratkaisun oikeellisuuden (esim. todistaa, että jos otat sanan "lehmä" ja SHA3 tiivistää sen miljoona kertaa, lopputulos alkaa numerolla 0x73064fe5), tai että ratkaisu on olemassa, jos rajoitat joitain parametreja. Esimerkiksi kryptovaluutta-instanssissa, jossa tapahtumasummat ja tilisaldot on salattu, haluat todistaa, että tiedät jonkin salauksenpurkuavaimen k:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
Salattu old_balance
, tx_value
ja new_balance
tulee määrittää julkisesti, koska ne ovat erityisiä arvoja, jotka pyrimme varmistamaan kyseisellä hetkellä; vain salauksenpurkuavain tulee piilottaa. Joitakin pieniä muutoksia protokollaan tarvitaan "mukautetun vahvistusavaimen" luomiseksi, joka vastaa tiettyjä syötteitä koskevia rajoituksia.
Mennään nyt vähän taaksepäin. Ensinnäkin, tässä on tarkistusalgoritmi kokonaisuudessaan Benin luvalla Sasson, Tromer, Virza ja Chiesa:
Ensimmäinen rivi käsittelee parametrisointia; pohjimmiltaan voit ajatella sen tehtävää "muokatun vahvistusavaimen" luomiseksi. ongelman tietylle tapaukselle jossa jotkin argumentit on määritelty. Toinen rivi on lineaarinen yhdistelmän tarkistus �,� ja �; kolmas rivi on tarkistus, että lineaarisilla yhdistelmillä on samat kertoimet, ja neljäs rivi on tulotarkistus �⋅�−�=�⋅�.
Kaiken kaikkiaan varmistusprosessi koostuu muutamasta elliptisen käyrän kertolaskusta (yksi jokaiselle "julkiselle" syötemuuttujalle) ja viidestä pariliitostarkistuksesta, joista yksi sisältää ylimääräisen parituskertoimen. Todistus sisältää kahdeksan elliptisen käyrän pistettä: pisteparin �(�),�(�) ja �(�), pisteen �� �⋅(�(�)+�(�)+�(� )), ja pisteen �ℎ �(�) kohdalla. Seitsemän näistä pisteistä on ��-käyrällä (32 tavua kussakin, koska voit pakata �-koordinaatin yhdeksi bitiksi), ja Zcash-toteutuksessa yksi piste (��) on ��2:n kierretyllä käyrällä (64 tavua), joten todistuksen kokonaiskoko on ~288 tavua.
Kaksi laskennallisesti vaikeinta osaa todisteen luomisessa ovat:
- Jakamalla (�⋅�−�)/� saadaksesi � (algoritmit, jotka perustuvat Nopea Fourier-muunnos voi tehdä tämän subquadraattisessa ajassa, mutta se on silti melko laskentaintensiivistä)
- Elliptisen käyrän kerto- ja yhteenlaskujen tekeminen �(�),�(�),�(�)- ja �(�)-arvojen ja niitä vastaavien parien luomiseksi
Perussyy siihen, miksi todisteen luominen on niin vaikeaa, on se, että se, mikä oli yksittäinen binäärilogiikkaportti alkuperäisessä laskelmassa, muuttuu operaatioksi, joka on prosessoitava kryptografisesti elliptisen käyrän operaatioilla, jos siitä tehdään nollatietotodistus . Tämä seikka yhdessä nopeiden Fourier-muunnosten superlineaarisuuden kanssa tarkoittaa, että todisteiden luominen kestää ~20–40 sekuntia Zcash-tapahtumassa.
Toinen erittäin tärkeä kysymys on: voimmeko yrittää tehdä luotetusta asetuksesta hieman… vähemmän luottamusta vaativaa? Valitettavasti emme voi tehdä siitä täysin luotettavaa; KoE-oletus itsessään sulkee pois itsenäisten parien (��,��⋅�) tekemisen tietämättä mitä � on. Voimme kuitenkin lisätä turvallisuutta huomattavasti käyttämällä monen osapuolen laskentaa – eli rakentamalla osapuolten väliset luotetut asetukset siten, että niin kauan kuin yksi osallistujista on poistanut myrkyllisen jätteensä, kaikki on kunnossa. .
Saadaksesi hieman käsitystä siitä, miten tämän tekisit, tässä on yksinkertainen algoritmi olemassa olevan joukon ottamiseksi (�,�⋅�,�⋅�2,�⋅�3…) ja oman salaisuutesi "lisäämiseksi" niin, että tarvitset sekä salaisuutesi että edellisen salaisuuden (tai edellisen salaisuuksien joukon) huijaamiseen.
Lähtösarja on yksinkertaisesti:
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…
Huomaa, että voit tuottaa tämän sarjan tietäen vain alkuperäisen sarjan ja s:t, ja uusi sarja toimii samalla tavalla kuin vanhakin, paitsi että nyt käytetään �⋅� ”myrkyllisenä jätteenä” �:n sijaan. Niin kauan kuin sinä ja edellisen sarjan luonut henkilö (tai henkilöt) jätä poistamatta myrkyllistä jätettäsi ja sovitte myöhemmin yhteen, sarja on "turvallinen".
Tämän tekeminen täydelliselle luotetulle asennukselle on hieman vaikeampaa, koska mukana on useita arvoja ja algoritmi on tehtävä osapuolten välillä useissa kierroksissa. Se on aktiivisen tutkimuksen ala, jotta nähdään, voidaanko monen osapuolen laskenta-algoritmia yksinkertaistaa entisestään ja tehdä niin, että se vaatii vähemmän kierroksia tai tehdä rinnakkaisemmaksi, sillä mitä enemmän voit tehdä sitä, sitä enemmän osapuolia on mahdollista sisällyttää luotettuun määritysmenettelyyn. . On järkevää ymmärtää, miksi luotettava kokoonpano kuuden osallistujan välillä, jotka kaikki tuntevat ja työskentelevät keskenään, saattaa aiheuttaa joillekin ihmisille epämukavuutta, mutta tuhansia osallistujia sisältävää luotettavaa kokoonpanoa ei voi melkein erottaa luottamattomuudesta – ja jos olet todella vainoharhainen , voit osallistua asennusprosessiin itse ja olla varma, että poistit arvosi henkilökohtaisesti.
Toinen aktiivisen tutkimuksen alue on muiden lähestymistapojen käyttö, jotka eivät käytä pariliitoksia ja samaa luotettua asetusparadigmaa saman tavoitteen saavuttamiseksi; katso Eli ben Sassonin äskettäinen esitys yksi vaihtoehto (vaikka varoittaa, se on matemaattisesti vähintään yhtä monimutkaista kuin SNARKit!)
Erityiset kiitokset Ariel Gabizonille ja Christian Reitwiessnerille arvostelusta.
- SEO-pohjainen sisällön ja PR-jakelu. Vahvista jo tänään.
- PlatoData.Network Vertical Generatiivinen Ai. Vahvista itseäsi. Pääsy tästä.
- PlatoAiStream. Web3 Intelligence. Tietoa laajennettu. Pääsy tästä.
- PlatoESG. hiili, CleanTech, energia, ympäristö, Aurinko, Jätehuolto. Pääsy tästä.
- PlatonHealth. Biotekniikan ja kliinisten kokeiden älykkyys. Pääsy tästä.
- BlockOffsets. Ympäristövastuun omistuksen nykyaikaistaminen. Pääsy tästä.
- Lähde: Platon Data Intelligence.