Ciao, Habr!
In Nell'articolo abbiamo discusso perché potrebbe essere necessario generare numeri casuali per partecipanti che non si fidano l'uno dell'altro, quali requisiti vengono posti a tali generatori di numeri casuali e abbiamo esaminato due approcci per la loro implementazione.
In questa parte dell'articolo esamineremo in dettaglio un altro approccio che utilizza le firme soglia.
Un po' di crittografia
Per comprendere come funzionano le firme soglia, è necessario avere una comprensione base della crittografia. Utilizzeremo due concetti: scalari, o semplicemente numeri, che indicheremo con lettere minuscole (x, y) e punti su una curva ellittica, che indicheremo con lettere maiuscole.
Per capire le basi delle firme soglia non è necessario comprendere come funzionano le curve ellittiche, a parte alcune nozioni fondamentali:
I punti su una curva ellittica possono essere sommati e moltiplicati per uno scalare (la moltiplicazione per uno scalare sarà indicata come xG, sebbene anche la notazione Gx sia spesso utilizzata nella letteratura). Il risultato della somma e della moltiplicazione per uno scalare è un punto sulla curva ellittica.
Sapendo solo il punto G e il suo prodotto con lo scalare xG non si può calcolare x.
Utilizzeremo anche il concetto di polinomio p(x) di grado k-1. In particolare, useremo la seguente proprietà dei polinomi: se conosciamo il valore p(x) per qualsiasi k diverso x (e non abbiamo ulteriori informazioni su p(x)), possiamo calcolare p(x) per qualsiasi altro x.
È interessante notare che per qualsiasi polinomio p(x) e un certo punto sulla curva G, conoscendo il valore p(x)G per qualsiasi k di valori diversi x, si può calcolare anche p(x)G per qualsiasi x.
Queste informazioni sono sufficienti per approfondire i dettagli su come funzionano le firme soglia e come utilizzarle per generare numeri casuali.
Generatore di numeri casuali basato su firme soglia
Supponiamo che n partecipanti vogliano generare un numero casuale, e vogliamo che la partecipazione di qualsiasi k di essi sia sufficiente per generare il numero, ma che i malintenzionati che controllano k-1 o meno partecipanti non possano prevedere o influenzare il numero generato.
Supponiamo esista un tale polinomio p(x) di grado k-1, in modo che il primo partecipante conosca p(1), il secondo conosca p(2), e così via (n-esimo conosce p(n)). Supponiamo anche che per un certo punto prestabilito G tutti conoscano p(x)G per tutti i valori x. Lo chiameremo p(i) “componente privata” i-o partecipante (perché solo i-il partecipante conosce il suo), e p(i)G “componente pubblica” i-o partecipante (perché tutti i partecipanti la conoscono). Come ricorderete, la conoscenza p(i)G non è sufficiente per ricostruire p(i).
Creare un tale polinomio in modo che solo i--o partecipante e nessun altro conosca la propria componente privata è la parte più complessa e interessante del protocollo, e la analizzeremo di seguito. Supponiamo per ora di avere un tale polinomio e che tutti i partecipanti conoscano le proprie componenti private.
Come possiamo utilizzare un tale polinomio per generare un numero casuale? Per iniziare, abbiamo bisogno di una stringa che non sia stata precedentemente utilizzata come input per il generatore. Nel caso della blockchain, l'hash dell'ultimo blocco h è un buon candidato per tale stringa. Supponiamo che i partecipanti vogliano creare un numero casuale, utilizzando h come seed. Prima di tutto, i partecipanti convertono h in un punto sulla curva usando qualunque funzione prestabilita:
H = scalarToPoint(h)
Poi ogni partecipante i calcola e pubblica Hi = p(i)H, cosa che possono fare perché conoscono p(i) e H. La rivelazione Hi non consente agli altri partecipanti di ricostruire la componente privata i-o partecipante, e quindi un insieme di componenti private può essere utilizzato da un blocco all'altro. Così, il costoso algoritmo di creazione del polinomio, descritto di seguito, deve essere eseguito solo una volta.
Quando k Una volta che i partecipanti hanno rivelato Hi = 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. A questo punto, tutti i partecipanti calcolano H0 = p(0)H, e questo sarà il numero casuale risultante. Si noti che nessuno conosce p(0), e quindi l'unico modo per calcolare p(0)H è l'interpolazione p(x)H, che è possibile solo quando k i valori p(i)H sono noti. La rivelazione di un numero inferiore p(i)H non fornisce alcuna informazione su p(0)H.
Il generatore sopra ha tutte le proprietà che desideriamo: gli aggressori che controllano solo k-1 partecipanti, o meno, non hanno alcuna informazione o influenza sull'output, mentre qualsiasi k partecipante può calcolare il numero risultante, e qualsiasi sottoinsieme di k partecipanti arriverà sempre allo stesso risultato per lo stesso seed.
C'è un problema che abbiamo eluso con attenzione sopra. Affinché l'interpolazione funzioni, è importante che il valore Hi pubblicato da ciascun partecipante i sia realmente uguale a p(i)H. Poiché nessuno oltre al i-esimo partecipante sa p(i), nessuno oltre al i--esimo partecipante può verificare che Hi sia davvero calcolato correttamente, e senza alcuna prova crittografica di correttezza Hi un attaccante potrebbe 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 diversi di H_0
Ci sono almeno due modi per dimostrare la correttezza Hi, li esamineremo dopo aver trattato la generazione del polinomio.
Generazione del polinomio
Nella sezione precedente abbiamo supposto di avere un tale polinomio p(x) di grado k-1 tale che il partecipante i conosce p(i), e nessun altro ha alcuna informazione su questo valore. Nella sezione successiva avremo anche bisogno che per un certo punto prefissato G tutti sappiano p(x)G per tutti x.
In questa sezione presupporremo che ogni partecipante abbia localmente una certa chiave privata xi, tale che la corrispondente chiave pubblica Xi sia nota.
Un possibile protocollo di generazione del polinomio è il seguente:
Ogni partecipante i crea localmente un polinomio arbitrario pi(x) di grado k-1. Essi quindi inviano a ciascun partecipante j valore pi(j), crittografato con la chiave pubblica Xj. Così solo i--esimo e j--esimo partecipante conosce pi(j). Il partecipante i annuncia anche pubblicamente pi(j)G per tutti j di 1 fino a k incluso.
Tutti i partecipanti usano un certo consenso per scegliere k i partecipanti i cui polinomi verranno usati. Poiché alcuni partecipanti potrebbero essere offline, non possiamo aspettare che tutti n i partecipanti pubblicano i polinomi. Il risultato di questo passo è un insieme Z composto da almeno k polinomi, creati nel passo (1).
I partecipanti si assicurano che i valori a loro noti pi(j) corrispondano ai pubblicamente annunciati pi(j)G. Dopo questo passo rimarranno nei Z solo i polinomi per i quali i privati trasmessi pi(j) corrispondano ai pubblicamente annunciati pi(j)G.
Ogni partecipante j calcolano il proprio componente privato p(j) come somma pi(j) per tutti i in Z. Ogni partecipante calcola anche tutti i valori p(x)G come somma pi(x)G per tutti i i in Z.
Si prega di notare che p(x) – è davvero un polinomio di grado k-1, poiché è la somma di singoli pi(x), ognuno dei quali è un polinomio di grado k-1. Successivamente, fai attenzione che mentre ogni partecipante j conosce p(j), non hanno alcuna informazione su p(x) per x ≠ j. Infatti, per calcolare questo valore, hanno bisogno di conoscere tutti pi(x), e finché il partecipante j non conosce almeno uno dei polinomi scelti, non hanno informazioni sufficienti su p(x).
Questo è l'intero processo di generazione del polinomio, che era necessario nel capitolo precedente. I passaggi 1, 2 e 4 sopra hanno una realizzazione piuttosto ovvia. Tuttavia, il passo 3 non è così triviale.
In particolare, dobbiamo essere in grado di dimostrare che i cifrati pi(j) corrispondono effettivamente a quanto pubblicato pi(j)G. Se non possiamo dimostrarlo, un attaccante i può inviare spazzatura al posto di pi(j) al partecipante j, e il partecipante j non sarà in grado di ottenere il reale valore pi(j), e non potrà calcolare il proprio componente privato.
Esiste un protocollo crittografico che consente di creare un messaggio aggiuntivo proofi(j), in modo tale che qualsiasi partecipante, avendo un certo valore e, e anche proofi(j) e pi(j)G, può verificare localmente che e – è davvero pi(j), cifrato con la chiave del partecipante j. Sfortunatamente, la dimensione di tale prova è incredibilmente grande, e considerando che è necessario pubblicare O(nk) prove di questo tipo, non può essere utilizzato per questo scopo.
Invece di dimostrare che pi(j) corrisponde a pi(j)G possiamo nel protocollo di generazione del polinomio dedicare un periodo di tempo molto ampio, durante il quale tutti i partecipanti verificano i cifrati ricevuti pi(j), e se il messaggio decifrato non corrisponde al pubblico pi(j)G, pubblicano una prova crittografica che l'informazione cifrata ricevuta è errata. Dimostrare che il messaggio non corrisponde a pi(G) è molto più semplice che dimostrare che esso corrisponde. Va notato che questo richiede che ogni partecipante appaia in rete almeno una volta nel periodo di tempo dedicato alla generazione di tali prove, e dipende dall'assunzione che se pubblicano tale prova, raggiungerà tutti gli altri partecipanti entro lo stesso periodo di tempo.
Se un partecipante non appare in rete in questo periodo di tempo, e ha effettivamente almeno un componente errato, quel particolare partecipante non sarà in grado di partecipare alla successiva generazione di numeri. Il protocollo, tuttavia, continuerà a funzionare se ci sono almeno k partecipanti che hanno ricevuto solo componenti corretti o hanno avuto il tempo di lasciare prova dell'erroneità nei tempi previsti.
Prove di correttezza H_i
L'ultima parte da discutere è come dimostrare la correttezza dei pubblicati Hi, ossia che Hi = p(i)H, senza rivelazione p(i).
Ricordiamo che i valori H, G, p(i)G sono pubblici e noti a tutti. L'operazione di ottenere p(i) sapendo p(i)G e G si chiama logaritmo discreto, o dlog, e vogliamo dimostrare che:
dlog(p(i)G, G) = dlog(Hi, H)
senza rivelazione p(i). Esistono costruzioni per tali prove, ad esempio.
Con tale costruzione, ogni partecipante insieme a Hi invia la prova di correttezza secondo la costruzione.
Quando un numero casuale è generato, spesso deve essere utilizzato da partecipanti diversi da quelli che lo hanno generato. A tali partecipanti è necessario inviare insieme al numero tutti Hi e le prove correlate.
Un lettore curioso potrebbe chiedere: poiché il numero casuale finale è H0, e p(0)G – è informazione pubblica, perché è necessaria una prova per ogni singolo Hi, perché invece non inviare una prova che
dlog(p(0)G, G) = dlog(H0, H)
Il problema è che con il Protocollo di Schnorr non è possibile creare una tale prova, perché nessuno conosce il valore p(0), necessario per creare la prova e, inoltre, tutto il 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 delle curve ellittiche che sia semanticamente simile alla moltiplicazione, la prova di correttezza H0 sarebbe banale, ci assicureremmo semplicemente che
H0 × G = p(0)G × H
Se la curva scelta supporta , tale prova funziona. In questo caso H0 non è solo l'output del generatore di numeri casuali, che può essere verificato da qualsiasi partecipante che conosce G, H e p(0)G. H0 è anche una firma su un messaggio che è stato usato come seed, a conferma che k e n i partecipanti hanno firmato questo messaggio. In questo modo, se il seed – è l'hash di un blocco nel protocollo blockchain, allora H0 è contemporaneamente una multi-firma su un blocco e un ottimo numero casuale.
In conclusione
Questo articolo è parte di una serie di articoli tecnici nel blog . NEAR è un protocollo blockchain e una piattaforma per lo sviluppo di applicazioni decentralizzate, con un focus sulla semplicità di sviluppo e sull'usabilità per gli utenti finali.
Il codice del protocollo è aperto, la nostra implementazione è scritta in Rust, ed è possibile trovarla .
Puoi vedere come appare lo sviluppo su NEAR e sperimentare nell'online IDE .
Puoi seguire tutte le novità in russo nel e in , e in inglese nel ufficiale .
A presto!
Fonte: habr.com
