Aleatorie publică și semnalizatoare ale aleatoriei

Aleatorie publică este o componentă esențială a multor protocoale de securitate din lumea reală. În unele aplicații, cum ar fi jocurile de noroc și jocurile multiplayer, aleatorietatea adaugă distracție. În alte aplicații, aleatorietatea oferă o modalitate echitabilă de a aloca resurse nedivizibile, variind de la cărți verzi, până la atribuirea judecătorilor de la tribunale de circuit la cazuri, până la seeding în turneele sportive. Este folosit și pentru a aloca negativ resurse, cum ar fi audituri fiscale sau control secundar de securitate la aeroport.

În mod tradițional, ne-am bazat pe autorități de încredere pentru a genera aleatoriu pentru aceste protocoale, dar în lumea web3, va trebui să facem mai bine. În această postare, vom explora abordări pentru construirea aleatoriei verificabile public prin balize aleatorii distribuite și apoi discutați câteva aplicații în lanț. (Partea a II-a, care urmează să apară, se va concentra în mod special pe alegerea liderului, oferind în același timp o evaluare a abordărilor privind alegerea liderului alternativ.) 

Proprietăți dorite

Generarea de numere aleatorii este o sarcină notoriu de subtilă. De exemplu, multe chei criptografice au fost scurse deoarece acestea sa bazat pe un generator de numere aleatoare defect (pentru care peretele lui Cloudflare de lămpi de lavă ar fi servit drept atenuare creativă). Doar asta aleatorie privată, totuși, unde doar o singură parte trebuie să-l genereze și să-l folosească.

Aleatoria publică, dimpotrivă, este un proces multipartid, care adaugă considerabil la dificultate. Un protocol bun pentru producerea aleatoriei publice va avea următoarele proprietăți de securitate:

• Imposibil: Niciun atacator sau coaliție de atacatori nu ar trebui să poată influența rezultatul. 
• Sigur: Niciun atacator nu ar trebui să poată împiedica protocolul să producă rezultate.
• verificabil: Oricine poate verifica cu ușurință ieșirea protocolului și ar trebui să vadă aceeași ieșire ca toți ceilalți.
• Imprevizibil: Dacă protocolul produce rezultate la timp T₁, nimeni nu ar trebui să poată prezice nimic despre rezultat înainte de ceva timp T₀<T₁, ideal cu T₀ foarte aproape de T₁.

Imposibilitatea este o proprietate mai slabă decât imprevizibilitatea, deoarece orice protocol care este imprevizibil trebuie să fie imparțial. Informaticienii ar spune imparțialitate reduce la imprevizibilitate, pentru că dacă poți părtini, poți prezice. Dar uneori vom dori să raționăm despre ele separat, deoarece se pot baza pe ipoteze diferite – de exemplu, o majoritate necinstită ar putea prezice rezultatul, dar nu îl părăsește.

În plus față de aceste proprietăți, protocolul ar trebui să fie eficient pentru a rula și a produce un număr mare de biți aleatori. (În practică, este adesea suficient ca aplicațiile să producă 128 de biți aleatori, folosindu-i pentru a genera un generator de numere pseudoaleatoare [PNRG] pentru a scoate mai mulți biți după cum este necesar. Cu toate acestea, impredictibilitatea ar trebui să fie valabilă pentru fiecare bit individual al ieșirii pentru a fi utilizabil pentru astfel de aplicații ca loterii sau alocări de resurse.) În mod ideal, protocolul ar trebui să fie eficient și în ceea ce privește costurile de comunicare și de calcul.

Protocoale diferite ar putea atinge aceste proprietăți în condiții diferite. De exemplu, unele protocoale ar putea fi nepărtinitoare de către orice coaliție de f₁ noduri rău intenționate și imprevizibile de orice coaliție de f₂<f₁ noduri rău intenționate. Există, de asemenea, diferite grade de părtinire. De exemplu, în unele protocoale, un participant ar putea fi capabil să polarească ieșirea cu „un bit” – ceea ce înseamnă că poate alege între una dintre cele două ieșiri posibile. Alte atacuri le-ar putea permite să repare complet rezultatul. În mod obișnuit, totuși, nu vrem să tolerăm deloc nicio părtinire (sau predictibilitate).

Idealul criptografic: Rbalize de andomness

Criptografii încep adesea prin a se gândi la o soluție ideală pentru problemele lor. În cazul aleatoriei publice, a far de aleatorie este un serviciu ideal care produce în mod regulat rezultate aleatorii care satisfac toate cerințele de securitate necesare.

Un astfel de far idealizat de aleatorie, similar cu alte abstracții criptografice – cum ar fi oracolele aleatorii sau modelul de grup generic – nu există în lumea reală. Dar este un obiectiv util spre care să lupți și un model util pentru a raționa despre protocoalele care se bazează pe aleatorietatea publicului. 

Putem lua în considerare câteva aproximări ale unui far ideal de aleatorie.

• Balize centralizate: Cea mai ușoară abordare pentru a genera aleatorie bună este printr-o terță parte centralizată cu servicii precum Far de aleatorie NIST or random.org, care generează aleatoriu din zgomotul atmosferic și este acreditat pentru utilizare în jocuri de noroc. Această dependență de un terț subminează complet filosofia descentralizării. Într-adevăr, în exemplul de mai sus trebuie să avem încredere că organizațiile relevante generează aleatoriu corect, fără nicio dovadă criptografică.
• Afișări aleatorii fizice: Multe loterie tradiționale se bazează pe o afișare publică, care ar putea include, de exemplu, cineva care ajunge într-un recipient cu mingi de ping pong cu numere diferite pe ele. Din păcate, acestea sunt adesea ușor de manipulat. De exemplu, anumite bile pot fi puse la congelator și selectorului i se poate spune să aleagă pe cele reci.
• Balize naturale: O idee comună este utilizarea fenomenelor naturale aleatorii, cum ar fi vremea sau radiația de fundal cosmică ca far. Din păcate, toate sursele propuse nu oferă un consens puternic. Diferiți observatori vor vedea valori ușor diferite, ceea ce necesită reintroducerea unei părți de încredere pentru a efectua o măsurare oficială, cu toate dezavantajele unui far centralizat.
• Balize semicentralizate: O abordare mai bună ar fi să obțineți aleatoriu de la Antete bloc Bitcoin direct sau din prețurile de închidere ale acțiunilor, care este mai ușor de verificat public și mai dificil de controlat complet de către oricare dintre părți. Cu toate acestea, atacuri subtile încă există asupra ambelor aleatorietatea blockchain-ului dovadă de lucru și aleatorietatea acțiunilor-preț. Cu anteturile blockchain, de exemplu, minerii pot alege să rețină blocurile ale căror anteturi produc o valoare far care nu le place. Sau pot alege să rupă legăturile atunci când sunt găsite două blocuri care se ciocnesc pe baza ieșirii lor preferate de far.

Indicatoare aleatorii descentralizate (DRB)

O abordare naturală a problemelor balizelor centralizate este proiectarea unui protocol criptografic descentralizat pentru producerea aleatoriei publice. Această problemă este oarecum ca proiectarea protocoalelor de consens descentralizate, doar că mai grea. Nu numai că toți participanții trebuie să cadă de acord asupra unui rezultat (aleatorie), dar ar trebui să fie imposibil ca un participant rău intenționat la protocol să părăsească sau să prezică rezultatul.

Protocoalele concepute pentru a simula o baliză aleatorie sunt numite balize aleatorii distribuite (DRB). (Alte nume includ „învârtirea de monede distribuită.”) Problema a fost studiată de zeci de ani, cu celebre rezultate de imposibilitate dovedite în anii 1980, dar interesul a fost reaprins în era blockchain. DRB-urile ar putea fi folosite pentru a oferi aleatorie în lanț, care ar fi un ingredient cheie pentru aplicații corecte, sigure și transparente în lanț.

Abordarea clasică: protocoale commit-reveal

Un protocol foarte simplu în două runde este suficient pentru un DRB în cazul optimist. În runda 1, fiecare participant i generează o valoare aleatorie r_i și publică un angajament criptografic c_i=comite(r_i). În această aplicație, angajamentul poate fi pur și simplu o funcție hash precum SHA-256. După ce angajamentul fiecărui participant este publicat, aceștia sunt blocați la alegerea lor r_i, dar angajamentele nu dezvăluie nicio informație despre contribuțiile altor participanți. În runda 2, fiecare participant își „deschide angajamentul” prin publicare r_i. Toate valorile aleatoare sunt apoi combinate, de exemplu prin XOR sau (de preferință) hashing concatenarea lor.

Acest protocol este simplu și produce o ieșire aleatorie de semnalizare, atâta timp cât chiar și unul dintre participanți își alege r_i la întâmplare. Din păcate, suferă de un defect clasic: atunci când toți participanții, cu excepția unuia, și-au dezvăluit valoarea aleatorie, ultimul participant este capabil să calculeze rezultatul presupus al semnalizatorului. Dacă nu le place, pot refuza să-și publice valoarea, avortând protocolul. Ignorarea contribuției unui participant defect nu rezolvă problema, deoarece asta îi oferă atacatorului posibilitatea de a alege între două ieșiri de semnalizare (una calculată cu contribuția lor și alta fără).

Blockchains oferă un remediu natural pentru această problemă: fiecărui participant i se poate cere să pună niște fonduri în escrow care sunt confiscate dacă nu își dezvăluie contribuția aleatorie. Exact aceasta a fost abordarea pe care a luat-o clasicul RANDAO far pe Ethereum. Dezavantajul acestei abordări este că rezultatul poate fi în continuare părtinitor, ceea ce poate fi util din punct de vedere financiar pentru atacator dacă banii în escrow sunt mai mici decât suma de bani care se bazează pe rezultatul farului. O mai bună securitate împotriva atacurilor părtinitoare necesită plasarea mai multor monede în escrow.

Protocoale commit-reveal-recuperare

În loc să încerce să forțeze toate părțile să-și dezvăluie contribuția aleatorie, unele protocoale includ un mecanism de recuperare, astfel încât, chiar dacă o minoritate de participanți abandonează, restul poate finaliza protocolul. Este important ca protocolul să producă același rezultat în oricare dintre cazuri, astfel încât părțile să nu influențeze rezultatul alegând dacă renunță sau nu.

O abordare pentru a realiza acest lucru este ca fiecare participant să furnizeze celorlalți părți din secretul său, astfel încât majoritatea acestora să îl poată reconstrui, folosind, de exemplu, Împărtășirea secretelor lui Shamir. O proprietate importantă, totuși, este că ceilalți pot verifica dacă secretul comis a fost partajat în mod corespunzător, necesitând utilizarea unei primitive mai puternice numită partajare secretă verificabilă public (PVSS).

Mai multe alte mecanisme de recuperare sunt posibile, dar toate au aceeași limitare. Dacă există N participanți și dorim rezistență dacă vreun grup de până la f noduri abandonează, atunci trebuie să fie cazul în care orice grup de Nf participanții pot calcula rezultatul final. Dar asta înseamnă și o coaliție rău intenționată de Nf participanții pot prezice rezultatul în avans prin simularea privată a mecanismului de recuperare. Acest lucru se poate întâmpla și în prima rundă a protocolului, timp în care o astfel de coaliție și-ar putea modifica propriile alegeri aleatorii și poate influența rezultatul. 

Cu alte cuvinte, asta înseamnă orice coaliție de Nf nodurile trebuie să includă cel puțin un nod sincer. Prin algebră simplă, Nf > f, asa de f < N/2, iar aceste protocoale necesită în mod inerent o majoritate onesta. Aceasta este o diferență semnificativă față de modelul de securitate original de commit-reveal, care necesită doar f<N (cel puțin un participant onest).

Aceste protocoale necesită adesea și costuri semnificative de comunicare pentru a partaja informațiile suplimentare PVSS între toate nodurile din fiecare rulare a protocolului. Comunitatea de cercetare a lucrat considerabil asupra acestei probleme în ultimii câțiva ani, inclusiv propuneri de cercetare RandShare, Racla, SecRand, HERB, Sau Albatros, dar niciunul nu pare să fi văzut implementare în lumea reală.

Protocoale aleatorii verificabile bazate pe funcții

Realizând că un grup de Nf participanții pot calcula valoarea semnalizatoare aleatoare în protocolul de mai sus duce la o abordare oarecum mai simplă: partajarea unei chei secrete pe termen lung între N părților și cereți-le să-l folosească pentru a evalua a funcție aleatorie verificabilă (VRF). Cheia secretă este partajată prin a t-din-N schema de prag, astfel încât orice t participanții pot calcula VRF (dar o coaliție mai mică nu poate). Pentru t=Nf, aceasta oferă aceeași rezistență la f noduri rău intenționate ca protocoalele commit-reveal-recover discutate mai sus.

DFINITATE a fost pionier în această abordare ca parte a protocolului lor de consens folosind semnături BLS de prag (care funcționează ca un VRF). Cel de sine stătător înșelătorie farul de aleatorie folosește în esență aceeași abordare, cu un set de participanți prag-BLS-semnând un contor în fiecare rundă. The Liga Entropiei este o instanță open source de drand care produce aleatoriu la fiecare 30 de secunde folosind 16 noduri participante (din septembrie 2022), conduse de un amestec de companii și grupuri de cercetare universitare. 

Un dezavantaj al acestor abordări este că inițializarea cheii de prag este relativ complexă, la fel ca și reconfigurarea cheii atunci când nodurile se unesc sau părăsesc. În cazul obișnuit, totuși, protocoalele sunt foarte eficiente. 

După cum este descris mai sus, simpla semnare a unei valori de contor nu adaugă nicio aleatorie nouă pe rundă, așa că dacă un număr suficient de chei ale participanților este compromis, atunci protocolul va fi previzibil în fiecare rundă viitoare.

VRF cu lanțuri combină această abordare (folosind NSEC5 VRF) cu o sursă externă de aleatorie specificată de părțile care solicită aleator, de obicei un antet blockchain recent în practică. Aceste date sunt apoi transmise printr-un VRF care este condus fie de una dintre părți, fie atribuit unui grup.

lui Ethereum Lanț de baliză utilizează în prezent VRF-uri bazate pe BLS: propunătorul fiecărei runde adaugă valoarea lor VRF la mix. Acest lucru salvează o rundă de comunicare în comparație cu paradigma commit-reveal (presupunând că o cheie publică BLS pe ​​termen lung este înregistrată o singură dată), deși acest design moștenește unele avertismente ale abordării commit-reveal, inclusiv posibilitatea de a părăsi ieșirea farului prin reținerea ieșirii. .

Protocoale verificabile bazate pe funcții de întârziere

În cele din urmă, o nouă direcție promițătoare este utilizarea criptografiei bazate pe timp, în special funcții de întârziere verificabile (VDF-uri). Această abordare promite să ofere o bună eficiență în comunicare și robustețe cu rezistență la N-1 noduri rău intenționate. 

Revenind la protocolul original commit-reveal, angajamentele tradiționale pot fi înlocuite cu angajamente programate pentru a elimina problema participanților care refuză să-și dezvăluie contribuția aleatorie. Angajamentele cronometrate pot fi deschise eficient de către committerul inițial sau de către oricine dorește să calculeze o funcție lentă (în esență un VDF). Astfel, dacă vreun participant renunță la un protocol de commit-reveal, angajamentul său poate fi deschis de către alții. Este esențial ca timpul minim de deschidere a angajamentului să fie suficient de lung încât să nu poată fi făcut în prima rundă (faza de comitere) a protocolului, altfel participanții rău intenționați ar putea deschide angajamentele altora suficient de repede pentru a-și modifica propria contribuție și a influența rezultatul. .

Un protocol într-o singură rundă și mai elegant este posibil cu VDF-urile moderne: renunțați complet la angajament. Fiecare participant își poate publica pur și simplu contribuția aleatorie r_i, iar rezultatul final este o combinație a contribuției fiecărui participant, rulată printr-un VDF. Întârzierea în calculul VDF asigură că nimeni nu își poate alege angajamentul într-un mod care influențează rezultatul final. Această abordare a fost propusă ca INOROG de Arjen Lenstra și Benjamin Wesolowski în 2015 și, într-adevăr, a fost o aplicație cheie motivantă în dezvoltarea VDF-urilor.

Această abordare a cunoscut o implementare practică. Chia implementează o versiune a acesteia ca parte a protocolului său de consens, folosind VDF-uri cu pătrare repetată în grupurile de clasă. Starkware implementat a far bazat pe VDF cu dovadă de concept folosind VDF-uri bazate pe SNARK. Ethereum de asemenea planuri să utilizeze această abordare, construind un ASIC dedicat pentru calcularea VDF-urilor pentru a genera aleatorie la nivelul consensului.

***

Aleatoria publică este o componentă esențială a multor protocoale, dar încă ne lipsește orice DRB standard care oferă securitate ridicată. Spațiul de proiectare este mare și sunt posibile multe hibrizi și combinații ale abordărilor de mai sus. De exemplu, este posibil să combinați un protocol bazat pe VRF cu un protocol bazat pe VDF, care adaugă entropie proaspătă, de exemplu, așa cum este propus de RandRunner. Beacon Chain de la Ethereum utilizează în prezent VRF-uri, deși poate adăuga VDF-uri în viitor pentru a elimina posibilitatea de părtinire a atacurilor de blocare.

Este, de asemenea, o întrebare deschisă atunci când protocoalele cu majoritate cinstită sunt acceptabile. Pentru un grup de participanți relativ mic și verificat - cum ar fi Liga Entropiei - o presupunere majoritară sinceră este rezonabilă. Pe de altă parte, protocoalele care necesită doar un singur participant cinstit au un avantaj inerent - mai mulți participanți nu pot decât să îmbunătățească securitatea. Aceasta înseamnă că aceste protocoale pot fi implementate cu participare deschisă, fără permisiune.

În partea a II-a, vom discuta despre aplicarea specifică a alegerii aleatorie a liderilor în protocoalele de consens, care are obiective de proiectare ușor diferite și, ca urmare, au fost propuse și mai multe protocoale și abordări.

***

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.