Ezagutza zero proba

Ezagutza zero probak (ingelesez Zero-Knowledge Proof, ZKP) kriptografia arloko protokoloen multzo bat dira. Protokolo hauen bidez, frogatzaile batek (prover) beste alde bati (verifier) baieztapen bat egia dela frogatu ahal dio, baieztapen hori egiaztatzeko beharrezkoa den informazio sekreturik agerian utzi gabe.^[1]

Ezagutza zero proben helburua ez da soilik baieztapen baten egiazkotasuna frogatzea, baizik eta egiaztapena egitean ez ematea informazio gehigarririk. Horregatik, protokolo mota hauek funtsezkoak dira pribatutasuna eta segurtasun informatikoa bermatzen dituzten sistema modernoetan.

Adierazpen baten froga sortu ahal izan beharko litzatekeela kontuan hartuta adierazpenarekin lotutako informazio sekretu jakin bat edukitzean bakarrik, egiaztatzaileak, ezagutza zero froga baten bidez adierazpenaren egiazkotasunaz konbentzitu ondoren ere, ezin izan beharko luke adierazpena hirugarrenei frogatu.

Kontzeptu orokorra

Ezagutza zero frogak probabilitatearen teoria eta konplexutasun konputazionala oinarrian definitzen dira. Protokolo horiek interaktiboak izan daitezke, bi aldeek mezuak trukatzen dituztenean, edo ez-interaktiboak, froga bakar baten bidez egiaztapena egin daitekeenean.

Historia

Ezagutza zero frogak 1980ko hamarkadan definitu zituzten Shafi Goldwasser, Silvio Micali eta Charles Rackoff ikertzaileek. Haien lanek erakutsi zuten posible zela baieztapen matematikoak egiaztatzea informazio sekreturik azaldu gabe, eta, ondorioz, kriptografia modernoaren oinarrietako bat bihurtu ziren.^[1]

Gainera, lehen ezagutza zero froga formala eman zuten arazo zehatz baterako eman zuen: m moduluarekiko hondar ez-koadratikoak erabakitzea. Lan horrek froga-sistema interaktiboen oinarriak ezarri zituen, eta egileek Gödel saria jaso zuten.

Ondoren, ikertzaileek erakutsi zuten elkarreragina gehitzeak frogatzeko behar den informazio-kopurua murriztu zezakeela. Geroago, beste lan batzuek frogatu zuten zenbait NP eta co-NP klaseetako zenbait arazok ezagutza zero frogak dituztela. Are gehiago, Goldreich, Micali eta Wigdersonen lanek erakutsi zuten, zifratze apurtezina edo norabide bakarreko funtzioak existitzen direla onartuz gero, NPko arazo guztiek ezagutza zero frogak izan ditzaketela.^[2]

Ikerketak aurrera egin ahala, frogatu zen IP = PSPACE klaseko arazo guztientzat ere posible direla ezagutza zero frogak, baldintza kriptografiko egokiak betez. Bestalde, hipotesi kriptografikoak saihesteko, frogatzaile anitzeko sistema interaktiboak garatu ziren; sistema horietan NP-ko hizkuntza guztiek ezagutza zero frogak izan ditzakete inolako suposizio konplexurik gabe.

Azkenik, Interneteko inguruneetan aldi berean exekutatzen diren protokoloek erronka berriak sortzen dituztela ikusi zen, eta horrek ezagutza zero frogaren aldaera berriak ekarri zituen, hala nola lekukoaren froga bereizezinak eta ezagutza zero froga ez-interaktiboak. Azken horietan, frogatzaileak eta egiaztatzaileak ausazko kate komun bat partekatzea nahikoa da, elkarreraginik gabe segurtasuna bermatzeko.^[3]^[4]

Adibide intuitiboak

Ali Babaren kobazuloa

Istorioan bi pertsonaiek parte hartzen dute: Peggyk, kobazulo batean ate magiko bat irekitzen duen hitza ezagutzen duena, eta Víctorrek, Peggyk benetan hitz hori ezagutzen duela ziurtatu nahi duenak.

Dilema horri konponbidea emateko, biak ados jarri ziren Peggyren ezagutza egiaztatzeko metodo batean, Peggyk hitza bera adierazi gabe. Peggy kobazuloan sartzen da bi bide posibleetako batetik, ausaz aukeratuta. Ondoren, Víctorrek adierazten dio zein bidetatik itzuli behar duen. Peggyk benetan hitz sekretua ezagutzen badu, atea ireki eta eskatutako bidetik itzuli ahal izango da, Víctorrek hasieran zein bide aukeratu zuen jakin gabe.

Peggyk hitza ezagutzen ez balu, bide zuzena ausaz bakarrik aukeratuko luke soilik, %50eko probabilitatearekin. Prozedura hau behin eta berriz errepikatzeak (adibidez, hogei aldiz) ia ezinezkoa egiten du hitza ez dakien norbaitek arrakasta izatea. Horrela, Víctor ia ziur egon daiteke Peggyk sekretua ezagutzen duela, Peggyk sekretua agerian jarri gabe.

Gainera, adibide honek puntu garrantzitsu bat azpimarratzen du: metodo honek Víctorri bakarrik ematen dio Peggyren ezagutza egiaztatzeko aukera, beste pertsona batzuek ezin dutelako hori egiaztatu edo hitz sekretua ezagutzeko aukerarik izan ere. Honek ezagutza zero frogen funtsa islatzen du: ezagutza modu fidagarrian frogatzea, informazio gehigarririk agerian utzi gabe.

Non dago Wally?

Ezagutza zero frogen beste adibide ezagun bat «Non dago Wally?» izenekoa da. Adibide honetan, frogatzaileak egiaztatzaileari frogatu nahi dio Where’s Wally? liburu bateko orrialde batean Wally non dagoen badakiela, haren kokapena zehazki adierazi gabe.^[5]

Horretarako, frogatzaileak panel beltz handi bat erabiltzen du, Wallyren tamainako zulo txiki batekin. Panela liburua baino handiagoa da alde guztietatik, horrela egiaztatzaileak ez dezan ikusi orriaren zein zatitan jartzen den. Ondoren, frogatzaileak panela orrialdearen gainean jartzen du, Wally zuloaren barruan geratzen den moduan.

Egiaztatzaileak zulotik begiratzean Wally ikus dezake, baina ezin du orrialdeko gainerako ezer ikusi. Horrela, frogatzaileak erakusten du Wally non dagoen badakiela, haren kokapenari buruzko informazio gehigarririk eman gabe.

Hala ere, adibide hau ez da ezagutza zero froga perfektua, frogatzaileak informazio apur bat ematen duelako, hala nola Wallyren gorputzaren orientazioa edo zati batzuk. Dena den, ezagutza zero frogen oinarrizko ideia ulertzeko adibide egokia eta intuitiboa da.

Beste adibide klasiko bat

Beste adibide batean, kolore desberdineko bi pilotak erabiltzen dira. Lagun bat kolore-itsua dela suposatuta, frogatu nahi zaio pilotak desberdinak direla, baina zein kolore duten adierazi gabe. Iterazio ugari egin ondoren, lagunak probabilitate handiarekin ondoriozta dezake pilotak ez direla berdinak, inolako informazio zehatzik jaso gabe.

Definizio formala

Ezagutza zero frogek hiru propietate nagusi bete behar dituzte:

Osotasuna (completeness): baieztapena egiazkoa bada eta protokoloa behar bezala exekutatzen bada, egiaztatzaileak frogatzailea sinetsi behar du.
Irmotasuna (soundness): baieztapena faltsua bada, ezinezkoa izan behar da egiaztatzaile zintzo bat engainatzea, salbu eta probabilitate oso txiki batekin.
Ezagutza zero (zero-knowledge): egiaztatzaileak ez du baieztapenaren egiazkotasunaz haratago inolako informazio sekreturik eskuratu behar.

Propietate hauek probabilitatearen teoria eta konplexutasun konputazionalaren bidez definitzen eta frogatzen dira.

Ezagutza zero frogak ez dira froga matematikoak termino klasikoan, probabilitate txiki bat dagoelako, —sendotasun errorea— frogatzaile iruzurgile batek baieztapen faltsu bati buruz egiaztatzailea konbentzitzeko. Hau da, ezagutza zero frogak froga probabilistikoak dira, eta ez demostrazioak. Hala ere, badira teknikak sendotasun-errorea nahi bezain txikia bihurtzeko (adibidez, ehun edo mila erabaki bitarren gainean asmatzeak, hurrenez hurren 1/2¹⁰⁰ edo 1/2¹⁰⁰⁰ eko sendotasun-errorea du). Iterazio kopurua handitzen den heinean, sendotasun errorea zero aldera hurbiltzen da.

Ezagutza zero frogen motak

Froga interaktiboak

Ezagutza zero froga interaktiboetan, frogatzaileak eta egiaztatzaileak mezuak trukatzen dituzte protokoloaren hainbat pausotan. Pausu horiek, normalean, erronka eta erantzun egituran antolatzen dira, frogatzaileak sekretua benetan ezagutzen duela frogatzeko.

Froga ez-interaktiboak

Ezagutza zero froga ez-interaktiboetan, frogatzaileak mezu bakar bat sortzen du, eta egiaztatzaileak modu independentean egiaztatzen du. Horrelako frogak sortzeko ohikoa da Fiat–Shamir heuristika erabiltzea, froga interaktiboak froga ez-interaktibo bihurtzeko.^[6]

Aplikazioak

Ezagutza zero frogek gaur egun aplikazio ugari dituzte informatikaren eta kriptografiaren arloan.

Autentifikazio-sistema seguruetan: erabiltzaile batek pasahitz edo gako kriptografiko bat ezagutzen duela frogatu dezake, informazio hori bera agerian utzi gabe.^[7]
Bloke-kateetan eta kriptomonetetan: transakzioak baliozkotzeko erabiltzen dira, datu sentikorrak partekatu gabe, hala nola zk-SNARK eta zk-STARK sistemetan.^[8]
Pribatutasuna bermatzen duten protokoloetan: identitatea eta datu pertsonalak babesteko mekanismoetan erabiltzen dira, informazioaren esposizioa minimizatuz.^[9]

Web3 eta eskalagarritasuna

Web3 arkitekturetan, ezagutza zero frogek sareen eskalagarritasuna eta eraginkortasuna hobetzen dituzte, egiaztapen-prozesuak optimizatuz eta, aldi berean, pribatutasuna mantenduz

Ezagutza zero sistemen segurtasun ahuleziak

Ezagutza zero frogak informazioa modu seguruan egiaztatzeko tresna indartsuak diren arren, horiek inplementatzen dituzten zirkuitu aritmetikoak arreta handiz diseinatu behar dira. Zirkuitu horiek murrizketa nahikorik ez badute, segurtasun-ahulezia sotil baina larriak sor daitezke.

Sistema horietan ohikoenetako ahulezietako bat logika azpimurriztua (ingelesez, underconstrained logic). Kasu horretan, murrizketa eskasek aukera ematen diote frogatzaile gaizto bati baieztapen oker baterako froga sortzeko, egiaztapena gainditzen badu ere. 2024an egindako eraso ezagunen sistematizazio batek erakutsi zuen SNARKetan oinarritutako sistemetako zirkuitu-mailan dokumentatutako akatsen %96 inguru zirkuitu azpimurriztuek eragindakoak zirela. ^[10]

Ahulezia horiek maiz sortzen dira maila altuko logika maila baxuko murrizketa-sistemetara itzultzean, bereziki Circom edo Gnark bezalako domeinu espezifikoko lengoaiak erabiltzen direnean. Ikerketa berriek erakutsi dute determinismoaren frogapen formala egiteak —hau da, zirkuitu baten irteerak sarreretan soilik oinarrituta daudela bermatzeak— ahulezia mota osoak ezabatu ditzakeela.^[11]

Erreferentziak

1 2 Goldwasser, S.; Micali, S.; Rackoff, C. (1989). The Knowledge Complexity of Interactive Proof Systems^{[Betiko hautsitako esteka]}. SIAM Journal on Computing.
↑ Goldreich, Oded (1985). «A zero-knowledge proof that a two-prime moduli is not a Blum integer^{[Betiko hautsitako esteka]}». Unpublished manuscript.
↑ Blum, Manuel; Feldman, Paul; Micali, Silvio (1988). «Non-interactive zero-knowledge and its applications». Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing.
↑ Wu, Huixin; Wang, Feng (2014). «A Survey of Noninteractive Zero Knowledge Proof System and Its Applications». The Scientific World Journal, 2014, Article ID 560484. doi:10.1155/2014/560484. PMID 24883407
↑ Murtagh, Jack (2023ko uztailaren 1a). «Where’s Wally? How to Mathematically Prove You Found Him without Revealing Where He Is^{[Betiko hautsitako esteka]}». Scientific American.
↑ Fiat, A.; Shamir, A. (1986). How to Prove Yourself: Practical Solutions to Identification and Signature Problems. Advances in Cryptology – CRYPTO.
↑ Goldreich, O. (2001). Foundations of Cryptography, Volume 1. Cambridge University Press.
↑ Ethereum Foundation. Zero-Knowledge Proofs.
↑ Agencia Española de Protección de Datos. Pruebas de conocimiento cero y privacidad.
↑ Chaliasos, Stefanos; Ernstberger, Jens; Theodore, David; Wong, David; Jahanara, Mohammad; Livshits, Benjamin (2024). «SoK: What Don’t We Know? Understanding Security Vulnerabilities in SNARKs». Proceedings of the 33rd USENIX Security Symposium (SEC ’24), 3855–3872. ISBN 978-1-939133-44-1.
↑ Pailoor, Shankara; Chen, Yanju; Wang, Franklyn; Rodríguez, Clara; Van Geffen, Jacob; Morton, Jason; Chu, Michael; Gu, Brian; Feng, Yu; Dillig, Işıl (2023). «Automated Detection of Under-Constrained Circuits in Zero-Knowledge Proofs». Proceedings of the ACM on Programming Languages, 7, 1510–1532. doi:10.1145/3591282.

Ikus, baita

[Goldwasser1989-1] 1 2 Goldwasser, S.; Micali, S.; Rackoff, C. (1989). The Knowledge Complexity of Interactive Proof Systems^{[Betiko hautsitako esteka]}. SIAM Journal on Computing.

[2] Goldreich, Oded (1985). «A zero-knowledge proof that a two-prime moduli is not a Blum integer^{[Betiko hautsitako esteka]}». Unpublished manuscript.

[3] Blum, Manuel; Feldman, Paul; Micali, Silvio (1988). «Non-interactive zero-knowledge and its applications». Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing.

[4] Wu, Huixin; Wang, Feng (2014). «A Survey of Noninteractive Zero Knowledge Proof System and Its Applications». The Scientific World Journal, 2014, Article ID 560484. doi:10.1155/2014/560484. PMID 24883407

[5] Murtagh, Jack (2023ko uztailaren 1a). «Where’s Wally? How to Mathematically Prove You Found Him without Revealing Where He Is^{[Betiko hautsitako esteka]}». Scientific American.

[FiatShamir1986-6] Fiat, A.; Shamir, A. (1986). How to Prove Yourself: Practical Solutions to Identification and Signature Problems. Advances in Cryptology – CRYPTO.

[GoldreichBook-7] Goldreich, O. (2001). Foundations of Cryptography, Volume 1. Cambridge University Press.

[EthereumZKP-8] Ethereum Foundation. Zero-Knowledge Proofs.

[AEPDZKP-9] Agencia Española de Protección de Datos. Pruebas de conocimiento cero y privacidad.

[10] Chaliasos, Stefanos; Ernstberger, Jens; Theodore, David; Wong, David; Jahanara, Mohammad; Livshits, Benjamin (2024). «SoK: What Don’t We Know? Understanding Security Vulnerabilities in SNARKs». Proceedings of the 33rd USENIX Security Symposium (SEC ’24), 3855–3872. ISBN 978-1-939133-44-1.

[11] Pailoor, Shankara; Chen, Yanju; Wang, Franklyn; Rodríguez, Clara; Van Geffen, Jacob; Morton, Jason; Chu, Michael; Gu, Brian; Feng, Yu; Dillig, Işıl (2023). «Automated Detection of Under-Constrained Circuits in Zero-Knowledge Proofs». Proceedings of the ACM on Programming Languages, 7, 1510–1532. doi:10.1145/3591282.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]