SNARK Sikkerhet og ytelse

A SNARK (Succinct Non-interactive Argument of Knowledge) er et kryptografisk verktøy som åpner for spennende nye muligheter innen systemdesign, spesielt i desentraliserte omgivelser. SNARK-er lar data behandles av upålitelige enheter, som deretter kan bevise at dataene er gyldige og har blitt behandlet riktig. En naiv måte å bevise dette på er å publisere dataene, slik at alle som ønsker kan sjekke gyldigheten og behandle dem direkte. 

En SNARK oppnår samme effekt, men med bedre kostnads til validatorene. For eksempel, i en lag-to (L2) verifiserbar sammenrulling, behandler en sammenrullingstjeneste blokkjedetransaksjoner. Tjenesten poster med jevne mellomrom brukernes kontosaldo til lag-ett-blokkjeden. Hver gang den legger inn en oppdatering til saldoene, legger den til et SNARK-bevis på at den kjenner en sekvens av gyldige transaksjoner som endret de gamle kontosaldoene til de oppdaterte. På denne måten trenger blokkjedevalidatorer ikke å gjøre det harde arbeidet med å sjekke transaksjonsgyldighet (f.eks. sjekke en digital signatur for hver transaksjon) eller eksplisitt behandle transaksjonene for å beregne de oppdaterte saldoene.  

My Forrige innlegg fokusert på ytelsen til SNARK-provere – den primære determinanten for SNARK-anvendbarhet. Selv om det kan være beregningsintensivt å kjøre en SNARK-prover, i den grad det kan være umulig å generere et bevis for beregninger i stor skala, er SNARK-verifisering vanligvis langt billigere enn direkte kontroll og behandling av data. SNARK-verifiseringskostnadene varierer imidlertid betydelig. Dette innlegget pakker ut disse kostnadene og sammenligner sikkerhetsegenskapene til forskjellige SNARK-er. 

Spesielt forklarer jeg at i praktiske SNARKer med plausibel postkvantesikkerhet (PQ-SNARKs) er det et betydelig spenningsforhold mellom sikkerhet og verifikasjonskostnader. Dessuten, i noen tilfeller, løses denne spenningen for tiden til fordel for verifikasjonskostnader fremfor sikkerhet.

For at SNARK-er skal realisere potensialet sitt, må distribuerte systemer være sikre og brukere må være trygge på sikkerheten deres. Jeg avslutter innlegget med å foreslå enkle handlinger som web3-fellesskapet kan ta for å sikre at disse egenskapene holder på lang sikt. 

Kvantitative sikkerhetstiltak 

En SNARK er sikker hvis det er beregningsmessig umulig å produsere et overbevisende bevis på en falsk påstand. For eksempel, i sammenheng med L2-sammenrullinger, vil en angriper som ønsker å stjele pengene mine ønske å bevise en falsk erklæring av skjemaet: "Jeg kjenner en digitalt signert transaksjon som overfører alle Justins eiendeler til min egen konto." 

Sikkerhetsnivået til en SNARK måles etter mengden arbeid som må gjøres for å finne et overbevisende bevis på en falsk erklæring. I likhet med andre kryptografiske primitiver som digitale signaturer, blir logaritmen til denne mengden arbeid referert til som "sikkerhetsbitene." For eksempel innebærer 30 bits sikkerhet at 2³⁰ ≈ 1 milliard «arbeidssteg» kreves for å angripe SNARK. Dette er iboende et omtrentlig mål på sikkerhet i den virkelige verden fordi forestillingen om ett arbeidstrinn kan variere, og praktiske hensyn som minnekrav eller muligheter for parallellitet vurderes ikke.

Og kvalitative

Biter av sikkerhet er en kvantitativ mål på sikkerheten til en SNARK. SNARK er også forskjellige i deres kvalitativ sikkerhetsegenskaper. 

Noen SNARK-er krever for eksempel en pålitelig oppsettseremoni for å generere en strukturert bevisnøkkel. SNARK-er som ikke krever et klarert oppsett i det hele tatt kalles gjennomsiktig. 

For at en ugjennomsiktig SNARK skal være sikker, må vanligvis minst én deltaker i seremonien ha opptrådt ærlig, noe som betyr at de produserte og deretter kastet en "felledør" som, hvis den ble kombinert med alle andre deltakere, ville gjøre det enkelt for å finne overbevisende SNARK "bevis" for enhver falsk påstand. Klarerte oppsett er være løpe med hundrevis eller tusenvis av deltakere for å gjøre denne antagelsen så mild som mulig. 

SNARK er også forskjellig i deres mottakelighet for kvanteangrep. Spesielt mange SNARK-er (f.eks. Groth16, PlonK, Marlin, Skuddsikker, Nova) stole på antakelsen om at diskrete logaritmer er vanskelige å beregne (og i noen tilfeller også ytterligere forutsetninger). Å beregne diskrete logaritmer er noe som kvantedatamaskiner ville være i stand til å gjøre effektivt. Derfor er disse SNARKene ikke post-kvantesikre (ikke-PQ). 

Mens det haster med å gå over til postkvante krypteringsordninger, er dette først og fremst drevet av behovet for å holde krypterte meldinger hemmelige mange tiår inn i fremtiden. En motstander som lagrer en avlyttet melding i dag og venter på at en kvantedatamaskin kommer om for eksempel femti år, kan bruke datamaskinen til å dekryptere den femti år gamle meldingen. Situasjonen med SNARK-er er ganske annerledes. Bruken av ikke-PQ SNARK-er i dag bør ikke kompromittere sikkerheten til blokkjeder femti år i fremtiden, selv om kvantedatamaskiner kommer innen den tid. 

Polynomiske forpliktelser

Alle SNARK-er bruker en kryptografisk primitiv kjent som en polynomisk forpliktelsesordning, og denne komponenten er ofte en ytelsesflaskehals. (For detaljer, se min Forrige innlegg.) I tillegg bestemmes en SNARKs åpenhet og plausible postkvantesikkerhet utelukkende av polynomforpliktelsesordningen den bruker. 

Et fremtredende eksempel er såkalt KZG polynomforpliktelser, som brukes av PlonK, Marlin, og mange andre. KZG-forpliktelser er verken transparente eller post-kvantesikre. Andre forpliktelsesordninger er transparente, men ikke postkvante, inkludert Skuddsikker, hyraxog Dory. 

Atter andre ordninger er både transparente og plausibelt postkvante. Disse inkluderer Fredag, ligero, Ligero++, Bryte sammenog Orion. Alle disse ordningene er basert på feilrettingskoder. Hashing er det eneste kryptografiske primitivet de bruker. De deler også følgende egenskap: verifikasjonskostnader (målt ved antall hash-evalueringer og feltoperasjoner) vokser lineært med antall sikkerhetsbiter.

Grovt sett oppnår en enkelt "iterasjon" av disse postkvantepolynomforpliktelsene bare et lite antall (for eksempel 2-4) sikkerhetsbiter. Så protokollen må gjentas mange ganger for å "forsterke" sikkerhetsnivået, med bekreftelseskostnadene som vokser med hver repetisjon. For å kontrollere verifikasjonskostnadene i PQ-SNARKs (og dermed gasskostnadene i blockchain-applikasjoner) blir protokolldesignere incentivert til å holde sikkerhetsnivået lavt. 

Med sjeldne unntak, denne spenningen mellom konkrete sikkerhet og verifikasjonskostnader oppstår ikke i ikke-PQ SNARKs (gjennomsiktig og ugjennomsiktig). Ikke-PQ-SNARK-er bruker elliptiske kurvegrupper der diskrete logaritmer antas å være vanskelig å beregne, og sikkerhetsnivåene deres bestemmes av gruppen som brukes. Størrelsen på den aktuelle elliptiske kurvegruppen, og dermed kostnadene for hver gruppeoperasjon, vokser med ønsket sikkerhetsnivå. Imidlertid Antall av gruppeelementer i et bevis er uavhengige av valg av gruppe. 

I PQ-SNARKs vokser ikke bare størrelsen på hash-evalueringer lineært med ønsket sikkerhetsnivå, det samme gjør antallet evalueringer som er inkludert i beviset og utført av verifikatoren. 

Konkrete verifikatorkostnader og sikkerhet i utplasserte SNARK-er

Kostnadene for konkrete verifikatoren og sikkerhetsnivåene til utplasserte SNARK-er varierer betydelig. Her er noen illustrative eksempler:

Verifikatorkostnader 

My Forrige innlegg nevnte to eksempler på konkrete verifikasjonskostnader: PlonK bevis koster etter 300,000 gass å verifisere på Ethereum, mens StarkWare sine bevis koster rundt 5 millioner gass. StarkWares bevis er transparente og plausibelt postkvante mens PlonKs ikke er det. Imidlertid, som detaljert neste, kjøres StarkWares bevis på et mye lavere sikkerhetsnivå enn PlonK-bevis på Ethereum.

Betong sikkerhet

Den eneste elliptiske kurven med Ethereum-prekompilere kalles altbn128, så dette er kurven alle ikke-PQ SNARK-er distribuert på Ethereum-bruk, inkludert Aztec's og zkSync's. Denne kurven - og dermed også de utplasserte SNARK-ene som bruker den - ble opprinnelig antatt å tilby omtrent 128 bits sikkerhet. Men pga forbedrede angrep (den nøyaktige kjøretiden er vanskelig å bestemme), er kurven nå ansett for å tilby 100 til 110 bits sikkerhet. 

Det er EIPer etter hensyn å introdusere prekompilere for forskjellige kurver som fortsatt antas å tilby nær 128 bits sikkerhet. Slike kurver er allerede brukt i SNARK-ene til ikke-Ethereum-prosjekter inkludert ZCash, Algorand, Dfinity, Filecoin og Aleo. 

I motsetning til dette, ifølge on-chain-data, har StarkWares PQ-SNARKs (i dets såkalte SHARP-system, forkortelse for SHARed Prover) blitt konfigurert til å målrette 80 bits sikkerhet. Dette sikkerhetsnivået gjelder for visse antagelser om den statistiske soliditeten til FRI (som jeg skal ta opp senere i dette innlegget). 

Begrepet "80 bits of security" er vagt i denne sammenhengen, så la meg pakke det ut. Grovt sett betyr det at en angriper kan produsere et overbevisende bevis på en falsk påstand ved å evaluere en hashfunksjon 2⁸⁰ ganger (nemlig KECCAK-256, hash-funksjonen som brukes av Ethereum). For å være mer presis, en angriper som er villig til å utføre 2^k hasj-evalueringer kan gi et overbevisende bevis med en sannsynlighet på omtrent 2^k-80. For eksempel med 2⁷⁰ hash-evalueringer, kan man finne et SNARK "bevis" på en falsk utsagn med en sannsynlighet på ca. 2^-10 = 1/1024. 

Denne forestillingen er svakere enn hva begrepet "80 bits of security" betyr i andre sammenhenger. For eksempel vil en kollisjonsbestandig hash-funksjon (CRHF) konfigurert til 80 bits sikkerhet produsere 160-bits utganger. Hvis hash-funksjonen er godt utformet, vil den raskeste prosedyren for å finne kollisjon være Bursdagsangrep, en brute-force-prosedyre som kan finne en kollisjon med omtrent 2^160/2 = 2⁸⁰ hasjevalueringer. Imidlertid med 2^k hash-evalueringer, vil bursdagsangrepet finne en kollisjon med en sannsynlighet på bare 2^2k-160. 

For eksempel 2⁷⁰ hash-evalueringer vil gi en kollisjon med en sannsynlighet på 2^-20  ≈ 1/1,000,000 1 1,000. Dette er langt mindre enn 80/XNUMX XNUMX-sannsynligheten for at en angriper smir et PQ-SNARK-bevis konfigurert til XNUMX bits sikkerhet. 

Denne forskjellen kan drastisk endre attraktiviteten ved å utføre et angrep. For å illustrere, forestill deg at en angriper har et budsjett på $100K, som kan kjøpe 2⁷⁰ hasjevalueringer. Og anta at dersom angriperen skulle lykkes, er utbetalingen $200 millioner. Den forventede verdien av angrepet mot en PQ-SNARK konfigurert til 80 bits sikkerhet er (1/1,000) * 200 millioner dollar, eller 200 1 dollar – det dobbelte av kostnadene. Hvis suksesssannsynligheten bare var 1,000,000/200 XNUMX XNUMX, som med en CRHF, ville den forventede verdien av angrepet være bare $XNUMX. 

De to forestillingene om "80 biter av sikkerhet" skiller seg også dramatisk i deres robusthet overfor uavhengige angrep. Anta for eksempel at 1,000 uavhengige parter hver angriper PQ-SNARK ved å utføre 2⁷⁰ hasjevalueringer. Siden hver lykkes med en sannsynlighet på omtrent 1/1,000, er det ganske sannsynlig at minst én av dem lykkes. Dette ville ikke vært tilfelle hvis hver enkelt lykkes med en sannsynlighet på bare 1/1,000,000 XNUMX XNUMX.

Godt utformede elliptiske kurvegrupper forventes å oppføre seg på samme måte som CRHF-er, med bursdagslignende angrep som f.eks. Pollards rho-algoritme å være den mest kjente. Dette betyr at i en gruppe som tilbyr 128 bits sikkerhet, 2^k gruppeoperasjoner skal gi en løsning på en forekomst av det diskrete logaritmeproblemet med en sannsynlighet på bare 2^2k-256. For eksempel 2⁷⁰ gruppeoperasjoner vil finne en diskret logaritme med bare en astronomisk liten sannsynlighet på 2^-116. Dessuten er hver gruppeoperasjon langsommere enn en CRHF-evaluering. 

Hvor mange hasj-evalueringer er gjennomførbare i dag?

I januar 2020 er kostnadene ved å beregne bare 2⁶⁴ SHA-1-evalueringer ved bruk av GPUer var $45,000. Dette koster 2⁷⁰ SHA-1-evalueringer på GPU-er til noen få millioner dollar (kanskje lavere etter Ethereum-sammenslåingen, ettersom overgangen bort fra GPU-dominert proof of work mining sannsynligvis vil redusere etterspørselen etter GPU-databehandling, og redusere kostnadene). 

Med gyldighetssammendrag som allerede lagrer hundrevis av millioner dollar i brukermidler, kan det å finne et overbevisende bevis på en falsk erklæring gi mange millioner dollar i fortjeneste. Konfigurering av en PQ-SNARK med 80 bits sikkerhet under aggressive formodninger gir under 10 bits slingringsmonn mellom lønnsomme angrep og den antatte sikkerheten til PQ-SNARK.

Som et annet datapunkt er Bitcoins hashrate for nettverket for øyeblikket omtrent 2⁶⁴  hasjevalueringer per sekund, som betyr at bitcoin-gruvearbeidere som helhet utfører 2⁸⁰ SHA-256-evalueringer hver 18. time. Selvfølgelig skyldes dette iøynefallende tallet den enorme investeringen i ASIC-er for bitcoin-gruvedrift. 

Forutsatt seks bitcoin-blokker opprettet per time, og gitt gjeldende blokkbelønning på 6.25 Bitcoin per blokk, disse 2⁸⁰ SHA-256-evalueringer koster antagelig mindre enn $22,000 18 * 6 * 6.25 * 15 ≈ $XNUMX millioner. Ellers ville bitcoin-gruvedrift ikke vært lønnsomt med dagens priser. 

Foreslåtte tiltak for et sunt økosystem

Hele poenget med å bruke SNARK-er i sammenrullinger er å oppnå skalerbarhet for blokkjeder uten at brukere trenger å stole blindt på sammenrullingstjenesten. Siden opprullingstjenesten skrev den smarte kontrakten som fungerer som SNARK-verifikator, må publikum kunne inspisere kontrakten og bekrefte at den faktisk verifiserer SNARK-bevis for de riktige uttalelsene. Offentlig gransking av den smarte kontrakten kan også være nødvendig for å sikre at sammenrullingstjenesten ikke er i stand til å sensurere sine egne brukere. Foreslåtte metoder for sensurmotstand krever sammendragets smarte kontrakt for å tillate brukere å tvinge ut pengene sine hvis sammendragstjenesten ikke klarer å behandle transaksjonene deres. 

Gitt den sofistikerte karakteren til disse protokollene, legger dette paradigmet for offentlig gransking en viss byrde på eksperter for åpent og ærlig å diskutere sikkerheten til de utplasserte kontraktene. 

Men med PQ-SNARK-er kan det være vanskelig selv for eksperter å fastslå sikkerhetsnivået til den utplasserte protokollen av samme grunn som sikkerhet og verifikatorytelse står i spenning for disse SNARK-ene: sikkerhetsnivået (og verifikatorens kostnader) avhenger av interne parametere til SNARK. Og i det minste for StarkWare smarte kontrakter, disse parameterne, called logBlowupFactor, proofOfWorkBits og n_Queries er ikke direkte spesifisert i smartkontraktens kode, men sendes til smartkontrakten som offentlige data. Så vidt jeg vet, er den enkleste måten å identifisere disse parameterne fra informasjon på kjeden via en fire-trinns prosess: 

1. se på passende smart kontrakt på en blokkutforsker som Etherscan, 
2. klikk på en passende "verifiser bevis"-transaksjon, 
3. dekode transaksjonens inndata, og
4. finne ut hvordan tolke de dekodede inngangsdataene for å lære de viktigste SNARK-parametrene som sammen bestemmer sikkerhetsnivået. 

Dette siste trinnet krever å finne den riktige Solidity-koden som implementerer transaksjonen, noe som i seg selv kan være en forvirrende oppgave. (Da jeg forberedte meg Undersøkelsen snakker på sammendrag i sommer, var Etherscan i stand til å dekode de relevante inngangsdataene til SHARP-verifikatorens transaksjoner i henhold til trinn 2 ovenfor. Men det ser ikke ut til å fungere lenger.)

Forslag 1: Gransking 

Med dette i tankene, er mitt første forslag til web3-fellesskapet å gjøre det langt enklere å granske sikkerhetsnivået til utplasserte post-kvante SNARK-er. Dette innebærer sannsynligvis bedre verktøy for å forstå kjededata og økt åpenhet fra prosjektene selv når det gjelder å gjøre disse parametrene kjent. 

Forslag 2: Sterkere normer

80 bits sikkerhet er for lavt, spesielt den svake versjonen der 2⁷⁰ hash-evalueringer er nok til å lykkes med å angripe med en sannsynlighet på omtrent 1/1000 – enda mer gitt den lange historien med overraskende angrep på kryptografiske primitiver. En, nevnt ovenfor, er bedre angrep på paringsvennlige elliptiske kurver som altbn128. Et mer kjent eksempel er SHA-1, som ble standardisert til 80 bits sikkerhet, men som til slutt ble vist å oppnå bare rundt 60 biter. Med denne historien i tankene, bør PQ-SNARK-designere gi seg selv mer enn 10 bits slingringsmonn når de konfigurerer sikkerhetsnivået, spesielt hvis sikkerhetsanalysen involverer sterke formodninger om den statistiske sikkerheten til relativt nye protokoller som FRI.

Selv for PQ-SNARK-er kan passende sikkerhetsnivåer alltid oppnås, ganske enkelt ved å øke verifiseringskostnadene. For eksempel vil øke sikkerheten til SHARPs verifikator fra 80 til 128 biter (under antagelser om FRIs statistiske soliditet) øke gasskostnadene med omtrent en faktor to, fra litt over 5 millioner til litt over 10 millioner. Uten formodninger om FRI ville gasskostnadene øke med ytterligere to faktorer, til over 20 millioner. 

Mitt neste forslag er derfor at web3-fellesskapet bør utvikle sterkere normer rundt passende sikkerhetsnivåer for utplasserte SNARK-er. Min personlige anbefaling vil være minst 100 biter, og minst 128 hvis SNARKs sikkerhet er basert på ikke-standardiserte forutsetninger. Jeg er ikke den første som gjør det komme med et slikt forslag.

Her er jeg villig til å kategorisere som en "standard antagelse" ubetinget sikkerhet i tilfeldig orakelmodell, hvis det tilfeldige oraklet i den utplasserte SNARK er instansiert med en standard hash-funksjon som KECCAK-256. Den tilfeldige orakelmodellen er en idealisert innstilling som er ment å fange oppførselen til godt utformede kryptografiske hashfunksjoner. Det brukes ofte til å analysere sikkerheten til PQ-SNARKs. 

Et eksempel på ikke-standardiserte forutsetninger er antagelser (beskrevet nedenfor) angående den kvantitative soliditeten til en protokoll som FRI, enten i en interaktiv setting eller som en ikke-interaktiv protokoll i den tilfeldige orakelmodellen.

SNARK-designere innoverer på mange spennende måter, hvorav noen kan presse rammen når det gjelder sikkerhet – for eksempel ved å bruke SNARK-vennlige hash-funksjoner som ikke har vært utsatt for like mye kryptoanalyse som mer standard hash-funksjoner. Jeg etterlyser ikke en slutt på slike anstrengelser – langt ifra. Men disse primitivene bør instansieres på sikkerhetsnivåer som overstiger kjente, gjennomførbare angrep med godt over 10 biter. 

Sammendrag som bruker SNARK-er, blir ofte beskrevet som å arve sikkerheten til deres L1. Men dette er en vanskelig sak å gjøre hvis de er konfigurert på mye lavere sikkerhetsnivåer enn noen kryptografiske primitiver som brukes av L1. Ettersom SNARKs ser økende adopsjon, bør vi sørge for at vi distribuerer dem på måter som er i samsvar med hvordan vi snakker om dem. Så lenge SNARK-er analyseres nøye, konfigureres riktig og implementeres riktig, er de like sikre som alle kryptografiske primitiv som brukes i dag. 

En side: Dykke enda dypere inn i PQ-SNARK-sikkerhet

De 80 bitene med sikkerhet i StarkWares PQ-SNARKs er regnskapsført som følger. Disse PQ-SNARK-ene bruker en polynomisk forpliktelsesplan kalt Fredag, og StarkWares SHARP-verifikator kjører FRI med 48 bits sikkerhet under en formodning. Grovt sett er formodningen at et enkelt angrep på forsvarligheten til FRI er optimalt. I dette angrepet genererer en juksebeviser, med en liten innsats, et "FRI-bevis" som passerer verifikatorens tilfeldig valgte sjekker med sannsynlighet 2^-48. 

StarkWare kombinerer FRI med en teknikk som kalles "sliping". Dette krever at den ærlige beviseren produserer et 32-biters bevis på arbeidet før det produseres et FRI-bevis. Fordelen med sliping er at det drastisk øker arbeidet som kreves for en juksebeviser for å utføre det enkle angrepet på FRI nevnt ovenfor, til ca.³² hasjevalueringer. 

Siden (i forventning) 2⁴⁸ forsøk på det enkle angrepet er nødvendig før ett av dem er vellykket, den totale mengden arbeid juksebeviseren må gjøre for å forfalske et FRI-bevis er omtrent 2⁴⁸ * 2³² = 2⁸⁰ hasjevalueringer.

Til slutt, la oss pakke ut hvordan de 48 bitene av sikkerhet for FRI oppstår. FRI-verifikatoren gjør "spørringer" til det forpliktede polynomet. FRI-verifiseringskostnadene vokser lineært med antall forespørsler. For eksempel er 36 FRI-bekreftelsesspørringer omtrent 4 ganger så dyre som 9 søk. Men flere spørsmål betyr mer sikkerhet. Antallet "sikkerhetsbiter per spørring" avhenger av en annen parameter i FRI, kalt kodehastigheten. 

Nærmere bestemt bruker FRI noe som kalles Reed-Solomon rate of rate r, Hvor r er alltid et tall strengt tatt mellom 0 og 1. FRI-beviserens kostnader er omvendt proporsjonale med r, så en hastighet på 1/16 fører til en prøve som er omtrent fire ganger langsommere og mer plasskrevende enn en hastighet på ¼. 

SHARP-verifikatoren har kjørt FRI med en kodehastighet på 1/16 og med 12 verifikatorspørringer.

StarkWare antar at hver FRI-bekreftelsesspørring legger til logg₂(1 /r) biter av sikkerhet. Under denne antagelsen gir 12 verifikatorspørringer 12 * logg₂(16) = 48 bits sikkerhet.

Nåværende analyser fastslår imidlertid bare at hver verifikatørspørring legger til litt mindre enn logg₂(1/r^1/2) biter av sikkerhet. Så 12 FRI-verifikatorspørringer gir bare mindre enn 12 * logg₂(4) = 24 bits "påvisbar" sikkerhet. 

Et forslag for å dempe spenningen mellom sikkerhet og ytelse

Praktiske PQ-SNARKs har verifikatorens kostnader som vokser lineært med ønsket antall biter av sikkerhet. En lovende teknikk for å dempe denne spenningen er SNARK-komposisjonen - som jeg beskrev i mitt forrige innlegg som et middel til å løse spenningen mellom prover- og verifikatorens kostnader, men den kan også adressere sikkerhet. 

To eksempler 

Polygon Hermez er komponere PQ-SNARKs med PlonK. Tanken er at beviseren først genererer et PQ-SNARK-bevis π. Hvis PQ-SNARK er konfigurert til å ha en rask prøveversjon og et tilstrekkelig sikkerhetsnivå, vil π være stor. Så beviseren sender ikke π til verifikatoren. I stedet bruker den PlonK for å bevise at den kjenner π. 

Dette betyr å bruke PlonK til en krets som tar π som inngang og kontrollerer at PQ-SNARK-verifikatoren vil akseptere π. Siden PQ-SNARK har polylogaritmiske bekreftelseskostnader, brukes PlonK på en liten krets, og derfor er PlonK-beviseren rask. Siden PlonK-bevis er små og billige å verifisere, er verifiseringskostnadene lave. 

Dessverre ødelegger bruken av PlonK transparens og post-kvantesikkerhet. Man kan i stedet vurdere å bruke selve PQ-SNARK i stedet for PlonK for å bevise kunnskap om π (faktisk er PQ-SNARK brukt av Polygon selvkomponert på denne måten). 

I denne andre applikasjonen av PQ-SNARK, for å bevise kunnskap om π, kan systemet konfigureres til å oppnå tilstrekkelig sikkerhet med bevis av rimelig størrelse, for eksempel ved å velge en veldig liten kodehastighet for bruk i FRI. Hovedpoenget er at selv om denne lille kodehastigheten er dårlig for prøvetid, brukes den andre applikasjonen av PQ-SNARK bare på en liten krets, så den totale prøvetiden bør fortsatt være liten.

Vår teoretiske forståelse av sikkerheten til sammensatte SNARK-er etterlater mye å være ønsket. Imidlertid er det ikke kjente angrep på dem som er raskere enn å angripe en av SNARK-ene individuelt. For eksempel, hvis vi komponerer en PQ-SNARK med PlonK, vet vi ikke et bedre angrep enn å enten angripe PQ-SNARK (dvs. finne et PQ-SNARK-bevis π for en falsk utsagn), eller å angripe PlonK (dvs. finn et PlonK-bevis for den falske påstanden "Jeg vet et PQ-SNARK-bevis π som verifikatoren ville ha akseptert.")

Å komponere SNARK-er på denne måten er en stadig mer populær måte å forbedre ytelsen på. Jeg håper at protokolldesignere også bruker det til å forbedre sikkerheten.

***

Justin Thaler er førsteamanuensis ved Georgetown University. Før han begynte i Georgetown, tilbrakte han to år som forskningsforsker ved Yahoo Labs i New York, før han var stipendiat ved Simons Institute for theory of Computing ved UC Berkeley. 

Redaktør: Tim Sullivan @tim_org

***

Synspunktene som uttrykkes her er de fra individuelle AH Capital Management, LLC (“a16z”) personell som er sitert og er ikke synspunktene til a16z eller dets tilknyttede selskaper. Visse opplysninger her er innhentet fra tredjepartskilder, inkludert fra porteføljeselskaper av fond forvaltet av a16z. Selv om a16z er hentet fra kilder som antas å være pålitelige, har ikke a16z uavhengig verifisert slik informasjon og gir ingen representasjoner om den varige nøyaktigheten til informasjonen eller dens hensiktsmessighet for en gitt situasjon. I tillegg kan dette innholdet inkludere tredjepartsannonser; aXNUMXz har ikke vurdert slike annonser og støtter ikke noe reklameinnhold som finnes deri.

Dette innholdet er kun gitt for informasjonsformål, og bør ikke stoles på som juridisk, forretningsmessig, investerings- eller skatterådgivning. Du bør rådføre deg med dine egne rådgivere om disse sakene. Referanser til verdipapirer eller digitale eiendeler er kun for illustrasjonsformål, og utgjør ikke en investeringsanbefaling eller tilbud om å tilby investeringsrådgivningstjenester. Videre er dette innholdet ikke rettet mot eller ment for bruk av noen investorer eller potensielle investorer, og kan ikke under noen omstendigheter stoles på når du tar en beslutning om å investere i et fond som forvaltes av a16z. (Et tilbud om å investere i et a16z-fond vil kun gis av det private emisjonsmemorandumet, tegningsavtalen og annen relevant dokumentasjon for et slikt fond og bør leses i sin helhet.) Eventuelle investeringer eller porteføljeselskaper nevnt, referert til, eller beskrevet er ikke representative for alle investeringer i kjøretøy forvaltet av a16z, og det kan ikke gis noen garanti for at investeringene vil være lønnsomme eller at andre investeringer som gjøres i fremtiden vil ha lignende egenskaper eller resultater. En liste over investeringer foretatt av fond forvaltet av Andreessen Horowitz (unntatt investeringer som utstederen ikke har gitt tillatelse til at a16z kan offentliggjøre så vel som uanmeldte investeringer i børsnoterte digitale eiendeler) er tilgjengelig på https://a16z.com/investments /.

Diagrammer og grafer gitt i er kun for informasjonsformål og bør ikke stoles på når du tar investeringsbeslutninger. Tidligere resultater er ikke en indikasjon på fremtidige resultater. Innholdet taler kun fra den angitte datoen. Eventuelle anslag, estimater, prognoser, mål, prospekter og/eller meninger uttrykt i dette materialet kan endres uten varsel og kan avvike eller være i strid med meninger uttrykt av andre. Vennligst se https://a16z.com/disclosures for ytterligere viktig informasjon.