Avalikud juhuslikkuse ja juhuslikkuse majakad

Avalik juhuslikkus on paljude reaalmaailma turvaprotokollide oluline komponent. Mõnes rakenduses, nagu hasartmängud ja mitme mängijaga mängud, lisab lõbusust juhuslikkus. Teistes rakendustes pakub juhuslikkus õiglast viisi mittejagatavate ressursside eraldamiseks, alates rohelistest kaartidest kuni ringkonnakohtu kohtunike määramiseni kohtuasjadesse ja lõpetades sporditurniiride külvamisega. Seda kasutatakse ka eraldamiseks negatiivne ressursse, nagu maksuauditid või teisene turvakontroll lennujaamas.

Traditsiooniliselt oleme nende protokollide juhuslikkuse loomiseks lootnud usaldusväärsetele asutustele, kuid web3 maailmas peame tegema paremini. Selles postituses uurime lähenemisviise, kuidas luua avalikult kontrollitavat juhuslikkust hajutatud juhuslikkuse majakad ja seejärel arutage mõningaid ketisiseseid rakendusi. (Peale ilmuvas II osas keskendutakse konkreetselt juhi valimistele, pakkudes samas hinnangut alternatiivsetele juhivalimisviisidele.) 

Soovitud omadused

Juhuslike arvude genereerimine on kurikuulsalt peen ülesanne. Näiteks on paljud krüptograafilised võtmed lekkinud, kuna need tugines vigasele juhuslike arvude generaatorile (mille jaoks Cloudflare'i sein laavalambid oleks olnud loominguline leevendus). See on lihtsalt privaatne juhuslikkusaga kui seda peab genereerima ja kasutama ainult üks osapool.

Avalik juhuslikkus on seevastu mitme osapoolega protsess, mis suurendab oluliselt raskusi. Heal protokollil avaliku juhuslikkuse loomiseks on järgmised turvaomadused:

• Erapooletu: ükski ründaja ega ründajate koalitsioon ei tohiks olla võimeline väljundit kallutama. 
• Usaldusväärne: ükski ründaja ei tohiks takistada protokolli väljundit.
• Kontrollitav: Igaüks saab hõlpsasti kontrollida protokolli väljundit ja peaks nägema sama väljundit nagu kõik teised.
• Ettearvamatu: Kui protokoll toodab väljundit ajal T₁, ei tohiks keegi enne mõnda aega väljundi kohta midagi ennustada T₀<T₁, ideaalis koos T₀ väga lähedal T₁.

Eelarvamusmatus on nõrgem omadus kui ettearvamatus, sest iga protokoll, mis on ettearvamatu, peab olema kallutamatu. Arvutiteadlased ütleksid erapooletust vähendab ettearvamatuseni, sest kui suudad kalduda, siis suudad ennustada. Kuid mõnikord tahame neid eraldi arutleda, sest nad võivad tugineda erinevatele eeldustele – näiteks võib ebaaus enamus ennustada tulemust, kuid mitte kallutada.

Lisaks nendele omadustele peaks protokoll olema efektiivne suure hulga juhuslike bittide käitamiseks ja tootmiseks. (Praktikas piisab sageli sellest, kui rakendused toodavad 128 juhuslikku bitti, kasutades neid pseudojuhuslike arvude generaatori [PNRG] külvamiseks, et vajadusel rohkem bitte väljastada. Siiski peaks ettearvamatus kehtima iga väljundi üksiku biti puhul, et seda saaks kasutada. loteriid või ressursside eraldamine.) Protokoll peaks ideaalis olema tõhus ka side- ja arvutuskulude osas.

Erinevad protokollid võivad need omadused erinevatel tingimustel saavutada. Näiteks võivad mõned protokollid olla ühegi koalitsiooni poolt erapooletud f₁ pahatahtlikud sõlmed ja mis tahes koalitsiooni jaoks ettearvamatud f₂<f₁ pahatahtlikud sõlmed. Samuti on erineval määral eelarvamusi. Näiteks võib mõnes protokollis osalejal olla võimalik väljundit "ühe biti" võrra kallutada – see tähendab, et nad saavad valida ühe kahest võimalikust väljundist. Muud rünnakud võivad võimaldada neil väljundit täielikult parandada. Tavaliselt ei taha me aga üldse sallida eelarvamusi (või etteaimatavust).

Krüptograafiline ideaal: Randomness majakad

Krüptograafid alustavad sageli sellest, et mõtlevad oma probleemidele ideaalsele lahendusele. Avaliku juhuslikkuse korral a juhuslikkuse majakas on idealiseeritud teenus, mis toodab regulaarselt juhuslikke väljundeid, mis vastavad kõigile vajalikele turvanõuetele.

Sellist idealiseeritud juhuslikkuse majakat, mis sarnaneb teiste krüptograafiliste abstraktsioonidega, nagu juhuslikud oraaklid või üldine rühmamudel, ei eksisteeri reaalses maailmas. Kuid see on kasulik eesmärk, mille poole püüelda, ja kasulik mudel avalikule juhuslikkusele tuginevate protokollide arutlemiseks. 

Võime kaaluda ideaalse juhuslikkuse majaka mõningaid lähendusi.

• Tsentraliseeritud majakad: Lihtsaim viis hea juhuslikkuse loomiseks on tsentraliseeritud kolmanda osapoole kaudu, millel on sarnased teenused NIST juhuslikkuse majakas or random.org, mis tekitab atmosfäärimürast juhuslikkust ja on hasartmängudes kasutamiseks akrediteeritud. See kolmandale osapoolele tuginemine õõnestab täielikult detsentraliseerimise filosoofiat. Tõepoolest, ülaltoodud näites peame usaldama, et asjaomased organisatsioonid genereerivad juhuslikkust õigesti, ilma krüptograafiliste tõenditeta.
• Kuvatakse füüsiline juhuslikkus: Paljud traditsioonilised loteriid põhinevad avalikul väljapanekul, mis võib hõlmata näiteks seda, kui keegi sirutab käe erinevate numbritega lauatennisepallide konteinerisse. Kahjuks on need sageli kergesti manipuleeritavad. Näiteks, teatud pallid võib panna sügavkülma ja valijal võib öelda, et vali külmad.
• Looduslikud majakad: Levinud idee on kasutada majakana juhuslikke loodusnähtusi, nagu ilm või kosmiline taustkiirgus. Kahjuks ei anna kõik pakutud allikad tugevat üksmeelt. Erinevad vaatlejad näevad veidi erinevaid väärtusi, mis nõuab ametliku mõõtmise tegemiseks usaldusväärse osapoole uuesti kasutuselevõttu koos kõigi tsentraliseeritud majaka puudustega.
• Pooltsentraliseeritud majakad: Parem lähenemine oleks juhuslikkuse hankimine Bitcoini ploki päised otse või sealt aktsiate sulgemishinnad, mida on lihtsam avalikult kontrollida ja mis tahes osapoolel raskem täielikult kontrollida. Siiski on mõlema suhtes endiselt peent rünnakut töötõendi plokiahela juhuslikkus ja aktsiahinna juhuslikkus. Näiteks plokiahela päiste puhul saavad kaevurid jätta kinni plokid, mille päised annavad majaka väärtuse, mis neile ei meeldi. Või võivad nad otsustada sidemed katkestada, kui leitakse kaks põrkuvat plokki, lähtudes nende eelistatud majaka väljundist.

Detsentraliseeritud juhuslikkuse majakad (DRB)

Loomulik lähenemine tsentraliseeritud majakate probleemidele on avaliku juhuslikkuse tekitamiseks detsentraliseeritud krüptograafilise protokolli kavandamine. See probleem sarnaneb mõneti detsentraliseeritud konsensusprotokollide kujundamisega, kuid raskem. Kõik osalejad ei pea mitte ainult väljundis (juhuslikkuses) kokku leppima, vaid ka pahatahtlikul protokollis osalejal peaks olema võimatu väljundit kallutada või ennustada.

Juhuslikkuse majaka simuleerimiseks loodud protokolle nimetatakse hajutatud juhuslikkuse majakateks (DRB). (Teised nimetused hõlmavad "hajutatud müntide viskamist".) Probleemi on uuritud aastakümneid, koos kuulsad võimatuse tulemused tõestasid 1980. aastatel, kuid huvi on plokiahela ajastul taas äratanud. DRB-sid saaks kasutada ahelasisese juhuslikkuse tagamiseks, mis oleks õiglaste, turvaliste ja läbipaistvate ahelasiseste rakenduste põhikomponent.

Klassikaline lähenemine: protokollid toime panevad ja paljastavad

Optimistlikul juhul piisab DRB jaoks väga lihtsast kaheringist protokollist. 1. voorus iga osaleja i genereerib juhusliku väärtuse r_i ja avaldab krüptograafilise kohustuse c_i=Kinnita(r_i). Selles rakenduses võib kohustus olla lihtsalt räsifunktsioon, näiteks SHA-256. Pärast iga osaleja kohustuse avaldamist jäävad nad oma valikusse r_i, kuid kohustused ei avalda mingit teavet teiste osalejate panuste kohta. 2. voorus avab iga osaleja oma kohustuse avaldamisega r_i. Seejärel kombineeritakse kõik juhuslikud väärtused, näiteks XOR-i või (eelistatavalt) nende konkatenatsiooni räsimise teel.

See protokoll on lihtne ja annab juhusliku majaka väljundi seni, kuni isegi üks osaleja valib oma r_i juhuslikult. Kahjuks on sellel klassikaline viga: kui kõik osalejad peale ühe on avaldanud oma juhusliku väärtuse, saab viimane osaleja arvutada oletatava majaka väljundi. Kui see neile ei meeldi, võivad nad keelduda oma väärtust avaldamast, katkestades protokolli. Vigase osaleja panuse ignoreerimine ei lahenda probleemi, sest see annab ründajale siiski valiku kahe majaka väljundi vahel (üks arvutatakse nende panusega ja teine ​​ilma).

Plokiahelad pakuvad sellele probleemile loomulikku lahendust: igalt osalejalt võidakse nõuda tingdeponeerimiskontot raha, mis arestitakse, kui ta oma juhuslikku panust ei avalda. Just sellise lähenemise võttis klassik RANDAO majakas Ethereumis. Selle lähenemisviisi negatiivne külg on see, et väljund võib siiski olla kallutatud, mis võib olla ründajale rahaliselt kasulik, kui tingdeponeerimisel olev raha on väiksem kui majaka tulemusel liikuv rahasumma. Parem turvalisus kallutatavate rünnakute vastu nõuab rohkem münte tingdeponeerimisse.

Kinnitamise-ilmutamise-taastamise protokollid

Selle asemel, et sundida kõiki osapooli oma juhuslikku panust avaldama, sisaldavad mõned protokollid taastamismehhanismi, nii et isegi kui osa osalejatest loobub, saavad ülejäänud protokolli täita. On oluline, et protokoll annaks mõlemal juhul sama tulemuse, et osapooled ei saaks tulemust kallutada, valides, kas loobuda või mitte.

Üks viis selle saavutamiseks on lasta igal osalejal anda teistele osa oma saladusest, nii et enamik neist saaks selle rekonstrueerida, kasutades näiteks Shamiri saladuste jagamine. Oluline omadus on aga see, et teised saavad kontrollida, kas antud saladus on õigesti jagatud, mis nõuab tugevama primitiivi kasutamist, mida nimetatakse avalikult kontrollitavaks saladuse jagamiseks (PVSS).

Võimalikud on ka mitmed muud taastamismehhanismid, kuid neil kõigil on samad piirangud. Kui neid on N osalejaid ja soovime vastupidavust, kui mõni kuni f sõlmed langevad välja, siis peab olema nii, et mis tahes rühm Nf osalejad saavad lõpptulemuse välja arvutada. Kuid see tähendab ka pahatahtlikku koalitsiooni Nf osalejad saavad tulemust ette ennustada, simuleerides privaatselt taastamismehhanismi. See võib juhtuda ka protokolli esimeses voorus, mille jooksul selline koalitsioon võib oma juhuslikkuse valikuid muuta ja tulemust kallutada. 

Teisisõnu tähendab see mis tahes koalitsiooni Nf sõlmed peavad sisaldama vähemalt ühte ausat sõlme. Lihtsa algebra järgi Nf > fnii f < N/2ja need protokollid nõuavad oma olemuselt ausat häälteenamust. See on märkimisväärne erinevus esialgsest commit-reveal turbemudelist, mis nõuab ainult f<N (vähemalt üks aus osaleja).

Need protokollid nõuavad sageli ka märkimisväärseid sidekulusid, et jagada PVSS-i lisateavet kõigi sõlmede vahel iga protokolli käitamise ajal. Teadusringkond on selle probleemiga viimastel aastatel palju tööd teinud, sealhulgas uurimisettepanekuid RandShare, Kraapima, SecRand, herbvõi Albatross, kuid näib, et ükski neist pole reaalset kasutuselevõttu näinud.

Kontrollitavad juhuslikud funktsioonipõhised protokollid

Mõistes, et rühm Nf osalejad saavad ülaltoodud protokollis arvutada juhusliku majaka väärtuse, mis viib mõnevõrra lihtsama lähenemiseni: jagage pikaajalist salavõtit N pooled ja lasta neil seda kasutada a hindamiseks kontrollitav juhuslik funktsioon (VRF). Salavõtit jagatakse läbi a t-otsas-N läve skeem, nii et mis tahes t osalejad saavad VRF-i arvutada (kuid väiksem koalitsioon ei saa). Sest t=Nf, tagab see sama vastupidavuse f pahatahtlikud sõlmed nagu ülalpool käsitletud commit-reveal-taaste protokollid.

LÕPLIKKUS selle lähenemisviisi pioneeriks osana nende konsensusprotokollist, kasutades läviväärtusega BLS-i allkirju (mis toimivad VRF-ina). Eraldi vedama juhuslikkuse majakas kasutab sisuliselt sama lähenemisviisi, kus osalejate kogum on igas voorus threshold-BLS-allkirjaga loendur. The Entroopia liiga on drandi avatud lähtekoodiga eksemplar, mis loob juhuslikkuse iga 30 sekundi järel, kasutades 16 osalevat sõlme (2022. aasta septembri seisuga), mida juhivad mitmed ettevõtted ja ülikoolide uurimisrühmad. 

Nende lähenemisviiside negatiivne külg on see, et lävevõtme lähtestamine on suhteliselt keeruline, nagu ka võtme ümberkonfigureerimine sõlmede liitumisel või lahkumisel. Üldjuhul on protokollid aga väga tõhusad. 

Nagu ülalpool kirjeldatud, ei lisa loenduri väärtuse allkirjastamine vooru kohta uut juhuslikkust, nii et kui piisav arv osalejate võtmeid on ohus, on protokoll igas järgmises voorus ennustatav.

Ketilüli VRF ühendab seda lähenemisviisi (kasutades NSEC5 VRF) välise juhuslikkuse allikaga, mille on määranud juhuslikkust taotlevad osapooled, mis on praktikas tavaliselt hiljutine plokiahela päis. Need andmed edastatakse seejärel VRF-i kaudu, mida haldab üks osapool või mis on piiratud rühmale.

Ethereumi omad Majakakett kasutab praegu BLS-põhiseid VRF-e: iga vooru ettepaneku tegija lisab segule oma VRF-i väärtuse. See säästab suhtlusringi võrreldes commit-reveal paradigmaga (eeldusel, et pikaajaline BLS-i avalik võti registreeritakse üks kord), kuigi see kujundus pärib mõningaid kinnistamis-ilmutamise lähenemisviisi hoiatusi, sealhulgas võimalust kallutada majaka väljundit väljundi kinnipidamisega. .

Kontrollitavad viivitusfunktsioonipõhised protokollid

Lõpuks on paljutõotav uus suund ajapõhise krüptograafia, täpsemalt kontrollitavate viivitusfunktsioonide kasutamine (VDF-id). See lähenemine tõotab pakkuda head suhtlustõhusust ja tugevust ning vastupidavust N-1 pahatahtlikud sõlmed. 

Tulles tagasi algse toimepanemise ja ilmutamise protokolli juurde, saab traditsioonilised kohustused asendada ajastatud kohustused kõrvaldada probleem, et osalejad keelduvad avaldamast oma juhuslikku panust. Ajastatud kohustusi saab tõhusalt avada algne volitaja või igaüks, kes on valmis arvutama aeglase funktsiooni (põhiliselt VDF). Seega, kui mõni osaleja commit-reveal protokollist välja langeb, saavad teised siiski tema pühendumust avada. On oluline, et kohustuse avamise minimaalne aeg oleks piisavalt pikk, et seda ei saaks teha protokolli esimese vooru (kohustuse faasi) ajal, vastasel juhul võivad pahatahtlikud osalejad avada teiste kohustused piisavalt kiiresti, et muuta oma panust ja moonutada tulemust. .

Kaasaegsete VDF-idega on võimalik veelgi elegantsem üheringiline protokoll: loobuge täielikult. Iga osaleja saab lihtsalt oma juhusliku panuse avaldada r_ija lõpptulemus on kombinatsioon iga osaleja panusest, mis jookseb läbi VDF-i. Ajaline viivitus VDF-i arvutamisel tagab, et keegi ei saa valida oma kohustust viisil, mis kallutab lõppväljundit. Seda lähenemisviisi pakuti välja kui UNICORN Arjen Lenstra ja Benjamin Wesolowski 2015. aastal ning see oli tõepoolest peamine motiveeriv rakendus VDF-ide arendamine.

Seda lähenemisviisi on praktiliselt rakendatud. Chia rakendab selle versiooni osana oma konsensusprotokollist, kasutades klassirühmades korduvaid ruudukujulisi VDF-e. Starkware rakendatud a kontseptsiooni tõestus VDF-põhine majakas kasutades SNARK-põhiseid VDF-e. Ethereum ka plaanid kasutada seda lähenemist, luues spetsiaalse ASIC-i VDF-ide arvutamiseks, et luua konsensuskihis juhuslikkust.

***

Avalik juhuslikkus on paljude protokollide oluline komponent, kuid meil puudub endiselt standardne DRB, mis tagaks kõrge turvalisuse. Disainiruum on suur ja võimalikud on paljud ülaltoodud lähenemisviiside hübriidid ja kombinatsioonid. Näiteks on võimalik kombineerida VRF-põhist protokolli VDF-põhise protokolliga, mis lisab näiteks värsket entroopiat, nagu soovitas RandRunner. Ethereumi majakakett kasutab praegu VRF-e, kuigi see võib tulevikus lisada VDF-e, et välistada tõkestamise rünnakute nihke võimalus.

Samuti on lahtine küsimus, millal ausa enamuse protokollid on vastuvõetavad. Suhteliselt väikese, kontrollitud osalejate rühma jaoks – nagu Entroopia Liiga – on aus enamuse eeldus mõistlik. Teisest küljest on protokollidel, mis nõuavad ainult ühte ausat osalejat, omane eelis – rohkem osalejaid saab turvalisust ainult parandada. See tähendab, et neid protokolle saab potentsiaalselt juurutada avatud ja loata osalemisega.

II osas käsitleme juhuslike juhivalimiste spetsiifilist rakendamist konsensusprotokollides, millel on veidi erinevad disainieesmärgid ja mille tulemusena on pakutud veelgi rohkem protokolle ja lähenemisviise.

***

Joseph Bonneau on a16z krüptouuringute partner. Tema uurimistöö keskendub rakenduslikule krüptograafiale ja plokiahela turvalisusele. Ta on õpetanud krüptoraha kursusi Melbourne'i ülikoolis, NYU-s, Stanfordi ja Princetoni ülikoolis ning saanud Cambridge'i ülikoolist arvutiteaduse doktorikraadi ja Stanfordist BS/MS kraadi.

Valeria Nikolaenko on a16z krüptouuringute partner. Tema uurimistöö keskendub krüptograafiale ja plokiahela turvalisusele. Ta on töötanud ka selliste teemadega nagu kaugrünnakud PoS-i konsensusprotokollides, allkirjaskeemid, kvantijärgne turvalisus ja mitme osapoole arvutus. Tal on doktorikraad krüptograafias Stanfordi ülikoolist professor Dan Boneh' juhendamisel ja ta töötas Diem'i plokiahela kallal osana uurimisrühmast.

***

Toimetaja: Tim Sullivan

***

Siin väljendatud seisukohad on tsiteeritud AH Capital Management, LLC (“a16z”) üksikute töötajate seisukohad, mitte a16z ega tema sidusettevõtete seisukohad. Teatud siin sisalduv teave on saadud kolmandate osapoolte allikatest, sealhulgas a16z hallatavate fondide portfelliettevõtetelt. Kuigi a16z on võetud usaldusväärsetest allikatest, ei ole a16z sellist teavet sõltumatult kontrollinud ega kinnita teabe püsivat täpsust ega selle sobivust antud olukorras. Lisaks võib see sisu sisaldada kolmandate isikute reklaame; aXNUMXz ei ole selliseid reklaame üle vaadanud ega toeta neis sisalduvat reklaamisisu.

See sisu on esitatud ainult informatiivsel eesmärgil ja sellele ei tohiks tugineda kui juriidilisele, äri-, investeerimis- ega maksunõustamisele. Nendes küsimustes peaksite konsulteerima oma nõustajatega. Viited mis tahes väärtpaberitele või digitaalsetele varadele on illustratiivse tähendusega ega kujuta endast investeerimissoovitust ega investeerimisnõustamisteenuste pakkumist. Lisaks ei ole see sisu suunatud ega mõeldud kasutamiseks ühelegi investorile ega potentsiaalsetele investoritele ning sellele ei tohi mingil juhul tugineda, kui tehakse otsus investeerida a16z hallatavasse fondi. (A16z fondi investeerimise pakkumine tehakse ainult sellise fondi erainvesteeringute memorandumi, märkimislepingu ja muu asjakohase dokumentatsiooni alusel ning neid tuleks lugeda tervikuna.) Kõik mainitud, viidatud investeeringud või portfelliettevõtted või kirjeldatud ei esinda kõiki a16z hallatavatesse sõidukitesse tehtud investeeringuid ning ei saa olla kindlust, et investeeringud on tulusad või et teised tulevikus tehtavad investeeringud on sarnaste omaduste või tulemustega. Andreessen Horowitzi hallatavate fondide tehtud investeeringute loend (v.a investeeringud, mille kohta emitent ei ole andnud A16z-le luba avalikustada, samuti etteteatamata investeeringud avalikult kaubeldavatesse digitaalvaradesse) on saadaval aadressil https://a16z.com/investments /.

Siin esitatud diagrammid ja graafikud on üksnes informatiivsel eesmärgil ja neile ei tohiks investeerimisotsuse tegemisel tugineda. Varasemad tulemused ei näita tulevasi tulemusi. Sisu räägib ainult märgitud kuupäeva seisuga. Kõik nendes materjalides väljendatud prognoosid, hinnangud, prognoosid, eesmärgid, väljavaated ja/või arvamused võivad muutuda ilma ette teatamata ning võivad erineda või olla vastuolus teiste väljendatud arvamustega. Olulist lisateavet leiate aadressilt https://a16z.com/disclosures.