Javna naključnost in svetilniki naključnosti

Javna naključnost je bistven sestavni del številnih varnostnih protokolov v resničnem svetu. V nekaterih aplikacijah, kot so igre na srečo in igre za več igralcev, naključnost doda zabavo. V drugih aplikacijah naključnost zagotavlja pravičen način dodeljevanja nedeljivih virov, od zelenih kart do dodelitve sodnikov okrožnih sodišč primerom do sejanja na športnih turnirjih. Uporablja se tudi za dodeljevanje negativna sredstva, kot so davčne revizije ali sekundarni varnostni pregledi na letališču.

Tradicionalno smo se pri ustvarjanju naključnosti za te protokole zanašali na zaupanja vredne organe, vendar bomo v svetu web3 morali biti boljši. V tej objavi bomo raziskali pristope k izgradnji javno preverljive naključnosti prek porazdeljeni svetilniki naključnosti in nato razpravljajte o nekaterih aplikacijah v verigi. (Drugi del, ki je v pripravi, se bo posebej osredotočil na volitve voditeljev, hkrati pa bo zagotovil oceno alternativnih pristopov volitev voditeljev.) 

Željene lastnosti

Generiranje naključnih števil je znano subtilna naloga. Na primer, veliko kriptografskih ključev je ušlo, ker so zanašal na pokvarjen generator naključnih števil (za katerega Cloudflarejev zid lava svetilke bi služil kot ustvarjalna ublažitev). To je samo zasebna naključnost, kjer pa ga mora ustvariti in uporabiti samo ena stranka.

Nasprotno pa je javna naključnost večstranski proces, kar znatno poveča težavo. Dober protokol za ustvarjanje javne naključnosti bo imel naslednje varnostne lastnosti:

• Nepristransko: noben napadalec ali koalicija napadalcev ne bi smela vplivati ​​na rezultat. 
• Zanesljivo: Noben napadalec ne bi smel preprečiti, da bi protokol ustvaril izhod.
• Preverljivo: Vsak lahko enostavno preveri izhod protokola in mora videti enak izhod kot vsi drugi.
• Nepredvidljivo: Če protokol ustvari izhod ob določenem času T₁, nihče ne bi smel napovedati ničesar o rezultatu prej kot nekaj časa T₀<T₁, idealno z T₀ zelo blizu T₁.

Nepristranskost je šibkejša lastnost kot nepredvidljivost, ker mora biti vsak protokol, ki je nepredvidljiv, nepristranski. Računalničarji bi rekli nepristranskost zmanjšuje do nepredvidljivosti, kajti če si lahko pristranski, lahko tudi predvidiš. Toda včasih bomo želeli o njih razmišljati ločeno, ker se lahko zanašajo na različne predpostavke – na primer, nepoštena večina lahko napove izid, vendar ga ne pristransko.

Poleg teh lastnosti mora biti protokol učinkovit za izvajanje in ustvarjanje velikega števila naključnih bitov. (V praksi pogosto zadošča, da aplikacije proizvedejo 128 naključnih bitov in jih uporabijo za seme generatorja psevdonaključnih števil [PNRG], da izpiše več bitov, kot je potrebno. Vendar bi morala nepredvidljivost veljati za vsak posamezen bit izhoda, da bi bil uporaben za take aplikacije kot loterije ali dodeljevanje virov.) Protokol bi moral biti v idealnem primeru tudi učinkovit v smislu stroškov komunikacije in računanja.

Različni protokoli lahko dosežejo te lastnosti pod različnimi pogoji. Na primer, nekateri protokoli so lahko nepristranski za katero koli koalicijo f₁ zlonamerna vozlišča in nepredvidljiva s strani katere koli koalicije f₂<f₁ zlonamerna vozlišča. Obstajajo tudi različne stopnje pristranskosti. Na primer, v nekaterih protokolih lahko udeleženec pristransko izhod spremeni za "en bit" – kar pomeni, da lahko izbira med enim od dveh možnih izhodov. Drugi napadi jim lahko omogočijo, da v celoti popravijo rezultat. Običajno pa sploh ne želimo tolerirati nobene pristranskosti (ali predvidljivosti).

Kriptografski ideal: Rsvetilniki andomness

Kriptografi pogosto začnejo z razmišljanjem o idealni rešitvi svojih težav. V primeru javne naključnosti, a svetilnik naključnosti je idealizirana storitev, ki redno proizvaja naključne izhode, ki izpolnjujejo vse potrebne varnostne zahteve.

Tak idealiziran svetilnik naključnosti, podoben drugim kriptografskim abstrakcijam – kot so naključni oraklji ali generični skupinski model – v resničnem svetu ne obstaja. Toda to je koristen cilj, h kateremu si je treba prizadevati, in uporaben model za razlago o protokolih, ki se opirajo na javno naključnost. 

Upoštevamo lahko nekaj približkov idealnega svetilnika naključnosti.

• Centralizirani svetilniki: Najlažji pristop k ustvarjanju dobre naključnosti je prek centralizirane tretje osebe s storitvami, kot je NIST svetilnik naključnosti or random.org, ki ustvarja naključnost iz atmosferskega hrupa in je akreditiran za uporabo pri igrah na srečo. To zanašanje na tretjo osebo popolnoma spodkopava filozofijo decentralizacije. Dejansko moramo v zgornjem primeru verjeti, da ustrezne organizacije pravilno generirajo naključnost, brez kakršnega koli kriptografskega dokaza.
• Prikazi fizične naključnosti: Številne tradicionalne loterije temeljijo na javnem prikazovanju, ki lahko vključuje na primer nekoga, ki seže v posodo z žogicami za namizni tenis z različnimi številkami. Na žalost je s temi pogosto enostavno manipulirati. Na primer, določene kroglice lahko postavite v zamrzovalnik in selektorju lahko rečejo, naj izbere hladne.
• Naravni svetilniki: Pogosta ideja je uporaba naključnih naravnih pojavov, kot je vreme ali sevanje kozmičnega ozadja, kot svetilnik. Na žalost vsi predlagani viri ne zagotavljajo trdnega soglasja. Različni opazovalci bodo videli nekoliko drugačne vrednosti, kar zahteva ponovno uvedbo zaupanja vredne osebe za izvedbo uradne meritve z vsemi pomanjkljivostmi centraliziranega svetilnika.
• Polcentralizirani svetilniki: Boljši pristop bi bil pridobiti naključnost iz Glave blokov Bitcoin neposredno ali iz zaključne tečaje delnic, ki ga je lažje javno preveriti in ga ena stran težje popolnoma nadzoruje. Vendar še vedno obstajajo subtilni napadi na oba proof-of-work blockchain naključnost in naključnost cen delnic. Z glavami verige blokov se lahko na primer rudarji odločijo, da zadržijo bloke, katerih glave ustvarijo vrednost svetilnika, ki jim ni všeč. Lahko pa se odločijo, da prekinejo vezi, ko najdejo dva bloka, ki trčita, na podlagi njihovega želenega izhoda svetilnika.

Decentralizirani svetilniki naključnosti (DRB)

Naravni pristop k težavam centraliziranih svetilnikov je oblikovanje decentraliziranega kriptografskega protokola za ustvarjanje javne naključnosti. Ta problem je nekoliko podoben oblikovanju decentraliziranih protokolov soglasja, le da je težji. Ne samo, da se morajo vsi udeleženci strinjati glede izhoda (naključnost), ampak bi moralo biti nemogoče, da bi zlonamerni udeleženec v protokolu vplival ali napovedal izhod.

Protokoli, zasnovani za simulacijo svetilnika naključnosti, se imenujejo svetilniki porazdeljene naključnosti (DRB). (Druga imena vključujejo »porazdeljeno metanje kovancev«.) Težavo preučujejo že desetletja znameniti rezultati nezmožnosti, dokazani v osemdesetih letih, vendar se je zanimanje ponovno vzbudilo v dobi blockchaina. DRB bi lahko uporabili za zagotavljanje naključnosti v verigi, ki bi bila ključna sestavina poštenih, varnih in preglednih aplikacij v verigi.

Klasični pristop: protokoli za potrditev in razkritje

Za DRB v optimističnem primeru zadostuje zelo preprost dvokrožni protokol. V 1. krogu vsak udeleženec i ustvari naključno vrednost r_i in objavi kriptografsko zavezo c_i=Zaveza (r_i). V tej aplikaciji je lahko zaveza preprosto zgoščevalna funkcija, kot je SHA-256. Ko je zaveza vsakega udeleženca objavljena, je zaklenjen na svojo izbiro r_i, vendar zaveze ne razkrivajo nobenih informacij o prispevkih drugih udeležencev. V 2. krogu vsak udeleženec "odpre svojo obvezo" z objavo r_i. Vse naključne vrednosti se nato združijo, na primer z XOR-jem ali (po možnosti) z zgoščevanjem njihovega veriženja.

Ta protokol je preprost in proizvede naključen izhod svetilnika, dokler vsaj eden od udeležencev izbere svoj r_i naključno. Na žalost trpi zaradi klasične napake: ko vsi udeleženci razen enega razkrijejo svojo naključno vrednost, lahko zadnji udeleženec izračuna domnevni izhod svetilnika. Če jim ni všeč, lahko zavrnejo objavo svoje vrednosti in prekinejo protokol. Ignoriranje napačnega prispevka udeleženca ne odpravi težave, ker to še vedno daje napadalcu možnost izbire med dvema izhodoma svetilnika (enega izračunanega z njihovim prispevkom in enega brez).

Blockchains ponujajo naravno rešitev za to težavo: od vsakega udeleženca se lahko zahteva, da da nekaj sredstev v hrambo, ki so zasežena, če ne razkrije svojega naključnega prispevka. Točno tak pristop je ubrala klasika RANDAO svetilnik na Ethereumu. Slaba stran tega pristopa je, da je lahko izhod še vedno pristranski, kar se lahko napadalcu finančno izplača, če je denar v hrambi manjši od zneska denarja, ki temelji na rezultatu svetilnika. Boljša varnost pred pristranskimi napadi zahteva vlaganje več kovancev v hrambo.

Protokoli potrdi-razkrij-obnovi

Namesto da bi vse strani poskušali prisiliti, da razkrijejo svoj naključni prispevek, nekateri protokoli vključujejo obnovitveni mehanizem, tako da tudi če manjšina udeležencev izpade, lahko preostali dokončajo protokol. Pomembno je, da protokol daje enak rezultat v obeh primerih, tako da strani ne morejo pristransko vplivati ​​na rezultat z izbiro, ali bodo izstopile ali ne.

Eden od pristopov za dosego tega je, da vsak udeleženec drugim posreduje svoje skrivnosti, tako da jih lahko večina rekonstruira z uporabo, na primer, Shamirjeva delitev skrivnosti. Pomembna lastnost pa je, da lahko drugi preverijo, ali je bila odobrena skrivnost pravilno deljena, kar zahteva uporabo močnejšega primitivnega elementa, imenovanega javno preverljiva tajna delitev (PVSS).

Možnih je več drugih obnovitvenih mehanizmov, vendar imajo vsi enako omejitev. Če obstajajo N udeležencev in želimo odpornosti, če katera koli skupina do f vozlišča izpadejo, potem mora biti tako, da katera koli skupina Nf udeleženci lahko izračunajo končni rezultat. A to pomeni tudi zlonamerno koalicijo Nf udeleženci lahko vnaprej napovejo rezultat z zasebno simulacijo obnovitvenega mehanizma. To se lahko zgodi tudi med prvim krogom protokola, v tem času pa bi lahko taka koalicija spremenila svoje lastne naključne izbire in pristranska izid. 

Povedano drugače, to pomeni vsako koalicijo Nf vozlišča morajo vsebovati vsaj eno pošteno vozlišče. S preprosto algebro, Nf > fTako f < N/2, ti protokoli pa sami po sebi zahtevajo pošteno večino. To je pomembna razlika v primerjavi s prvotnim varnostnim modelom commit-reveal, ki zahteva samo f<N (vsaj en pošten udeleženec).

Ti protokoli pogosto zahtevajo znatne komunikacijske stroške za deljenje dodatnih informacij PVSS med vsemi vozlišči v vsakem zagonu protokola. Raziskovalna skupnost je v zadnjih nekaj letih opravila veliko dela na tem problemu, vključno z raziskovalnimi predlogi RandShare, Strgaj, SecRand, Herbali Albatross, vendar se zdi, da nobeden ni videl uvajanja v resničnem svetu.

Preverljivi protokoli, ki temeljijo na naključnih funkcijah

Ob spoznanju, da skupina Nf udeleženci lahko izračunajo naključno vrednost svetilnika v zgornjem protokolu vodi do nekoliko preprostejšega pristopa: delite dolgoročni skrivni ključ med N stranke in naj jih uporabijo za oceno a preverljiva naključna funkcija (VRF). Skrivni ključ se deli prek a t-izven-N mejna shema, tako da katera koli t udeleženci lahko izračunajo VRF (vendar manjša koalicija ne more). Za t=Nf, to zagotavlja enako odpornost na f zlonamerna vozlišča kot zgoraj obravnavani protokoli commit-reveal-recover.

DFINITET pionir tega pristopa kot del njihovega protokola soglasja z uporabo podpisov praga BLS (ki delujejo kot VRF). Samostojni vleči svetilnik naključnosti uporablja v bistvu enak pristop, z naborom udeležencev, ki v vsakem krogu podpišejo prag BLS in števec. The Liga entropije je odprtokodni primerek drand, ki proizvaja naključnost vsakih 30 sekund z uporabo 16 sodelujočih vozlišč (od septembra 2022), ki jih vodi mešanica podjetij in univerzitetnih raziskovalnih skupin. 

Slaba stran teh pristopov je, da je inicializacija ključa praga razmeroma zapletena, tako kot ponovna konfiguracija ključa, ko se vozlišča pridružijo ali zapustijo. V običajnem primeru pa so protokoli zelo učinkoviti. 

Kot je opisano zgoraj, preprosto podpisovanje protivrednosti ne doda nove naključnosti na krog, tako da, če je ogroženo zadostno število ključev udeležencev, bo protokol predvidljiv v vsakem prihodnjem krogu.

Chainlink VRF združuje ta pristop (z uporabo NSEC5 VRF) z zunanjim virom naključnosti, ki ga določijo strani, ki zahtevajo naključnost, kar je v praksi običajno nedavna glava verige blokov. Ti podatki se nato napajajo prek VRF, ki ga vodi bodisi ena stranka ali pa so pragovi za skupino.

Ethereum's Beacon veriga trenutno uporablja VRF-je, ki temeljijo na BLS: predlagatelj vsakega kroga mešanici doda svojo vrednost VRF. To prihrani krog komunikacije v primerjavi s paradigmo commit-reveal (ob predpostavki, da je dolgoročni javni ključ BLS registriran enkrat), čeprav ta zasnova podeduje nekaj opozoril pristopa commit-reveal, vključno z možnostjo pristranskosti izhoda svetilnika z zadrževanjem izhoda .

Protokoli, ki temeljijo na funkciji preverljive zakasnitve

Nazadnje, obetavna nova smer je uporaba časovno temelječe kriptografije, zlasti preverljivih funkcij zakasnitve (VDF-ji). Ta pristop obljublja dobro komunikacijsko učinkovitost in robustnost z odpornostjo na N-1 zlonamerna vozlišča. 

Če se vrnemo k izvirnemu protokolu za razkritje potrditev, lahko tradicionalne zaveze nadomestimo z časovno določene obveznosti odpraviti problem udeležencev, ki nočejo razkriti svojega naključnega prispevka. Časovno določene zaveze lahko učinkovito odpre izvirni izvršitelj ali kdorkoli, ki je pripravljen izračunati počasno funkcijo (v bistvu VDF). Torej, če kateri koli udeleženec izpade iz protokola za razkritje objave, lahko njegovo zavezo še vedno odprejo drugi. Bistveno je, da je minimalni čas za odpiranje zaveze dovolj dolg, da tega ni mogoče storiti med prvim krogom (faza potrditve) protokola, sicer bi lahko zlonamerni udeleženci dovolj hitro odprli zaveze drugih, da bi spremenili svoj prispevek in pristranski rezultat .

S sodobnimi VDF-ji je možen še bolj eleganten enokrožni protokol: popolnoma opustite obvezo. Vsak udeleženec lahko preprosto objavi svoj naključni prispevek r_i, končni rezultat pa je kombinacija prispevka vsakega udeleženca, ki poteka skozi VDF. Časovni zamik pri izračunu VDF zagotavlja, da nihče ne more izbrati svoje zaveze na način, ki bi vplival na končni rezultat. Ta pristop je bil predlagan kot UNICORN avtorja Arjena Lenstre in Benjamina Wesolowskega leta 2015 in je bila dejansko ključna motivacijska aplikacija v razvoj VDF-jev.

Ta pristop je doživel nekaj praktične uporabe. Chia implementira različico tega kot del svojega protokola soglasja z uporabo ponavljajočih se kvadratov VDF v skupinah razredov. Starkware izvedel a svetilnik, ki temelji na dokazu koncepta VDF z uporabo VDF-jev, ki temeljijo na SNARK. Ethereum tudi načrte uporabiti ta pristop, gradnjo namenskega ASIC-ja za računalništvo VDF-jev za generiranje naključnosti na ravni soglasja.

***

Javna naključnost je bistvena sestavina mnogih protokolov, vendar še vedno nimamo nobenega standardnega DRB, ki bi zagotavljal visoko varnost. Oblikovalski prostor je velik in možni so številni hibridi in kombinacije zgornjih pristopov. Na primer, mogoče je združiti protokol, ki temelji na VRF, s protokolom, ki temelji na VDF, kar na primer doda novo entropijo, kot je predlagal RandRunner. Ethereum's Beacon Chain trenutno uporablja VRF, čeprav bo morda v prihodnosti dodal VDF, da odpravi možnost pristranskosti zaradi napadov z zadrževanjem blokov.

Prav tako je odprto vprašanje, kdaj so sprejemljivi protokoli poštene večine. Za razmeroma majhno, preverjeno skupino udeležencev – kot je League of Entropy – je poštena predpostavka večine razumna. Po drugi strani pa imajo protokoli, ki zahtevajo samo enega poštenega udeleženca, lastno prednost – več udeležencev lahko le izboljša varnost. To pomeni, da je te protokole potencialno mogoče uvesti z odprtim sodelovanjem brez dovoljenj.

V drugem delu bomo razpravljali o specifični uporabi naključnih volitev vodje v protokolih soglasja, ki ima nekoliko drugačne cilje zasnove in je posledično videla še več predlaganih protokolov in pristopov.

***

Joseph Bonneau je raziskovalni partner pri a16z crypto. Njegove raziskave se osredotočajo na uporabno kriptografijo in varnost blockchaina. Poučeval je tečaje o kriptovalutah na Univerzi v Melbournu, NYU, Stanfordu in Princetonu ter prejel doktorat iz računalništva na Univerzi v Cambridgeu in diplomo BS/MS na Stanfordu.

Valerija Nikolaenko je raziskovalni partner pri a16z crypto. Njeno raziskovanje se osredotoča na kriptografijo in varnost blockchaina. Ukvarjala se je tudi s temami, kot so napadi na velike razdalje v soglasnih protokolih PoS, podpisne sheme, postkvantna varnost in večstransko računanje. Ima doktorat iz kriptografije na univerzi Stanford pod vodstvom profesorja Dana Boneha in je delala na verigi blokov Diem kot del osrednje raziskovalne skupine.

***

Editor: Tim Sullivan

***

Tukaj izražena stališča so stališča posameznega citiranega osebja družbe AH Capital Management, LLC (»a16z«) in niso stališča družbe a16z ali njenih podružnic. Nekatere informacije, vsebovane tukaj, so bile pridobljene iz virov tretjih oseb, vključno s portfeljskimi družbami skladov, ki jih upravlja a16z. Čeprav so vzeti iz virov, za katere menijo, da so zanesljivi, a16z ni neodvisno preveril takih informacij in ne daje nobenih zagotovil o trajni točnosti informacij ali njihovi ustreznosti za dano situacijo. Poleg tega lahko ta vsebina vključuje oglase tretjih oseb; a16z ni pregledal takšnih oglasov in ne podpira nobene oglaševalske vsebine v njih.

Ta vsebina je na voljo samo v informativne namene in se je ne smete zanašati kot pravni, poslovni, naložbeni ali davčni nasvet. Glede teh zadev se morate posvetovati s svojimi svetovalci. Sklici na katere koli vrednostne papirje ali digitalna sredstva so samo v ilustrativne namene in ne predstavljajo naložbenega priporočila ali ponudbe za zagotavljanje investicijskih svetovalnih storitev. Poleg tega ta vsebina ni namenjena nobenim vlagateljem ali bodočim vlagateljem niti ji ni namenjena in se nanjo v nobenem primeru ne smete zanašati, ko se odločate za vlaganje v kateri koli sklad, ki ga upravlja a16z. (Ponudba za vlaganje v sklad a16z bo podana le z memorandumom o zasebni plasiranju, pogodbo o vpisu in drugo ustrezno dokumentacijo katerega koli takega sklada in jo je treba prebrati v celoti.) Vse naložbe ali portfeljske družbe, omenjene, navedene ali opisane niso reprezentativne za vse naložbe v vozila, ki jih upravlja a16z, in ni nobenega zagotovila, da bodo naložbe donosne ali da bodo imele druge naložbe v prihodnosti podobne značilnosti ali rezultate. Seznam naložb skladov, ki jih upravlja Andreessen Horowitz (razen naložb, za katere izdajatelj ni dal dovoljenja a16z za javno razkritje, ter nenapovedanih naložb v digitalna sredstva, s katerimi se javno trguje), je na voljo na https://a16z.com/investments /.

Grafi in grafi, ki so navedeni znotraj, so izključno informativne narave in se nanje ne bi smeli zanašati pri sprejemanju kakršnih koli investicijskih odločitev. Pretekla uspešnost ni pokazatelj prihodnjih rezultatov. Vsebina govori samo od navedenega datuma. Vse projekcije, ocene, napovedi, cilji, obeti in/ali mnenja, izražena v tem gradivu, se lahko spremenijo brez predhodnega obvestila in se lahko razlikujejo ali so v nasprotju z mnenji, ki so jih izrazili drugi. Za dodatne pomembne informacije obiščite https://a16z.com/disclosures.