--- title: "Asymmetrisk-kunnskap nullkunnskap for autoregressiv språkmodell-inferens" subtitle: "PSI-LM, AKZK og AsymVZK — tre bidrag til verifiserbar LLM-tjeneste" author: - Einar Holt, Founder & Partner at tenki date: "Mai 2026" lang: nb-NO documentclass: article geometry: margin=2.5cm fontsize: 11pt linestretch: 1.15 header-includes: - \usepackage[norsk]{babel} --- ## Sammendrag Vi presenterer to konstruksjoner for verifiserbar autoregressiv språkmodell-inferens, og en ny formell trusselmodell — **asymmetrisk-kunnskap nullkunnskap** (AKZK) — som er avgjørende for den ene av dem. **Bakgrunn.** Eksisterende systemer for nullkunnskapsbevis (*zero-knowledge proofs*) over store språkmodeller, typifisert ved zkLLM (Sun et al., CCS 2024) og zkGPT (Qu et al., USENIX Security 2025), beviser én forwardpass om gangen og rapporterer kostnader på 15 minutter per 13B-modell-token. Autoregressiv generering — hvor en chat-fullføring krever hundre­vis av sekvensielle forwardpass-bevis — er fundamentalt ikke adressert. Naiv komposisjon koster opp mot ti dager per svar. **Bidrag 1: PSI-LM (baseline).** Vi formaliserer en *sampling-soundness*-konstruksjon som dekoblet bevistid fra sekvenslengde. Bevisansvarlig forplikter seg til *logits* per token; verifikator utfordrer en liten tilfeldig delmengde av posisjoner via Fiat–Shamir; soliditet kommer fra union-grense over utfordrings­distribusjonen. Posisjonsvis nullkunnskap holder utenfor utfordringssettet. **Bidrag 2: AKZK-trusselmodellen.** Vi formaliserer en utvidelse av Goldwasser–Micali–Rackoff-rammeverket der verifikatoren har tilgang til en offentlig hjelpe-orakel-funksjon. Orakelet er deterministisk og kan kjøres lokalt av verifikatoren. Dette generaliserer streng nullkunnskap; den klassiske definisjonen tilsvarer trivielt-orakel-tilfellet. Vi gir en formell simulator-basert definisjon og en assosiert sikkerhetsteorem for protokoller i denne modellen. **Bidrag 3: AsymVZK (hovedkonstruksjon).** Vi instansierer AKZK med orakelet $\mathcal{O}_{M_d}$ — en liten draft-modell som verifikatoren kjører fritt. Bevisansvarlig kjører speculative decoding (Leviathan et al., 2023) under en kryptografisk forpliktet aksept/forkast-test. Verifikator gjenkjører draft-modellen ved alle posisjoner (gratis i forhold til kryptografiske bevis) og utfordrer kun et lite antall *aksepterte* og *forkastede* posisjoner med fullt nullkunnskap-bevis. Verifikatorens kostnad skalerer med uenighet mellom $M$ og $M_d$, ikke med sekvenslengde. **Eksperimentelt.** Vi implementerer begge konstruksjonene og evaluerer på et reelt modellpar, **Qwen 2.5-1.5B-Instruct** (stor) og **Qwen 2.5-0.5B-Instruct** (utkast). På en typisk prompt oppnår speculative-aksept-raten ≈ 70 %, hvilket betyr at AsymVZK trenger kryptografiske bevis kun ved ≈ 30 % av posisjonene — og bare på et lite tilfeldig utvalg av disse. Empiriske deteksjons­rater for et juksende prover matcher det teoretiske *hybride* sikkerhets­båndet $1 - (1-\varepsilon_a)^{k_a}(1-\varepsilon_r)^{k_r}$. Ved kombinering med publiserte zkLLM-tall projiserer vi at AsymVZK kan flytte verifikasjonskostnaden for en 1024-token chat-fullføring fra ti dager (naiv full-trace) til en størrelsesorden under én time — over én størrelsesorden bedre enn PSI-LMs allerede betydelige forbedring. **Posisjonering.** AsymVZK er ikke en erstatning for full-trace ZKML; det er en kompletterende *protokoll-ramme* som utnytter en ny trusselmodell. Vi argumenterer for at AKZK-rammen — verifikator bevæpnet med svak modell-kunnskap — har anvendelser utover LLM-er, blant annet for verifiserbar federert læring, strømmende inferens, og edge-deploy modeller med retracing. --- ## 1. Innledning Tilliten til at en gitt språkmodellrespons er produsert av en bestemt modell kjørt korrekt blir i økende grad et regulatorisk krav. Forordninger som *EU AI Act*, *DORA* (Digital Operational Resilience Act) og medisinske tilsynsmyndigheters retningslinjer forutsetter sporbarhet av maskinlæringsbeslutninger som påvirker individer. Den relevante kryptografiske primitiven for *transferabel* tredjepartsverifikasjon er nullkunnskapsbevis (*zero-knowledge proofs*) — bevis som kan kontrolleres av enhver, med svært lav verifikatorkostnad, uten tillit til tjenestetilbyderens infrastruktur. I norsk og nordisk kontekst er behovet særlig synlig i tre sektorer. Helsesektoren har gjennom Helseplattformen-debatten og diskusjonen om kunstig intelligens i journal­føring blitt eksplisitt om at modellbeslutninger må være etterprøvbare. Bank- og forsikringssektoren under DORA krever revisjonsspor for algoritmiske beslutninger. Offentlig forvaltning under Datatilsynets tolkning av GDPR artikkel 22 krever begrunnelser for automatiserte avgjørelser. I alle disse settingene er det operative behovet *transferabel* verifiserbarhet: en regulator skal kunne kontrollere at modellen ble brukt korrekt, uten å re-eksekvere modellen og uten å få tilgang til hverken modellvektene eller brukerens prompt. ### 1.1 Det gapet litteraturen ikke har lukket Den dominerende forskningstråden i ZKML — typifisert ved zkLLM (Sun, Li og Zhang, CCS 2024), zkGPT (Qu et al., USENIX Security 2025), zkPyTorch (Polyhedra, 2025) og DeepProve (Lagrange Labs, 2025) — har konsentrert seg om å kompilere LLM-inferens direkte til en aritmetisk krets og bevise hele forwardpass-beregningen. Resultatene er imponerende: zkGPT beviser én GPT-2-forwardpass på under 25 sekunder; zkLLM når 13-milliarders modeller på under 15 minutter for én forwardpass, med under 200 KB bevis og 1–3 sekunders verifikasjon. Likevel forblir et grunnleggende gap åpent: **alle disse systemene måler kostnaden for én forwardpass på én prompt**. Autoregressiv generering — der modellen genererer ett token om gangen, hver gang basert på den voksende konteksten — sammensettes ikke gratis. Til vår kunnskap har intet produksjonssystem rapportert ende-til-ende-bevis for en autoregressiv chat-fullføring av realistisk lengde. En naiv komposisjon ville koste $L \cdot T_{\text{zk}}$, det vil si $L \cdot 15$ minutter for $L$-token utdata på 13B-modeller — i størrelsesordenen ti dager for typiske 1000-token-svar. ### 1.2 Vår tilnærming, i to steg **Steg 1: PSI-LM — sampling-soundness som baseline.** Vi formaliserer en cut-and-choose-konstruksjon der bevisansvarlig forplikter seg til *logit*-vektorer per token, og verifikatoren utfordrer en tilfeldig delmengde av $k$ posisjoner via Fiat–Shamir-transformasjonen. Soliditet kommer fra en union-grense over utfordrings­distribusjonen: en motpart som lyver på en andel $\varepsilon$ av posisjonene oppdages med sannsynlighet $1 - (1-\varepsilon)^k$. Konstruksjonen dekoblet bevistid fra $L$: bevisansvarliges kostnad er $O(L \cdot T_{\text{infer}} + k \cdot T_{\text{zk-pos}})$. For $k = 32$ og $L = 1024$ gir dette $\approx 32\times$ speedup over den naive autoregressive komposisjonen. **Steg 2: AsymVZK — asymmetrisk-kunnskap som ny trusselmodell.** Vi observerer at PSI-LM (og hele eksisterende ZKML-litteratur) antar at verifikatoren har null modell-kunnskap. Bryt denne antakelsen, og kostnadsstrukturen kollapser. AsymVZK formaliserer en ny trusselmodell — *asymmetrisk-kunnskap nullkunnskap* (AKZK) — der verifikatoren har tilgang til et offentlig hjelpe-orakel $\mathcal{O}$. Vi instansierer dette med en *draft-modell* $M_d$ som verifikatoren kan kjøre fritt. Protokollen bruker speculative decoding (Leviathan et al., 2023) under en kryptografisk forpliktet aksept/forkast-test. Verifikator gjenkjører draft-modellen ved alle posisjoner (gratis i forhold til kryptografiske bevis) og utfordrer kun ved et lite antall *aksepterte* og *forkastede* posisjoner med fullt nullkunnskap-bevis. ### 1.3 Bidrag, navngitt eksplisitt 1. **Asymmetrisk-kunnskap nullkunnskap (AKZK)**, en ny formell trusselmodell. Vi gir en simulator-basert definisjon (§5) som generaliserer den klassiske Goldwasser–Micali–Rackoff-rammen, og viser at standard ZK er det trivielle hjelpe-orakel-tilfellet. 2. **PSI-LM** (§6), en sampling-soundness-konstruksjon som baseline for sammenligning. Soliditet $1 - (1-\varepsilon)^k$ med eksplisitt $\varepsilon$-$\delta$ avveining; posisjonsvis nullkunnskap. 3. **AsymVZK** (§7), den første nullkunnskap-konstruksjonen for autoregressiv LLM-inferens som bruker speculative decoding kryptografisk. Hybrid soliditet $1 - (1-\varepsilon_a)^{k_a}(1-\varepsilon_r)^{k_r}$ over aksepterte/forkastede utfordringer; verifikator­kostnad skalerer med uenighet, ikke med sekvenslengde. 4. **Implementasjon på ekte modeller** (§8) — vi kjører begge konstruksjonene på Qwen 2.5-1.5B-Instruct (stor) og Qwen 2.5-0.5B-Instruct (utkast), måler aksept-rater på flere prompt-domener, sveiper prover/verifier-kostnader over $(L, k)$-rutenettet, og validerer empiriske deteksjons­rater mot teoretiske bånd. 5. **Posisjonering og videre arbeid** (§10): AKZK-rammen åpner en familie av konstruksjoner utover PSI-LM og AsymVZK — verifiserbar federert læring, strømmende inferens, edge-deploy med retracing. Vi diskuterer flere konkrete åpne spørsmål. --- ## 2. Bakgrunn Denne seksjonen samler det leseren behøver fra fire områder: nullkunnskapsbevis, språkmodell-arkitektur, ZKML-kostnads­regimet, og *speculative decoding* som inferens-akselerasjons­teknikk. ### 2.1 Nullkunnskapsbevis Et *zero-knowledge proof system* består av en bevisansvarlig $P$ og en verifikator $V$ som kjører et protokoll for å avgjøre om et utsagn $x$ tilhører et språk $\mathcal{L}$. Tre egenskaper kreves: - **Fullstendighet (completeness)**: hvis $x \in \mathcal{L}$ og $P$ kjenner et vitne $w$ slik at $(x, w) \in R$ for relasjonen $R$, aksepterer $V$ med høy sannsynlighet. - **Soliditet (soundness)**: hvis $x \notin \mathcal{L}$, aksepterer $V$ med forsvinnende liten sannsynlighet, selv mot adversielle bevisansvarlige. - **Nullkunnskap (zero-knowledge)**: $V$ lærer ingenting fra protokollen utover at $x \in \mathcal{L}$. Formelt finnes en simulator $\mathsf{Sim}$ som produserer en utskrift som er beregnings­messig uskillelig fra et ekte protokoll­opptak, gitt bare $x$. Den klassiske formuleringen er interaktiv (Goldwasser, Micali og Rackoff, 1989). Fiat–Shamir-transformasjonen (Fiat og Shamir, 1986) gjør protokollen ikke-interaktiv ved å erstatte verifikatorens tilfeldige utfordringer med en hash av tidligere meldinger — sikker i den tilfeldig orakel-modellen. For LLM-anvendelser bruker vi bygge­klosser som forpliktelses-skjema (*commitment schemes*): en bevisansvarlig binder seg til en verdi $m$ uten å avsløre den, og kan senere åpne forpliktelsen. *Hiding* sikrer at $m$ ikke avsløres før åpning; *binding* sikrer at forpliktelsen ikke kan åpnes til to forskjellige verdier. Pedersen-forpliktelser gir både hiding og binding under DL-antakelsen; SHA-256-baserte forpliktelser gir kun computational binding men er enklere og brukes i vår referanse­implementasjon. For matrise-tunge ML-beregninger har **sumcheck-protokollen** (Lund, Fortnow, Karloff og Nisan, STOC 1990) blitt den foretrukne primitiven, fordi den lar bevisansvarlig overbevise verifikatoren om en sum over en multilineær utvidelse av en tensor med polylog-mange runder. Sumcheck er en generalisering av Freivalds-algoritmen (Freivalds, 1979) til vilkårlige polynomer. **Lookup-argumenter** — *plookup*, *Lasso* (Setty et al., 2023), *Jolt* (Arun et al., 2023) — gjør ikke-lineariteter (softmax, GELU, LayerNorm) overkommelige ved å la beviset henvise til en forhåndsberegnet tabell, hvor *prover*-arbeidet skalerer med antall *unike* oppslag som faktisk brukes. **Folding-skjema** (Nova, SuperNova, HyperNova; Kothapalli et al., 2021–2023) lar bevisansvarlig akkumulere identiske gjentatte beregninger inkrementelt i én enkelt akkumulator. ### 2.2 Språkmodell-arkitektur i kortform En moderne LLM er en *decoder-only transformer* (Vaswani et al., 2017). En prompt $p = (x_1, \dots, x_n)$ tokeniseres til ID-er fra et vokabular $\mathcal{V}$ (typisk 30 000–150 000 tokens). Hvert token avbildes til en vektor i en *embedding*-tabell, og sekvensen passerer gjennom $L_d$ identiske blokker (typisk 12–80 avhengig av modellstørrelse). Hver blokk består av en *self-attention*-modul og et fremover­matet nettverk (FFN) omsluttet av residual­koblinger og lagnormalisering. For genering kjører modellen *autoregressivt*: gitt prompt $p$, beregnes *logits* $z_{n+1} \in \mathbb{R}^{|\mathcal{V}|}$ for det neste tokenet, et token $y_1$ trekkes ifølge en samplings-regel $R$ (greedy, top-$k$, top-$p$, eller temperatur-skalert kategorisk), deretter beregnes $z_{n+2}$ basert på $(p, y_1)$, og så videre. Sekvensen $h_t = (p, y_1, \dots, y_{t-1})$ er konteksten ved posisjon $t$. Operatorer som er problematiske kryptografisk inkluderer **softmax** (eksponential, divisjon, global normalisering), **GELU**/**SiLU**/**SwiGLU** (transcendentale ikke-lineariteter), **LayerNorm/RMSNorm** (kvadratrot, divisjon), og **selvoppmerksomhet** (kvadratisk i sekvenslengde). Matrisemultiplikasjon er enkel — den er den kostbare operasjonen i flytkomma-aritmetikk, men relativt billig i et SNARK-rammeverk basert på sumcheck. ### 2.3 Hvor skjæringspunktet er hardt LLM-er opererer på flytkommatall (typisk fp16 eller bf16); aritmetiske kretser opererer over en endelig kropp $\mathbb{F}_p$. Direkte emulering av én fp32-multiplikasjon koster hundretalls til tusentalls *constraints*; produksjons-ZKML-systemer kvantiserer derfor til INT8 eller INT16 og betaler en målbar perplexitets­tap. Trunkerings- og avrundnings­kontrollene som følger med denne kvantiseringen er, ifølge zkGPT (Qu et al., 2025), den enkelt største bidragsyteren til *prover*-tid — ikke matrisemultiplikasjonene selv. For å gi konkret skala: én GELU-evaluering rapporteres med ~11 654 PlonK-*constraints* ved polynomtilnærming. zkAttn-konstruksjonen i zkLLM bryter softmax ned i $K$ basis-$b$-segmenter og bruker tlookup på hver. Selvoppmerksomhets-matrisen — $N \times N$ for sekvenslengde $N$ — krever i et klassisk plonkish-oppsett å bli forpliktet i sin helhet; for GPT-2 small med $N = 2048, L_d = 12$ lag og 12 hoder gir det rundt 600 millioner cellevitner bare for selvoppmerksomhets­scorene. Det er likevel én flaskehals litteraturen ikke har drevet hardt: vitnegenererings­minne under autoregressiv dekoding. Hver ny token trenger en ny forwardpass på voksende kontekst. KV-cachen (key/value-bufferen som plaintext-LLM-tjenester bruker for å unngå å gjenta selvoppmerksomhets­beregningen) har ingen ren ekvivalent i ZKML: bufferede tensorer må fortsatt forpliktes og bevises. Dette er gapet både PSI-LM og AsymVZK adresserer. ### 2.4 Speculative decoding som plaintext-akselerasjon Speculative decoding (Leviathan, Kalman og Matias, ICML 2023; Chen et al., 2023) er en plaintext LLM-akselerasjons­teknikk som vi adopterer kryptografisk i AsymVZK. Ideen: la en mindre, billigere "draft"-modell $M_d$ foreslå tokens, og la den større $M$ verifisere forslagene gjennom en aksept/forkast-test som *bevarer den marginale fordelingen* av $M$. Konkret: ved hver posisjon $t$ trekker $M_d$ et forslag $y_t^{draft}$ fra sin distribusjon. Aksepterings-testen er: $$ u \sim U(0, 1), \quad \text{aksepter hvis } u \le \frac{p_M(y_t^{draft} \mid h_{t-1})}{p_{M_d}(y_t^{draft} \mid h_{t-1})}. $$ Hvis aksept: $y_t = y_t^{draft}$, og vi har spart én forwardpass av $M$ (hvis vi ikke allerede har gjort den). Hvis forkast: $y_t$ trekkes fra rest-distribusjonen $\max(p_M - p_{M_d}, 0)$ normalisert. Denne korreksjonen sikrer at marginalen av $y_t$ er nøyaktig $p_M$ — speculative decoding er *ubiasert*. I praksis implementeres speculative decoding ved at $M_d$ predikerer flere tokens av gangen ("draft chunk"), og $M$ beregner *parallelt* over hele draftet før aksept/forkast brukes. Dette gir en ~2–3× hastighets­forbedring på godt-justerte $(M, M_d)$-par, fordi $M$ kjører batched inferens i stedet for autoregressivt. For våre formål bryr vi oss ikke om hastighetsfordelen *for prover* — den er i størrelsesordenen 2–3× og forsvinnende i forhold til kryptografiske kostnader. Det vi bryr oss om er **at aksept/forkast-beslutningen er en ren funksjon av $(p_M(y^{draft}), p_{M_d}(y^{draft}), u)$, og at den derfor er kryptografisk kontrollerbar**: hvis verifikatoren har $M_d$ og $u$, og *prover* påstår en bestemt verdi for $p_M(y^{draft})$, kan verifikatoren regne ut om aksept/forkast-beslutningen er konsistent med påstanden. Det er denne strukturelle egenskapen som muliggjør AsymVZK. --- ## 3. Relatert arbeid Vi syntetiserer her det vi anser som de fem mest betydningsfulle trådene i ZKML-litteraturen, sett gjennom linsen til vår konstruksjon. ### 3.1 ZKML-systemer for transformere **zkLLM** (Sun et al., 2024) er den viktigste forløperen. Konstruksjonen kombinerer *tlookup* (et parallellisert lookup-argument over tensor-verdier) med *zkAttn* (en spesialisert sumcheck for selvoppmerksomhet) og kjører som CUDA-kjerne direkte på GPU-minne. Resultatet er bevis for én forwardpass av LLaMA-2-13B på under 15 minutter, med bevis under 200 KB og 1–3 sekunders verifikasjon. zkLLM-arbeidet identifiserer eksplisitt at konstruksjonen kun bedømmer én forwardpass — ende-til-ende-autoregressiv dekoding er ikke målt. **zkGPT** (Qu et al., 2025) forbedrer kostnadsprofilen for GPT-2-skala modeller dramatisk: en forwardpass av GPT-2 (117M parametre) bevises på under 25 sekunder ved hjelp av *constraint fusion* for ikke-lineære lag og *circuit squeeze* for parallellisering. zkGPT bekrefter at flaskehalsen har flyttet seg fra matrisemultiplikasjon til avrundningskontroller i kvantiseringen. **zkPyTorch** (Polyhedra, 2025) er en kompilator fra PyTorch til *Expander*-bevissystemet, med rapporterte ~150 sekunders bevistid per token for Llama-3.1-8B. Hardware og bevis­størrelser er ikke offentliggjort. **DeepProve-1** (Lagrange Labs) hevder nedbrytning til omtrent ett minutt per inferens på et 10-maskins distribuert oppsett. **ZKTorch** rapporterer GPT-J 6B på rundt 20 minutter med 64 tråder. **Modulus Labs** publiserte et tidlig referansepunkt: GPT2-XL (1,5 milliarder parametre) bevist ende-til-ende på Halo2 i mars 2024, med ~200 timers bevisproduksjon på en 128-kjerners maskin med 1 TB RAM og 10 TB disk. Forholdet til ren inferens er rapportert som 1 125 761×. Felles for alle disse systemene: bevisstørrelsen og bevistiden gjelder *én* forwardpass. Ingen rapporterer ende-til-ende-kostnad for en realistisk autoregressiv chat-fullføring. ### 3.2 Bevissystemer Konsensusen for hvor SNARK-er for transformere skal bygges har konvergert: **sumcheck** (Lund et al., Libra) over multilineære utvidelser av tensorer på innsiden av hver lag, **lookup-argumenter** (Lasso, Jolt, LogUp) for ikke-lineariteter, eventuelt **folding-skjema** (Nova, HyperNova, Sangria) for repetert struktur, og en KZG- eller Groth16-innpakning utenpå for kompakte on-chain-bevis. Den 35,7× hastighetsforskjellen zkLLM oppnådde over Halo2-baserte ZKML-systemer er det empiriske beviset på at *Plonkish*-monolittiske kretser er feil arkitektur. For våre konstruksjoner er det mest interessante observasjonen at folding-skjema er strukturelt ideelle for transformere — hver av $L_d$ identiske blokker er et nytt fold-trinn — men *folding av lookup-argumenter* er fortsatt et åpent forskningsspørsmål (Bünz og Chen, 2024; *Origami*, *Mova*, *Protostar*). Dette betyr at den asymptotisk «riktige» arkitekturen for transformere ennå ikke er en ferdig leverbar konstruksjon. ### 3.3 Tilstøtende personverntiln­ærminger Tre alternativer til ZK konkurrerer om samme tjenester, men løser forskjellige problemer: **FHE** (fullt homomorf kryptering): kjører modellen på kryptert input. Zama Concrete-ML har vist at flytting av *ett enkelt oppmerksomhetslag* av phi-1.5 til FHE gir 2,5 sekunders latens per token; GPT-2 small ende-til-ende i FHE ligger på rundt 11 sekunder per token på GPU. Ingen FHE-stack har vist seg på modeller større enn ~1B i 2026. **MPC** (sikker flerpartsberegning): deler modell og/eller input på flere ikke-samkjørte parter. PUMA gir LLaMA-7B-inferens i ~5 minutter per token via 3PC; BumbleBee og SIGMA er sammenlignbare. Krever en non-collusion-antakelse som er vanskelig i praksis. **TEE-er** (trusted execution environments): NVIDIA H100 Confidential Computing rapporterer under 7 % overhead på frontier-skala. Apple Private Cloud Compute og Anthropic Confidential Inference bygger på dette. Dette er klart vinneren på *konfidensialitet ved kjøretid*. Likevel: *TEE.fail* (oktober 2025) viste sub-$1000-DDR5-angrep som bryter Intel TDX/SGX og AMD SEV-SNP, og *Heracles* (CCS 2025) demonstrerte en chosen-plaintext-sidekanal mot SEV-SNP. Begge maskinvareleverandørene erklærte fysiske angrep utenfor scope. Implikasjon: ZK konkurrerer ikke med TEE på konfidensialitet ved kjøretid. ZK leverer *transferabel kryptografisk verifiserbarhet* — en eiendom ingen av de andre alternativene har. ### 3.4 Slalom og Freivalds-tradisjonen **Slalom** (Tramèr og Boneh, ICLR 2019) brukte Freivalds' algoritme (Freivalds, 1979) inni et SGX-enclave for å verifisere matrisemultiplikasjoner som ble outsourcet til en upålitelig GPU. Selv om Slalom ikke er kryptografisk nullkunnskap, er det det viktigste referansepunktet for *probabilistisk maskinlæringsverifikasjon*. Sumcheck-protokollen (Lund et al., 1990; Goldwasser, Kalai og Rothblum, STOC 2008) kan ses som en generalisering av Freivalds. PSI-LM tar et lignende skritt: vi bruker probabilistisk soliditet over *posisjoner* i en autoregressiv sekvens, der Slalom brukte den over rader/kolonner i en matrisemultiplikasjon. AsymVZK går videre: den bruker Slalom-aktig asymmetri (verifikator har en *lokalt-kjørbar* lavere-tier-orakel) men byttet ut SGX med en kryptografisk forpliktet lokalmodell. Strukturen er lignende; substansen er annerledes. En samtidig og nært beslektet tråd er **Chong, Ohsaki og Ng (2025)** [@chong2025tractable], som foreslår *tractable asymmetric verification* for LLM-utdata ved å utnytte *deterministisk replikerbarhet*: i et homogent maskinvare-/programvaremiljø er autoregressive modeller bit-eksakt reproduserbare, slik at en validator kan re-kjøre små tilfeldige utdata-segmenter og sammenligne. De rapporterer verifikasjon mer enn 12× raskere enn full regenerering, med justerbar deteksjonssannsynlighet, på simulerte arbeidslaster. Dette ligger i samme «asymmetriske innsats»-slekt som AsymVZK, men i et ikke-kryptografisk regime: det finnes ingen bindende forpliktelse, verifikatoren kjører *hele* modellen på det auditerte segmentet (bare på et strengt utvalg av posisjoner), og soliditet hviler på homogeniteten i validatorens stack snarere enn på en kryptografisk primitiv. AsymVZK og PSI-LM utfyller dermed snarere enn konkurrerer med denne linjen: Chong et al. gir en deployment-vennlig tillitsmekanisme innenfor én homogen flåte; vi gir en kryptografisk bindende mekanisme som overlever et heterogent, adversarielt prover/verifikator-par og produserer et overførbart bevis. ### 3.5 Verifiserbar evaluering (South et al., 2024) foreslår *verifiable evaluations*: kryptografiske bevis for at en gitt modell oppnår en gitt nøyaktighet på en held-out testsett. Dette er en *outputbasert* tilnærming i samme ånd som PSI-LM, men anvendt på batch-evaluering, ikke autoregressiv inferens. Vårt bidrag kan ses som å videreføre denne linjen til generative settings. ### 3.6 Speculative decoding Speculative decoding (Leviathan et al., 2023; Chen, Borgeaud et al., 2023) er en plaintext-akselerasjons­teknikk for LLM-tjenester. Standard akselerering bruker draft-modellen til å forutsi flere tokens parallelt, som verifiseres batched av den store modellen. Hastighetsforbedring 2–3× er typisk for godt-justerte $(M, M_d)$-par. Til vår kunnskap har ingen tidligere arbeid brukt speculative decodings aksept/forkast-test som en *kryptografisk* forpliktelse. AsymVZK gjør det. ### 3.7 Det autoregressive gapet, eksplisitt For å gjøre tydelig hvorfor vi anser det autoregressive gapet for sentralt, sammenstiller vi det publiserte tallene med hva en realistisk komposisjon ville koste: | System | Forwardpass-bevistid | Naiv autoregr.\ ($L=1000$) | Naiv autoregr.\ ($L=4000$) | |---|---:|---:|---:| | zkLLM (LLaMA-2-13B) | 15 min | 250 t (~10 dager) | 1000 t (~42 dager) | | zkGPT (GPT-2 117M) | 25 s | 6,9 t | 27,8 t | | zkPyTorch (Llama-3 8B) | ~150 s/token | 41 t | 167 t | | Modulus (GPT2-XL 1,5B) | 200 t | 200 000 t (~22 år) | 800 000 t (~91 år) | Disse tallene er ikke publiserte i de respektive artiklene; de er beregnet ved å multiplisere den rapporterte forwardpass-tiden med utdatalengden. Dette er den eneste komposisjons­modellen som er offentlig kjent for autoregressive bevis i dag, og den er klart utilstrekkelig for produksjon. PSI-LM endrer komposisjons­modellen fra $L \cdot T_{\text{zk}}$ til $L \cdot T_{\text{infer}} + k \cdot T_{\text{zk}}$, der det andre leddet dominerer ved typiske $k \in [30, 60]$. AsymVZK reduserer det videre til $L \cdot T_{M_d} + (k_a + k_r) \cdot T_{\text{zk}}$, der $L \cdot T_{M_d}$ er $M_d$-eksekutering som verifikator gjør lokalt og gratis. ### 3.8 Den nordiske konteksten Vi argumenterer for at AKZK-rammen og dens instansieringer er særlig relevante for den nordiske offentligheten. Tre forhold underbygger dette: For det første har Norden en høy regulatorisk modenhet rundt automatiserte beslutninger. Datatilsynet i Norge har siden 2021 krevd «forklaringsevne» i automatiserte avgjørelser etter GDPR artikkel 22. EUs AI Act (vedtatt 2024) krever sporbarhet for AI-systemer i kategorien «høy risiko», og DORA (Digital Operational Resilience Act, ikrafttredelse 2025) krever revisjonsspor for finansielle algoritmer. ZK-baserte teknikker som tillater *senere* verifikasjon av en allerede utført inferens — uten å re-eksekvere modellen, og uten tilgang til verken parametre eller input — er nettopp egnet for slike revisjonskrav. For det andre er motviljen mot å sende sensitive data til amerikanske skytjenester målbar i de nordiske offentlige sektorene. Helseplattformen-debatten i Norge, kontroversene rundt FHIs koronaapper, og den svenske *MSB*s eksplisitte anbefalinger om on-prem AI for forsvars­tilstøtende formål peker alle i retning av at on-prem-løsninger er strategisk preferert. AsymVZKs asymmetri lar en regulator (f.eks. *Datatilsynet* eller en sekundær myndighet) verifisere en inferens *lokalt* uten datatilgang og uten å re-eksekvere modellen. For det tredje er den nordiske finanssektorens DORA-rammeverk eksplisitt om at **utkontraktert AI** krever tilstrekkelige tekniske kontroller for å forsikre regulatoren om kontinuerlig korrekthet. En tjeneste som leverer LLM-respons med et ledsagende AsymVZK-bevis kan tilfredsstille dette uten at regulatoren må stole på utkontrakterings­operatørens infrastruktur. --- ## 4. Trusselmodell og notasjon Vi formaliserer her elementene som er felles for begge konstruksjonene før vi spesialiserer §5–§7. ### 4.1 Notasjon - $\mathcal{V}$: token-vokabular, $V = |\mathcal{V}|$. - $M$: stor språkmodell, hemmelig for *prover*. $M(h) \in \mathbb{R}^V$ er *logits* gitt kontekst $h$. - $M_d$: liten draft-modell, offentlig (i AsymVZK). - $p$: prompt, $p \in \mathcal{V}^*$, hemmelig. - $L$: antall genererte tokens. - $h_t = (p, y_1, \ldots, y_{t-1})$: kontekst ved posisjon $t$. - $z_t = M(h_{t-1}) \in \mathbb{R}^V$: *logits* ved posisjon $t$. - $p_M(y \mid h) = \mathrm{softmax}(z)[y]$: sannsynlighet for token $y$ gitt kontekst $h$. - $R$: offentlig samplings-regel. $R(z, \rho) \in \mathcal{V}$, deterministisk gitt logits og randomness. - $\mathsf{Com} = (\mathsf{Setup}, \mathsf{Commit}, \mathsf{Open})$: forpliktelses-skjema. - $H$: hash-funksjon, modellert som tilfeldig orakel for Fiat–Shamir. - $\Pi_M$: bevissystem for modell-konsistens ved gitt posisjon (relasjon $R_M$). - $\lambda$: sikkerhetsparameter. ### 4.2 Generelle antakelser - **Bevisansvarlig** er adversiell og kontrollerer alt på sin side: prompt, modell, samplings-tilfeldighet, utdata. Bevisansvarlig har polynomial regnetid og et begrenset *grinding*-budsjett $T_{\text{grind}}$ for Fiat–Shamir. - **Verifikator** er ærlig og følger protokollen. - **Antagelser**: forpliktelses-skjema er hiding og binding mot probabilistisk polytid (PPT), $\Pi_M$ er fullstendig, solid og nullkunnskaps­bevarende, og $H$ er en kollisjonsresistent hash i den tilfeldig orakel-modellen. ### 4.3 Modell-konsistens-relasjonen For begge konstruksjonene er den indre kryptografiske primitiven et bevissystem $\Pi_M$ for relasjonen $$ R_M = \{ ((C, p, h, t, z); (M, w_M)) : C = \mathsf{Com}_M(M; w_M) \land M(p, h)_t = z \}, $$ det vil si: gitt en modell-forpliktelse $C$, en prompt $p$, et prefiks $h$ og en posisjon $t$, er *logit*-vektoren $z$ ved posisjon $t$ nøyaktig det modellen $M$ gir på kontekst $(p, h)$. Bevissystemet $\Pi_M$ skal være ZK over $(p, h, M, w_M)$; bare $C, t, z$ er offentlige. PSI-LM og AsymVZK er parametrisert over $\Pi_M$; konkrete instansieringer kan være zkLLM-class single-position SNARK-er, sumcheck-baserte protokoller, eller GKR-folder. For våre referanse­implementasjoner *stubber* vi $\Pi_M$ ved at verifikator re-evaluerer $M$ ved utfordrede posisjoner. Dette er en eksplisitt innrømmelse som lar oss måle proto­kollene rundt $\Pi_M$ uten å implementere zkLLM på nytt. --- ## 5. Asymmetrisk-kunnskap nullkunnskap (AKZK) Vi formaliserer her trusselmodellen som AsymVZK avhenger av. AKZK er et bidrag i seg selv — en utvidelse av Goldwasser–Micali–Rackoff-rammen — og er egen­publisering verdig. ### 5.1 Motivasjon I standard ZK lærer verifikatoren ingenting utover utsagnets sannhets­verdi. *Public-coin*-protokoller tillater verifikatoren å bidra med tilfeldige biter, men ikke med *domene­kunnskap*. For en LLM-anvendelse er denne antakelsen unødvendig streng: i praksis er det fullt rimelig å gi verifikatoren tilgang til en *liten, offentlig* modell som verifikatoren kan kjøre lokalt for konsistenssjekker. Den lille modellen avslører ikke noe om den store modellen; den er en *separat* offentlig artefakt. Standard ZK kan ikke modellere dette uten å gi verifikatoren *full* kunnskap om alt offentlig — som inkluderer den lille modellen — men den klassiske ZK-definisjonen forplikter simulator­en til å produsere en utskrift kun fra det *offentlige inputet*. AKZK utvider dette: simulatoren har samme orakel-tilgang som verifikatoren. ### 5.2 Formell definisjon **Definisjon 1 (AKZK).** La $\mathcal{O}: X \to Y$ være en deterministisk offentlig orakel-funksjon. Et protokoll $\Pi$ for relasjonen $R \subseteq X \times W$ er **asymmetrisk-kunnskap nullkunnskap** med hensyn på $\mathcal{O}$ hvis: 1. **Fullstendighet.** For alle $(x, w) \in R$, en ærlig bevisansvarlig overbeviser en ærlig verifikator med sannsynlighet $\ge 1 - \mathsf{negl}(\lambda)$. 2. **AKZ-soliditet.** For enhver PPT motpart $\mathcal{A}$ med orakel-tilgang til $\mathcal{O}$, $\Pr[\mathsf{Verify} \text{ aksepterer på } x \notin R] \le \mathsf{negl}(\lambda)$. 3. **Asymmetrisk nullkunnskap.** Det finnes en PPT simulator $\mathsf{Sim}^{\mathcal{O}(\cdot)}$ som, gitt $x$ og orakel-tilgang til $\mathcal{O}$, produserer en utskrift som er beregnings­messig uskillelig fra et ekte protokoll-opptak. Simulatorens orakel-tilgang speiler verifikatorens. Dette er en streng generalisering av standard ZK: når $\mathcal{O}$ er det trivielle orakelet (returnerer ingenting), reduseres AKZK til vanlig ZK. ### 5.3 Sammenligning med eksisterende rammer AKZK er ikke det samme som: - **Public-coin ZK**: verifikatoren bidrar med *tilfeldige biter*, ikke med en *funksjon*. AKZK gir verifikatoren en deterministisk hjelpefunksjon. - **Ikke-malleable ZK**: ortogonalt; handler om at bevis ikke kan modifiseres. - **Witness-indistinguishable proofs**: forskjellige vitner gir samme bevis; ortogonalt til hjelpe-orakel. - **Selective opening**: handler om hvor mye av et vitne som åpnes; ortogonalt. - **Signature-based ZK** (Boneh, Camenisch et al.): bruker signaturer som offentlige hjelpe­objekter, men disse er statiske, ikke en kjøre-tids­funksjon. Det nærmeste eksisterende rammeverket er **arguments with reference string** der verifikatoren har tilgang til en *struktur* (f.eks. en CRS). AKZK skiller seg ved at hjelpe­objektet er en *funksjon* som verifikatoren *evaluerer* på kjøretid på vilkårlig input — det er en orakel, ikke en streng. ### 5.4 Hvorfor det betyr noe I LLM-kontekst er forskjellen ikke akademisk. Hvis verifikatoren har en draft-modell $M_d$, kan den selv verifisere store deler av en autoregressiv generering uten å invokere kryptografi i det hele tatt. Den kryptografiske primitiven trenger bare å dekke posisjoner der draft og full modell *kan være uenige*. Hvis aksept-raten er 90 %, er kryptografisk arbeid begrenset til 10 % av posisjonene, modulo cut-and-choose. Dette er kategorisk forskjellig fra standard ZK, hvor verifikator­arbeidet skalerer med protokollens egne primitiver. AKZK åpner for en familie av konstruksjoner. Foruten AsymVZK kan man tenke seg: - **Orakel = en sektorspesifikk regelmodell** (f.eks. juridisk klassifikator): ZK-bevis at LLM-utdata oppfyller juridisk skranke uten å avsløre prompt eller modell. - **Orakel = en sikkerhets­filter**: ZK-bevis at modellen ikke har gitt forbudt utdata. - **Orakel = en historisk modell**: ZK-bevis at en finjustert modell ikke avviker mer enn $\delta$ fra en tidligere godkjent versjon. Hver av disse er en separat anvendelse av AKZK-rammen. ### 5.5 Reduksjon til standard ZK i grensetilfellet Vi viser eksplisitt at AKZK reduseres til klassisk ZK når orakelet er trivielt. **Lemma 1 (Bakover-kompatibilitet).** La $\mathcal{O}_\bot$ være orakelet som returnerer $\bot$ på alle input. Da er $\Pi$ AKZ-zero-knowledge med hensyn på $\mathcal{O}_\bot$ hvis og bare hvis $\Pi$ er klassisk zero-knowledge. *Bevisskisse.* Hvis $\Pi$ er AKZ-ZK med hensyn på $\mathcal{O}_\bot$, er simulatoren $\mathsf{Sim}^{\mathcal{O}_\bot}$ ekvivalent med en simulator som ikke bruker orakel (orakelet leverer ingen informasjon). Motsatt, hvis $\Pi$ er klassisk ZK, kan simulatoren ignorere $\mathcal{O}_\bot$. ∎ **Lemma 2 (Generalisering ved orakel-utvidelse).** La $\Pi$ være klassisk ZK. Da er $\Pi$ trivielt AKZ-ZK med hensyn på *enhver* offentlig orakel $\mathcal{O}$. *Bevisskisse.* Simulatoren beholder sin klassiske oppførsel og ignorerer $\mathcal{O}$-tilgangen. Verifikatoren kan også ignorere $\mathcal{O}$. ∎ Disse lemmaene viser at AKZK er en *meningsfull* utvidelse: hvis vi bare definerer det som «klassisk ZK pluss orakel», vinner vi ingenting. Det interessante skjer når protokollen *bruker* orakel-tilgangen til å forenkle prover- og verifikator-arbeidet, slik AsymVZK gjør. Den substansielle definisjonen krever at *både* prover og verifikator (og simulator) drar nytte av orakelet. ### 5.6 En forsvarlig formell ekvivalens­klasse **Definisjon 2 (Substansiell AKZK).** Et AKZK-protokoll $\Pi$ er *substansielt* hvis det finnes ingen klassisk ZK-protokoll $\Pi'$ for samme relasjon der prover-arbeidet $T_P$, verifikator-arbeidet $T_V$, og bevisstørrelsen $|s|$ alle er innen en konstant faktor av $\Pi$s tilsvarende kostnader, mens vi gir $\Pi'$ tilgang til de samme primitiver. AsymVZK er substansiell AKZK i denne forstand: enhver klassisk ZK-protokoll for samme problemfamilie ($L$-token autoregressiv generering) har enten $T_V \in \Omega(L \cdot T_M)$ (full verifikator-replay) eller $T_V \in \Omega(L \cdot T_{\Pi_M})$ (full forwardpass-bevis). AsymVZK gir $T_V \in O(L \cdot T_{M_d} + k \cdot T_{\Pi_M})$ — en strikt billigere klasse for $T_{M_d} \ll T_M$. ### 5.7 Anvendelsesperspektiv: hva AKZK gjør mulig For å konkretisere hva AKZK åpner som ikke var mulig før, lister vi tre konkrete scenarier: **Scenario 1: Regulator-revisjon av medisinsk LLM.** En sykehus-AI gir behandlings­anbefalinger. Datatilsynet eller Statens Legemiddelverk vil verifisere at modellens svar er korrekte uten tilgang til pasient­data eller modellvektene. Med AKZK kan tilsynet holde en *liten*, offentlig referanse­modell trent på offentlig medisinsk litteratur. Tilsynet kjører referanse­modellen lokalt og krever AsymVZK-bevis for posisjoner der referansen er uenig. Dette gir tilsynet meningsfull kontroll uten kostbart full-trace-bevis. **Scenario 2: Verifiserbar rekkefølge­tjeneste.** En bank gir AI-baserte kreditt­vurderinger. EU-banktilsynet (EBA) vil ha jevnlig kontroll. Banken og EBA blir enige om en offentlig "EBA-referanse­modell" som er svakere enn bankens produksjonsmodell men strukturelt lik. EBA kan da utføre AsymVZK-revisjon: kjøre referanse­modellen lokalt og kreve bevis ved posisjoner der bankens modell sier noe vesentlig forskjellig. Dette gjør at EBA kan revidere uten å måtte holde bankens modell. **Scenario 3: On-chain LLM-tjeneste.** En desentralisert LLM-tjeneste (f.eks. på Ethereum) krever bevis for at responsen er produsert av den lovede modellen. Smartkontrakten holder en kompakt sjekksum av en *liten* draft-modell ved hjelp av et offentlig manifest. Brukerens egen wallet kan kjøre draft-modellen lokalt (det er småskala) og verifisere AsymVZK-beviset på chain. Den store modellen er aldri eksponert. Disse scenariene har en felles struktur: tilstedeværelsen av en *naturlig* offentlig hjelpemodell — en som er liten nok til å distribueres, men strukturelt lik nok til den store modellen til å gi meningsfull aksept-rate. Når dette er på plass, gir AKZK et praktisk rammeverk for transferebar verifikasjon. --- ## 6. Konstruksjon 1 — PSI-LM (sampling-soundness baseline) Vi formaliserer her PSI-LM som vår baseline. Den er en cut-and-choose-konstruksjon som dekoblet bevistid fra sekvenslengde gjennom probabilistisk soliditet. ### 6.1 Setup ``` PSI-LM.Setup(1^lambda, params_R): pp_Com <- Com.Setup(1^lambda) pp_M <- Pi_M.Setup(1^lambda) pp_R <- params_R // f.eks. temperatur tau, top-k = K return pp = (pp_Com, pp_M, pp_R, lambda) ``` ### 6.2 Bevisansvarliges algoritme ``` Phase A — generering: h_0 <- p for t = 1..L: z_t <- M(h_{t-1}) // logits rho_t <- random y_t <- R(z_t, rho_t) // sampling r_t <- random c_t <- Com.Commit( z_t || rho_t ; r_t ) // forpliktelse h_t <- h_{t-1} || y_t Phase B — Fiat-Shamir: transcript <- (pp, C_M, c_1..c_L, y_1..y_L) S <- Challenge(transcript, k) // |S| = k Phase C — åpninger ved utfordrede posisjoner: For hver t i S: Generer Pi_M-bevis pi_M^t for at M(p, y_ \varepsilon] \le T_{\text{grind}} \cdot (1 - \varepsilon)^k + \mathsf{negl}(\lambda), $$ der $f(y)$ er andelen av posisjoner hvor *prover*ens forpliktede $z_t$ er inkonsistent med $M$ etter ekstraktor­argument, og $T_{\text{grind}}$ er motpartens *grinding*-budsjett. **Bevisskisse.** Gitt en fast utskrift, er $S$ uniformt fordelt over $\binom{[L]}{k}$. Hvis $\mathcal{A}$ lyver på fraksjon $> \varepsilon$, er sannsynligheten for at $S$ unngår alle løgnposisjoner høyst $(1-\varepsilon)^k$ (binomisk grense). $T_{\text{grind}}$-faktoren gjenspeiler antall ulike tilfeldighetsbiter $\mathcal{A}$ kan grinde over; $\mathsf{negl}(\lambda)$-leddet absorberer feilraten i $\Pi_M$ og bindingen i $\mathsf{Com}$. ∎ ### 6.5 Hva «zero-knowledge» betyr i PSI-LM PSI-LM gir *ikke* full beregningsmessig nullkunnskap over forwardpassen. Det vi gir er: - **Uskillelighet ved ikke-utfordrede posisjoner**: verifikator skiller ikke en ekte utskrift fra en simulert; *logits* og samplings-tilfeldighet ved $t \notin S$ er gjemt. - **Avsløring ved utfordrede posisjoner**: $z_t$ og $\rho_t$ avsl­øres for $t \in S$, men prompten $p$, modellparametrene $M$, og *logits* ved alle øvrige posisjoner forblir hemmelige. - **Distributiv soliditet med $\varepsilon$–$\delta$**: motparten oppdages med eksplisitt sannsynlighet som funksjon av $k$ og motpartens løgnandel. Dette er en *posisjonsvis* nullkunnskap. Det er en svakere egenskap enn standard «hele beregningen er ZK», men den er sterkere enn «ingen kryptografisk garanti i det hele tatt». --- ## 7. Konstruksjon 2 — AsymVZK (hovedkonstruksjon) Vi formaliserer her AsymVZK, vår hoved­konstruksjon. AsymVZK instansierer AKZK-trusselmodellen med orakelet $\mathcal{O}_{M_d}$ (kjøring av draft-modell). Protokollen bruker speculative decoding under en kryptografisk forpliktet aksept/forkast-test. ### 7.1 Tilleggs-primitiver I tillegg til primitiver fra §4 trenger AsymVZK: - **Draft-modell** $M_d$, offentlig. Vi antar $M_d$s vekter er offentlige; alternativt en separat forpliktelse $C_{M_d}$ som verifikatoren stoler på. - **Resamplings-regel** $R_{\text{corr}}$ for rest-distribusjon ved forkast: $R_{\text{corr}}(z_M, z_{M_d}, \rho) \in \mathcal{V}$ trekker fra $\max(p_M - p_{M_d}, 0) / \|\cdot\|_1$. ### 7.2 Aksepterings-testen For hver posisjon $t$: - Trekk $u_t \sim U(0, 1)$ fra offentlig randomness $\rho_t^{acc}$. - Aksepter $y_t^{draft}$ hvis $$ u_t \le \mathrm{thr}_t = \frac{p_M(y_t^{draft} \mid h_{t-1})}{p_{M_d}(y_t^{draft} \mid h_{t-1})}. $$ Hvis aksept: $y_t = y_t^{draft}$. Hvis forkast: $y_t = R_{\text{corr}}(z_t, z_t^d, \rho_t^b)$. Den marginale fordelingen av $y_t$ er nøyaktig $p_M(\cdot \mid h_{t-1})$. (Bevis: standard speculative decoding ubiasertet, Leviathan et al., 2023.) ### 7.3 Prover-algoritmen ``` AsymVZK.Prove(pp, M, w_M, p, L, k_a, k_r): Phase A — generering med speculative decoding: h_0 <- p for t = 1..L: # Draft-steg z_t^d <- M_d(h_{t-1}) rho_t^d <- random y_t^d <- R(z_t^d, rho_t^d) # Stor-modell-steg z_t <- M(h_{t-1}) rho_t^a <- random u_t <- UniformFromBytes(rho_t^a) thr_t <- p_M(y_t^d) / p_{M_d}(y_t^d) a_t <- (u_t <= thr_t) # Token-beslutning if a_t == 1: y_t <- y_t^d else: rho_t^b <- random y_t <- R_corr( residual(z_t, z_t^d), rho_t^b ) # Forplikt c_t <- Com( z_t || rho_t^d || rho_t^a || rho_t^b || a_t || y_t^d ; r_t ) h_t <- h_{t-1} || y_t Phase B — Fiat-Shamir: transcript <- (pp, C_M, C_{M_d}, c_1..c_L, a_1..a_L, y_1..y_L) S_a <- ChallengeAccepted(transcript, k_a) # underset av aksepterte posisjoner S_r <- ChallengeRejected(transcript, k_r) # underset av forkastede Phase C — åpninger: For t i S_a: Åpne c_t til (z_t, rho_t^d, rho_t^a, _, a_t=1, y_t^d). Generer Pi_M-bevis pi_M^t som viser M(h_{t-1})_t = z_t, og at thr_t >= u_t (aksept rettferdiggjort). For t i S_r: Åpne c_t til (z_t, rho_t^d, rho_t^a, rho_t^b, a_t=0, y_t^d). Generer Pi_M-bevis pi_M^t som viser M(h_{t-1})_t = z_t, at thr_t < u_t (forkast rettferdiggjort), og at y_t = R_corr(residual(z_t, z_t^d), rho_t^b). Returner pi = (C_{M_d}, a_1..a_L, c_1..c_L, S_a, S_r, åpninger, Pi_M-bevis, rho_t^d for alle t, // draft randomness åpnes for V's gjenopplivelse av M_d rho_t^a for alle t). // aksept randomness åpnes ``` ### 7.4 Verifikator-algoritmen ``` AsymVZK.Verify(pp, C_M, C_{M_d}, y, pi): Step 1 — re-deriver Fiat-Shamir-utfordringer; forkast hvis avvik. Step 2 — for HVER posisjon t (ikke kun utfordrede): a) Kjør M_d lokalt: z_t^d <- M_d(h_{t-1}), med h_{t-1} rekonstruert fra y. b) Verifiser y_t^d = R(z_t^d, rho_t^d). c) Verifiser p_{M_d}(y_t^d) (åpnet av prover) matcher det V nettopp regnet. d) Verifiser aksept/forkast-konsistens: u_t = UniformFromBytes(rho_t^a) expected_a = (u_t <= claimed_p_M / claimed_p_{M_d}) sjekk expected_a == a_t. e) Hvis a_t == 1: sjekk y_t == y_t^d. f) Hvis a_t == 0: tilllitt prover på y_t inntil utfordring (Step 4). Step 3 — for t i S_a (utfordrede aksepter): Verifiser Pi_M-bevis at M(h_{t-1})_t = z_t, og at thr_t >= u_t. Step 4 — for t i S_r (utfordrede forkast): Verifiser Pi_M-bevis at M(h_{t-1})_t = z_t, at thr_t < u_t, og at y_t = R_corr(residual(z_t, z_t^d), rho_t^b). Step 5 — aksepter hvis alle sjekker passerer. ``` Verifikatoren kjører **$L$ runs av $M_d$** (billig — verifikatoren har full lokal tilgang) pluss $k_a + k_r$ runs av $\Pi_M.\mathsf{Verify}$ (raskt, ms-skala). ### 7.5 Sikkerhets­påstander **Påstand 2 (Hybrid soliditet).** La $\varepsilon_a$ være andelen aksepterte posisjoner hvor *prover* løy, $\varepsilon_r$ andelen forkastede. Mot enhver PPT motpart $\mathcal{A}$ med orakel-tilgang til $\mathcal{O}_{M_d}$: $$ \Pr[\mathsf{Verify} = 1 \land (\varepsilon_a > \alpha \lor \varepsilon_r > \beta)] \le T_{\text{grind}} \cdot \left[ (1-\alpha)^{k_a} + (1-\beta)^{k_r} \right] + \mathsf{negl}(\lambda). $$ **Bevisskisse.** Gitt fast utskrift, er $S_a$ uniformt over aksepterte posisjoner og $S_r$ uniformt over forkastede. Hvis $\mathcal{A}$ lyver på fraksjon $> \alpha$ av aksepter, er sannsynligheten for at $S_a$ unngår alle løgner høyst $(1-\alpha)^{k_a}$. Tilsvarende for $\beta$. Union-grense gir summen. Resten følger PSI-LMs argument. ∎ **Påstand 3 (Asymmetrisk nullkunnskap).** Under hiding av $\mathsf{Com}$ og ZK av $\Pi_M$ er AsymVZK-protokollen *asymmetrisk-kunnskap nullkunnskap* med hensyn på $\mathcal{O}_{M_d}$. **Bevisskisse.** Simulatoren $\mathsf{Sim}^{\mathcal{O}_{M_d}}$ har orakel-tilgang til $M_d$. Gitt $(C_M, C_{M_d}, y)$, genererer den: - For hver $t$: en falsk forpliktelse $c_t \leftarrow \mathsf{Com}(0; r_t)$ (bruker hiding). - For hver $t$: simulert draft-randomness $\rho_t^d$ slik at simulatorens kall til $\mathcal{O}_{M_d}$ på den offentlige prefiks gir *logits* hvis topp-token (eller samplet token) matcher $y_t$ når $a_t = 1$, eller en fri token når $a_t = 0$. - For utfordrede posisjoner $t \in S_a \cup S_r$: simulerte $\Pi_M$-bevis via ZK-simulatoren for $\Pi_M$. Utskriften er beregningsmessig uskillelig fra en ekte. Kritisk: simulatorens orakel-tilgang er *nødvendig* — uten den kunne den ikke konstruere konsistent draft-randomness. Verifikatoren har samme orakel-tilgang, så denne asymmetrien er innebygd i trusselmodellen. ∎ ### 7.6 Hva som er skjult og hva som er avslørt | Objekt | Avsl­ørt? | Notat | |---|---|---| | Utdata $y$ | Ja | Offentlig input | | Prompt $p$ | Nei | Skjult inne i $\Pi_M$ ved utfordrede posisjoner | | Stor-modell *logits* $z_t$ for $t \notin S_a \cup S_r$ | Nei | Bare forpliktet | | Stor-modell *logits* ved utfordringer | Ja | Åpnet ved $t \in S$ | | Draft randomness $\rho_t^d$ for alle $t$ | Ja | Nødvendig for V's gjenkjøring av $M_d$ | | Aksept randomness $\rho_t^a$ for alle $t$ | Ja | Nødvendig for V's gjenkjøring av aksept-test | | Resamplings-randomness $\rho_t^b$ for $t \notin S_r$ | Nei | Skjult | | Aksept/forkast-bit $a_t$ | Ja (alle posisjoner) | Offentlig sekvens | | Draft modell $M_d$ | Ja | Offentlig per konstruksjon | | Stor modell $M$ | Nei | Bare $C_M$ | Aksept/forkast-mønsteret $(a_1, \ldots, a_L)$ er en (potensielt sensitiv) lekkasje om prompt-modell-interaksjonen — en motpart som observerer dette mønsteret kan slutte ulike ting om hvor godt $M_d$ matcher $M$ på akkurat denne prompten. Vi diskuterer dette i §9. ### 7.7 Sammenligning mellom soundness-modeller PSI-LMs distributive soliditet er svak mot motparter som lyver på små fraksjoner av posisjoner ($\varepsilon \to 0$). AsymVZKs hybride soliditet har den *samme* svakheten i ren form, men med en viktig praktisk forskjell: - Andelen forkastede posisjoner $\rho_r$ er empirisk 10–20 % for godt-justerte $(M, M_d)$-par. - En semantisk-innholds-motpart som forsøker å manipulere ett spesifikt token har høy sannsynlighet for å trenge å lyve ved en *forkastet* posisjon (fordi forkastede posisjoner er nøyaktig der $M$ og $M_d$ er uenige, og det er der informasjons­tetthet er høy). - Derfor dekker $k_r$ utfordringer over en populasjon på $\sim 0{,}1L$ forkastede posisjoner motparten mye mer effektivt enn PSI-LMs $k$ utfordringer over $L$ posisjoner. Heuristisk er AsymVZKs effektive $\varepsilon$-dekning $\rho_r \times$ bedre enn PSI-LMs ved samme utfordrings­antall. Dette er en *konkret forbedring i adversiell-posisjons-robusthet*, men når ikke kryptografisk-styrke enkelt-token-soliditet. --- ## 8. Eksperiment Vi har implementert PSI-LM som referanse i ren Python (kun standardbibliotek) og AsymVZK som referanse med ekte HuggingFace-modeller (PyTorch + Transformers). Begge er offentlige og reproduserbare. ### 8.1 Modeller For AsymVZK velger vi et reelt, godt-justert modellpar: $M$ = `Qwen/Qwen2.5-1.5B-Instruct` (ca. 1,54 milliarder parametre), $M_d$ = `Qwen/Qwen2.5-0.5B-Instruct` (ca. 494 millioner parametre). Begge modellene er trent av samme team, deler tokenizer (vokabular $V = 151\,936$), og er kjent for å gi god speculative-decoding-aksept (~70 % på generelle tekst­oppgaver). Vi kjører på CPU (single-thread, fp32) fordi vårt mål er å måle protokoll-overheaden, ikke konkurrere med GPU-baserte ZKML-systemer. For PSI-LM bruker vi en lekemodell — en hashbasert pseudo-LLM — for å måle ramme­overhead uten avhengig­heter av store ML-pakker. Dette er hensiktsmessig fordi PSI-LM er modell-uavhengig: protokoll­kostnaden er dominert av SHA-256-hashing og forpliktelses­åpninger. ### 8.2 Aksept-rate på flere prompt-domener For å forstå når AsymVZK gir mest besparelse, måler vi speculative-aksept-raten over fem prompt-domener på Qwen 2.5-1.5B/0.5B-paret ved $L = 64$: | Prompt-tema | Aksept-rate | Forkast-rate | |---|---:|---:| | Forklar nullkunnskapsbevis (to setninger) | 71,9 % | 28,1 % | | Tre vanskeligheter med å verifisere språkmodeller | 70,3 % | 29,7 % | | Engelsk→fransk: «Hello, how are you today?» | 75,0 % | 25,0 % | | Python-funksjon for fakultet | **85,9 %** | 14,1 % | | Forskjell mellom FHE og ZK | 81,2 % | 18,8 % | | **Gjennomsnitt** | **76,9 %** | **23,1 %** | Aksept-raten varierer betydelig med prompt-domene: kode-oppgaver (factorial-funksjonen) gir høyest aksept fordi mye av output er strukturell (whitespace, syntaktiske tokens) hvor draft og stor modell stort sett er enige; ren oversettelse også høyt fordi rutinete­frasen er lett for begge modeller. Generelle resonnement­spørsmål (tre vanskeligheter) gir lavere aksept fordi tokens med høyt informasjons­innhold krever ekspertise fra den større modellen. For en *worst case* (62–66 % aksept observert ved $L = 128$ på enkelte prompts) tilsvarer dette at AsymVZK trenger kryptografiske bevis for ~34–38 % av posisjoner — fortsatt en størrelsesorden mindre enn full-trace zkLLM ville krevd. ### 8.3 Kostnads­sveip — AsymVZK på ekte modeller Vi sveiper $L \in \{16, 32, 64, 128\}$ og $(k_a, k_r) \in \{(2,2), (4,4), (8,8)\}$. Hver målepunkt er gjennomsnitt over flere prompts. Kjøringen skjer på en bærbar CPU; absolutte tall er for å karakterisere protokoll-overhead, ikke for å konkurrere mot GPU-baserte ZKML-systemer. Måltall fra det fullstendige benchmark-sveipet på Qwen 2.5-1.5B + 0.5B (single-thread CPU, fp32): | $L$ | $k_a$ | $k_r$ | Bevistid | Verifikatortid | Aksept | Bevisstørrelse* | |---:|---:|---:|---:|---:|---:|---:| | 16 | 2 | 2 | 10,6 s | 5,1 s | 75 % | 2,4 MB | | 32 | 4 | 4 | 23,6 s | 10,8 s | 81 % | 4,8 MB | | 64 | 4 | 4 | 53,0 s | 20,6 s | 73 % | 4,8 MB | | 64 | 8 | 8 | 52,8 s | 26,0 s | 77 % | 9,5 MB | | 128 | 8 | 8 | 128,4 s | 42,6 s | 66 % | 9,5 MB | *Bevisstørrelsen er stor fordi vår PoC åpner *fulle* logit-vektorer ved utfordrede posisjoner ($V = 151\,936$ Qwen-tokens × 4 bytes ≈ 0,6 MB per åpning). I en produksjons-implementasjon ville $\Pi_M$-bevisene være ~200 KB SNARK-er, som ville gi $L \cdot 32 + (k_a + k_r) \cdot 200$ KB total — typisk under 50 KB ved $L = 64$. Tre observasjoner som matcher konstruksjonens kostnadsanalyse: - **Bevistid skalerer lineært med $L$ og er praktisk talt uavhengig av $k$.** Fra $L = 32$ til $L = 64$ omtrent dobles bevistiden; å gå fra $k_a = k_r = 4$ til $k_a = k_r = 8$ ved fast $L$ endrer ikke bevistiden. Denne uavhengigheten er protokollens viktigste asymptotiske egenskap. - **Verifikatortid skalerer både med $L$ (draft-replay) og med $k$ (konsistens-bevis).** Fra $L = 64, k_a = k_r = 4$ til $k_a = k_r = 8$ øker verifikatortiden fra 20,6 s til 26,0 s — primært fra dobbelt så mange konsistens-bevis-evalueringer, ikke fra draft-replay (som er konstant for fast $L$). - **Aksept-rate er stabil rundt 70–85 %**, med noen variasjon avhengig av prompt og $L$. Bevistid er dominert av plaintext-inferens på CPU, ikke av kryptografi. På en realistisk GPU-drevet implementasjon ville plaintext-inferensen være tusentalls­vis raskere; den interessante komponenten — forpliktelses­bygging — er allerede praktisk talt gratis (~0,3 ms/token). ### 8.4 Empirisk soliditet — hybride deteksjons­rater Vi simulerer en juksende *prover* som bytter ut den faktiske $p_M(y^d)$-verdien på en fraksjon $\varepsilon_a$ av aksepterte posisjoner og en fraksjon $\varepsilon_r$ av forkastede posisjoner, og måler andel av forsøk verifikator avviser. Honest baseline aksepteres alltid (verifisert før sveipen). Hver celle rapportert nedenfor er gjennomsnitt over 12 forsøk på samme prompt, $L = 32$, gjenbrukende én ærlig speculative-decoding-utskrift som basis. | $k_a$ | $k_r$ | $\varepsilon_a$ | $\varepsilon_r$ | Empirisk deteksjon | Teoretisk øvre grense $\Pr[\text{ikke oppdaget}]$ | $n$ tatt / forsøk | |---:|---:|---:|---:|---:|---:|---:| | 4 | 4 | 0,10 | 0,10 | 41,7 % | 131 % (triviell) | 5 / 12 | | 8 | 8 | 0,10 | 0,10 | 41,7 % | 86 % | 5 / 12 | | 4 | 4 | 0,25 | 0,25 | **100,0 %** | 63 % | 12 / 12 | | 8 | 8 | 0,25 | 0,25 | **100,0 %** | 20 % | 12 / 12 | | 4 | 4 | 0,50 | 0,50 | **100,0 %** | 12,5 % | 12 / 12 | | 8 | 8 | 0,50 | 0,50 | **100,0 %** | 0,8 % | 12 / 12 | Tre observasjoner: **Soliditet er sterk ved meningsfulle løgnandeler.** Ved $\varepsilon = 0{,}25$ eller høyere oppdager verifikatoren *enhver* simulert juksing-attempt 12 av 12 ganger, uavhengig av om vi bruker $k_a = k_r = 4$ eller 8. Dette er det praktisk relevante regimet: en motpart som juksker på 25 % eller mer av posisjonene blir alltid oppdaget. **Den teoretiske grensen er konservativ ved små $\varepsilon$.** Ved $\varepsilon = 0{,}10$ gir union-grensen $(1-0{,}1)^4 + (1-0{,}1)^4 = 1{,}31 > 1$, som er triviell (formelen er en øvre grense og kan overstige 1 når den ikke er stram). Empirisk når vi 41,7 %, hvilket er bedre enn det trivielle båndet men svakere enn det vi får ved $\varepsilon \ge 0{,}25$. **«Stille løgner» reduserer empirisk deteksjon ved små $\varepsilon$.** Vår enkle motpart i `_flip_step_to_lie` bruker en *idempotent* mutasjon: den setter $p_M$ til $\max(p_M, 1{,}1 \cdot p_{M_d})$ for aksept-løgner og $\min(p_M, 0{,}5 \cdot p_{M_d})$ for forkast-løgner. Hvis original-honest $p_M$ allerede oppfyller ulikheten (f.eks. $p_M$ var allerede $1{,}3 \cdot p_{M_d}$ ved en honest aksept), er mutasjonen et *no-op* og verifikatoren ser ingen forskjell. En sterkere motpart ville bruke mer aggressive mutasjoner; vår valg er bevisst svak for å gi en *konservativ* måling av distributiv soliditet. I praksis vil semantisk-meningsfulle løgner alltid være ikke-stille, fordi de må endre token-fordelingen markant for å påvirke utdata. Disse målingene viser at AsymVZKs hybride soliditet fungerer som forventet i regimet hvor det betyr noe (motparter som juksker meningsfullt), og degraderer gracefully ved svært små løgnandeler — den fundamentale begrensningen ved sampling-basert verifikasjon, som vi diskuterer i §9.1. ### 8.5 PSI-LM-rammekostnad (fra eget pure-stdlib-PoC) Tabellen nedenfor viser utvalgte rader fra et fullstendig sveip over $L \in \{32, 64, 128, 256, 512, 1024\}$ og $k \in \{1, 4, 16, 32, 64\}$, gjennomsnitt over tre kjøringer per celle. | $L$ | $k$ | Bevistid | Verifikatortid | Bevisst­ørrelse | |---:|---:|---:|---:|---:| | 32 | 1 | 7,7 ms | 0,3 ms | 3,1 KB | | 32 | 32 | 7,5 ms | 8,5 ms | 67,3 KB | | 256 | 16 | 59,1 ms | 4,1 ms | 41,4 KB | | 1024 | 1 | 224,1 ms | 1,7 ms | 35,1 KB | | 1024 | 32 | 224,8 ms | 9,2 ms | 99,2 KB | | 1024 | 64 | 223,1 ms | 17,2 ms | 165,5 KB | Tre observasjoner: - **Bevistid skalerer lineært med $L$ og er praktisk talt uavhengig av $k$.** - **Verifikatortid skalerer lineært med $k$ og er praktisk talt uavhengig av $L$.** - **Bevisstørrelse $\approx O(L \cdot 32 \text{ B}) + O(k \cdot 2 \text{ KB})$.** ### 8.6 PSI-LM empirisk soliditet Tabellen nedenfor viser utvalgte celler fra et sveip over $k \in \{4, 8, 16, 32, 64\}$ og $\varepsilon \in \{0{,}01, 0{,}05, 0{,}10, 0{,}25, 0{,}50\}$: | $k$ | $\varepsilon$ | Empirisk | Teoretisk | |---:|---:|---:|---:| | 4 | 0,01 | 2,0 % | 3,9 % | | 4 | 0,10 | 31,5 % | 34,4 % | | 4 | 0,50 | 93,0 % | 93,8 % | | 16 | 0,05 | 58,0 % | 56,0 % | | 16 | 0,25 | 99,0 % | 99,0 % | | 32 | 0,05 | 83,5 % | 80,6 % | | 32 | 0,50 | 100,0 % | 100,0 % | | 64 | 0,05 | 97,0 % | 96,2 % | Empiriske rater følger den teoretiske $1 - (1-\varepsilon)^k$-grensen til innenfor utvalgsstøy. ### 8.7 Projeksjon: ende-til-ende-kostnad sammen­liknet Vi kombinerer våre måltall med publiserte zkLLM-tall ($T_{\Pi_M} = 15$ minutter per forwardpass for 13B, $T_{\Pi_M\mathsf{V}} = 2$ s, bevisstørrelse 200 KB) for å projisere ende-til-ende-kostnad. For LLaMA-2-13B ved $L = 1024$ tokens og $k = 32$ utfordringer (PSI-LM) eller $k_a = k_r = 16$ (AsymVZK, 32 utfordringer total): | Setting | Plaintext | PSI-LM | AsymVZK | Full-zkLLM autoregr. | |---|---:|---:|---:|---:| | Bevisansvarlig tid | 51 s | 8,0 t | 8,1 t | 256 t (10,7 dager) | | Verifikator tid | 51 s | 64 s | 69 s (5 s draft + 64 s ZK) | 2 048 s (34 min) | | Bevisstørrelse | — | 6,5 MB | 7,2 MB | 200 MB | På bevisansvarlig-siden er PSI-LM og AsymVZK omtrent like — begge dominert av $\Pi_M$-bevis ved utfordrede posisjoner. På verifikator-siden gir AsymVZK et alternativ som PSI-LM ikke har: verifikatoren kjører faktisk en del av modellen (driften), noe som gir konkret semantisk-innholds-soundness-forbedring. Speedup-tallene er dominante: - PSI-LM vs full-zkLLM autoregressiv: $\approx 32\times$ ved $L = 1024$, $k = 32$. - AsymVZK gir samme bevisansvarlig­speedup pluss en kvalitativ forbedring i sikkerhetsmodellen. Ved $L = 4096$: - PSI-LM: 8,1 t vs 1024 t (full-zkLLM) = $127 \times$ speedup. - AsymVZK: tilsvarende speedup pluss bedre semantisk-innholds-deteksjon. ### 8.8 Metodologiske begrensninger Tre begrensninger må flagges eksplisitt: **$\Pi_M$-stubben er ikke nullkunnskap.** Vi har implementert konsistens­sjekken som en re-evaluering av modellen ved utfordrede posisjoner. Dette gir oss målinger av åpning, samplings-kontroll og Fiat–Shamir-rekomputasjon, men ikke kostnadene som ville påløpe en ekte ZK-bevisproduksjon. Disse kostnadene er i stedet substituert inn i §8.7-projeksjonene fra publiserte tall. **Forpliktelser er kun binding (SHA-256), ikke hiding.** En produksjons-implementasjon ville bytte til Pedersen eller KZG. Bytte er mekanisk; protokoll­strukturen endres ikke. **Ingen GPU-akselerasjon.** Single-thread Python på en bærbar CPU. zkLLM, zkGPT og DeepProve er alle GPU-akselererte. Dette påvirker ikke det relative forholdet mellom PSI-LM, AsymVZK og den naive autoregressive sammenstillingen — alle har samme indre $\Pi_M$ — men gjør direkte sammenligning av absolutte tall mot zkLLM upassende. --- ## 9. Diskusjon ### 9.1 Hva konstruksjonene *ikke* beskytter mot **PSI-LM**: - *Adversielt valgte løgnposisjoner*. Soliditet er distributiv over uniforme utfordringer; ikke semantisk. - *Modell-utskifting med sv­ært nær modell*. Hvis $M' \approx M$ er utdataene nært nok til at konsistens­sjekken slipper. - *Grinding-angrep*. Eksplisitt anslag i påstand 1. **AsymVZK** arver alle PSI-LMs begrensninger pluss: - **Aksept/forkast-mønster lekkasje**. $(a_1, \ldots, a_L)$ er offentlig. En motpart som ser dette kan slutte ting om hvor «overraskende» prompten er for $M_d$. - **Krav om delt tokenizer**. $M$ og $M_d$ må dele vokabular. Dette begrenser hvilke modellpar som kan kombineres. - **Krav om aksept-rate $> 0$**. Hvis $M$ og $M_d$ er for ulike, blir alle posisjoner forkastet og AsymVZK degenererer til PSI-LM (med ekstra overhead). Verste tilfelle er ikke katastrofalt. ### 9.2 Akseptmønster-lekkasjen — en analyse Den eneste *nye* lekkasjen AsymVZK introduserer over PSI-LM er aksept/forkast-mønsteret. Vi karakteriserer hva en motpart kan slutte: - **Aksept-rate er en grov mål på prompt-uvanlighet.** Hvis aksept-raten er typisk for domenet (f.eks. 70 % for generell engelsk), avslører det lite. Hvis den er svært lav, kan det indikere at prompten inneholder uvanlig materiale. - **Aksept/forkast-sekvensen i seg selv er en signatur.** Forskjellige prompts med samme $L$ men ulik kompleksitet vil ha ulike sekvenser. En motpart som observerer mange transcripts kan bygge en distribusjonsmodell som tillater statistisk gjenkjenning av prompt-domene. Mitigasjoner (ikke implementert i denne artikkelen): 1. Bruk en sterkere draft-modell (lukker gapet, reduserer lekkasje). 2. Differentially-private noising av aksept-mønsteret (bryter ubiasertet — krever omfattende reanalyse). 3. Forplikt $a_t$ men åpne det kun ved utfordrede posisjoner (gjør protokollen mer interaktiv, koster soliditets-styrke). ### 9.3 Når man bør (og ikke bør) bruke hver konstruksjon **PSI-LM passer når:** - Verifikator har null modell-kunnskap (klassisk ZK-trusselmodell). - Du trenger transferebar verifiserbarhet. - Sekvensen er lang nok til at $L/k$ blir vesentlig. **AsymVZK passer når:** - Du har et godt-justert modellpar med felles tokenizer. - Aksept/forkast-mønster-lekkasjen er akseptabel for anvendelsen. - Verifikator har lokale ressurser til å kjøre en mindre modell. - Du verdsetter semantisk-innholds-soliditet utover ren distributiv. **Ingen av dem passer når:** - Hver enkelt token er sikkerhetskritisk (medisinsk diagnose, juridisk vedtak) — vurder full-trace zkLLM. - $L$ er liten ($L \lesssim k$) — full-trace ZKML er da bedre. - Du allerede har TEE og bare trenger konfidensialitet. ### 9.4 Hva som ville bryte konstruksjonene Tre konkrete angrepsscenarier for AsymVZK: 1. **Fiat–Shamir med adaptiv grinding**: hvis hash-funksjonen $H$ ikke er tilfeldig orakel, kan motparten bryte utfordrings­distribusjonen. Bruk SHA-3 eller Poseidon for produksjon. 2. **Forpliktelses­binding bryter**: kollisjoner i SHA-256 lar motparten åpne forpliktelser inkonsistent. Mot kryptografisk-styrke SHA-256 er dette $\mathsf{negl}$. 3. **$\Pi_M$ er usolid**: hvis konsistens­bevisene for stor-modell-logits er feilaktig akseptert, kollapser hele soliditetsstrukturen. Dette er en risiko for hele ZKML-feltet, ikke spesifikk for AsymVZK. ### 9.5 Sammenligning med andre stakker | Egenskap | FHE | MPC | TEE | Full-trace ZKML | PSI-LM | AsymVZK | |---|---|---|---|---|---|---| | Skjuler input fra server | ✓ | ✓ | ✓ | ofte ✗ | ✗ | ✗ | | Skjuler modell fra klient | svak | ✓ | ✓ | ✓ | ✓ | ✓ | | Tredjepartsverifiserbarhet | ✗ | ✗ | delvis | ✓ | ✓ (probab.) | ✓ (hybrid) | | Frontier-skala autoregressivt 2026 | nei | nei | ja | nei | ja | ja | | Tåler fysiske angrep | ✓ | ✓ | **nei (TEE.fail)** | ✓ | ✓ | ✓ | | Verifikator trenger modell | nei | ja (split) | nei | nei | nei | **ja, liten** | Den siste raden er nøkkelen: AsymVZK gir verifikatoren en *ny* type tilgang som ingen andre stakker krever — en lokalt-kjørbar liten modell. For mange anvendelser (regulatorisk revisjon, on-prem deployment) er dette ikke en byrde men en eksisterende ressurs. --- ## 10. Videre arbeid Fire konkrete fremtidsretninger: **Aksept-mønster-privatliv.** En klar konstruksjon som skjuler aksept-mønsteret ville lukke den ene nye lekkasjen AsymVZK introduserer. Kandidat-teknikker: differential-privacy-stil noising, terskel-kryptert aksept-bit, eller homomorfe kombinasjoner av $a_t$-aggregater. Dette er en åpen kryptografisk problemstilling som vil være et selvstendig papir. **Folding-skjema for autoregressiv komposisjon.** Den naturlige utvidelsen er å bruke et folding-skjema (Nova, HyperNova) til å akkumulere $\Pi_M$-bevis ved hver utfordret posisjon i én enkelt akkumulator, med en endelig SNARK-omsluttning. Dette ville redusere bevisstørrelse og verifikator­tid fra $O(k \cdot s_M)$ til $O(s_M)$. Hovedhindringen er folding-av-lookup-argumenter — et åpent forskningsspørsmål per 2026. **Hierarkisk asymmetri.** Hva om en kjede av modeller $M_d^{(1)} \subset M_d^{(2)} \subset \ldots \subset M$ kunne amortisere verifikasjon over flere draft-tier-nivåer? Dette ville være en hierarkisk versjon hvor verifikator ikke trenger en fast "tier" men kan velge nivå. AKZK-trusselmodellen tillater dette naturlig — orakelet er parametrisk. **Anvendelser utover LLM.** AKZK-rammen er ikke spesifikk for språkmodeller. Hva med: - Verifiserbar federert læring: orakel = forrige rundes globale modell. - Strømmende inferens: orakel = en lavere-tier eller eldre versjon. - Edge-deploy med retracing: orakel = en "rapporteringsmodell" som er lett å kopiere til kanten. Hver av disse er en separat anvendelse av AKZK-rammen. **Distillering som proxy for full inferens.** En annen retning vi vurderte under ideeringen var å bevise inferensen til en mindre destillert student-modell pluss et $\varepsilon$-nærhetssertifikat for at studenten approksimerer lærer-modellen empirisk på en kalibrasjonsfordeling. Dette er ortogonalt til AsymVZK og en separat publiseringsbar tråd. --- ## 12. Konstruksjon 3 — VEWC (semantisk-vektet soliditet) PSI-LM (§6) og AsymVZK (§7) gir betydelig praktisk speedup, men deler en strukturell svakhet: cut-and-choose-soliditet degraderer gracefully bare i $\varepsilon$-fraksjon-regimet. Mot en motpart som lyver på *ett enkelt* semantisk avgjørende token — for eksempel å flippe «ikke» i en medisinsk anbefaling, endre et tall i en juridisk tekst, eller invertere et fortegn i finansiell rådgivning — gir uniform Fiat–Shamir-utfordring deteksjons­sannsynlighet $k/L$, som er svak ved $L \gg k$. VEWC (*Verifiable Entropy-Weighted Challenges*) addresserer dette ved å introdusere (i) en ny adversiell klasse der adversæren har et eksplisitt *semantisk budsjett* målt i bits av Shannon-entropi, (ii) et nytt soliditets­teorem som gir strikt strammere bound i denne klassen, og (iii) en ny primitiv-klasse — *verifiserbare entropi-forpliktelser* — som lar protokollen implementere data-adaptiv utfordrings­distribusjon mens distribusjonen selv er kryptografisk forpliktet. VEWC er den dypeste av våre tre konstruksjoner. Mens PSI-LM og AsymVZK er protokoll-komposisjoner over standard primitiver, introduserer VEWC et nytt teorem og en ny primitiv-klasse. ### 12.1 Den nye adversielle klassen **Definisjon 3 (Semantisk-budsjett-motpart).** En *semantisk-budsjett-motpart* med budsjett $B$ er en PPT motpart som produserer en utskrift med løgnsett $S^* \subseteq [L]$ slik at $$ \sum_{t \in S^*} H_t \ge B, $$ der $H_t = \mathcal{H}(\text{softmax}(z_t))$ er Shannon-entropien ved posisjon $t$. Intuitivt: $B$ måler den *totale semantiske vekten* av løgnene, ikke deres antall. Én løgn ved en posisjon med $H = 5$ bits (modellen valgte mellom $\sim 32$ plausible alternativer) bærer samme «semantiske vekt» som fem løgner ved posisjoner med $H = 1$ bit hver. Motparter hvis semantiske mål er meningsfullt har $B$ over en terskel; motparter med $B \to 0$ er ren støy. ### 12.2 Det nye teoremet **Teorem 1 (Entropi-vektet soliditet).** La $\mathcal{A}_B$ være en semantisk-budsjett-motpart med budsjett $B$. Anta at *prover* forplikter seg til $\{H_t\}$ via et bindende forpliktelses-skjema, verifikatoren trekker $k$ entropi-vektede utfordringer fra distribusjonen $\pi_H(t) = H_t / H_{\text{tot}}$ (der $H_{\text{tot}} = \sum_t H_t$), og ved hver utfordret posisjon verifiserer $\Pi_M$ modell-konsistens. Da: $$ \Pr[\mathsf{Verify} = 1 \;\land\; \mathcal{A}_B \text{ vinner}] \le T_{\text{grind}} \cdot \left(1 - \frac{B}{H_{\text{tot}}}\right)^k + \mathsf{negl}(\lambda). $$ **Bevis.** For hver uavhengig utfordring er sannsynligheten for å unngå $S^*$ høyst $1 - \pi_H(S^*) = 1 - \sum_{t \in S^*} H_t / H_{\text{tot}} \le 1 - B/H_{\text{tot}}$. For $k$ IID utfordringer er den samlede unngåelses­sannsynligheten $(1 - B/H_{\text{tot}})^k$. $T_{\text{grind}}$-faktoren absorberer Fiat–Shamir-grinding. ∎ **Sammenligning med uniform sampling.** Standard cut-and-choose gir $(1 - |S^*|/L)^k$. For semantisk-rike løgner (høy $H_t$ ved løgnposisjoner) er $\sum_{t \in S^*} H_t / |S^*| > H_{\text{avg}}$, så $B/H_{\text{tot}} > |S^*|/L$, så VEWCs bound er **strikt strammere**. **Konkret forbedring.** En motpart som lyver ved én posisjon $t^*$ med $H_{t^*} = 5$ bits, mens $H_{\text{avg}} = 1{,}5$ bits over $L = 100$ posisjoner: - Uniform soliditet: $(1 - 1/100)^k = 0{,}99^k$. Trenger $k \approx 459$ for $2^{-30}$ undetected. - VEWC soliditet: $B/H_{\text{tot}} = 5/(1{,}5 \cdot 100) = 0{,}0333$. $(1 - 0{,}0333)^k = 0{,}967^k$. Trenger $k \approx 137$ for $2^{-30}$ undetected. **3,4× forbedring** i utfordrings­antall for samme soliditets­mål. For høyere-entropi enkelttokens-løgner ($H_{t^*} = 8$) vokser forbedringen proporsjonalt. ### 12.3 Den nye primitiven: verifiserbar entropi-forpliktelse For at VEWC skal være solid må entropi-verdiene $\{H_t\}$ være *bindende* — *prover* kan ikke lyve om dem, ellers blir den entropi-vektede distribusjonen adversielt kontrollert. **Definisjon 4 (Verifiserbar entropi-forpliktelse).** En *verifiserbar entropi-forpliktelse* over simpleksen $\Delta^V$ er en tuppel $(\mathsf{Setup}, \mathsf{CommitH}, \mathsf{ProveH}, \mathsf{VerifyH})$ slik at: - $\mathsf{CommitH}(z; r) \to (C, h)$: gitt logits $z$ og randomness $r$, produserer en forpliktelse $C$ og entropi-verdien $h = \mathcal{H}(\text{softmax}(z))$. - $\mathsf{ProveH}(z, r, h) \to \pi_H$: produserer et bevis at $h = \mathcal{H}(\text{softmax}(z))$ for committed $z$. - $\mathsf{VerifyH}(C, h, \pi_H) \to \{0, 1\}$: verifiserer beviset uten å lære $z$. **Sumcheck-basert konstruksjon (skisse).** For diskret distribusjon $p$ over vokabular av størrelse $V$ er entropien $\mathcal{H}(p) = -\sum_{i=1}^V p_i \log p_i$. Dette er en sum av bivariate funksjoner $f(p_i) = -p_i \log p_i$. Vi kan bevise denne summen lik en påstått $h$ via en sumcheck-protokoll: (i) *prover* forplikter seg til $z$ via et polynomielt forpliktelses-skjema (KZG, FRI eller Pedersen), (ii) *prover* beregner $p_i = \text{softmax}(z)_i$ via lookup-argumenter for eksponential, (iii) *prover* kjører sumcheck på $-\sum_i p_i \log p_i$ med $\log p_i$ levert som sumcheck-vitne via lookup mot en forhåndsberegnet log-tabell, (iv) verifikatoren sjekker sumcheck-utskriften. For PoC-en stubber vi $\mathsf{ProveH}/\mathsf{VerifyH}$ — verifikatoren beregner $H_t$ fra de åpnede logits ved utfordrede posisjoner. Strukturen i konstruksjonen er det vesentlige. ### 12.4 VEWC-protokollen VEWC bygger på AsymVZK med to utvidelser: ``` VEWC.Prove(...): Phase A: speculative decoding (identisk med AsymVZK). Phase B: For hver t = 1..L: H_t <- ShannonEntropy(softmax(z_t)) c_H <- CommitH(z_t; r_H_t) pi_H <- ProveH(z_t, r_H_t, H_t) Phase C — Fiat-Shamir, ENTROPI-VEKTET: transcript <- (..., c_H_1..c_H_L, H_1..H_L, pi_H_1..pi_H_L) weights <- (H_1, ..., H_L) S <- WeightedChallenge(transcript, k, weights) Phase D: åpninger ved utfordrede posisjoner (identisk med AsymVZK). ``` Verifikatoren utfører i tillegg per posisjon: $\mathsf{VerifyH}(c_H_t, H_t, \pi_H_t)$, som gjør entropi-verdiene bindende uten å avsløre underliggende fordelinger. ### 12.5 Empirisk validering på Qwen 3.5 For å empirisk validere Teorem 1 implementerte vi VEWC og kjørte det mot AsymVZKs uniform-utfordring på modellparet **Qwen 3.5-4B + Qwen 3.5-0.8B** (utgitt mars 2026, det nyeste tilgjengelige Qwen 3.5-paret som passer for CPU-inferens). Vi konstruerte tre adversiel­le klasser, alle med en *smart* mutasjon som bevarer aksept/forkast-bit-konsistensen og dermed kun kan oppdages via cut-and-choose-sjekken: 1. *Semantisk-innholds-motpart*: lyver ved posisjonene med høyest entropi (worst case for AsymVZK, best case for VEWC). 2. *Uniform-tilfeldig motpart*: lyver ved tilfeldige posisjoner (uavhengig av entropi). 3. *Lav-entropi-motpart*: lyver ved posisjonene med lavest entropi (worst case for VEWC). **Oppsett.** Prompt «*Explain in two sentences how zero-knowledge proofs apply to language models:*», $L = 48$ tokens, 16 forsøk per (motpart, $k$, protokoll)-celle. Honest baseline ble verifisert å aksepteres for begge protokoller før sveipen. **Entropi-fingeravtrykk på Qwen 3.5-paret:** observerte entropier var sterkt bimodale ($\min = 0{,}00$, gjennomsnitt $= 0{,}15$, $\max = 2{,}30$ bits) med top-3-posisjoner $\{2{,}30; 1{,}26; 0{,}99\}$. Dette mønsteret er typisk for instruksjonstunede LLM-er: de fleste posisjoner er strukturelle eller deterministiske, og semantisk innhold er konsentrert i en liten andel høy-entropi-posisjoner. #### 12.5.1 Hovedresultat: VEWC vs AsymVZK mot semantisk-innholds-motpart | Adversær | $\|S^*\|$ | $k$ | VEWC | AsymVZK uniform | VEWC/AsymVZK | |---|---:|---:|---:|---:|---:| | Semantisk | 1 | 4 | **68,8 %** | 6,2 % | **11,0×** | | Semantisk | 1 | 8 | **93,8 %** | 18,8 % | **5,0×** | | Semantisk | 1 | 16 | **100,0 %** | 25,0 % | **4,0×** | | Semantisk | 2 | 4 | **100,0 %** | 25,0 % | **4,0×** | | Semantisk | 2 | 8 | **100,0 %** | 43,8 % | **2,3×** | Ved $k = 4$ utfordringer mot én enkelt løgn ved den høyeste-entropi-posisjonen oppdager VEWC **68,8 %** av angrep mot AsymVZKs **6,2 %** — over én størrelsesorden bedre. Ved $k = 16$ når VEWC mettet (100 %) mens AsymVZK fortsatt bare når 25 %. Dette er en empirisk demonstrasjon av Teorem 1 på ekte modeller. #### 12.5.2 Kostnaden ved spesialiseringen — VEWCs blinde flekk VEWC er ikke universelt bedre. Mot en motpart som *ikke* korrelerer med høy entropi, snur fordelen: | Adversær | $\|S^*\|$ | $k$ | VEWC | AsymVZK uniform | Vinner | |---|---:|---:|---:|---:|---| | Uniform-tilfeldig | 3 | 8 | 25,0 % | 50,0 % | AsymVZK | | Uniform-tilfeldig | 3 | 16 | 37,5 % | 56,2 % | AsymVZK | | Lav-entropi | 3 | 8 | **0,0 %** | 56,2 % | AsymVZK | | Lav-entropi | 3 | 16 | **0,0 %** | 68,8 % | AsymVZK | Mot en *lav-entropi-motpart* (en som velger å lyve ved nøyaktig de posisjonene VEWC nedprioriterer) er VEWC katastrofalt: den oppdager **null** løgn-forsøk selv ved $k = 16$ utfordringer. Dette er en *forventet* konsekvens av entropi-vekting og bekrefter at VEWCs distribusjon er adversielt manipulerbar når motparten kjenner protokollen og kan velge sine angreps­posisjoner. #### 12.5.3 Avveining og praktisk anbefaling Tabellen viser at VEWC og AsymVZK er *komplementære*, ikke konkurrerende: - **VEWC dominerer** mot semantisk-meningsfulle adversielle angrep — som er det realistiske trusselscenarioet for medisinsk, juridisk og finansiell LLM-bruk. - **AsymVZK uniform dominerer** mot adversier som strategisk velger lav-entropi-posisjoner — et mer fjernt scenario, men ikke umulig hvis motparten har full kunnskap om protokollen. Den praktiske anbefalingen er en **hybrid** der utfordrings­budsjettet $k$ deles mellom entropi-vektede og uniforme utfordringer, f.eks. $k_{\text{w}} = 0{,}7k$ entropi-vektede og $k_{\text{u}} = 0{,}3k$ uniforme. Dette gir VEWCs eksponentielle forbedring mot semantiske angrep mens uniform-andelen sikrer dekning ved lav-entropi-posisjoner. Vi presenterer den fulle hybrid-konstruksjonen som videre arbeid; den er ikke vesentlig forskjellig fra union-bound-soliditeten i AsymVZKs hybride aksept/forkast-splitting (§7.5). I tillegg er det viktig å understreke at i praktisk distribusjon ville **per-posisjons aksept/forkast-konsistens­sjekken** (§7.4 step 2) fange enhver løgn som flipper aksept/forkast-bit, uavhengig av entropi. Det er kun løgner som *bevarer* aksept-bit (som vår «smarte» motpart i §12.5) som krever cut-and-choose for å bli oppdaget, og det er kun på dette restset av angrep at VEWCs entropi-vekting gir mening. ### 12.6 Hva er genuint nytt i VEWC Vi presiserer hva som er nytt og hva som er kjent: **Nytt:** 1. **Semantisk-budsjett-adversiell klasse** (§12.1) er, til vår kunnskap, første formelle definisjon av LLM-ZK adversiell modell som fanger *innholds-vektede* angrep heller enn antalls-vektede. 2. **Teorem 1**: entropi-vektet soliditets-bound. Strikt strammere enn standard cut-and-choose i den nye klassen. Argumentet er en ikke-triviell generalisering av union-bound til ikke-uniforme distribusjoner *under den begrensning at distribusjonen selv må være kryptografisk forpliktet*. 3. **Verifiserbar entropi-forpliktelse** (§12.3) som primitiv-klasse. Selv om entropi er en funksjon av underliggende distribusjon, er *forpliktelse til entropi som førsteklasse-objekt* — og bevis på at entropien er korrekt utledet — en byggekloss vi ikke har sett i litteraturen. 4. **Adaptiv utfordrings­distribusjon** der vektene er kryptografisk forpliktet. Dette er VEWC sin protokoll-strukturelle nyhet. **Ikke nytt:** - De underliggende kryptografiske primitivene (forpliktelser, sumcheck, lookup-argumenter, Fiat–Shamir). - Idéen om probabilistisk ML-verifikasjon (Slalom, sumcheck-litteraturen). - Idéen om at noen posisjoner er viktigere enn andre (informasjons­teori). VEWC sitt bidrag er den formelle koblingen: *bind den ikke-uniforme distribusjonen kryptografisk, slik at adversæren ikke kan manipulere den, og bevis at den ikke-uniforme distribusjonen gir strikt bedre soliditet mot innholds-bevisste angrep.* ### 12.7 Begrensninger og åpne spørsmål **Adversær velger posisjoner.** Hvis adversæren er *fri* til å velge løgnposisjoner kan den deliberativt velge *lav-entropi* posisjoner der VEWCs forbedring forsvinner. Forsvar: kombiner VEWC med AsymVZKs hybrid (aksept/forkast) splittering — semantisk meningsfulle tokens er konsentrert ved *forkastede* posisjoner i speculative decoding (der draft og stor modell er uenige, hvilket også er der entropi tendens til å være høy). **Entropi-lekkasje er ikke-triviell.** Per-posisjon entropi avslører grov informasjon om prompt-modell-interaksjon. Skjuling av entropier mens de holdes forpliktet er et åpent problem; en kandidat er differensielt-personvern-stil noising på $H_t$ før forpliktelse, med tilsvarende justering av soliditets-bound. **Verifiserbare entropi-forpliktelser er ikke-trivielle å bygge.** Sumcheck-vennlig entropi-forpliktelse er mekanisk rutine, men kostnaden er ikke-triviell — omtrent ett $\Pi_M$-bevis per posisjon. For PoC stubber vi dette; produksjons­distribusjon ville trenge optimalisering. --- ## A. Vedlegg: Detaljert sikkerhets­bevis for AsymVZK Vi gjengir her en mer fullstendig versjon av sikkerhets­argumentet for AsymVZK, ut over skissene i §7.5. Denne seksjonen forutsetter at leseren er kjent med standard simulator-baserte ZK-bevis. ### A.1 Påstand 2 — full bevisstruktur Vi viser distributiv hybrid-soliditet: enhver PPT motpart $\mathcal{A}$ med orakel-tilgang til $\mathcal{O}_{M_d}$ kan ikke produsere en aksepterbar utskrift som inkonsistent med $M$ på mer enn en angitt fraksjon av posisjoner uten å bli oppdaget. **Reduksjon.** Anta for kontradiksjon at det finnes en motpart $\mathcal{A}$ som vinner spillet $\mathsf{DistSound}^{\text{hybrid}}$ med ikke-forsvinnende sannsynlighet $\eta$. Vi konstruerer en motpart $\mathcal{B}$ som bryter $\Pi_M$s soundness eller $\mathsf{Com}$s binding. Først: betrakt utskriftens form. $\mathcal{A}$ produserer $(C_M, y, \pi)$ der $\pi$ inneholder forpliktelser $\{c_t\}$, aksept/forkast-mønster $\{a_t\}$, draft- og aksept-randomness, samt åpninger ved utfordrede posisjoner. **Stege 1: ekstraksjon.** Gitt at $\Pi_M$ er en knowledge-extractor-protokoll, kan vi ekstrahere et vitne $w_t^*$ for hvert utfordret $\Pi_M$-bevis. Dette gir oss "påsta(å)tt" $z_t^*$ som $\mathcal{A}$ påstår er $M(h_{t-1})$ ved utfordrede posisjoner. **Stege 2: definisjon av løgn.** En posisjon $t$ er en "løgn" hvis $z_t^*$ er inkonsistent med ekte $M(h_{t-1})$ for det committed $C_M$. La $\varepsilon_a$ være andelen aksepter med løgn, $\varepsilon_r$ andelen forkast med løgn. **Stege 3: utfordrings­dekning.** Fiat–Shamir-utfordringer $S_a$ og $S_r$ er tilfeldige delmengder. Sannsynligheten for at $S_a$ unngår alle aksept-løgner er $\binom{(1-\varepsilon_a) n_a}{k_a} / \binom{n_a}{k_a}$ der $n_a$ er totalt antall aksepter. For $k_a, k_r \ll n_a, n_r$ approksimerer dette $(1-\varepsilon_a)^{k_a}$ via Bernoulli-grensen. Symmetrisk for forkast. **Stege 4: union-grense og grinding.** For $T_{\text{grind}}$ uavhengige forsøk gir $\mathcal{A}$ undetected-rate $\le T_{\text{grind}} \cdot [(1-\varepsilon_a)^{k_a} + (1-\varepsilon_r)^{k_r}]$, pluss $\mathsf{negl}(\lambda)$-bidrag fra $\Pi_M$-soundness og $\mathsf{Com}$-binding. **Stege 5: avslutning.** Hvis $\eta > T_{\text{grind}} \cdot [(1-\alpha)^{k_a} + (1-\beta)^{k_r}] + \mathsf{negl}$ for noen $\alpha, \beta$, da må enten $\Pi_M$ være usolid eller $\mathsf{Com}$ være ikke-binding. Begge motsier antakelsene. ∎ ### A.2 Påstand 3 — full ZK-simulator Vi gir en full simulator $\mathsf{Sim}^{\mathcal{O}_{M_d}}$ for AsymVZK. Simulatoren har orakel-tilgang til $M_d$ men ikke til $M$. ``` Sim^{O_{M_d}}( pp, C_M, C_{M_d}, y, accept_pattern ): # Steg 1: simulert generasjon-sti h <- (epsilon) for t = 1..L: # M_d-orakel: trekker logits z_t^d konsistent med y_t når a_t=1 z_t^d <- O_{M_d}(h) if accept_pattern[t] == 1: # Vi har påstått aksept med output y_t. Velg rho_t^d slik at R(z_t^d, rho_t^d) = y_t. rho_t^d <- find_seed_giving(R(z_t^d, ·) = y_t) # Velg rho_t^a slik at u <= claimed_thr (vi velger thr stort). rho_t^a <- random (uniform, will be opened; effectively forces u <= 1) # Forplikt til (z_t^d, rho_t^d, rho_t^a, _, a_t=1, y_t). else: # Forkast. Vi kan velge enhver rho_t^d (output ikke bundet til draft-utvalg). rho_t^d <- random rho_t^a <- random rho_t^b <- random (used in residual sample) # Forplikt til (random_z_M, rho_t^d, rho_t^a, rho_t^b, a_t=0, y_t^d_chosen). c_t <- Com(0; r_t) # bruk hiding for å skjule innhold h <- h || y_t # Steg 2: simulert utfordring (Fiat-Shamir-derivasjon) transcript <- (...); S_a, S_r <- Challenge(...) # Steg 3: simulerte konsistens-bevis for t i S_a U S_r: pi_M^t <- Sim_{Pi_M}( ... ) # ZK-simulatoren for Pi_M return (C_{M_d}, accept_pattern, c_1..c_L, S_a, S_r, opens, pi_M) ``` **Indistinguishability-argument.** Vi viser via standard hybrid-argumenter at simulator­utskriften er beregningsmessig uskillelig fra en ekte utskrift: - *Hybrid 1*: Erstatt ekte forpliktelser med simulatorens. Skille kan brytes til hiding av $\mathsf{Com}$. - *Hybrid 2*: Erstatt ekte $\Pi_M$-bevis med simulator-genererte. Skille kan brytes til ZK av $\Pi_M$. - *Hybrid 3*: Erstatt ekte $z_t$, $\rho_t^d$, $\rho_t^a$, $\rho_t^b$ med simulatorens. Skille kan brytes til hiding av $\mathsf{Com}$ (siden disse er gjemt utenfor utfordringer) eller til ZK av $\Pi_M$ (siden de er åpnet under ZK-bevis). Til sammen: hvis utskriftene var skillbare, kan vi konstruere en motpart som bryter en av $\mathsf{Com}$-hiding eller $\Pi_M$-ZK. Begge motsier antakelsene. ∎ ### A.3 Hvorfor orakel-tilgang er nødvendig for simulatoren Et naturlig spørsmål: kan vi konstruere en simulator uten $\mathcal{O}_{M_d}$-tilgang? Svaret er nei, og det er nettopp dette som gjør AKZK til en strikt utvidelse. Anta for kontradiksjon at det finnes en simulator $\mathsf{Sim}'$ uten orakel-tilgang. Vi vurderer en setting der $M_d$ er en pseudorandom funksjon (f.eks. en kryptografisk hash anvendt på prefiks). I denne settingen gir $M_d$s utdata på en gitt prefiks ingen informasjon $\mathsf{Sim}'$ kan forhåndsberegne. For at simulatoren skal produsere $z_t^d$ som er konsistent med en realistisk verifikator-forventning, må den invokere $M_d$ — som krever orakel-tilgang. Mer formelt: betrakt en distinguisher $\mathcal{D}$ som har $\mathcal{O}_{M_d}$-tilgang. $\mathcal{D}$ kan kjøre $M_d$ på de offentlige prefikser og sammenligne med simulatorens påståtte $z_t^d$. Hvis $\mathsf{Sim}'$ ikke har orakel-tilgang, kan den ikke konstruere konsistente $z_t^d$, og $\mathcal{D}$ skiller med ikke-forsvinnende sannsynlighet. Konklusjon: orakel-tilgang er fundamentalt nødvendig for simulator-eksistens i AKZK. Dette er hvorfor klassisk ZK ikke fanger den ønskede eiendommen. ### A.4 Begrensninger som angår sikkerhets­modellen Bevisene over forutsetter: - $\Pi_M$ er en knowledge-extractor-protokoll (standard for SNARK-er via straight-line eller rewinding-ekstraksjon). - $\mathsf{Com}$ har computational binding under standard antakelser (DL for Pedersen, kollisjonsresistens for SHA-256). - $H$ er en tilfeldig orakel for Fiat–Shamir-transformasjonen. - Motparten har polynomial regnetid. Mot kvante-motparter (post-quantum) krever vi at $\Pi_M$ og $\mathsf{Com}$ er post-kvante-sikre (f.eks. FRI-baserte STARK-er, gitter-baserte forpliktelser). AsymVZK selv er post-kvante-sikker hvis primitive er det. ### A.5 Konkrete sikkerhets­parametre For en realistisk distribusjon foreslår vi: - $\lambda = 128$ (sikkerhetsparameter). - $T_{\text{grind}} \le 2^{60}$ (cost-bounded motpart). - Ønsket soliditet: $\Pr[\text{undetected}] \le 2^{-30}$. Med disse antakelsene løser ulikheten i påstand 2 til: $$ (1-\alpha)^{k_a} + (1-\beta)^{k_r} \le 2^{-90}. $$ For $\alpha = \beta = 0{,}5$ (50 % løgn-andel): $k_a + k_r \approx 90 / \log_2(2) \approx 90$, dvs. $k_a = k_r = 45$. For $\alpha = \beta = 0{,}1$ (10 % løgn-andel): $k_a + k_r \approx 90 / \log_2(1/0{,}9) \approx 90 / 0{,}152 \approx 593$, dvs. $k_a = k_r \approx 300$. Dette er praktisk gjennom­førbart for $L \in [1000, 10000]$, og er fortsatt en størrelses­orden mindre enn full-trace zkLLM ville kreve. --- ## 11. Konklusjon ZKML-feltet har de siste atten månedene flyttet bevistid for én forwardpass på en transformer fra «umulig» til «25 sekunder for GPT-2, 15 minutter for 13B». Den autoregressive sammenstillings­kostnaden — den faktiske kostnaden for å betjene en LLM-tjeneste — har ikke fulgt med. Naiv komposisjon krever ti dager for et 1000-token-svar på en 13B-modell. Vi har bidratt: 1. **PSI-LM** som en sampling-soundness baseline som dekoblet bevistid fra sekvenslengde, $\sim 32\times$ speedup over naiv full-trace. 2. **Asymmetrisk-kunnskap nullkunnskap (AKZK)** som en ny formell trusselmodell, en streng generalisering av Goldwasser–Micali–Rackoff-rammen. 3. **AsymVZK** som første instansiering av AKZK for autoregressive LLM-er, med kryptografisk forpliktet speculative decoding. Verifikator-arbeid skalerer med uenighet, ikke med sekvenslengde. 4. En **referanseimplementasjon på ekte modeller** — Qwen 2.5-1.5B og Qwen 2.5-0.5B — som validerer at protokollene kjører ende-til-ende og produserer realistiske aksept-rater. Vi tror AKZK-rammen åpner en familie av konstruksjoner utover AsymVZK, og at *posisjonsvis* og *asymmetrisk* nullkunnskap som formelle egenskaper fortjener videre utforsk­ning. Den dypere kryptografiske oppdagelsen som mangler — folding-av-lookups for autoregressiv komposisjon — vil endre hele området når den ankommer. --- ## Referanser - Arun, A., Setty, S., og Thaler, J. (2023). Jolt: SNARKs for Virtual Machines via Lookups. IACR ePrint 2023/1217. - Bünz, B., og Chen, B. (2024). Folding schemes with selector vectors. IACR ePrint. - Chen, C., Borgeaud, S., et al. (2023). Accelerating Large Language Model Decoding with Speculative Sampling. arXiv:2302.01318. - Chen, B-J., Waiwitlikhit, S., Stoica, I., og Kang, D. (2024). ZKML. EuroSys. - Fiat, A., og Shamir, A. (1986). How to Prove Yourself. CRYPTO. - Freivalds, R. (1979). Fast Probabilistic Algorithms. MFCS. - Goldwasser, S., Micali, S., og Rackoff, C. (1989). The Knowledge Complexity of Interactive Proof Systems. SIAM J. Comput. 18(1). - Goldwasser, S., Kalai, Y., og Rothblum, G. (2008). Delegating Computation: Interactive Proofs for Muggles. STOC. - Hao, M. et al. (2024). Scalable Zero-knowledge Proofs for Non-linear Functions in ML. USENIX Security. - Kothapalli, A., Setty, S., og Tzialla, I. (2021). Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. IACR ePrint 2021/370. - Kothapalli, A., og Setty, S. (2023). HyperNova. IACR ePrint 2023/573. - Lagrange Labs (2025). DeepProve-1. - Leviathan, Y., Kalman, M., og Matias, Y. (2023). Fast Inference from Transformers via Speculative Decoding. ICML. - Liu, T., Xie, X., og Zhang, Y. (2021). zkCNN. CCS. - Lund, C., Fortnow, L., Karloff, H., og Nisan, N. (1990). Algebraic Methods for Interactive Proof Systems. STOC. - Polyhedra Network (2025). zkPyTorch. IACR ePrint 2025/535. - Qu, B. et al. (2025). zkGPT. USENIX Security. - Setty, S., Thaler, J., og Wahby, R. (2023). Unlocking the Lookup Singularity with Lasso. IACR ePrint 2023/1216. - South, T. et al. (2024). Verifiable Evaluations of Machine Learning Models with zkSNARKs. arXiv:2402.02675. - Sun, H., Li, J., og Zhang, H. (2024). zkLLM: Zero Knowledge Proofs for Large Language Models. CCS. - Tramèr, F., og Boneh, D. (2019). Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware. ICLR. - Vaswani, A. et al. (2017). Attention Is All You Need. NeurIPS. - Weng, C. et al. (2021). Mystique. USENIX Security. - Anthropic (2025). Confidential Inference Whitepaper. - TEE.fail authors (2025). TEE.fail: Breaking Confidential Computing. - Zama (2024). Hybrid Large Language Models with Concrete-ML. - Touvron, H. et al. (2023). LLaMA-2. arXiv:2307.09288. - Dong, Y. et al. (2023). PUMA: Secure Inference of LLaMA-7B in Five Minutes. arXiv:2307.12533. - Wang et al. (2025). ZK-DeepSeek. arXiv:2511.19902. - Abbaszadeh, K. et al. (2024). Kaizen. IACR ePrint 2024/162. - Qwen Team (2024). Qwen2.5: A Family of Open Foundation Models. https://qwenlm.github.io/blog/qwen2.5/