Introduzione
«La generazione di numeri casuali è troppo importante per essere lasciata al caso»
Robert Kavey, 1970
Questo articolo è dedicato all'applicazione pratica di soluzioni che utilizzano la generazione collettiva di numeri casuali in un ambiente non fidato. In breve — come e per cosa viene utilizzato il random nelle blockchain, e un po' su come distinguere un “buon” random da un “cattivo”. La generazione di numeri realmente casuali è un problema estremamente complesso anche su un singolo computer ed è da tempo studiata dai crittografi. Nelle reti decentralizzate, la generazione di numeri casuali è ancora più complessa e importante.
Proprio nelle reti in cui i partecipanti non si fidano l'uno dell'altro, la possibilità di generare un numero casuale inconfutabile consente di affrontare efficacemente molte questioni cruciali e migliorare significativamente gli schemi esistenti. Inoltre, il gioco d'azzardo e le lotterie non sono affatto l'obiettivo principale, come potrebbe sembrare a prima vista a un lettore inesperto.
Generazione di numeri casuali
I computer non sono in grado di generare numeri casuali autonomamente; hanno bisogno di un aiuto esterno. Un computer può ottenere un valore casuale utilizzando, ad esempio, il movimento del mouse, la quantità di memoria utilizzata, i segnali di disturbo nei contatti del processore e molte altre fonti, chiamate fonti di entropia. Questi valori non sono del tutto casuali, poiché rientrano in un certo intervallo o presentano un carattere di cambiamento prevedibile. Per trasformare tali numeri in un vero numero casuale in un intervallo specificato, si applicano trasformazioni crittografiche, per ottenere valori pseudocasuali uniformemente distribuiti da valori di entropia non uniformemente distribuiti. I valori ottenuti sono chiamati pseudocasuali, poiché non sono veramente casuali, ma sono stati prodotti deterministicamente dall'entropia. Qualsiasi buon algoritmo crittografico, cifrando i dati, produce testi cifrati che statisticamente dovrebbero essere indistinguibili da una sequenza casuale; pertanto, per generare casualità si può utilizzare una fonte di entropia che fornisca solo una buona imprevedibilità e unicità dei valori, anche in piccoli intervalli, mentre l'algoritmo di cifratura si occuperà del resto per disperdere e mescolare i bit nel valore risultante.
Per concludere questo breve approfondimento, aggiungo che la generazione di numeri casuali anche su un singolo dispositivo è uno dei pilastri della sicurezza dei nostri dati. I numeri pseudo-casuali generati vengono utilizzati per stabilire connessioni sicure in diverse reti, per la generazione di chiavi crittografiche, per il bilanciamento del carico, il controllo dell'integrità e per molte altre applicazioni. La sicurezza di molti protocolli dipende dalla capacità di generare un random affidabile e imprevedibile dall'esterno, di conservarlo e di non rivelarlo fino al passaggio successivo del protocollo; altrimenti, la sicurezza sarà compromessa. Un attacco al generatore di valori pseudo-casuali è estremamente pericoloso e mette in pericolo tutto il software che utilizza la generazione di random.
Tutto questo dovete sapere se avete seguito un corso base di crittografia, quindi continuiamo a parlare delle reti decentralizzate.
Random nei blockchain
Prima di tutto, parlerò delle blockchain che supportano i contratti smart, poiché sono queste che possono sfruttare appieno le possibilità fornite da un random di alta qualità e inconfutabile. In seguito, per brevità, chiamerò questa tecnologia “Publicly Verifiable Random Beacons” o PVRB. Poiché le blockchain sono reti in cui qualsiasi partecipante può verificare le informazioni, una parte chiave del nome è “Publicly Verifiable”, ossia chiunque può ottenere una prova, tramite calcoli, che il numero ottenuto e registrato nella blockchain possiede le seguenti proprietà:
- Il risultato deve avere una distribuzione dimostrabilmente uniforme, basata su crittografia dimostrabilmente robusta.
- Nessuno dei bit del risultato può essere controllato. Di conseguenza, il risultato non può essere previsto in anticipo.
- Non è possibile sabotare il protocollo di generazione non partecipando al protocollo o sovraccaricando la rete con messaggi malevoli.
- Tutto quanto sopra deve essere resistente a collusioni di un numero accettabile di partecipanti disonesti al protocollo (ad esempio, 1/3 dei partecipanti).
Qualsiasi possibilità di un gruppo minoritario complice di generare anche un random controllato pari/dispari rappresenta una falla nella sicurezza. Qualsiasi possibilità per il gruppo di interrompere l'emissione del random è una falla nella sicurezza. In generale, ci sono molti problemi, e questo compito non è semplice...
Sembra che l'applicazione più importante per PVRB sia nei vari giochi, lotterie e, in generale, in qualsiasi forma di gioco d'azzardo sulla blockchain. In effetti, questa è una direzione importante, ma ci sono applicazioni più significative per il random nelle blockchain. Analizziamole.
Algoritmi di consenso
PVRB per l'organizzazione del consenso di rete è di enorme importanza. Le transazioni nelle blockchain sono protette da una firma elettronica, quindi un 'attacco alla transazione' è sempre l'inclusione/esclusione di una transazione in un blocco (o in più blocchi). La principale responsabilità dell'algoritmo di consenso è concordare l'ordine di queste transazioni e dell'ordine dei blocchi che le includono. Inoltre, una caratteristica necessaria per le blockchain reali è la finalità: la capacità della rete di concordare che la catena fino al blocco finalizzato è definitiva e non sarà mai esclusa a causa dell'emergere di un nuovo fork. Di norma, per concordare che un blocco è valido e, cosa fondamentale, finale, è necessario raccogliere le firme dalla maggior parte dei produttori di blocchi (di seguito BP - block-producers), il che richiede almeno di inviare la catena di blocchi a tutti i BP e di diffondere le firme tra tutti i BP. Con l'aumento del numero di BP, il numero di messaggi necessari nella rete cresce esponenzialmente, quindi gli algoritmi di consenso che richiedono la finalità, utilizzati ad esempio nel consenso pBFT di Hyperledger, non funzionano con la velocità richiesta, già a partire da alcune decine di BP, richiedendo un enorme numero di connessioni.
Se c'è un PVRB incontrovertibile e onesto nella rete, allora, anche nella sua forma più semplice, si può selezionare uno dei produttori di blocchi e nominarlo "leader" per un round del protocollo. Se abbiamo N produttori di blocchi, da cui M: M > 1/2 N sono onesti, non censurano le transazioni e non creano fork della catena per attuare un attacco di "double spend", allora l'uso di un PVRB incontrovertibile uniformemente distribuito consentirà di scegliere un leader onesto con una probabilità di M / N (M / N > 1/2). Se a ciascun leader venisse assegnato un intervallo di tempo specifico durante il quale può creare un blocco e validare la catena, e questi intervalli fossero uguali in termini di tempo, la catena di blocchi degli onesti BP sarebbe più lunga rispetto a quella formata dai BP malevoli, e l'algoritmo di consenso che si basa sulla lunghezza della catena scarterebbe semplicemente la "cattiva". Questo principio di assegnare intervalli di tempo uguali a ciascun BP è stato applicato per la prima volta in Graphene (il predecessore di EOS) e consente di chiudere la maggior parte dei blocchi con una sola firma, il che riduce notevolmente il carico sulla rete e permette a questo consenso di funzionare in modo estremamente veloce e stabile. Tuttavia, le reti EOS ora devono utilizzare blocchi speciali (Last Irreversible Block), che vengono confermati con le firme di 2/3 BP. Questi blocchi servono per garantire la finalità (l'impossibilità di una fork della catena che inizi prima dell'ultimo Last Irreversible Block).
In real implementations, the protocol scheme is more complex — voting for proposed blocks takes place in several stages to maintain network operations in case of block omissions and network issues, but even taking this into account, consensus algorithms using PVRB require significantly fewer messages between BPs, allowing them to be faster than traditional PВFT or its various modifications.
The most prominent representative of such algorithms is: from the Cardano team, which has been declared to have mathematically proven resilience against collusion among BPs.
In Ouroboros, PVRB is used to determine the so-called "BP schedule" — a timetable wherein each BP is assigned its own time slot for block publication. A significant advantage of using PVRB is the complete "equality" of BPs (according to the size of their balances). The fairness of PVRB ensures that malicious BPs cannot control the timing of the slots, and therefore cannot manipulate the chain by pre-preparing and analyzing chain forks; instead, they can rely solely on the length of the chain to select a fork, without resorting to clever methods of calculating the "utility" of BPs and the "weight" of their blocks.
In generale, in tutti i casi in cui è necessario selezionare un partecipante casuale in una rete decentralizzata, la scelta migliore sarà quasi sempre PVRB, piuttosto che un'opzione deterministica basata, ad esempio, sull'hash del blocco. Senza PVRB, la possibilità di influenzare la selezione del partecipante porta a attacchi in cui l'attaccante può, scegliendo tra diverse opzioni future, selezionare il prossimo partecipante corrotto o addirittura più di uno, per garantire una quota maggiore nel processo decisionale. L'uso di PVRB scredita questi tipi di attacchi.
Scalabilità e bilanciamento del carico
PVRB può portare seri vantaggi anche in compiti per ridurre il carico, scalare i pagamenti. Per iniziare, ha senso familiarizzare con Rivista “Electronic Lottery Tickets as Micropayments”. Il concetto principale è che, anziché effettuare 100 pagamenti da 1 centesimo dal pagatore al beneficiario, si può giocare a una lotteria equa con un premio di 1$ = 100 centesimi, dove il pagatore, ad ogni pagamento di 1 centesimo, trasferisce alla banca uno dei 100 suoi “biglietti della lotteria”. Uno di questi biglietti vince per la banca 1$, e proprio questo biglietto il beneficiario può registrare nella blockchain. La cosa più importante è che gli altri 99 biglietti vengono trasferiti tra il beneficiario e il pagatore senza alcuna partecipazione esterna, attraverso un canale privato e con la velocità necessaria. Una buona descrizione del protocollo basato su questo schema nella rete Emercoin può essere letta. .
Questo schema presenta alcune problematiche; per esempio, il beneficiario può smettere di servire il pagatore subito dopo aver ricevuto il biglietto vincente, ma per molte applicazioni specifiche, come la tariffazione al minuto o gli abbonamenti elettronici ai servizi, si può sorvolare su di esse. Il requisito principale, ovviamente, è l'onestà della lotteria condotta, e per la sua realizzazione è necessario un PVRB.
La selezione casuale dei nodi è estremamente importante anche per i protocolli di sharding, il cui obiettivo è la scalabilità orizzontale della blockchain, consentendo a diversi BP di elaborare solo il proprio ambito di transazioni. Si tratta di un compito molto complesso, soprattutto in termini di sicurezza nella fusione dei shard. Una selezione equa del BP casuale per la responsabilità di un determinato shard, come nei protocolli di consenso, è anch'essa una questione PVRB. Nei sistemi centralizzati, gli shard sono assegnati da un bilanciatore, il quale calcola semplicemente un hash della richiesta e lo invia all'esecutore designato. Nelle blockchain, la possibilità di influenzare questa assegnazione può portare a un attacco al consenso. Ad esempio, il contenuto delle transazioni può essere controllato da un attaccante, il quale può decidere quali transazioni entrare nello shard da lui controllato e manipolare la blockchain al suo interno. È possibile leggere discussioni sui problemi dell'utilizzo di numeri casuali per i compiti di sharding su Ethereum.
Lo sharding è una delle sfide più ambiziose e serie nel campo della blockchain; la sua soluzione permetterà di costruire reti decentralizzate con prestazioni e capacità straordinarie. PVRB è solo uno dei blocchi fondamentali per la sua risoluzione.
Giochi, protocolli economici, arbitraggio
Il ruolo dei numeri casuali nell'industria del gioco è difficile da sottovalutare. Il loro utilizzo esplicito nei casinò online e implicito nel calcolo degli effetti di determinate azioni dei giocatori presenta sfide complesse per le reti decentralizzate, dove non si può fare affidamento su una fonte centrale di casualità. Tuttavia, la selezione casuale può risolvere molti problemi economici e contribuire a costruire protocolli più semplici ed efficienti. Supponiamo che nel nostro protocollo ci siano dispute riguardo il pagamento di servizi a basso costo, e che tali dispute si verifichino abbastanza raramente. In questo caso, se è presente un PVRB indiscutibile, clienti e fornitori possono concordare una risoluzione casuale delle dispute, con una probabilità stabilita. Per esempio, con una probabilità del 60%, vince il cliente e con una probabilità del 40%, vince il fornitore. Questo approccio, apparentemente assurdo, consente di risolvere automaticamente le dispute con una quota di vincite/perdite previsibile, soddisfacendo entrambe le parti senza il coinvolgimento di un terzo e senza perdite di tempo. Inoltre, il rapporto di probabilità può essere dinamico e dipendere da alcune variabili globali. Se, ad esempio, l'azienda sta andando bene, si osservano pochi contenziosi e un'alta redditività, essa può automaticamente spostare la probabilità di risoluzione delle dispute verso il cliente, ad esempio 70/30 o 80/20, e viceversa, se i contenziosi causano molte perdite e risultano fraudolenti o inadeguati, si può spostare la probabilità nell'altra direzione.
Un gran numero di interessanti protocolli decentralizzati, come i token curated registries, i mercati delle previsioni, le curve di bonding e molti altri, rappresentano giochi economici in cui viene premiato il buon comportamento e penalizzato quello cattivo. In essi si riscontrano spesso problematiche di sicurezza, la cui protezione è controproducente. Ciò che è protetto da attacchi di "whale" con miliardi di token è vulnerabile ad attacchi provenienti da migliaia di account con piccoli saldi. Le misure adottate contro un tipo di attacco, come le commissioni non lineari create per rendere svantaggioso il grande staking, vengono solitamente annientate da un altro attacco. Poiché si tratta di un gioco economico, i pesi statistici pertinenti possono essere calcolati in anticipo e le commissioni possono essere semplicemente sostituite con commissioni randomizzate secondo la distribuzione adeguata. Tali commissioni probabilistiche sono estremamente facili da implementare, a condizione che ci sia una fonte affidabile di casualità nella blockchain, e non richiedono calcoli complessi, complicando la vita sia ai whale che agli attaccanti sybil.
È importante continuare a tenere a mente che il controllo su un singolo bit in questo random consente di ingannare, raddoppiando e dimezzando le probabilità, quindi un PVRB onesto è una componente fondamentale di tali protocolli.
Dove trovare il giusto random?
In teoria, una selezione casuale onesta nelle reti decentralizzate consente di garantire la sicurezza dimostrabile di quasi qualsiasi protocollo contro il collusione. La giustificazione è piuttosto semplice: se la rete concorda su un bit 0 o 1, e tra i partecipanti meno della metà è disonesta, allora, con un numero sufficiente di iterazioni, la rete arriverà sicuramente a un consenso su quel bit con una probabilità fissa. Questo perché il random onesto sceglierà 51 dei 100 partecipanti nel 51% dei casi. Ma questo è in teoria, poiché nelle reti reali, per garantire tale livello di sicurezza, come nelle articolazioni, è necessario un numero elevato di messaggi tra host, una crittografia complessa e qualsiasi complicazione del protocollo introduce immediatamente nuovi vettori di attacco.
Ecco perché non vediamo ancora nei blockchain PVRB comprovati e resistenti, che siano stati utilizzati per abbastanza tempo da superare le prove delle applicazioni reali, molteplici audit, carichi e, naturalmente, attacchi reali, senza i quali è difficile definire un prodotto davvero sicuro.
Tuttavia, ci sono diversi approcci promettenti, che differiscono per molti dettagli, e sicuramente uno di essi risolverà il problema. Con le attuali risorse computazionali, la teoria crittografica è in grado di trasformarsi abilmente in applicazioni pratiche. In futuro, saremo lieti di parlare delle implementazioni di PVRB: ce ne sono attualmente alcune, ognuna con il proprio insieme di importanti proprietà e caratteristiche nella realizzazione, e ciascuna sostenuta da una buona idea. Non molte squadre si occupano di randomizzazione, e l'esperienza di ognuna di esse è estremamente importante per tutte le altre. Speriamo che le nostre informazioni possano consentire ad altre squadre di progredire più rapidamente, tenendo conto dell'esperienza dei predecessori.
Fonte: habr.com
