SNARK Säkerhet och prestanda

A SNARK (Succinct Non-interactive Argument of Knowledge) är ett kryptografiskt verktyg som öppnar för spännande nya möjligheter inom systemdesign, särskilt i decentraliserade miljöer. SNARKs tillåter att data behandlas av opålitliga enheter, som sedan kan bevisa att uppgifterna är giltiga och har behandlats korrekt. Ett naivt sätt att bevisa detta skulle vara att publicera uppgifterna, så att alla som vill kan kontrollera dess giltighet och bearbeta dem direkt. 

En SNARK uppnår samma effekt, men med bättre kostnads till validerarna. Till exempel, i en lager-två (L2) verifierbar sammanställning, bearbetar en sammanställningstjänst blockkedjetransaktioner. Tjänsten bokför med jämna mellanrum sina användares kontosaldon till lager-ett-blockkedjan. Varje gång den postar en uppdatering av saldonen, lägger den till ett SNARK-bevis på att den känner till en sekvens av giltiga transaktioner som ändrade de gamla kontosaldona till de uppdaterade. På detta sätt behöver blockchain-validerare inte göra det hårda arbetet med att kontrollera transaktionens giltighet (t.ex. kontrollera en digital signatur för varje transaktion) och inte heller explicit bearbeta transaktionerna för att beräkna de uppdaterade saldona.  

My tidigare inlägg fokuserat på prestanda hos SNARK-provare – den primära bestämningsfaktorn för SNARKs tillämplighet. Även om det kan vara beräkningskrävande att köra en SNARK-provare, i den mån det kan vara omöjligt att generera ett bevis för storskaliga beräkningar, är SNARK-verifiering vanligtvis mycket billigare än att direkt kontrollera och bearbeta data. SNARK-verifieringskostnaderna varierar dock avsevärt. Det här inlägget packar upp dessa kostnader och jämför säkerhetsegenskaperna för olika SNARKs. 

Speciellt förklarar jag att det i praktiska SNARKs med rimlig postkvantsäkerhet (PQ-SNARKs) finns en betydande spänning mellan säkerhet och verifieringskostnader. Dessutom, i vissa fall, håller denna spänning för närvarande på att lösas till förmån för verifieringskostnader framför säkerhet.

För att SNARK:er ska förverkliga sin potential måste utplacerade system vara säkra och användare måste vara säkra på sin säkerhet. Jag avslutar inlägget med att föreslå enkla åtgärder som web3-communityt kan vidta för att säkerställa att dessa egenskaper håller på lång sikt. 

Kvantitativa säkerhetsåtgärder 

En SNARK är säker om det är beräkningsmässigt omöjligt att producera ett övertygande bevis för ett falskt påstående. Till exempel, i samband med L2-samlingar, skulle en angripare som vill stjäla mina pengar vilja bevisa ett falskt påstående i formen: "Jag vet en digitalt signerad transaktion som överför alla Justins tillgångar till mitt eget konto." 

Säkerhetsnivån för en SNARK mäts genom hur mycket arbete som måste göras för att hitta ett övertygande bevis på ett falskt påstående. I likhet med andra kryptografiska primitiver som digitala signaturer, kallas logaritmen för denna mängd arbete som "säkerhetsbitarna". Till exempel, 30 bitar av säkerhet innebär att 2³⁰ ≈ 1 miljard "steg av arbete" krävs för att attackera SNARK. Detta är till sin natur ett ungefärligt mått på verklig säkerhet eftersom föreställningen om ett steg i arbetet kan variera, och praktiska överväganden som minneskrav eller möjligheter till parallellitet beaktas inte.

Och kvalitativa sådana

Bitar av säkerhet är en kvantitativ mått på säkerheten för en SNARK. SNARKs skiljer sig också i sina kvalitativ säkerhetsegenskaper. 

Till exempel kräver vissa SNARKs en pålitlig installationsceremoni för att generera en strukturerad provningsnyckel. SNARKs som inte alls kräver en pålitlig installation kallas transparent. 

För att en icke-transparent SNARK ska vara säker måste vanligtvis minst en deltagare i ceremonin ha uppträtt ärligt, vilket innebär att de producerade och sedan kasserade en "fälllucka" som, om den kombineras med alla andra deltagares luckor, skulle göra det enkelt för att hitta övertygande SNARK "bevis" på alla falska påståenden. Pålitliga inställningar är Där vi får lov att vara utan att konstant prestera, köra med hundratals eller tusentals deltagare för att göra detta antagande så mildt som möjligt. 

SNARK skiljer sig också i sin känslighet för kvantattacker. Specifikt många SNARKs (t.ex. Groth16, PlonK, Marlin, Skyddsskydd, Nytt) lita på antagandet att diskreta logaritmer är svåra att beräkna (och i vissa fall även ytterligare antaganden). Att beräkna diskreta logaritmer är något som kvantdatorer skulle kunna göra effektivt. Därför är dessa SNARK inte post-kvantsäkra (icke-PQ). 

Medan brådskande ansträngningar pågår för att byta till postkvant krypteringsscheman, detta drivs främst av behovet av att hålla krypterade meddelanden hemliga många decennier in i framtiden. En motståndare som lagrar ett avlyssnat meddelande idag och väntar på att en kvantdator ska anlända om, säg, femtio år, kan använda datorn för att dekryptera det femtio år gamla meddelandet. Situationen med SNARKs är helt annorlunda. Användningen av icke-PQ SNARKs idag bör inte äventyra säkerheten för blockkedjor femtio år i framtiden, även om kvantdatorer kommer fram vid den tiden. 

Polynomåtaganden

Alla SNARKs använder sig av en kryptografisk primitiv känd som en polynomiellt åtagandesystem, och den här komponenten är ofta en prestandaflaskhals. (För detaljer, se min tidigare inlägg.) Dessutom bestäms en SNARK:s transparens och rimliga post-kvantsäkerhet enbart av det polynomiska åtagandeschema som det använder. 

Ett framträdande exempel är sk KZG polynomåtaganden, som används av PlonK, Marlin, och många andra. KZG-åtaganden är varken transparenta eller postkvantsäkra. Andra åtagandesystem är transparenta men inte postkvantum, inklusive Skyddsskydd, hyraxoch dory. 

Ytterligare andra system är både transparenta och troligtvis post-kvantum. Dessa inkluderar Fredag, lätt, Ligero++, Bromsningoch Orion. Alla dessa scheman är baserade på felkorrigerande koder. Hashing är den enda kryptografiska primitiva de använder. De delar också följande egenskap: verifieringskostnaderna (mätt med antalet hash-utvärderingar och fältoperationer) växer linjärt med antalet säkerhetsbitar.

Grovt sett uppnår en enda "iteration" av dessa postkvantpolynomåtaganden endast ett litet antal (säg 2-4) säkerhetsbitar. Så protokollet måste upprepas många gånger för att "förstärka" säkerhetsnivån, med verifieringskostnaderna som ökar för varje upprepning. För att kontrollera verifieringskostnaderna i PQ-SNARKs (och därmed gaskostnaderna i blockchain-applikationer) uppmanas protokolldesigners att hålla säkerhetsnivån låg. 

Med sällsynt undantag, denna spänning mellan konkreta säkerhet och verifieringskostnader uppstår inte i icke-PQ SNARKs (transparenta och icke-transparenta likadana). Icke-PQ-SNARKs använder elliptiska kurvgrupper där diskreta logaritmer antas vara svåra att beräkna, och deras säkerhetsnivåer bestäms av den grupp som används. Storleken på den lämpliga elliptiska kurvgruppen, och därmed kostnaden för varje gruppoperation, växer med önskad säkerhetsnivå. Men den antal av gruppelement i ett bevis är oberoende av valet av grupp. 

I PQ-SNARKs växer inte bara storleken på hash-utvärderingar linjärt med den önskade säkerhetsnivån, utan även antalet utvärderingar som ingår i beviset och utförs av verifieraren. 

Konkreta verifieringskostnader och säkerhet i utplacerade SNARKs

De konkreta verifieringskostnaderna och säkerhetsnivåerna för utplacerade SNARK:er varierar avsevärt. Här är några illustrativa exempel:

Verifieringskostnader 

My tidigare inlägg nämnde två exempel på konkreta verifieringskostnader: PlonK bevis kostar under 300,000 gas att verifiera på Ethereum, medan StarkWares prover kostade cirka 5 miljoner gas. StarkWares bevis är transparenta och troligtvis post-quantum medan PlonKs inte är det. Men som beskrivs härnäst körs StarkWares prov på en mycket lägre säkerhetsnivå än PlonK-prov på Ethereum.

Betongsäkerhet

Den enda elliptiska kurvan med Ethereum-prekompilerar kallas altbn128, så detta är kurvan som alla icke-PQ SNARK:er som används på Ethereum-användning, inklusive Aztecs och zkSyncs. Den här kurvan – och därmed också de utplacerade SNARKs som använder den – troddes ursprungligen erbjuda ungefär 128 bitar av säkerhet. Men pga förbättrade attacker (vars exakta körtid är svårt att bestämma), anses kurvan nu allmänt erbjuda 100 till 110 bitar av säkerhet. 

Det finns EIP under övervägande att införa förkompilerar för olika kurvor som fortfarande tros erbjuda nära 128 bitars säkerhet. Sådana kurvor är redan använd i SNARKs för icke-Ethereum-projekt inklusive ZCash, Algorand, Dfinity, Filecoin och Aleo. 

Däremot, enligt on-chain-data, har StarkWares PQ-SNARKs (i dess så kallade SHARP-system, kort för SHARed Prover) konfigurerats för att rikta in sig på 80 bitars säkerhet. Denna säkerhetsnivå gäller för vissa gissningar om den statistiska sundheten hos FRI (som jag kommer att ta upp senare i det här inlägget). 

Termen "80 bitar av säkerhet" är vag i detta sammanhang, så låt mig packa upp den. Grovt sett betyder det att en angripare kan producera ett övertygande bevis på ett falskt påstående genom att utvärdera en hashfunktion 2⁸⁰ gånger (nämligen KECCAK-256, hashfunktionen som används av Ethereum). För att vara mer exakt, en angripare som är villig att utföra 2^k hash-utvärderingar kan ge ett övertygande bevis med en sannolikhet på ungefär 2^k-80. Till exempel med 2⁷⁰ hash-utvärderingar, kan man hitta ett SNARK "bevis" på ett falskt påstående med en sannolikhet på cirka 2^-10 = 1/1024. 

Denna uppfattning är svagare än vad termen "80 bitar av säkerhet" betyder i andra sammanhang. Till exempel skulle en kollisionssäker hashfunktion (CRHF) konfigurerad till 80 bitars säkerhet producera 160-bitars utdata. Om hash-funktionen är väldesignad kommer den snabbaste kollisionssökningsproceduren att vara Födelsedagattack, en brute-force procedur som kan hitta en kollision med cirka 2^160/2 = 2⁸⁰ hash-utvärderingar. Dock med 2^k hash-utvärderingar, kommer födelsedagsattacken att hitta en kollision med en sannolikhet på endast 2^2k-160. 

Till exempel 2⁷⁰ hash-utvärderingar kommer att ge en kollision med en sannolikhet på 2^-20  ≈ 1/1,000,000 1 1,000. Detta är mycket mindre än 80/XNUMX XNUMX sannolikheten för att en angripare förfalskar ett PQ-SNARK-bevis konfigurerat till XNUMX bitars säkerhet. 

Denna skillnad kan drastiskt förändra attraktiviteten för att utföra en attack. För att illustrera, föreställ dig att en angripare har en budget på 100 2 $, som kan köpa XNUMX⁷⁰ hash-utvärderingar. Och anta att om angriparen skulle lyckas är utdelningen $200 miljoner. Det förväntade värdet av attacken mot en PQ-SNARK konfigurerad till 80 bitars säkerhet är (1/1,000 200) * 200 miljoner USD, eller 1 1,000,000 USD – dubbelt så mycket som kostnaden. Om sannolikheten för framgång endast var 200/XNUMX XNUMX XNUMX, som med en CRHF, skulle det förväntade värdet av attacken vara bara $XNUMX. 

De två begreppen "80 bitar av säkerhet" skiljer sig också dramatiskt i sin robusthet för oberoende attacker. Anta till exempel att 1,000 2 oberoende parter var och en attackerar PQ-SNARK genom att utföra XNUMX⁷⁰ hash-utvärderingar. Eftersom var och en lyckas med en sannolikhet på cirka 1/1,000 1, är ​​det ganska troligt att minst en av dem lyckas. Detta skulle inte vara fallet om var och en lyckades med en sannolikhet på endast 1,000,000/XNUMX XNUMX XNUMX.

Väldesignade elliptiska kurvgrupper förväntas bete sig på samma sätt som CRHF, med födelsedagsliknande attacker som t.ex. Pollards rho-algoritm vara den mest kända. Detta innebär att i en grupp som erbjuder 128 bitars säkerhet, 2^k gruppoperationer bör ge en lösning på en instans av det diskreta logaritmproblemet med en sannolikhet på endast 2^2k-256. Till exempel 2⁷⁰ gruppoperationer skulle hitta en diskret logaritm med endast en astronomiskt liten sannolikhet på 2^-116. Dessutom är varje gruppoperation långsammare än en CRHF-utvärdering. 

Hur många hash-utvärderingar är möjliga idag?

I januari 2020 är kostnaden för beräkning bara drygt 2⁶⁴ SHA-1-utvärderingar med GPU:er var $45,000. Detta kostar 2⁷⁰ SHA-1-utvärderingar på GPU:er till några miljoner dollar (kanske lägre efter Ethereums sammanslagning, eftersom övergången från GPU-dominerad proof of work mining sannolikt kommer att minska efterfrågan på GPU-datorer, vilket sänker dess kostnad). 

Med giltighetssamlar som redan lagrar hundratals miljoner dollar i användarmedel, kan det ge många miljoner dollar i vinst att hitta ett övertygande bevis på ett falskt påstående. Att konfigurera en PQ-SNARK till 80 bitars säkerhet under aggressiva gissningar lämnar under 10 bitars rörelseutrymme mellan lönsamma attacker och den förmodade säkerheten hos PQ-SNARK.

Som en annan datapunkt är Bitcoins nätverkshashhastighet för närvarande cirka 2⁶⁴  hash-utvärderingar per sekund, vilket innebär att bitcoin-gruvarbetare som helhet utför 2⁸⁰ SHA-256-utvärderingar var 18:e timme. Naturligtvis beror detta iögonfallande siffra på den stora investeringen i ASIC:er för bitcoin-gruvdrift. 

Förutsatt sex bitcoin-block skapas per timme, och med tanke på den nuvarande blockbelöningen på 6.25 Bitcoin per block, dessa 2⁸⁰ SHA-256-utvärderingar kostar förmodligen mindre än 22,000 18 USD * 6 * 6.25 * 15 ≈ XNUMX miljoner USD. Annars skulle bitcoin-brytning inte vara lönsamt till nuvarande priser. 

Föreslagna åtgärder för ett hälsosamt ekosystem

Hela poängen med att använda SNARKs i rollups är att uppnå blockkedjeskalbarhet utan att användarna behöver lita blint på rolluptjänsten. Eftersom rollup-tjänsten skrev det smarta kontraktet som fungerar som SNARK-verifieraren måste allmänheten kunna inspektera kontraktet och bekräfta att det verkligen verifierar SNARK-bevis för lämpliga påståenden. Offentlig granskning av det smarta kontraktet kan också vara nödvändigt för att säkerställa att rolluptjänsten inte kan censurera sina egna användare. Föreslagna metoder för censurmotstånd kräver sammanställningens smarta kontrakt för att tillåta användare att tvinga ut sina pengar om sammanställningstjänsten misslyckas med att behandla deras transaktioner. 

Med tanke på dessa protokolls sofistikerade karaktär lägger detta paradigm av offentlig granskning en viss börda på experter att öppet och uppriktigt diskutera säkerheten för de utplacerade kontrakten. 

Men med PQ-SNARKs kan det vara svårt även för experter att fastställa det utplacerade protokollets säkerhetsnivå av samma anledning som säkerhet och verifieringsprestanda är i spänning för dessa SNARKs: säkerhetsnivån (och verifieringskostnaderna) beror på interna parametrar för SNARK. Och åtminstone för StarkWares smarta kontrakt, dessa parametrar, called logBlowupFactor, proofOfWorkBits och n_Queries specificeras inte direkt i det smarta kontraktets kod utan skickas snarare till det smarta kontraktet som offentlig data. Så vitt jag vet är det enklaste sättet att identifiera dessa parametrar från information i kedjan via en process i fyra steg: 

1. visa lämpligt smart kontrakt på en blockutforskare som Etherscan, 
2. klicka på en lämplig "verifiera bevis" transaktion, 
3. avkoda transaktionens indata, och
4. ta reda på hur tolka de avkodade indata för att lära sig de viktigaste SNARK-parametrarna som tillsammans bestämmer säkerhetsnivån. 

Detta sista steg kräver att man hittar den lämpliga Solidity-koden som implementerar transaktionen, vilket i sig kan vara en förvirrande uppgift. (När jag förberedde mig undersökning samtal vid sammanslagningar i somras kunde Etherscan avkoda relevant indata till SHARP-verifierartransaktionerna enligt steg 2 ovan. Men det verkar inte längre fungera.)

Förslag 1: Granskning 

Med detta i åtanke är mitt första förslag till web3-communityt att göra det mycket lättare att granska säkerhetsnivån för utplacerade post-quantum SNARKs. Detta innebär sannolikt bättre verktyg för att förstå data i kedjan och ökad transparens från projekten själva när det gäller att göra dessa parametrar kända. 

Förslag 2: Starkare normer

80 bitars säkerhet är för lågt, speciellt den svaga versionen där 2⁷⁰ hash-utvärderingar räcker för att framgångsrikt attackera med en sannolikhet på cirka 1/1000 – ännu mer med tanke på den långa historien av överraskande attacker på kryptografiska primitiver. En, som nämns ovan, är bättre attacker på parningsvänliga elliptiska kurvor som altbn128. Ett mer känt exempel är SHA-1, som standardiserades till 80 bitars säkerhet men som så småningom visade sig uppnå endast cirka 60 bitar. Med denna historia i åtanke bör PQ-SNARK-designers lämna mer än 10 bitars rörelseutrymme när de konfigurerar säkerhetsnivån, särskilt om säkerhetsanalysen involverar starka gissningar om den statistiska säkerheten för relativt nya protokoll som FRI.

Även för PQ-SNARKs kan lämpliga säkerhetsnivåer alltid uppnås, helt enkelt genom att öka verifieringskostnaderna. Att till exempel öka säkerheten för SHARPs verifierare från 80 till 128 bitar (under gissningar om FRI:s statistiska sundhet) skulle öka gaskostnaderna med ungefär en faktor två, från lite över 5 miljoner till lite över 10 miljoner. Utan gissningar om FRI skulle gaskostnaderna öka med ytterligare en faktor två, till över 20 miljoner. 

Mitt nästa förslag är alltså att web3-communityt bör utveckla starkare normer kring lämpliga säkerhetsnivåer för utplacerade SNARKs. Min personliga rekommendation skulle vara minst 100 bitar, och minst 128 om SNARK:s säkerhet är baserad på icke-standardiserade antaganden. Jag är inte den första som gör det lägga fram ett sådant förslag.

Här är jag villig att kategorisera som ett "standardantagande" ovillkorlig säkerhet i slumpmässig orakelmodell, om det slumpmässiga oraklet i den utplacerade SNARK instansieras med en standardhashfunktion som KECCAK-256. Den slumpmässiga orakelmodellen är en idealiserad inställning som är tänkt att fånga beteendet hos väldesignade kryptografiska hashfunktioner. Det används ofta för att analysera säkerheten för PQ-SNARKs. 

Ett exempel på icke-standardiserade antaganden är gissningar (beskrivs nedan) angående den kvantitativa sundheten hos ett protokoll som FRI, antingen i en interaktiv miljö eller som ett icke-interaktivt protokoll i den slumpmässiga orakelmodellen.

SNARK-designers förnyar sig på många spännande sätt, varav några kan skjuta på gränsen vad gäller säkerhet – till exempel genom att använda SNARK-vänliga hashfunktioner som inte har utsatts för lika mycket kryptoanalys som fler vanliga hashfunktioner. Jag kräver inte ett slut på sådana ansträngningar – långt ifrån. Men dessa primitiver bör instansieras på säkerhetsnivåer som överstiger kända, genomförbara attacker med långt över 10 bitar. 

Samlar som använder SNARK beskrivs vanligtvis som att de ärver säkerheten för deras L1. Men detta är ett svårt fall att göra om de är konfigurerade på mycket lägre säkerhetsnivåer än alla kryptografiska primitiver som används av L1. När SNARKs ser en ökande adoption bör vi se till att vi distribuerar dem på ett sätt som överensstämmer med hur vi pratar om dem. Så länge SNARKs analyseras noggrant, konfigureras på lämpligt sätt och implementeras korrekt, är de lika säkra som alla kryptografiska primitiv som används idag. 

En sida: Dyka ännu djupare in i PQ-SNARK säkerhet

De 80 bitarna av säkerhet i StarkWares PQ-SNARKs redovisas enligt följande. Dessa PQ-SNARKs använder sig av ett polynomiellt åtagandeschema som kallas Fredag, och StarkWares SHARP-verifierare kör FRI med 48 bitars säkerhet under en gissning. Grovt sett är gissningen att en enkel attack mot FRI:s sundhet är optimal. I denna attack genererar en fuskbevisare, med en liten ansträngning, ett "FRI-bevis" som klarar verifierarens slumpmässigt valda kontroller med sannolikhet 2^-48. 

StarkWare kombinerar FRI med en teknik som kallas "slipning". Detta kräver att den ärliga bevisaren producerar ett 32-bitars bevis på arbete innan han producerar ett FRI-bevis. Fördelen med slipning är att det drastiskt ökar det arbete som krävs för en fuskbevisare att utföra den enkla attacken mot FRI som nämnts ovan, till cirka 2³² hash-utvärderingar. 

Sedan (i väntan) 2⁴⁸ försök till den enkla attacken är nödvändiga innan en av dem lyckas, den totala mängden arbete som fuskbevisaren måste göra för att förfalska ett FRI-bevis är ungefär 2⁴⁸ * 2³² = 2⁸⁰ hash-utvärderingar.

Slutligen, låt oss packa upp hur de 48 bitarna av säkerhet för FRI uppstår. FRI-verifieraren gör "frågor" till det engagerade polynomet. FRI-verifieringskostnaderna växer linjärt med antalet förfrågningar. Till exempel är 36 FRI-verifieringsfrågor ungefär 4 gånger så dyra som 9 frågor. Men fler frågor betyder mer säkerhet. Antalet "säkerhetsbitar per fråga" beror på en annan parameter i FRI, som kallas kodhastigheten. 

Specifikt använder FRI något som kallas Reed-Solomon-koden rDär r är alltid ett tal strikt mellan 0 och 1. FRI-provarens kostnader är omvänt proportionella mot r, så en hastighet på 1/16 leder till en provning som är ungefär fyra gånger långsammare och mer utrymmeskrävande än en hastighet på ¼. 

SHARP-verifieraren har kört FRI med en kodhastighet på 1/16 och med 12 verifieringsfrågor.

StarkWare antar att varje FRI-verifieringsfråga lägger till logg₂(1 /r) bitar av säkerhet. Enligt denna gissning ger 12 verifieringsfrågor 12 * log₂(16) = 48 bitars säkerhet.

Men aktuella analyser fastställer bara att varje verifieringsfråga lägger till något mindre än loggen₂(1/r^1/2) bitar av säkerhet. Så 12 FRI-verifieringsfrågor ger bara mindre än 12 * log₂(4) = 24 bitar av "bevisbar" säkerhet. 

Ett förslag för att mildra spänningen mellan säkerhet och prestanda

Praktiska PQ-SNARKs har verifieringskostnader som växer linjärt med önskat antal säkerhetsbitar. En lovande teknik för att mildra denna spänning är SNARK-kompositionen - som jag beskrev i mitt tidigare inlägg som ett sätt att lösa spänningen mellan provnings- och verifieringskostnader, men det kan också ta itu med säkerheten. 

Två exempel 

Polygon Hermez är komponera PQ-SNARKs med PlonK. Tanken är att provaren först genererar ett PQ-SNARK-bevis π. Om PQ-SNARK är konfigurerad att ha en snabb provning och en adekvat säkerhetsnivå, kommer π att vara stor. Så provaren skickar inte π till verifieraren. Istället använder den PlonK för att bevisa att den känner till π. 

Detta innebär att man tillämpar PlonK på en krets som tar π som ingång och kontrollerar att PQ-SNARK-verifieraren skulle acceptera π. Eftersom PQ-SNARK har en polylogaritmisk verifieringskostnad, appliceras PlonK på en liten krets, och därför är PlonK-provaren snabb. Eftersom PlonK-proven är små och billiga att verifiera, är verifieringskostnaderna låga. 

Tyvärr förstör användningen av PlonK transparens och postkvantsäkerhet. Man kan istället överväga att använda själva PQ-SNARK istället för PlonK för att bevisa kunskap om π (i själva verket är PQ-SNARK som används av Polygon självkomponerad på detta sätt). 

I denna andra tillämpning av PQ-SNARK, för att bevisa kunskap om π, kan systemet konfigureras för att uppnå adekvat säkerhet med rimligt stora bevis, till exempel genom att välja en mycket liten kodhastighet för användning i FRI. Nyckelpunkten är att även om denna lilla kodhastighet är dålig för provningstid, tillämpas den andra tillämpningen av PQ-SNARK endast på en liten krets, så den totala provningstiden bör fortfarande vara liten.

Vår teoretiska förståelse av säkerheten hos komponerade SNARK lämnar mycket övrigt att önska. Det finns dock inga kända attacker mot dem som är snabbare än att attackera en av de ingående SNARKs individuellt. Till exempel, om vi komponerar en PQ-SNARK med PlonK, vet vi inte en bättre attack än att antingen attackera PQ-SNARK (dvs. hitta ett PQ-SNARK-bevis π för ett falskt påstående), eller att attackera PlonK (dvs. hitta ett PlonK-bevis för det falska påståendet "Jag vet ett PQ-SNARK-bevis π som verifieraren skulle ha accepterat.")

Att komponera SNARKs på detta sätt är ett allt populärare sätt att förbättra prestandan. Jag hoppas att protokolldesigners också använder det för att förbättra säkerheten.

***

Justin Thaler är docent vid Georgetown University. Innan han började på Georgetown tillbringade han två år som forskare vid Yahoo Labs i New York, innan han var forskare vid Simons Institute for theory of Computing på UC Berkeley. 

Redaktör: Tim Sullivan @tim_org

***

De åsikter som uttrycks här är de från den individuella AH Capital Management, LLC (“a16z”) personal som citeras och är inte åsikterna från a16z eller dess dotterbolag. Viss information som finns här har erhållits från tredjepartskällor, inklusive från portföljbolag av fonder som förvaltas av a16z. Även om den är hämtad från källor som anses vara tillförlitliga, har a16z inte självständigt verifierat sådan information och gör inga utfästelser om informationens varaktiga riktighet eller dess lämplighet för en given situation. Dessutom kan detta innehåll innehålla tredjepartsannonser; a16z har inte granskat sådana annonser och stöder inte något reklaminnehåll i dem.

Detta innehåll tillhandahålls endast i informationssyfte och bör inte litas på som juridisk rådgivning, affärs-, investerings- eller skatterådgivning. Du bör rådfråga dina egna rådgivare i dessa frågor. Hänvisningar till värdepapper eller digitala tillgångar är endast i illustrativt syfte och utgör inte en investeringsrekommendation eller erbjudande om att tillhandahålla investeringsrådgivningstjänster. Dessutom är detta innehåll inte riktat till eller avsett att användas av några investerare eller potentiella investerare, och får inte under några omständigheter lita på när man fattar ett beslut om att investera i någon fond som förvaltas av a16z. (Ett erbjudande om att investera i en a16z-fond kommer endast att göras av det privata emissionsmemorandumet, teckningsavtalet och annan relevant dokumentation för en sådan fond och bör läsas i sin helhet.) Alla investeringar eller portföljbolag som nämns, hänvisas till, eller beskrivna är inte representativa för alla investeringar i fordon som förvaltas av a16z, och det finns ingen garanti för att investeringarna kommer att vara lönsamma eller att andra investeringar som görs i framtiden kommer att ha liknande egenskaper eller resultat. En lista över investeringar gjorda av fonder som förvaltas av Andreessen Horowitz (exklusive investeringar för vilka emittenten inte har gett tillstånd för a16z att offentliggöra såväl som oanmälda investeringar i börsnoterade digitala tillgångar) finns tillgänglig på https://a16z.com/investments /.

Diagram och grafer som tillhandahålls i är endast i informationssyfte och bör inte litas på när man fattar investeringsbeslut. Tidigare resultat är inte en indikation på framtida resultat. Innehållet talar endast från det angivna datumet. Alla prognoser, uppskattningar, prognoser, mål, framtidsutsikter och/eller åsikter som uttrycks i detta material kan ändras utan föregående meddelande och kan skilja sig åt eller strida mot åsikter som uttrycks av andra. Se https://a16z.com/disclosures för ytterligare viktig information.