És possible generar números aleatoris si no ens confiem? Part 2

Hola Habr!

В la primera part En aquest article, vam discutir per què podria ser necessari generar números aleatoris per als participants que no confien entre ells, quins requisits es proposen per a aquests generadors de números aleatoris i vam considerar dos enfocaments per a la seva implementació.

En aquesta part de l'article, analitzarem més de prop un altre enfocament que utilitza signatures de llindar.

Una mica de criptografia

Per entendre com funcionen les signatures de llindar, heu d'entendre una mica de criptografia bàsica. Utilitzarem dos conceptes: escalars, o simplement nombres, que denotarem amb lletres minúscules (x, i) i punts de la corba el·líptica, que denotarem amb majúscules.

Per entendre els conceptes bàsics de les signatures de llindar, no cal que entengueu com funcionen les corbes el·líptiques, a part d'algunes coses bàsiques:

1. Els punts d'una corba el·líptica es poden sumar i multiplicar per un escalar (indicarem la multiplicació per un escalar com xG, encara que la notació Gx també s'utilitza sovint a la literatura). El resultat de la suma i la multiplicació per un escalar és un punt en una corba el·líptica.

2. Saber només el punt G i el seu producte amb un escalar xG no es pot calcular x.

També utilitzarem el concepte de polinomi p (x) grau k-1. En particular, utilitzarem la següent propietat dels polinomis: si coneixem el valor p (x) per ningu k diferent x (i no tenim més informació sobre p (x)), podem calcular p (x) per a qualsevol altre x.

Curiosament, per a qualsevol polinomi p (x) i algun punt de la corba Gconeixent el significat p(x)G per ningu k significats diferents x, també podem calcular p(x)G per ningu x.

Aquesta és informació suficient per aprofundir en els detalls de com funcionen les signatures de llindar i com utilitzar-les per generar números aleatoris.

Generador de números aleatoris en signatures de llindar

Diguem-ho n els participants volen generar un nombre aleatori i volem que tothom hi participi k n'hi havia prou per generar un nombre, però perquè els atacants que controlen k-1 o menys participants no van poder predir ni influir en el nombre generat.

Suposem que hi ha aquest polinomi p (x) grau k-1 el que sap el primer participant pàg (1), el segon ho sap p(2), etcètera (n-th sap p(n)). També assumim que per a algun punt predeterminat G tothom sap p(x)G per a tots els valors x. trucarem Pi) "component privat" iparticipant (perquè només iel participant-è la coneix), i p(i)G "component públic" i-è participant (perquè tots els participants la coneixen). Com recordeu, coneixement p(i)G no n'hi ha prou per restaurar Pi).

Creant aquest polinomi de manera que només i-El tercer participant i ningú més coneixia el seu component privat: aquesta és la part més complexa i interessant del protocol, i l'analitzarem a continuació. De moment, suposem que tenim aquest polinomi i que tots els participants coneixen els seus components privats.

Com podem utilitzar aquest polinomi per generar un nombre aleatori? Per començar, necessitem una cadena que no s'hagi utilitzat prèviament com a entrada al generador. En el cas d'una cadena de blocs, el hash de l'últim bloc h és un bon candidat per a aquesta línia. Permet que els participants vulguin crear un nombre aleatori amb h com la llavor. Els participants es converteixen primer h a un punt de la corba utilitzant qualsevol funció predefinida:

H = escalarToPoint(h)

Després cada participant i calcula i publica Hi = p(i)H, què poden fer perquè ho saben p (i) i H. Divulgació HNo permeto que altres participants recuperin el component privat iparticipant, i per tant es pot utilitzar un conjunt de components privats de bloc en bloc. Per tant, el costós algorisme de generació de polinomis descrit a continuació només s'ha d'executar una vegada.

Quan k els participants van ser autopsiats Hi = p(i)H, tothom pot calcular Hx = p(x)H per a tot x gràcies a la propietat dels polinomis que hem comentat a l'últim apartat. En aquest moment, tots els participants calculen H0 = p(0)H, i aquest és el nombre aleatori resultant. Tingueu en compte que ningú ho sap p(0), i per tant l'única manera de calcular p(0)H – això és la interpolació p(x)H, que només és possible quan k valors p(i)H conegut. Obrint qualsevol quantitat menor p(i)H no proporciona cap informació sobre p(0)H.

El generador de dalt té totes les propietats que volem: els atacants només controlen k-1 participants o menys no tenen informació ni influència en la conclusió, mentre que n'hi ha cap k els participants poden calcular el nombre resultant i qualsevol subconjunt de k els participants sempre arribaran al mateix resultat per la mateixa llavor.

Hi ha un problema que hem evitat amb cura més amunt. Perquè la interpolació funcioni, és important que el valor Hi que va ser publicat per cada participant i realment era el mateix p(i)H. Ja que ningú excepte i-è participant no ho sap Pi), ningú excepte i-El participant no pot verificar-ho Hi realment calculat correctament, i sense cap prova criptogràfica de correcció Hun atacant pot publicar qualsevol valor com Hola, i influir arbitràriament en la sortida del generador de nombres aleatoris:

Els diferents valors de H_1 enviats pel primer participant donen lloc a un H_0 resultant diferent

Hi ha almenys dues maneres de demostrar la correcció Hi, els considerarem després d'analitzar la generació del polinomi.

Generació de polinomis

A l'últim apartat vam suposar que tenim aquest polinomi p (x) grau k-1 que el participant i sap Pi), i ningú més té cap informació sobre aquest valor. A la següent secció també ho necessitarem per a algun punt predeterminat G tothom ho sabia p(x)G per a tot x.

En aquesta secció assumirem que cada participant té localment alguna clau privada xi, de manera que tothom conegui la clau pública corresponent Xi.

Un possible protocol de generació de polinomis és el següent:

1. Cada participant i localment crea un polinomi arbitrari pi(x) grau k-1. Després envien a cada participant j значение pi(j), xifrat amb clau pública Xj. Només així i-th и j-th el participant sàpiga pi (j). Participant i també ho anuncia públicament pi(j)G per a tot j d' 1 до k inclusiu.

2. Tots els participants fan servir un cert consens per triar k participants els polinomis dels quals s'utilitzaran. Com que alguns participants poden estar fora de línia, no podem esperar fins que tothom n els participants publicaran polinomis. El resultat d'aquest pas és un conjunt Z format almenys per k polinomis creats al pas (1).

3. Els participants s'asseguren que els valors que coneixen pi(j) corresponen a anunciats públicament pi(j)G. Després d'aquest pas Z només polinomis per als quals es transmeten de manera privada pi(j) corresponen a anunciats públicament pi(j)G.

4. Cada participant j calcula el seu component privat p(j) com a suma pi(j) per a tots i в Z. Cada participant també calcula tots els valors p(x)G com a suma pi(x)G per a tot i в Z.

Tingueu en compte que p(x) – realment és un polinomi k-1, perquè és la suma de l'individu pi(x), cadascun dels quals és un polinomi de grau k-1. A continuació, tingueu en compte que mentre cada participant j sap p(j), no tenen informació sobre p (x) per x ≠ j. De fet, per calcular aquest valor, necessiten saber-ho tot pi(x), i sempre que el participant j no coneix almenys un dels polinomis seleccionats, no en tenen prou informació p(x).

Aquest és tot el procés de generació de polinomis que es necessitava a la darrera secció. Els passos 1, 2 i 4 anteriors tenen una implementació força òbvia. Però el pas 3 no és tan trivial.

Concretament, hem de ser capaços de demostrar-ho xifrat pi(j) corresponen realment a les publicades pi(j)G. Si no ho podem demostrar, l'atacant i pot enviar escombraries pi(j) al participant j, i participant j no podrà obtenir el valor real pi(j), i no podrà calcular el seu component privat.

Hi ha un protocol criptogràfic que permet crear un missatge addicional provai(j), de manera que qualsevol participant, tingui algun valor e, així com prova (j) и pi(j)G, pot verificar-ho localment e - es realment pi(j), xifrat amb la clau del participant j. Malauradament, la mida d'aquestes proves és increïblement gran i, atès que cal publicar-les O(nk) Aquestes proves no es poden utilitzar amb aquesta finalitat.

En lloc de demostrar-ho pi(j) correspon pi(j)G podem assignar un període de temps molt gran en el protocol de generació de polinomis, durant el qual tots els participants comproven el xifrat rebut. pi(j), i si el missatge desxifrat no correspon al públic pi(j)G, publiquen una prova criptogràfica que el missatge xifrat que han rebut és incorrecte. Demostra que el missatge no correspon pi(G) molt més fàcil que demostrar que coincideix. Cal tenir en compte que això requereix que cada participant aparegui en línia almenys una vegada durant el temps assignat per crear aquestes proves, i es basa en el supòsit que si publiquen aquesta prova, arribarà a tots els altres participants en el mateix temps assignat.

Si un participant no va aparèixer en línia durant aquest període de temps i tenia almenys un component incorrecte, aquest participant en concret no podrà participar en la generació de números addicionals. El protocol, però, continuarà funcionant si almenys n'hi ha k participants que acaben de rebre els components correctes o han aconseguit deixar una prova d'incorrecció en el temps assignat.

Proves de correcció de H_i

L'última part que queda per discutir és com demostrar la correcció de publicades Hi, és a dir, això Hi = p(i)H, sense obrir Pi).

Recordem que els valors H, G, p(i)G públic i conegut per tothom. Operació de recepció Pi) saber p(i)G и G anomenat logaritme discret, o dlog, i volem demostrar que:

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

sense revelació Pi). Existeixen construccions per a aquestes proves, per exemple Protocol de Schnorr.

Amb aquest disseny, cada participant, juntament amb Hi envia una prova de correcció segons el disseny.

Una vegada que s'ha generat un nombre aleatori, sovint ha de ser utilitzat per participants diferents dels que l'han generat. Aquests participants, juntament amb el número, han d'enviar-los tots Hi i proves relacionades.

Un lector curiós pot preguntar: ja que el nombre aleatori final és H0, i p(0)G – Aquesta és informació pública, per què necessitem una prova per a cada individu Hi, per què no enviar una prova en lloc d'això

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

El problema és que aquesta prova no es pot crear amb el protocol Schnorr perquè ningú en coneix el valor pàg (0), necessari per crear la prova i, a més, tot el generador de números aleatoris es basa en el fet que ningú coneix aquest valor. Per tant, cal tenir tots els valors Hi i les seves proves individuals per demostrar la correcció H0.

Tanmateix, si hi hagués alguna operació sobre punts de corbes el·líptiques que sigui semànticament similar a la multiplicació, la prova de correcció H0 seria trivial, simplement ens asseguraríem que això

H0 × G = p(0)G × H

Si la corba seleccionada és compatible aparellaments de corbes el·líptiques, aquesta prova funciona. En aquest cas H0 no és només la sortida d'un generador de números aleatoris, que pot ser verificat per qualsevol participant que ho sàpiga G, H и p(0)G. H0 també és una signatura al missatge que es va utilitzar com a llavor, confirmant-ho k и n els participants han signat aquest missatge. Així, si llavor - és el hash del bloc al protocol blockchain, doncs H0 és alhora una signatura múltiple en un bloc i un nombre aleatori molt bo.

en conclusió

Aquest article forma part d'una sèrie de blocs tècnics A PROP. NEAR és un protocol i una plataforma blockchain per desenvolupar aplicacions descentralitzades amb èmfasi en la facilitat de desenvolupament i la facilitat d'ús per als usuaris finals.

El codi del protocol és obert, la nostra implementació està escrita en Rust, es pot trobar aquí.

Podeu veure com és el desenvolupament de NEAR i experimentar a l'IDE en línia aquí.

Podeu seguir totes les notícies en rus a grup de telegrames i grup a VKontakte, i en anglès a l'oficial twitter.

Fins aviat!

Font: www.habr.com