Ciao, Habr!
In questo articolo parlerò della generazione di numeri pseudo-casuali tra partecipanti che non si fidano l'uno dell'altro. Come vedremo più avanti, implementare un generatore “quasi” buono è abbastanza semplice, mentre realizzarne uno molto buono è complicato.
Perché è necessario generare numeri casuali per i partecipanti che non si fidano l'uno dell'altro? Uno dei campi di applicazione è nelle applicazioni decentralizzate. Ad esempio, un'app che accetta una scommessa da un partecipante e raddoppia l'importo con una probabilità del 49%, oppure lo prende con una probabilità del 51%, funzionerà solo se può ottenere un numero casuale in modo imparziale. Se un malintenzionato può influenzare il risultato del generatore di numeri casuali, anche solo marginalmente aumentare le proprie possibilità di ricevere un pagamento nell'app, 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 influenzare in alcun modo il risultato del generatore di numeri casuali.
Deve essere imprevedibile. In altre parole, nessun partecipante deve essere in grado di prevedere quale numero verrà generato (o di dedurre alcune delle sue proprietà) prima che venga generato.
Il protocollo deve essere sostenibile, cioè resistente al fatto che una certa percentuale di partecipanti si disconnetta dalla rete o tenti deliberatamente di fermare il protocollo.
In questo articolo esamineremo due approcci: RANDAO + VDF e un approccio basato su codici di cancellazione. Nella parte successiva analizzeremo in dettaglio l'approccio basato su firme soggettive.
Ma prima di tutto, analizziamo un algoritmo semplice e spesso utilizzato, che è sostenibile, imprevedibile, ma parziale.
RANDAO
RANDAO è un approccio molto semplice e quindi abbastanza spesso utilizzato per ottenere casualità. Tutti i partecipanti della rete prima scelgono localmente un numero pseudo casuale, poi ogni partecipante invia l'hash del numero scelto. Successivamente, i partecipanti rivelano a turno i loro numeri scelti e applicano l'operazione XOR sui numeri rivelati, e il risultato di questa operazione diventa il risultato dell'operazione del protocollo.
Il passo di pubblicare gli hash prima di rivelare i numeri è essenziale, affinché un malintenzionato non possa scegliere il proprio numero dopo aver visto i numeri degli altri partecipanti. Questo gli consentirebbe di determinare effettivamente da solo l'output del generatore di numeri casuali.
Durante il protocollo, i partecipanti devono raggiungere due volte un accordo comune (il cosiddetto consenso): quando iniziare a rivelare i numeri scelti e quindi smettere di accettare gli hash, e quando terminare di accettare i numeri scelti e calcolare il risultato finale. Raggiungere tali decisioni tra partecipanti che non si fidano l'uno dell'altro è già di per sé un compito difficile, e torneremo su questo in articoli futuri; in questo articolo daremo per scontato che tale algoritmo di consenso ci sia accessibile.
Quali delle proprietà che abbiamo descritto sopra ha RANDAO? È imprevedibile, ha la stessa capacità di sopravvivenza del protocollo di consenso sottostante, ma è sbilanciato. In particolare, un malintenzionato può osservare la rete, e dopo che gli altri partecipanti rivelano i loro numeri, può calcolare il loro XOR e decidere se rivelare o meno il proprio numero per influenzare il risultato. Anche se questo non consente al malintenzionato di determinare da solo l'output del generatore di numeri casuali, gli fornisce comunque 1 bit di influenza. E se i malintenzionati controllano più partecipanti, il numero di bit che controllano sarà uguale al numero di partecipanti sotto il loro controllo.
L'influenza dei malintenzionati può essere significativamente ridotta se si richiede che i partecipanti rivelino i numeri in ordine. In tal caso, il malintenzionato potrà influenzare l'esito solo se si rivela per ultimo. Anche se l'influenza è significativamente ridotta, l'algoritmo rimane comunque sbilanciato.
RANDAO + VDF
Una delle opzioni per rendere RANDAO imparziale è la seguente: dopo che tutti i numeri sono stati rivelati e l'XOR calcolato, il suo risultato viene passato come input a una funzione che richiede molto tempo per essere calcolata, ma consente di verificare la correttezza del calcolo in modo molto rapido.
(vdf_output, vdf_proof) = VDF_compute(input) // questo è molto lento
correct = VDF_verify(input, vdf_output, vdf_proof) // questo è molto veloceQuesta funzione si chiama Verifiable Delay Function, o VDF. Se il calcolo del risultato finale richiede più tempo rispetto alla fase di rivelazione dei numeri, allora un malintenzionato non sarà in grado di prevedere l'effetto della sua dimostrazione o della sua reticenza nel rivelare il numero, e quindi perderà la possibilità di influenzare il risultato.
Sviluppare buoni VDF è estremamente complesso. Recentemente sono stati fatti alcuni progressi, ad esempio e che ha reso i VDF più applicabili nella pratica, e Ethereum 2.0 prevede di utilizzare RANDAO con VDF come fonte di numeri casuali a lungo termine. Oltre al fatto che questo approccio è imprevedibile e imparziale, ha il vantaggio aggiuntivo di essere sostenibile, se almeno due partecipanti sono disponibili in rete (a condizione che il protocollo di consenso utilizzato sia sostenibile con un numero così ridotto di partecipanti).
La maggiore difficoltà di questo approccio è impostare i VDF in modo tale che anche un partecipante con attrezzature specializzate molto costose non possa calcolare i VDF prima della fase di rivelazione. Idealmente, l'algoritmo dovrebbe avere anche un margine di sicurezza significativo, diciamo 10x. Nella figura sottostante è mostrato un attacco di un partecipante che dispone di un ASIC specializzato, il quale gli consente di eseguire il VDF più rapidamente del tempo assegnato per la rivelazione della conferma RANDAO. Tale partecipante potrebbe comunque calcolare il risultato finale utilizzando o meno il proprio numero, e poi, in base ai calcoli, decidere se mostrarlo o meno.
Per la famiglia di VDF sopra menzionata, le prestazioni di un ASIC specializzato possono essere superiori a 100 volte rispetto a quelle di un'attrezzatura normale. Pertanto, se la fase di rivelazione dura 10 secondi, il VDF calcolato su un tale ASIC dovrebbe richiedere più di 100 secondi per avere un margine di sicurezza di 10 volte, e così lo stesso VDF, calcolato su attrezzature normali, dovrebbe richiedere 100 x 100 secondi = ~ 3 ore.
La Ethereum Foundation intende affrontare questo problema creando i propri ASIC pubblici e gratuiti. Una volta che ciò avverrà, tutti gli altri protocolli potranno anch'essi avvantaggiarsi 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.
Molti articoli, video e altre informazioni su VDF sono stati raccolti su .
Utilizziamo codici di cancellazione
In questa sezione esamineremo il protocollo di generazione di numeri casuali che utilizza . Può sopportare fino a ⅓ di attaccanti rimanendo praticabile e consente l'esistenza fino a ⅔ di 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 inoltre che tutti i partecipanti abbiano localmente una certa chiave privata e che le chiavi pubbliche di tutti i partecipanti siano conosciute da tutti i partecipanti:
Ogni partecipante genera localmente una stringa lunga, la suddivide in 67 parti, crea codici di cancellazione per ottenere 100 quote, tali che qualsiasi 67 siano sufficienti per ricostruire la stringa, assegna ciascuna delle 100 quote a uno dei partecipanti e le crittografa con la chiave pubblica dello stesso partecipante. Dopodiché, 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, crittografate con la loro chiave pubblica, decifra tutte queste quote e pubblica tutte queste quote decifrate.
Una volta che 67 partecipanti hanno completato il passaggio (3), tutti i set concordati possono essere completamente decodificati e ripristinati grazie alle proprietà dei codici di cancellazione, e il numero finale può essere ottenuto come XOR delle stringhe iniziali da cui i partecipanti sono partiti nel (1).
Si può dimostrare che questo protocollo è imparziale e imprevedibile. Il numero casuale risultante è definito dopo aver raggiunto il consenso, ma nessuno lo conosce fino a quando ⅔ dei partecipanti non decodificano le parti criptate con la loro chiave pubblica. In questo modo, il numero casuale è determinato prima che le informazioni necessarie per il suo recupero siano pubblicate.
Cosa succede se nel passaggio (1) uno dei partecipanti invia ad altri partecipanti delle parti codificate che non sono un codice di cancellazione corretto per una certa stringa? Senza ulteriori modifiche, i diversi partecipanti non saranno in grado di recuperare la stringa affatto, oppure recupereranno stringhe diverse, il che farà sì che partecipanti diversi ricevano un numero casuale diverso. Per prevenire ciò, si può fare quanto segue: ogni partecipante, oltre alle parti codificate, calcola anche di tutte queste parti, e invia a ogni partecipante sia la parte codificata stessa, sia la radice dell'albero di Merkle e la prova dell'inclusione della parte nell'albero di Merkle. Nel consenso al passaggio (2), quindi, i partecipanti non si accordano solo su un insieme di set, ma su un insieme di radici specifiche di tali alberi (se un certo partecipante si discosta dal protocollo e invia radici diverse dell'albero di Merkle a partecipanti diversi, e due di tali radici vengono presentate durante il consenso, la sua stringa non viene inclusa nell'insieme risultante). Alla fine del consenso, avremo 67 stringhe codificate e le corrispondenti radici dell'albero di Merkle tali che ci siano almeno 67 partecipanti (non necessariamente gli stessi che hanno proposto le stringhe corrispondenti), per le quali per ciascuna delle 67 stringhe c'è un messaggio con una parte del codice di cancellazione e una prova dell'inclusione della loro parte nell'albero di Merkle corrispondente.
Quando al passaggio (4) un partecipante decodifica 67 parti per una certa stringa e cerca di recuperare la stringa originale, una delle seguenti opzioni è possibile:
La stringa viene recuperata e se viene poi codificata di nuovo con i codici di cancellazione e si calcola l'albero di Merkle per le parti calcolate localmente, la radice coincide con quella su cui è stato raggiunto il consenso.
La stringa viene recuperata, ma la radice calcolata localmente non corrisponde a quella su cui è stato raggiunto il consenso.
La stringa non viene recuperata.
È facile dimostrare che se almeno per un partecipante si verifica il caso (1), allora per tutti i partecipanti si verificherà il caso (1), e viceversa, se almeno per un partecipante si verifica il caso (2) o (3), allora per tutti i partecipanti si verificherà il caso (2) o (3). Pertanto, per ogni riga nel set, o tutti i partecipanti la ripristineranno con successo, oppure tutti i partecipanti non saranno in grado di ripristinarla. Il numero casuale risultante sarà quindi l'XOR solo delle righe che i partecipanti sono riusciti a ripristinare.
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 di soglia ha esattamente le stesse garanzie dell'algoritmo basato su codici di cancellazione descritto sopra, ma ha un'assintotica significativamente minore nel numero di messaggi trasmessi in rete per ogni numero generato.
Le firme BLS sono una costruzione che consente a più partecipanti di creare una singola firma comune per un messaggio. Queste firme sono spesso utilizzate per risparmiare spazio e larghezza di banda in quanto non richiedono l'invio di più firme.
Un'applicazione comune delle firme BLS nei protocolli blockchain, oltre alla generazione di numeri casuali, è la firma di blocchi nei protocolli BFT. Supponiamo che 100 partecipanti creino blocchi e un blocco venga considerato definitivo se 67 di essi lo firmano. Tutti possono presentare le proprie parti della firma BLS e utilizzare un certo algoritmo di consenso per concordare 67 di esse, per poi unirle in una singola firma BLS. Qualsiasi 67 (o più) parti possono essere utilizzate per creare la firma finale, che dipenderà da quali 67 firme sono state unite, e quindi potrebbe variare, ma nonostante ciò, una selezione diversa di 67 partecipanti creerà una firma diversa, qualsiasi di queste firme sarà comunque una firma valida per il blocco. Gli altri partecipanti dovranno quindi ricevere tramite rete e verificare solo una firma per ogni blocco, invece di 67, il che riduce notevolmente il carico sulla rete.
Si scopre che se le chiavi private utilizzate dai partecipanti sono generate in un certo modo, allora, indipendentemente dalle 67 firme (o più, ma mai meno) aggregate, la firma risultante sarà la stessa. Questo può essere utilizzato come sorgente di casualità: i partecipanti prima concordano su un messaggio da firmare (questo può essere l'output di RANDAO o semplicemente l'hash dell'ultimo blocco, in realtà non importa, purché cambi ogni volta ed sia concordato), e creano una firma BLS per esso. Il risultato della generazione sarà imprevedibile fino a quando 67 partecipanti non forniscono le loro parti, e dopo di ciò, i dati in uscita sono già predeterminati e non possono dipendere dalle azioni di alcun partecipante.
Questo approccio alla casualità è fattibile se almeno ⅔ dei partecipanti sono online e seguono il protocollo, ed è imparziale e imprevedibile finché almeno ⅓ dei partecipanti seguono il protocollo. È importante notare che un malintenzionato che controlla più di ⅓ ma meno di ⅔ dei partecipanti può fermare il protocollo, ma non può prevedere o influenzare la sua uscita.
Le firme soglia sono di per sé un tema molto interessante. Nella seconda parte dell'articolo esamineremo dettagliatamente come funzionano e come devono essere generate 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 nel blog . NEAR è un protocollo blockchain e una piattaforma per lo sviluppo di applicazioni decentralizzate con un'enfasi sulla facilità di sviluppo e sulla facilità d'uso 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
