È possibile generare numeri casuali se non ci fidiamo l'uno dell'altro? Parte 2

Ehi Habr!

В la prima parte In questo articolo abbiamo discusso del motivo per cui potrebbe essere necessario generare numeri casuali per i partecipanti che non si fidano l'uno dell'altro, quali requisiti sono avanzati per tali generatori di numeri casuali e abbiamo considerato due approcci alla loro implementazione.

In questa parte dell'articolo esamineremo più da vicino un altro approccio che utilizza le firme di soglia.

Un po' di crittografia

Per capire come funzionano le firme di soglia, è necessario comprendere un po' di crittografia di base. Utilizzeremo due concetti: scalari, o semplicemente numeri, che indicheremo con lettere minuscole (x, y) e punti sulla curva ellittica, che indicheremo con lettere maiuscole.

Per comprendere le basi delle firme di soglia, non è necessario capire come funzionano le curve ellittiche, a parte alcune cose basilari:

1. I punti su una curva ellittica possono essere sommati e moltiplicati per uno scalare (denoteremo la moltiplicazione per uno scalare come xG, sebbene la notazione Gx spesso utilizzato anche in letteratura). Il risultato dell'addizione e della moltiplicazione per uno scalare è un punto su una curva ellittica.

2. Conoscendo solo il punto G e il suo prodotto con uno scalare xG non può essere calcolato x.

Utilizzeremo anche il concetto di polinomio p(x) степени k-1. In particolare utilizzeremo la seguente proprietà dei polinomi: se ne conosciamo il valore p(x) per ogni k diverso x (e non abbiamo ulteriori informazioni a riguardo p(x)), possiamo calcolare p(x) per chiunque altro x.

È interessante che per qualsiasi polinomio p(x) e qualche punto sulla curva Gconoscendone il significato p(x)G per ogni k significati diversi x, possiamo anche calcolare p(x)G per ogni x.

Queste sono informazioni sufficienti per approfondire i dettagli di come funzionano le firme di soglia e come utilizzarle per generare numeri casuali.

Generatore di numeri casuali sulle firme di soglia

Diciamo questo n i partecipanti vogliono generare un numero casuale e vogliamo che chiunque partecipi k ce n'erano abbastanza per generare un numero, ma in modo che gli aggressori lo controllassero k-1 o meno partecipanti non hanno potuto prevedere o influenzare il numero generato.

Supponiamo che esista un tale polinomio p(x) степени k-1 ciò che sa il primo partecipante p (1), il secondo lo sa p(2), e così via (n-lo sa p(n)). Lo assumiamo anche per un punto predeterminato G lo sanno tutti p(x)G per tutti i valori x. Chiameremo pi) “componente privata” i° partecipante (perché solo il'esimo partecipante la conosce), e maiale “componente pubblica” i-esima partecipante (perché tutti i partecipanti la conoscono). Come ricordi, conoscenza maiale non abbastanza per ripristinare pi).

Creare un polinomio tale che solo i-Il primo partecipante e nessun altro conosceva la sua componente privata: questa è la parte più complessa e interessante del protocollo e la analizzeremo di seguito. Per ora, supponiamo di avere un polinomio di questo tipo e che tutti i partecipanti conoscano le loro componenti private.

Come possiamo usare un polinomio del genere per generare un numero casuale? Per cominciare, abbiamo bisogno di una stringa che non sia stata precedentemente utilizzata come input per il generatore. Nel caso di una blockchain, l'hash dell'ultimo blocco h è un buon candidato per una linea del genere. Lascia che i partecipanti vogliano creare un numero casuale utilizzando h come il seme. I partecipanti si convertono per primi h ad un punto sulla curva utilizzando qualsiasi funzione predefinita:

H = scalarToPoint(h)

Poi ogni partecipante i calcola e pubblica Ciao = p(i)H, cosa possono fare perché lo sanno p(i) e H. rivelazione Hnon consento ad altri partecipanti di ripristinare la componente privata ipartecipante, e quindi un set di componenti privati ​​può essere utilizzato da un blocco all'altro. Pertanto, il costoso algoritmo di generazione dei polinomi descritto di seguito deve essere eseguito solo una volta.

Quando k i partecipanti sono stati sottoposti ad autopsia Ciao = p(i)H, tutti possono calcolare Hx = p(x)H per tutti x grazie alla proprietà dei polinomi di cui abbiamo parlato nella sezione precedente. In questo momento, tutti i partecipanti calcolano H0 = p(0)H, e questo è il numero casuale risultante. Tieni presente che nessuno lo sa p(0), e quindi l'unico modo per calcolare p(0)H – questa è l'interpolazione p(x)H, che è possibile solo quando k valori p(i)H conosciuto. Apertura di qualsiasi quantità inferiore p(i)H non fornisce alcuna informazione in merito p(0)H.

Il generatore sopra ha tutte le proprietà che vogliamo: solo controllo degli attaccanti k-1 partecipante o meno non hanno alcuna informazione o influenza sulla conclusione, mentre qualsiasi k i partecipanti possono calcolare il numero risultante e qualsiasi sottoinsieme di k i partecipanti arriveranno sempre allo stesso risultato per lo stesso seme.

C'è un problema che abbiamo accuratamente evitato sopra. Affinché l'interpolazione funzioni, è importante che il valore value Hi che è stato pubblicato da ciascun partecipante i era davvero lo stesso p(i)H. Dal momento che nessuno tranne i-il partecipante non lo sa pi), nessuno tranne i-il partecipante non può verificarlo Hi effettivamente calcolato correttamente e senza alcuna prova crittografica di correttezza Hun utente malintenzionato può pubblicare qualsiasi valore come Ciao, e influenzare arbitrariamente l'output del generatore di numeri casuali:

Valori diversi di H_1 inviati dal primo partecipante portano a risultati H_0 diversi

Ci sono almeno due modi per dimostrare la correttezza Hi, li considereremo dopo aver analizzato la generazione del polinomio.

Generazione di polinomi

Nell'ultima sezione abbiamo ipotizzato di avere un tale polinomio p(x) степени k-1 che il partecipante i egli sa pi)e nessun altro ha informazioni su questo valore. Nella prossima sezione avremo bisogno anche di quello per qualche punto predeterminato G tutti sapevano p(x)G per tutti x.

In questa sezione assumeremo che ogni partecipante abbia localmente una chiave privata xi, in modo tale che tutti conoscano la chiave pubblica corrispondente Xi.

Un possibile protocollo di generazione di polinomi è il seguente:

1. Ogni partecipante i localmente crea un polinomio arbitrario pi(x) grado k-1. Quindi inviano ciascun partecipante j значение pi(j), crittografato con chiave pubblica Xj. Solo così i-esimo и j-esimo il partecipante lo sa pio(j). Partecipante i annuncia anche pubblicamente pi(j)G per tutti j от 1 a k compreso.

2. Tutti i partecipanti utilizzano un certo consenso per scegliere k partecipanti i cui polinomi verranno utilizzati. Poiché alcuni partecipanti potrebbero essere offline, non possiamo aspettare che siano tutti n i partecipanti pubblicheranno i polinomi. Il risultato di questo passaggio è un set Z composto da almeno k polinomi creati nel passaggio (1).

3. I partecipanti si assicurano che i valori che conoscono pi(j) corrisponde a quanto annunciato pubblicamente pi(j)G. Dopo questo passaggio Z solo polinomi per i quali trasmessi privatamente pi(j) corrisponde a quanto annunciato pubblicamente pi(j)G.

4. Ogni partecipante j calcola la sua componente privata p(j) come somma pi(j) per tutti i в Z. Ogni partecipante calcola anche tutti i valori p(x)G come somma pi(x)G per ogni i в Z.

Si noti che p(x) – è davvero un polinomio k-1, perché è la somma dell'individuo pi(x), ciascuno dei quali è un polinomio di grado k-1. Quindi, nota che mentre ogni partecipante j egli sa p(j), non hanno informazioni su p(x) per x ≠ j. Infatti, per calcolare questo valore, devono sapere tutto pi(x), e finché il partecipante j non conosce almeno uno dei polinomi selezionati, di cui non ha informazioni sufficienti p(x).

Questo è l'intero processo di generazione dei polinomi necessario nell'ultima sezione. I passaggi 1, 2 e 4 sopra hanno un'implementazione abbastanza ovvia. Ma il passaggio 3 non è così banale.

Nello specifico, dobbiamo essere in grado di dimostrarlo crittografato pi(j) corrispondono realmente a quelli pubblicati pi(j)G. Se non possiamo provarlo, l'aggressore i potrebbe invece inviare spazzatura pi(j) al partecipante je partecipante j non sarà in grado di ottenere il valore reale pi(j), e non sarà in grado di calcolare la sua componente privata.

Esiste un protocollo crittografico che ti consente di creare un messaggio aggiuntivo provai(j), tale che qualsiasi partecipante, avente un certo valore e, oltre prova(j) и pi(j)G, può verificarlo localmente e - è davvero pi(j), crittografato con la chiave del partecipante j. Sfortunatamente, la dimensione di tali prove è incredibilmente grande e, pertanto, è necessario pubblicarle O (nk) Tali prove non possono essere utilizzate per questo scopo.

Invece di dimostrarlo pi(j) fiammiferi pi(j)G possiamo allocare un periodo di tempo molto lungo nel protocollo di generazione del polinomio, durante il quale tutti i partecipanti controllano i dati crittografati ricevuti pi(j), e se il messaggio decriptato non corrisponde al pubblico pi(j)G, pubblicano una prova crittografica che il messaggio crittografato ricevuto non è corretto. Dimostrare che il messaggio no fiammiferi maiale) molto più semplice che dimostrare che corrisponde. Va notato che ciò richiede che ciascun partecipante si presenti online almeno una volta durante il tempo assegnato per creare tali prove e si basa sul presupposto che, se pubblicano tale prova, raggiungeranno tutti gli altri partecipanti nello stesso tempo assegnato.

Se un partecipante non è apparso online durante questo periodo di tempo e aveva almeno un componente errato, quel particolare partecipante non sarà in grado di partecipare all'ulteriore generazione del numero. Il protocollo, tuttavia, continuerà a funzionare se almeno ci sarà k partecipanti che hanno appena ricevuto i componenti corretti o sono riusciti a lasciare una prova di errore entro il tempo assegnato.

Prove di correttezza di H_i

L'ultima parte che resta da discutere è come dimostrare la correttezza della pubblicazione Hio, cioè quello Ciao = p(i)H, senza aprire pi).

Ricordiamoci che i valori H, G, p(i)G pubblico e conosciuto da tutti. Ricevi l'operazione pi) sapendo maiale и G chiamato logaritmo discreto, o blog, e vogliamo dimostrare che:

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

senza divulgazione pi). Esistono, ad esempio, costruzioni per tali dimostrazioni Protocollo Schnorr.

Con questo disegno, ogni partecipante, insieme Hi invia una prova di correttezza secondo il progetto.

Una volta generato un numero casuale, spesso deve essere utilizzato da partecipanti diversi da quelli che lo hanno generato. Tali partecipanti, insieme al numero, devono inviare tutto Hi e relative prove.

Un lettore curioso potrebbe chiedere: poiché il numero casuale finale è H0 e p(0)G – Queste sono informazioni pubbliche, perché abbiamo bisogno di prove per ogni individuo Hio, perché invece non inviarne la prova

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

Il problema è che una prova del genere non può essere creata utilizzando il protocollo Schnorr perché nessuno ne conosce il valore p (0), necessario per creare la prova, e inoltre l'intero generatore di numeri casuali si basa sul fatto che nessuno conosce questo valore. Pertanto è necessario avere tutti i valori Hi e le loro prove individuali per dimostrare la correttezza H0.

Tuttavia, se ci fosse qualche operazione sui punti sulle curve ellittiche che è semanticamente simile alla moltiplicazione, la prova di correttezza H0 sarebbe banale, ci assicureremmo semplicemente che sia così

H0 × G = p(0)G × H

Se la curva selezionata supporta accoppiamenti di curve ellittiche, questa prova funziona. In questo caso H0 non è solo l'output di un generatore di numeri casuali, che può essere verificato da qualsiasi partecipante che lo sappia G, H и p(0)G. H0 è anche una firma sul messaggio che è stata utilizzata come seme, a conferma di ciò k и n i partecipanti hanno firmato questo messaggio. Quindi, se seme - è quindi l'hash del blocco nel protocollo blockchain H0 è sia una firma multipla su un blocco che un ottimo numero casuale.

insomma

Questo articolo fa parte di una serie di blog tecnici NEAR. NEAR è un protocollo e una piattaforma blockchain per lo sviluppo di applicazioni decentralizzate con particolare attenzione alla facilità di sviluppo e alla facilità d'uso per gli utenti finali.

Il codice del protocollo è aperto, la nostra implementazione è scritta in Rust, può essere trovata qui.

Puoi vedere come si presenta lo sviluppo per NEAR e sperimentare nell'IDE online qui.

Puoi seguire tutte le notizie in russo su gruppo telegrafico e gruppo su VKontaktee in inglese nel funzionario cinguettio.

Arrivederci!

Fonte: habr.com