Helló, Habr!
Ebben a cikkben a résztvevők által generált pszeudo-véletlenszámokról fogok beszélni, akik nem bíznak egymásban. Ahogy alább láthatjuk, egy „majdnem” jó generátor megvalósítása elég egyszerű, míg egy igazán jó generátor megalkotása már nehéz.
Miért van egyáltalán szükség véletlenszámok generálására olyan résztvevők számára, akik nem bíznak egymásban? Az alkalmazás egyik területe a decentralizált alkalmazások. Például egy olyan alkalmazás, amely fogadást fogad el egy résztvevőtől, és az összeget 49% valószínűséggel megduplázza, vagy 51%-kal elveszi, csak akkor fog működni, ha pártatlan módon képes véletlenszámot kapni. Ha egy támadó befolyásolhatja a véletlenszám-generátor működését, és akár csak minimálisan is növelheti a kifizetés esélyét az alkalmazásban, akkor könnyedén ki tudja üríteni azt.
Amikor elosztott protokollt fejlesztünk véletlenszámok generálására, szeretnénk, ha három tulajdonságot teljesítene:
Pártatlannak kell lennie. Más szóval, egyik résztvevő sem befolyásolhatja a véletlenszám-generátor eredményét.
Megjósolhatatlannak kell lennie. Más szóval, egyik résztvevő sem tudhatja előre, hogy milyen számot fognak generálni (vagy bármely tulajdonságát) a generálás előtt.
A protokollnak életképesnek kell lennie, azaz ellenállónak annak, hogy a résztvevők egy része desconectáljon a hálózatból, vagy szándékosan megpróbálja leállítani a protokollt.
Ebben a cikkben két megközelítést fogunk megvizsgálni: RANDAO + VDF és egy megközelítés, amely a törléses kódokon alapul. A következő részben részletesen fogunk foglalkozni a küszöb aláírásokon alapuló megközelítéssel.
De először nézzük meg egy egyszerű és gyakran használt algoritmust, amely életképes, megjósolhatatlan, de pártolt.
RANDAO
A RANDAO egy nagyon egyszerű, így viszonylag gyakran használt megközelítés a véletlenség megszerzésére. Az összes résztvevő először helyben választ egy pszeudo-véletlenszámot, majd minden résztvevő elküldi a választott szám hash-ét. Ezután a résztvevők felváltva felfedik a választott számaikat, és XOR-ozzák a feltárt számokat, és e művelet eredménye lesz a protokoll kimenetele.
A lépés a hash-ek közzétételével, mielőtt felfednénk a számokat 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 egyedül határozza meg a véletlenszám-generátor kimenetét.
A protokoll során a résztvevőknek kétszer kell közös döntésre jutniuk (úgynevezett konszenzusra): mikor kezdjék el a kiválasztott számok felfedését, és ezáltal mikor álljanak le a hash-ek befogadásával, és mikor fejezzék be a kiválasztott számok befogadását, valamint számolják ki az eredő véletlen számot. Az ilyen döntések meghozatala a résztvevők között, akik nem bíznak egymásban, önmagában nem egyszerű feladat, és erre a jövőbeni cikkekben visszatérünk, ebben a cikkben feltételezzük, hogy egy ilyen konszenzus algoritmus rendelkezésre áll.
Milyen tulajdonságai vannak a fentebb leírt RANDAO-nak? Megjósolhatatlan, ugyanakkora életerővel bír, mint a mögöttes konszenzus protokoll, de elfogult. Különösen, a támadó megfigyelheti a hálózatot, és miután a többi résztvevő felfedi a számát, kiszámíthatja azok XOR-át, és elhatározhatja, hogy felfedi-e a saját számát vagy sem, hogy befolyásolja az eredményt. Míg ez nem engedi meg a támadónak, hogy egyedül meghatározza a véletlenszám-generátor kimenetét, mégis ad neki 1 bit befolyást. Ha pedig a támadók több résztvevőt irányítanak, akkor a kezükben lévő bitek száma megegyezik az általuk irányított résztvevők számával.
A támadók befolyását jelentősen csökkenthetjük, ha megköveteljük, hogy a résztvevők sorrendben fedjék fel a számokat. Így a támadó csak akkor tudja befolyásolni az eredményt, ha ő fedi fel az utolsó számot. Míg a befolyás jelentősen csökken, a algoritmus még mindig elfogult.
RANDAO + VDF
Az RANDAO elfogulatlanná tételének egyik módja a következő: miután minden számot felfedtek, és az XOR-t kiszámolták, az eredményt be kell táplálni egy olyan funkcióba, amelynek a kiszámítása nagyon sok időt vesz igénybe, de lehetővé teszi az eredmény gyors ellenőrzését.
(vdf_output, vdf_proof) = VDF_compute(input) // ez nagyon lassú
correct = VDF_verify(input, vdf_output, vdf_proof) // ez nagyon gyorsEz a funkció ellenőrizhető késleltetési funkciónak, vagy VDF-nek hívják. Ha a végső eredmény kiszámítása tovább tart, mint a számok felfedésének szakasza, a támadó nem tudja megjósolni a számának bemutatásából vagy elrejtéséből származó hatást, így elveszíti a lehetőséget, hogy befolyásolja az eredményt.
Jó VDF-ek kifejlesztése rendkívül nehéz. Az utóbbi időben több áttörés is történt, például és amelyek a VDF-et gyakorlatilag alkalmazhatóbbá tették, és az Ethereum 2.0 hosszú távon a RANDAO-t tervezi használni VDF-del véletlenszám-forrásként. Ezen túlmenően, hogy ez a megközelítés kiszámíthatatlan és elfogulatlan, van egy további előnye is, amely a fenntarthatóságból fakad, amennyiben legalább két résztvevő elérhető a hálózaton (feltéve, hogy a használt konszenzusprotokoll életképes ilyen kevés résztvevő mellett).
A megközelítés legnagyobb nehézsége egy olyan VDF beállítása, hogy még egy nagyon drága, speciális berendezéssel rendelkező résztvevő se tudja kiszámítani a VDF-t a felfedési szakasz vége előtt. Ideálisan az algoritmusnak jelentős biztonsági tartalékkal kell rendelkeznie, mondjuk 10x. Az alábbi ábrán egy olyan résztvevő támadása látható, aki speciális ASIC-kal rendelkezik, ami lehetővé teszi számára, hogy a VDF-t gyorsabban futtassa, mint a RANDAO megerősítés felfedésére szánt idő. Az ilyen résztvevő továbbra is ki tudja számítani a végső eredményt a számának felhasználásával és anélkül, majd ezek alapján kiválasztja, hogy megmutatja-e vagy sem.
A fent említett VDF család esetében a speciális ASIC teljesítménye több mint 100-szor magasabb lehet, mint a hagyományos berendezéseké. Így ha a felfedési szakasz 10 másodpercig tart, akkor a VDF-nek, amelyet ilyen ASIC-on számítanak, több mint 100 másodpercig kell tartania ahhoz, hogy 10-szeres biztonsági tartalékot biztosítson, így a hagyományos berendezéseken számított VDF-nek 100 x 100 másodperc = ~ 3 óra időtartamúnak kell lennie.
Az Ethereum Foundation azt tervezi, hogy ezt a problémát egy saját, nyilvános ingyenes ASIC létrehozásával oldja meg. Amint ez megtörténik, minden más protokoll is kihasználhatja majd ezt a technológiát, de addig a RANDAO + VDF megközelítés nem lesz ilyen életképes azok számára a protokollok számára, amelyek nem tudnak befektetni saját ASIC fejlesztésébe.
Számos cikk, videó és egyéb információ a VDF-ről található a .
Használjunk eltüntető kódokat
Ebben a részben a véletlenszám-generáló protokollt vizsgáljuk, amely használ. Ez képes elviselni akár ⅓ rosszindulatú résztvevőt is, miközben életképes marad, és lehetővé teszi, hogy akár ⅔ rosszindulatú résztvevő is létezzen, mielőtt meg tudnák jósolni vagy befolyásolni tudnák az eredményt.
A protokoll alapgondolata a következő. Egyszerűség kedvéért tegyük fel, hogy pontosan 100 résztvevő van benne. Tegyük fel azt is, hogy minden résztvevőnek helyben van egy privát kulcsa, és az összes résztvevő nyilvános kulcsa ismert minden résztvevő számára:
Minden résztvevő helyben kitalál egy hosszú karakterláncot, felbontja azt 67 részre, eltüntető kódokat hoz létre 100 rész létrehozásához, úgy, hogy bármely 67 elegendő a karakterlánc helyreállításához, kiosztja a 100 rész egyikét minden résztvevőnek, és azokat az adott résztvevő nyilvános kulcsával titkosítja. Ezt követően az összes titkosított részt publikálják.
A résztvevők valamilyen konszenzust használnak, hogy egyetértsenek a konkrét 67 résztvevőtől kapott kódolt halmazokkal kapcsolatban.
Amint a konszenzus megvalósul, minden résztvevő a 67 halmazban található kódolt részeket, amelyek az ő nyilvános kulcsukkal titkosítva lettek, dekripálja, és közzéteszi az összes ilyen dekripált részt.
Amint a 67 résztvevő elvégezte a (3) lépést, az összes egyesített halmaz teljesen dekódolható és helyreállítható az eltüntető kódok tulajdonságainak köszönhetően, és a végső szám az eredeti karakterláncok XOR opeációjaként nyerhető, amelyekkel a résztvevők (1) pontban kezdtek.
Meg lehet mutatni, hogy ez a protokoll pártatlan és kiszámíthatatlan. Az eredményeként kapott véletlenszám a konszenzus elérése után kerül meghatározásra, de senki sem tud róla, amíg a résztvevők ⅔-a nem dekódolja az ő nyilvános kulcsukkal titkosított részeket. Így a véletlenszám meghatározása korábban történik, mint ami elegendő információ a helyreállításához, közzé van téve.
Mi történik, ha az (1) lépésben az egyik résztvevő olyan kódolt részeket küldött a többi résztvevőnek, amelyek nem megfelelő törlési kódok egy bizonyos sztringhez? További módosítások nélkül a különböző résztvevők vagy egyáltalán nem tudják helyreállítani a sztringet, vagy különböző sztringeket állítanak elő, ami azt eredményezi, hogy a különböző résztvevők különböző véletlenszámokat kapnak. Ennek megelőzésére a következő tehető: minden résztvevő a kódolt részek mellett számolja ki az összes ilyen részhez, és minden résztvevőnek elküldi a kódolt részt, valamint a Merkle-fa gyökerét és a rész fa-ba való beillesztésének bizonyítékát. A konszenzus (2) lépésében a résztvevők nem csak abban egyeznek meg, hogy több halmaz létezik, hanem abban is, hogy ezeknek a fák gyökerei is vannak (ha valamely résztvevő eltér a protokolltól, és különböző Merkle-fákat küld különböző résztvevőknek, és ezek a gyökerek konszenzus alatt felmerülnek, az ő része nem kerül be az eredményhalmazba). A konszenzus végén 67 kódolt sztring és az azoknak megfelelő Merkle-fa gyökerek állnak rendelkezésre, így legalább 67 résztvevő van (nem feltétlenül ugyanazok, akik a megfelelő sztringeket javasolták), akiknek minden 67 sztringhez van üzenet a törlési kód részéről, valamint a rész beillesztésének bizonyítéka a megfelelő Merkle-fába.
Amikor a (4) lépésben a résztvevő dekódolja a 67 részét egy bizonyos sztringhez, és próbálja azokat helyreállítani az eredeti sztringhez, a következő lehetőségek merülnek fel:
A sztring helyreáll, és ha azt ugyanakkor törlési kódokkal újra kódolják, és a helyi részekből számolják a Merkle-fát, a gyökér megegyezik azzal, amelyiken a konszenzust elérték.
A sztring helyreáll, de a helyben számított gyökér nem felel meg annak, amelyiken a konszenzust elérték.
A sztring nem áll helyre.
Könnyen belátható, hogy ha legalább egy résztvevő számára az (1) történik, akkor minden résztvevő számára az (1) fog történni, és fordítva, ha legalább egy résztvevő számára a (2) vagy (3) történik, akkor minden résztvevő számára a (2) vagy (3) fog történni. Így tehát minden sor esetében vagy minden résztvevő sikeresen helyreállítja, vagy minden résztvevő nem tudja helyreállítani. Ezután a kapott véletlenszám – az csak azokat a sorokat érinti, amelyeket a résztvevők helyre tudtak állítani XOR-al.
Küszöbönyi aláírások
Egy másik megközelítés a véletlenséghez a BLS úgynevezett küszöbönyi aláírásainak használata. A küszöbönyi aláírásokon alapuló véletlenszám-generátor pontosan ugyanazokat a garanciákat nyújtja, mint a fent említett, törlési kódokon alapuló algoritmus, de lényegesen kisebb aszimptotikát mutat az elküldött üzenetek számában minden egyes generált számra.
A BLS aláírások olyan struktúrák, amelyek lehetővé teszik, hogy több résztvevő egy közös aláírást hozzon létre egy üzenethez. Az ilyen aláírásokat gyakran használják a helymegtakarítás és a sávszélesség csökkentése érdekében, mivel nem szükséges több aláírás elosztása.
A BLS aláírások gyakori alkalmazása a blokklánc protokollokban, a véletlenszámok generálása mellett, a blokkok aláírása BFT protokollokban. Tegyük fel, hogy 100 résztvevő blokkokat hoz létre, és a blokk véglegesnek számít, ha 67-en aláírják azt. Mindannyian bemutathatják a BLS-aláírásuk részeit, és felhasználhatnak egy konszenzus-algoritmust, hogy összeállítsák a 67 aláírást, majd egy BLS-aláírásra egyesítsék őket. Bármely 67 (vagy több) rész felhasználható a végső aláírás létrehozására, amely attól függ, hogy pontosan melyik 67 aláírást egyesítették, és ezért változhat, de bár a különböző választás 67 résztvevőtól különböző aláírást eredményez, bármely ilyen aláírás érvényes aláírása lesz a blokknak. A többi résztvevőnek elég, ha a hálózaton megkapják, és ellenőrzik az egyes blokkokra vonatkozó egy aláírást, a 67 helyett, ami jelentősen csökkenti a hálózat terhelését.
Úgy tűnik, hogy ha a résztvevők által használt zártkulcsok bizonyos módon generálódnak, akkor függetlenül attól, hogy hány 67 aláírás (vagy több, de kevesebb nem) aggregálódik, az így keletkező aláírás azonos lesz. Ez felhasználható a véletlenség forrásaként: a résztvevők először megbeszélnek egy üzenetet, amelyet alá fognak írni (ez lehet a RANDAO kimenete vagy egyszerűen az utolsó blokk hash értéke, lényeg, hogy minden alkalommal változzon és egyetértésben legyen), és létrehoznak egy BLS-aláírást. A generálási eredmény kiszámíthatatlan lesz, amíg 67 résztvevő nem biztosítja a saját részét, utána a kimenet előre meghatározott és nem függhet bármely résztvevő akcióitól.
Ez a véletlenséghez való megközelítés életképes, ha legalább ⅔ résztvevő online van és betartja a protokollt, és pártatlan és kiszámíthatatlan, amíg legalább ⅓ résztvevő betartja a protokollt. Fontos megjegyezni, hogy egy rosszindulatú fél, aki több mint ⅓, de kevesebb mint ⅔ résztvevőt irányít, megakadályozhatja a protokoll működését, de nem tudja megjósolni vagy befolyásolni a kimenetét.
A küszöb aláírások önállóan is nagyon érdekes téma. A cikk második részében részletesen megvizsgáljuk, hogyan működnek, és hogyan kell pontosan generálni a résztvevők kulcsait, hogy a küszöb aláírásokat véletlenszám-generátorként lehessen használni.
Végül
Ez a cikk az első a műszaki cikkek sorozatában a blogban. . A NEAR egy blokklánc protokoll és platform a decentralizált alkalmazások fejlesztésére, kiemelve a fejlesztés egyszerűségét és a végfelhasználók számára történő könnyű használatot.
A protokoll kódja nyílt forráskódú, a megvalósításunk Rust nyelven íródott, és megtalálható itt .
Megnézheti, hogyan néz ki a NEAR fejlesztése, és kísérletezhet az online IDE-ben .
Minden hír követhető oroszul a és a , angolul pedig a hivatalos .
Hamarosan találkozunk!
Forrás: habr.com
