Zero-Knowledge Proofs: En guide för nybörjare

Zero-Knowledge Proofs (ZKP), också känt som nollkunskapsbevis, är kraftfulla kryptografiska verktyg med ett brett spektrum av praktiska tillämpningar.

I den här artikeln ger vi en enkel introduktion till de grundläggande principerna för nollkunskapsbevis utan att dyka för djupt in i komplex matematik.

Vi kommer att diskutera de grundläggande idéerna bakom nollkunskapsbevis, med fokus på de grundläggande begrepp som har sitt ursprung i datavetenskap på 1980-talet. (Så vi kommer inte att täcka moderna protokoll som ZK-SNARKs och Bulletproofs.)

Oavsett om du har stött på termen och vill förstå den bättre eller är nyfiken på hur nollkunskapsbevis kan vara relevanta för ditt arbete, är den här guiden ett bra ställe att börja.

Vad är nollkunskapsbevis?

Nollkunskapsbevis är en kryptografisk teknik som gör det möjligt för en part, en så kallad bevisare, att övertyga en annan part, en verifierare, om att ett påstående är sant utan att avslöja någon ytterligare information.

Detta innebär att verifieraren inte lär sig något annat än att påståendet är sant.

En kort historik över nollkunskapsbevis

Begreppet Zero-Knowledge Proofs introducerades först i en banbrytande artikel som publicerades 1985 av forskarna Shafi Goldwasser, Silvio Micali och Charles Rackoff.

För att bättre förstå deras innovation, låt oss överväga den traditionella uppfattningen om ett bevis:

Ett bevis bekräftar inte bara sanningshalten i ett påstående, utan innehåller också ytterligare information som visar hur sanningshalten har fastställts.

Föreställ dig att du har löst ett mycket svårt matematiskt problem. Du skulle kunna visa din vän lösningen för att bevisa att du har löst det, men det skulle också avslöja svaret. Finns det ett sätt att bevisa att du har löst det utan att avslöja själva lösningen?

Detta leder till en bredare fråga:

Är det möjligt att bevisa att ett påstående är sant utan att avslöja något annat än att påståendet är sant?

Goldwasser, Micali och Rackoff gav ett positivt svar på den frågan, vilket ledde till utvecklingen av vad vi nu känner som nollkunskapsbevis.

Sedan dess har ZKP utvecklats från ett teoretiskt koncept till att hitta många praktiska tillämpningar, särskilt inom områden där integritet och säkerhet är kritiska.

Bevis vs. bevis på kunskap

Nollkunskapsbevis kallas ibland också för "nollkunskapsbevis för kunskap".

Även om dessa termer beskriver relaterade men tekniskt olika koncept används de ofta synonymt i nyare litteratur.

Strängt taget är nollkunskapsbevis för kunskap en delmängd av nollkunskapsbevis. Men för de flesta praktiska ändamål, när vi talar om nollkunskapsbevis, hänvisar vi till bevis där bevisaren demonstrerar sin kunskap om en lösning snarare än att bara bekräfta att en lösning finns.

I den här artikeln, när vi hänvisar till nollkunskapsbevis (ZKP), menar vi specifikt nollkunskapsbevis för kunskap.

Förstå ZKP genom exempel

Låt oss illustrera ZKP:er med hjälp av två exempel:

1. Att hitta Waldo

Föreställ dig att du tittar på ett "Var är Waldo?"-pussel och hittar Waldo gömd i bilden. Du vill bevisa för någon annan att du vet var Waldo är, men du vill inte visa hans exakta plats.

Ett sätt att göra detta är att ta en stor bit kartong och klippa ett litet hål i den, precis tillräckligt stort för att visa Waldo och inget annat. Sedan placerar du kartongen över pusslet på ett sådant sätt att bara Waldo syns genom hålet. På så sätt övertygar du den andra personen om att du vet var Waldo befinner sig utan att avslöja hans position.

Den här analogin fångar kärnan i ett nollkunskapsbevis: Du visar att du vet något (var Waldo befinner sig) utan att avslöja själva kunskapen (Waldos specifika position i pusslet).

2. Färgläggning av grafer

Graffärgning är ett klassiskt problem inom matematiken.

Föreställ dig en graf som består av noder (punkter) och kanter (linjer som förbinder punkterna): Målet är att färglägga varje nod på ett sådant sätt att inga två anslutna noder har samma färg, med hjälp av endast tre färger: Föreställ dig att du har hittat en giltig färgläggning för grafen och vill bevisa detta för en verifierare utan att avslöja de faktiska färgerna.

För att göra det kan du dölja varje nods färg från vyn genom att placera den i ett litet kuvert. Verifieraren kan nu välja vilken kant de vill. Oavsett vad de väljer öppnar du kuverten för de två noderna som är anslutna av den kanten för att visa att de är färgade på olika sätt. Även om kontrollanten kan se att angränsande noder har olika färger, lär han sig inte grafens övergripande färg.

Men verifieraren skulle sannolikt förbli skeptisk efter bara ett eller två försök. För att ytterligare övertyga verifieraren skulle du upprepa processen flera gånger och måla om grafen på olika sätt varje gång innan du avslöjar färgerna igen. Denna upprepade demonstration övertygar kontrollanten om att du känner till lösningen utan att någonsin avslöja de faktiska färgerna (inte ens delvis, eftersom grafen målas om varje gång).

Du kan själv uppleva den här processen - som kontrollant - med den här interaktiva demonstrationen.

Låt oss nu titta på hur ZKP:er fungerar i praktiken genom att undersöka deras viktigaste egenskaper.

Protokollstrukturen (med tre drag)

Vi kommer att diskutera en specifik klass av bevissystem med nollkunskap som kallas Σ-protokoll (Sigma-protokoll).

Dessa protokoll är särskilt effektiva och följer en distinkt struktur med tre steg: åtagande, utmaning och svar. Interaktionen sker mellan två datorprogram: bevisaren och verifieraren.

1. Åtagande (första meddelandet):
   • Bevisaren genererar ett slumpmässigt värde och använder det för att skapa ett åtagande . Åtagandet är beroende av både det slumpmässiga värdet och den hemliga informationen(vittnet).
   • Bevisaren skickar detta åtagande till verifieraren.
2. Utmaning (andra meddelandet):
   • Verifieraren genererar och skickar en slumpmässig utmaning till bevisaren, där bevisaren ombeds att öppna vissa delar av åtagandet.
3. Svar (tredje meddelandet):
   • Provaren beräknar ett svar med hjälp av vittnet , det slumpmässiga värdet från åtagandesteget och utmaningen från verifieraren i utmaningssteget.
   • Bevisaren skickar tillbaka svaret till verifieraren, som verifierar det mot det ursprungliga åtagandet och utmaningen för att säkerställa att det är korrekt.

Du kanske har insett att graffärgningsexemplet från tidigare passar perfekt in i de tre stegen:

1. Bevisaren åtar sig att färga grafen på ett giltigt sätt.
2. Verifieraren skickar en utmaning och ber om färgerna på de noder som är associerade med en specifik kant.
3. Provaren svarar med den information som krävs.

Vad är ett åtagande?

Kommer du ihåg kuverten som vi använde för att dölja färgerna?

Ett åtagande (eller ett åtagandeschema) är en matematisk motsvarighet till dessa. Ett åtagande binder bevisaren till ett specifikt värde, men håller det dolt för verifieraren tills åtagandet öppnas.

Viktiga begrepp för Σ-protokoll

Interaktivitet

Nollkunskapsbevis förlitar sig vanligtvis på ett interaktivt utbyte av meddelanden mellan bevisaren och verifieraren.* Protokollets interaktiva natur gör det möjligt att stegvis övertyga verifieraren om bevisarens kunskap. Protokollet bör köras flera gånger tills det bara finns en försumbar sannolikhet för att bevisaren faktiskt inte känner till hemligheten.

Slumpmässighet

Ett annat viktigt element är slumpens roll. Verifieraren ställer en serie frågor och väljer frågorna genom en elektronisk motsvarighet till att singla slant.

På så sätt blir varje utmaning slumpmässig, vilket hindrar bevisaren från att helt enkelt "fejka" beviset och säkerställer att varje omgång av protokollet ger en ny möjlighet att testa bevisarens kunskaper.

Egenskaperna hos ett protokoll med nollkunskap

För att ett bevissystem formellt ska kunna erkännas som nollkunskap måste det uppfylla tre kriterier:

1. Fullständighet: Om ett påstående är sant kan en bevisare som känner till beviset övertyga en verifierare om att det är sant.
2. Sundhet: Om ett påstående är falskt kan ingen bevisare övertyga en verifierare om att det är sant (utom med försumbar sannolikhet).
3. Nollkunskap: Om ett påstående är sant, lär sig verifieraren ingenting utöver det faktum att påståendet är sant. Beviset avslöjar ingen ytterligare information om påståendet.

Medan de två första egenskaperna är relativt okomplicerade är det en verklig utmaning att hitta ett sätt att formellt definiera nollkunskap. Problemet är att det inte är klart hur man formaliserar begreppet "verifieraren lär sig ingenting" från beviset.

Simulatoralgoritmen

Lösningen kom från Goldwasser, Micali och Rackoff, och den är mycket intressant.

De hävdade att ett protokoll kan betraktas som nollkunskap om det för varje möjlig verifierare finns en algoritm som kan fungera som en simulator för nollkunskapsbeviset. Simulatorn kan generera en utskrift av bevisinteraktionen som inte går att skilja från ett riktigt bevis, men utan att faktiskt känna till hemligheten.

Obs: Simulatorn är en hypotetisk konstruktion som används i ett tankeexperiment. Den deltar faktiskt inte i en normal körning av protokollet. Dess existens används endast för att visa att protokollutskriften inte avslöjar något om hemligheten.

Hur är detta möjligt?

Simulatorn använder en teknik som kallas återspolning, vilket gör att den kan "återbesöka" tidigare stadier av interaktionen med verifieraren. För enkelhetens skull kan man tänka sig att spola tillbaka på samma sätt som att gå tillbaka till en tidigare commit i ett versionskontrollsystem som Git.

För att demonstrera tekniken med återspolning ska vi titta på hur en simulator skulle fungera i scenariot med graffärgning:

1. Initialt åtagande (till slumpmässiga värden)
   Om simulatorn i förväg känner till den kant som ska efterfrågas kan den åta sig att slumpmässigt välja olika färger endast på de två noderna i den kanten - och på dummyvärden på andra ställen. Detta kommer inte att kunna särskiljas för verifieraren på grund av den dolda egenskapen hos åtagandeschemat. Simulatorn kommer därför helt enkelt att upprepade gånger gissa vilken kant som ska frågas i förväg i hopp om att kontrollanten kommer att fråga efter den kanten.
   
   
2. Utmaning och svar
   Kontrollören utfärdar en slumpmässig utmaning. Om kontrollanten väljer den förväntade kanten öppnar simulatorn kuverten för de två anslutna noderna och simuleringen av denna iteration är klar. Om så inte är fallet görs en återspolning.
   
   
3. Spola tillbaka och försök på nytt
   Om kontrollantens utmaning inte stämmer överens med simulatorns förutsägelse spolar simulatorn tillbaka kontrollanten till början av iterationen och försöker igen genom att välja en ny slumpmässig kant. Detta upprepas tills simulatorn lyckas anpassa sitt svar till kontrollantens utmaning så många gånger som krävs.

För verifieraren är simuleringen identisk med en verklig protokollkörning. I båda fallen ser kontrollanten hur en uppsättning "kuvert" med två olika slumpmässiga färger öppnas. Den enda skillnaden är att ingen återspolning sker i ett verkligt bevis, till skillnad från i simuleringen. Detta är dock inte uppenbart för kontrollanten, och protokollutskrifterna ser likadana ut.

För en mer detaljerad och teknisk förklaring - inklusive hur det är möjligt att tekniskt "spola tillbaka" verifieraren, förhållandet mellan riktighet och nollkunskap och vad som krävs för att uppnå försumbar sannolikhet - rekommenderar vi handledningen om simuleringsbevisteknik.

Varför är detta viktigt?

Tanken här är att om man skapar en övertygande falsk protokollutskrift som ser exakt likadan ut som den riktiga - utan attkänna till hemligheten - visardet att den riktiga protokollutskriften inte avslöjar någon information om hemligheten.

Verifieraren kan inte skilja mellan ett riktigt bevis och ett simulerat bevis, vilket innebär att de inte lär sig något om själva hemligheten och protokollet är verkligen "zero-knowledge".

*Icke-interaktiva nollkunskapsbevis

Ursprungligen krävde bevissystem med nollkunskap att en bevisare och en verifierare utväxlade flera meddelanden. I vissa scenarier är dock sådan interaktivitet oönskad eller opraktisk.

Detta ledde till utvecklingen av icke-interaktiva bevis för nollkunskap (NIZK), kortfattade icke-interaktiva kunskapsargument för nollkunskap (zk-SNARK) och kortfattade transparenta kunskapsargument för nollkunskap (zk-STARK).

Dessa protokoll eliminerar behovet av att bevisaren och verifieraren är online samtidigt, vilket gör dem mer effektiva i vissa scenarier. (Men denna effektivitet kommer med vissa kompromisser).

Praktiska tillämpningar

Tillämpningar av nollkunskapsbevis sträcker sig långt bortom graffärgning.

De kan anpassas till alla kombinatoriska problem där utmaningen är att bevisa kunskap utan att avslöja den.

Ännu viktigare är att ZKP:er framgångsrikt används i komplexa scenarier i verkligheten inom flera olika domäner:

• Kryptovalutor och blockkedjor: ZKP:er används ofta i kryptovalutor för att säkerställa transaktioners integritet. Till exempel implementerar integritetsfokuserade kryptovalutor som Zcash ZK-SNARKs för att ge anonymitet i transaktioner.
  
  
• System för autentisering: Tänk på serverautentisering. För att möjliggöra säker kommunikation delar en server med sig av sin publika nyckel samtidigt som den hemliga nyckeln hålls privat. Innan en klient interagerar med servern kan den behöva försäkra sig om att den ansluter till den legitima servern och inte till en bedragare. För att göra detta ber klienten servern att utföra ett nollkunskapsbevis på att den känner till den hemliga nyckeln.
  
  
• Digitala signaturer: Schnorr-protokollet är en grundläggande teknik för nollkunskapsbevis som ligger till grund för många moderna signaturscheman. EdDSA-signaturfamiljen är till exempel baserad på Schnorr och är en viktig komponent i tekniker som OpenSSH, GnuPG och olika säkra kommunikationsprotokoll.
  
  
• Säker identifiering: I digitala identitetssystem kan ZKP:er användas för att skydda användarnas integritet. Traditionella digitala identifieringsmetoder kräver ofta att individer delar med sig av mer information än nödvändigt, vilket innebär att onödiga identitetsattribut och kryptografiska detaljer avslöjas. Med ZKP:er kan individer endast bevisa den specifika information som verifieraren behöver och minimera exponeringen av data. BBS/BBS+-signaturer och Camenisch-Lysyanskaya-signaturer är exempel på ZKP-baserade lösningar som möjliggör integritetsskyddande identifiering.

ZKP:er och integritet

Till sin natur är nollkunskapsbevis ett idealiskt verktyg för att bevisa beräkningsintegritet utan att avslöja indata. Med andra ord kan de säkerställa att en beräkning har utförts korrekt och ärligt. Detta gör ZKP:er särskilt värdefulla i kryptovalutor, där de används i stor utsträckning.

ZKP:er i sig ger inte fullständig integritet för digitala interaktioner. Beslutsamma och resursstarka aktörer kan fortfarande hitta sätt att återidentifiera och spåra användare. Men i kombination med andra integritetsskyddande mekanismer gör ZKP:er det mycket svårare för illasinnade aktörer att komma åt personlig eller känslig information. Därför bör ZKP:er användas som en del av en bredare säkerhetsstrategi som tar hänsyn till hela spektrumet av potentiella hot.

Ytterligare läsning

Teorin om nollkunskapsbevis är mycket mer komplex än vad vi behandlade i den här artikeln. Här är några utmärkta resurser som kan vägleda dig vidare:

Zero Knowledge Proofs: An illustrated primer av Matthew Green: en nybörjarvänlig introduktion till nollkunskapsbevis i två delar.

Geoffroy Couteaus doktorsavhandling innehåller en enkel översikt över området i de inledande kapitlen 2 och 3.

How To Simulate It - A Tutorial on the Simulation Proof Technique: även om det är matematiskt tungt, ger del 5 en tydlig förklaring av simulering i ett nollkunskapssammanhang.

ZK Basics Cheatsheet en affisch som syftar till att förenkla kärnkoncept samtidigt som den täcker väsentliga ämnen, perfekt för dem som vill ha en snabb men ändå omfattande översikt.

En praktisk handledning för nollkunskapsbevis: Guider dig genom att skriva grundläggande kod för att lösa ett matematiskt problem med hjälp av nollkunskapstekniker. Nybörjarvänlig och perfekt för dem som har grundläggande kunskaper i Python.

Awesome zero knowledge proofs: ett GitHub-förvar med en lista över resurser som innehåller både material för nybörjare och mer avancerade resurser.