ZKP-intuition: Ali Babas grotte

Et nulvidensbevis (ZKP) gør det muligt for en beviser at overbevise en verifikator om, at vedkommende kender en hemmelighed (eller at et udsagn er sandt) uden at afsløre selve hemmeligheden. Tre egenskaber: fuldstændighed, sundhed og nulviden.

Hvis beviseren kender hemmeligheden, kan vedkommende altid overbevise verifikatoren. En ærlig beviser, der følger protokollen, lykkes med sandsynlighed 1 (eller overvældende sandsynlighed). Verifikatoren vil ikke afvise et gyldigt bevis.

En beviser, der snyder (og ikke kender hemmeligheden), kan kun overbevise verifikatoren med ubetydelig sandsynlighed. Hver interaktionsrunde reducerer sandsynligheden for snyd — efter k runder: højst 2^{-k} sandsynlighed for succes for en snyder.

Verifikatoren lærer intet ud over, at udsagnet er sandt. Formelt findes der en simulator, som uden at kende hemmeligheden producerer en protokoludskrift, der ikke kan skelnes fra en ægte interaktion mellem beviser og verifikator. Verifikatoren opnår ingen yderligere viden.

En hule har en ringformet passage med en magisk dør i midten. Beviseren (Alice) hævder, at hun kender adgangskoden. Verifikatoren (Bob) venter udenfor. Alice går ind og går til venstre eller højre. Bob råber, hvilken side hun skal komme ud af. Hvis Alice kender adgangskoden, kommer hun altid korrekt ud. Sandsynligheden for snyd pr. runde: 1/2.

Efter 20 runder lykkes det en snyder med sandsynligheden 2^{-20} ≈ 1 ud af en million. Alice (som kender adgangskoden) lykkes hver gang. Bob lærer aldrig adgangskoden — han ser kun Alice komme ud fra den ønskede side. Dette er nulviden.

Interaktive nulvidensbeviser kræver en udveksling frem og tilbage mellem beviser og verifikator. Ikke-interaktive nulvidensbeviser (NIZK'er) bruger Fiat-Shamir-transformationen: Erstat verifikatorens tilfældige udfordring med en hash af forpligtelsen (hash = tilfældigt orakel). Det frembringer en enkelt bevisstreng, som alle kan verificere.

Et ZKP er et vidensbevis (PoK), hvis beviserens strategi indebærer, at vedkommende kunne udtrække hemmeligheden. Det er stærkere end blot at bevise, at et udsagn er sandt. ECDSA- og Schnorr-signaturer er ikke-interaktive vidensbeviser for kendskab til den private nøgle.

Adgangskodegodkendelse uden at sende adgangskoden. Aldersverificering uden at afsløre fødselsdatoen. Intervalbeviser (din løn ligger inden for et interval) uden at afsløre lønnen. Blockchain: Bevis, at du kender en gyldig transaktion, uden at afsløre transaktionen.

Perfekt nulviden: simulatorens output er identisk med den virkelige protokoludskrift. Statistisk ZK: kan ikke skelnes fra den virkelige protokoludskrift bortset fra med negligerbar sandsynlighed. Beregningsmæssig ZK: kan ikke skelnes fra den virkelige protokoludskrift af verifikatorer, der kører i polynomiel tid. Svagere garantier = mere effektive beviser.

Grotten er en protokol med 3 trin: forpligtelse → udfordring → svar. Den kaldes formelt en Sigma-protokol. De fleste praktiske ZKP'er (Schnorr, Pedersen, Fiat-Shamir) er Sigma-protokoller eller sammensætninger af dem. Navnet kommer fra formen Σ i diagrammet over meddelelsesflowet.

ZKP'er beviser kendskab til en hemmelighed uden at afsløre den. Tre egenskaber: fuldstændighed, sundhed og nulviden. Ali Baba-grotten illustrerer en interaktiv ZKP. Næste emne: Sigma-protokoller og Schnorr-identifikation.