Lovász László, az Abel-díj és a kriptovaluták: hogyan működik a nulla ismeretű bizonyítás elve és mi köze van ennek a magyar matematikushoz?

Múlt héten nagy elismerésben volt része Lovász László magyar matematikusnak: egy meglepetés Zoom hívás során tudta meg ugyanis, hogy 2021-ben ő és izraeli kollégája, a Princetonon kutató Ali Wigderson kapja meg az Abel-díjat. A köztudatban csak matematikai Nobel-díjként elhíresült kitüntetést „az elméleti számítógép-tudomány és a diszkrét matematika területén elért kimagasló szerepükért” kapták.

És hogy ez miért is olyan fontos a kriptoközösség számára? Erre egyszerű a válasz: mert az említett tudományterületek egyik legérdekesebb kérdése a nulla ismeretű bizonyítás (zero knowledge proof, továbbiakban ZKP), amely a számítógépes adatvédelem mellett számos kriptovalutának képezi alapvető működési elvét. A legnépszerűbb privátcoinok, például a zcash vagy a monero működése például teljesen elképzelhetetlen lenne a ZKP elvének kidolgozása nélkül.

Nézzük is meg közelebbről, hogy pontosan mit is takar ez a téma. Senki ne ijedjen meg, a nagyon komplex matematikai háttérbe azért nem fogunk hosszasan elmélyedni – ehelyett egy rövid elméleti áttekintést szeretnénk adni az érdeklődőknek.

A zero knowledge proof: úgy igazolni egy állítást, hogy valójában semmit sem árulunk el róla

A matematika szerint (sőt, ha már itt tartunk, szinte az összes tudományág és még a mindennapi életünk szerint is) ahhoz, hogy igazolni tudjunk egy állítást, valamiféle bizonyítékot kell felmutatnunk. Nem hiszel Pitagorasz tételében vagy éppen az evolúcióban? A bizonyítékok mind ott vannak, készen arra, hogy igazolják a tudományos állításokat. De mi van akkor, ha ennek nem kell mindig igaznak lennie? Mi van akkor, ha azt mondjuk, igazolni tudjuk azt, hogy ismerjük X értékét, anélkül, hogy valóban el kellene mondanunk, hogy mennyi is pontosan X?

Bár elsőre ez lehetetlennek és szinte egy ellentmondásnak tűnik, a valóságban számtalan megoldási lehetőséget láthatunk ezekre a problémákra, amely során teljesül a nulla ismeret kitétele.

Hol van Waldo? – Az egyik leghíresebb ZKP példa

Az egyik leghíresebb példa a Hol van Waldo? játékhoz kapcsolódik. Biztosan sokan belefutottunk már a népszerű piros-fehér csíkos rajzolt figurába, de aki esetleg nem ismerné a játékot, annak sincs oka az aggodalomra. A lényeg egy mondatban ennyi: egy sűrűn, különböző, színes figurákkal telerajzolt képen a rajzoló elrejti Waldo-t, egy piros és fehér csíkos pulóvert viselő fiút, akit a játékban résztvevőknek minél hamarabb meg kell találniuk.

Lovász László, az Abel-díj és a kriptovaluták: hogyan működik a nulla ismeretű bizonyítás elve és mi köze van ennek a magyar matematikushoz?

Most képzeljük el azt, hogy két ember, Anna és Béla játssza ezt a játékot. Néhány perc buzgó keresgélés után Anna odafordul Bélához, és azt mondja neki, hogy megtalálta Waldot. Hogyan tudja Anna igazolni azt, hogy tényleg megtalálta, anélkül, hogy megmutatná, hogy hol rejtőzik a figura – ezzel pedig elvéve a fiútól a lehetőséget, hogy ő maga is megoldja a feladványt?

A leghíresebb megoldás szerint egy kivágott kartonlappal kell Annának lefednie a fotót, melyen pontosan akkor lyuk található csak, ami Waldo alakját tudja megmutatni. A lyukat a figura felé helyezve így meg tudja mutatni Bélának, hogy valóban megtalálta azt. Waldo pontos hollétét azonban nem kellett felfednie. Így a játék folytatódik, a nulla ismeretű bizonyítás pedig a gyakorlatban is bizonyításra került.

Jó pár hasonló szemléletes példát tudunk még találni a koncepcióra, a legtöbb esetben azonban érvényesül az interaktivitás megléte. Ez azt jelenti, hogy bár a bizonyítónak nem kell felfednie az állításának pontos értékét, de mégis kapcsolatba kell lépnie az igazoló féllel. Ahogy a példában is láthattuk, Annának muszáj volt Bélával interakcióba lépnie ahhoz, hogy bebizonyíthassa neki, tudja, hol bújt meg a képen Waldo.

Itt jönnek azonban képbe a matematikai számítások és a hashfüggvények: ezeknek használatával ugyanis az ún. „nem-interaktív nulla ismeretű bizonyítások” is lehetségessé vállnak. Ahogy aztán lehetségessé válnak az anonim kriptopénz tranzakciók is pont ezeknek használatával.

Milyen szerepet játszik a nulla ismeretű bizonyítás az adatvédelemben?

Mielőtt azonban kitérnénk arra, hogy miért is olyan jelentős ez a kriptopénzek működési elvében, azt is mindenképpen meg kell jegyeznünk, hogy általánosan az adatvédelemben is jelentős szerepet játszik ez az elv. Nagyon alapvető, de gondoljunk például a jelszavaink helyzetére. Amikor egy internetes oldalra szeretnénk belépni, akkor a korábban megadott jelszavunkat kell megadnunk. Ezt a szerver aztán összeveti azzal, amit a rendszer eltárolt. Emiatt viszont elkerülhetetlen, hogy a rendszer tárolja ennek a jelszónak a szöveges változatát is, hiszen valamivel össze kell ezt hasonlítania.

Ez azonban két fő problémához vezet. Egyrészről bíznunk kell az adott internetes oldalban vagy cégben, hogy ők nem fognak visszaélni a megadott adatainkkal. Másrészről abban is bíznunk kell, hogy még ha nem is használják ezt fel nem megfelelő célokra, akkor sem lesznek egy esetleges hackertámadás áldozatai. Hiszen akármilyen komolyan is veszik az adatvédelmet, nincs olyan rendszer, ami teljesen védett lenne.

Ilyen esetekben is kiváló megoldást jelentenek a zero knowledge proof elvére épülő biztonsági megoldások. Amennyiben ugyanis a szenzitív adatok eleve sincsenek megosztva a harmadik féllel, úgy a bizalom is teljesen feleslegessé válik. Ebből szintén látható, hogy mennyi gyakorlati felhasználása van a ZKP elvének.

Összességében a ZKP elv során tehát három fő elvnek kell érvényesülnie – legyen szó ez egy olyan elméleti esetről, mint a Hol van Waldo játék, vagy mondjuk egy anonim zcash tranzakcióról. Egyrészől érvényesülnie kell a teljesség (completeness) elvének, azaz, hogy ha tényleg igaz az állítás, akkor biztosan meggyőződhetünk annak igazságáról. Másodikként a megbízhatóságnak (soundness) is teljesülnie, miszerint, ha nem igaz állítás, akkor lehetetlen bizonyítani ennek ellentétét. A harmadik pedig a nulla ismeret (zero knowledge), azaz, hogy a bizonyítás során nem kell megosztani semmilyen információt az állításról.

Lovász László, az Abel-díj és a kriptovaluták: hogyan működik a nulla ismeretű bizonyítás elve és mi köze van ennek a magyar matematikushoz?

A nulla ismeretű bizonyítás a privátcoinok esetében

Most, hogy nagyjából van egy elképzelésünk arról, hogy mi is a nulla ismeretű bizonyítás, térjünk ki egy kicsit arra is, hogy miként jelenik meg ez a blokkláncok és a kriptopénzek esetében. Ebbe nagyon részletesen nem fogunk belemenni, a matematikai magyarázat ugyanis ennél jóval nagyobb lélegzetvételt igényelne. Akit azonban egy komplexebb, tudományosabb magyarázat érdekel, az ezen vagy ezen linken tud további magyarázathoz jutni.

A zcash esetében a nulla ismeretű bizonyítás a zk-SNARKS (Zero Knowledge Succinct Non-Interactive Argument of Knowledge) formájában jelenik meg. A privátcoinok egyik legfontosabb tulajdonsága, hogy a tranzakció résztvevőinek anonimitást tudnak biztosítani. Ez azt jelenti, hogy míg például egy bitcoin tranzakció esetén az blokkláncon mint elosztott főkönyvön minden tranzakciónál nyíltan elérhető a küldő és fogadó fél tárcacímet, addig a privátcoinok esetében ezek nem jelennek meg.

A zk-SNARKS (nagyon leegyszerűsítve) három különböző algoritmus segítségével működik, amely során egy kulcsgenerátor egy ún. „lambda” bemenetet kreál. A lambda ezt követően két nyilvánosan elérhető kulcsot állít elő (egy bizonyító és egy igazoló kulcsot, amely mindkét fél számára rendelkezésére áll). A bizonyító a bizonyító kulcs és egyéb megadott adatokból fog egy új algoritmus segítségével bizonyítékot generálni, melyet aztán az igazoló algoritmus az igazoló kulccsal együtt használ fel. A folyamat legvégén ez fogja megadni, hogy igaz vagy hamis-e a végső állítás. A folyamat során nagyon fontos, hogy a lambda értéke semmi esetben se kerüljön megosztásra, ez ugyanis illetéktelen kezekbe kerülve hamis bizonyítékok megalkotására is használható, mellyel a nulla ismeretű bizonyítások második feltételét sértjük meg.

A ZKP jelentőségét már majdnem 50 éve tudják

Ha ez bonyolultnak tűnik, azt teljesen megértjük: nem hiába kapott hosszú évek kitartó munkásságáért Lovász László és Ali Wigderson Abel-díjat idén. A lényeg azonban talán egy mondatban még a leglaikusabbaknak is összefoglalható. A privátcoinok teljes mértékben a nulla ismeretű bizonyítás elvére alapulnak, amely lehetővé teszi azt, hogy egy tranzakciót úgy igazoljunk két fél között, hogy eközben ne kelljen semmilyen szenzitív információt megadnunk magáról a tranzakcióról. A ZKP elve pedig amellett, hogy lehetővé teszi ezen anonim tranzakciók lebonyolítását, nagyon jelentős az adatvédelem területén is. Ez a növekvő hackertámadások korában kifejezetten fontosnak számít.

Lovász Lászlóról

Lovász László már az 1970-es években felfedezte a számítási bonyolultság elméletének sajátos problémáit, amikor gráfelmélettel kezdett foglalkozni. Az azóta eltelt hosszú évtizedekben számos területtel foglalkozott a tiszta matematika témakörén belül. Egyik legkiemelkedőbb eredménye, hogy a diszkrét matematika megoldásait a számítógép-tudomány elméleti kérdéseire tudta levezetni. Jelenleg az ELTE és a Rényi Alfréd Matematikai Kutatóintézet kutatóprofesszora.

Coinmixed logo
Neked van
Kapsz
Email
Vásárlás regisztráció nélkül!
Telefonszám
Vezetéknév
Keresztnév
Tárcacím a kiküldéshez

Likeolj bennünket!

Facebook Pagelike Widget