Introduzione
«La generazione di numeri casuali è troppo importante per lasciarla al caso»
Robert Cavyu, 1970
Questo articolo è dedicato all'applicazione pratica delle soluzioni che utilizzano la generazione collettiva di numeri casuali in ambienti non fidati. In breve, come e perché viene utilizzato il random nei blockchain, e un po' su come distinguere un “buon” random da un “cattivo”. Generare un numero veramente casuale è un problema estremamente complesso anche su un singolo computer, ed è da tempo studiato dai crittografi. Nelle reti decentralizzate, la generazione di numeri casuali è ancora più complicata e importante.
Proprio nelle reti in cui i partecipanti non si fidano l'uno dell'altro, la possibilità di generare un numero casuale innegabile consente di affrontare in modo efficace molte delle questioni più importanti e migliorare significativamente gli schemi già esistenti. Inoltre, il gioco d'azzardo e le lotterie non sono affatto l'obiettivo principale, come potrebbe sembrare a un lettore inesperto.
Generazione di numeri casuali
I computer non possono generare numeri casuali da soli: hanno bisogno di un aiuto esterno. Un computer può ottenere un certo valore casuale utilizzando, ad esempio, i movimenti del mouse, la quantità di memoria utilizzata, i tassi parasitari sui contatti del processore e molte altre fonti, denominate fonti di entropia. Questi valori non sono del tutto casuali, poiché si trovano in un intervallo specifico o presentano un carattere di cambiamento prevedibile. Per trasformare questi numeri in numeri realmente casuali in un determinato intervallo, si applicano criptotrasformazioni, per ottenere valori pseudo-casuali uniformemente distribuiti da valori di entropia non uniformemente distribuiti. I valori ottenuti vengono chiamati pseudo-casuali, poiché non sono veramente casuali, ma sono stati deterministicamente generati dall'entropia. Qualsiasi buon algoritmo crittografico, crittografando i dati, produce testi cifrati che statisticamente non dovrebbero essere distinguibili da una sequenza casuale, quindi per generare casualità si può utilizzare una fonte di entropia che garantisca solo una buona ripetibilità e imprevedibilità dei valori anche in intervalli ridotti, mentre il resto del lavoro di diffusione e mescolamento dei bit nel valore risultante sarà svolto dall'algoritmo di crittografia.
Per concludere questo breve chiarimento, aggiungo che la generazione di numeri casuali, anche su un solo dispositivo, è uno dei pilastri della sicurezza dei nostri dati. I numeri pseudo-casuali generati vengono utilizzati per stabilire connessioni protette in diverse reti, per generare chiavi crittografiche, per bilanciare il carico, per il controllo dell'integrità e per molte altre applicazioni. La sicurezza di molti protocolli dipende dalla possibilità di generare un casuale affidabile e imprevedibile da fonti esterne, conservarlo e non rivelarlo fino al passo successivo del protocollo, altrimenti la sicurezza sarà compromessa. Un attacco al generatore di valori pseudo-casuali è estremamente pericoloso e mette a rischio tutto il software che utilizza la generazione di casualità.
Tutto ciò dovreste saperlo se avete seguito un corso base di crittografia, pertanto continuiamo a parlare di reti decentralizzate.
Random nei blockchain
In primo luogo parlerò dei blockchain con supporto per smart contract, poiché sono in grado di sfruttare appieno le potenzialità offerte da un random di alta qualità e innegabile. In seguito, per brevità, chiamerò questa tecnologia “Publicly Verifiable Random Beacons” o PVRB. Poiché i blockchain sono reti le cui informazioni possono essere verificate da qualsiasi partecipante, una parte chiave del nome è “Publicly Verifiable”, cioè chiunque può, attraverso calcoli, ottenere la prova che il numero ricevuto, registrato nel blockchain, possiede queste caratteristiche:
- Il risultato deve avere una distribuzione dimostrabilmente uniforme, cioè basata su crittografia dimostrabilmente sicura.
- Non è possibile controllare alcun bit del risultato. Di conseguenza, il risultato non può essere previsto in anticipo.
- Non è possibile sabotare il protocollo di generazione mediante l'astensione dal protocollo o sovraccaricando la rete con messaggi malevoli.
- Tutto quanto sopra deve essere resistente a cospirazioni di un numero consentito di partecipanti disonesti al protocollo (ad esempio 1/3 dei partecipanti).
Qualsiasi possibilità per un gruppo di partecipanti cospiratori di generare anche un random pari/dispari controllato rappresenta una falla nella sicurezza. Qualsiasi possibilità per un gruppo di fermare l'erogazione del random è una falla nella sicurezza. In generale, ci sono molti problemi e questo compito non è affatto facile…
Sembra che l'applicazione più importante per i PVRB sia nei vari giochi, lotterie e, in generale, in qualsiasi forma di gioco su blockchain. In effetti, questa è una direzione importante, ma il random nei blockchain ha applicazioni più significative. Esaminiamole.
Algoritmi di consenso
Il PVRB ha un'importanza enorme per l'organizzazione del consenso di rete. Le transazioni nelle blockchain sono protette da una firma elettronica, quindi un'"attacco alla transazione" consiste sempre nell'inclusione/esclusione di una transazione in un blocco (o in più blocchi). Il compito principale dell'algoritmo di consenso è convenire sull'ordine di queste transazioni e sull'ordine dei blocchi che le includono. Inoltre, una proprietà necessaria per le reali blockchain è la finalità: la possibilità che la rete concordi che la catena fino al blocco finalizzato sia definitiva e non verrà mai esclusa a causa della comparsa di un nuovo fork. Di solito, per convenire che un blocco sia valido e, cosa più importante, finale, è necessario raccogliere le firme dalla maggior parte dei produttori di blocchi (BP - block producers), il che richiede almeno di inviare la catena di blocchi a tutti i BP e di distribuire le firme tra tutti i BP. Con l'aumento del numero di BP, il numero di messaggi necessari nella rete cresce esponenzialmente; pertanto, gli algoritmi di consenso che richiedono la finalità, come quelli utilizzati nel consenso pBFT di Hyperledger, non funzionano con la velocità necessaria, già a partire da alcune decine di BP, richiedendo un enorme numero di connessioni.
Se nella rete esiste un PVRB indiscutibile e onesto, è possibile, anche nella sua forma più semplice, selezionare uno dei block producers come "leader" per un round del protocollo. Se abbiamo N block producer, da cui M: M > 1/2 N sono onesti, non censurano le transazioni e non costruiscono fork della catena per attuare un attacco di "double spend", l'uso di un PVRB indiscutibile uniformemente distribuito permetterà di scegliere un leader onesto con una probabilità di M / N (M / N > 1/2). Se a ciascun leader viene assegnato un proprio intervallo di tempo durante il quale può creare un blocco e validare la catena, e questi intervalli sono uguali tra loro, allora la catena di blocchi dei BP onesti sarà più lunga della catena formata dai BP malevoli, e l'algoritmo di consenso basato sulla lunghezza della catena scarterà semplicemente quella “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 a molti blocchi di essere chiusi con una sola firma, riducendo significativamente il carico di rete e permettendo a questo consenso di operare in modo estremamente veloce e stabile. Tuttavia, le reti EOS devono attualmente utilizzare blocchi speciali (Last Irreversible Block), che vengono confermati da firme di 2/3 dei BP. Questi blocchi servono a garantire la finalità (l'impossibilità di un fork della catena che inizi prima dell'ultimo Last Irreversible Block).
Inoltre, nelle implementazioni reali, lo schema del protocollo è più complesso: le votazioni sui blocchi proposti avvengono su più fasi, per mantenere attiva la rete in caso di blocchi saltati e problemi di rete, ma anche considerando questo, gli algoritmi di consenso che utilizzano PVRB richiedono sostanzialmente meno messaggi tra i BP, rendendoli più veloci rispetto al tradizionale PВFT o a varie sue modifiche.
Il più rappresentativo di tali algoritmi è: del team di Cardano, che, come dichiarato, possiede una resistenza matematicamente dimostrabile a situazioni di collusione tra i BP.
In Ouroboros, il PVRB viene utilizzato per definire il cosiddetto “BP schedule” — un programma secondo cui a ciascun BP viene assegnato il proprio slot temporale per la pubblicazione del blocco. Un grande vantaggio dell'uso del PVRB è la completa “uguaglianza” dei BP (in base alle dimensioni dei loro saldi). L'onestà del PVRB garantisce che i BP malevoli non possano controllare il programma degli slot temporali e, quindi, non possano manipolare la catena, preparando e analizzando in anticipo i fork della catena, e per scegliere un fork basta affidarsi semplicemente alla lunghezza della catena, senza dover fare calcoli complessi sulla “utilità” dei BP e sul “peso” dei loro blocchi.
In tutti i casi in cui è necessario scegliere un partecipante casuale in una rete decentralizzata, quasi sempre la scelta migliore sarà PVRB, piuttosto che un'opzione deterministica basata, ad esempio, sull'hash di un blocco. Senza PVRB, la possibilità di influenzare la scelta del partecipante porta all'insorgere di attacchi in cui l'attaccante può, scegliendo tra diverse opzioni future, selezionare il partecipante corrotto successivo o addirittura più di uno, per garantire una porzione maggiore nel processo decisionale. L'utilizzo del PVRB discredita questi tipi di attacchi.
Scalabilità e bilanciamento del carico
Il PVRB può portare seri vantaggi anche per ridurre il carico e scalare i pagamenti. Innanzitutto, è utile prendere confidenza con Rivista “Biglietti della Lotteria Elettronica come Micropagamenti”. L'idea principale è che, invece di effettuare 100 pagamenti da 1 centesimo dal pagante al destinatario, si può partecipare a una lotteria equa con un premio di 1$ = 100 centesimi, dove il pagante, a ogni pagamento da 1 centesimo, trasferisce alla banca uno dei 100 “biglietti della lotteria”. Uno di questi biglietti vincerà alla banca 1$, e proprio questo biglietto potrà essere registrato nel blockchain dal destinatario. La cosa più importante è che gli altri 99 biglietti vengono trasferiti tra il destinatario e il pagante senza alcun intervento esterno, su un canale privato e a qualsiasi velocità necessaria. Una buona descrizione del protocollo basato su questo schema nella rete Emercoin può essere letta .
Questa soluzione presenta alcuni problemi, ad esempio il destinatario potrebbe smettere di servire il pagante subito dopo aver ricevuto il biglietto vincente, ma per molte applicazioni specifiche, come la tariffazione al minuto o gli abbonamenti elettronici ai servizi, questi possono essere trascurati. La principale esigenza, ovviamente, è l'onestà della lotteria condotta, e per la sua attuazione è assolutamente necessario il PVRB.
La selezione casuale di un partecipante è estremamente importante anche per i protocolli di sharding, il cui obiettivo è la scalabilità orizzontale della catena di blocchi, consentendo ai diversi BP di elaborare solo il proprio ambito di transazioni. Questa è un compito molto complesso, soprattutto in termini di sicurezza durante la fusione dei shard. Una corretta selezione casuale del BP per nominare i suoi responsabili per uno specifico shard, come nelle algoritmi di consenso, è anch'essa una sfida del PVRB. Nei sistemi centralizzati, gli shard sono assegnati da un bilanciatore, che calcola semplicemente un hash della richiesta e lo invia all'esecutore necessario. Nelle blockchain, la possibilità di influenzare questa assegnazione può portare a un attacco sul consenso. Ad esempio, il contenuto delle transazioni può essere controllato da un attaccante, che può gestire quali transazioni finiscono nel proprio shard controllato e manipolare la catena di blocchi al suo interno. Si può leggere la discussione sulla questione dell'uso dei numeri casuali per compiti di sharding in Ethereum.
Lo sharding è uno dei compiti più ambiziosi e seri nel campo del blockchain; la sua risoluzione permetterà di costruire reti decentralizzate di straordinaria prestazione e volume. Il PVRB è solo uno dei blocchi importanti per risolverlo.
Giochi, protocolli economici, arbitraggio
Il ruolo dei numeri casuali nell'industria dei giochi è difficile da sovrastimare. L'uso esplicito nei casinò online e l'uso implicito nel calcolo degli effetti delle azioni del giocatore rappresentano tutte questioni estremamente complesse per le reti decentralizzate, dove non è possibile fare affidamento su una fonte centrale di casualità. Tuttavia, la selezione casuale può anche risolvere molti problemi economici e contribuire alla costruzione di protocolli più semplici ed efficienti. Supponiamo che nel nostro protocollo ci siano controversie riguardo al pagamento di servizi a basso costo, e queste controversie si verificano piuttosto raramente. In questo caso, se c'è un PVRB indiscutibile, clienti e venditori possono accordarsi per una risoluzione casuale delle controversie, ma con una probabilità prestabilita. Ad esempio, con una probabilità del 60% vince il cliente, mentre con una probabilità del 40% vince il venditore. Questo approccio, che potrebbe sembrare assurdo a prima vista, consente di risolvere automaticamente le controversie con una percentuale di vincite/perdite esattamente prevedibile, soddisfacente per entrambe le parti senza il coinvolgimento di una terza parte e senza spreco di tempo. Inoltre, il rapporto delle probabilità può essere dinamico e dipendere da alcune variabili globali. Ad esempio, se l'azienda sta andando bene, si riscontra un basso numero di controversie e un'elevata redditività, l'azienda può automaticamente spostare la probabilità di risoluzione della controversia verso una maggiore orientamento al cliente, ad esempio 70/30 o 80/20, e viceversa, se le controversie comportano grandi spese e sono fraudolente o inadeguate, si può spostare la probabilità in direzione opposta.
Un gran numero di protocolli decentralizzati interessanti, come i registri curati dai token, i mercati predittivi, le curve di legame e molti altri, rappresentano giochi economici in cui viene premiato il buon comportamento e penalizzato il cattivo. Spesso emergono problemi di sicurezza, le cui soluzioni possono risultare in conflitto tra loro. Ciò che è protetto da un attacco di "whale" con miliardi di token ("big stake"), è vulnerabile ad attacchi da migliaia di account con piccoli saldi ("sybil stake"), e le misure contro un tipo di attacco, come le commissioni non lineari create per rendere svantaggioso il lavoro di un grande stake, vengono solitamente discreditate da un altro attacco. Poiché si tratta di un gioco economico, i pesi statistici appropriati possono essere calcolati in anticipo e le commissioni possono essere semplicemente sostituite con commissioni randomizzate secondo una distribuzione appropriata. Tali commissioni probabilistiche sono realizzate in modo estremamente semplice, se nel blockchain esiste una fonte affidabile di casualità e non richiedono calcoli complessi, complicando la vita sia ai whale sia agli attaccanti sybil.
È necessario continuare a ricordare che il controllo su un singolo bit in questa casualità consente di ingannare, raddoppiando e dimezzando le probabilità, quindi un PVRB onesto è una componente fondamentale di tali protocolli.
Dove trovare la casualità giusta?
In teoria, una selezione casuale onesta nelle reti decentralizzate consente di garantire la sicurezza dimostrabile di quasi qualsiasi protocollo contro la collusione. La logica è piuttosto semplice: se la rete concorda su un singolo bit 0 o 1, e tra i partecipanti meno della metà sono disonesti, allora, con un numero sufficiente di iterazioni, la rete garantirà di arrivare a un consenso su questo bit con una probabilità fissa. Questo perché un randome onesto selezionerà 51 su 100 partecipanti nel 51% dei casi. Ma questo è solo in teoria, poiché nelle reti reali, per garantire un livello di sicurezza come in articoli, è necessario scambiare molti messaggi tra gli host, criptografia complessa e multilivello, e qualsiasi complicazione del protocollo introduce immediatamente nuovi vettori di attacco.
È proprio per questo che non vediamo ancora in blockchain un PVRB dimostrabilmente resistente, che sia stato utilizzato a lungo abbastanza da superare le prove delle applicazioni reali, molteplici audit, carichi e, naturalmente, veri attacchi, senza i quali è difficile definire un prodotto realmente sicuro.
Tuttavia, ci sono diversi approcci promettenti, che si differenziano per molti dettagli, e uno di essi sicuramente risolverà il problema. Con le attuali risorse di calcolo, la teoria crittografica può essere trasformata in applicazioni pratiche abbastanza agilmente. In futuro, saremo lieti di parlare delle implementazioni di PVRB: ce ne sono attualmente diverse, ognuna con il proprio insieme di proprietà e caratteristiche importanti, e dietro ognuna c'è una buona idea. Non ci sono molte squadre che si occupano di randomizzazione, e l'esperienza di ciascuna di esse è estremamente importante per tutte le altre. Speriamo che le nostre informazioni possano aiutare le altre squadre a muoversi più rapidamente, tenendo conto delle esperienze dei predecessori.
Fonte: habr.com
