Ciao, Habr!
In In questo articolo abbiamo discusso perché potrebbe essere necessario generare numeri casuali per i partecipanti che non si fidano l'uno dell'altro, quali requisiti devono avere tali generatori di numeri casuali e abbiamo esaminato due approcci alla loro implementazione.
In questa sezione dell'articolo esamineremo un altro approccio che utilizza le firme soglia.
Un po' di crittografia
Per comprendere come funzionano le firme soglia, è necessario sapere un po' di crittografia di base. Useremo 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 comprendere i fondamenti delle firme soglia non è necessario sapere come funzionano le curve ellittiche, a parte alcune nozioni di base:
I punti su una curva ellittica possono essere sommati e moltiplicati per uno scalare (la moltiplicazione per uno scalare sarà indicata come xG, anche se la notazione Gx è spesso usata nella letteratura). Il risultato della somma e della moltiplicazione per uno scalare è un punto sulla curva ellittica.
Conoscendo solo un punto G e il suo prodotto con uno 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 ogni 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ò anche calcolare p(x)G per qualsiasi x.
Queste informazioni sono sufficienti per approfondire i dettagli di come funzionano le firme soglia e come utilizzarle per generare numeri casuali.
Generatore di numeri casuali basato su firme soglia
Supponiamo che n i partecipanti vogliano generare un numero casuale, e vogliamo che la partecipazione di qualsiasi k di essi sia sufficiente per generare il numero, ma che gli attaccanti, che controllano k-1 o meno partecipanti, non possano prevedere o influenzare il numero generato.
Supponiamo che esista un polinomio p(x) di grado k-1, tale che il primo partecipante conosca p(1), il secondo conosca p(2), e così via (n-esimo conosce p(n)). Assume inoltre che, per un certo punto predeterminato G , tutti sappiano p(x)G per tutti i valori x. Noi ci riferiremo a p(i) come a "componente privata" idel partecipante - (perché solo i- il partecipante sa quale essa sia), e p(i)G come a "componente pubblica" idel partecipante - (perché tutti i partecipanti la conoscono). Come ricorderete, conoscere p(i)G non è sufficiente per ricostruire p(i).
Creare un polinomio tale che solo il partecipante i-conosca la sua componente privata è la parte più complessa e interessante del protocollo, e la esamineremo di seguito. Supponiamo per ora che abbiamo un tale polinomio e che tutti i partecipanti conoscano le proprie componenti private.
Come possiamo utilizzare questo polinomio per generare un numero casuale? Innanzitutto abbiamo bisogno di una stringa che non sia mai stata usata come input per il generatore. Nel caso della blockchain, l'hash dell'ultimo blocco h è un buon candidato per tale stringa. Poniamo che i partecipanti vogliano creare un numero casuale utilizzando h come seme. Inizialmente, i partecipanti convertono h in un punto sulla curva usando qualsiasi funzione definita in anticipo:
H = scalarToPoint(h)
Dopodiché, ogni partecipante i calcola e pubblica Hi = p(i)H, cosa che possono fare, poiché conoscono p(i) e H. Rivelazione Hnon consente ad altri partecipanti di ripristinare il componente privato i-o partecipante, e quindi un insieme di componenti privati può essere utilizzato da blocco a blocco. Pertanto, il costoso algoritmo di generazione del polinomio, descritto di seguito, deve essere eseguito solo una volta.
Quando k i partecipanti hanno rivelato Hi = p(i)H, tutti possono calcolare Hx = p(x)H per tutti x grazie alla proprietà dei polinomi che abbiamo discusso nel capitolo precedente. A questo punto, tutti i partecipanti calcolano H0 = p(0)H, e questo è 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. Rivelare un numero inferiore p(i)H non fornisce alcuna informazione su p(0)H.
Il generatore sopra ha tutte le proprietà che desideriamo: i malintenzionati che controllano solo k-1 partecipanti, o meno, non hanno alcuna informazione e influenza sull'output, mentre qualsiasi k partecipanti possono calcolare il numero risultante, e qualsiasi sottoinsieme di k partecipanti arriverà sempre allo stesso risultato per lo stesso seed.
C'è un problema che abbiamo gentilmente eluso nel paragrafo precedente. Affinché l'interpolazione funzioni, è fondamentale che il valore Hi pubblicato da ogni partecipante i sia realmente uguale a p(i)H. Poiché nessuno, tranne il i-esimo partecipante, sa p(i), nessuno, tranne il il partecipante i--esimo partecipante, può verificare che Ciao sia effettivamente calcolato correttamente e senza una prova crittografica della correttezza Hi un avversario 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 diversi H_0 risultanti
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 presunto che ci fosse un tale polinomio p(x) di grado k-1 che il partecipante i sa p(i), e nessun altro ha alcuna informazione su questo valore. Nella prossima sezione sarà necessario che per un certo punto predefinito G tutti sappiano p(x)G per tutti x.
In questa sezione presumeremo che ogni partecipante abbia localmente una chiave privata xi, ovvero, è ben noto il corrispondente chiave pubblica Xi.
Un possibile protocollo di generazione del polinomio è il seguente:
Ogni partecipante i crea localmente un polinomio arbitrario pi(x) di grado k-1. Essi poi inviano a ciascun partecipante j valore pi(j), cifrato con la chiave pubblica Xj. In questo modo solo il partecipante i-j- e il partecipante conoscej- i(j). Il partecipante pannuncia anche pubblicamente i pi(j)G incluso. per tutti j da 1 fino a k Tutti i partecipanti utilizzano un certo consenso per scegliere
i partecipanti i cui polinomi saranno utilizzati. Poiché alcuni partecipanti potrebbero essere offline, non possiamo aspettare che tutti k i partecipanti pubblichino i polinomi. Il risultato di questo passo è un insieme n composto da almeno Z polinomi creati nel passo (1) k I partecipanti si assicurano che i valori a loro noti.
i(j) corrispondano a quelli annunciati pubblicamente ppi(j)G. Dopo questo passo devono rimanere solo i polinomi per i quali il privato trasmesso calcola la sua componente privata Z p(j) ppi(j)G. Dopo questo passo devono rimanere solo i polinomi per i quali il privato trasmesso
Ogni partecipante j come somma i(j) per tutti . Ogni partecipante calcola anche tutti i valori ppi(x)G per tutti i i in Zp(x) – p(x)G . Ogni partecipante calcola anche tutti i valori è davvero un polinomio di grado in Z.
Nota che k-1, perché è la somma di singoli i(x), ognuno dei quali è un polinomio di grado perché si tratta della somma dei singoli pi(x), ognuno dei quali è un polinomio di grado k-1. Poi, è importante notare che mentre ogni partecipante j sa p(j), non hanno alcuna informazione su p(x) per x ≠ j. Infatti, per calcolare questo valore, devono conoscere tutti pi(x), e finché un 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 è stato necessario nella sezione precedente. I passaggi 1, 2 e 4 sopra hanno un'implementazione abbastanza ovvia. Tuttavia, il passo 3 non è così banale.
In particolare, dobbiamo essere in grado di dimostrare che i cifrati pi(j) corrispondono effettivamente a quelli pubblicati. Dopo questo passo devono rimanere solo i polinomi per i quali il privato trasmesso Se non possiamo dimostrarlo, un malintenzionato i può inviare spazzatura invece di pi(j) al partecipante, je il partecipante j non sarà in grado di ottenere il vero 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 ogni partecipante, avendo un certo valore e, assieme a proofi(j) e pi(j)G, può verificare localmente che e sia realmente pi(j), cifrato con la chiave del partecipante j. Purtroppo, le dimensioni di tale prova sono incredibilmente grandi e considerando che è necessario pubblicarne O(nk) tali prove, non sarà possibile utilizzarle per questo scopo.
Invece di dimostrare che pi(j) corrisponde a pi(j)G, possiamo riservare un intervallo di tempo molto ampio nel protocollo di generazione del polinomio, durante il quale tutti i partecipanti verificano i messaggi crittografati ricevuti pi(j), e se il messaggio decrittato non corrisponde a pi(j)G, pubblicano una prova crittografica che dimostra che il messaggio crittografato ricevuto è errato. Dimostrare che il messaggio non corrisponde a pi(G) è molto più semplice che dimostrare che corrisponde. È importante notare che ciò richiede che ogni partecipante appaia in rete almeno una volta durante il tempo assegnato per creare tali prove, e si basa sull'assunzione che, se hanno pubblicato una tale prova, essa raggiungerà tutti gli altri partecipanti entro lo stesso tempo assegnato.
Se un partecipante non è apparso online durante questo periodo e ha effettivamente avuto almeno un componente errato, quel particolare partecipante non potrà partecipare a ulteriori generazioni di numeri. Tuttavia, il protocollo funzionerà ancora se ci sono almeno k partecipanti che hanno ricevuto solo componenti corrette o che sono riusciti a lasciare una prova di errore entro il tempo assegnato.
Prove di correttezza H_i
L'ultima parte da discutere è come dimostrare la correttezza di quanto pubblicato Hi, ovvero 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 è chiamata logaritmo discreto, o dlog, e vogliamo dimostrare che:
dlog(p(i)G, G) = dlog(Hi, H)
senza divulgazione p(i). Le costruzioni per tali prove esistono, ad esempio.
Con tale costruzione, ogni partecipante insieme a Ciao invia una prova di correttezza secondo la costruzione.
Quando un numero casuale è generato, spesso è necessario utilizzarlo per partecipanti diversi da quelli che lo hanno generato. A tali partecipanti, insieme al numero, devono essere inviati tutti Ciao e le prove correlate.
Il lettore curioso potrebbe chiedere: poiché il numero casuale finale è H0, e p(0)G – è informazione pubblica, perché è necessaria una prova per ciascun singolo Hi, perché non inviare invece la prova che
dlog(p(0)G, G) = dlog(H0, H)
Il problema è che con il Protocollo di Schnorr non è possibile creare tale prova, perché nessuno 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 Ciao e le loro prove individuali, per dimostrare la correttezza H0.
Tuttavia, se ci fosse qualche operazione sui punti delle curve ellittiche, semanticamente simile alla moltiplicazione, la prova di correttezza H0 sarebbe banale, ci assicureremmo semplicemente che
H0 × G = p(0)G × H
Se la curva selezionata supporta , questa prova funziona. In questo caso H0 – non è solo l'output di un generatore di numeri casuali, che può essere verificato da qualsiasi partecipante a conoscenza di G, H e p(0)G. H0 – è anche una firma sul messaggio usato come seed, che conferma che k e n i partecipanti hanno firmato questo messaggio. Pertanto, se seed – è l'hash del blocco nel protocollo blockchain, allora H0 – è sia una multi-firma sul blocco, sia un buon 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 è open source, l'implementazione è scritta in Rust e può essere trovata .
Puoi vedere come appare lo sviluppo su NEAR e sperimentare nell'IDE online .
Puoi seguire tutte le novità in russo nel e nel , mentre in inglese nel .
A presto!
Fonte: habr.com
