Salut, Habr!
În În articolele noastre am discutat despre motivele pentru care ar putea fi necesară generarea de numere aleatorii pentru participanții care nu se încred unul în altul, ce cerințe trebuie să îndeplinească astfel de generatoare de numere aleatorii și am examinat două abordări pentru implementarea lor.
În această parte a articolului, vom explora în detaliu o altă abordare care utilizează semnături de prag.
Puțin despre criptografie
Pentru a înțelege cum funcționează semnăturile de prag, trebuie să cunoaștem puțină criptografie de bază. Vom folosi două concepte: scalari, sau pur și simplu numere, pe care le vom denumi cu litere mici (x, y) și puncte pe o curbă eliptică, pe care le vom denumi cu litere mari.
Pentru a înțelege principiile de bază ale semnăturilor de prag nu este necesar să știm cum funcționează curbele eliptice, în afară de câteva lucruri de bază:
Punctele pe o curbă eliptică pot fi adunate și înmulțite cu un scalar (înmulțirea cu un scalar o vom denumi ca xG, deși notația Gx este, de asemenea, frecvent utilizată în literatură). Rezultatul adunării și înmulțirii cu un scalar este un punct pe o curbă eliptică.
Cunoașterea doar a punctului G și a produsului său cu scalarul xG nu permite calcularea x.
De asemenea, vom folosi conceptul de polinom p(x) de grad k-1. În special, vom folosi următoarea proprietate a polinoamelor: dacă știm valoarea p(x) pentru orice k valorile distincte x (și nu avem nicio altă informație despre p(x)), putem calcula p(x) pentru orice alt x.
Este interesant că, pentru orice polinom p(x) și pentru un anumit punct pe curbă G, cunoscând valoarea p(x)G pentru orice k a unor valori distincte x, se poate calcula, de asemenea, p(x)G pentru orice x.
Această informație este suficientă pentru a ne aprofunda în detaliile despre cum funcționează semnăturile de prag și cum pot fi utilizate pentru a genera numere aleatorii.
Generator de numere aleatorii bazat pe semnături de prag
Să presupunem că n participanții doresc să genereze un număr aleator, și dorim ca participarea oricăror k dintre ei să fie suficientă pentru a genera numărul, dar ca atacatorii care controlează k-1 sau mai puțini participanți să nu poată prezice sau influența numărul generat.
Să presupunem că există un astfel de polinom p(x) de grad k-1, astfel încât primul participant să știe p(1), al doilea știe p(2), și așa mai departe (n-le știe p(n)). De asemenea, să presupunem că, pentru un anumit punct definit anterior, G toți știu p(x)G pentru toate valorile x. Vom numi p(i) „componenta privată” i-a participantului (deoarece doar i-ul participant știe care este), și p(i)G „componenta publică” i-a participantului (deoarece toți participanții o cunosc). Așa cum vă amintiți, cunoașterea p(i)G nu este suficientă pentru a restaura p(i).
Crearea unei astfel de polinoame astfel încât doar i--ul participant și nimeni altcineva să își cunoască componenta privată – aceasta este cea mai complexă și interesantă parte a protocolului, și o vom analiza mai jos. Între timp, să presupunem că avem o astfel de polinomă, și toți participanții își cunosc componentele private.
Cum putem folosi o 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 pentru generator. În cazul blockchain-ului, hash-ul ultimei blocuri h — este un bun candidat pentru un astfel de șir. Să presupunem că participanții doresc să creeze un număr aleatoriu folosind h ca seed. Mai întâi, participanții transformă h într-un punct pe curbă folosind orice funcție predefinită:
H = scalarToPoint(h)
Apoi, fiecare participant i calculează și publică Hi = p(i)H, ceea ce pot face, deoarece cunosc p(i) și H. Dezvăluirea Hi nu permite altor participanți să restaureze componenta privată i-ului participant, și de aceea un set de componente private poate fi folosit de la un bloc la altul. Astfel, algoritmul costisitor de creare a polinomului, descris mai jos, trebuie să fie executat doar o singură dată.
Când k participanții au dezvăluit Hi = p(i)H, toți pot calcula Hx = p(x)H pentru toți x datorită proprietății polinoamelor, pe care am discutat-o în secțiunea anterioară. În acest moment, toți participanții calculează H0 = p(0)H, și acesta este numărul aleatoriu rezultat. Rețineți că nimeni nu știe p(0), și prin urmare, singura modalitate de a calcula p(0)H – este interpolarea p(x)H, ceea ce este posibil doar atunci când k valorile p(i)H sunt cunoscute. Dezvăluirea 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 participanți, sau mai puțin, nu au nicio informație și influență asupra ieșirii, în timp ce oricare k participanți pot calcula numărul rezultat, iar orice submulțime de k participanți va ajunge întotdeauna la același rezultat pentru același seed.
Există o problemă pe care am evitat-o cu atenție mai sus. Pentru ca interpolarea să funcționeze, este important ca valoarea Hi publicată de fiecare participant i să fie cu adevărat egală cu p(i)H. Deoarece nimeni, în afară de i-ul participant nu știe p(i), nimeni în afară de i-participantul respectiv nu poate verifica dacă Salut a fost într-adevăr calculat corect, și fără o dovadă criptografică a corectitudinii Hi un atacator poate publica orice valoare ca fiind Salut, și poate afecta aleatoriu rezultatul generatorului de numere aleatoare.:
Valori diferite H_1 trimise de primul participant duc la H_0 rezultant diferit.
Există cel puțin două moduri de a dovedi corectitudinea Hi, le vom examina după ce discutăm despre generarea polinomului.
Generarea polinomului
În secțiunea precedentă am presupus că avem un astfel de polinom p(x) de grad k-1 pe care participantul i cunoaște, p(i)iar nimeni altcineva nu are nicio informație despre această valoare. În secțiunea următoare, va trebui de asemenea să ne asigurăm că pentru un anumit punct predefinit G toți știu p(x)G pentru toți x.
În această secțiune vom presupune că fiecare participant are local o cheie privată xi, astfel încât cheia publică corespunzătoare Xi este cunoscută.
Un protocol posibil de generare a polinomului este următorul:
Fiecare participant i crează local un polinom aleator pi(x) de grad k-1. Aceștia apoi trimit fiecărui participant j valoarea pi(j), criptat cu cheia publică Xj. Astfel, doar i-j-l și participant știej-l i(j). Participantul pde asemenea anunță public i pi(j)G inclusiv. pentru toți j de la 1 la k Toți participanții folosesc un consens pentru a selecta
participanții ale căror polinoame vor fi utilizate. Deoarece unii participanți pot fi offline, nu putem aștepta ca toți k participanții să publice polinoamele. Rezultatul acestui pas este un set n format din cel puțin Z polinoame create în pasul (1) k Participanții se asigură că valorile pe care le cunosc.
i(j) corespund celor public anunțate ppi(j)G. După acest pas, ar trebui să rămână doar polinoame pentru care componentele private calculă componenta sa privată Z p(j) ppi(j)G. După acest pas, ar trebui să rămână doar polinoame pentru care componentele private
Fiecare participant j ca sumă i(j) pentru toți. Fiecare participant de asemenea calculează toate valorile ppi(x)G pentru toți i i în Zp(x) – p(x)G Fiecare participant de asemenea calculează toate valorile acesta este cu adevărat un polinom de grad în Z.
Rețineți că k-1, deoarece este suma indivizibilelor i(x), fiecare dintre care este un polinom de grad потому что это сумма отдельных pi(x), каждый из которых – это полином степени k-1. Apoi, rețineți că, în timp ce fiecare participant j cunoaște, p(j), nu au nicio informație despre p(x) pentru x ≠ j. Într-adevăr, pentru a calcula această valoare, trebuie să cunoască toate pi(x), și atât timp cât participantul j nu știe cel puțin unul dintre polinoamele alese, nu au informații suficiente despre p(x).
Aceasta este întreaga proces de generare a polinomului, care a fost necesară în secțiunea precedentă. Pașii 1, 2 și 4 de mai sus au o implementare suficient de evidentă. Dar pasul 3 nu este atât de trivial.
Specifically, trebuie să putem dovedi că encryptările pi(j) corespund cu cele publicate. După acest pas, ar trebui să rămână doar polinoame pentru care componentele private Dacă nu putem dovedi acest lucru, un atacator i poate trimite gunoi în loc de pi(j) participantului j, iar participantul j nu va putea obține valoarea reală pi(j), și nu va putea calcula componenta sa privată..
Există un protocol criptografic care permite generarea unui mesaj suplimentar proofi(j), astfel încât orice participant, având o anumită valoare e, și de asemenea proofi(j) și pi(j)G, poate verifica local că e – este cu adevărat pi(j), criptat cu cheia participantului j. Din păcate, dimensiunea unei astfel de dovezi este incredibil de mare, iar având în vedere că trebuie să publice O(nk) astfel de dovezi, utilizarea lor în acest scop nu va fi posibilă.
În loc să dovedim că pi(j) corespunde pi(j)G, putem în protocolul de generare a polinomului să alocăm un interval de timp foarte mare, în timpul căruia toți participanții verifică encryptările primite pi(j), și dacă mesajul decriptat nu corespunde publicului pi(j)G, ei publică o dovadă criptografică că mesajul encryptat pe care l-au primit este greșit. A dovedi că mesajul nu corespunde pi(G) este mult mai simplu decât a dovedi că acesta corespunde. Trebuie remarcat că acest lucru necesită ca fiecare participant să apară în rețea cel puțin o dată în timpul alocat pentru generarea acestor dovezi și se bazează pe presupunerea că, dacă au publicat o astfel de dovadă, aceasta va ajunge la toți ceilalți participanți în acel timp acordat.
Dacă un participant nu a apărut în rețea în această perioadă de timp, iar el avea cu adevărat cel puțin o componentă incorectă, atunci acest participant specific nu va putea participa la generarea ulterioară a numerelor. Protocolul, însă, va continua să funcționeze, dacă există măcar k participanților, care fie că abia au primit componente corecte, fie că au reușit să lase dovada incorectitudinii la timp.
Dovada corectitudinii H_i
Ultima parte care trebuie discutată este cum să demonstrăm corectitudinea celor publicate Hi, și anume că Hi = p(i)H, fără dezvăluire p(i).
Să ne amintim că valorile H, G, p(i)G sunt publice și cunoscute de toți. Operația de obținere p(i) cunoașterea p(i)G și G se numește logaritm discret, sau dlog, și dorim să demonstrăm că:
dlog(p(i)G, G) = dlog(Hi, H)
fără dezvăluire p(i). Există construcții pentru astfel de dovezi, de exemplu.
Cu o astfel de construcție, fiecare participant împreună cu Salut trimite dovezi de corectitudine conform construcției.
Când numărul aleatoriu este generat, adesea trebuie să fie folosit de participanți diferiți de cei care l-au generat. Astfel, acestora împreună cu numărul trebuie să le fie trimise toate Salut și dovezile aferente.
Cititorul curios s-ar putea întreba: având în vedere că numărul aleatoriu final este H0, și p(0)G – aceasta este informație publică, de ce este necesară dovada pentru fiecare individual Hi, de ce să nu trimitem în loc dovada că
dlog(p(0)G, G) = dlog(H0, H)
Problema este că, prin Protocolul Schnorr, nu se poate crea o astfel de dovadă, deoarece nimeni nu cunoaște valoarea p(0), necesară pentru a crea dovada, iar mai mult, întregul generator de numere aleatoare se bazează pe faptul că nimeni nu știe această valoare. Prin urmare, este necesar să avem toate valorile Salut și dovezile lor individuale pentru a demonstra corectitudinea H0.
Cu toate acestea, dacă ar exista o operație pe punctele de pe curbele eliptice care să fie semantic asemănătoare cu înmulțirea, dovada corectitudinii H0 ar fi trivială, am verifica pur și simplu că
H0 × G = p(0)G × H
Dacă curba aleasă susține , această dovadă funcționează. În acest caz H0 – este nu doar ieșirea generatorului de numere aleatoare, pe care o poate verifica orice participant care știe G, H și p(0)G. H0 – este de asemenea o semnătură pe un mesaj care a fost utilizat ca seed, confirmând că k și n participanții au semnat acest mesaj. Astfel, dacă seed – este hash-ul blocului în protocolul blockchain, atunci H0 – este simultan o semnătură multi-pe bloc, și un număr aleatoriu foarte bun.
În concluzie
Acest articol este parte dintr-o serie de articole tehnice pe blog . NEAR – este un protocol blockchain și o platformă pentru dezvoltarea aplicațiilor descentralizate, axată pe simplitatea dezvoltării și ușurința 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
