Ciao, Habr!
In questo articolo parlerò della generazione di numeri pseudo-casuali tra partecipanti che non si fidano l'uno dell'altro. Come vedremo di seguito, realizzare un generatore "quasi" buono è piuttosto semplice, mentre crearne uno veramente buono è difficile.
Perché è necessario generare numeri casuali tra partecipanti che non si fidano l'uno dell'altro? Un'area di applicazione è quella delle applicazioni decentralizzate. Ad esempio, un'applicazione che accetta una scommessa da un partecipante e raddoppia l'importo con una probabilità del 49%, oppure lo ritira con una probabilità del 51%, funzionerà solo se può ottenere in modo imparziale un numero casuale. Se un malintenzionato può influenzare il risultato del generatore di numeri casuali e anche solo aumentare leggermente le proprie probabilità di ricevere un pagamento nell'applicazione, può facilmente svuotarla.
Quando sviluppiamo un protocollo distribuito per la generazione di numeri casuali, vogliamo che abbia tre proprietà:
Deve essere imparziale. In altre parole, nessun partecipante deve in alcun modo influenzare il risultato del generatore di numeri casuali.
Deve essere imprevedibile. In altre parole, nessun partecipante dovrebbe essere in grado di prevedere quale numero verrà generato (o dedurre alcune delle sue proprietà) prima che venga generato.
Il protocollo deve essere robusto, cioè resistente al fatto che una certa percentuale di partecipanti si disconnetta dalla rete o tenti intenzionalmente di fermare il protocollo.
In questo articolo esamineremo due approcci: RANDAO + VDF e un approccio basato sui codici di cancellazione. Nella prossima sezione approfondiremo l'approccio basato sulle firme soggette a soglia.
Ma prima di tutto, esploriamo un algoritmo semplice e comunemente usato che è robusto, imprevedibile, ma parziale.
RANDAO
RANDAO è un approccio molto semplice e, quindi, piuttosto spesso utilizzato per ottenere casualità. Tutti i partecipanti alla rete inizialmente scelgono un numero pseudo-casuale a livello locale, poi ciascun partecipante invia l'hash del numero scelto. Successivamente, i partecipanti rivelano a turno i loro numeri scelti e applicano l'operazione XOR ai numeri rivelati, e il risultato di quest'operazione diventa il risultato del protocollo.
Il passaggio della pubblicazione degli hash prima di rivelare i numeri è necessario affinché un attaccante non possa selezionare il proprio numero dopo aver visto i numeri degli altri partecipanti. Questo gli permetterebbe di determinare unilateralmente l'output del generatore di numeri casuali.
Durante il protocollo, i partecipanti devono raggiungere un accordo due volte (il cosiddetto consenso): quando iniziare a rivelare i numeri scelti e quindi interrompere la raccolta degli hash, e quando completare la raccolta dei numeri scelti e calcolare il numero casuale risultante. Prendere tali decisioni tra partecipanti che non si fidano l'uno dell'altro è di per sé un compito complesso, e torneremo su questo in articoli futuri; in questo articolo, presumeremo che un tale algoritmo di consenso sia a nostra disposizione.
Quali delle proprietà che abbiamo descritto sopra ha RANDAO? È imprevedibile, ha la stessa vitalità del protocollo di consenso sottostante, ma è comunque di parte. In particolare, un attaccante può osservare la rete, e dopo che gli altri partecipanti hanno rivelato i loro numeri, può calcolarne l'XOR e decidere se rivelare o meno il proprio numero per influenzare il risultato. Anche se ciò non consente all'attaccante di determinare unilateralmente l'output del generatore di numeri casuali, gli fornisce comunque 1 bit di influenza. E se gli attaccanti controllano più partecipanti, il numero di bit controllati sarà pari al numero di partecipanti sotto il loro controllo.
L'influenza degli attaccanti può essere fortemente ridotta richiedendo che i partecipanti rivelino i numeri in ordine. In questo modo, l'attaccante può influenzare l'uscita solo se si rivela per ultimo. Anche se l'influenza è significativamente ridotta, l'algoritmo rimane comunque di parte.
RANDAO + VDF
Uno dei modi per rendere RANDAO imparziale è il seguente: dopo che tutti i numeri sono stati rivelati e l'XOR calcolato, il risultato viene fornito come input a 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) // è molto lento
correct = VDF_verify(input, vdf_output, vdf_proof) // è molto veloceQuesta funzione è chiamata Funzione di Ritardo Verificabile, o VDF. Se il calcolo del risultato finale richiede più tempo rispetto alla fase di rivelazione dei numeri, un malintenzionato non sarà in grado di prevedere l'effetto della dimostrazione o della sottrazione del proprio numero, perdendo così la possibilità di influenzare il risultato.
Sviluppare buone VDF è estremamente complesso. Recentemente sono stati fatti alcuni progressi, ad esempio e che hanno reso VDF più praticabili, ed Ethereum 2.0 prevede a lungo termine di utilizzare RANDAO con VDF come fonte di numeri casuali. Oltre al fatto che questo approccio è imprevedibile e imparziale, ha il vantaggio aggiuntivo della sostenibilità, a condizione che siano disponibili almeno due partecipanti nella rete (supponendo che il protocollo di consenso utilizzato sia sostenibile con un numero così ridotto di partecipanti).
La maggiore difficoltà di questo approccio è configurare il VDF in modo che anche un partecipante con attrezzature specializzate molto costose non possa calcolare il VDF prima della fine della fase di rivelazione. In modo ideale, l'algoritmo dovrebbe avere anche una significativa riserva di sicurezza, diciamo 10x. Nella figura sottostante è mostrato un attacco da parte di un partecipante con un ASIC specializzato, che gli consente di eseguire VDF più velocemente del tempo assegnato per la rivelazione della conferma RANDAO. Tale partecipante può comunque calcolare il risultato finale utilizzando e non utilizzando il proprio numero, e in seguito, sulla base dei calcoli, decidere se mostrarlo o meno.
Per la famiglia VDF menzionata sopra, le prestazioni di un ASIC specializzato possono essere superiori di oltre 100 volte rispetto a quelle delle attrezzature normali. Pertanto, se la fase di svelamento dura 10 secondi, il VDF calcolato su un ASIC di questo tipo dovrebbe richiedere più di 100 secondi per avere un margine di sicurezza di 10 volte; quindi, lo stesso VDF calcolato su attrezzature comuni dovrebbe richiedere 100 x 100 secondi = ~ 3 ore.
La Ethereum Foundation prevede di affrontare questo problema creando propri ASIC pubblici e gratuiti. Una volta fatto ciò, anche tutti gli altri protocolli potranno beneficiare di 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 disponibili molti articoli, video e altre informazioni su VDF su .
Utilizziamo codici di cancellazione
In questa sezione esamineremo il protocollo di generazione di numeri casuali che utilizza . Può tollerare fino a ⅓ degli attaccanti, rimanendo funzionante, e consente l'esistenza fino a ⅔ degli attaccanti prima che possano prevedere o influenzare il risultato.
L'idea principale del protocollo è la seguente. Per semplificare, supponiamo che ci siano esattamente 100 partecipanti. Supponiamo anche che ogni partecipante abbia localmente una chiave privata e che le chiavi pubbliche di tutti i partecipanti siano note a tutti i partecipanti:
Ogni partecipante inventa localmente una lunga stringa, la suddivide in 67 parti, crea codici erasing per ottenere 100 quote, tali che qualsiasi 67 siano sufficienti per recuperare la stringa, assegna ciascuna delle 100 quote a uno dei partecipanti e le cifra utilizzando la chiave pubblica di quel partecipante. Poi tutte le quote codificate vengono pubblicate.
I partecipanti utilizzano un certo consenso per raggiungere un accordo sui set codificati di 67 partecipanti specifici.
Una volta raggiunto il consenso, ogni partecipante prende le quote codificate in ciascuno dei 67 set, cifrate con la loro chiave pubblica, decifra tutte queste quote e pubblica tutte queste quote decifrate.
Una volta che 67 partecipanti hanno completato il passo (3), tutti i set concordati possono essere completamente decodificati e ripristinati grazie alle proprietà dei codici cancellabili, e il numero finale può essere ottenuto come XOR delle righe iniziali da cui i partecipanti hanno iniziato nel (1).
Si può dimostrare che questo protocollo è imparziale e imprevedibile. Il numero casuale risultante è definito dopo aver raggiunto il consenso, ma non è noto a nessuno fino a quando ⅔ dei partecipanti non decodificano le parti criptate con la loro chiave pubblica. Pertanto, il numero casuale è definito prima che le informazioni sufficienti per il suo ripristino vengano pubblicate.
Cosa succede se, al passo (1), uno dei partecipanti invia agli altri partecipanti delle parti codificate che non sono un codice cancellabile valido di una certa riga? Senza modifiche aggiuntive, i diversi partecipanti potrebbero non essere in grado di ripristinare affatto la riga, oppure ripristinare diverse righe, portando così a risultati diversi tra i partecipanti. Per prevenire questo, ogni partecipante, oltre alle parti codificate, calcola anche di tutte queste quote, e invia a ciascun partecipante sia la quota codificata che la radice dell'albero Merkle, insieme alla prova dell'inclusione della quota nell'albero Merkle. Nel consenso, nella fase (2), i partecipanti non si accordano semplicemente su insiemi multipli, ma su molte radici specifiche di questi alberi (se un partecipante si allontana dal protocollo e invia radici diverse dell'albero Merkle a partecipanti diversi, e due di queste radici vengono mostrate durante il consenso, la sua stringa non viene inclusa nell'insieme risultante). Alla fine del consenso avremo 67 stringhe codificate e le rispettive radici degli alberi Merkle tali che ci siano almeno 67 partecipanti (non necessariamente gli stessi che hanno proposto le stringhe corrispondenti) per cui per ognuna delle 67 stringhe ci sia un messaggio con una quota di codice cancellante e la prova dell'inclusione della loro quota nel corrispondente albero Merkle.
Quando nella fase (4) un partecipante decodifica 67 quote per una certa stringa e cerca di ricostruire la stringa originale, è possibile una delle seguenti opzioni:
La stringa viene ripristinata, e se successivamente viene codificata di nuovo con i codici di cancellazione, e si calcola l'albero Merkle per le quote calcolate localmente, la radice coincide con quella su cui è stato raggiunto il consenso.
La stringa viene ripristinata, ma la radice calcolata localmente non corrisponde a quella su cui è stato raggiunto il consenso.
La stringa non viene ripristinata.
È facile dimostrare che se almeno per un partecipante si verifica l'opzione (1), allora per tutti i partecipanti si verificherà l'opzione (1), e viceversa, se almeno per un partecipante si verifica l'opzione (2) o (3), allora per tutti i partecipanti si verificherà l'opzione (2) o (3). Pertanto, per ogni stringa nel set, o tutti i partecipanti la ripristineranno con successo, oppure tutti i partecipanti non saranno in grado di ripristinarla. Il numero casuale risultante è quindi l'XOR solo delle stringhe che i partecipanti sono riusciti a ripristinare.
Firma soglia
Un altro approccio alla casualità consiste nell'utilizzo delle cosiddette firme BLS soglia. Un generatore di numeri casuali basato su firme soglia ha esattamente le stesse garanzie dell'algoritmo descritto sopra basato su codici di cancellazione, ma presenta un'asimptotica significativamente minore del numero di messaggi trasmessi attraverso la rete per ogni numero generato.
Le firme BLS sono una struttura che consente a più partecipanti di creare un'unica firma comune per un messaggio. Tali firme vengono spesso utilizzate per risparmiare spazio e larghezza di banda poiché non richiedono l'invio di più firme.
Un uso comune delle firme BLS nei protocolli blockchain, oltre alla generazione di numeri casuali, è la firma dei blocchi nei protocolli BFT. Immaginiamo che 100 partecipanti creino blocchi e che un blocco venga considerato finale se 67 di essi lo firmano. Tutti possono presentare le loro parti della firma BLS e utilizzare un certo algoritmo di consenso per concordare 67 di esse e poi combinarle in una singola firma BLS. Qualsiasi combinazione di 67 (o più) parti può essere utilizzata per creare la firma finale, che dipenderà da quali specifiche 67 firme siano state unite, e quindi può variare. Tuttavia, sebbene la scelta di 67 partecipanti diversi generi firme diverse, ogni firma sarà corretta per il blocco. Gli altri partecipanti devono quindi solo ricevere e verificare una singola firma per ogni blocco, invece di 67, riducendo notevolmente il carico sulla rete.
Si scopre che se le chiavi private utilizzate dai partecipanti vengono generate in un certo modo, allora indipendentemente da quali 67 firme (o più, ma non meno di 67) vengano aggregate, la firma risultante sarà la stessa. Questo può essere utilizzato come fonte di casualità: i partecipanti prima convengono su un certo messaggio che firmeranno (può essere l'output di RANDAO o semplicemente l'hash dell'ultimo blocco, in realtà non importa, purché cambi ogni volta e sia concordato), e creano una firma BLS per esso. Il risultato della generazione sarà imprevedibile, fino a quando 67 partecipanti non forniranno le loro parti, dopo di che i dati in uscita saranno già predeterminati e non possono dipendere dalle azioni di alcun partecipante.
Questo approccio alla casualità è sostenibile se almeno il ⅔ dei partecipanti è online e segue il protocollo, ed è imparziale e imprevedibile finché almeno ⅓ dei partecipanti segue il protocollo. È importante notare che un attaccante che controlla più del ⅓ ma meno del ⅔ dei partecipanti può fermare il protocollo, ma non può prevedere o influenzare il suo output.
Le firme soglia sono di per sé un argomento molto interessante. Nella seconda parte dell'articolo esamineremo in dettaglio come funzionano e come generare le chiavi dei partecipanti affinché le firme soglia possano essere utilizzate come generatore di numeri casuali.
In conclusione
Questo articolo è il primo di una serie di articoli tecnici sul blog . NEAR è un protocollo blockchain e una piattaforma per sviluppare 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
