Salut, Habr!
În acest articol voi vorbi despre generarea numerelor pseudo-aleatoare de către participanți care nu se încrede în ceilalți. Așa cum vom vedea mai jos, implementarea unui generator „aproape” bun este destul de simplă, dar unul foarte bun este complicat.
De ce ar trebui să genereze participanții numere aleatoare dacă nu se încred unul în altul? Una dintre aplicațiile posibile este în aplicațiile descentralizate. De exemplu, o aplicație care acceptă o miză de la un participant și fie dublează suma cu o probabilitate de 49%, fie o ia cu 51%, va funcționa doar dacă poate obține un număr aleatoriu într-un mod nepartinitor. Dacă un atacator poate influența rezultatul generatorului de numere aleatoare, chiar și printr-o mică creștere a șanselor sale de a obține o plată în aplicație, va putea să o golească ușor.
Atunci când dezvoltăm un protocol distribuit pentru generarea numerelor aleatoare, dorim ca acesta să aibă trei proprietăți:
Trebuie să fie nepartinitor. Cu alte cuvinte, niciun participant nu ar trebui să influențeze în vreun fel rezultatul generatorului de numere aleatoare.
Trebuie să fie imprevizibil. Cu alte cuvinte, niciun participant nu ar trebui să poată prezice ce număr va fi generat (sau să deducă vreo proprietate a acestuia) înainte ca acesta să fie generat.
Protocolul trebuie să fie viabil, adică rezistent la faptul că un anumit procent de participanți se deconectează de la rețea sau încearcă intenționat să oprească protocolul.
În acest articol vom examina două abordări: RANDAO + VDF și o abordare bazată pe coduri de ștergere. În partea următoare, vom analiza mai detaliat abordarea bazată pe semnături de prag.
Dar mai întâi, să analizăm un algoritm simplu și adesea folosit, care este viabil, imprevizibil, dar partinitor.
RANDAO
RANDAO este o abordare foarte simplă și, prin urmare, destul de des utilizată pentru obținerea randomizării. Toți participanții din rețea aleg mai întâi un număr pseudo-aleatoriu local, apoi fiecare participant trimite hash-ul numărului ales. Apoi, participanții își scot la lumină pe rând numerele alese și efectuează o operație XOR asupra numerelor dezvăluite, iar rezultatul acestei operații devine rezultatul protocolului.
Pasul de publicare a hash-urilor înainte de a revela numerele este necesar pentru ca un atacator să nu poată alege propriul său număr după ce a văzut numerele celorlalți participanți. Aceasta i-ar permite să determine de fapt în mod unilateral rezultatul generatorului de numere aleatoare.
Pe parcursul protocolului, participanții trebuie să ajungă de două ori la un consens (așa-numitul consorț) cu privire la momentul în care să înceapă să dezvăluie numerele alese, și, prin urmare, să înceteze să mai primească hash-uri, și când să termine primirea numerelor alese și să calculeze numărul aleatoriu rezultat. Luarea acestor decizii între participanți, care nu au încredere unii în alții, este o sarcină complicată și ne vom întoarce la aceasta în articolele viitoare; în acest articol ne vom considera că un astfel de algoritm de consens este accesibil.
Ce proprietăți, pe care le-am descris mai sus, are RANDAO? Este imprevizibil, are aceeași viabilitate ca și protocolul de consens care stă la baza sa, dar este părtinitor. În special, un atacator poate observa rețeaua și, după ce ceilalți participanți își dezvăluie numerele, poate calcula XOR-ul acestora și decide dacă să își dezvăluie sau nu numărul pentru a influența rezultatul. Deși acest lucru nu permite atacatorului să determine unilateral rezultatul generatorului de numere aleatoare, îi oferă totuși 1 bit de influență. Dacă atacatorii controlează mai mulți participanți, numărul de biți controlați de ei va fi egal cu numărul de participanți sub controlul lor.
Influența atacatorilor poate fi redusă semnificativ dacă se cere ca participanții să dezvăluie numerele în ordine. Atunci, atacatorul poate influența rezultatul doar dacă dezvăluie ultimul. Deși influența este semnificativ mai mică, algoritmul este totuși părtinitor.
RANDAO + VDF
Una dintre opțiuni pentru a face RANDAO nepărtinitor este următoarea: după ce toate numerele au fost dezvăluite și XOR-ul a fost calculat, rezultatul să fie trimis ca intrare unei funcții care necesită mult timp pentru a fi calculată, dar permite verificarea rapidă a corectitudinii calculului.
(vdf_output, vdf_proof) = VDF_compute(input) // este foarte lent
correct = VDF_verify(input, vdf_output, vdf_proof) // este foarte rapidAceastă funcție se numește Verifiable Delay Function, sau VDF. Dacă calcularea rezultatului final durează mai mult decât etapa de revelare a numerelor, atunci un atacator nu va putea prezice efectul demonstrației sau ascunderii numărului său, și, prin urmare, va pierde capacitatea de a influența rezultatul.
Dezvoltarea unor VDF bune este extrem de complicată. În ultima vreme, au avut loc câteva progrese, de exemplu, și care au făcut ca VDF să fie mai aplicabile în practică, iar Ethereum 2.0 preconizează că va folosi RANDAO cu VDF ca sursă de numere aleatorii pe termen lung. Pe lângă faptul că această abordare este imprevizibilă și imparțială, are un avantaj suplimentar în ceea ce privește viabilitatea, cu condiția ca măcar doi participanți să fie disponibili în rețea (atâta timp cât protocolul de consens utilizat este viabil pentru a funcționa cu un număr atât de mic de participanți).
Cea mai mare dificultate a acestei abordări constă în configurarea VDF astfel încât chiar și un participant cu echipament specializat foarte scump să nu poată calcula VDF până la finalizarea etapei de revelație. În mod ideal, algoritmul ar trebui să aibă chiar și un rezervă semnificativă de putere, să zicem, 10x. În figura de mai jos este arătat un atac al unui participant care dispune de un ASIC specializat, care îi permite să ruleze VDF mai repede decât timpul alocat pentru revelația confirmării RANDAO. Acest participant poate calcula în continuare rezultatul final folosind și neluând în considerare numărul său, și, pe baza calculului, să decidă dacă să-l arate sau nu.
Pentru familia VDF menționată mai sus, performanța unui ASIC specializat poate fi de peste 100 de ori mai mare decât a echipamentului obișnuit. Astfel, dacă etapa de revelație durează 10 secunde, atunci VDF calculat pe un astfel de ASIC ar trebui să dureze mai mult de 100 de secunde pentru a avea un rezervă de securitate de 10x, și, prin urmare, același VDF calculat pe echipament obișnuit ar trebui să dureze 100 x 100 secunde = ~ 3 ore.
Fundația Ethereum intenționează să rezolve această problemă prin crearea propriilor ASIC publice și gratuite. Odată ce acest lucru se va întâmpla, toate celelalte protocoale vor putea beneficia de această tehnologie, dar până atunci abordarea RANDAO + VDF nu va fi la fel de viabilă pentru protocoalele care nu pot investi în dezvoltarea propriilor ASIC.
O mulțime de articole, videoclipuri și alte informații despre VDF au fost adunate pe .
Folosim coduri de ștergere
În această secțiune, vom explora protocolul de generare a numerelor aleatoare, care folosește . Acesta poate tolera până la ⅓ din atacatori, rămânând viabil, și permite existența a până la ⅔ din atacatori înainte ca aceștia să poată prezice sau influența rezultatul.
Ideea de bază a protocolului este următoarea. Pentru a simplifica, să presupunem că sunt exact 100 de participanți. De asemenea, să presupunem că fiecare participant are local o cheie privată, iar cheile publice ale tuturor participanților sunt cunoscute de toți participanții:
Fiecare participant generează local un șir lung, îl fragmentează în 67 de părți, creează coduri de ștergere pentru a obține 100 de părți, astfel încât oricare 67 să fie suficiente pentru a recupera șirul, alocă fiecare din cele 100 de părți unui participant și le criptează folosind cheia publică a aceluiași participant. Apoi, toate părțile criptate sunt publicate.
Participanții folosesc un anumit consens pentru a ajunge la un acord asupra seturilor codificate de la anumiți 67 de participanți.
Odată ce consensul este atins, fiecare participant ia părțile codificate din fiecare dintre cele 67 de seturi, criptate cu cheia lor publică, decriptează toate aceste părți și publică toate aceste părți decriptate.
Odată ce 67 de participanți au finalizat pasul (3), toate seturile convenite pot fi complet decriptate și restaurate datorită proprietăților codurilor de ștergere, iar numărul final poate fi obținut ca XOR al șirurilor inițiale din care participanții au început în (1).
Se poate demonstra că acest protocol este imparțial și imprevizibil. Numărul aleatoriu rezultat este definit după atingerea consensului, dar nimănui nu îi este cunoscut până când ⅔ din participanți nu decodează părțile criptate cu cheia lor publică. Astfel, numărul aleatoriu este definit înainte ca informația necesară pentru recuperarea sa să fie publicată.
Ce se întâmplă dacă în pasul (1) unul dintre participanți trimite altor participanți părți codificate care nu sunt un cod de ștergere corect pentru o anumită linie? Fără modificări suplimentare, participanții diferiți fie nu vor putea să recupereze deloc linia, fie vor recupera linii diferite, ceea ce va duce la obținerea unui număr aleatoriu diferit de către participanți. Pentru a preveni acest lucru, se poate face următoarele: fiecare participant, pe lângă părțile codificate, calculează de asemenea pentru toate aceste părți și trimite fiecărui participant atât partea codificată, cât și rădăcina arborelui Merkle, și dovada includerii părții în arborele Merkle. În consens, în pasul (2), participanții nu doar că sunt de acord asupra mai multor seturi, ci și asupra mai multor rădăcini specifice ale acestor arbori (dacă un anumit participant s-a abătut de la protocol și a trimis rădăcini diferite ale arborelui Merkle diferitelor participanți, iar aceste două rădăcini sunt prezentate în timpul consensului, linia sa nu este inclusă în setul rezultat). La finalul consensului, vom avea 67 de linii codificate și rădăcinile corespunzătoare ale arborelui Merkle, astfel încât să existe cel puțin 67 de participanți (nu neapărat aceiași care au propus liniile respective), care pentru fiecare dintre cele 67 de linii au un mesaj cu o parte a codului de ștergere și o dovadă a includerii părții lor în arborele Merkle corespunzător.
Când în pasul (4) un participant decodează 67 de părți pentru o anumită linie și încearcă să recupereze linia originală din acestea, este posibil unul dintre următoarele scenarii:
Linia este recuperată, iar dacă este din nou codificată cu coduri de ștergere și se calculează arborele Merkle pentru părțile calculate local, rădăcina coincide cu cea la care s-a obținut consensul.
Linia este recuperată, dar rădăcina calculată local nu corespunde celei la care s-a obținut consensul.
Linia nu poate fi recuperată.
Este ușor de demonstrat că, dacă cel puțin pentru un participant a apărut varianta (1), atunci pentru toți participanții va apărea varianta (1), și invers, dacă cel puțin pentru un participant a apărut varianta (2) sau (3), atunci pentru toți participanții va apărea varianta (2) sau (3). Astfel, pentru fiecare linie din set, fie toți participanții o vor reconstitui cu succes, fie toți participanții nu o vor putea reconstitui. Apoi, numărul aleatoriu rezultat este XOR doar al acelor linii pe care participanții le-au putut reconstitui.
Semnături prin prag
O altă abordare a aleatorizării implică utilizarea așa-numitelor semnături BLS prin prag. Generatorul de numere aleatoare, bazat pe semnături prin prag, are aceleași garanții ca algoritmul descris mai sus, bazat pe coduri care șterg, dar are o complexitate asimptotică semnificativ mai mică în ceea ce privește numărul de mesaje transmise prin rețea pentru fiecare număr generat.
Semnăturile BLS sunt o construcție care permite mai multor participanți să creeze o semnătură comună pentru un mesaj. Aceste semnături sunt adesea utilizate pentru a economisi spațiu și lățime de bandă, deoarece nu este necesară distribuirea mai multor semnături.
O utilizare frecventă pentru semnăturile BLS în protocoalele blockchain, pe lângă generarea numerelor aleatoare, este semnarea blocurilor în protocoalele BFT. Să zicem că 100 de participanți creează blocuri, iar un bloc este considerat final dacă 67 dintre ei îl semnează. Toți pot prezenta părțile lor de semnătură BLS și pot folosi un anumit algoritm de consens pentru a conveni asupra celor 67 dintre ei, iar apoi le pot combina într-o singură semnătură BLS. Orice 67 (sau mai multe) părți pot fi utilizate pentru a genera semnătura finală, care va depinde de ce 67 de semnături au fost combinate, și, prin urmare, poate varia, dar, deși diversele selecții ale celor 67 de participanți vor crea o semnătură diferită, oricare astfel de semnătură va fi o semnătură corectă pentru bloc. Celorlalți participanți le va fi suficient să primească prin rețea și să verifice o singură semnătură pentru fiecare bloc, în loc de 67, ceea ce reduce semnificativ încărcarea pe rețea.
Se pare că dacă cheile private folosite de participanți sunt generate într-un anumit mod, atunci indiferent de ce 67 de semnături (sau mai multe, dar nu mai puțin) sunt agregate, semnătura rezultată va fi identică. Acest lucru poate fi utilizat ca sursă de aleatoritate: participanții se înțeleg mai întâi asupra unui anumit mesaj pe care vor să-l semneze (acesta poate fi rezultatul RANDAO sau pur și simplu hash-ul ultimei blocuri, de fapt nu are importanță, atâta timp cât se schimbă de fiecare dată și este convenit), și creează pentru el o semnătură BLS. Rezultatul generării va fi imprevizibil, până când 67 de participanți își vor oferi părțile, iar după aceea, ieșirea va fi deja predeterminată și nu poate depinde de acțiunile vreunui participant.
Această abordare a aleatorității este viabilă dacă cel puțin ⅔ dintre participanți sunt online și respectă protocolul, și este imparțială și imprevizibilă atâta timp cât cel puțin ⅓ dintre participanți respectă protocolul. Este important de menționat că un atacator care controlează mai mult de ⅓ dar mai puțin de ⅔ dintre participanți poate opri protocolul, dar nu poate prezice sau influența ieșirea acestuia.
Semnăturile de prag sunt ele însele o temă foarte interesantă. În a doua parte a articolului vom analiza în detaliu cum funcționează acestea și cum trebuie generate cheile participanților pentru ca semnăturile de prag să poată fi folosite ca generator de numere aleatoare.
În concluzie
Acest articol este primul dintr-o serie de articole tehnice pe blog. . NEAR este un protocol blockchain și o platformă pentru dezvoltarea aplicațiilor descentralizate, cu accent pe ușurința dezvoltării și ușurința utilizării pentru utilizatorii finali.
Codul protocolului este deschis, iar implementarea noastră este scrisă în Rust, și poate fi găsită .
Puteți vedea cum arată dezvoltarea pe NEAR și experimenta în online-IDE .
Urmării toate noutățile în limba română se poate în și în , iar în limba engleză în oficialul .
Pe curând!
Sursa: habr.com
