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

Ehi Habr!

In questo articolo parlerò della generazione di numeri pseudo-casuali da parte di partecipanti che non si fidano l'uno dell'altro. Come vedremo in seguito, implementare un generatore “quasi” buono è abbastanza semplice, ma realizzarne uno molto buono è difficile.

Perché sarebbe necessario generare numeri casuali tra i partecipanti che non si fidano l'uno dell'altro? Un'area di applicazione sono le applicazioni decentralizzate. Ad esempio, un'applicazione che accetta una scommessa da un partecipante e raddoppia l'importo con una probabilità del 49% o la toglie con una probabilità del 51%, funzionerà solo se può ricevere in modo imparziale un numero casuale. Se un utente malintenzionato riesce a influenzare il risultato del generatore di numeri casuali e ad aumentare anche leggermente le sue possibilità di ricevere un pagamento nell'applicazione, lo devasterà facilmente.

Quando progettiamo un protocollo di generazione di numeri casuali distribuiti, vogliamo che abbia tre proprietà:

1. Deve essere imparziale. In altre parole, nessun partecipante dovrebbe in alcun modo influenzare il risultato del generatore di numeri casuali.

2. Deve essere imprevedibile. In altre parole, nessun partecipante dovrebbe essere in grado di prevedere quale numero verrà generato (o dedurre una qualsiasi delle sue proprietà) prima che venga generato.

3. Il protocollo deve essere vitale, cioè resistente al fatto che una certa percentuale di partecipanti si disconnetta dalla rete o tenti deliberatamente di interrompere il protocollo.

In questo articolo esamineremo due approcci: RANDAO + VDF e l'approccio dei codici di cancellazione. Nella parte successiva esamineremo in dettaglio l’approccio basato sulle firme a soglia.

Ma prima, diamo un'occhiata a un algoritmo semplice e comunemente usato che è praticabile, imprevedibile, ma parziale.

RANDAO

RANDAO è un approccio molto semplice e quindi abbastanza comunemente usato per generare casualità. Tutti i partecipanti alla rete selezionano prima localmente un numero pseudocasuale, quindi ciascun partecipante invia un hash del numero selezionato. Successivamente, i partecipanti, a turno, rivelano i numeri scelti ed eseguono un'operazione XOR sui numeri rivelati, e il risultato di questa operazione diventa il risultato del protocollo.

La fase di pubblicazione degli hash prima di rivelare i numeri è necessaria affinché l'attaccante non possa scegliere il proprio numero dopo aver visto i numeri degli altri partecipanti. Ciò gli consentirebbe di determinare praticamente da solo l'output del generatore di numeri casuali.

Nel corso del protocollo, i partecipanti devono giungere a una decisione comune (il cosiddetto consenso) due volte: quando iniziare a rivelare i numeri selezionati, e quindi smettere di accettare gli hash, e quando smettere di accettare i numeri selezionati e calcolare il risultato casuale numero. Prendere tali decisioni tra partecipanti che non si fidano l'uno dell'altro non è un compito facile di per sé, e ritorneremo su questo argomento nei prossimi articoli; in questo articolo assumeremo che un tale algoritmo di consenso sia a nostra disposizione.

Quali delle proprietà che abbiamo descritto sopra possiede RANDAO? È imprevedibile, ha la stessa vitalità del protocollo di consenso sottostante, ma è parziale. Nello specifico, un utente malintenzionato può osservare la rete e, dopo che gli altri partecipanti hanno rivelato i propri numeri, può calcolare il proprio XOR e decidere se rivelare o meno il proprio numero per influenzare il risultato. Sebbene ciò impedisca all'attaccante di determinare da solo l'output del generatore di numeri casuali, gli dà comunque 1 bit di influenza. E se gli aggressori controllano più partecipanti, il numero di bit che controllano sarà uguale al numero di partecipanti sotto il loro controllo.

L'influenza degli aggressori può essere notevolmente ridotta richiedendo ai partecipanti di rivelare i numeri in ordine. Quindi l'attaccante potrà influenzare l'esito solo se verrà aperto per ultimo. Anche se l’influenza è significativamente minore, l’algoritmo è ancora parziale.

RANDAO+VDF

Un modo per rendere RANDAO imparziale è questo: dopo che tutti i numeri sono stati rivelati e lo XOR è stato calcolato, il suo risultato viene inserito nell'input di una funzione, che richiede molto tempo per essere calcolata, ma consente di verificare la correttezza del calcolo molto rapidamente.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Questa funzione è chiamata Funzione di ritardo verificabile o VDF. Se il calcolo del risultato finale richiede più tempo della fase di divulgazione del numero, l'attaccante non sarà in grado di prevedere l'effetto di mostrare o nascondere il suo numero e quindi perderà l'opportunità di influenzare il risultato.

Sviluppare buoni VDF è estremamente difficile. Recentemente ci sono state diverse scoperte, ad es. questo и questo che ha reso VDF più pratico nella pratica, ed Ethereum 2.0 prevede di utilizzare RANDAO con VDF come fonte di numeri casuali a lungo termine. A parte il fatto che questo approccio è imprevedibile e imparziale, ha l’ulteriore vantaggio di essere fattibile se sulla rete sono disponibili almeno due partecipanti (assumendo che il protocollo di consenso utilizzato sia fattibile quando si ha a che fare con un numero così piccolo di partecipanti).

La sfida più grande di questo approccio è impostare il VDF in modo tale che anche un partecipante con hardware specializzato molto costoso non sarà in grado di calcolare il VDF prima della fine della fase di scoperta. Idealmente, l’algoritmo dovrebbe avere anche un margine di sicurezza significativo, diciamo 10x. La figura seguente mostra un attacco da parte di un attore che dispone di un ASIC specializzato che gli consente di eseguire un VDF più velocemente del tempo assegnato per rivelare la conferma RANDAO. Tale partecipante potrà comunque calcolare il risultato finale utilizzando o meno il proprio numero, e poi, in base al calcolo, scegliere se mostrarlo o meno.

Per la famiglia VDF menzionata sopra, le prestazioni di un ASIC dedicato possono essere oltre 100 volte superiori rispetto all'hardware convenzionale. Pertanto, se la fase di divulgazione dura 10 secondi, il VDF calcolato su tale ASIC deve impiegare più di 100 secondi per avere un margine di sicurezza 10x, e quindi lo stesso VDF calcolato sull'hardware di base deve impiegare 100x 100 secondi = ~3 ore.

La Fondazione Ethereum intende risolvere questo problema creando i propri ASIC gratuiti e disponibili al pubblico. Una volta che ciò accadrà, anche tutti gli altri protocolli potranno trarre vantaggio da questa tecnologia, ma fino ad allora l’approccio RANDAO+VDF non sarà altrettanto praticabile per i protocolli che non possono investire nello sviluppo dei propri ASIC.

Sono stati raccolti molti articoli, video e altre informazioni su VDF questo sito.

Utilizziamo codici di cancellazione

In questa sezione esamineremo un protocollo di generazione di numeri casuali che utilizza cancellazione dei codici. Può tollerare fino a ⅓ aggressori pur rimanendo vitale e consente a un massimo di ⅔ aggressori di esistere prima che possano prevedere o influenzare il risultato.

L'idea principale del protocollo è la seguente. Per semplicità, supponiamo che ci siano esattamente 100 partecipanti. Supponiamo anche che tutti i partecipanti abbiano localmente una chiave privata e che le chiavi pubbliche di tutti i partecipanti siano note a tutti i partecipanti:

1. Ogni partecipante si presenta localmente con una lunga stringa, la spezza in 67 parti, crea codici di cancellazione per ottenere 100 condivisioni in modo tale che 67 qualsiasi siano sufficienti per recuperare la stringa, assegna ciascuna delle 100 condivisioni a uno dei partecipanti e le crittografa con la chiave pubblica dello stesso partecipante. Tutte le condivisioni codificate vengono quindi pubblicate.

2. I partecipanti utilizzano una sorta di consenso per raggiungere un accordo sui set codificati di specifici 67 partecipanti.

3. Una volta raggiunto il consenso, ciascun partecipante prende le condivisioni codificate in ciascuno dei 67 set crittografati con la propria chiave pubblica, decrittografa tutte le condivisioni e pubblica tutte le condivisioni decrittografate.

4. Una volta che 67 partecipanti hanno completato il passaggio (3), tutti i set concordati possono essere completamente decodificati e ricostruiti grazie alle proprietà dei codici di cancellazione e il numero finale può essere ottenuto come XOR delle righe iniziali con cui i partecipanti hanno iniziato in (1) .

È possibile dimostrare che questo protocollo è imparziale e imprevedibile. Il numero casuale risultante viene determinato dopo il raggiungimento del consenso, ma non è noto a nessuno finché ⅔ dei partecipanti non decodificano le parti crittografate con la propria chiave pubblica. Pertanto, il numero casuale viene determinato prima che vengano pubblicate informazioni sufficienti per ricostruirlo.

Cosa succede se nel passaggio (1) uno dei partecipanti ha inviato agli altri partecipanti condivisioni codificate che non rappresentano il codice di cancellazione corretto per qualche stringa? Senza ulteriori modifiche, partecipanti diversi non saranno in grado di recuperare affatto la stringa oppure recupereranno stringhe diverse, il che si tradurrà in partecipanti diversi che riceveranno un numero casuale diverso. Per evitare ciò, puoi fare quanto segue: ogni partecipante, oltre alle azioni codificate, calcola anche Albero di Merkla tutte queste condivisioni e invia a ciascun partecipante sia la condivisione codificata stessa che la radice del merkle tree, nonché la prova dell'inclusione della condivisione nel merkle tree. Nel consenso della fase (2), i partecipanti non si accordano solo su un insieme di insiemi, ma su un insieme di radici specifiche di tali alberi (se qualche partecipante ha deviato dal protocollo e ha inviato diverse radici di alberi merkle a partecipanti diversi, e due di queste radici vengono mostrate durante il consenso, la sua riga non è inclusa nel set di risultati). Come risultato del consenso, avremo 67 linee codificate e le corrispondenti radici dell'albero merkle tali che ci siano almeno 67 partecipanti (non necessariamente gli stessi che hanno proposto le linee corrispondenti), che per ciascuna delle 67 linee hanno un messaggio con una quota del codice di cancellazione e una prova del verificarsi della loro quota nell'albero corrispondente sbiadito.

Quando nel passaggio (4) il partecipante decifra 67 battute per una certa corda e cerca di ricostruire la corda originale da essi, è possibile una delle opzioni:

1. La stringa viene ripristinata e, se viene poi nuovamente codificata per la cancellazione, e viene calcolato l'albero Merkle per le quote calcolate localmente, la radice coincide con quella su cui è stato raggiunto il consenso.

2. La riga viene ripristinata, ma la radice calcolata localmente non corrisponde a quella in cui è stato raggiunto il consenso.

3. La riga non viene ripristinata.

È facile dimostrare che se l'opzione (1) si è verificata per almeno uno dei partecipanti sopra, allora l'opzione (1) si è verificata per tutti i partecipanti e viceversa, se l'opzione (2) o (3) si è verificata per almeno un partecipante, allora per tutti i partecipanti si verificherà l'opzione (2) o (3). Pertanto, per ogni riga del set, tutti i partecipanti la recupereranno con successo oppure tutti i partecipanti non riusciranno a recuperarla. Il numero casuale risultante è quindi uno XOR delle sole righe che i partecipanti sono riusciti a recuperare.

Firme di soglia

Un altro approccio alla casualità consiste nell'utilizzare le cosiddette firme di soglia BLS. Un generatore di numeri casuali basato su firme a soglia ha esattamente le stesse garanzie dell'algoritmo basato su codici di cancellazione descritto sopra, ma ha un numero asintotico significativamente inferiore di messaggi inviati in rete per ciascun numero generato.

Le firme BLS sono un design che consente a più partecipanti di creare una firma comune per un messaggio. Queste firme vengono spesso utilizzate per risparmiare spazio e larghezza di banda non richiedendo l'invio di più firme. 

Un’applicazione comune per le firme BLS nei protocolli blockchain, oltre alla generazione di numeri casuali, è la firma a blocchi nei protocolli BFT. Diciamo che 100 partecipanti creano blocchi e un blocco è considerato definitivo se 67 di loro lo firmano. Tutti possono inviare le proprie parti della firma BLS e utilizzare un algoritmo di consenso per concordarne 67 e quindi unirle in un'unica firma BLS. Qualsiasi 67 (o più) parti possono essere utilizzate per creare la firma finale, che dipenderà da quali 67 firme sono state combinate e quindi può variare, sebbene scelte diverse da parte dei 67 partecipanti creeranno una firma diversa, qualsiasi firma di questo tipo sarà valida firma per il blocco. I restanti partecipanti devono quindi ricevere e verificare solo una firma per blocco, invece di 67, sulla rete, il che riduce notevolmente il carico sulla rete.

Si scopre che se le chiavi private utilizzate dai partecipanti vengono generate in un certo modo, indipendentemente da quali 67 firme (o più, ma non meno) vengono aggregate, la firma risultante sarà la stessa. Questo può essere usato come fonte di casualità: i partecipanti prima si accordano su un messaggio che firmeranno (questo potrebbe essere l'output di RANDAO o semplicemente l'hash dell'ultimo blocco, non importa purché cambi ogni volta ed è coerente) e creare una firma BLS per esso. Il risultato della generazione sarà imprevedibile finché 67 partecipanti non forniranno le loro parti, dopodiché il risultato è già predeterminato e non può dipendere dalle azioni di alcun partecipante.

Questo approccio alla casualità è praticabile fintanto che almeno ⅔ dei partecipanti online seguono entrambi il protocollo, ed è imparziale e imprevedibile fintanto che almeno ⅓ dei partecipanti segue il protocollo. È importante notare che un utente malintenzionato che controlla più di ⅓ ma meno di ⅔ dei partecipanti può interrompere il protocollo, ma non può prevederne o influenzarne l’output.

Le firme delle soglie stesse sono un argomento molto interessante. Nella seconda parte dell'articolo analizzeremo in dettaglio come funzionano e come esattamente sia necessario generare le chiavi partecipanti affinché le firme di soglia possano essere utilizzate come generatore di numeri casuali.

insomma

Questo articolo è il primo di una serie di articoli 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