Introduzione
“La generazione di numeri casuali è troppo importante per essere lasciata al caso.”
Robert Cavue, 1970
Questo articolo è dedicato all'applicazione pratica di soluzioni che utilizzano la generazione collettiva di numeri casuali in un ambiente non affidabile. In breve, come e perché il casuale viene utilizzato nelle blockchain, e qualcosa su come distinguere il casuale “buono” da quello “cattivo”. Generare un numero veramente casuale è un problema estremamente difficile, anche su un singolo computer, ed è stato a lungo studiato dai crittografi. Ebbene, nelle reti decentralizzate, la generazione di numeri casuali è ancora più complessa e importante.
È nelle reti in cui i partecipanti non si fidano l'uno dell'altro che la capacità di generare un numero casuale indiscutibile consente di risolvere efficacemente molti problemi critici e di migliorare significativamente gli schemi esistenti. Inoltre, il gioco d'azzardo e le lotterie non sono l'obiettivo numero uno qui, come potrebbe sembrare a prima vista al lettore inesperto.
Generazione di numeri casuali
I computer non possono generare numeri casuali da soli; hanno bisogno di un aiuto esterno per farlo. Il computer può ottenere alcuni valori casuali, ad esempio, dai movimenti del mouse, dalla quantità di memoria utilizzata, dalle correnti vaganti sui pin del processore e da molte altre fonti chiamate fonti di entropia. Questi valori stessi non sono del tutto casuali, poiché rientrano in un certo intervallo o presentano uno schema di cambiamento prevedibile. Per trasformare tali numeri in un numero veramente casuale all'interno di un determinato intervallo, vengono applicate loro criptotrasformazioni per produrre valori pseudo-casuali distribuiti uniformemente dai valori distribuiti in modo non uniforme della fonte di entropia. I valori risultanti sono detti pseudocasuali perché non sono veramente casuali, ma derivano deterministicamente dall’entropia. Qualsiasi buon algoritmo crittografico, quando crittografa i dati, produce testi cifrati che dovrebbero essere statisticamente indistinguibili da una sequenza casuale, quindi per produrre casualità si può prendere una fonte di entropia, che fornisce solo una buona ripetibilità e imprevedibilità dei valori anche in piccoli intervalli, il il resto del lavoro consiste nel disperdere e mescolare i bit. Il valore risultante verrà rilevato dall'algoritmo di crittografia.
Per completare un breve programma didattico, aggiungo che generare numeri casuali anche su un dispositivo è uno dei pilastri per garantire la sicurezza dei nostri dati. I numeri pseudo-casuali generati vengono utilizzati quando si stabiliscono connessioni sicure in varie reti, per generare chiavi crittografiche, per il bilanciamento del carico, il monitoraggio dell'integrità e per molte altre applicazioni. La sicurezza di molti protocolli dipende dalla capacità di generare un dato casuale affidabile e imprevedibile dall'esterno, di memorizzarlo e di non rivelarlo fino al passaggio successivo del protocollo, altrimenti la sicurezza sarà compromessa. Un attacco a un generatore di valori pseudocasuali è estremamente pericoloso e minaccia immediatamente tutto il software che utilizza la generazione casuale.
Dovresti sapere tutto questo se hai seguito un corso base di crittografia, quindi continuiamo con le reti decentralizzate.
Casualità nelle blockchain
Innanzitutto parlerò delle blockchain con supporto per gli smart contract; sono quelle che possono sfruttare appieno le opportunità offerte da una casualità innegabile e di alta qualità. Inoltre, per brevità, chiamerò questa tecnologia “Beacon casuali verificabili pubblicamente" o PVRB. Poiché le blockchain sono reti in cui le informazioni possono essere verificate da qualsiasi partecipante, la parte fondamentale del nome è “Pubblicamente verificabile”, ovvero Chiunque può utilizzare i calcoli per ottenere la prova che il numero risultante pubblicato sulla blockchain ha le seguenti proprietà:
- Il risultato deve avere una distribuzione uniforme e dimostrabile, cioè essere basato su una crittografia forte e dimostrabile.
- Non è possibile controllare nessuno dei bit del risultato. 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 di attacco
- Tutto quanto sopra deve essere resistente alla collusione di un numero consentito di partecipanti al protocollo disonesti (ad esempio, 1/3 dei partecipanti).
Qualsiasi possibilità che un gruppo minore di partecipanti colluda produca anche solo un numero pari/dispari controllato è una falla di sicurezza. Qualsiasi capacità del gruppo di fermare l'emissione di dati casuali è una falla di sicurezza. In generale, ci sono molti problemi e questo compito non è facile...
Sembra che l'applicazione più importante per PVRB siano vari giochi, lotterie e in generale qualsiasi tipo di gioco d'azzardo sulla blockchain. In effetti, questa è una direzione importante, ma la casualità nelle blockchain ha applicazioni ancora più importanti. Diamo un'occhiata a loro.
Algoritmi di consenso
Il PVRB svolge un ruolo enorme nell'organizzazione del consenso della rete. Le transazioni in blockchain sono protette da una firma elettronica, quindi un “attacco a una transazione” è sempre l’inclusione/esclusione di una transazione in un blocco (o più blocchi). E il compito principale dell’algoritmo di consenso è concordare l’ordine di queste transazioni e l’ordine dei blocchi che le includono. Inoltre, una proprietà necessaria per le blockchain reali è la definitività: la capacità della rete di concordare che la catena fino al blocco finalizzato è definitiva e non sarà mai esclusa a causa della comparsa di un nuovo fork. Di solito, per concordare che un blocco sia valido e, soprattutto, definitivo, è necessario raccogliere le firme della maggior parte dei produttori di blocchi (di seguito denominati BP - produttori di blocchi), il che richiede almeno la consegna della catena di blocchi a tutte le BP e distribuendo le firme tra tutte le BP. Man mano che il numero di BP cresce, il numero di messaggi necessari nella rete cresce in modo esponenziale, pertanto, gli algoritmi di consenso che richiedono finalità, utilizzati ad esempio nel consenso Hyperledger pBFT, non funzionano alla velocità richiesta, a partire da diverse decine di BP, richiedendo un numero enorme di connessioni.
Se nella rete esiste un PVRB innegabile e onesto, allora, anche nell'approssimazione più semplice, si può scegliere uno dei produttori di blocchi in base ad esso e nominarlo "leader" durante un round del protocollo. Se abbiamo N produttori di blocchi, di cui M: M > 1/2 N sono onesti, non censurano le transazioni e non biforcano la catena per effettuare un attacco di “doppia spesa”, quindi l’utilizzo di un PVRB incontrastato distribuito uniformemente consentirà di scegliere con probabilità un leader onesto M / N (M / N > 1/2). Se a ciascun leader viene assegnato il proprio intervallo di tempo durante il quale può produrre un blocco e convalidare la catena, e questi intervalli sono uguali nel tempo, allora la catena di blocchi dei BP onesti sarà più lunga della catena formata dai BP dannosi, e il consenso L'algoritmo si basa sulla lunghezza della catena e scarterà semplicemente quello "cattivo". Questo principio di allocazione di porzioni 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 singola firma, riducendo notevolmente il carico di rete e consentendo a questo consenso di funzionare in modo estremamente rapido e costantemente. Tuttavia, la rete EOS ora deve utilizzare blocchi speciali (Last Irreversible Block), che sono confermati dalle firme di 2/3 BP. Questi blocchi servono a garantire la definitività (l'impossibilità di una biforcazione della catena che inizi prima dell'ultimo Ultimo Blocco Irreversibile).
Inoltre, nelle implementazioni reali, lo schema del protocollo è più complicato: la votazione per i blocchi proposti viene effettuata in più fasi per mantenere la rete in caso di blocchi mancanti e problemi con la rete, ma anche tenendo conto di ciò, gli algoritmi di consenso che utilizzano PVRB richiedono un numero significativamente inferiore di messaggi tra i BP, il che rende possibile renderli più veloci del tradizionale PVFT o delle sue varie modifiche.
Il rappresentante più importante di tali algoritmi: dal team Cardano, che si dice sia matematicamente dimostrabile contro la collusione della BP.
In Ouroboros, PVRB viene utilizzato per definire il cosiddetto "programma BP", un programma in base al quale a ciascun BP viene assegnato il proprio intervallo di tempo per la pubblicazione di un blocco. Il grande vantaggio dell’utilizzo del PVRB è la completa “uguaglianza” dei BP (in base alla dimensione dei loro bilanci). L'integrità del PVRB garantisce che i BP dannosi non possano controllare la programmazione delle fasce orarie, e quindi non possano manipolare la catena preparando e analizzando in anticipo i fork della catena, e per selezionare un fork è sufficiente fare semplicemente affidamento sulla lunghezza del catena, senza utilizzare metodi complicati per calcolare l’“utilità” di BP e il “peso” dei suoi blocchi.
In generale, in tutti i casi in cui è necessario scegliere un partecipante casuale in una rete decentralizzata, il PVRB è quasi sempre la scelta migliore, piuttosto che un’opzione deterministica basata, ad esempio, su un hash del blocco. Senza PVRB, la capacità di influenzare la scelta di un partecipante porta ad attacchi in cui l'aggressore può scegliere tra più futuri per scegliere il successivo partecipante corrotto o più partecipanti contemporaneamente per assicurarsi una maggiore partecipazione alla decisione. L'uso del PVRB scredita questo tipo di attacchi.
Scalabilità e bilanciamento del carico
Il PVRB può anche essere di grande vantaggio in attività quali la riduzione del carico e il ridimensionamento dei pagamenti. Per cominciare, ha senso familiarizzare con Rivesta “Biglietti della lotteria elettronica come micropagamenti”. L’idea generale è che invece di effettuare 100 pagamenti da 1 centesimo dal pagatore al destinatario, si può giocare ad una lotteria onesta con un premio di 1$ = 100 centesimi, dove il pagatore dà alla banca uno dei 1 dei suoi “biglietti della lotteria” per ciascuno. pagamento 100c. Uno di questi biglietti vince un barattolo da $ 1, ed è questo biglietto che il destinatario può registrare nella blockchain. La cosa più importante è che i restanti 99 biglietti vengano trasferiti tra il destinatario e il pagatore senza alcuna partecipazione esterna, attraverso un canale privato e a qualsiasi velocità desiderata. Si può leggere una buona descrizione del protocollo basato su questo schema sulla rete Emercoin .
Questo schema presenta alcuni problemi, ad esempio il destinatario potrebbe interrompere il servizio al pagatore immediatamente dopo aver ricevuto un biglietto vincente, ma per molte applicazioni speciali, come la fatturazione al minuto o gli abbonamenti elettronici ai servizi, questi possono essere trascurati. Il requisito principale, ovviamente, è l'equità della lotteria e per la sua attuazione è assolutamente necessario un PVRB.
La scelta di un partecipante casuale è estremamente importante anche per i protocolli di sharding, il cui scopo è scalare orizzontalmente la catena di blocchi, consentendo a diversi BP di elaborare solo il proprio ambito di transazioni. Questo è un compito estremamente difficile, soprattutto in termini di sicurezza quando si uniscono i frammenti. Anche la selezione equa di un BP casuale allo scopo di assegnare i responsabili di uno specifico frammento, come negli algoritmi di consenso, è compito del PVRB. Nei sistemi centralizzati, gli shard vengono assegnati da un bilanciatore; calcola semplicemente l'hash dalla richiesta e lo invia all'esecutore richiesto. Nelle blockchain, la capacità di influenzare questa assegnazione può portare ad un attacco al consenso. Ad esempio, il contenuto delle transazioni può essere controllato da un utente malintenzionato, può controllare quali transazioni vanno allo shard che controlla e manipolare la catena di blocchi al suo interno. Puoi leggere una discussione sul problema dell'uso di numeri casuali per le attività di sharding in Ethereum
Lo sharding è uno dei problemi più ambiziosi e seri nel campo della blockchain; la sua soluzione consentirà di costruire reti decentralizzate con prestazioni e volume fantastici. Il PVRB è solo uno degli ostacoli importanti per risolverlo.
Giochi, protocolli economici, arbitrati
È difficile sopravvalutare il ruolo dei numeri casuali nel settore dei giochi. L’uso esplicito nei casinò online e l’uso implicito nel calcolo degli effetti dell’azione di un giocatore sono tutti problemi estremamente difficili per le reti decentralizzate, dove non è possibile fare affidamento su una fonte centrale di casualità. Ma la selezione casuale può anche risolvere molti problemi economici e contribuire a costruire protocolli più semplici ed efficienti. Supponiamo che nel nostro protocollo ci siano controversie sul pagamento di alcuni servizi poco costosi e che queste controversie si verifichino abbastanza raramente. In questo caso, se esiste un PVRB indiscusso, clienti e venditori possono concordare di risolvere le controversie in modo casuale, ma con una determinata probabilità. Ad esempio, con una probabilità del 60% vince il cliente e con una probabilità del 40% vince il venditore. Questo approccio, assurdo dal primo punto di vista, consente di risolvere automaticamente le controversie con una quota di vincite/perdite esattamente prevedibile, conveniente per entrambe le parti, senza alcuna partecipazione di terzi e inutile perdita di tempo. Inoltre, il rapporto di probabilità può essere dinamico e dipendere da alcune variabili globali. Ad esempio, se un'azienda sta andando bene, ha un basso numero di controversie e un'elevata redditività, l'azienda può spostare automaticamente la probabilità di risolvere una controversia verso la centralità del cliente, ad esempio 70/30 o 80/20, e viceversa, se le controversie richiedono molto denaro e sono fraudolente o inadeguate, è possibile spostare la probabilità nella direzione opposta.
Un gran numero di interessanti protocolli decentralizzati, come registri curati da token, mercati di previsione, curve di legame e molti altri, sono giochi economici in cui il buon comportamento viene premiato e il cattivo comportamento viene penalizzato. Spesso contengono problemi di sicurezza per i quali le protezioni sono in conflitto tra loro. Ciò che è protetto da un attacco di “balene” con miliardi di token (“big stake”) è vulnerabile agli attacchi di migliaia di account con saldi piccoli (“sybil stake”) e alle misure adottate contro un singolo attacco, come non- Le commissioni lineari create per rendere non redditizio lavorare con una grande quota vengono solitamente screditate da un altro attacco. Dato che stiamo parlando di un gioco economico, i corrispondenti pesi statistici possono essere calcolati in anticipo, e basta semplicemente sostituire le commissioni con commissioni randomizzate con la distribuzione adeguata. Tali commissioni probabilistiche vengono implementate in modo estremamente semplice se la blockchain ha una fonte affidabile di casualità e non richiedono calcoli complessi, rendendo la vita difficile sia alle balene che alle sibille.
Allo stesso tempo, è necessario continuare a ricordare che il controllo su un singolo bit in questa casualità consente di imbrogliare, riducendo e aumentando le probabilità della metà, quindi un PVRB onesto è la componente più importante di tali protocolli.
Dove trovare il casuale giusto?
In teoria, una selezione casuale equa nelle reti decentralizzate rende quasi tutti i protocolli sicuri contro la collusione. La logica è abbastanza semplice: se la rete è d'accordo su un singolo 0 o 1 bit e meno della metà dei partecipanti è disonesta, allora, date un numero sufficiente di iterazioni, è garantito che la rete raggiunga un consenso su quel bit con una probabilità fissa. Semplicemente perché un onesto random sceglierà 51 partecipanti su 100 il 51% delle volte. Ma questo è in teoria, perché... nelle reti reali, per garantire il livello di sicurezza come negli articoli, sono necessari molti messaggi tra host, una complessa crittografia multi-pass e qualsiasi complicazione del protocollo aggiunge immediatamente nuovi vettori di attacco.
Questo è il motivo per cui non vediamo ancora un PVRB resistente e comprovato nelle blockchain, che sarebbe stato utilizzato per un tempo sufficiente per essere testato da applicazioni reali, audit multipli, carichi e, naturalmente, attacchi reali, senza i quali è difficile definire un prodotto veramente sicuro.
Tuttavia, esistono diversi approcci promettenti, differiscono in molti dettagli e uno di questi risolverà sicuramente il problema. Con le moderne risorse informatiche, la teoria crittografica può essere tradotta in modo abbastanza intelligente in applicazioni pratiche. In futuro saremo felici di parlare delle implementazioni di PVRB: ora ce ne sono diverse, ognuna ha il proprio insieme di proprietà importanti e caratteristiche di implementazione, e dietro ognuna c'è una buona idea. Non ci sono molti team coinvolti nella randomizzazione e l'esperienza di ciascuno di loro è estremamente importante per tutti gli altri. Ci auguriamo che le nostre informazioni consentano ad altri team di muoversi più velocemente, tenendo conto dell'esperienza dei loro predecessori.
Fonte: habr.com