Nyilvános véletlenszerűség és véletlenszerűség jeladói

Nyilvános véletlenszerűség számos valós biztonsági protokoll elengedhetetlen összetevője. Egyes alkalmazásokban, például a szerencsejátékokban és a többjátékos játékokban, a véletlenszerűség növeli a szórakozást. Más alkalmazásokban a véletlenszerűség méltányos módot biztosít a nem osztható erőforrások elosztására, kezdve a zöldkártyákkal, a körzetbíróság bíráinak ügyekkel való kijelölésén át a sportversenyeken való vetésig. Kiosztásra is használják negatív olyan források, mint az adóellenőrzés vagy a másodlagos biztonsági átvilágítás a repülőtéren.

Hagyományosan megbízható hatóságokra hagyatkoztunk, hogy véletlenszerűséget generáljanak ezekhez a protokollokhoz, de a web3 világában jobban kell tennünk. Ebben a bejegyzésben megvizsgáljuk a nyilvánosan ellenőrizhető véletlenszerűség létrehozásának módjait elosztott véletlenszerűségi jeladók majd beszéljen meg néhány on-chain alkalmazást. (A hamarosan megjelenő II. rész kifejezetten a vezetőválasztásra fog összpontosítani, miközben értékeli az alternatív vezetőválasztási megközelítéseket.) 

Kívánt tulajdonságok

A véletlen számok generálása köztudottan finom feladat. Például sok kriptográfiai kulcs kiszivárgott, mert azok hibás véletlenszám-generátorra támaszkodott (amihez Cloudflare fala láva lámpák kreatív enyhítésként szolgált volna). Ez csak privát véletlenszerűség, ahol azonban csak az egyik félnek kell előállítania és használnia.

Ezzel szemben a nyilvános véletlenszerűség egy többpárti folyamat, ami jelentősen tovább nehezíti. Egy jó protokoll nyilvános véletlenszerűség előállítására a következő biztonsági tulajdonságokkal rendelkezik:

• Elfogulatlan: Egyetlen támadó vagy támadók koalíciója sem képes torzítani a kimenetet. 
• Megbízható: Egyetlen támadó sem akadályozhatja meg a protokoll kimenetét.
• Igazolható: Bárki könnyen ellenőrizheti a protokoll kimenetét, és ugyanazt a kimenetet kell látnia, mint mindenki más.
• kiszámíthatatlan: Ha a protokoll adott időben kimenetet állít elő T₁, senki sem tud előre megjósolni semmit a kimenettel kapcsolatban egy idő előtt T₀<T₁, ideális esetben azzal T₀ nagyon közel van T₁.

A torzítatlanság gyengébb tulajdonság, mint a kiszámíthatatlanság, mert minden előre nem látható protokollnak torzíthatatlannak kell lennie. Az informatikusok elfogulatlanságot mondanának csökkenti a kiszámíthatatlanságig, mert ha tudsz torzítani, akkor előre tudsz jelezni. De néha külön-külön kívánunk érvelni róluk, mert eltérő feltételezésekre támaszkodhatnak – például egy tisztességtelen többség megjósolhatja az eredményt, de nem torzítja azt.

Ezeken a tulajdonságokon túlmenően a protokollnak hatékonynak kell lennie ahhoz, hogy nagyszámú véletlenszerű bitet tudjon futtatni és előállítani. (A gyakorlatban gyakran elegendő, ha az alkalmazások 128 véletlenszerű bitet állítanak elő, és ezek segítségével egy pszeudovéletlen számgenerátort [PNRG] indítanak, hogy szükség szerint több bitet adjanak ki. A kiszámíthatatlanságnak azonban fenn kell állnia a kimenet minden egyes bitjénél, hogy használható legyen az ilyen célokra. alkalmazások sorsjátékként vagy erőforrás-allokációként.) A protokollnak ideális esetben kommunikációs és számítási költségek szempontjából is hatékonynak kell lennie.

Különböző protokollok különböző feltételek mellett érhetik el ezeket a tulajdonságokat. Például egyes protokollok elfogulatlanok lehetnek bármely koalíció számára f₁ rosszindulatú csomópontok, és előre nem láthatók bármely koalíció számára f₂<f₁ rosszindulatú csomópontok. Az elfogultságnak is különböző fokozatai vannak. Például egyes protokollokban a résztvevő képes lehet „egy bittel” torzítani a kimenetet – ami azt jelenti, hogy két lehetséges kimenet közül választhat. Más támadások lehetővé tehetik számukra a kimenet teljes javítását. Jellemzően azonban egyáltalán nem akarunk eltűrni semmilyen elfogultságot (vagy kiszámíthatóságot).

A kriptográfiai ideális: Rálságjelzők

A kriptográfusok gyakran azzal kezdenek, hogy ideális megoldást keresnek problémáikra. Nyilvános véletlenszerűség esetén a véletlenszerűség jeladója egy idealizált szolgáltatás, amely rendszeresen készít véletlenszerű kimenetet, amely megfelel az összes szükséges biztonsági követelménynek.

Ilyen idealizált véletlenszerűség jeladó, amely hasonló más kriptográfiai absztrakciókhoz – mint például a véletlen orákulumokhoz vagy az általános csoportmodellhez – a való világban nem létezik. De ez egy hasznos cél, amelyre törekedni kell, és hasznos modell a nyilvános véletlenszerűségen alapuló protokollok érvelésére. 

Tekinthetünk néhány közelítést egy ideális véletlenszerűségi jeladóhoz.

• Központosított jeladók: A jó véletlenszerűség létrehozásának legegyszerűbb módja egy központosított harmadik fél, olyan szolgáltatásokkal, mint NIST véletlenszerűség jeladó or random.org, amely a légköri zajból véletlenszerűséget generál, és szerencsejátékban való használatra akkreditált. Ez a harmadik félre való támaszkodás teljesen aláássa a decentralizáció filozófiáját. Valóban, a fenti példában bíznunk kell abban, hogy az érintett szervezetek helyesen generálják a véletlenszerűséget, mindenféle kriptográfiai bizonyíték nélkül.
• Fizikai véletlenszerűség jelenik meg: Sok hagyományos lottó a nyilvános megjelenítésre támaszkodik, például, ha valaki belenyúl a különböző számokkal ellátott pingponglabdákba. Sajnos ezek gyakran könnyen manipulálhatók. Például, bizonyos golyókat fagyasztóba lehet helyezni és a a választónak lehet mondani, hogy a hidegeket válassza.
• Természetes jeladók: Egy általános ötlet az, hogy véletlenszerű természeti jelenségeket, például időjárást vagy kozmikus háttérsugárzást használnak jelzőfényként. Sajnos az összes javasolt forrás nem ad határozott konszenzust. Különböző megfigyelők némileg eltérő értékeket látnak majd, amihez egy megbízható fél újbóli bevezetése szükséges a hivatalos mérés elvégzéséhez, a központosított jelzőfény minden hátrányával együtt.
• Félig központosított jelzőfények: A jobb megközelítés az lenne, ha a véletlenszerűséget levonnánk Bitcoin blokkfejlécek közvetlenül vagy onnan részvények záróárai, amelyet könnyebb nyilvánosan ellenőrizni, és bármelyik fél számára nehezebb teljes mértékben ellenőrizni. Még mindig vannak finom támadások mindkettő ellen a munka blokklánc véletlenszerűségének igazolása és a részvényárfolyam véletlenszerűsége. A blokklánc fejlécekkel például a bányászok dönthetnek úgy, hogy visszatartják azokat a blokkokat, amelyek fejlécei olyan beacon értéket hoznak létre, amely nem tetszik nekik. Vagy dönthetnek úgy, hogy megszakítják a kapcsolatokat, amikor két ütköző blokkot találnak a preferált jeladó kimenet alapján.

Decentralizált véletlenszerűségi jeladók (DRB)

A központosított jeladók problémáinak természetes megközelítése egy decentralizált kriptográfiai protokoll tervezése nyilvános véletlenszerűség előállítására. Ez a probléma némileg olyan, mint a decentralizált konszenzusos protokollok tervezése, csak nehezebb. Nemcsak az összes résztvevőnek meg kell állapodnia a kimenetben (a véletlenszerűségben), hanem lehetetlennek kell lennie a protokoll rosszindulatú résztvevője számára, hogy torzítsa vagy előre jelezze a kimenetet.

A véletlenszerűségi jeladók szimulálására tervezett protokollokat elosztott véletlenszerűségi jeladóknak (DRB) nevezik. (Más nevek között szerepel az „elosztott érmefeldobás”.) A problémát évtizedek óta tanulmányozzák, a híres lehetetlenségi eredmények bizonyultak az 1980-as években, de a blokklánc korszakban újra fellángolt az érdeklődés. A DRB-ket fel lehetne használni a láncon belüli véletlenszerűség biztosítására, ami a tisztességes, biztonságos és átlátható láncon belüli alkalmazások kulcsfontosságú összetevője lenne.

A klasszikus megközelítés: Commit-reveal protokollok

Optimista esetben egy nagyon egyszerű kétfordulós protokoll is elegendő egy DRB-hez. Az 1. fordulóban minden résztvevő i véletlenszerű értéket generál r_i és kriptográfiai kötelezettségvállalást tesz közzé c_i=Elkövetni(r_i). Ebben az alkalmazásban a kötelezettségvállalás egyszerűen egy hash függvény lehet, például az SHA-256. Az egyes résztvevők kötelezettségvállalásának közzététele után be vannak zárva a választásukba r_i, de a kötelezettségvállalások nem árulnak el semmilyen információt más résztvevők hozzájárulásairól. A 2. fordulóban minden résztvevő publikálással „megnyitja elköteleződését”. r_i. Ezután az összes véletlenszerű értéket kombinálják, például XOR-eléssel vagy (lehetőleg) összefűzésük kivonatával.

Ez a protokoll egyszerű, és véletlenszerű jeladó kimenetet ad mindaddig, amíg akár az egyik résztvevő is kiválasztja a sajátját r_i véletlenszerűen. Sajnos van egy klasszikus hibája: amikor a résztvevők közül egy kivételével mindenki felfedte véletlenszerű értékét, az utolsó résztvevő ki tudja számítani a feltételezett beacon kimenetet. Ha ez nem tetszik nekik, megtagadhatják értékük közzétételét, ezzel megszakítva a protokollt. A hibás résztvevő hozzájárulásának figyelmen kívül hagyása nem oldja meg a problémát, mert így a támadó továbbra is választhat két jeladó kimenet között (az egyik a hozzájárulásával számítva, a másik pedig anélkül).

A blokkláncok természetes megoldást kínálnak erre a problémára: minden résztvevőtől megkövetelhetik, hogy letétbe helyezzen bizonyos összegeket, amelyeket lefoglalnak, ha nem fedik fel véletlenszerű hozzájárulását. Pontosan ezt a megközelítést választotta a klasszikus RANDAO jeladó az Ethereumon. Ennek a megközelítésnek az a hátránya, hogy a kimenet továbbra is elfogult lehet, ami anyagilag megtérülhet a támadó számára, ha a letétben lévő pénz kevesebb, mint a jeladó eredményén meglovagolt pénzösszeg. Az elfogult támadásokkal szembeni jobb biztonság érdekében több érmét kell letétbe helyezni.

Végrehajtási-felfedési-visszaállítási protokollok

Ahelyett, hogy az összes felet arra kényszerítenék, hogy felfedjék véletlenszerű hozzájárulásukat, egyes protokollok helyreállítási mechanizmust is tartalmaznak, így még ha a résztvevők kisebb része is kiesik, a többiek befejezhetik a protokollt. Fontos, hogy a protokoll mindkét esetben ugyanazt az eredményt adja, hogy a felek ne torzíthassák az eredményt azzal, hogy kiválasztják, hogy kilépnek-e vagy sem.

Ennek egyik módja az, hogy minden résztvevő átadja a többieknek titkát, hogy többségük rekonstruálhassa azt, például Shamir titokmegosztása. Fontos tulajdonság azonban, hogy a többiek ellenőrizni tudják, hogy az elkötelezett titkot megfelelően megosztották-e, ehhez egy erősebb primitív, a nyilvánosan ellenőrizhető titkos megosztás (PVSS) használata szükséges.

Számos más helyreállítási mechanizmus is lehetséges, de mindegyiknek ugyanaz a korlátja. Ha vannak N résztvevők, és rugalmasságot akarunk, ha bármely csoport legfeljebb f csomópontok kiesnek, akkor minden olyan csoportnak kell lennie Nf A résztvevők kiszámolhatják a végeredményt. De ez egyben rosszindulatú koalíciót is jelent Nf a résztvevők előre megjósolhatják az eredményt a helyreállítási mechanizmus privát szimulálásával. Ez megtörténhet a protokoll első fordulójában is, amely idő alatt egy ilyen koalíció módosíthatja saját véletlenszerűségi döntéseit, és torzíthatja az eredményt. 

Más szóval, ez minden koalíciót jelent Nf a csomópontoknak tartalmazniuk kell legalább egy becsületes csomópontot. Egyszerű algebrával, Nf > f, Így f < N/2, és ezek a protokollok eredendően becsületes többséget igényelnek. Ez jelentős különbség az eredeti commit-reveal biztonsági modellhez képest, amely csak megköveteli f<N (legalább egy becsületes résztvevő).

Ezek a protokollok gyakran jelentős kommunikációs költségeket is igényelnek az extra PVSS-információk megosztásához az összes csomópont között a protokoll minden egyes futtatásakor. A kutatói közösség az elmúlt néhány évben jelentős munkát végzett ezen a problémán, többek között kutatási javaslatokkal RandShare, Kaparás, SecRand, HERBvagy Albatrosz, de úgy tűnik, hogy egyik sem látott valós telepítést.

Ellenőrizhető véletlenszerű függvény alapú protokollok

Felismerve, hogy egy csoport Nf A résztvevők kiszámíthatják a véletlen beacon értéket a fenti protokollban, ami valamivel egyszerűbb megközelítéshez vezet: megosztani egy hosszú távú titkos kulcsot N feleket, és kérje meg őket, hogy értékeljék a ellenőrizhető véletlenszerű függvény (VRF). A titkos kulcs megosztása a t-kívül-N küszöbséma, így bármely t a résztvevők ki tudják számítani a VRF-et (de egy kisebb koalíció nem). Mert t=Nf, ez ugyanazt az ellenálló képességet biztosítja f rosszindulatú csomópontok, mint a fent tárgyalt commit-reveal-recover protokollok.

VÉGLEGES úttörője volt ennek a megközelítésnek konszenzusprotokolljuk részeként küszöbértékes BLS aláírásokat használva (amelyek VRF-ként működnek). Az önálló Drand A véletlenszerűségi jeladó lényegében ugyanazt a megközelítést alkalmazza, ahol a résztvevők egy csoportja küszöbérték-BLS-aláír egy számlálót minden körben. A Entrópia Ligája a drand nyílt forráskódú példánya, amely 30 másodpercenként véletlenszerűséget produkál 16 résztvevő csomópont segítségével (2022 szeptemberétől), amelyet vállalatok és egyetemi kutatócsoportok vegyesen üzemeltetnek. 

E megközelítések hátránya, hogy a küszöbkulcs inicializálása viszonylag bonyolult, csakúgy, mint a kulcs újrakonfigurálása, amikor csomópontok csatlakoznak vagy távoznak. A gyakori esetekben azonban a protokollok nagyon hatékonyak. 

Ahogy fentebb leírtuk, egy számláló értékének egyszerű aláírása nem ad új véletlenszerűséget körönként, így ha elegendő számú résztvevő kulcsa sérül, akkor a protokoll minden következő körben kiszámítható lesz.

Láncszem VRF kombájnok ezt a megközelítést (a NSEC5 VRF) a véletlenszerűséget kérő felek által meghatározott külső véletlenszerű forrással, amely a gyakorlatban jellemzően egy újabb blokklánc fejléc. Ezeket az adatokat azután egy VRF-en keresztül továbbítják, amelyet vagy az egyik fél üzemeltet, vagy küszöbértéket biztosít egy csoportnak.

Ethereum a Beacon lánc jelenleg BLS-alapú VRF-eket használ: az egyes körök javaslattevője hozzáadja a VRF értékét a keverékhez. Ezzel egy kör kommunikációt takaríthat meg a commit-reveal paradigmához képest (feltételezve, hogy a hosszú távú BLS nyilvános kulcsot egyszer regisztrálják), bár ez a kialakítás örökli a commit-reveal megközelítés néhány figyelmeztetését, beleértve a jeladó kimenetének torzításának lehetőségét a kimenet visszatartásával. .

Ellenőrizhető késleltetési függvény alapú protokollok

Végül egy ígéretes új irány az időalapú kriptográfia, konkrétan ellenőrizhető késleltetési funkciók (VDF-ek). Ez a megközelítés jó kommunikációs hatékonyságot és robusztusságot ígér, valamint rugalmasságot N-1 rosszindulatú csomópontok. 

Visszatérve az eredeti commit-reveal protokollhoz, a hagyományos kötelezettségvállalások helyettesíthetők időzített kötelezettségvállalások hogy megszüntesse annak problémáját, hogy a résztvevők nem hajlandók felfedni véletlenszerű hozzájárulásukat. Az időzített kötelezettségvállalásokat hatékonyan megnyithatja az eredeti committer, vagy bárki, aki hajlandó lassú függvényt (lényegében VDF-et) kiszámítani. Így, ha valamelyik résztvevő kiesik egy commit-reveal protokollból, az elkötelezettségét továbbra is megnyithatják mások. Alapvető fontosságú, hogy a kötelezettségvállalás megnyitásának minimális ideje elég hosszú legyen ahhoz, hogy azt a protokoll első fordulójában (a véglegesítési szakaszban) ne lehessen megtenni, különben a rosszindulatú résztvevők elég gyorsan megnyithatják mások kötelezettségvállalásait ahhoz, hogy módosítsák saját hozzájárulásukat és torzítsák az eredményt. .

A modern VDF-ekkel még elegánsabb egyfordulós protokoll érhető el: hagyja el teljesen az elkötelezettséget. Minden résztvevő egyszerűen közzéteheti véletlenszerű hozzájárulását r_i, a végeredmény pedig az egyes résztvevők hozzájárulásának kombinációja, amely egy VDF-en keresztül fut. A VDF kiszámításának késleltetése biztosítja, hogy senki se tudja megválasztani elkötelezettségét úgy, hogy az torzítsa a végső kimenetet. Ezt a megközelítést a következőképpen javasolták UNICORN Arjen Lenstra és Benjamin Wesolowski 2015-ben, és valóban kulcsfontosságú motiváló alkalmazás volt a VDF-ek fejlesztése.

Ez a megközelítés gyakorlati alkalmazáson ment keresztül. Chia ennek egy változatát a konszenzusprotokoll részeként valósítja meg, ismételt négyzetes VDF-eket használva az osztálycsoportokban. Starkware végrehajtva a proof-of-concept VDF alapú jeladó SNARK-alapú VDF-ek használatával. Ethereum tervek is használata ez a megközelítés, dedikált ASIC felépítése a VDF-ek kiszámításához, hogy véletlenszerűséget generáljon a konszenzus rétegben.

***

A nyilvános véletlenszerűség sok protokoll alapvető összetevője, de még mindig hiányzik a magas biztonságot nyújtó szabványos DRB. A tervezési tér nagy, és a fenti megközelítések számos hibridje és kombinációja lehetséges. Például lehetséges egy VRF-alapú protokoll kombinálása VDF-alapú protokollal, amely új entrópiát ad, például a RandRunner. Az Ethereum Beacon Chain jelenleg VRF-eket használ, bár a jövőben hozzáadhat VDF-eket, hogy kiküszöbölje a blokk-visszatartási támadások torzításának lehetőségét.

Az is nyitott kérdés, hogy a becsületes többségi protokollok mikor elfogadhatók. A résztvevők viszonylag kis, ellenőrzött csoportja esetében – mint például az Entrópia Ligája – az őszinte többségi feltételezés ésszerű. Másrészt az egyetlen becsületes résztvevőt igénylő protokollok eredendő előnyük is van – több résztvevő csak javíthatja a biztonságot. Ez azt jelenti, hogy ezek a protokollok nyílt, engedély nélküli részvétellel telepíthetők.

A II. részben a véletlenszerű vezetőválasztás specifikus alkalmazását tárgyaljuk a konszenzusos protokollokban, amelynek kissé eltérő tervezési céljai vannak, és ennek eredményeként még több protokollt és megközelítést javasoltak.

***

Joseph Bonneau az a16z crypto kutatási partnere. Kutatásai az alkalmazott kriptográfiára és a blokklánc biztonságra összpontosítanak. Tanított kriptovaluta kurzusokat a Melbourne-i Egyetemen, a New York-i Egyetemen, a Stanfordon és a Princetonon, PhD fokozatot szerzett számítástechnikából a Cambridge-i Egyetemen és BS/MS fokozatot a Stanfordon.

Valeria Nikolaenko az a16z crypto kutatási partnere. Kutatásai a kriptográfiára és a blokklánc biztonságra összpontosítanak. Olyan témákkal is foglalkozott, mint a hosszú távú támadások a PoS konszenzus protokollokban, az aláírási sémák, a kvantum utáni biztonság és a többoldalú számítás. A Stanford Egyetemen szerzett PhD fokozatot kriptográfiából Dan Boneh professzor vezetésével, és a kutatócsoport tagjaként a Diem blokkláncon dolgozott.

***

Szerkesztő: Tim Sullivan

***

Az itt kifejtett nézetek az AH Capital Management, LLC („a16z”) egyes alkalmazottainak nézetei, és nem az a16z vagy leányvállalatai nézetei. Az itt található bizonyos információk harmadik féltől származnak, többek között az a16z által kezelt alapok portfólióvállalataitól. Noha megbízhatónak vélt forrásokból származnak, az a16z nem ellenőrizte önállóan ezeket az információkat, és nem nyilatkozik az információk tartós pontosságáról vagy adott helyzetre való megfelelőségéről. Ezenkívül ez a tartalom harmadik féltől származó hirdetéseket is tartalmazhat; az a16z nem vizsgálta át az ilyen hirdetéseket, és nem támogatja az abban található reklámtartalmat.

Ez a tartalom csak tájékoztatási célokat szolgál, és nem támaszkodhat rá jogi, üzleti, befektetési vagy adótanácsadásként. Ezekkel a kérdésekkel kapcsolatban konzultáljon saját tanácsadójával. Bármely értékpapírra vagy digitális eszközre történő hivatkozások csak illusztrációs célt szolgálnak, és nem minősülnek befektetési ajánlásnak vagy ajánlatnak befektetési tanácsadási szolgáltatások nyújtására. Ezen túlmenően ez a tartalom nem befektetőknek vagy leendő befektetőknek szól, és nem is szánható felhasználásra, és semmilyen körülmények között nem támaszkodhat rá az a16z által kezelt alapokba történő befektetésről szóló döntés meghozatalakor. (A16z alapba történő befektetésre vonatkozó ajánlatot csak az ilyen alap zártkörű kibocsátási memoranduma, jegyzési szerződése és egyéb vonatkozó dokumentációja tesz, és azokat teljes egészében el kell olvasni.) Minden említett, hivatkozott befektetés vagy portfóliótársaság, ill. A leírtak nem reprezentatívak az a16z által kezelt járművekbe történő összes befektetésre, és nem garantálható, hogy a befektetések nyereségesek lesznek, vagy a jövőben végrehajtott egyéb beruházások hasonló tulajdonságokkal vagy eredménnyel járnak. Az Andreessen Horowitz által kezelt alapok befektetéseinek listája (kivéve azokat a befektetéseket, amelyek esetében a kibocsátó nem adott engedélyt az a16z számára a nyilvánosságra hozatalra, valamint a nyilvánosan forgalmazott digitális eszközökbe történő be nem jelentett befektetéseket) a https://a16z.com/investments oldalon érhető el. /.

A benne található diagramok és grafikonok kizárólag tájékoztató jellegűek, és nem szabad rájuk hagyatkozni befektetési döntések meghozatalakor. A múltbeli teljesítmény nem jelzi a jövőbeli eredményeket. A tartalom csak a feltüntetett dátum szerint beszél. Az ezekben az anyagokban megfogalmazott előrejelzések, becslések, előrejelzések, célok, kilátások és/vagy vélemények előzetes értesítés nélkül változhatnak, és mások véleményétől eltérhetnek vagy ellentétesek lehetnek. További fontos információkért látogasson el a https://a16z.com/disclosures oldalra.