Nullkunnskapsbevis: En nybegynnerveiledning

Nullkunnskapsbevis (ZKP) er et kraftig kryptografisk verktøy med et bredt spekter av praktiske bruksområder.

I denne artikkelen gir vi en enkel innføring i kjerneprinsippene for nullkunnskapsbevis uten å dykke for dypt ned i kompleks matematikk.

Vi diskuterer de grunnleggende ideene bak ZKP-er, med fokus på de grunnleggende konseptene som oppsto i informatikken på 1980-tallet. (Vi kommer altså ikke til å ta for oss moderne protokoller som ZK-SNARKs og Bulletproofs).

Enten du har støtt på begrepet og ønsker å forstå det bedre, eller om du er nysgjerrig på hvordan nullkunnskapsbevis kan være relevant for arbeidet ditt, er denne veiledningen et godt sted å starte.

Hva er nullkunnskapsbevis?

Nullkunnskapsbevis er en kryptografisk teknikk som gjør det mulig for en part, en såkalt bevisfører, å overbevise en annen part, en verifikator, om at et utsagn er sant, uten å avsløre ytterligere informasjon.

Dette betyr at verifikatoren ikke får vite noe annet enn at utsagnet er sant.

En kort historikk om ZKP-er

Konseptet Zero-Knowledge Proofs ble først introdusert i en banebrytende artikkel publisert i 1985 av forskerne Shafi Goldwasser, Silvio Micali og Charles Rackoff.

For å forstå innovasjonen deres bedre, la oss se på den tradisjonelle oppfatningen av et bevis:

Et bevis bekrefter vanligvis ikke bare sannheten i et utsagn, men avslører også tilleggsinformasjon som viser hvordan sannheten ble etablert.

Tenk deg at du har løst et veldig vanskelig matematisk problem. Du kan vise vennen din løsningen for å bevise at du har løst det, men det ville også avsløre svaret. Finnes det en måte å bevise at du har løst det på uten å avsløre selve løsningen?

Dette leder til et bredere spørsmål:

Er det mulig å bevise sannheten i et utsagn uten å avsløre noe annet enn at utsagnet er sant?

Goldwasser, Micali og Rackoff ga et positivt svar på dette spørsmålet, noe som førte til utviklingen av det vi i dag kjenner som nullkunnskapsbevis.

Siden den gang har ZKP-er utviklet seg fra å være et teoretisk konsept til å finne en rekke praktiske anvendelser, spesielt på områder der personvern og sikkerhet er avgjørende.

Bevis vs. bevis på kunnskap

Nullkunnskapsbevis kalles noen ganger også "nullkunnskapsbevis for kunnskap".

Selv om disse begrepene beskriver beslektede, men teknisk sett forskjellige konsepter, brukes de ofte om hverandre i nyere litteratur.

Strengt tatt er kunnskapsfrie kunnskapsbevis en delmengde av kunnskapsfrie bevis. Men for de fleste praktiske formål refererer vi til bevis der beviseren demonstrerer sin kunnskap om en løsning i stedet for bare å bekrefte at det finnes en løsning.

Når vi i denne artikkelen snakker om nullkunnskapsbevis (ZKP-er), mener vi spesifikt nullkunnskapsbevis for kunnskap.

Forstå ZKP-er gjennom eksempler

La oss illustrere ZKP-er ved hjelp av to eksempler:

1. Å finne Waldo

Tenk deg at du ser på et "Hvor er Waldo?"-puslespill og finner Waldo gjemt i bildet. Du vil bevise for noen andre at du vet hvor Waldo er, men du vil ikke vise den nøyaktige posisjonen hans.

En måte å gjøre dette på er å ta et stort stykke papp og klippe et lite hull i det, akkurat stort nok til å vise Waldo og ikke noe annet. Deretter plasserer du pappen over puslespillet på en slik måte at bare Waldo er synlig gjennom hullet. På denne måten overbeviser du den andre personen om at du vet hvor Waldo er, uten å røpe hvor han befinner seg.

Denne analogien fanger essensen i et nullkunnskapsbevis: Du viser at du vet noe (Waldos posisjon) uten å avsløre selve kunnskapen (Waldos spesifikke posisjon i puslespillet).

2. Fargelegging av grafer

Graf-farging er et klassisk problem i matematikken.

Se for deg en graf bestående av noder (punkter) og kanter (linjer som forbinder punktene): Målet er å fargelegge hver node på en slik måte at ingen to sammenkoblede noder har samme farge, ved hjelp av kun tre farger: Se for deg at du har funnet en gyldig fargelegging for grafen og ønsker å bevise dette for en verifiserende part uten å avsløre de faktiske fargene.

Da kan du skjule hver nodes farge ved å plassere den i en liten konvolutt. Kontrolløren kan nå velge en hvilken som helst kant. Uansett hva de velger, åpner du konvoluttene for de to nodene som er forbundet med den kanten, for å demonstrere at de er farget forskjellig. Selv om kontrolløren kan se at tilstøtende noder har forskjellige farger, får han eller hun ikke vite den generelle fargen på grafen.

Kontrolløren vil imidlertid sannsynligvis forbli skeptisk etter bare ett eller to forsøk. For å overbevise kontrolløren ytterligere, kan du gjenta prosessen flere ganger, og male grafen annerledes hver gang før du avslører fargene på nytt. Denne gjentatte demonstrasjonen overbeviser kontrolløren om at du kjenner løsningen uten å avsløre de faktiske fargene (selv delvis, siden grafen males på nytt hver gang).

Du kan selv oppleve denne prosessen - som kontrollør - med denne interaktive demoen.

La oss nå se på hvordan ZKP-er fungerer i praksis ved å undersøke de viktigste egenskapene deres.

Protokollstrukturen (med tre trekk)

Vi skal se nærmere på en bestemt klasse av nullkunnskapsbevissystemer, kjent som Σ-protokoller (Sigma-protokoller).

Disse protokollene er spesielt effektive og følger en distinkt struktur med tre trekk: forpliktelse, utfordring og svar. Samspillet skjer mellom to dataprogrammer: beviseren og verifikatoren.

1. Forpliktelse (første melding):
   • Beviseren genererer en tilfeldig verdi og bruker den til å skape en forpliktelse . Forpliktelsen avhenger av både den tilfeldige verdien og den hemmelige informasjonen(vitnet).
   • Beviseren sender denne forpliktelsen til kontrolløren.
2. Utfordring (andre melding):
   • Kontrolløren genererer og sender en tilfeldig utfordring til beviseren, og ber beviseren om å åpne noen deler av forpliktelsen.
3. Svar (tredje melding):
   • Beviseren beregner et svar ved hjelp av vitnet , den tilfeldige verdien fra forpliktelsestrinnet og utfordringen som ble gitt av kontrolløren i utfordringstrinnet.
   • Beviseren sender svaret tilbake til kontrolløren, som verifiserer det mot den opprinnelige forpliktelsen og utfordringen for å sikre at det er korrekt.

Du har kanskje lagt merke til at eksemplet med graf-fargelegging fra tidligere passer perfekt til de tre trinnene:

1. Beviseren forplikter seg til en gyldig fargelegging av grafen.
2. Verifikatoren sender en utfordring og ber om fargene på nodene som er knyttet til en bestemt kant.
3. Beviseren svarer med den nødvendige informasjonen.

Hva er en forpliktelse?

Husker du konvoluttene vi brukte til å skjule fargene?

En forpliktelse (eller et forpliktelsesskjema) er en matematisk ekvivalent til disse. En forpliktelse binder beviseren til en bestemt verdi, men holder den skjult for verifikatoren til forpliktelsen åpnes.

Viktige begreper for Σ-protokoller

Interaktivitet

Nullkunnskapsbevis baserer seg vanligvis på en interaktiv utveksling av meldinger mellom den som beviser og den som verifiserer.* Denne interaktiviteten gjør det mulig å overbevise verifisøren om den bevisendes kunnskap trinnvis. Protokollen bør kjøres flere ganger helt til det bare er en ubetydelig sannsynlighet for at beviseren faktisk ikke kjenner hemmeligheten.

Tilfeldigheter

Et annet viktig element er tilfeldighetenes rolle. Verifikatoren stiller en rekke spørsmål, og velger spørsmålene ved hjelp av et elektronisk myntkast.

Dette tilfører tilfeldigheter til hver utfordring, noe som hindrer beviseren i å "forfalske" beviset og sikrer at hver runde av protokollen gir en ny mulighet til å teste bevisernes kunnskap.

Egenskapene til en nullkunnskapsprotokoll

For at et bevissystem formelt skal kunne anerkjennes som nullkunnskap, må det oppfylle tre kriterier:

1. Fullstendighet: Hvis et utsagn er sant, kan en bevisfører som kjenner beviset, overbevise en kontrollør om at det er sant.
2. Soliditet: Hvis et utsagn er usant, kan ingen bevisfører overbevise en verifiserer om at det er sant (unntatt med ubetydelig sannsynlighet).
3. Null-kunnskap: Hvis et utsagn er sant, får verifikatoren ikke vite noe utover det faktum at utsagnet er sant. Beviset avslører ingen ytterligere informasjon om utsagnet.

Mens de to første egenskapene er relativt enkle, er det en stor utfordring å finne en måte å definere nullkjennskap på. Problemet er at det ikke er klart hvordan man skal formalisere begrepet "verifikatoren lærer ingenting" av beviset.

Simulatoralgoritmen

Løsningen kom fra Goldwasser, Micali og Rackoff, og den er veldig interessant.

De argumenterte for at en protokoll kan betraktes som nullkunnskapsbevis hvis det for alle mulige verifikatorer finnes en algoritme som kan fungere som en simulator for nullkunnskapsbeviset. Simulatoren kan generere en utskrift av bevisinteraksjonen som ser ut som et ekte bevis, men uten å kjenne til hemmeligheten.

Merk: Simulatoren er en hypotetisk konstruksjon som brukes i et tankeeksperiment. Den deltar ikke i en normal kjøring av protokollen. Dens eksistens brukes kun til å demonstrere at protokollutskriften ikke avslører noe om hemmeligheten.

Hvordan er dette mulig?

Simulatoren bruker en teknikk som kalles tilbakespoling, som gjør at den kan "gå tilbake" til tidligere stadier av interaksjonen med verifikatoren. For enkelhets skyld kan du tenke på tilbakespoling som å gå tilbake til en tidligere commit i et versjonskontrollsystem som Git.

For å demonstrere tilbakespolingsteknikken, la oss se på hvordan en simulator ville fungert i graffargingsscenarioet:

1. Innledende forpliktelse (til tilfeldige verdier)
   Hvis simulatoren på forhånd vet hvilken kant som skal spørres etter, kan den forplikte seg til tilfeldige forskjellige farger bare på de to nodene i denne kanten - og til dummyverdier andre steder. Dette vil være umulig å skille ut for verifikatoren på grunn av den skjulte egenskapen til forpliktelsesskjemaet. Simulatoren vil derfor gjette hvilken kant som skal spørres etter på forhånd, i håp om at kontrolløren vil spørre etter den aktuelle kanten.
   
   
2. Utfordring og svar
   Kontrolløren utsteder en tilfeldig utfordring. Hvis kontrolløren velger den forventede kanten, åpner simulatoren konvoluttene for de to tilkoblede nodene, og simuleringen av denne iterasjonen er fullført. Hvis ikke, spoles det tilbake.
   
   
3. Spole tilbake og prøve på nytt
   Hvis verifikatorens utfordring ikke stemmer overens med simulatorens prediksjon, spoler simulatoren verifikatoren tilbake til begynnelsen av iterasjonen og prøver på nytt ved å velge en ny tilfeldig kant. Dette gjentas til simulatoren lykkes med å få svaret sitt til å stemme overens med verifikatorens utfordring så mange ganger som nødvendig.

For kontrolløren er simuleringen identisk med en ekte protokollkjøring. I begge tilfeller ser kontrolløren et sett med "konvolutter" og to forskjellige tilfeldige farger som åpnes. Den eneste forskjellen er at det ikke spoles tilbake i et ekte bevis, i motsetning til i simuleringen. Dette er imidlertid ikke tydelig for kontrolløren, og protokollutskriftene ser like ut.

For en mer detaljert og teknisk forklaring - inkludert hvordan det er teknisk mulig å "spole tilbake" kontrolløren, forholdet mellom soliditet og nullvisshet, og hva som kreves for å oppnå neglisjerbar sannsynlighet - anbefaler vi veiledningen om simuleringsbevisteknikken.

Hvorfor er dette viktig?

Tanken her er at det å lage en overbevisende falsk protokollutskrift som ser nøyaktig ut som den ekte - uten åkjenne til hemmeligheten - viserat den ekte protokollutskriften ikke røper noen informasjon om hemmeligheten.

Kontrolløren kan ikke skille mellom et ekte og et simulert bevis, noe som betyr at de ikke får vite noe om selve hemmeligheten, og protokollen er faktisk "nullkunnskap".

*Ikke-interaktive nullkunnskapsbevis

Opprinnelig krevde bevissystemer med nullkunnskapsbevis at den som beviste, og den som verifiserte, utvekslet flere meldinger. Men i noen tilfeller er slik interaktivitet uønsket eller upraktisk.

Dette førte til utviklingen av ikke-interaktive nullkunnskapsbevis (NIZK), Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge(zk-SNARK) og Zero-Knowledge Succinct Transparent Arguments of Knowledge(zk-STARK).

Disse protokollene eliminerer behovet for at beviseren og verifikatoren må være online samtidig, noe som gjør dem mer effektive i visse scenarier. (Men denne effektiviteten kommer med visse kompromisser).

Praktiske anvendelser

Bevis med nullkunnskap kan brukes til langt mer enn graf-farging.

De kan tilpasses ethvert kombinatorisk problem der utfordringen er å bevise kunnskap uten å avsløre den.

Enda viktigere er det at ZKP-er brukes med hell i komplekse scenarier i den virkelige verden på tvers av flere domener:

• Kryptovalutaer og blokkjeder: ZKP-er er mye brukt i kryptovalutaer for å sikre personvern i transaksjoner. For eksempel implementerer personvernfokuserte kryptovalutaer som Zcash ZK-SNARKs for å sikre anonymitet i transaksjoner.
  
  
• Autentiseringssystemer: Tenk på serverautentisering. For å muliggjøre sikker kommunikasjon deler en server sin offentlige nøkkel, mens den hemmelige nøkkelen holdes privat. Før en klient kommuniserer med serveren, kan det være nødvendig å forsikre seg om at den kobler seg til den legitime serveren, og ikke en bedrager. For å gjøre dette ber klienten serveren om å bevise at den kjenner den hemmelige nøkkelen.
  
  
• Digitale signaturer: Schnorr-protokollen er en grunnleggende teknikk for nullkunnskapsbevis som ligger til grunn for mange moderne signaturordninger. EdDSA-signaturfamilien er for eksempel basert på Schnorr og er en nøkkelkomponent i teknologier som OpenSSH, GnuPG og ulike sikre kommunikasjonsprotokoller.
  
  
• Sikker identifikasjon: I digitale identitetssystemer kan ZKP-er brukes til å beskytte brukernes personvern. Tradisjonelle digitale identifikasjonsmetoder krever ofte at enkeltpersoner deler mer informasjon enn nødvendig, noe som eksponerer unødvendige identitetsattributter og kryptografiske detaljer. Med ZKP-er kan enkeltpersoner kun bevise den spesifikke informasjonen som kontrolløren trenger, og minimere eksponeringen av data. BBS/BBS+-signaturer og Camenisch-Lysyanskaya-signaturer er eksempler på ZKP-baserte løsninger som muliggjør identifikasjon som ivaretar personvernet.

ZKP-er og personvern

Nullkunnskapsbevis er i sin natur et ideelt verktøy for å bevise beregningsintegritet uten å avsløre inndata. Med andre ord kan de sikre at en beregning ble utført korrekt og ærlig. Dette gjør ZKP-er spesielt verdifulle i kryptovalutaer, der de er mye brukt.

ZKP-er i seg selv gir ikke fullstendig personvern for digitale interaksjoner. Besluttsomme og ressurssterke aktører kan fortsatt finne måter å reidentifisere og spore brukere på. Men i kombinasjon med andre personvernmekanismer gjør ZKP-er det mye vanskeligere for ondsinnede aktører å få tilgang til personlig eller sensitiv informasjon. Derfor bør ZKP-er brukes som en del av en bredere sikkerhetsstrategi som tar høyde for hele spekteret av potensielle trusler.

Ytterligere lesning

Teorien om nullkunnskapsbevis er langt mer kompleks enn det vi har dekket i denne artikkelen. Her er noen utmerkede ressurser som kan hjelpe deg videre:

Zero Knowledge Proofs: An illustrated primer av Matthew Green: en nybegynnervennlig introduksjon til nullkunnskapsbevis i to deler.

Geoffroy Couteaus doktorgradsavhandling inneholder en enkel oversikt over feltet i de innledende kapitlene 2 og 3.

How To Simulate It - A Tutorial on the Simulation Proof Technique: Selv om del 5 er matematisk tung, gir den en klar forklaring av simulering i en nullkunnskapskontekst.

ZK Basics Cheatsheet - en plakat som tar sikte på å forenkle kjernekonsepter samtidig som den dekker viktige emner, perfekt for de som ønsker en rask, men omfattende oversikt.

En praktisk veiledning for nullkunnskapsbevis: Veileder deg gjennom skriving av grunnleggende kode for å løse et matematisk problem ved hjelp av nullkunnskapsteknikker. Nybegynnervennlig og ideell for deg som har grunnleggende kunnskaper i Python.

Awesome zero knowledge proofs: et GitHub-repository med en liste over ressurser som inkluderer både materiale for nybegynnere og mer avanserte ressurser.