Lehetséges véletlen számokat generálni, ha nem bízunk egymásban? 1. rész

Szia Habr!

Ebben a cikkben az egymásban nem bízó résztvevők által generált álvéletlen számokról fogok beszélni. Amint alább látni fogjuk, egy „majdnem” jó generátor megvalósítása meglehetősen egyszerű, de egy nagyon jó generátort nehéz.

Miért lenne szükség véletlen számok generálására olyan résztvevők között, akik nem bíznak egymásban? Az egyik alkalmazási terület a decentralizált alkalmazások. Például egy olyan alkalmazás, amely elfogad egy fogadást egy résztvevőtől, és 49%-os valószínűséggel megduplázza az összeget, vagy 51%-os valószínűséggel elveszi az összeget, csak akkor működik, ha elfogulatlanul tud véletlen számot kapni. Ha egy támadó befolyásolni tudja a véletlenszám-generátor kimenetelét, és kismértékben is növeli az esélyét, hogy kifizetést kapjon az alkalmazásban, könnyen tönkreteszi azt.

Amikor egy elosztott véletlenszám-generáló protokollt tervezünk, azt szeretnénk, hogy annak három tulajdonsága legyen:

1. Elfogulatlannak kell lennie. Más szóval, egyetlen résztvevő sem befolyásolhatja a véletlenszám-generátor eredményét.

2. Biztosan kiszámíthatatlan. Más szóval, egyetlen résztvevő sem tudja megjósolni, hogy milyen szám generálódik (vagy következtethet annak tulajdonságaira), mielőtt az előáll.

3. A protokollnak életképesnek kell lennie, azaz ellenállnia kell annak, hogy a résztvevők bizonyos százaléka lekapcsolja a hálózatot, vagy szándékosan megpróbálja leállítani a protokollt.

Ebben a cikkben két megközelítést fogunk megvizsgálni: a RANDAO + VDF és a törlési kódok megközelítését. A következő részben részletesen megvizsgáljuk a küszöb aláírásokon alapuló megközelítést.

De először nézzünk meg egy egyszerű és általánosan használt algoritmust, amely életképes, kiszámíthatatlan, de elfogult.

RANDAO

A RANDAO egy nagyon egyszerű és ezért meglehetősen gyakran használt megközelítés a véletlenszerűség generálására. A hálózat összes résztvevője először helyileg választ ki egy pszeudovéletlen számot, majd minden résztvevő elküldi a kiválasztott szám hash-jét. Ezután a résztvevők felváltva felfedik a kiválasztott számokat, és a feltárt számokon XOR műveletet hajtanak végre, és ennek a műveletnek az eredménye lesz a protokoll eredménye.

A kivonatok közzététele a számok felfedése előtt azért szükséges, hogy a támadó ne tudja kiválasztani a számát, miután látta a többi résztvevő számát. Ez lehetővé tenné számára, hogy gyakorlatilag egymaga meghatározza a véletlenszám-generátor kimenetét.

A protokoll lebonyolítása során a résztvevőknek kétszer kell közös döntésre (ún. konszenzusra) jutniuk: mikor kezdik el a kiválasztott számok felfedését, és ezért hagyják abba a hash elfogadását, és mikor hagyják abba a kiválasztott számok elfogadását és a kapott véletlen kiszámítását. szám. Ilyen döntések meghozatala az egymásban nem bízó résztvevők között önmagában nem könnyű feladat, erre a későbbi cikkekben még visszatérünk, ebben a cikkben feltételezzük, hogy egy ilyen konszenzusos algoritmus rendelkezésünkre áll.

A fent leírt tulajdonságok közül melyikkel rendelkezik a RANDAO? Kiszámíthatatlan, ugyanolyan vitalitással bír, mint a mögöttes konszenzus protokoll, de elfogult. Pontosabban, a támadó megfigyelheti a hálózatot, és miután a többi résztvevő felfedte a számukat, kiszámíthatja az XOR-t, és eldöntheti, hogy felfedi-e a számát, hogy befolyásolja az eredményt. Bár ez megakadályozza, hogy a támadó egyedül határozza meg a véletlenszám-generátor kimenetét, mégis 1 bit befolyást ad neki. És ha a támadók több résztvevőt irányítanak, akkor az általuk irányított bitek száma megegyezik az általuk irányított résztvevők számával.

A támadók befolyása nagymértékben csökkenthető, ha megkövetelik, hogy a résztvevők sorrendben közöljék a számokat. Ekkor a támadó csak akkor tudja befolyásolni az eredményt, ha utoljára nyitja meg. Bár a befolyás lényegesen kisebb, az algoritmus még mindig torz.

RANDAO+VDF

A RANDAO elfogulatlansá tételének egyik módja a következő: miután az összes számot feltártuk, és az XOR kiszámítása megtörtént, az eredményt egy függvény bemenetére tápláljuk, aminek kiszámítása nagyon hosszú időt vesz igénybe, de lehetővé teszi a függvény helyességének ellenőrzését. nagyon gyorsan számol.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Ezt a funkciót Verifiable Delay Function-nak vagy VDF-nek nevezik. Ha a végeredmény kiszámítása tovább tart, mint a számközlési szakasz, akkor a támadó nem tudja megjósolni a szám megjelenítésének vagy elrejtésének hatását, így elveszíti az eredmény befolyásolásának lehetőségét.

A jó VDF-ek fejlesztése rendkívül nehéz. Az utóbbi időben több áttörés is történt, pl. ezt и ez, ami a gyakorlatban praktikusabbá tette a VDF-et, az Ethereum 2.0 pedig hosszú távon a RANDAO VDF-fel való használatát tervezi véletlenszám-forrásként. Amellett, hogy ez a megközelítés kiszámíthatatlan és elfogulatlan, további előnye, hogy életképes, ha legalább két résztvevő elérhető a hálózaton (feltételezve, hogy az alkalmazott konszenzusos protokoll életképes, ha ilyen kis számú résztvevővel foglalkozunk).

Ennek a megközelítésnek a legnagyobb kihívása a VDF beállítása úgy, hogy még egy nagyon drága speciális hardverrel rendelkező résztvevő sem tudja kiszámítani a VDF-et a felfedezési fázis vége előtt. Ideális esetben az algoritmusnak még jelentős biztonsági ráhagyással is rendelkeznie kell, mondjuk 10-szeresével. Az alábbi ábra egy olyan színész támadását mutatja, akinek speciális ASIC-je van, amely lehetővé teszi számára, hogy gyorsabban futtasson egy VDF-et, mint a RANDAO megerősítésének felfedésére szánt idő. Az ilyen résztvevő továbbra is kiszámolhatja a végeredményt a számával vagy anélkül, majd a számítás alapján választhat, hogy megjeleníti-e vagy sem.

A fent említett VDF család esetében a dedikált ASIC teljesítménye 100-szor nagyobb lehet, mint a hagyományos hardveré. Tehát ha a telepítési fázis 10 másodpercig tart, akkor az ilyen ASIC-en számított VDF-nek több mint 100 másodpercnek kell lennie ahhoz, hogy 10-szeres biztonsági ráhagyással rendelkezzen, és így ugyanannak a VDF-nek, amelyet árucikk hardveren számítanak ki, 100x 100 másodperc = ~3 óra.

Az Ethereum Alapítvány saját, nyilvánosan elérhető, ingyenes ASIC-ek létrehozásával kívánja megoldani ezt a problémát. Ha ez megtörténik, az összes többi protokoll is kihasználhatja ezt a technológiát, de addig a RANDAO+VDF megközelítés nem lesz olyan életképes azon protokollok esetében, amelyek nem tudnak beruházni saját ASIC-eik fejlesztésébe.

Számos cikket, videót és egyéb információt gyűjtöttek össze a VDF-ről ezen az oldalon.

Törlési kódokat használunk

Ebben a részben egy véletlenszám-generáló protokollt fogunk megvizsgálni, amelyet használ kódok törlése. Akár ⅓ támadót is képes elviselni, miközben életképes marad, és legfeljebb ⅔ támadó létezését teszi lehetővé, mielőtt megjósolhatnák vagy befolyásolhatnák az eredményt.

A protokoll fő gondolata a következő. Az egyszerűség kedvéért tegyük fel, hogy pontosan 100 résztvevő van. Tételezzük fel azt is, hogy helyileg minden résztvevő rendelkezik valamilyen privát kulccsal, és az összes résztvevő nyilvános kulcsát minden résztvevő ismeri:

1. Minden résztvevő helyileg előáll egy hosszú karakterlánccal, 67 részre bontja, törlési kódokat hoz létre 100 megosztás eléréséhez, így bármelyik 67 elegendő a karakterlánc helyreállításához, a 100 megosztás mindegyikét hozzárendeli az egyik résztvevőhöz, és titkosítja őket ugyanaz a résztvevő nyilvános kulcsa. Ezt követően az összes kódolt megosztást közzéteszik.

2. A résztvevők valamilyen konszenzust alkalmaznak, hogy megállapodásra jussanak a 67 résztvevő kódolt halmazairól.

3. A konszenzus megszületése után minden résztvevő elveszi a kódolt megosztásokat mind a 67 készletben, amelyeket nyilvános kulcsával titkosítanak, dekódolja az összes ilyen megosztást, és közzéteszi az összes ilyen dekódolt megosztást.

4. Ha 67 résztvevő teljesítette a (3) lépést, a törlési kódok tulajdonságai miatt az összes egyeztetett halmaz teljesen dekódolható és rekonstruálható, és a végső szám megkapható a kezdeti sorok XOR-értékeként, amelyekkel a résztvevők az (1)-ben kezdtek. .

Ez a protokoll elfogulatlan és kiszámíthatatlan. Az eredményül kapott véletlenszámot a konszenzus elérése után határozzák meg, de ezt senki sem tudja, amíg a résztvevők ⅔ dekódolja a nyilvános kulcsával titkosított részeket. Így a véletlenszámot a rekonstrukcióhoz elegendő információ közzététele előtt határozzák meg.

Mi történik, ha az (1) lépésben az egyik résztvevő olyan kódolt megosztásokat küld a többi résztvevőnek, amelyek nem a megfelelő törlési kódok valamelyik karakterlánchoz? További változtatások nélkül a különböző résztvevők vagy egyáltalán nem tudják visszaállítani a karakterláncot, vagy különböző karakterláncokat állítanak helyre, ami azt eredményezi, hogy a különböző résztvevők eltérő véletlenszámot kapnak. Ennek megelőzése érdekében a következőket teheti: minden résztvevő a kódolt megosztásokon kívül kalkulál még Merkla fa az összes ilyen megosztást, és minden résztvevőnek elküldi magát a kódolt megosztást és a merkle-fa gyökerét, valamint a megosztásnak a merkle-fába való felvételének bizonyítékát. A (2) lépésben a konszenzus során a résztvevők nem csak egy halmazban állapodnak meg, hanem az ilyen fák meghatározott gyökereinek halmazában is (ha valamelyik résztvevő eltért a protokolltól, és különböző merklefa gyökereket küldött a különböző résztvevőknek, és két ilyen gyök látható a konszenzus során, ha a sor nem szerepel az eredményhalmazban). A konszenzus eredményeként 67 kódolt sorunk és a merkle fa megfelelő gyökerei lesznek úgy, hogy legalább 67 résztvevő legyen (nem feltétlenül ugyanazok, akik a megfelelő sorokat javasolták), akik mind a 67 sorhoz rendelkeznek egy üzenet a törlési kód megosztásával, és a megfelelő fában való részesedésük előfordulásának bizonyítéka elhalványult.

Amikor a (4) lépésben a résztvevő 67 ütemet fejt meg egy bizonyos karakterlánchoz, és megpróbálja ezekből rekonstruálni az eredeti karakterláncot, a következő lehetőségek közül választhat:

1. A karakterlánc visszaállításra kerül, és ha ezután újra törléskódolásra kerül, és a Merkle-fát a lokálisan számított megosztásokra számítják ki, akkor a gyökér egybeesik azzal, amelyről konszenzus született.

2. A sor visszaáll, de a helyileg számított gyökér nem egyezik azzal, amelynél konszenzus született.

3. A sor nem áll vissza.

Könnyen kimutatható, hogy ha az (1) opció legalább egy résztvevővel megtörtént, akkor az (1) lehetőség minden résztvevővel, és fordítva, ha a (2) vagy (3) lehetőség legalább egy résztvevővel történt, akkor minden résztvevő esetében a (2) vagy (3) lehetőség fog megvalósulni. Így a készlet minden soránál vagy minden résztvevő sikeresen visszaállítja, vagy az összes résztvevő nem tudja visszaállítani. Az eredményül kapott véletlen szám csak azon sorok XOR-ja, amelyeket a résztvevők vissza tudtak állítani.

Aláírások küszöbértéke

A véletlenszerűség másik megközelítése az úgynevezett BLS küszöb aláírások használata. A küszöb-aláírásokon alapuló véletlenszám-generátor pontosan ugyanazokkal a garanciákkal rendelkezik, mint a fent leírt törlési kód alapú algoritmus, de lényegesen alacsonyabb a hálózaton keresztül küldött üzenetek aszimptotikus száma minden generált szám esetén.

A BLS aláírások olyan kialakítás, amely lehetővé teszi több résztvevő számára, hogy egyetlen közös aláírást hozzanak létre egy üzenethez. Ezeket az aláírásokat gyakran használják hely és sávszélesség megtakarítására, mivel nem kell több aláírást kiküldeni. 

A blokklánc-protokollokban a BLS aláírások általános alkalmazása a véletlen számok generálása mellett a blokk aláírás a BFT protokollokban. Tegyük fel, hogy 100 résztvevő hoz létre blokkokat, és egy blokk akkor tekinthető véglegesnek, ha 67-en aláírják. Mindannyian beküldhetik a BLS-aláírás saját részeit, és valamilyen konszenzusos algoritmus segítségével megegyezhetnek 67-ben, majd egyesíthetik őket egyetlen BLS-aláírásba. Bármely 67 (vagy több) rész felhasználható a végső aláírás létrehozásához, amely attól függ, hogy melyik 67 aláírást kombinálták, és ezért változhat, bár a 67 résztvevő eltérő választása eltérő aláírást hoz létre, minden ilyen aláírás érvényes aláírás a blokkhoz. A többi résztvevőnek ekkor blokkonként csak egy aláírást kell fogadnia és ellenőriznie a hálózaton keresztül 67 helyett, ami jelentősen csökkenti a hálózat terhelését.

Kiderült, hogy ha a résztvevők által használt privát kulcsokat egy bizonyos módon generálják, akkor függetlenül attól, hogy melyik 67 aláírást (vagy többet, de nem kevesebbet) összesítik, a kapott aláírás ugyanaz lesz. Ez a véletlenszerűség forrásaként használható: a résztvevők először megállapodnak valami üzenetben, amit aláírnak (ez lehet a RANDAO kimenete, vagy csak az utolsó blokk hashje, nem igazán számít, amíg minden alkalommal változik és konzisztens), és hozzon létre hozzá egy BLS-aláírást. A generálás eredménye mindaddig megjósolhatatlan, amíg 67 résztvevő be nem adja alkatrészeit, utána pedig a kimenet már előre meghatározott, és nem függhet egyetlen résztvevő tevékenységétől sem.

A véletlenszerűségnek ez a megközelítése mindaddig életképes, amíg az online résztvevők legalább ⅔-a követi a protokollt, és elfogulatlan és kiszámíthatatlan mindaddig, amíg a résztvevők legalább egyharmada követi a protokollt. Fontos megjegyezni, hogy az a támadó, aki a résztvevők több mint ⅓-át, de kevesebb mint ⅔-át irányítja, leállíthatja a protokollt, de nem tudja előre jelezni vagy befolyásolni annak kimenetét.

Maguk a küszöb aláírások nagyon érdekes téma. A cikk második részében részletesen elemezzük, hogyan működnek, és hogyan kell pontosan generálni a résztvevői kulcsokat ahhoz, hogy a küszöb-aláírásokat véletlenszám-generátorként lehessen használni.

Összefoglalva

Ez a cikk az első a technikai blog cikkek sorozatában NEAR. A NEAR egy blokklánc protokoll és platform decentralizált alkalmazások fejlesztésére, különös tekintettel a könnyű fejlesztésre és a végfelhasználók egyszerű használatára.

A protokoll kód nyitott, a megvalósításunk Rust-ban van írva, megtalálható itt.

Megnézheti, hogyan néz ki a NEAR fejlesztése, és kísérletezhet az online IDE-ben itt.

Az összes hírt oroszul követheti a címen távirat csoport és csoport a VKontakte-on, angolul pedig a hivatalosban Twitter.

Hamarosan találkozunk!

Forrás: will.com