zk-SNARKs: Korte ikke-interaktive argumenter

En zk-SNARK (Zero-Knowledge Succinct Non-interactive ARgument of Knowledge) er et bevis, der: (1) giver nulviden, (2) er kortfattet (lille bevis, hurtig verifikation uanset beregningens størrelse), (3) er ikke-interaktivt (én enkelt bevisstreng).

Sigma-protokoller fungerer for simple udsagn (kendskab til en diskret logaritme). Til komplekse beregninger — "Jeg kørte denne funktion korrekt på private input" — har vi brug for et generelt bevissystem. SNARK'er beviser vilkårlige beregninger med verifikationstid på O(1).

Beregningen udtrykkes først som et aritmetisk kredsløb: en rettet acyklisk graf af additions- og multiplikationsporte over et endeligt legeme. Eksempel: bevis, at du kender x, så x^3 + x + 5 = 35, uden at afsløre x=3. Kredsløbet har ~5 porte.

Et aritmetisk kredsløb omdannes til R1CS: et sæt begrænsninger (A*z)*(B*z) = C*z, hvor z er en vektor med alle ledningsværdier. Hver multiplikationsport bliver til én begrænsning. Beviseren skal finde z, der opfylder alle begrænsninger, uden at afsløre private ledninger.

R1CS omdannes til et QAP: polynomierne A(x), B(x), C(x), således at A(x)*B(x)-C(x) er deleligt med et målpolynomium t(x), hvis og kun hvis begrænsningerne er opfyldt. Beviseren viser, at vedkommende kender et polynomium H(x) som kvotient, uden at afsløre vidnet.

Groth16 (2016) er den mest effektive generelle SNARK. Efter en betroet opsætning (generering af CRS) producerer beviseren et bevis med 3 gruppeelementer (~192 bytes for BLS12-381). Verifikation: 3 paringsoperationer. Beviset har konstant størrelse uanset kredsløbets størrelse.

Groth16 kræver en betroet opsætning for hvert kredsløb: udvælg giftigt affald (en tilfældig hemmelighed), beregn den fælles referencestreng, og tilintetgør derefter det giftige affald. Hvis affaldet overlever, kan en modstander forfalske beviser. Flerparts-ceremonier (Powers of Tau) fordeler tilliden.

PLONK (2019) bruger en universel betroet opsætning: én ceremoni fungerer for alle kredsløb op til en fastsat størrelse. Der kræves ingen opsætning for hvert enkelt kredsløb. Afvejningen er lidt større beviser end med Groth16. Bruges i ZK-EVM-implementeringer (Polygon Hermez, zkSync Era).

STARK'er (Scalable Transparent ARguments of Knowledge) kræver ingen betroet opsætning og bruger hashfunktioner (postkvantesikre). Afvejningen er større beviser (snesevis af KB mod 200 bytes). Bruges i StarkWare/StarkNet og programmeringssproget Cairo. SNARK'er er mindre; STARK'er er kvantesikre.

Groth16 bruger bilineære paringer: e: G1 × G2 → GT, hvor e(a*P, b*Q) = e(P,Q)^{ab}. Det gør det muligt at kontrollere polynomielle identiteter i eksponenten uden at afsløre værdierne. Kurven BLS12-381 er optimeret til effektive Groth16-paringer.

Groth16's bevisgenereringstid for et kredsløb med 10^6 porte: ~10 sekunder på en moderne CPU. Verifikation: ~1 ms. Denne asymmetri er tilsigtet: beviseren, som udførte den tunge beregning, udfører arbejdet; verifikatoren (en blockchain-node) udfører næsten intet arbejde.

zk-SNARK'er beviser vilkårlige beregninger med beviser af konstant størrelse. Procesforløb: beregning → aritmetisk kredsløb → R1CS → QAP → SNARK-bevis. Groth16 er mest effektiv (betroet opsætning for hvert kredsløb); PLONK bruger en universel opsætning. Næste emne: ZKP-anvendelser i blockchain.