SNARK sikkerhed og ydeevne

A SNARK (Succinct Non-interactive Argument of Knowledge) er et kryptografisk værktøj, der åbner for spændende nye muligheder inden for systemdesign, især i decentrale indstillinger. SNARK'er tillader, at data behandles af upålidelige enheder, som derefter kan bevise, at dataene er gyldige og er blevet behandlet korrekt. En naiv måde at bevise dette på ville være at offentliggøre dataene, så alle, der ønsker, kan kontrollere deres gyldighed og behandle dem direkte. 

En SNARK opnår samme effekt, men med bedre omkostningers til validatorerne. For eksempel, i en lag-to (L2) verificerbar rollup, behandler en rollup-tjeneste blockchain-transaktioner. Tjenesten bogfører med jævne mellemrum sine brugeres kontosaldi til lag-et blockchain. Hver gang den sender en opdatering til saldierne, tilføjer den et SNARK-bevis på, at den kender en sekvens af gyldige transaktioner, der ændrede de gamle kontosaldi til de opdaterede. På denne måde behøver blockchain-validatorer ikke at gøre det hårde arbejde med at kontrollere transaktionens gyldighed (f.eks. kontrollere en digital signatur for hver transaktion) eller eksplicit behandle transaktionerne for at beregne de opdaterede saldi.  

My forrige indlæg fokuseret på ydeevnen af ​​SNARK-provere – den primære determinant for SNARK-anvendelighed. Selvom det kan være beregningskrævende at køre en SNARK-prover, i det omfang det kan være umuligt at generere et bevis for beregninger i stor skala, er SNARK-verifikation typisk langt billigere end direkte kontrol og behandling af data. SNARK-verifikationsomkostningerne varierer dog betydeligt. Dette indlæg udpakker disse omkostninger og sammenligner sikkerhedsegenskaberne for forskellige SNARK'er. 

Specielt forklarer jeg, at der i praktiske SNARK'er med plausibel postkvantesikkerhed (PQ-SNARK'er) er en betydelig spænding mellem sikkerheds- og verifikationsomkostninger. Desuden er denne spænding i nogle tilfælde ved at blive løst til fordel for verifikationsomkostninger frem for sikkerhed.

For at SNARK'er kan realisere deres potentiale, skal installerede systemer være sikre, og brugerne skal være sikre på deres sikkerhed. Jeg afslutter indlægget med at foreslå simple handlinger, som web3-fællesskabet kan tage for at sikre, at disse egenskaber holder på lang sigt. 

Kvantitative sikkerhedsforanstaltninger 

En SNARK er sikker, hvis det er beregningsmæssigt umuligt at frembringe et overbevisende bevis for en falsk erklæring. For eksempel, i forbindelse med L2-oprulninger, vil en angriber, der ønsker at stjæle mine penge, gerne bevise en falsk erklæring af formularen: "Jeg kender en digitalt signeret transaktion, der overfører alle Justins aktiver til min egen konto." 

Sikkerhedsniveauet for en SNARK måles ved mængden af ​​arbejde, der skal gøres for at finde et overbevisende bevis for en falsk erklæring. I lighed med andre kryptografiske primitiver som digitale signaturer, omtales logaritmen af ​​denne mængde arbejde som "sikkerhedsstykkerne". For eksempel indebærer 30 bits sikkerhed, at 2³⁰ ≈ 1 milliard "arbejdstrin" er påkrævet for at angribe SNARK. Dette er i sagens natur et omtrentligt mål for sikkerhed i den virkelige verden, fordi ideen om et arbejdstrin kan variere, og praktiske overvejelser som hukommelseskrav eller muligheder for parallelitet tages ikke i betragtning.

Og kvalitative

Bits af sikkerhed er en kvantitativ mål for sikkerheden af ​​en SNARK. SNARKs adskiller sig også i deres kvalitative sikkerhedsegenskaber. 

For eksempel kræver nogle SNARK'er en betroet opsætningsceremoni for at generere en struktureret bevisnøgle. SNARK'er, der slet ikke kræver en betroet opsætning, kaldes gennemsigtig. 

For at et ikke-gennemsigtigt SNARK skal være sikkert, skal mindst én deltager i ceremonien typisk have opført sig ærligt, hvilket betyder, at de producerede og derefter kasserede en "fældelåge", der, hvis den kombineres med alle andre deltageres fældelåger, ville gøre det nemt at finde overbevisende SNARK "beviser" for enhver falsk erklæring. Pålidelige opsætninger er være køre med hundreder eller tusinder af deltagere for at gøre denne antagelse så mild som muligt. 

SNARK'er adskiller sig også i deres modtagelighed for kvanteangreb. Specifikt mange SNARK'er (f.eks. Groth16, PlonK, Marlin, Bulletproofs, Nova) stole på den antagelse, at diskrete logaritmer er vanskelige at beregne (og i nogle tilfælde også yderligere antagelser). At beregne diskrete logaritmer er noget, som kvantecomputere ville være i stand til effektivt. Derfor er disse SNARK'er ikke post-kvantesikre (ikke-PQ). 

Mens der er akutte bestræbelser på at skifte til post-kvante krypteringsordninger, er dette primært drevet af behovet for at holde krypterede beskeder hemmelige mange årtier ud i fremtiden. En modstander, der gemmer en opsnappet besked i dag og venter på, at en kvantecomputer ankommer om for eksempel halvtreds år, kan bruge computeren til at dekryptere den halvtreds år gamle besked. Situationen med SNARKs er helt anderledes. Brugen af ​​ikke-PQ SNARK'er i dag bør ikke kompromittere sikkerheden af ​​blockchains halvtreds år ude i fremtiden, selv om kvantecomputere kommer til den tid. 

Polynomiske forpligtelser

Alle SNARK'er gør brug af en kryptografisk primitiv kendt som en polynomisk forpligtelsesordning, og denne komponent er ofte en flaskehals i ydeevnen. (For detaljer, se min forrige indlæg.) Derudover bestemmes en SNARKs gennemsigtighed og plausible post-kvantesikkerhed udelukkende af den polynomielle forpligtelsesordning, den bruger. 

Et fremtrædende eksempel er såkaldte KZG polynomielle forpligtelser, som bruges af PlonK, Marlin, og mange andre. KZG-forpligtelser er hverken gennemsigtige eller post-kvantesikre. Andre tilsagnsordninger er gennemsigtige, men ikke postkvante, herunder Bulletproofs, hyraxog Dory. 

Atter andre ordninger er både gennemsigtige og plausibelt postkvante. Disse omfatter FRE, lys, Ligero++, Nedbremsningog Orion. Alle disse skemaer er baseret på fejlkorrigerende koder. Hashing er det eneste kryptografiske primitive, de bruger. De deler også følgende egenskab: verifikationsomkostninger (målt ved antallet af hash-evalueringer og feltoperationer) vokser lineært med antallet af bits af sikkerhed.

Groft sagt opnår en enkelt "iteration" af disse post-kvante polynomielle forpligtelser kun et lille antal (f.eks. 2-4) bits af sikkerhed. Så protokollen skal gentages mange gange for at "forstærke" sikkerhedsniveauet, hvor verifikationsomkostningerne vokser med hver gentagelse. For at kontrollere verifikationsomkostningerne i PQ-SNARK'er (og dermed gasomkostninger i blockchain-applikationer) tilskyndes protokoldesignere til at holde sikkerhedsniveauet lavt. 

Med sjældne undtagelser, opstår denne spænding mellem konkrete sikkerheds- og verifikationsomkostninger ikke i ikke-PQ SNARK'er (gennemsigtige og ikke-gennemsigtige ens). Ikke-PQ-SNARK'er bruger elliptiske kurvegrupper, hvor diskrete logaritmer formodes at være svære at beregne, og deres sikkerhedsniveauer bestemmes af den anvendte gruppe. Størrelsen af ​​den passende elliptiske kurvegruppe og dermed omkostningerne ved hver gruppeoperation vokser med det ønskede sikkerhedsniveau. Imidlertid nummer af gruppeelementer i et bevis er uafhængige af valget af gruppe. 

I PQ-SNARKs vokser ikke kun størrelsen af ​​hash-evalueringer lineært med det ønskede sikkerhedsniveau, det samme gør antallet af evalueringer inkluderet i beviset og udført af verifikatoren. 

Konkrete verifikatoromkostninger og sikkerhed i implementerede SNARK'er

De konkrete verifikatoromkostninger og sikkerhedsniveauer for installerede SNARK'er varierer betydeligt. Her er nogle illustrative eksempler:

Verifikator omkostninger 

My forrige indlæg nævnte to eksempler på konkrete verifikationsomkostninger: PlonK beviser koster under 300,000 gas at verificere på Ethereum, mens StarkWares beviser koster omkring 5 millioner gas. StarkWares beviser er gennemsigtige og plausibelt post-kvante, mens PlonK's ikke er det. Men som detaljeret næste, køres StarkWares beviser på et meget lavere sikkerhedsniveau end PlonK-beviser på Ethereum.

Konkret sikkerhed

Den eneste elliptiske kurve med Ethereum-prækompilere kaldes altbn128, så dette er kurven for alle ikke-PQ SNARK'er, der er installeret på Ethereum-brug, inklusive Aztecs og zkSync's. Denne kurve - og dermed også de installerede SNARK'er, der bruger den - blev oprindeligt antaget at tilbyde omkring 128 bits af sikkerhed. Men pga forbedrede angreb (hvis præcise køretid er vanskeligt at bestemme), er kurven nu bredt anset for at tilbyde 100 til 110 bits sikkerhed. 

Der er EIP'er under overvejelse at introducere prækompiler til forskellige kurver, der stadig menes at tilbyde tæt på 128 bits sikkerhed. Sådanne kurver er allerede brugt i SNARK'erne for ikke-Ethereum-projekter, herunder ZCash, Algorand, Dfinity, Filecoin og Aleo. 

I modsætning hertil er StarkWares PQ-SNARKs (i dets såkaldte SHARP-system, forkortelse for SHARed Prover) ifølge on-chain data konfigureret til at målrette 80 bits af sikkerhed. Dette sikkerhedsniveau gælder under visse formodninger om den statistiske soliditet af FRI (som jeg vil behandle senere i dette indlæg). 

Udtrykket "80 bits of security" er vagt i denne sammenhæng, så lad mig pakke det ud. Groft sagt betyder det, at en angriber kan frembringe et overbevisende bevis for en falsk udsagn ved at evaluere en hashfunktion 2⁸⁰ gange (nemlig KECCAK-256, hash-funktionen brugt af Ethereum). For at være mere præcis, en angriber, der er villig til at udføre 2^k hash-evalueringer kan give et overbevisende bevis med en sandsynlighed på ca. 2^k-80. For eksempel med 2⁷⁰ hash-evalueringer, kan man finde et SNARK "bevis" på en falsk udsagn med en sandsynlighed på omkring 2^-10 = 1 / 1024. 

Denne opfattelse er svagere end hvad udtrykket "80 bits af sikkerhed" betyder i andre sammenhænge. For eksempel ville en kollisionsbestandig hash-funktion (CRHF'er) konfigureret til 80 bits sikkerhed producere 160-bit output. Hvis hash-funktionen er veldesignet, vil den hurtigste kollisionsfindingsprocedure være Fødselsdagsangreb, en brute-force procedure, der kan finde en kollision med omkring 2^160/2 = 2⁸⁰ hash-evalueringer. Dog med 2^k hash-evalueringer, vil fødselsdagsangrebet finde en kollision med en sandsynlighed på kun 2^2-160. 

For eksempel 2⁷⁰ hash-evalueringer vil give en kollision med en sandsynlighed på 2^-20  ≈ 1/1,000,000. Dette er langt mindre end 1/1,000-sandsynligheden for, at en angriber forfalsker et PQ-SNARK-bevis konfigureret til 80 bits sikkerhed. 

Denne forskel kan drastisk ændre attraktiviteten ved at udføre et angreb. For at illustrere, forestil dig, at en angriber har et budget på $100K, som kan købe 2⁷⁰ hash-evalueringer. Og antag, at hvis angriberen lykkes, er udbetalingen $200 millioner. Den forventede værdi af angrebet mod en PQ-SNARK konfigureret til 80 bits sikkerhed er (1/1,000) * 200 millioner USD eller 200 USD – det dobbelte af prisen. Hvis successandsynligheden kun var 1/1,000,000, som med en CRHF, ville den forventede værdi af angrebet kun være $200. 

De to begreber "80 bits af sikkerhed" adskiller sig også dramatisk i deres robusthed over for uafhængige angreb. Antag for eksempel, at 1,000 uafhængige parter hver angriber PQ-SNARK ved at udføre 2⁷⁰ hash-evalueringer. Da hver lykkes med en sandsynlighed på omkring 1/1,000, er mindst én af dem ret sandsynligt, at de lykkes. Dette ville ikke være tilfældet, hvis hver enkelt lykkedes med en sandsynlighed på kun 1/1,000,000.

Veldesignede elliptiske kurvegrupper forventes at opføre sig på samme måde som CRHF'er, med fødselsdagslignende angreb som f.eks. Pollards rho-algoritme være den bedst kendte. Det betyder, at i en gruppe, der tilbyder 128 bits sikkerhed, 2^k gruppeoperationer bør give en løsning på en instans af det diskrete logaritmeproblem med en sandsynlighed på kun 2^2-256. For eksempel 2⁷⁰ gruppeoperationer ville finde en diskret logaritme med kun en astronomisk lille sandsynlighed på 2^-116. Desuden er hver gruppeoperation langsommere end en CRHF-evaluering. 

Hvor mange hash-evalueringer er mulige i dag?

I januar 2020 er omkostningerne ved at beregne kun 2⁶⁴ SHA-1-evalueringer ved hjælp af GPU'er var $45,000. Det koster 2⁷⁰ SHA-1-evalueringer på GPU'er til et par millioner dollars (måske lavere efter Ethereum-fusionen, da overgangen væk fra GPU-domineret proof of work mining sandsynligvis vil mindske efterspørgslen efter GPU-computere, hvilket reducerer omkostningerne). 

Med gyldighedsoprulninger, der allerede lagrer hundredvis af millioner af dollars i brugermidler, kan det give mange millioner dollars i profit at finde et overbevisende bevis for en falsk erklæring. Konfiguration af en PQ-SNARK til 80 bits sikkerhed under aggressive formodninger efterlader under 10 bits slingreplads mellem profitable angreb og den formodede sikkerhed i PQ-SNARK.

Som et andet datapunkt er Bitcoins netværkshashrate i øjeblikket omkring 2⁶⁴  hash-evalueringer per sekund, hvilket betyder, at bitcoin-minearbejdere som helhed udfører 2⁸⁰ SHA-256 evalueringer hver 18. time. Selvfølgelig skyldes dette iøjnefaldende tal den store investering i ASIC'er til bitcoin-minedrift. 

Antages seks bitcoin-blokke oprettet i timen, og givet den nuværende blokbelønning på 6.25 Bitcoin per blok, er disse 2⁸⁰ SHA-256-evalueringer koster formodentlig mindre end $22,000 * 18 * 6 * 6.25 ≈ $15 millioner. Ellers ville bitcoin-minedrift ikke være rentabel til nuværende priser. 

Foreslåede handlinger for et sundt økosystem

Hele pointen med at bruge SNARK'er i rollups er at opnå blockchain-skalerbarhed uden at brugerne behøver at stole blindt på rollup-tjenesten. Da rollup-tjenesten skrev den smarte kontrakt, der fungerer som SNARK-verifikator, skal offentligheden være i stand til at inspicere kontrakten og bekræfte, at den faktisk verificerer SNARK-beviser for de relevante udsagn. Offentlig kontrol af den smarte kontrakt kan også være nødvendig for at sikre, at rollup-tjenesten ikke er i stand til at censurere sine egne brugere. Foreslåede metoder til censur-modstand kræver rollup'ens smarte kontrakt for at give brugerne mulighed for at tvinge tilbagetrækningen af ​​deres midler, hvis rollup-tjenesten ikke behandler deres transaktioner. 

I betragtning af disse protokollers sofistikerede karakter lægger dette paradigme af offentlig kontrol en vis byrde på eksperter til åbent og ærligt at diskutere sikkerheden af ​​de udsendte kontrakter. 

Men med PQ-SNARK'er kan det være vanskeligt selv for eksperter at fastslå den installerede protokols sikkerhedsniveau af samme grund, som sikkerhed og verifikatorydelse er i spænding for disse SNARK'er: sikkerhedsniveauet (og verifikatoromkostningerne) afhænger af interne parametre i SNARK. Og i det mindste for StarkWare's smarte kontrakter, disse parametre, called logBlowupFactor, proofOfWorkBits og n_Queries er ikke direkte specificeret i den smarte kontrakts kode, men videregivet til den smarte kontrakt som offentlige data. Så vidt jeg ved, er den nemmeste måde at identificere disse parametre fra on-chain information via en fire-trins proces: 

1. se passende smart kontrakt på en blokudforsker såsom Etherscan, 
2. klik på en passende "bekræft bevis" transaktion, 
3. afkode transaktionens inputdata, og
4. finde ud af hvordan fortolke de afkodede inputdata for at lære de vigtigste SNARK-parametre, der tilsammen bestemmer sikkerhedsniveauet. 

Dette sidste trin kræver at finde den passende Solidity-kode, der implementerer transaktionen, hvilket i sig selv kan være en forvirrende opgave. (Da jeg forberedte mig undersøgelse samtaler ved oprulninger denne sommer var Etherscan i stand til at afkode de relevante inputdata til SHARP-verifikatortransaktionerne som i trin 2 ovenfor. Men det ser ikke ud til at virke længere.)

Forslag 1: Gennemgang 

Med dette i tankerne er mit første forslag til web3-fællesskabet at gøre det langt nemmere at granske sikkerhedsniveauet for udrullede post-kvante SNARK'er. Dette indebærer sandsynligvis bedre værktøj til at forstå on-chain data og øget gennemsigtighed af projekterne selv i at gøre disse parametre kendt. 

Forslag 2: Stærkere normer

80 bits sikkerhed er for lavt, især den svage version, hvor 2⁷⁰ hash-evalueringer er nok til at angribe med succes med en sandsynlighed på omkring 1/1000 - endnu mere i betragtning af den lange historie med overraskende angreb på kryptografiske primitiver. Den ene, nævnt ovenfor, er bedre angreb på parringsvenlige elliptiske kurver såsom altbn128. Et mere berømt eksempel er SHA-1, som blev standardiseret til 80 bits sikkerhed, men til sidst viste sig kun at opnå omkring 60 bit. Med denne historie i tankerne, bør PQ-SNARK-designere give sig selv mere end 10 bits slingrende plads, når de konfigurerer sikkerhedsniveauet, især hvis sikkerhedsanalysen involverer stærke formodninger om den statistiske sikkerhed af relativt nye protokoller såsom FRI.

Selv for PQ-SNARK'er kan passende sikkerhedsniveauer altid opnås, blot ved at øge verifikationsomkostningerne. For eksempel ville en forøgelse af sikkerheden for SHARP's verifikator fra 80 til 128 bit (under formodninger om FRI's statistiske soliditet) øge gasomkostningerne med ca. en faktor to, fra lidt over 5 millioner til lidt over 10 millioner. Uden formodninger om FRI ville gasomkostningerne stige med endnu en faktor to til over 20 mio. 

Mit næste forslag er så, at web3-fællesskabet bør udvikle stærkere normer omkring passende sikkerhedsniveauer for installerede SNARK'er. Min personlige anbefaling vil være mindst 100 bit, og mindst 128, hvis SNARK's sikkerhed er baseret på ikke-standardiserede antagelser. Jeg er ikke den første til stille et sådant forslag.

Her er jeg villig til at kategorisere ubetinget sikkerhed i en "standardantagelse". tilfældig orakelmodel, hvis det tilfældige orakel i den installerede SNARK er instantieret med en standard hash-funktion såsom KECCAK-256. Den tilfældige orakelmodel er en idealiseret indstilling, der er beregnet til at fange adfærden af ​​veldesignede kryptografiske hash-funktioner. Det bruges ofte til at analysere sikkerheden af ​​PQ-SNARKs. 

Et eksempel på ikke-standardmæssige antagelser er formodninger (beskrevet nedenfor) vedrørende den kvantitative forsvarlighed af en protokol såsom FRI, enten i en interaktiv indstilling eller som en ikke-interaktiv protokol i den tilfældige orakelmodel.

SNARK-designere fornyer sig på mange spændende måder, hvoraf nogle kan skubbe rammerne sikkerhedsmæssigt – for eksempel ved at bruge SNARK-venlige hash-funktioner, der ikke har været udsat for så meget kryptoanalyse som mere standard-hash-funktioner. Jeg opfordrer ikke til at stoppe sådanne bestræbelser – langt fra. Men disse primitiver bør instansieres på sikkerhedsniveauer, der overstiger kendte, gennemførlige angreb med langt over 10 bit. 

Rollups, der bruger SNARK'er, beskrives almindeligvis som at arve sikkerheden i deres L1. Men dette er en vanskelig sag at lave, hvis de er konfigureret til meget lavere sikkerhedsniveauer end nogen kryptografiske primitiver, der bruges af L1. Efterhånden som SNARK'er ser stigende adoption, bør vi sørge for, at vi implementerer dem på måder, der er i overensstemmelse med, hvordan vi taler om dem. Så længe SNARK'er analyseres omhyggeligt, konfigureres korrekt og implementeres korrekt, er de lige så sikre som enhver kryptografisk primitiv i brug i dag. 

En sidebemærkning: Dykke endnu dybere ned i PQ-SNARK-sikkerhed

De 80 bits af sikkerhed i StarkWare's PQ-SNARK'er er opgjort som følger. Disse PQ-SNARK'er gør brug af en polynomisk forpligtelsesordning kaldet FRE, og StarkWares SHARP-verifikator kører FRI ved 48 bits sikkerhed under en formodning. Groft sagt er formodningen, at et simpelt angreb på FRI's forsvarlighed er optimalt. I dette angreb genererer en snyd-beviser med en lille indsats et "FRI-bevis", der består verifikatorens tilfældigt valgte checks med sandsynlighed 2^-48. 

StarkWare kombinerer FRI med en teknik kaldet "slibning". Dette kræver, at den ærlige beviser fremlægger et 32-bit bevis på arbejdet, før der produceres et FRI-bevis. Fordelen ved slibning er, at det drastisk øger det arbejde, der kræves for en snyd-beviser til at udføre det simple angreb på FRI nævnt ovenfor, til ca.³² hash-evalueringer. 

Siden (i forventning) 2⁴⁸ forsøg på det simple angreb er nødvendige, før et af dem lykkes, den samlede mængde arbejde, som snyderen skal udføre for at lave et FRI-bevis, er ca. 2⁴⁸ * 2³² = 2⁸⁰ hash-evalueringer.

Lad os endelig pakke ud, hvordan de 48 bits af sikkerhed for FRI opstår. FRI-verifikatoren foretager "forespørgsler" til det forpligtede polynomium. FRI-verifikationsomkostninger vokser lineært med antallet af forespørgsler. For eksempel er 36 FRI-verifikatorforespørgsler omtrent 4 gange så dyre som 9 forespørgsler. Men flere forespørgsler betyder mere sikkerhed. Antallet af "sikkerhedsbits pr. forespørgsel" afhænger af en anden parameter i FRI, kaldet kodehastigheden. 

Specifikt bruger FRI noget, der kaldes Reed-Solomon rate of rate rHvor r er altid et tal strengt taget mellem 0 og 1. FRI-beviserens omkostninger er omvendt proportional med r, så en hastighed på 1/16 fører til en prøve, der er cirka fire gange langsommere og mere pladskrævende end en hastighed på ¼. 

SHARP-verifikatoren har kørt FRI med en kodehastighed på 1/16 og med 12 verifikatorforespørgsler.

StarkWare formoder, at hver FRI-verifikatorforespørgsel tilføjer log₂(1 /r) stykker sikkerhed. Under denne formodning giver 12 verifikatorforespørgsler 12 * log₂(16) = 48 bits sikkerhed.

Nuværende analyser fastslår dog kun, at hver verifikatorforespørgsel tilføjer lidt mindre end log₂(1/r^1/2) stykker sikkerhed. Så 12 FRI-verifikatorforespørgsler giver kun mindre end 12 * log₂(4) = 24 bits "bevisbar" sikkerhed. 

Et forslag til at mindske spændingen mellem sikkerhed og ydeevne

Praktiske PQ-SNARK'er har verifikatoromkostninger, der vokser lineært med det ønskede antal bits af sikkerhed. En lovende teknik til at afbøde denne spænding er SNARK-sammensætning - som jeg beskrev i mit tidligere indlæg som et middel til at løse spændingen mellem prover- og verifikatoromkostninger, men det kan også adressere sikkerhed. 

To eksempler 

Polygon Hermez er komponere PQ-SNARKs med PlonK. Ideen er, at beviseren først genererer et PQ-SNARK-bevis π. Hvis PQ-SNARK er konfigureret til at have en hurtig test og et passende sikkerhedsniveau, vil π være stor. Så beviseren sender ikke π til verifikatoren. I stedet bruger den PlonK til at bevise, at den kender π. 

Dette betyder at anvende PlonK til et kredsløb, der tager π som input og kontrollerer, at PQ-SNARK-verifikatoren vil acceptere π. Da PQ-SNARK har polylogaritmiske verifikationsomkostninger, anvendes PlonK på et lille kredsløb, og derfor er PlonK-beviseren hurtig. Da PlonK-beviser er små og billige at verificere, er verifikationsomkostningerne lave. 

Desværre ødelægger brugen af ​​PlonK gennemsigtighed og post-kvantesikkerhed. Man kan i stedet overveje at bruge selve PQ-SNARK i stedet for PlonK for at bevise viden om π (faktisk er PQ-SNARK, der bruges af Polygon, selvkomponeret på denne måde). 

I denne anden anvendelse af PQ-SNARK, for at bevise viden om π, kan systemet konfigureres til at opnå tilstrækkelig sikkerhed med rimeligt store beviser, for eksempel ved at vælge en meget lille kodehastighed til brug i FRI. Nøglepunktet er, at selvom denne lille kodehastighed er dårlig for prøvetid, anvendes den anden anvendelse af PQ-SNARK kun på et lille kredsløb, så den samlede prøvetid bør stadig være lille.

Vores teoretiske forståelse af sikkerheden ved sammensatte SNARK'er lader meget tilbage at ønske. Der er dog ikke kendte angreb på dem, der er hurtigere end at angribe en af ​​de konstituerende SNARK'er individuelt. For eksempel, hvis vi komponerer en PQ-SNARK med PlonK, kender vi ikke et bedre angreb end enten at angribe PQ-SNARK (dvs. finde et PQ-SNARK bevis π for en falsk udsagn), eller at angribe PlonK (dvs. find et PlonK-bevis for den falske udsagn "Jeg kender et PQ-SNARK-bevis π, som verifikatoren ville have accepteret.")

At komponere SNARK'er på denne måde er en stadig mere populær måde at forbedre ydeevnen på. Jeg håber, at protokoldesignere også bruger det til at forbedre sikkerheden.

***

Justin Thaler er lektor ved Georgetown University. Før han kom til Georgetown, tilbragte han to år som forskningsforsker ved Yahoo Labs i New York, før han var forskningsstipendiat ved Simons Institut for Theory of Computing på UC Berkeley. 

Redaktør: Tim Sullivan @tim_org

***

De synspunkter, der er udtrykt her, er dem fra det enkelte AH Capital Management, LLC ("a16z") personale, der er citeret, og er ikke synspunkter fra a16z eller dets tilknyttede selskaber. Visse oplysninger indeholdt heri er indhentet fra tredjepartskilder, herunder fra porteføljeselskaber af fonde forvaltet af a16z. Selvom det er taget fra kilder, der menes at være pålidelige, har a16z ikke uafhængigt verificeret sådanne oplysninger og fremsætter ingen erklæringer om informationernes vedvarende nøjagtighed eller deres passende for en given situation. Derudover kan dette indhold omfatte tredjepartsreklamer; a16z har ikke gennemgået sådanne annoncer og støtter ikke noget reklameindhold indeholdt deri.

Dette indhold er kun givet til informationsformål og bør ikke påberåbes som juridisk, forretningsmæssig, investerings- eller skatterådgivning. Du bør rådføre dig med dine egne rådgivere om disse spørgsmål. Henvisninger til værdipapirer eller digitale aktiver er kun til illustrationsformål og udgør ikke en investeringsanbefaling eller tilbud om at levere investeringsrådgivningstjenester. Ydermere er dette indhold ikke rettet mod eller beregnet til brug af nogen investorer eller potentielle investorer og kan under ingen omstændigheder stoles på, når der træffes en beslutning om at investere i en fond, der administreres af a16z. (Et tilbud om at investere i en a16z-fond vil kun blive givet af private placement-memorandummet, tegningsaftalen og anden relevant dokumentation for en sådan fond og bør læses i deres helhed.) Eventuelle investeringer eller porteføljeselskaber nævnt, refereret til eller beskrevne er ikke repræsentative for alle investeringer i køretøjer, der administreres af a16z, og der kan ikke gives sikkerhed for, at investeringerne vil være rentable, eller at andre investeringer foretaget i fremtiden vil have lignende karakteristika eller resultater. En liste over investeringer foretaget af fonde forvaltet af Andreessen Horowitz (undtagen investeringer, hvortil udstederen ikke har givet tilladelse til, at a16z offentliggør såvel som uanmeldte investeringer i offentligt handlede digitale aktiver) er tilgængelig på https://a16z.com/investments /.

Diagrammer og grafer, der er angivet i, er udelukkende til informationsformål og bør ikke stoles på, når der træffes nogen investeringsbeslutning. Tidligere resultater er ikke vejledende for fremtidige resultater. Indholdet taler kun fra den angivne dato. Alle fremskrivninger, estimater, prognoser, mål, udsigter og/eller meninger udtrykt i disse materialer kan ændres uden varsel og kan afvige fra eller være i modstrid med andres meninger. Se venligst https://a16z.com/disclosures for yderligere vigtige oplysninger.