Alegerea liderului de la Randomness Beacons și alte strategii

Alegerea liderului într-un cadru blockchain are ca scop selectarea participantului care va determina următorul bloc care urmează să fie atașat la blockchain. De obicei, un validator este ales per slot din setul de validatoare și primește dreptul de a extinde lanțul cu un nou bloc în acel slot. (Presumăm că validatorii păstrează ora exactă și convin asupra numărului de slot curent.) În acest articol explorăm strategii pentru alegerea aleatorie a liderului în protocoale de consens. (Pentru mai multe despre aleatorie în general, consultați articolul nostru anterior, Aleatorie publică și semnalizatoare ale aleatoriei, În cazul în care am analizat protocoale de sine stătătoare pentru generarea aleatoriei verificabile public și imprevizibile.) 

De ce contează alegerea liderului

Alegerea liderilor onești și activi este crucială pentru creșterea sănătoasă a lanțului. Validatorii rău intenționați nu ar trebui să poată influența procesul de alegere a liderilor pentru a deveni lideri mai des. În caz contrar, producția de blocuri ar putea cădea în mâinile părților care pot cenzura tranzacțiile sau pot opri complet blockchain-ul. În protocoalele de consens în stilul cel mai lung lanț, un lider care produce un bloc invalid (sau nici un bloc) ar putea face ca lanțul să se bifurcă temporar. În protocoalele de consens în stil BFT, un lider rău declanșează un subprotocol de modificare a vederii care va genera o suprasarcină de comunicare. 

Alternativa alegerii comisiei

Alegerea comisiei este o problemă conexă, în care scopul este de a selecta un subset uniform aleatoriu de validatori de o dimensiune fixă. k. Această funcționalitate este utilă în sine, deoarece subcomitetele sunt adesea necesare în setările blockchain pentru a reduce dimensiunea setului de validator pentru a face consensul să ruleze mai rapid (printre multe exemple sunt sortarea lui Algorand și Selecția comitetului Ethereum). Dar alegerea comisiei este utilă și pentru alegerea liderului, permițând validatorilor să evite reluarea unui protocol de alegere a liderului dacă liderul ales nu se prezintă. Dacă, în locul unui lider, un comitet este ales cu o ordine fixă, al doilea membru al comitetului poate deveni lider dacă primul nu este disponibil. 

Proprietățile unui protocol electoral bun

Într-un protocol de alegere a liderilor, liderii ar trebui să fie imprevizibili. Dacă un atacator află cine este viitorul lider, ar putea lansa un atac de tip Denial of Service (DoS) asupra lui pentru a-l împiedica să publice un blocaj. Atacatorul ar putea apoi să doboare următorul lider și așa mai departe, oprind blockchain-ul. Imprevizibilitatea ar putea fi, de asemenea, consolidată pentru a se asigura că validatorul însuși nu învață când va conduce, ceea ce ar putea fi important pentru prevenirea mituirii.

Procesul de alegere a liderului ar trebui să aibă următoarele trei proprietăți:

• Cinste: fiecare validator sincer are o probabilitate de 1/N a fi ales dintr-un set de N validatori (o noțiune relaxată de corectitudinea teoretică a jocului permite construirea alegerii liderului chiar și în prezența unei majorități rău intenționate, deși cu o limită inferioară neconstantă a numărului de tururi).
• imprevizibilitatea: adversarul nu-l învață pe următorul lider până la un timp T înainte ca liderul să anunţe următorul bloc.
• unicitatea: se alege exact un lider în fiecare slot.

Alegerea secretă a liderului

Alegerea secretă a liderului este o alegere imprevizibilă cu T = 0. În acest proces, liderul nu este cunoscut de nimeni până când nu publică blocul. Acest lucru elimină complet fereastra pentru un atac DoS: înainte ca liderul să se dezvăluie, atacatorul nu știe pe cine să atace, făcând cea mai bună strategie o ghicire aleatorie. Și după ce liderul își publică blocul, este prea târziu să atace pentru că liderul și-a îndeplinit deja responsabilitatea față de protocol. 

Noțiunea de „după ce liderul își publică blocul” este de fapt o simplificare, deoarece nu avem difuzare instantanee în lumea reală. Un atacator cu o poziție puternică în rețea ar putea observa un lider care difuzează mai întâi un bloc și poate să-l corupă rapid pe lider, să creeze un alt bloc și să difuzeze în avans difuzarea originală. 

Deși acesta este un model de atacator foarte puternic, au fost propuse apărări împotriva acestuia. Algorand a propus model de ștersături, în care liderul este efectiv capabil să șteargă cheia necesară semnării blocului în slotul său înainte difuzând-o, așa că este într-adevăr prea târziu pentru a ataca până când liderul ia vreo acțiune publică. Thaddeus Dryja, Quanquan C. Liu și, Neha Narula, trei cercetători de la MIT Media Lab, propus ca liderul să calculeze un VDF pe blocul său înainte de difuzare, asigurându-se că un atacator adaptiv nu poate construi un bloc alternativ valid la timp pentru a-l accepta pentru slotul dorit.

Alte metode de alegere 

Cel mai simplu proces de alegere a liderului este round robin, unde liderii sunt aleși în ordine deterministă. În ciuda faptului că această abordare este previzibilă și, prin urmare, este predispusă la atacuri DoS, este potrivită pentru sistemele autorizate în care validatorii au o bună protecție DoS.

Un lider poate fi ales și folosind o ieșire a unui extern far de aleatorie, dacă unul este disponibil și de încredere este sigur. Din păcate, este dificil pentru participanții la consens să ruleze ei înșiși un protocol de semnalizare aleatorie distribuită (DRB), deoarece acestea presupun de obicei o noțiune de difuzare fiabilă sau consens, care, la rândul său, necesită alegerea din nou a liderului, introducând o dependență circulară.

Curent alegerea liderului în Ethereum este un bun studiu de caz. Fiecare lider nou calculează o ieșire a funcției de aleatorie verificabilă (VRF) (o semnătură BLS pe ​​numărul epocii) și XOR face valoarea în amestec. Valoarea amestecului la sfârșitul epocii i defineşte conducătorii şi subcomitetele pe durata epocii i+2. Liderii și programul lor sunt previzibile cu o epocă înainte (în prezent ~6.4 min). Protocolul este predispus la atacuri de corectitudine, deoarece ultimul lider poate alege să publice sau să-și rețină contribuția la amestec și astfel să influențeze rezultatul următoarelor alegeri cu un pic. Dacă ultimul  k liderii se complică, pot introduce k  biți de părtinire și fac mai probabilă alegerea utilizatorilor rău intenționați. Fundația Ethereum lucrează activ la tehnici mai avansate de alegere a liderilor pe care le discutăm mai jos.

Alegerea liderului bazată pe VRF

O altă abordare, pionieră de Algorand, Este un Alegerea liderului bazată pe VRF, care implică fiecare validator să calculeze în mod privat o ieșire VRF și să verifice dacă ieșirea scade sub un prag. Această procedură filtrează deja majoritatea validatorilor, deoarece pragul este ales astfel încât să scadă sub acesta este puțin probabil. Puținii validatori rămași își dezvăluie ieșirile VRF, iar cel cu cea mai mică valoare VRF este ales. Această abordare realizează imprevizibilitatea (sau secretul) perfectă, dar nu garantează unicitatea. Unii dintre validatori ar putea să nu primească mesaje de la toți potențialii lideri și ar putea presupune că liderul greșit a câștigat alegerile, determinând acești validatori să iasă din lanțul principal. 

Evaluarea VRF este însămânțată periodic cu ieșirea unui semnal de aleatorie pentru a face mai puțin previzibil pentru validatorii înșiși să vadă ce sloturi vor conduce. Această proprietate împiedică un atacator care compromite în tăcere validatorul să învețe slotul când validatorul ar deveni lider și să lanseze un atac când validatorul este pe cale să anunțe un bloc. Această abordare ajută, de asemenea, la prevenirea atacurilor de mită, în cazul în care un validator demonstrează părților externe că va fi lider într-un anumit slot și recoltează mită în schimbul îndeplinirii unei sarcini ca lider (de exemplu, blocarea unei tranzacții).

Se apelează astfel de abordări, în care numărul de lideri aleși este o variabilă aleatorie Alegerea probabilistică a liderului (PLE). PLE poate duce la alegerea niciunui lider pentru un anumit loc. Acest lucru este echivalent cu alegerea unui lider care este rău intenționat sau offline, deoarece slotul va ajunge în cele din urmă să fie omis, reducând eficiența protocolului de consens.

Dar cea mai mare avertizare cu PLE este că ar putea fi aleși mai mulți lideri, ceea ce necesită un fel de procedură de departajare. Legăturile reprezintă un risc pentru consens, deoarece un validator cu o intrare câștigătoare îl poate raporta doar la jumătate din rețea, provocând potențial dezacord în liderul ales. În plus, procesele de rezolvare a legăturilor pot necesita timp suplimentar și comunicare, dăunând eficienței. Dfinity, discutat mai detaliat în primul post din această serie, folosește un semnal de aleatorie bazat pe VRF pentru a alege un singur lider; cu toate acestea, sacrifică imprevizibilitatea pentru a face acest lucru. În mod ideal, orice proces de alegere a unui lider ar trebui să evite în totalitate legăturile și să fie totuși imprevizibil, ceea ce ne conduce la sfântul Graal al acestei zone de cercetare – Alegerea unui singur lider secret.

Alegerea unui singur lider secret 

Scopul Alegerea unui singur lider secret (SSLE) este de a selecta un lider unic dintr-un set de validatori, menținând în același timp corectitudinea și imprevizibilitatea. Protocol Labs a prezentat noțiunea ca a problema cercetării, și Dan Boneh, informaticianul Stanford și consilier de cercetare criptografică a16z, împreună cu Saba Eskandarian, Lucjan Hanzlik și Nicola Greco, au oferit ulterior o definiție formală a SSLE. Această proprietate de unicitate evită riscurile de consens și costurile de eficiență care decurg din procedurile de departajare. Concret, Sarah Azouvi, de la Protocol Labs, și Danielle Cappelletti, de la Politecnico di Torino, Arăta că atunci când SSLE este utilizat în comparație cu PLE într-un protocol de lanț cel mai lung, blocurile pot fi finalizate semnificativ mai repede (cu 25 la sută mai rapid cu un adversar controlând o treime din miză). Astfel, dezvoltarea unui protocol practic SSLE este o problemă importantă.

În cea mai comună abordare, pe care o vom numi bazat pe amestecare (utilizat atât în ​​hârtia originală SSLE, cât și în o propunere Ethereum SSLE), fiecare validator înregistrează a nunțiu care pare aleatoriu, dar că pot dovedi că le aparține. Nonce-urile sunt apoi compilate într-o listă. Lista este amestecată astfel încât nonce-urile să fie deconectate de validatorii care le-au trimis; adică, având în vedere lista amestecată, niciun adversar nu poate spune care validator a trimis care nonce. Un index de listă este apoi ales în funcție de un public far de aleatorie, iar liderul se dezvăluie demonstrând că nonce la acel index al listei amestecate le aparține. 

Deoarece este ales un singur index, protocolul bazat pe shuffle produce întotdeauna a unic lider. Deoarece baliza aleatoare este construită pentru a scoate valori uniform aleatoare, protocolul este de asemenea echitabil: fiecare validator are șanse egale de a fi ales. În plus, dacă amestecarea se face corect (adică uniform la întâmplare) și nonce-urile devin nelegate de identitățile validatorilor, acest protocol realizează și imprevizibilitate.

Amestecarea este necesară deoarece, în timp ce simpla alegere a unui index din lista nemestecată pe baza unui semnal aleator ar oferi deja unicitate și corectitudine, imprevizibilitatea este mai greu de atins: dacă un adversar știe care validator a trimis care nonce, știe cine a trimis nonce la locul ales. indice și poate identifica liderul. 

Următoarele două abordări amestecă lista în moduri diferite. Cu cât este mai simplu Propunere Ethereum SSLEîn care n validatorii își trimit non-urile prin Tor pentru a deconecta identitățile validatorilor de non-urile lor. Odată ce toți validatorii s-au înregistrat, lista este amestecată folosind un semnal public de aleatorie, iar validatorii devin lideri în ordinea listei amestecate. Deși această schemă este practică – alegerile trebuie să fie organizate o singură dată pe fiecare n sloturi – această dependență de Tor poate fi nedorită (cum este cazul în care se bazează pe securitatea oricărui protocol extern). În plus, nu este perfect imprevizibil: după primul n-1 lideri se dezvăluie, finala nth liderul este cunoscut.

În loc să folosească Tor, lucrarea originală SSLE are fiecare registru de validare pentru alegere în secvență, adăugând nonce la listă, amestecând lista și re-randomizare noncele. Această re-randomizare înseamnă că fiecare nonce este mapat la un șir nou, de nelegat, astfel încât validatorul căruia îi aparține poate dovedi în continuare proprietatea nonce-ului re-randomizat. Re-randomizarea face ca un adversar să nu poată spune în ce poziție a ajuns un anumit nonce după amestecare, presupunând că cel puțin un amestecător este sincer.

În timp ce această abordare de amestecare secvențială din lucrarea originală SSLE evită dependența de Tor și atinge proprietățile formale ale SSLE, este costisitoare: ori de câte ori se înregistrează un nou validator, trebuie să posteze întreaga listă amestecată în blockchain, să re-randomizeze toate non-urile și să ofere o dovadă că au făcut acest lucru cinstit, ceea ce are ca rezultat o cantitate liniară de comunicare per validator. Cu un set neschimbat de validatori, acest lucru trebuie făcut (amortizat) o dată pe alegere, deoarece liderul se reînregistrează odată ce a dezvăluit dovada pentru nonce. Lucrarea oferă un compromis reglabil între eficiență și predictibilitate: putem în schimb să amestecăm doar un subset mai mic al listei, reducând costurile, dacă suntem dispuși să permitem o cantitate mică de predictibilitate. Atingerea unui echilibru bun între eficiență și securitate este o provocare și, în consecință, protocoalele SSLE nu sunt încă utilizate pe scară largă în practică. 

În mod convenabil, această abordare de amestecare secvențială poate fi folosită și pentru a rezolva problema alegerilor în comitet, folosind semnalul aleator pentru a alege k indici diferiți din listă ca membri ai comitetului. Aceasta este o realizare frumoasă, deoarece problema nu este rezolvată trivial prin abordări bazate pe VRF, deoarece rulează un protocol probabilist bazat pe VRF. k ori poate alege o dimensiune diferită a comitetului în funcție de aleatorie. 

Alte abordări ale SSLE

O altă abordare bazată pe amestecare este SSLE securizat adaptiv de la DDH. Această construcție este puțin mai complicată, dar realizează o noțiune mai puternică de securitate, protejând împotriva unei adversar adaptativ în modelul ştersărilor lui Algorand. Acest adversar este adaptabil prin faptul că poate alege ce validatori să corupă în timpul protocolului, spre deosebire de înainte de începerea protocolului. 

O altă provocare în SSLE este alegerea fiecărui validator cu probabilitatea proporțională cu miza lor, mai degrabă decât uniform la întâmplare. Protocoalele bazate pe amestecare pot realiza acest lucru în mod naiv, permițând fiecărui validator să înregistreze mai multe nonce: un nonce pentru fiecare unitate de miză pe care o dețin. Cu toate acestea, costul amestecării crește liniar cu numărul de unități de miză S, devenind foarte scump chiar și pentru distribuiri realiste de mize. Un elegant SSLE bazat pe MPC abordarea are complexitatea crescând doar cu log S, și, de asemenea, evită necesitatea unei configurații de încredere sau a unui semnal aleatoriu. Cu toate acestea, în comparație cu abordările bazate pe amestecare, necesită mai multe runde de comunicare (logaritmică în numărul de participanți) per lider ales.

***

Am rezumat analiza noastră în acest tabel la îndemână.

	Cinste	imprevizibilitate/ secret*	unicitatea
Round-robin	✓	✗	✓
Aleatorie-far ideal	✓	✗	✓
Alegerea liderului Ethereum (actuală)	✗	✗	✓
Alegerea liderului bazată pe VRF (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Farul round-robin este complet previzibil, dar în restul balizelor ✗ înseamnă că noțiunea este realizată până la un anumit grad limitat: farul ideal-aleatorie este imprevizibil, dar adversarul învață rezultatul în același timp cu liderul ales, prin urmare liderul ales poate fi atacat înainte de a anunța un blocaj; Baliza lui Etherum este imprevizibilă până la ~6 minute și poate fi ușor părtinitoare pentru a afecta corectitudinea; Algorand alege mai mulți lideri cu o probabilitate mică.

SSLE este o direcție promițătoare, care realizează corectitudinea, imprevizibilitatea și unicitatea. Două provocări proeminente cu care se confruntă adoptarea acestuia sunt eficiența și capacitatea de a permite distribuirea neuniformă a mizei. În plus, abordările SSLE bazate pe shuffle pe care le evidențiem presupun existența unui far aleatoriu imparțial, care nu este ușor de realizat în practică. Întrucât SSLE a fost definit oficial doar recent, este probabil să vedem protocoale îmbunătățite care abordează provocările sale în viitorul apropiat. 

***

Miranda Hristos este doctorand în Informatică la Universitatea Columbia, unde este membră a Theory Group și Presidential Fellow. Ea este, de asemenea, stagiar de cercetare la a16z crypto.

Joseph Bonneau este partener de cercetare la a16z crypto. Cercetările sale se concentrează pe criptografia aplicată și securitatea blockchain. A predat cursuri de criptomonedă la Universitatea din Melbourne, NYU, Stanford și Princeton și a primit un doctorat în informatică de la Universitatea din Cambridge și diplome de licență/MS de la Stanford.

Valeria Nikolaenko este partener de cercetare la a16z crypto. Cercetarea ei se concentrează pe criptografie și securitatea blockchain. Ea a lucrat, de asemenea, pe subiecte precum atacurile pe rază lungă în protocoalele de consens PoS, schemele de semnătură, securitatea post-cuantică și calculul cu mai multe părți. Ea deține un doctorat în criptografie de la Universitatea Stanford sub consilierea profesorului Dan Boneh și a lucrat la blockchain-ul Diem ca parte a echipei de cercetare de bază.

***

Editor: Tim Sullivan

***

Părerile exprimate aici sunt cele ale personalului individual AH Capital Management, LLC („a16z”) citat și nu sunt punctele de vedere ale a16z sau ale afiliaților săi. Anumite informații conținute aici au fost obținute din surse terțe, inclusiv de la companii de portofoliu de fonduri administrate de a16z. Deși este luat din surse considerate a fi de încredere, a16z nu a verificat în mod independent astfel de informații și nu face nicio declarație cu privire la acuratețea durabilă a informațiilor sau adecvarea lor pentru o anumită situație. În plus, acest conținut poate include reclame de la terți; a16z nu a revizuit astfel de reclame și nu aprobă niciun conținut publicitar conținut în acestea.

Acest conținut este furnizat doar în scop informativ și nu ar trebui să fie bazat pe consiliere juridică, de afaceri, de investiții sau fiscală. Ar trebui să vă consultați propriii consilieri cu privire la aceste aspecte. Referințele la orice titluri de valoare sau active digitale au doar scop ilustrativ și nu constituie o recomandare de investiții sau o ofertă de a oferi servicii de consiliere în materie de investiții. În plus, acest conținut nu este îndreptat și nici nu este destinat utilizării de către niciun investitor sau potențial investitor și nu poate fi bazat în nicio circumstanță atunci când se ia o decizie de a investi într-un fond administrat de a16z. (Ofertă de a investi într-un fond a16z va fi făcută numai prin memoriul de plasament privat, acordul de subscriere și alte documente relevante ale oricărui astfel de fond și trebuie citită în întregime.) Orice investiții sau companii de portofoliu menționate, la care se face referire sau descrise nu sunt reprezentative pentru toate investițiile în vehicule administrate de a16z și nu poate exista nicio asigurare că investițiile vor fi profitabile sau că alte investiții realizate în viitor vor avea caracteristici sau rezultate similare. O listă a investițiilor realizate de fondurile gestionate de Andreessen Horowitz (excluzând investițiile pentru care emitentul nu a oferit permisiunea ca a16z să dezvăluie public, precum și investițiile neanunțate în active digitale tranzacționate public) este disponibilă la https://a16z.com/investments /.

Diagramele și graficele furnizate în cadrul sunt doar în scop informativ și nu trebuie să se bazeze pe acestea atunci când se ia vreo decizie de investiție. Performanța trecută nu indică rezultatele viitoare. Conținutul vorbește doar de la data indicată. Orice previziuni, estimări, prognoze, obiective, perspective și/sau opinii exprimate în aceste materiale pot fi modificate fără notificare și pot diferi sau pot fi contrare opiniilor exprimate de alții. Vă rugăm să consultați https://a16z.com/disclosures pentru informații suplimentare importante.