Vad är Zero Knowledge Proof?

Zero Knowledge Proof (nollkunskapsbevis på svenska) är ett begrepp inom kryptografi som lanserades 1985 via den vetenskapliga artikeln ”The Knowledge complexity of interactive proof system”.  Det är den definition som används i denna artikel som fortfarande används idag. 

Kortfattat så innebär det att en part (bevisaren) kan bevisa för någon annan (verifieraren) att ett påstående är sant men utan att avslöja någon annan information utöver detta påstående.   

Det skulle det kunna vara att en person vill sälja en digital värdekod till någon annan. Skulle värdekoden visas upp kan den stjälas. Samtidigt vill köparen vara säker på att värdekoden verkligen finns och har den funktion som anges. Hur kan säljaren (bevisaren) bevisa att den har informationen utan att ge ut denna information till köparen (verifieraren)?

Ett nollkunskapsbevis eller nollkunskapsprotokoll är, inom kryptografi, ett sätt att bevisa ett sant påstående utan att avslöja någon information utöver faktumet att påståendet är sant. / Wikipedia.org

Exempel – Grottan och dörren

En av de vanligaste och enklaste liknelserna, som används för att förklara zero-knowledge proof, är berättelsen om Ali Babas magiska grotta. Sagoberättelsen publicerades 1990 av bland annat Jean-Jacques Quisquater och har titeln ”How to explain zero-knowledge protocols to your children”. Hela sagan kan laddas hem i PDF-format här. 

I denna saga ska Peggy bevisa för Victor att hon har det hemliga lösenordet som kan låsa upp innerdörren i grottan (se bild nedan). Hon vill däremot inte säga lösenordet till honom. Hon behöver därför bevisa att hennes påstående är sant (att hon har lösenordet) utan att ge Victor någon annan information. De löser detta på följande sätt:

Viktor (V) vänder sig om och Peggy (P) går in i grottan, antingen via väg A eller väg B, för att komma fram till innerdörren. Victor har nu ingen kunskap om vilken väg hon gick in. 

Nästa steg är att Victor ropar A eller B och önskar därmed att Peggy ska komma ut den angivna vägen. Om Peggy gått in via väg A och Victor ropar A kan hon gå tillbaka samma väg som hon kom in utan att ha öppnat dörren. Ropar han B är hon tvungen att öppna dörren för att kunna gå denna väg. 

Det är alltså 50 % chans att hon behöver använda sitt hemliga lösenord. Så för att säkerställa att hon verkligen har gjort det genomför Peggy och Victor denna övning 10 gånger. Nu är det mindre än 0,1% chans att Peggy lyckats gått in den väg som Victor sedan ropar att hon ska komma ut. 

Efter tio försök känner Victor sig säker på att Peggy kan lösenordet. Detta eftersom hon alltid kommit ut den väg som han ropat. Han vet att hon har en viss information utan att hon behövt visa upp denna information. Victor har inte heller fått någon annan kunskap än beviset på att hon har lösenordet. Han vet inte vilken väg hon gick in, om lösenordet är ett ord eller ett tal eller ens hur den magiska dörren såg ut. 

Bara Victor som vet

I detta fall är Victor övertygad om att Peggy har rätt lösenord. Han har däremot ingen information som han kan använda för att övertyga sin vän, Peter, om detta. Med andra ord är det bara den som har informationen (Peggy) som kan bevisa det för någon annan. Även denna funktion är viktig inom zero-knowledge proof. 

Finns en risk…

Hur många kontrollfrågor som Victor än säger så kommer det alltså finnas en viss risk att Peggy valt samma ingång som Victor sedan ropar att hon ska komma ut ifrån. Med zero-knowledge proof finns alltså en risk är att bevisaren kan gissa sig fram till rätt resultat. Men genom att öka antalet tester minskas risken succesivt till att bli så försumbar att beviset anses vara trovärdigt.  

Tre krav

För att det ska klassas som zero-knowledge proof måste alltid de tre punkterna som presenteras nedan vara uppfyllda. 

• Fullständigt

Den som verifierar kunskapen behöver bli fullständigt övertygad om att bevisaren har den information som den anger sig ha tillgång till. Detta förutsatt att bevisaren agerar ärligt. 

• Sunt

Som visas i exemplet ovan kan bevisaren inte till 100% bevisa att den har tillgång till informationen. Däremot kan det, via ett flertal tester, uppnås en sannolikhet som är mycket stor. Att beviset ska vara sunt innebär därmed att sannolikheten att bevisaren bara har lyckats gissa rätt är försumbar. 

• Nollkunskapligt

Nollkunskaplighet betyder att verifierande part inte får någon annan information än att bevisaren har angiven information. 

Non-interactive zero-knowledge proof

I exemplet ovan måste Victor och Peggy interagera för att Victor ska bli övertygad om att Peggy har den information som hon utger sig för att ha tillgång till. Det är knappast en praktisk lösning då Victor behöver komma till grottan, vilket även gäller för alla andra som Peggy önskar bevisa detta för. 

En lösning på det problemet är non-interactive zero-knowledge proof. Kortfattat är detta en lösning som innebär att interaktion inte måste ske direkt mellan parterna. Informationen går istället via algoritmer som enbart dessa parter har tillgång till. 

Zero Knowledge som skalningsfunktion  

Zero-knowledge proof används för flera funktioner på olika blockkedjor. Bland annat kan tekniken användas för skala upp en blockkedja så att fler transaktioner kan hanteras utan att vare sig säkerhet eller funktion påverkas.  Ett exempel är ZkRoll-ups som bland används på blockkedjan BNB via sidokedjan, och second-layer solution, zkBNB.

Underlag för transaktioner på BNB kan hanteras och valideras på zkBNB och sedan ”paketeras” och skickas tillbaka till BNB. I samband med att all information skickas till BNB bifogas kryptografiskt bevis som anger att uträkningarna är korrekta. Det innebär att uträkningarna inte behöver visas upp i dess helhet. I detta fall är zkBNB bevisaren och BNB den som verifierar beviset. För att jämföra mot exemplet ovan är zkBNB Peggy medan BNB är Victor. 

Liknande funktioner finns exempelvis på Ethereum där noder, som validerar transaktioner off-chain, använder zero-knowledge proof för att bevisa att transaktionerna är korrekta. Detta i samband med att de överförs till Ethereum och publiceras på denna blockkedja. Det kryptografiska bevis som noderna i detta fall använder kallas för ”validity proof”.