Juhuslike majakate ja muude strateegiate juhivalimised

Plokiahela seadistuses juhi valimise eesmärk on valida osaleja, kes määrab järgmise ploki, mis plokiahelasse lisatakse. Tavaliselt valitakse validaatorite komplektist iga pesa kohta üks validaator ja see saab õiguse pikendada ketti uue plokiga selles pesas. (Eeldame, et validaatorid hoiavad täpset aega ja lepivad kokku praeguse pesa numbriga.) Selles artiklis uurime strateegiaid juhuslikud juhivalimised konsensusprotokollides. (Lisateavet juhuslikkuse kohta üldiselt leiate meie varasemast artiklist, Avalikud juhuslikkuse ja juhuslikkuse majakad, Kus uurisime eraldiseisvaid protokolle avalikult kontrollitava ja ettearvamatu juhuslikkuse genereerimiseks.) 

Miks juhivalimine on oluline

Ausate ja aktiivsete juhtide valimine on keti terve kasvu jaoks ülioluline. Pahatahtlikud kinnitajad ei tohiks olla võimelised juhivalimiste protsessi kallutama, et end sagedamini liidriks saada. Vastasel juhul võib plokkide tootmine sattuda osapoolte kätte, kes saavad tehinguid tsenseerida või plokiahela üldse peatada. Pikima ahela stiilis konsensusprotokollide korral võib kehtetu ploki tekitav juht (või plokki üldse mitte) põhjustada ahela ajutise hargnemise. BFT-stiilis konsensusprotokollides käivitab halb juht vaate muutmise alamprotokolli, mis põhjustab sidekulusid. 

Komisjoni valimise alternatiiv

Komitee valimine on sellega seotud probleem, kus eesmärgiks on valida mingi kindla suurusega validaatoritest ühtlaselt juhuslik alamhulk k. See funktsioon on iseenesest kasulik, kuna plokiahela sätetes on sageli vaja alamkomiteesid, et vähendada validaatori komplekti suurust, et konsensus toimuks kiiremini (paljude näidete hulgas on Algorandi sorteerimine ja Ethereumi komitee valik). Kuid komisjonide valimine on kasulik ka juhi valimisel, võimaldades valideerijatel vältida juhi valimise protokolli uuesti läbiviimist, kui valitud juht ei ilmu kohale. Kui juhi asemel valitakse komisjon kindla järjekorraga, võib juhiks saada teine ​​komisjoniliige, kui esimest ei ole. 

Hea valimisprotokolli omadused

Juhi valimise protokollis peaksid juhid olema ettearvamatud. Kui ründaja saab teada, kes on tulevane juht, võib ta käivitada tema vastu teenuse keelamise (DoS) rünnaku, et takistada neil blokki avaldamast. Ründaja võib seejärel järgmise juhi maha võtta ja nii edasi, peatades plokiahela. Ettearvamatust võib samuti tugevdada tagamaks, et valideerija ise ei õpiks, millal ta hakkab juhtima, mis võib olla oluline altkäemaksu ennetamiseks.

Juhi valimise protsessil peaks olema kolm järgmist omadust:

• õiglus: iga ausa valideerija tõenäosus on 1/N olla valitud hulgast N validaatorid (leebe mõiste mänguteoreetiline õiglus lubab juhi valimised isegi pahatahtliku enamuse juuresolekul, ehkki voorude arvu mittekonstantse alampiiriga).
• Ettearvamatus: vastane õpib järgmise juhi selgeks alles mõne aja pärast T enne kui juht teatab järgmise ploki.
• unikaalsus: igas pesas valitakse täpselt üks juht.

Salajuhi valimised

Salajase juhi valimised on ettearvamatud valimised T = 0. Selles protsessis pole juht enne ploki avaldamist kellelegi teada. See välistab DoS-i rünnaku akna täielikult: enne kui juht end paljastab, ei tea ründaja, keda rünnata, mistõttu on tema parim strateegia juhuslik oletus. Ja pärast seda, kui juht on selle ploki avaldanud, on liiga hilja rünnata, sest juht on juba täitnud oma kohustuse protokolli ees. 

Mõiste "pärast seda, kui juht oma ploki avaldab" on tegelikult lihtsustus, sest meil pole reaalses maailmas hetkeülekannet. Tugeva võrgupositsiooniga ründaja võib märgata juhti, kes edastab ploki esimesena, ning suudab juhti kiiresti rikkuda, luua teistsuguse ploki ja juhtida algset edastust. 

Kuigi see on väga tugev ründaja mudel, on selle vastu pakutud kaitsemeetmeid. Algorand tegi ettepaneku kustutusmudel, milles juht saab tegelikult kustutada oma pesas oleva ploki allkirjastamiseks vajaliku võtme enne edastades seda, seega on tõesti liiga hilja rünnata selleks ajaks, kui juht avalikult tegutseb. Thaddeus Dryja, Quanquan C. Liu ja Neha Narula, kolm teadlast MIT Media Labist, pakutud et juht arvutaks enne levitamist oma ploki VDF-i, tagades, et adaptiivne ründaja ei suuda õigel ajal luua alternatiivset kehtivat plokki, et see soovitud pesa jaoks aktsepteeritaks.

Muud valimismeetodid 

Lihtsaim juhi valimise protsess on ümmargune röövel, kus juhid valitakse deterministlikus järjekorras. Vaatamata sellele, et selline lähenemine on prognoositav ja seetõttu kalduvus DoS-i rünnakutele, sobib see loaga süsteemidele, kus validaatoritel on hea DoS-kaitse.

Juhi saab valida ka välise väljundi abil juhuslikkuse majakas, kui see on saadaval ja usaldusväärne. Kahjuks on konsensuses osalejatel keeruline ise hajutatud juhuslikkuse majaka (DRB) protokolli käivitada, kuna need eeldavad tavaliselt usaldusväärset edastust või konsensust, mis omakorda nõuab uuesti juhi valimist, mis toob kaasa ringsõltuvuse.

Praegune juhivalimised Ethereumis on hea juhtumiuuring. Iga uus juht arvutab kontrollitava juhuslikkuse funktsiooni (VRF) väljundi (BLS-signatuur epohhinumbril) ja XOR-i väärtuse segusse. Segu väärtus epohhi lõpus i määratleb juhid ja alamkomiteed epohhi ajaks i+2. Juhid ja nende ajakava on etteaimatavad üks epohh ette (hetkel ~6.4 min). Protokoll on altid õigluse rünnakutele, kuna viimane juht võib otsustada, kas avaldab oma panuse segusse või jätab selle andmata ja seeläbi mõjutada järgmiste valimiste tulemust ühe biti võrra. Kui viimane  k juhid teevad kokku, võivad nad tutvustada k  erapoolikust ja muudavad pahatahtlike kasutajate valimise tõenäolisemaks. Ethereumi sihtasutus töötab aktiivselt juhtide valimise täiustatud tehnikate kallal, mida arutame allpool.

VRF-põhine juhivalimine

Teine lähenemine, mille teerajajaks Algorand, On VRF-põhine juhivalimine, mille käigus arvutab iga valideerija privaatselt välja VRF-i väljundi ja kontrollib, kas väljund langeb alla läve. See protseduur filtreerib juba välja enamiku valideerijatest, kuna lävi on valitud nii, et selle alla jäämine on ebatõenäoline. Mõned järelejäänud validaatorid näitavad oma VRF-väljundid ja valitakse see, mille VRF-väärtus on madalaim. Selline lähenemine saavutab täiusliku ettearvamatuse (või salastatuse), kuid see ei taga unikaalsust. Mõned valideerijad ei pruugi saada sõnumeid kõigilt potentsiaalsetelt juhtidelt ja võivad eeldada, et valimised võitis vale juht, mistõttu need valijad peaahelast hargnevad. 

VRF-i hindamine külvatakse perioodiliselt juhuslikkuse majaka väljundiga, et muuta valideerijatel endil vähem prognoositavaks näha, milliseid pesasid nad juhivad. See omadus takistab valijat vaikselt kompromiteerival ründajal õppida pesa, millal validaatorist saab juht, ja alustada rünnakut, kui validaator on blokist teatamas. Selline lähenemine aitab ära hoida ka altkäemaksurünnakuid, mille puhul valideerija tõestab välistele osapooltele, et ta on konkreetses teenindusajas liider, ja võtab altkäemaksu vastutasuks mõne juhiülesande täitmise (nt tehingu blokeerimise) eest.

Selliseid lähenemisviise, kus valitud juhtide arv on juhuslik suurus, nimetatakse Tõenäosuslikud juhivalimised (PLE). PLE võib kaasa tuua selle, et antud pesa jaoks ei valita ühtegi juhti. See on samaväärne pahatahtliku või võrguühenduseta juhi valimisega, kuna lõpuks jäetakse pesa vahele, vähendades konsensusprotokolli tõhusust.

Kuid PLE suurim hoiatus on see, et valitud võib olla mitu juhti, mistõttu on vaja mingit viimide katkestamise protseduuri. Sidemed ohustavad konsensust, kuna võitnud sisendiga valideerija võib sellest teada anda ainult poolele võrgust, mis võib põhjustada valitud juhis lahkarvamusi. Lisaks võivad sidemete lahendamise protsessid võtta lisaaega ja suhtlemist, kahjustades tõhusust. Dfinity, millest on üksikasjalikumalt arutatud esimene postitus selle seeria puhul kasutab VRF-põhist juhuslikkuse majakat ühe juhi valimiseks; selleks ohverdatakse aga ettearvamatus. Ideaalis peaks iga juhi valimise protsess täielikult vältima sidemeid ja olema siiski ettearvamatu, mis viib meid selle uurimisvaldkonna püha graalini – ühe salajase juhi valimiseni.

Üksiku salajuhi valimised 

Eesmärk Üksiku salajuhi valimised (SSLE) on valida validaatorite hulgast ainulaadne juht, säilitades samas õigluse ja ettearvamatuse. Protocol Labs esitas selle mõiste a uurimisprobleemja Stanfordi arvutiteadlane ja a16z krüptouuringute nõustaja Dan Boneh koos Saba Eskandariani, Lucjan Hanzliku ja Nicola Grecoga, keda hiljem pakkusid SSLE ametlik määratlus. See unikaalsuse omadus väldib konsensuse riske ja tõhususe kulusid, mis tulenevad võrdsuste katkestamise protseduuridest. Täpsemalt Sarah Azouvi, Protocol Labs ja Danielle Cappelletti, Politecnico di Torino, näitama et kui SSLE-d kasutatakse pikima ahela protokollis võrreldes PLE-ga, saab plokke oluliselt kiiremini lõpetada (25 protsenti kiiremini, kui vastane kontrollib kolmandikku osalusest). Seega on praktilise SSLE-protokolli väljatöötamine oluline probleem.

Kõige tavalisemas lähenemisviisis, mida me nimetame segamispõhine (kasutatakse nii algses SSLE-paberis kui ka Ethereumi SSLE ettepanek), iga validaator registreerib a nuntsius mis näib juhuslikult, kuid suudab tõestada, et see kuulub neile. Seejärel koostatakse nüansid loendisse. Loetelu segatakse nii, et mittemidagiütlevad elemendid ei ole seotud valideerijatega, kes need esitasid; see tähendab, et segatud loendit arvestades ei saa ükski vastane öelda, milline validaator millise nonce'i esitas. Seejärel valitakse avalikkuse järgi loendi register juhuslikkuse majakas, ja juht paljastab end, tõestades, et segatud loendi indeksis olev nonce kuulub neile. 

Kuna valitud on ainult üks indeks, väljastab segamispõhine protokoll alati a ainulaadne juht. Kuna juhuslik majakas on ehitatud ühtlaselt juhuslike väärtuste väljastamiseks, on ka protokoll õiglane: igal valideerijal on võrdne võimalus valituks osutuda. Veelgi enam, kui segamine on tehtud korralikult (st ühtlaselt juhuslikult) ja mittesaavutused muutuvad valideerijate identiteetidega sidumatuks, saavutab see protokoll ka ettearvamatus.

Segamine on vajalik, sest kuigi lihtsalt indeksi valimine segamata loendist juhusliku majaka põhjal annaks juba kordumatust ja õiglust, on ettearvamatust raskem saavutada: kui vastane teab, milline validaator millise nonce'i esitas, teab ta, kes esitas nonce'i valitud kohas. indeks ja suudab liidri tuvastada. 

Need kaks järgmist lähenemisviisi segavad loendit erineval viisil. Lihtsam on Ethereumi SSLE ettepanek, milles n valideerijad esitavad oma mittemidagiütlemised Tori kaudu, et lahutada valideerijate identiteedid nende mittevastavustest. Kui kõik valideerijad on registreerunud, segatakse loend avaliku juhuslikkuse majaka abil ja valideerijatest saavad segatud loendi järjekorras liidrid. Kuigi see skeem on praktiline, tuleb valimisi korraldada ainult üks kord n teenindusajad – Torile tuginemine võib olla ebasoovitav (nagu mis tahes välise protokolli turvalisusele tuginemise puhul). Pealegi pole see täiesti ettearvamatu: pärast esimest n-1 liidrid paljastavad end, finaal nth juht on teada.

Tori kasutamise asemel on algsel SSLE-paberil kõik validaatorid järjestikku registreeritud, lisades loendisse selle nonce'i, segades loendit ja uuesti randomiseerimine mittemidagiütlemised. See ümberjuhuslikuks muutmine tähendab, et iga nonde vastendatakse uueks, sidumatuks stringiks, nii et valideerija, kellele see kuulub, saab siiski tõestada, et see uuesti juhuslikult muudetud nonce kuulub. Juhusliku ümberkorraldamise tõttu ei saa vastane öelda, millisele positsioonile konkreetne nonce pärast segamist sattus, eeldades, et vähemalt üks segaja on aus.

Kuigi see algse SSLE paberi järjestikune segamisviis väldib Torile tuginemist ja saavutab SSLE formaalsed omadused, on see kallis: iga kord, kui registreerub uus valideerija, peab ta postitama kogu segatud loendi plokiahelasse, muutma kõik mittevajalikud juhused ja tõendama, et nad tegid seda ausalt, mille tulemuseks on lineaarne suhtluse hulk validaatori kohta. Muutumatu valideerijate komplekti korral tuleb seda teha (amortiseerida) üks kord valimiste jooksul, kuna juht registreerib end uuesti, kui on paljastanud tõendi selle kohta. Paber annab häälestatava tõhususe ja prognoositavuse kompromissi: selle asemel saame segada ainult väiksemat loendi alamhulka, vähendades kulusid, kui oleme valmis lubama väikest prognoositavust. Tõhususe ja turvalisuse vahelise hea tasakaalu saavutamine on keeruline ja seetõttu ei ole SSLE-protokolle praktikas veel laialdaselt kasutatud. 

Mugavalt saab seda järjestikuse segamise lähenemisviisi kasutada ka komitee valimise probleemi lahendamiseks, kasutades juhuslikku majakat, et valida nimekirjast komisjoni liikmeteks k erinevat indeksit. See on hea saavutus, kuna VRF-põhised lähenemisviisid ei lahenda probleemi triviaalselt, kuna tõenäosusliku VRF-põhise protokolli käitamine k korda võib sõltuvalt juhuslikkusest valida erineva suuruse komitee. 

Muud lähenemisviisid SSLE-le

Teine segamispõhine lähenemine on Kohanduvalt turvaline SSLE DDH-lt. See konstruktsioon on veidi keerulisem, kuid saavutab tugevama turvalisuse, kaitstes selle eest kohanemisvõimeline vastane Algorandi kustutusmudelis. See vastane on kohanemisvõimeline, kuna ta saab valida, milliseid valideerijaid protokolli ajal rikkuda, mitte enne protokolli käivitamist. 

Veel üks väljakutse SSLE-s on valida iga valideerija tõenäosusega, mis on proportsionaalne nende panusega, mitte ühtlaselt juhuslikult. Segamispõhised protokollid suudavad seda naiivselt saavutada, lubades igal validaatoril registreerida mitu nonce’i: üks nonce iga oma panuseühiku kohta. Segamise hind aga kasvab lineaarselt koos panuseühikute arvuga S, muutudes väga kalliks isegi realistlike panuste jaotuste puhul. Elegantne MPC-põhine SSLE lähenemise keerukus kasvab ainult logiga S, ja see väldib ka vajadust usaldusväärse seadistuse või juhuslikkuse majaka järele. Võrreldes segamispõhiste lähenemisviisidega nõuab see aga rohkem suhtlusringe (osalejate arvus logaritmiline) valitud juhi kohta

***

Oleme oma analüüsi kokku võtnud sellesse käepärasesse tabelisse.

	õiglus	ettearvamatus/ Saladus*	unikaalsus
Ring-robin	✓	✗	✓
Ideaalne juhuslikkuse-majakas	✓	✗	✓
Ethereumi juhi valimised (praegune)	✗	✗	✓
VRF-il põhinevad juhivalimised (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Ring-robin majakas on täielikult etteaimatav, kuid ülejäänud majakates ✗ tähendab, et mõiste saavutatakse teatud piiratud määral: ideaaljuhuslikkuse majakas on ettearvamatu, kuid vastane saab väljundi teada valitud juhiga samal ajal, seega võidakse valitud juhti rünnata enne, kui ta blokeeringust teatab; Etherumi majakas on kuni ~6 minutini ettearvamatu ja võib õigluse kahjustamiseks olla veidi kallutatud; Algorand valib väikese tõenäosusega mitu juhti.

SSLE on paljutõotav suund, mis saavutab õigluse, ettearvamatuse ja unikaalsuse. Selle kasutuselevõtu kaks silmapaistvat väljakutset on tõhusus ja võime kohandada panuste ebaühtlast jaotamist. Lisaks eeldavad meie esiletõstetud segamispõhised SSLE-lähenemised erapooletu juhusliku majaka olemasolu, mida pole praktikas lihtne saavutada. Kuna SSLE on ametlikult määratletud alles hiljuti, näeme tõenäoliselt lähitulevikus selle väljakutsetega tegelemiseks täiustatud protokolle. 

***

Miranda Kristus on Columbia ülikooli arvutiteaduse doktorant, kus ta on teooriarühma liige ja presidendi stipendiaat. Ta on ka a16z krüptouuringute praktikant.

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.