Este posibil să generăm numere aleatorii dacă nu avem încredere unul în celălalt? Partea 2

Hei Habr!

В prima parte În acest articol, am discutat de ce ar putea fi necesar să se genereze numere aleatorii pentru participanții care nu au încredere unul în altul, ce cerințe sunt prezentate pentru astfel de generatori de numere aleatoare și am luat în considerare două abordări ale implementării lor.

În această parte a articolului, vom arunca o privire mai atentă asupra unei alte abordări care utilizează semnături de prag.

Un pic de criptografie

Pentru a înțelege cum funcționează semnăturile de prag, trebuie să înțelegeți puțină criptografie de bază. Vom folosi două concepte: scalari, sau pur și simplu numere, pe care le vom nota cu litere mici (X y) și puncte de pe curba eliptică, pe care le vom nota cu majuscule.

Pentru a înțelege elementele de bază ale semnăturilor de prag, nu trebuie să înțelegeți cum funcționează curbele eliptice, în afară de câteva lucruri de bază:

1. Punctele de pe o curbă eliptică pot fi adăugate și înmulțite cu un scalar (vom nota înmulțirea cu un scalar ca xG, deși notația Gx folosită adesea în literatură). Rezultatul adunării și înmulțirii cu un scalar este un punct pe o curbă eliptică.

2. Cunoscând doar ideea G iar produsul său cu un scalar xG nu poate fi calculată x.

Vom folosi și conceptul de polinom p(x) grad k-1. În special, vom folosi următoarea proprietate a polinoamelor: dacă știm valoarea p(x) pentru orice k diferit x (și nu avem mai multe informații despre p(x)), putem calcula p(x) pentru oricine altcineva x.

Este interesant că pentru orice polinom p(x) și un punct de pe curbă Gcunoscând sensul p(x)G pentru orice k sensuri diferite x, putem calcula și noi p(x)G pentru orice x.

Acestea sunt suficiente informații pentru a explora detaliile despre cum funcționează semnăturile de prag și cum să le folosiți pentru a genera numere aleatorii.

Generator de numere aleatorii pe semnăturile de prag

Să spunem asta n participanții doresc să genereze un număr aleatoriu și vrem să participe oricine k au fost destui pentru a genera un număr, dar pentru ca atacatorii care controlează k-1 sau mai puțini participanți nu au putut prezice sau influența numărul generat.

Să presupunem că există un astfel de polinom p(x) grad k-1 ceea ce știe primul participant p (1), al doilea stie p(2), și așa mai departe (n-th stie p(n)). De asemenea, presupunem că pentru un punct prestabilit G toata lumea stie p(x)G pentru toate valorile x. Vom suna p(i) „componentă privată” ial-lea participant (pentru că numai ial-lea participant o cunoaște) și porc „componentă publică” i- al-lea participant (pentru că toți participanții o cunosc). După cum vă amintiți, cunoașterea porc nu este suficient pentru a restaura p(i).

Crearea unui astfel de polinom astfel încât numai i-Primul participant și nimeni altcineva își cunoștea componenta privată - aceasta este cea mai complexă și interesantă parte a protocolului și o vom analiza mai jos. Deocamdată, să presupunem că avem un astfel de polinom și toți participanții își cunosc componentele private.

Cum putem folosi un astfel de polinom pentru a genera un număr aleatoriu? Pentru început, avem nevoie de un șir care nu a fost folosit anterior ca intrare la generator. În cazul unui blockchain, hash-ul ultimului bloc h este un bun candidat pentru o astfel de linie. Permiteți participanților să dorească să creeze un număr aleatoriu folosind h ca sămânța. Participanții se convertesc primii h la un punct al curbei folosind orice funcție predefinită:

H = scalarToPoint(h)

Apoi fiecare participant i calculează și publică Hi = p(i)H, ce pot face pentru ca stiu p(i) și H. dezvăluire Hnu permit altor participanți să restaureze componenta privată ial-lea participant și, prin urmare, un set de componente private poate fi utilizat de la bloc la bloc. Astfel, algoritmul costisitor de generare a polinomului descris mai jos trebuie executat o singură dată.

Când k participanții au fost autopsiați Hi = p(i)H, toată lumea poate calcula Hx = p(x)H pentru toți x datorită proprietății polinoamelor pe care am discutat-o ​​în ultima secțiune. În acest moment, toți participanții calculează H0 = p(0)H, și acesta este numărul aleatoriu rezultat. Vă rugăm să rețineți că nimeni nu știe p(0), și deci singura modalitate de a calcula p(0)H – aceasta este interpolare p(x)H, ceea ce este posibil numai atunci când k valori p(i)H cunoscut. Deschiderea oricărei cantități mai mici p(i)H nu oferă nicio informație despre p(0)H.

Generatorul de mai sus are toate proprietățile pe care le dorim: atacatorii care controlează doar k-1 sau mai puțin de participanți nu au nicio informație sau influență asupra concluziei, în timp ce oricare k participanții pot calcula numărul rezultat și orice subset de k participanții vor ajunge întotdeauna la același rezultat pentru aceeași sămânță.

Există o problemă pe care am evitat-o ​​cu atenție mai sus. Pentru ca interpolarea să funcționeze, este important ca valoarea Hi care a fost publicat de fiecare participant i chiar a fost la fel p(i)H. Din moment ce nimeni în afară de i- al doilea participant nu știe p(i), nimeni în afară de i-al-lea participant nu poate verifica asta Hi calculat corect și fără nicio dovadă criptografică de corectitudine Hun atacator pot publica orice valoare ca Bună, și influențează în mod arbitrar rezultatul generatorului de numere aleatorii:

Valorile diferite ale lui H_1 trimise de primul participant conduc la rezultate diferite H_0

Există cel puțin două moduri de a dovedi corectitudinea Hi, le vom lua în considerare după ce vom analiza generarea polinomului.

Generarea polinomelor

În ultima secțiune am presupus că avem un astfel de polinom p(x) grad k-1 că participantul i El știe p(i), și nimeni altcineva nu are informații despre această valoare. În secțiunea următoare vom avea nevoie și de asta pentru un punct predeterminat G toată lumea știa p(x)G pentru toți x.

În această secțiune vom presupune că fiecare participant are la nivel local o cheie privată xi, astfel încât toată lumea să cunoască cheia publică corespunzătoare Xi.

Un posibil protocol de generare a polinomului este următorul:

1. Fiecare participant i creează local un polinom arbitrar pi(x) gradul k-1. Apoi trimit fiecare participant j valoare pi(j), criptat cu cheie publică Xj. Numai asa i-lea и j-lea participantul stie pi(j). Participant i anunță și public pi(j)G pentru toți j din 1 la k inclusiv.

2. Toți participanții folosesc un anumit consens pentru a alege k participanții ale căror polinoame vor fi utilizate. Deoarece unii participanți pot fi offline, nu putem aștepta până când toată lumea n participanții vor publica polinoame. Rezultatul acestui pas este un set Z constând din cel puţin k polinoame create la pasul (1).

3. Participanții se asigură că valorile pe care le cunosc pi(j) corespund anunțului public pi(j)G. După acest pas în Z numai polinoame pentru care transmis privat pi(j) corespund anunțului public pi(j)G.

4. Fiecare participant j calculează componenta sa privată pijamale) ca sumă pi(j) pentru toți i в Z. Fiecare participant calculează, de asemenea, toate valorile p(x)G ca sumă pi(x)G pentru tot i в Z.

Vă rugăm să rețineți faptul că p(x) – chiar este un polinom k-1, deoarece este suma individului pi(x), fiecare dintre acestea fiind un polinom de grad k-1. Apoi, rețineți că în timp ce fiecare participant j El știe pijamale), nu au informatii despre p(x) pentru x ≠ j. Într-adevăr, pentru a calcula această valoare, ei trebuie să știe totul pi(x), și atâta timp cât participantul j nu cunoaște cel puțin unul dintre polinoamele selectate, nu au suficiente informații despre p(x).

Acesta este întregul proces de generare a polinomului care a fost necesar în ultima secțiune. Pașii 1, 2 și 4 de mai sus au o implementare destul de evidentă. Dar pasul 3 nu este atât de banal.

Mai exact, trebuie să putem dovedi că este criptat pi(j) corespund cu adevărat celor publicate pi(j)G. Dacă nu putem dovedi, atacatorul i poate trimite gunoi în schimb pi(j) către participant j, și participant j nu va putea obține valoarea reală pi(j), și nu își va putea calcula componenta privată.

Există un protocol criptografic care vă permite să creați un mesaj suplimentar dovadăi(j), astfel încât orice participant, având o anumită valoare e, precum dovada(j) и pi(j)G, poate verifica local că e - e într-adevăr pi(j), criptat cu cheia participantului j. Din păcate, dimensiunea unor astfel de dovezi este incredibil de mare și având în vedere că este necesar să fie publicate O(nk) Astfel de dovezi nu pot fi folosite în acest scop.

În loc să dovedească asta pi(j) соответствует pi(j)G putem aloca o perioadă foarte lungă de timp în protocolul de generare a polinomului, timp în care toți participanții verifică criptarea primită. pi(j), iar dacă mesajul decriptat nu corespunde publicului pi(j)G, publică o dovadă criptografică că mesajul criptat pe care l-au primit este incorect. Demonstrează că mesajul nu соответствует porc) mult mai ușor decât să demonstrezi că se potrivește. Trebuie remarcat faptul că acest lucru necesită ca fiecare participant să apară online cel puțin o dată în timpul alocat pentru a crea astfel de dovezi și se bazează pe presupunerea că, dacă publică o astfel de dovadă, aceasta va ajunge la toți ceilalți participanți în același timp alocat.

Dacă un participant nu a apărut online în această perioadă de timp și a avut cel puțin o componentă incorectă, atunci acel participant nu va putea participa la generarea ulterioară a numerelor. Protocolul va funcționa în continuare dacă există cel puțin k participanții care fie tocmai au primit componentele corecte, fie au reușit să lase dovezi incorecte în timpul alocat.

Dovezi de corectitudine a lui H_i

Ultima parte care rămâne de discutat este cum se dovedește corectitudinea publicației Heu și anume că Hi = p(i)H, fara deschidere p(i).

Să ne amintim că valorile H, G, p(i)G publice și cunoscute de toată lumea. Operațiune de primire p(i) știind porc и G numit logaritm discret sau dlog, și vrem să demonstrăm că:

dlog(p(i)G, G) = dlog(Hi, H)

fără dezvăluire p(i). Construcții pentru astfel de dovezi există, de exemplu Protocolul Schnorr.

Cu acest design, fiecare participant, împreună cu Hi trimite o dovadă de corectitudine conform proiectului.

Odată ce un număr aleator este generat, acesta trebuie adesea folosit de participanți, alții decât cei care l-au generat. Astfel de participanți, împreună cu numărul, trebuie să trimită pe toți Hi și dovezi aferente.

Un cititor curios poate întreba: deoarece numărul final aleatoriu este H0 și p(0)G – Aceasta este o informație publică, de ce avem nevoie de dovezi pentru fiecare individ HEu, de ce să nu trimiți în schimb dovada asta

dlog(p(0)G, G) = dlog(H0, H)

Problema este că o astfel de dovadă nu poate fi creată folosind Protocolul Schnorr pentru că nimeni nu știe valoarea p (0), necesar pentru a crea dovada și, mai mult, întregul generator de numere aleatoare se bazează pe faptul că nimeni nu cunoaște această valoare. Prin urmare, este necesar să avem toate valorile Hi și dovezile lor individuale pentru a dovedi corectitudinea H0.

Cu toate acestea, dacă ar exista o operațiune asupra punctelor de pe curbele eliptice care este similară din punct de vedere semantic cu înmulțirea, dovada corectitudinii H0 ar fi banal, pur și simplu ne-am asigura că

H0 × G = p(0)G × H

Dacă curba selectată suportă perechi de curbe eliptice, această dovadă funcționează. În acest caz H0 nu este doar rezultatul unui generator de numere aleatorii, care poate fi verificat de orice participant care știe G, H и p(0)G. H0 este, de asemenea, o semnătură pe mesaj care a fost folosit ca semințe, confirmând asta k и n participanții au semnat acest mesaj. Astfel, dacă samanta - este hash-ul blocului în protocolul blockchain, atunci H0 este atât o multi-semnătură pe un bloc, cât și un număr foarte bun aleatoriu.

în concluzie

Acest articol face parte dintr-o serie de bloguri tehnice NEAR. NEAR este un protocol și o platformă blockchain pentru dezvoltarea aplicațiilor descentralizate, cu accent pe ușurința dezvoltării și ușurința în utilizare pentru utilizatorii finali.

Codul de protocol este deschis, implementarea noastră este scrisă în Rust, poate fi găsit aici.

Puteți vedea cum arată dezvoltarea pentru NEAR și puteți experimenta în IDE-ul online aici.

Puteți urmări toate știrile în limba rusă la grup de telegrame și grup pe VKontakte, iar în engleză în oficial stare de nervozitate.

Pe curând!

Sursa: www.habr.com