Aloittelijan opas nollatietotodistuksiin

Nollatietotodistukset (Zero-Knowledge Proofs, ZKPs) ovat tehokkaita kryptografisia menetelmiä, joilla on laaja kirjo käytännön sovelluksia. Tämä artikkeli sopii niin nollatietotodistuksiin ensi kertaa tutustuvalle kuin lukijalle, joka haluaa ymmärtää niiden toimintaperiaatteita ja käytännön sovelluksia syvällisemmin.

(Keskitymme nollatietotodistusten perusteisiin emmekä käsittele uudempia protokollia, kuten zk-SNARKeja tai Bulletproofs-protokollia.)

Mitä nollatietotodistukset ovat?

Nollatietotodistus on kryptografinen menetelmä, jonka avulla yksi osapuoli, todistaja (prover), voi vakuuttaa toiselle osapuolelle, todentajalle (verifier), että jokin väite on tosi paljastamatta samalla mitään muuta tietoa. Toisin sanoen todentaja saa tietää ainoastaan sen, että tietty väite pitää paikkansa.

Esimerkiksi verkkopalvelu voi varmistaa käyttäjän täysi-ikäisyyden ilman, että hänen syntymäaikaansa tai muita henkilötietojaan tarvitsee paljastaa. Tämän mahdollistaa taustalla toimiva nollatietotodistusprotokolla, jolla palvelu voi varmistua väitteen oikeellisuudesta saamatta tietoonsa mitään ylimääräistä.

Nollatietotodistus ei siis ole fyysinen tai digitaalinen ”todistus” sanan perinteisessä merkityksessä, vaan viittaa puhtaasti kryptografiseen menetelmään.

Nollatietotodistusten lyhyt historia

Nollatietotodistusten käsite esiteltiin ensimmäisen kerran vuonna 1985 tutkijoiden Shafi Goldwasserin, Silvio Micalin ja Charles Rackoffin julkaisemassa uraauurtavassa tutkimusartikkelissa.

Ymmärtääksemme heidän innovaationsa merkityksen on hyvä tarkastella ensin perinteistä käsitystä todistamisesta:

Tavallisesti todiste ei ainoastaan vahvista jonkun väitteen olevan tosi, vaan samalla myös paljastaa, miksi tai miten väite voidaan osoittaa oikeaksi. Kuvitellaan esimerkiksi, että olet ratkaissut erittäin vaikean matemaattisen ongelman. Voisit näyttää ratkaisun ystävällesi todistaaksesi, että todella ratkaisit sen. Samalla kuitenkin paljastaisit itse ratkaisun.

Voisiko olla olemassa tapa todistaa ongelman ratkaiseminen ilman, että itse ratkaisu paljastuu? Tämä johtaa vielä perustavanlaatuisempaan kysymykseen:

“Voiko väitteen oikeellisuuden todistaa paljastamatta mitään muuta kuin sen, että väite on tosi?”

Goldwasser, Micali ja Rackoff osoittivat, että vastaus tähän kysymykseen on kyllä. Tämä oivallus johti nollatietotodisteiden kehittämiseen.

Sittemmin nollatietotodisteet ovat kehittyneet puhtaasti teoreettisesta tutkimusaiheesta teknologioiksi, joilla on lukuisia käytännön sovelluksia erityisesti sellaisilla aloilla, joilla yksityisyydensuoja ja tietoturva ovat keskiössä.

Muutamia esimerkkejä

Nollatietotodistusten periaatteita on usein helpointa havainnollistaa esimerkein. Tarkastellaan seuraavaksi kahta klassista esimerkkiä.

1. Waldon (tai "Vallun") etsiminen kuvasta

Kuvitellaan, että olet ratkaisemassa Where’s Waldo -kuva-arvoitusta, ja onnistut kuin onnistutkin löytämään "Vallun" kuvasta. Haluat todistaa toiselle henkilölle löytäneesi Vallun, mutta et halua paljastaa, missä hän tarkalleen ottaen on.

Yksi tapa tehdä tämä on ottaa suuri pahvinpala ja leikata siihen pieni aukko, joka on juuri sen kokoinen, että Vallu näkyy sen läpi, mutta mikään muu osa kuvasta ei paljastu. Kun asetat pahvin kuvan päälle siten, että aukosta näkyy vain Vallu, voit vakuuttaa toiselle henkilölle tietäväsi hänen sijaintinsa paljastamatta sitä.

Tämä vertaus kuvaa hyvin nollatietotodistuksen perusajatusta: voit osoittaa tietäväsi jotakin – tässä tapauksessa Vallun sijainnin – paljastamatta itse tietoa.

2. Graafin väritys

Graafin väritys  Graafin väritys on klassinen matematiikan ja tietojenkäsittelytieteen ongelma, jota käytetään usein havainnollistamaan myös nollatietotodistusten toimintaa. Tarkastellaan oheista graafia eli kuviota, joka koostuu solmuista (pisteistä) ja särmistä (solmuja yhdistävistä viivoista). 

Tavoitteena on värittää jokainen solmu käyttäen vain kolmea väriä siten, että mitkään kaksi toisiinsa yhdistettyä solmua eivät ole samanvärisiä:

Nyt olet ratkaissut kuvion väritysongelman ja haluat todistaa sen todentajalle paljastamatta kuitenkaan itse värejä.

Voit tehdä tämän piilottamalla jokaisen solmun värin pieneen kirjekuoreen. Todentaja saa tämän jälkeen valita vapaasti minkä tahansa särmän. Valinnasta riippumatta avaat kyseisen viivan yhdistämien kahden solmun kirjekuoret ja osoitat, että niiden värit ovat keskenään erilaiset.

Näin todentaja voi varmistua siitä, että vierekkäiset solmut ovat erivärisiä, mutta hän ei saa tietoonsa kuvion koko väritystä.

Todentaja tuskin kuitenkaan vakuuttuu vielä yhden tai kahden tarkistuksen perusteella. Luottamuksen lisäämiseksi sama menettely toistetaan useita kertoja. Ennen jokaista kierrosta kuvio väritetään uudelleen satunnaisesti samoja sääntöjä noudattaen, minkä jälkeen todentaja valitsee jälleen tarkistettavan kaaren.

Toistuvien tarkistusten myötä todentaja vakuuttuu siitä, että tunnet graafin oikean värityksen, vaikka yksittäisten solmujen todellisia värejä ei koskaan paljasteta. Koska väritys vaihtuu jokaisella kierroksella, todentaja ei voi myöskään yhdistää eri kierroksilla näkemiään värejä toisiinsa ja päätellä graafin alkuperäistä väritystä.

Nollatietotodistukset käytännössä

Nollatietotodistusten käyttö ei rajoitu matematiikan esimerkkitehtäviin, vaan niitä hyödynnetään jo monissa käytännön sovelluksissa. Kuten todettua, erityisen hyödyllisiä ne ovat tilanteissa, joissa jokin tieto täytyy pystyä todistamaan paljastamatta itse tietoa. Niitä hyödynnetään esimerkiksi näillä aloilla ja osa-alueilla:

Sähköinen tunnistautuminen

Digitaalisissa identiteettijärjestelmissä nollatietotodistukset mahdollistavat henkilöllisyyden tai yksittäisten ominaisuuksien todistamisen ilman tarpeettomien henkilötietojen luovuttamista. Käyttäjä voi esimerkiksi todistaa olevansa täysi-ikäinen, opiskelija tai tietyn organisaation jäsen ilman, että hänen tarvitsee jakaa syntymäaikaansa, henkilötunnustaan tai muita asiaan liittymättömiä henkilötietojaan. Tämä perustuu niin sanottuun tietojen minimointiin sekä valikoivaan jakamiseen, jotka ovat myös GDPR:n keskeisiä periaatteita.

Digitaaliset identiteettilompakot

Nollatietotodistuksilla on keskeinen rooli myös tulevissa digitaalisissa identiteettilompakoissa, kuten EU:n digitaalisessa identiteettilompakossa (EUDI Wallet). Sen sijaan, että käyttäjä jakaisi koko digitaalisen henkilökorttinsa tai ajokorttinsa, hän voi todistaa vain sen tiedon, jonka palvelu tarvitsee. Käyttäen aiempaa esimerkkiä, verkkokauppa voi varmistaa asiakkaan olevan täysi-ikäinen tai oikeutettu tiettyyn alennukseen saamatta tietoonsa hänen syntymäaikaansa.

Lohkoketjut ja kryptovaluutat

Lohkoketjuteknologioissa nollatietotodistuksia käytetään erityisesti yksityisyyden suojaamiseen. Ne mahdollistavat esimerkiksi sen todistamisen, että siirto on kelvollinen, ilman että tapahtuman kaikkia yksityiskohtia tarvitsee paljastaa. Tunnettu esimerkki tästä on Zcash-kryptovaluutta, joka hyödyntää zk-SNARK-nollatietotodistuksia käyttäjien anonymiteetin suojaamiseen.

Tietoturva ja palveluiden todentaminen

Nollatietotodistuksia voidaan käyttää myös palvelinten ja muiden järjestelmien todentamiseen. Esimerkiksi palvelin voi osoittaa hallitsevansa salaisen avaimensa paljastamatta itse avainta. Näin käyttäjä voi varmistua siitä, että hän on yhteydessä oikeaan palveluun eikä hyökkääjän ylläpitämään palvelimeen.

Nollatietotodistukset ja yksityisyydensuoja

Nollatietotodistuksetkaan eivät yksin takaa täydellistä yksityisyydensuojaa. Vaikka nollatietotodistus ei paljasta itse salassa pidettävää tietoa, käyttäjä voidaan joissakin tilanteissa pyrkiä tunnistamaan esimerkiksi metatietojen, liikennetietojen tai muiden epäsuorien tunnistetietojen perusteella. Tämä ei ole yksinkertaista ja vaatii usein hyökkääjältä poikkeuksellisia resursseja sekä määrätietoisuutta.

Yhdistettynä muihin yksityisyyttä vahvistaviin teknologioihin nollatietotodistukset muodostavat kuitenkin tehokkaan keinon vähentää henkilötietojen tarpeetonta jakamista ja vaikeuttaa arkaluonteisten tietojen väärinkäyttöä. Siksi niitä pidetään yhtenä lupaavimmista teknologioista tulevaisuuden digitaalisen identiteetin ja yksityisyydensuojan kehittämisessä.

Aiheesta lisää

Olemme tässä artikkelissa vain raapaisseet nollatietotodistusten teorian pintaa. Tästä erittäin monimutkaisesta aiheesta kiinnostuneelle löytyy onneksi runsaasti lisäluettavaa. Voit esimerkiksi aloittaa tämän artikkelin englanninkielisestä versiosta, jossa syvennytään aiheen teoriaan perusteellisemmin. Sen lisäksi voit tutustua muun muassa seuraaviin syväluotaavampiin kirjoituksiin:

Zero Knowledge Proofs: An illustrated primer by Matthew Green: aloittejille soveltuva kaksiosainen opas.

Geoffroy Couteaun väitöskirja tarjoaa syvennystä aiheeseen.

How To Simulate It – A Tutorial on the Simulation Proof Technique: matematiikkapainotteinen, mutta perusteellinen opas.

ZK Basics Cheatsheet kattava ja perusteellinen yleiskatsaus.

A Hands-On Tutorial for Zero-Knowledge Proofs: Auttaa alkuun käytännössä.

Awesome zero knowledge proofs: kattava kirjasto, josta löytyy jotain sekä aloittelijoille että alan asiantuntijoille.