Izvolitev vodje iz svetilnikov naključnosti in drugih strategij

Namen volitev voditelja v nastavitvi blockchain je izbrati udeleženca, ki bo določil naslednji blok, ki bo pripet k blockchainu. Običajno je en validator izbran na režo iz niza validatorjev in dobi pravico razširiti verigo z novim blokom v tej reži. (Predvidevamo, da validatorji vodijo točen čas in se strinjajo s trenutno številko reže.) V tem članku raziskujemo strategije za naključne volitve vodje v protokolih soglasja. (Za več o naključnosti na splošno glejte naš prejšnji članek, Javna naključnost in svetilniki naključnosti, Kjer preučili smo samostojne protokole za generiranje javno preverljive in nepredvidljive naključnosti.) 

Zakaj so volitve vodje pomembne

Izvolitev poštenih in aktivnih vodij je ključnega pomena za zdravo rast verige. Zlonamerni potrjevalci ne bi smeli imeti pristranskosti postopka volitev vodje, da bi sami postali voditelji pogosteje. V nasprotnem primeru bi proizvodnja blokov lahko padla v roke strank, ki lahko cenzurirajo transakcije ali povsem ustavijo verigo blokov. V konsenznih protokolih v slogu najdaljše verige lahko vodja, ki ustvari neveljaven blok (ali ga sploh ni), povzroči začasno razcepitev verige. V konsenznih protokolih v slogu BFT slab vodja sproži podprotokol za spremembo pogleda, ki bo povzročil komunikacijske stroške. 

Alternativa volitve odbora

Izvolitev odbora je soroden problem, kjer je cilj izbrati enakomerno naključno podmnožico validatorjev neke fiksne velikosti k. Ta funkcionalnost je uporabna sama po sebi, ker so v nastavitvah verige blokov pogosto potrebni pododbori za zmanjšanje velikosti nabora validatorjev, da bi soglasje delovalo hitreje (med mnogimi primeri so Algorandova razvrstitev in Izbor komisije Ethereum). Toda izvolitev v odbor je uporabna tudi za izvolitev vodje, saj validatorjem omogoča, da se izognejo ponovnemu izvajanju protokola o volitvah vodje, če se izvoljeni vodja ne pojavi. Če je namesto vodje izvoljena komisija s fiksnim vrstnim redom, lahko drugi član komisije postane vodja, če prvi ni na voljo. 

Lastnosti dobrega volilnega protokola

V protokolu volitev voditeljev bi morali biti voditelji nepredvidljivi. Če napadalec izve, kdo je prihajajoči vodja, lahko nanj sproži napad z zavrnitvijo storitve (DoS), da prepreči objavo bloka. Napadalec bi lahko nato odstranil naslednjega vodjo in tako naprej, s čimer bi se veriga blokov ustavila. Nepredvidljivost se lahko tudi okrepi, da se zagotovi, da validator sam ne izve, kdaj bo vodil, kar je lahko pomembno za preprečevanje podkupovanja.

Postopek volitev vodje bi moral imeti naslednje tri lastnosti:

• Poštenost: vsak pošten validator ima verjetnost 1/N biti izvoljen iz niza N validatorji (sproščeno pojmovanje teoretična poštenost dopušča volitve vodje zgradbe tudi v prisotnosti zlonamerne večine, čeprav z nekonstantno spodnjo mejo števila krogov).
• Nepredvidljivost: nasprotnik šele čez nekaj časa spozna naslednjega vodjo T preden vodja napove naslednji blok.
• Edinstvenost: v vsaki reži je izbran natanko en vodja.

Tajne volitve vodje

Tajne volitve vodje so nepredvidljive volitve z T = 0. V tem procesu vodja ni znan nikomur, dokler ne objavi bloka. To popolnoma odstrani okno za napad DoS: preden se vodja razkrije, napadalec ne ve, koga bi napadel, zaradi česar je njegova najboljša strategija naključno ugibanje. In ko vodja objavi svoj blok, je za napad prepozno, ker je vodja že izpolnil svojo odgovornost do protokola. 

Pojem "potem ko vodja objavi svoj blok" je pravzaprav poenostavitev, ker v resničnem svetu nimamo takojšnjega oddajanja. Napadalec z močnim položajem v omrežju lahko opazi vodilnega, ki prvi oddaja blok, in lahko hitro pokvari vodilnega, ustvari drugačen blok in sproži prvotno oddajanje. 

Čeprav je to model zelo močnega napadalca, so bile proti njemu predlagane obrambe. Algorand je predlagal izbriše model, v katerem lahko vodja dejansko izbriše ključ, ki je potreben za podpis bloka v njegovi reži pred oddaja, tako da je res prepozno za napad do trenutka, ko vodja javno ukrepa. Thaddeus Dryja, Quanquan C. Liu in Neha Narula, trije raziskovalci iz MIT Media Lab, predlagano da vodilni izračuna VDF na svojem bloku pred oddajanjem, s čimer zagotovi, da prilagodljivi napadalec ne more pravočasno zgraditi nadomestnega veljavnega bloka, da bi bil sprejet za želeno režo.

Druge volilne metode 

Najenostavnejši postopek volitev vodje je okroglo-robin, kjer so voditelji izvoljeni po determinističnem vrstnem redu. Kljub temu, da je ta pristop predvidljiv in zato nagnjen k napadom DoS, je primeren za sisteme z dovoljenji, kjer imajo validatorji dobro zaščito DoS.

Vodja je lahko izvoljen tudi z izidom zunanjega svetilnik naključnosti, če je na voljo in je varen. Na žalost je za udeležence soglasja težavno, da sami zaženejo protokol porazdeljenega svetilnika naključnosti (DRB), saj ti običajno predpostavljajo pojem zanesljivega oddajanja ali soglasja, kar posledično zahteva ponovno izvolitev vodje, kar uvaja krožno odvisnost.

Trenutna volitve vodje v Ethereumu je dobra študija primera. Vsak novi vodja izračuna izhod funkcije preverljive naključnosti (VRF) (podpis BLS na številki epohe) in vrednost XOR uporabi v mešanici. Vrednost mešanice na koncu epohe i določa vodje in pododbore za čas trajanja epohe i+2. Voditelji in njihov urnik so predvidljivi eno epoho vnaprej (trenutno ~6.4 min). Protokol je nagnjen k napadom na poštenost, saj se lahko zadnji vodja odloči, da bo objavil ali zadržal svoj prispevek k mešanici in s tem vsaj malo vplival na rezultat naslednjih volitev. Če zadnji  k vodje se dogovarjajo, lahko uvedejo k  malo pristranskosti in poveča verjetnost izvolitve zlonamernih uporabnikov. Fundacija Ethereum aktivno dela na naprednejših tehnikah za volitve vodje, o katerih razpravljamo spodaj.

Volitve vodje na podlagi VRF

Drug pristop, pionir pri Algorand, Je Volitve vodje na podlagi VRF, ki vključuje vsak validator, ki zasebno izračuna izhod VRF in preveri, ali izhod pade pod prag. Ta postopek že filtrira večino validatorjev, saj je prag izbran tako, da padec pod njega ni verjeten. Nekaj ​​preostalih validatorjev razkrije svoje rezultate VRF in izvoljen je tisti z najnižjo vrednostjo VRF. S tem pristopom dosežemo popolno nepredvidljivost (ali tajnost), vendar ne zagotavljamo edinstvenosti. Nekateri validatorji morda ne bodo prejeli sporočil od vseh potencialnih vodij in lahko domnevajo, da je na volitvah zmagal napačen vodja, zaradi česar se ti validatorji odcepijo od glavne verige. 

Vrednotenje VRF se občasno doda izhodu svetilnika naključnosti, da je za validatorje manj predvidljivo, da vidijo, katere reže bodo vodili. Ta lastnost preprečuje, da bi napadalec, ki tiho ogrozi validator, izvedel režo, ko bi validator postal vodilni, in začel napad, ko je validator tik pred tem, da objavi blok. Ta pristop pomaga tudi pri preprečevanju napadov s podkupovanjem, kjer validator dokaže zunanjim stranem, da bo vodilni v določenem reženju, in pobira podkupnine v zameno za dokončanje neke naloge kot vodja (npr. blokiranje transakcije).

Takšni pristopi, kjer je število izvoljenih vodij naključna spremenljivka, se imenujejo Verjetnostne volitve vodje (PLE). PLE lahko povzroči, da za določeno mesto ni izvoljen noben voditelj. To je enakovredno izvolitvi vodje, ki je zlonameren ali brez povezave, saj bo reža na koncu preskočena, kar zmanjša učinkovitost protokola soglasja.

Toda največje opozorilo pri PLE je, da je lahko izvoljenih več voditeljev, kar zahteva nekakšen postopek za določanje izenačevanja. Izenačene povezave predstavljajo tveganje za soglasje, saj lahko validator z zmagovitim vnosom to sporoči le polovici omrežja, kar lahko povzroči nestrinjanje pri izbranem voditelju. Poleg tega lahko postopki za reševanje vezi zahtevajo več časa in komunikacije, kar škodi učinkovitosti. Dfinity, podrobneje obravnavano v prvo objavo te serije uporablja svetilnik naključnosti, ki temelji na VRF, za izvolitev enega vodje; vendar za to žrtvuje nepredvidljivost. V idealnem primeru bi se moral vsak postopek izbire vodje v celoti izogibati povezavam in bi bil še vedno nepredvidljiv, kar nas pripelje do svetega grala tega raziskovalnega področja – ene same tajne volitve vodje.

Enotne tajne volitve vodje 

Cilj Enotne tajne volitve vodje (SSLE) je izbrati edinstvenega vodjo iz nabora validatorjev, hkrati pa ohraniti pravičnost in nepredvidljivost. Protocol Labs je koncept predstavil kot a raziskovalni problem, in Dan Boneh, računalniški znanstvenik s Stanforda in svetovalec za raziskave kriptovalut a16z, s Sabo Eskandarian, Lucjanom Hanzlikom in Nicolo Greco, je kasneje ponudil formalna definicija SSLE. Ta lastnost edinstvenosti se izogne ​​tveganjem soglasja in stroškom učinkovitosti, ki izhajajo iz postopkov za določanje izenačevanja. Natančneje, Sarah Azouvi iz Protocol Labs in Danielle Cappelletti iz Politecnico di Torino, Prikaži da je pri uporabi SSLE v primerjavi s PLE v protokolu z najdaljšo verigo bloke mogoče dokončati bistveno hitreje (25 odstotkov hitreje, ko nasprotnik nadzoruje tretjino vložka). Zato je razvoj praktičnega protokola SSLE pomemben problem.

V najpogostejšem pristopu, ki ga bomo imenovali naključno (uporabljen tako v izvirnem dokumentu SSLE kot v predlog Ethereum SSLE), vsak validator registrira a nuncij ki je videti naključno, vendar lahko dokažejo, da pripada njim. Nonce se nato sestavijo v seznam. Seznam je premešan tako, da so nepovezane enote odstranjene od validatorjev, ki so jih predložili; to pomeni, da glede na premešan seznam noben nasprotnik ne more ugotoviti, kateri validator je predložil kateri nonce. Indeks seznama se nato izbere glede na javnost svetilnik naključnosti, vodja pa se razkrije tako, da dokaže, da nonce na tem indeksu premešanega seznama pripada njim. 

Ker je izbran samo en indeks, protokol, ki temelji na naključnem predvajanju, vedno izpiše a edinstven vodja. Ker je naključni svetilnik ustvarjen za izpis enakomerno naključnih vrednosti, je tudi protokol sejem: vsak validator ima enake možnosti, da je izvoljen. Nadalje, če je mešanje opravljeno pravilno (tj. enakomerno naključno) in postanejo nepovezane enote nepovezane z identitetami validatorjev, ta protokol prav tako doseže nepredvidljivost.

Premeščanje je potrebno, ker bi preprosta izbira indeksa z nepomešanega seznama na podlagi naključnega svetilnika že zagotovila edinstvenost in pravičnost, vendar je težje doseči nepredvidljivost: če nasprotnik ve, kateri potrjevalec je predložil kateri nonce, ve, kdo je predložil nonce ob izbranem indeks in lahko identificira vodjo. 

Ta naslednja dva pristopa premešata seznam na različne načine. Enostavnejši je Ethereum SSLE Predlog, v katerem n validatorji predložijo svoje nonce prek Tor, da prekinejo povezavo med identiteto validatorjev in njihovimi nonce. Ko so vsi validatorji registrirani, se seznam premeša z uporabo javnega svetilnika naključnosti in validatorji postanejo vodilni v vrstnem redu na premešanem seznamu. Čeprav je ta shema praktična – volitve morajo biti izvedene samo enkrat na dan n reže – to zanašanje na Tor je lahko nezaželeno (kot velja za zanašanje na varnost katerega koli zunanjega protokola). Poleg tega ni popolnoma nepredvidljiv: po prvem n-1 voditelji se razkrijejo, finale nth vodja je znan.

Namesto da bi uporabljal Tor, ima izvirni papir SSLE vsak register validatorjev za izvolitev v zaporedju, tako da doda svojo nonce na seznam, premeša seznam in ponovno randomiziranje nonces. Ta ponovna naključna razvrstitev pomeni, da je vsaka enkratna enota preslikana v nov niz, ki ga ni mogoče povezati, tako da validator, ki mu pripada, še vedno lahko dokaže lastništvo ponovno naključne enkratne enote. Ponovna naključna izbira omogoča, da nasprotnik ne more ugotoviti, na katerem položaju se je posamezen nonce znašel po premešanju, ob predpostavki, da je vsaj en premešalec pošten.

Medtem ko se ta pristop zaporednega mešanja iz prvotnega papirja SSLE izogne ​​zanašanju na Tor in doseže formalne lastnosti SSLE, je drag: vsakič, ko se registrira nov validator, mora objaviti celoten premešan seznam v verigi blokov, ponovno naključno razvrstiti vse nonce in zagotovijo dokaz, da so to storili pošteno, kar ima za posledico linearno količino komunikacije na validatorja. Z nespremenljivim naborom validatorjev je treba to narediti (amortizirati) enkrat na volitve, saj se vodja znova registrira, ko razkrije dokazilo za enkratno uporabo. Prispevek ponuja nastavljiv kompromis med učinkovitostjo in predvidljivostjo: namesto tega lahko premešamo le manjšo podmnožico seznama, s čimer zmanjšamo stroške, če smo pripravljeni dovoliti majhno količino predvidljivosti. Doseganje dobrega ravnovesja med učinkovitostjo in varnostjo je zahtevno, zato se protokoli SSLE v praksi še ne bodo široko uporabljali. 

Priročno je, da se ta pristop zaporednega mešanja lahko uporabi tudi za reševanje problema volitev v komisiji, tako da se z uporabo naključnega svetilnika izbere k različnih indeksov s seznama kot članov komisij. To je lep dosežek, saj problema ne rešijo trivialno s pristopi, ki temeljijo na VRF, saj se izvaja verjetnostni protokol, ki temelji na VRF. k lahko izberejo različno velikost odbora, odvisno od naključnosti. 

Drugi pristopi k SSLE

Drug pristop, ki temelji na premešanju, je Prilagodljivo zaščitite SSLE pred DDH. Ta konstrukcija je nekoliko bolj zapletena, vendar dosega močnejšo predstavo o varnosti, ščiti pred prilagodljiv nasprotnik v Algorandovem modelu izbrisov. Ta nasprotnik je prilagodljiv v tem smislu, da lahko izbere, katere validatorje bo pokvaril med protokolom, v nasprotju s tistimi pred začetkom protokola. 

Nadaljnji izziv pri SSLE je izbira vsakega validatorja z verjetnostjo, ki je sorazmerna z njihovim deležem, namesto enotno naključno. Protokoli, ki temeljijo na mešanju, lahko to naivno dosežejo tako, da vsakemu validatorju dovolijo, da registrira več nonce: enega nonce za vsako enoto deleža, ki jo ima. Vendar se stroški mešanja povečujejo linearno s številom enot vložka S, postanejo zelo drage celo pri realističnih razdelitvah deležev. Eleganten SSLE, ki temelji na MPC pristop ima kompleksnost, ki se povečuje samo z log S, poleg tega pa se izogne ​​potrebi po zaupanja vredni nastavitvi ali svetilniku naključnosti. Vendar pa v primerjavi s pristopi, ki temeljijo na mešanju, zahteva več krogov komunikacije (logaritmično glede na število udeležencev) na izvoljenega vodjo

***

Našo analizo smo strnili v to priročno tabelo.

	Poštenost	Nepredvidljivost/ Tajnost*	Edinstvenost
Round-robin	✓	✗	✓
Idealen svetilnik naključnosti	✓	✗	✓
Volitve vodje Ethereuma (trenutno)	✗	✗	✓
Volitve vodje na podlagi VRF (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Krožni svetilnik je popolnoma predvidljiv, vendar v ostalih svetilnikih ✗ pomeni, da je pojem dosežen do določene omejene stopnje: svetilnik idealne naključnosti je nepredvidljiv, vendar nasprotnik izve izhod istočasno z izvoljenim vodjo, zato je lahko izvoljeni vodja napaden, preden napove blok; Etherumov svetilnik je nepredvidljiv do ~6 minut in je lahko nekoliko pristranski, da škoduje pravičnosti; Algorand z majhno verjetnostjo izvoli več vodij.

SSLE je obetavna smer, ki dosega pravičnost, nepredvidljivost in edinstvenost. Dva pomembna izziva, s katerima se sooča njegovo sprejetje, sta učinkovitost in zmožnost prilagoditve neenakomerne porazdelitve deležev. Poleg tega pristopi SSLE, ki temeljijo na mešanju, ki jih izpostavljamo, predvidevajo obstoj nepristranskega naključnega svetilnika, česar v praksi ni enostavno doseči. Ker je bil SSLE uradno definiran šele pred kratkim, bomo verjetno v bližnji prihodnosti videli izboljšane protokole, ki bodo reševali njegove izzive. 

***

Miranda Kristus je doktorska študentka računalništva na Univerzi Columbia, kjer je članica Theory Group in predsedniška sodelavka. Je tudi raziskovalna pripravnica pri a16z crypto.

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.