SNARK turvallisuus ja suorituskyky

A SNARK (Succinct Non-Interactive Argument of Knowledge) on salaustyökalu, joka avaa jännittäviä uusia mahdollisuuksia järjestelmän suunnittelussa, erityisesti hajautetuissa olosuhteissa. SNARKit sallivat tietojen käsittelyn epäluotettaville tahoille, jotka voivat sitten todistaa, että tiedot ovat kelvollisia ja niitä on käsitelty oikein. Naiivi tapa todistaa tämä olisi julkaista tiedot, jolloin kuka tahansa haluaa tarkistaa niiden oikeellisuuden ja käsitellä niitä suoraan. 

SNARK saavuttaa saman vaikutuksen, mutta edullisemmins validaattoreille. Esimerkiksi toisen kerroksen (L2) varmennettavissa olevassa kokoelmassa rullauspalvelu käsittelee lohkoketjutapahtumat. Palvelu lähettää ajoittain käyttäjiensä tilisaldot kerroksen yksi lohkoketjuun. Joka kerta kun se lähettää päivityksen saldoihin, se liittää SNARK-todistuksen siitä, että se tietää sarjan kelvollisia tapahtumia, jotka muuttivat vanhat tilisaldot päivitetyiksi. Tällä tavalla lohkoketjun validaattoreiden ei tarvitse tehdä kovaa työtä tapahtuman oikeellisuuden tarkistamiseksi (esim. jokaisen tapahtuman digitaalisen allekirjoituksen tarkistaminen) eikä myöskään erikseen prosessoida tapahtumia päivitettyjen saldojen laskemiseksi.  

My Edellinen viesti keskittyi SNARK-todistajien suorituskykyyn – SNARKin sovellettavuuden pääasialliseen määrään. Vaikka SNARK-todistajan suorittaminen voi olla laskennallisesti intensiivistä, siinä määrin kuin voi olla mahdotonta tuottaa todisteita laajamittaisille laskelmille, SNARK-todentaminen on yleensä paljon halvempaa kuin tietojen suora tarkistaminen ja käsittely. SNARK-varmennuskustannukset vaihtelevat kuitenkin huomattavasti. Tämä viesti purkaa nämä kustannukset ja vertailee eri SNARKien suojausominaisuuksia. 

Selitän erityisesti, että käytännön SNARKeissa, joissa on uskottava post-quantum-turvallisuus (PQ-SNARK), turvallisuuden ja varmennuskustannusten välillä on merkittävä jännite. Lisäksi joissakin tapauksissa tätä jännitystä ratkaistaan ​​parhaillaan siten, että varmistuskustannukset asetetaan turvallisuuden sijaan.

Jotta SNARKit voivat toteuttaa potentiaalinsa, käyttöön otettujen järjestelmien on oltava turvallisia ja käyttäjien on luottava tietoturvaansa. Päätän viestin ehdottamalla yksinkertaisia ​​toimia, joita web3-yhteisö voi tehdä varmistaakseen, että nämä kiinteistöt säilyvät pitkällä aikavälillä. 

Määrälliset turvatoimenpiteet 

SNARK on turvallinen, jos on laskennallisesti mahdotonta tuottaa vakuuttavaa todistetta väärästä väitteestä. Esimerkiksi L2-kokoelman yhteydessä hyökkääjä, joka haluaa varastaa rahani, haluaisi todistaa väärän väitteen muodossa: "Tiedän digitaalisesti allekirjoitetun tapahtuman, joka siirtää kaikki Justinin varat omalle tililleni." 

SNARKin turvallisuustasoa mitataan työn määrällä, joka on tehtävä vakuuttavan todisteen löytämiseksi väärästä väitteestä. Muiden kryptografisten primitiivien, kuten digitaalisten allekirjoitusten, tapaan tämän työn logaritmia kutsutaan "turvan bitteiksi". Esimerkiksi 30 bittiä tietoturva tarkoittaa, että 2³⁰ SNARKin hyökkääminen vaatii ≈ miljardi "työaskelta". Tämä on luonnostaan ​​likimääräinen todellisen turvallisuuden mitta, koska käsitys yhdestä työvaiheesta voi vaihdella, eikä käytännön näkökohtia, kuten muistivaatimuksia tai rinnakkaisuuden mahdollisuuksia, oteta huomioon.

Ja laadukkaat

Turvallisuusosia on a määrällinen SNARKin turvallisuuden mitta. SNARKit eroavat myös toisistaan laadullinen turvallisuusominaisuudet. 

Esimerkiksi jotkin SNARKit vaativat luotettavan asennusseremonian jäsennellyn todistusavaimen luomiseksi. SNARKit, jotka eivät vaadi luotettua asennusta ollenkaan, kutsutaan läpinäkyvä. 

Jotta läpinäkymätön SNARK olisi turvallinen, tyypillisesti ainakin yhden seremonian osallistujan on täytynyt käyttäytyä rehellisesti, mikä tarkoittaa, että hän tuotti ja sitten hylkäsi "luukun", joka, jos se yhdistetään kaikkien muiden osallistujien sulkuoviin, tekisi siitä helppoa. löytää vakuuttavia SNARKin "todisteita" mistä tahansa väärästä väitteestä. Luotetut asetukset ovat ovat ajaa satojen tai tuhansien osallistujien kanssa, jotta tämä oletus olisi mahdollisimman lievä. 

SNARKit eroavat myös herkkyydestään kvanttihyökkäyksille. Erityisesti monet SNARKit (esim. Groth16, Punkku, Marlin, Bulletproofs, Nova) luottaa siihen oletukseen, että diskreettejä logaritmeja on vaikea laskea (ja joissain tapauksissa myös lisäoletuksia). Diskreettien logaritmien laskeminen on jotain, mitä kvanttitietokoneet pystyisivät tekemään tehokkaasti. Näin ollen nämä SNARKit eivät ole kvanttiturvallisia (ei-PQ). 

Vaikka kiireellisiä ponnisteluja on meneillään siirtymiseksi post-kvanttiin salausjärjestelmiä, tämä johtuu ensisijaisesti tarpeesta pitää salatut viestit salassa vuosikymmeniä eteenpäin. Vastustaja, joka tallentaa siepatun viestin tänään ja odottaa kvanttitietokoneen saapumista esimerkiksi viidenkymmenen vuoden kuluttua, voi käyttää tietokonetta XNUMX vuotta vanhan viestin salauksen purkamiseen. SNARKien tilanne on aivan toinen. Muiden kuin PQ SNARKien käytön tänään ei pitäisi vaarantaa lohkoketjujen turvallisuutta XNUMX vuoden kuluttua, vaikka kvanttitietokoneet saapuisivatkin siihen mennessä. 

Polynomiset sitoumukset

Kaikki SNARKit käyttävät kryptografista primitiiviä, joka tunnetaan nimellä a polynominen sitoumusjärjestelmä, ja tämä komponentti on usein suorituskyvyn pullonkaula. (Lisätietoja, katso minun Edellinen viesti.) Lisäksi SNARKin läpinäkyvyys ja uskottava post-kvanttiturva määräytyvät yksinomaan sen käyttämän polynomisen sitoumusmallin mukaan. 

Eräs näkyvä esimerkki on ns KZG-polynomiset sitoumukset, joita käyttävät Punkku, Marlin, ja monet muut. KZG-sitoumukset eivät ole avoimia eivätkä jälkikäteen turvallisia. Muut sitoumusjärjestelmät ovat avoimia, mutta eivät jälkikäteen, mukaan lukien Bulletproofs, hyraxja Pietarinkala. 

Vielä muut suunnitelmat ovat sekä läpinäkyviä että uskottavasti postkvanttia. Nämä sisältävät Perjantai, ligero, Ligero++, Jarrutusja Orion. Kaikki nämä mallit perustuvat virheenkorjauskoodeihin. Hashing on ainoa kryptografinen primitiivi, jota he käyttävät. Niillä on myös yhteinen ominaisuus: varmennuskustannukset (mitattuna hash-arviointien ja kenttäoperaatioiden määrällä) kasvavat lineaarisesti tietoturvabittien määrän kanssa.

Karkeasti sanottuna yksi "iteraatio" näistä kvanttipolynomin jälkeisistä sitoumuksista saavuttaa vain pienen määrän (esimerkiksi 2-4) tietoturvabittiä. Protokolla on siis toistettava useita kertoja turvatason "vahvistamiseksi" ja varmennuskustannukset kasvavat jokaisen toiston myötä. Näin ollen PQ-SNARK:ien varmennuskustannusten (ja siten kaasukustannusten lohkoketjusovelluksissa) hallitsemiseksi protokollasuunnittelijoita kannustetaan pitämään suojaustaso alhaisena. 

Harvinaisten kanssa poikkeukset, tämä jännite konkreettisten turvallisuus- ja todentamiskustannusten välillä ei esiinny ei-PQ SNARKissa (sekä läpinäkyvissä että ei-läpinäkyvissä). Muut kuin PQ-SNARKit käyttävät elliptisiä käyräryhmiä, joissa diskreettien logaritmien oletetaan olevan vaikea laskea, ja niiden suojaustasot määräytyvät käytetyn ryhmän mukaan. Sopivan elliptisen käyräryhmän koko ja siten kunkin ryhmäoperaation kustannukset kasvavat halutun suojaustason mukana. Kuitenkin numero Todistuksen ryhmäelementit ovat riippumattomia ryhmän valinnasta. 

PQ-SNARK:issa hash-arviointien koko ei kasva lineaarisesti halutun suojaustason kanssa, vaan myös todistukseen sisältyvien ja todentajan suorittamien arviointien määrä. 

Konkreettiset todentajakustannukset ja turvallisuus käyttöönotetuissa SNARKeissa

Käytettyjen SNARKien konkreettiset todentamiskustannukset ja turvallisuustasot vaihtelevat huomattavasti. Tässä muutamia havainnollistavia esimerkkejä:

Varmentajan kustannukset 

My Edellinen viesti mainitsi kaksi esimerkkiä konkreettisista todentamiskustannuksista: Punkku todisteiden hinta varten 300,000-kaasu tarkistaa Ethereumissa, kun taas StarkWaren todisteet maksoivat noin 5 miljoonaa kaasua. StarkWaren todistukset ovat läpinäkyviä ja uskottavasti postkvanttia, kun taas PlonK:n todisteet eivät ole. Kuitenkin, kuten seuraavassa kerrotaan, StarkWaren vedoksia ajetaan paljon alhaisemmalla suojaustasolla kuin PlonK-vedoksia Ethereumissa.

Konkreettinen turvallisuus

Ainoa elliptinen käyrä, jossa on Ethereumin esikäännöksiä, on nimeltään altbn128, joten tämä on käyrä, jota kaikki ei-PQ SNARKit ovat käytössä Ethereumin käytössä, mukaan lukien aztecja zkSync's. Tämän käyrän – ja siten myös sitä käyttävien SNARKien – uskottiin alun perin tarjoavan noin 128 bittiä turvallisuutta. Mutta johtuen paremmat hyökkäykset (jonka tarkka suoritusaika on vaikea määrittää), käyrän katsotaan nykyään laajalti tarjoavan 100-110 bitin turvallisuutta. 

On olemassa EIP:itä varten harkinta esikäännöksiä eri käyriin, joiden uskotaan edelleen tarjoavan lähes 128 bitin turvallisuutta. Sellaisia ​​käyrät ovat jo käytetty muiden kuin Ethereum-projektien SNARKissa, mukaan lukien ZCash, Algorand, Dfinity, Filecoin ja Aleo. 

Sitä vastoin ketjussa olevien tietojen mukaan StarkWaren PQ-SNARKit (sen ns. SHARP-järjestelmässä, lyhenne sanoista SHARed Prover) on konfiguroitu kohdistamaan 80 bitin suojausta. Tämä turvataso pätee tietyissä olettamuksissa FRI:n tilastollisesta luotettavuudesta (jota käsittelen myöhemmin tässä viestissä). 

Termi "80 bittiä turvallisuutta" on epämääräinen tässä yhteydessä, joten saanen purkaa sen. Karkeasti sanottuna se tarkoittaa, että hyökkääjä voi tuottaa vakuuttavan todisteen väärästä lausunnosta arvioimalla hash-funktion 2⁸⁰ kertaa (eli KECCAK-256, Ethereumin käyttämä hash-funktio). Tarkemmin sanottuna hyökkääjä, joka on valmis suorittamaan 2^k hash-arvioinnit voivat tuottaa vakuuttavan todisteen noin 2:n todennäköisyydellä^k-80. Esimerkiksi 2:lla⁷⁰ hash-arvioinnit, voidaan löytää SNARK "todiste" väärästä lausunnosta todennäköisyydellä noin 2^-10 = 1 / 1024. 

Tämä käsitys on heikompi kuin mitä termi "80 bittiä tietoturvaa" tarkoittaa muissa yhteyksissä. Esimerkiksi törmäyksenkestävä hash-funktio (CRHF), joka on määritetty 80-bittiseen suojaukseen, tuottaa 160-bittisiä tulosteita. Jos hash-funktio on hyvin suunniteltu, nopein törmäyshakumenettely on Syntymäpäivähyökkäys, raa'an voiman menetelmä, joka voi löytää törmäyksen noin 2^160/2 = 2⁸⁰ hash-arvioinnit. Kuitenkin 2:n kanssa^k hash-arvioinnit, Birthday-hyökkäys löytää törmäyksen vain 2:n todennäköisyydellä^2k-160. 

Esimerkiksi 2⁷⁰ hash-arvioinnit tuottavat törmäyksen todennäköisyydellä 2^-20  ≈ 1/1,000,000 1 1,000. Tämä on paljon pienempi kuin 80/XNUMX XNUMX:n todennäköisyys, että hyökkääjä väärentää PQ-SNARK-suojauksen, joka on määritetty XNUMX bitin tietoturvaan. 

Tämä ero voi muuttaa dramaattisesti hyökkäyksen houkuttelevuutta. Esimerkkinä kuvitellaan, että hyökkääjän budjetti on 100 2 dollaria, josta voi ostaa XNUMX⁷⁰ hash-arvioinnit. Ja oletetaan, että jos hyökkääjä onnistuu, voitto on 200 miljoonaa dollaria. Hyökkäyksen odotettu arvo 80 bitin tietoturvan PQ-SNARKIin on (1/1,000 200) * 200 miljoonaa dollaria eli 1 1,000,000 dollaria – kaksinkertainen hinta. Jos onnistumisen todennäköisyys olisi vain 200/XNUMX XNUMX XNUMX, kuten CRHF:n tapauksessa, hyökkäyksen odotettu arvo olisi vain XNUMX dollaria. 

Kaksi käsitettä "80 bittiä tietoturvasta" eroavat myös dramaattisesti niiden kestävyydestä itsenäisiä hyökkäyksiä vastaan. Oletetaan esimerkiksi, että 1,000 2 itsenäistä osapuolta kukin hyökkää PQ-SNARKia vastaan ​​suorittamalla XNUMX⁷⁰ hash-arvioinnit. Koska jokainen onnistuu noin 1/1,000 todennäköisyydellä, ainakin yksi niistä onnistuu melko todennäköisesti. Näin ei olisi, jos kukin onnistuisi todennäköisyydellä vain 1/1,000,000 XNUMX XNUMX.

Hyvin suunniteltujen elliptisten käyräryhmien odotetaan käyttäytyvän samalla tavalla kuin CRHF:t, syntymäpäivän kaltaisilla hyökkäyksillä, kuten Pollardin rho-algoritmi olla tunnetuin. Tämä tarkoittaa, että ryhmässä, joka tarjoaa 128 bitin suojausta, 2^k ryhmäoperaatioiden pitäisi antaa ratkaisu diskreetin logaritmiongelman esiintymään todennäköisyydellä vain 2^2k-256. Esimerkiksi 2⁷⁰ ryhmäoperaatiot löytäisivät diskreetin logaritmin vain tähtitieteellisesti pienellä todennäköisyydellä 2^-116. Lisäksi jokainen ryhmätoiminto on hitaampi kuin CRHF-arviointi. 

Kuinka monta hash-arviointia on mahdollista tehdä nykyään?

Tammikuussa 2020 laskennan kustannukset olivat vain 2⁶⁴ SHA-1-arvioinnit GPU:illa oli $45,000. Tämä maksaa 2⁷⁰ SHA-1-arvioinnit GPU:sta muutamalla miljoonalla dollarilla (ehkä alhaisempi Ethereumin yhdistämisen jälkeen, koska siirtyminen pois GPU-dominoimasta työn louhinnasta vähentää todennäköisesti GPU-laskennan kysyntää ja alentaa sen kustannuksia). 

Kun kelpoisuuskokoelmat sisältävät jo satoja miljoonia dollareita käyttäjävaroja, vakuuttavan todisteen löytäminen väärästä lausunnosta voi tuottaa useita miljoonia dollareita voittoa. PQ-SNARKin määrittäminen 80 bitin tietoturvaan aggressiivisissa olettamuksissa jättää alle 10 bitin liikkumavaraa kannattavien hyökkäysten ja PQ-SNARKin oletetun turvallisuuden välille.

Toisena tietopisteenä Bitcoinin verkon hajautusnopeus on tällä hetkellä noin 2⁶⁴  hash-arvioita sekunnissa, mikä tarkoittaa, että bitcoin-kaivostyöntekijät suorittavat kokonaisuutena 2⁸⁰ SHA-256-arvioinnit 18 tunnin välein. Tietenkin tämä silmiä hivelevä luku johtuu valtavasta investoinnista bitcoinin louhintaan. 

Olettaen että kuusi bitcoin-lohkoa luotu tunnissa, ja ottaen huomioon nykyisen lohkopalkkion 6.25 Bitcoinia per lohko, nämä 2⁸⁰ SHA-256-arvioinnit maksavat oletettavasti alle 22,000 18 * 6 * 6.25 * 15 ≈ XNUMX miljoonaa dollaria. Muuten bitcoinin louhinta ei olisi kannattavaa nykyhinnoilla. 

Ehdotetut toimet terveen ekosysteemin edistämiseksi

SNARK:ien käyttämisen tiivistelmissä tarkoitus on saavuttaa lohkoketjun skaalautuvuus ilman, että käyttäjien tarvitsee luottaa rullauspalveluun sokeasti. Koska koontipalvelu kirjoitti älykkään sopimuksen, joka toimii SNARK-varmentajana, yleisön on voitava tarkastaa sopimus ja vahvistaa, että se todella tarkistaa asianmukaisten lausuntojen SNARK-todisteet. Älykkään sopimuksen julkinen tarkastelu voi olla tarpeen myös sen varmistamiseksi, ettei rollup-palvelu pysty sensuroimaan omia käyttäjiään. Ehdotetut menetelmät sensuurin vastustamiseksi edellyttävät rollupin älykästä sopimusta, jonka avulla käyttäjät voivat pakottaa nostamaan varansa, jos rollup-palvelu ei pysty käsittelemään heidän tapahtumiaan. 

Koska nämä protokollat ​​ovat kehittyneitä, tämä julkisen valvonnan paradigma asettaa asiantuntijoille jonkin verran taakkaa keskustella avoimesti ja rehellisesti käytettyjen sopimusten turvallisuudesta. 

Mutta PQ-SNARK:ien kanssa jopa asiantuntijoiden voi olla vaikeaa varmistaa käyttöönotetun protokollan suojaustaso samasta syystä kuin näiden SNARKien turvallisuus ja todentajan suorituskyky ovat jännitteisiä: suojaustaso (ja todentajan kustannukset) riippuvat protokollan sisäisistä parametreista. SNARK. Ja ainakin StarkWarelle älykkäät sopimukset, nämä parametrit, soitad logBlowupFactor, ​​proofOfWorkBits ja n_Queries eivät ole suoraan määritetty älykkään sopimuksen koodissa, vaan ne välitetään älykkäälle sopimukselle julkisina tietoina. Sikäli kuin tiedän, helpoin tapa tunnistaa nämä parametrit ketjun tiedoista on nelivaiheinen prosessi: 

1. Näytä sopiva älykäs sopimus lohkotutkimuksessa, kuten Etherscan, 
2. napsauta an asianmukainen "todista todiste" -tapahtuma, 
3. purkaa tapahtuman syöttötiedot ja
4. selvittää miten tulkita dekoodattu syöttödata oppiakseen tärkeimmät SNARK-parametrit, jotka yhdessä määrittävät suojaustason. 

Tämä viimeinen vaihe vaatii oikean Solidity-koodin löytämisen tapahtuman toteuttamiseksi, mikä voi itsessään olla hämmentävä tehtävä. (Kun valmistauduin tutkimus neuvottelut tämän kesän koontiversioissa Etherscan pystyi purkamaan SHARP-vahvistimien tapahtumiin liittyvät syöttötiedot yllä olevan vaiheen 2 mukaisesti. Mutta se ei näytä enää toimivan.)

Ehdotus 1: Tarkastus 

Tätä silmällä pitäen ensimmäinen ehdotukseni web3-yhteisölle on helpottaa käytettyjen post-quantum SNARKien turvallisuustason tarkastelua. Tämä edellyttää todennäköisesti parempia työkaluja ketjun sisäisten tietojen ymmärtämiseen ja hankkeiden avoimuuden lisäämistä näiden parametrien tunnetuksi tekemisessä. 

Ehdotus 2: Tiukemmat normit

80 bitin tietoturva on liian alhainen, varsinkin heikko versio, jossa 2⁷⁰ hash-arvioinnit riittävät onnistuneeseen hyökkäykseen noin 1/1000 todennäköisyydellä – varsinkin kun otetaan huomioon salausprimitiivien yllättävien hyökkäysten pitkä historia. Yksi edellä mainituista on paremmat hyökkäykset pariliitosystävällisiä elliptisiä käyriä vastaan, kuten altbn128. Kuuluisempi esimerkki on SHA-1, joka standardisoitiin 80 bitin turvallisuuteen, mutta jonka osoitettiin lopulta saavuttavan vain noin 60 bittiä. Tämä historia mielessä PQ-SNARK-suunnittelijoiden tulisi jättää itselleen yli 10 bittiä liikkumavaraa suojaustasoa määrittäessään, varsinkin jos tietoturva-analyysiin liittyy vahvoja olettamuksia suhteellisen uusien protokollien, kuten FRI:n, tilastollisesta turvallisuudesta.

Jopa PQ-SNARK-laitteille voidaan aina saavuttaa sopiva suojaustaso yksinkertaisesti lisäämällä varmennuskustannuksia. Esimerkiksi SHARPin verifierin turvallisuuden lisääminen 80 bitistä 128 bittiin (FRI:n tilastollisen pätevyyden arveluilla) nostaisi kaasukustannuksia noin kaksinkertaiseksi, hieman yli 5 miljoonasta hieman yli 10 miljoonaan. Ilman olettamuksia FRI:stä kaasukustannukset nousisivat vielä kaksinkertaiseksi, yli 20 miljoonaan. 

Seuraava ehdotukseni on siis, että web3-yhteisön tulisi kehittää vahvempia normeja soveltuvien suojaustasojen ympärille käytössä oleville SNARKeille. Henkilökohtainen suositukseni olisi vähintään 100 bittiä ja vähintään 128, jos SNARKin tietoturva perustuu epätyypillisiin oletuksiin. En ole ensimmäinen tehdä tällainen ehdotus.

Tässä olen valmis luokittelemaan "vakiooletukseksi" ehdottoman turvallisuuden satunnainen oraakkelimalli, jos käytetyn SNARKin satunnainen oraakkeli on toteutettu tavallisella hash-funktiolla, kuten KECCAK-256. Satunnainen oraakkelimalli on idealisoitu asetus, jonka tarkoituksena on kaapata hyvin suunniteltujen kryptografisten hajautusfunktioiden käyttäytyminen. Sitä käytetään usein analysoimaan PQ-SNARKien turvallisuutta. 

Esimerkki epätyypillisistä oletuksista ovat olettamukset (kuvattu alla), jotka koskevat protokollan, kuten FRI:n, kvantitatiivista luotettavuutta joko interaktiivisessa ympäristössä tai ei-interaktiivisena protokollana satunnaisessa oraakkelimallissa.

SNARK-suunnittelijat innovoivat monilla jännittävillä tavoilla, joista osa saattaa nostaa verhoa turvallisuuden kannalta – esimerkiksi käyttämällä SNARK-ystävällisiä hash-funktioita, joita ei ole alettu yhtä paljon krypta-analyysiin kuin tavallisempia hash-funktioita. En vaadi tällaisten ponnistelujen lopettamista – kaukana siitä. Mutta nämä primitiivit tulisi ilmentää suojaustasoilla, jotka ylittävät tunnetut, mahdolliset hyökkäykset reilusti yli 10 bitillä. 

SNARKeja käyttävien tiivistelmien kuvataan yleensä perivän L1:n suojauksen. Mutta tämä on vaikea tapaus tehdä, jos ne on määritetty paljon alhaisemmille suojaustasoille kuin mitkään L1:n käyttämät kryptografiset primitiivit. Koska SNARKit näkevät yleistyvän omaksumisen, meidän tulee varmistaa, että otamme ne käyttöön tavoilla, jotka ovat yhdenmukaisia ​​sen kanssa, miten heistä puhumme. Niin kauan kuin SNARKit analysoidaan huolellisesti, konfiguroidaan asianmukaisesti ja toteutetaan oikein, ne ovat yhtä turvallisia kuin mikä tahansa nykyään käytössä oleva salausprimitiivi. 

Sivu: Sukellus entistä syvemmälle PQ-SNARK-turvallisuuteen

StarkWaren PQ-SNARK:ien 80 bitin suojaus huomioidaan seuraavasti. Nämä PQ-SNARKit käyttävät polynomista sitoutumisjärjestelmää nimeltä Perjantai, ja StarkWaren SHARP-todentaja suorittaa FRI:n 48-bittisellä suojauksella olettaen. Karkeasti sanottuna olettamus on, että yksinkertainen hyökkäys FRI:n luotettavuuteen on optimaalinen. Tässä hyökkäyksessä huijauksen todistaja luo pienellä vaivalla "FRI-todistuksen", joka läpäisee todentajan satunnaisesti valitsemat tarkastukset todennäköisyydellä 2^-48. 

StarkWare yhdistää FRI:n tekniikkaan nimeltä "hionta". Tämä edellyttää, että rehellinen todistaja tuottaa 32-bittisen todisteen työstä ennen FRI-todistuksen tuottamista. Hionnan etuna on, että se lisää huomattavasti työtä, joka vaaditaan huijaustodistajalta edellä mainitun yksinkertaisen hyökkäyksen FRI:tä vastaan, noin 2:een.³² hash-arvioinnit. 

Koska (odotusten mukaan) 2⁴⁸ yksinkertaisen hyökkäyksen yritykset ovat välttämättömiä ennen kuin yksi niistä onnistuu, kokonaistyömäärä, joka huijaustodistajan on tehtävä väärentääkseen FRI-todistuksen, on noin 2⁴⁸ * 2³² = 2⁸⁰ hash-arvioinnit.

Lopuksi kerrotaan, kuinka FRI:n 48 bitin suojaus syntyy. FRI-todentaja tekee "kyselyitä" sitoutuneelle polynomille. FRI-varmennuskustannukset kasvavat lineaarisesti kyselyjen määrän myötä. Esimerkiksi 36 FRI-vahvistajan kyselyä ovat noin 4 kertaa kalliimpia kuin 9 kyselyä. Mutta enemmän kyselyitä lisää turvallisuutta. "Suojausbittien määrä kyselyä kohti" riippuu toisesta FRI:n parametrista, jota kutsutaan koodinopeudeksi. 

Tarkemmin sanottuna FRI käyttää jotain nimeltä Reed-Solomon korkokoodi r, Jossa r on aina luku tiukasti välillä 0 ja 1. FRI-todistajan kustannukset ovat kääntäen verrannollisia r, joten nopeus 1/16 johtaa todisteeseen, joka on noin neljä kertaa hitaampi ja tilaa vievämpi kuin nopeus ¼. 

SHARP-todentaja on käyttänyt FRI:tä koodinopeudella 1/16 ja 12 vahvistuskyselyllä.

StarkWare olettaa, että jokainen FRI-todentajakysely lisää lokin₂(1 /r) turvaa. Tämän olettamuksen mukaan 12 todentajakyselyä tuottaa 12 * lokia₂(16) = 48 bittiä suojausta.

Nykyiset analyysit osoittavat kuitenkin vain, että jokainen todentajakysely lisää hieman vähemmän kuin loki₂(1/r^1/2) turvaa. Joten 12 FRI-todentajakyselyä tuottaa vain alle 12 * lokin₂(4) = 24 bittiä "todistettavaa" turvallisuutta. 

Ehdotus turvallisuuden ja suorituskyvyn välisen jännitteen lieventämiseksi

Käytännöllisissä PQ-SNARKeissa on todentamiskustannukset, jotka kasvavat lineaarisesti halutun tietoturvabittien määrän kanssa. Yksi lupaava tekniikka tämän jännitteen lieventämiseksi on SNARK-koostumus – jota kuvailin edellisessä viestissäni keinona ratkaista todentaja- ja todentajakustannusten välinen jännitys, mutta se voi myös käsitellä turvallisuutta. 

Kaksi esimerkkiä 

Monikulmio Hermez on PQ-SNARKien säveltäminen PlonK:n kanssa. Ajatuksena on, että todistaja generoi ensin PQ-SNARK-todistuksen π. Jos PQ-SNARK on määritetty käyttämään nopeaa testausta ja riittävää suojaustasoa, π on suuri. Todistaja ei siis lähetä π:ää todentajalle. Sen sijaan se käyttää PlonK:ta todistamaan, että se tietää π:n. 

Tämä tarkoittaa PlonK:n soveltamista piiriin, joka ottaa π:n tulona ja tarkistaa, että PQ-SNARK-todentaja hyväksyy π:n. Koska PQ-SNARKilla on polylogaritminen varmennuskustannukset, PlonK:ta sovelletaan pieneen piiriin, ja siksi PlonK-todistaja on nopea. Koska PlonK-todisteet ovat pieniä ja halpoja todentaa, varmennuskustannukset ovat alhaiset. 

Valitettavasti PlonK:n käyttö tuhoaa läpinäkyvyyden ja kvanttiturvallisuuden. Sen sijaan voidaan harkita PQ-SNARKin käyttämistä PlonK:n sijasta π:n tuntemisen osoittamiseksi (itse asiassa Polygonin käyttämä PQ-SNARK on itse laadittu tällä tavalla). 

Tässä toisessa PQ-SNARK-sovelluksessa π:n tuntemisen osoittamiseksi järjestelmä voidaan konfiguroida saavuttamaan riittävä turvallisuus kohtuullisen kokoisilla todisteilla, esimerkiksi valitsemalla erittäin pieni koodinopeus käytettäväksi FRI:ssä. Keskeinen asia on, että vaikka tämä pieni koodinopeus on huono testausajalle, PQ-SNARKin toista sovellusta sovelletaan vain pieneen piiriin, joten kokonaistodistusajan pitäisi silti olla pieni.

Teoreettinen ymmärryksemme koottujen SNARKien turvallisuudesta jättää paljon toivomisen varaa. Niitä vastaan ​​ei kuitenkaan ole tunnettuja hyökkäyksiä, jotka olisivat nopeampia kuin hyökkääminen yksittäistä SNARKia vastaan. Jos esimerkiksi kirjoitetaan PQ-SNARKI PlonK:n kanssa, emme tiedä parempaa hyökkäystä kuin joko hyökätä PQ-SNARKIin (eli löytää PQ-SNARKin todiste π väärästä lausunnosta) tai hyökätä PlonK:ta vastaan ​​(ts. löydä PlonK-todiste väärälle väitteelle "Tiedän PQ-SNARK-todistuksen π, jonka todentaja olisi hyväksynyt.")

SNARKien säveltäminen tällä tavalla on yhä suositumpi tapa parantaa suorituskykyä. Toivon, että myös protokollasuunnittelijat käyttävät sitä turvallisuuden parantamiseen.

***

Justin Thaler on apulaisprofessori Georgetownin yliopistossa. Ennen Georgetowniin tuloaan hän työskenteli kaksi vuotta tutkijana Yahoo Labsissa New Yorkissa, mitä ennen hän oli tutkijana Simons Institute for the Theory of Computing UC Be:ssärkeley. 

Toimittaja: Tim Sullivan @tim_org

***

Tässä esitetyt näkemykset ovat yksittäisen AH Capital Management, LLC:n ("a16z") lainaaman henkilöstön näkemyksiä, eivätkä ne ole a16z:n tai sen tytäryhtiöiden näkemyksiä. Tietyt tähän sisältyvät tiedot on saatu kolmansien osapuolien lähteistä, mukaan lukien a16z:n hallinnoimien rahastojen kohdeyrityksiltä. Vaikka a16z on otettu luotettaviksi uskotuista lähteistä, se ei ole itsenäisesti tarkistanut tällaisia ​​tietoja eikä esitä tietojen pysyvää tarkkuutta tai sen soveltuvuutta tiettyyn tilanteeseen. Lisäksi tämä sisältö voi sisältää kolmannen osapuolen mainoksia; a16z ei ole tarkistanut tällaisia ​​mainoksia eikä tue mitään niiden sisältämää mainossisältöä.

Tämä sisältö on tarkoitettu vain tiedoksi, eikä siihen tule luottaa lainopillisena, liike-, sijoitus- tai veroneuvona. Näissä asioissa kannattaa kysyä neuvojanne. Viittaukset arvopapereihin tai digitaaliseen omaisuuteen ovat vain havainnollistavia, eivätkä ne ole sijoitussuositus tai tarjous tarjota sijoitusneuvontapalveluita. Lisäksi tämä sisältö ei ole suunnattu eikä tarkoitettu sijoittajien tai mahdollisten sijoittajien käytettäväksi, eikä siihen voida missään olosuhteissa luottaa tehdessään sijoituspäätöstä mihinkään a16z:n hallinnoimaan rahastoon. (A16z-rahastoon sijoitustarjous tehdään vain minkä tahansa tällaisen rahaston suunnatun osakeannin muistion, merkintäsopimuksen ja muiden asiaankuuluvien asiakirjojen perusteella, ja ne tulee lukea kokonaisuudessaan.) Kaikki mainitut sijoitukset tai kohdeyritykset, joihin viitataan, tai kuvatut eivät edusta kaikkia investointeja a16z:n hallinnoimiin ajoneuvoihin, eikä voi olla varmuutta siitä, että investoinnit ovat kannattavia tai että muilla tulevaisuudessa tehtävillä investoinneilla on samanlaisia ​​ominaisuuksia tai tuloksia. Luettelo Andreessen Horowitzin hallinnoimien rahastojen tekemistä sijoituksista (lukuun ottamatta sijoituksia, joiden osalta liikkeeseenlaskija ei ole antanut a16z:lle lupaa julkistaa, sekä ennalta ilmoittamattomat sijoitukset julkisesti noteerattuihin digitaalisiin omaisuuseriin) on saatavilla osoitteessa https://a16z.com/investments /.

Kaaviot ja kaaviot ovat vain tiedoksi, eikä niihin tule luottaa sijoituspäätöstä tehtäessä. Aiempi kehitys ei kerro tulevista tuloksista. Sisältö puhuu vain ilmoitetun päivämäärän mukaan. Kaikki näissä materiaaleissa esitetyt ennusteet, arviot, ennusteet, tavoitteet, näkymät ja/tai mielipiteet voivat muuttua ilman erillistä ilmoitusta ja voivat poiketa tai olla ristiriidassa muiden ilmaisemien mielipiteiden kanssa. Tärkeitä lisätietoja on osoitteessa https://a16z.com/disclosures.