Casualità pubblica è una componente essenziale di molti protocolli di sicurezza del mondo reale. In alcune applicazioni, come il gioco d'azzardo e i giochi multiplayer, la casualità aggiunge divertimento. In altre applicazioni, la casualità fornisce un modo equo per allocare risorse non divisibili, che vanno dalle carte verdi, all'assegnazione di giudici di corte di circoscrizione ai casi, al seeding nei tornei sportivi. Viene anche utilizzato per allocare negativo. risorse, come controlli fiscali o controlli di sicurezza secondari in aeroporto.

Tradizionalmente, ci siamo affidati ad autorità fidate per generare casualità per questi protocolli, ma nel mondo web3 dovremo fare di meglio. In questo post, esploreremo gli approcci per costruire una casualità verificabile pubblicamente tramite segnali di casualità distribuita e poi discutere alcune applicazioni on-chain. (La Parte II, di prossima pubblicazione, si concentrerà specificamente sull'elezione dei leader, fornendo al contempo una valutazione degli approcci di elezione dei leader alternativi.) 

Proprietà desiderate

Generare numeri casuali è un compito notoriamente sottile. Ad esempio, molte chiavi crittografiche sono trapelate perché si basava su un generatore di numeri casuali difettoso (per cui il muro di Cloudflare lampade lava sarebbe servito da mitigazione creativa). Questo è solo casualità privata, tuttavia, laddove solo una parte deve generarlo e utilizzarlo.

La casualità pubblica, al contrario, è un processo multipartitico, che aumenta considerevolmente la difficoltà. Un buon protocollo per la produzione di casualità pubblica avrà le seguenti proprietà di sicurezza:

• Impassibile: nessun attaccante, o coalizione di aggressori, dovrebbe essere in grado di influenzare l'output. 
• Affidabile: nessun utente malintenzionato dovrebbe essere in grado di impedire al protocollo di produrre output.
• Verificabile: chiunque può verificare facilmente l'output del protocollo e dovrebbe vedere lo stesso output di tutti gli altri.
• Imprevedibile: Se il protocollo produce output in un momento T₁, nessuno dovrebbe essere in grado di prevedere nulla sull'output prima di qualche tempo T₀<T₁, idealmente con T₀ molto vicino a T₁.

L'imprevedibilità è una proprietà più debole dell'imprevedibilità perché qualsiasi protocollo imprevedibile deve essere imparziale. Gli informatici direbbero imparzialità riduce all'imprevedibilità, perché se puoi influenzare, puoi prevedere. Ma a volte vorremo ragionare su di loro separatamente perché possono fare affidamento su ipotesi diverse: ad esempio, una maggioranza disonesta potrebbe prevedere il risultato, ma non influenzarlo.

Oltre a queste proprietà, il protocollo dovrebbe essere efficiente per l'esecuzione e produrre un numero elevato di bit casuali. (In pratica, è spesso sufficiente che le applicazioni producano 128 bit casuali, usandoli per creare un generatore di numeri pseudocasuali [PNRG] per produrre più bit secondo necessità. Tuttavia, l'imprevedibilità dovrebbe valere affinché ogni singolo bit dell'output sia utilizzabile per tale applicazioni come lotterie o allocazioni di risorse.) Il protocollo dovrebbe anche essere idealmente efficiente in termini di costi di comunicazione e calcolo.

Protocolli diversi potrebbero ottenere queste proprietà in condizioni diverse. Ad esempio, alcuni protocolli potrebbero essere imparziali da qualsiasi coalizione di f₁ nodi dannosi e imprevedibili da qualsiasi coalizione di f₂<f₁ nodi dannosi. Ci sono anche diversi gradi di distorsione. Ad esempio, in alcuni protocolli un partecipante potrebbe essere in grado di polarizzare l'output di "un bit", il che significa che può scegliere tra uno dei due possibili output. Altri attacchi potrebbero consentire loro di correggere completamente l'output. In genere, tuttavia, non vogliamo tollerare alcun pregiudizio (o prevedibilità).

L'ideale crittografico: Rfari di andomness

I crittografi spesso iniziano pensando a una soluzione ideale ai loro problemi. In caso di casualità pubblica, a segnale di casualità è un servizio idealizzato che produce regolarmente output casuale che soddisfa tutti i requisiti di sicurezza necessari.

Un tale segnale di casualità idealizzato, simile ad altre astrazioni crittografiche – come gli oracoli casuali o il modello di gruppo generico – non esiste nel mondo reale. Ma è un obiettivo utile a cui tendere e un modello utile per ragionare sui protocolli che si basano sulla casualità pubblica. 

Possiamo considerare alcune approssimazioni di un beacon di casualità ideale.

• Fari centralizzati: L'approccio più semplice per generare una buona casualità è attraverso una terza parte centralizzata con servizi come Segnale di casualità NIST or random.org, che genera casualità dal rumore atmosferico ed è accreditato per l'uso nel gioco d'azzardo. Questa dipendenza da una terza parte mina completamente la filosofia del decentramento. In effetti, nell'esempio sopra, dobbiamo confidare che le organizzazioni competenti stiano generando la casualità in modo corretto, senza alcuna prova crittografica.
• Viene visualizzata la casualità fisica: Molte lotterie tradizionali si basano su un'esposizione pubblica, che potrebbe includere, ad esempio, qualcuno che raggiunge un contenitore di palline da ping pong con numeri diversi su di esse. Sfortunatamente, questi sono spesso facilmente manipolabili. Per esempio, alcune palline possono essere poste in un congelatore ed si può dire al selettore di scegliere quelli freddi.
• Fari naturali: Un'idea comune è quella di utilizzare fenomeni naturali casuali come il tempo o la radiazione cosmica di fondo come faro. Sfortunatamente, tutte le fonti proposte non forniscono un forte consenso. Osservatori diversi vedranno valori leggermente diversi, il che richiede la reintroduzione di una parte fidata per eseguire una misurazione ufficiale, con tutti gli svantaggi di un faro centralizzato.
• Fari semicentrali: Un approccio migliore sarebbe quello di ottenere la casualità da Intestazioni di blocco Bitcoin direttamente o da prezzi di chiusura delle azioni, che è più facile da verificare pubblicamente e più difficile da controllare completamente per qualsiasi parte. Eppure esistono ancora sottili attacchi su entrambi casualità blockchain proof-of-work ed casualità del prezzo delle azioni. Con le intestazioni blockchain, ad esempio, i minatori possono scegliere di trattenere i blocchi le cui intestazioni producono un valore beacon che non gli piace. Oppure possono scegliere di rompere i legami quando vengono trovati due blocchi in collisione in base al loro output di beacon preferito.

Beacon di casualità decentralizzata (DRB)

Un approccio naturale ai problemi dei beacon centralizzati è progettare un protocollo crittografico decentralizzato per produrre casualità pubblica. Questo problema è un po' come progettare protocolli di consenso decentralizzati, solo più difficile. Non solo tutti i partecipanti devono concordare un output (la casualità), ma dovrebbe essere impossibile per un partecipante malintenzionato al protocollo distorcere o prevedere l'output.

I protocolli progettati per simulare un beacon di casualità sono chiamati beacon di casualità distribuita (DRB). (Altri nomi includono "lancio di monete distribuito.") Il problema è stato studiato per decenni, con famosi risultati di impossibilità dimostrati negli anni '1980, ma l'interesse si è riacceso nell'era della blockchain. I DRB potrebbero essere utilizzati per fornire casualità on-chain, che sarebbe un ingrediente chiave per applicazioni on-chain eque, sicure e trasparenti.

L'approccio classico: protocolli Commit-reveal

Un protocollo molto semplice a due round è sufficiente per un DRB nel caso ottimista. Nel round 1, ogni partecipante i genera un valore casuale r_i e pubblica un impegno crittografico c_i=Commettere(r_i). In questa applicazione, l'impegno può essere semplicemente una funzione hash come SHA-256. Dopo che l'impegno di ogni partecipante è stato pubblicato, sono vincolati alla loro scelta r_i, ma gli impegni non rivelano alcuna informazione sui contributi degli altri partecipanti. Nel round 2, ogni partecipante “apre il proprio impegno” pubblicando r_i. Tutti i valori casuali vengono quindi combinati, ad esempio XORing o (preferibilmente) hashing la loro concatenazione.

Questo protocollo è semplice e produce un output beacon casuale purché anche uno dei partecipanti lo scelga r_i a caso. Sfortunatamente, soffre di un classico difetto: quando tutti i partecipanti tranne uno hanno rivelato il loro valore casuale, l'ultimo partecipante è in grado di calcolare l'output del beacon presunto. Se non gli piace, possono rifiutarsi di pubblicare il loro valore, interrompendo il protocollo. Ignorare il contributo di un partecipante difettoso non risolve il problema, perché ciò dà comunque a un utente malintenzionato la possibilità di scegliere tra due output beacon (uno calcolato con il loro contributo e uno senza).

Le blockchain offrono un rimedio naturale a questo problema: a ogni partecipante può essere richiesto di mettere in deposito alcuni fondi che vengono sequestrati se non rivelano il loro contributo casuale. Questo era esattamente l'approccio adottato dal classico RANDAO faro su Ethereum. Lo svantaggio di questo approccio è che l'output può ancora essere distorto, il che potrebbe essere vantaggioso finanziariamente per l'attaccante se il denaro in deposito a garanzia è inferiore alla quantità di denaro derivante dal risultato del beacon. Una migliore sicurezza contro gli attacchi distorsivi richiede di mettere più monete in deposito a garanzia.

Protocolli di commit-reveal-recupero

Invece di cercare di costringere tutte le parti a rivelare il loro contributo casuale, alcuni protocolli includono un meccanismo di recupero in modo che, anche se una minoranza di partecipanti abbandona, il resto può completare il protocollo. È importante che il protocollo produca lo stesso risultato in entrambi i casi, in modo che le parti non possano influenzare il risultato scegliendo se abbandonare o meno.

Un approccio per raggiungere questo obiettivo consiste nel fare in modo che ciascun partecipante fornisca agli altri parti del suo segreto, in modo tale che la maggioranza di loro possa ricostruirlo, utilizzando, ad esempio, La condivisione dei segreti di Shamir. Una proprietà importante, tuttavia, è che gli altri possono verificare che il segreto commesso sia stato correttamente condiviso, richiedendo l'uso di una primitiva più forte chiamata condivisione segreta verificabile pubblicamente (PVSS).

Sono possibili diversi altri meccanismi di recupero, ma hanno tutti la stessa limitazione. Se ci sono N partecipanti e vogliamo resilienza se un gruppo fino a f nodi cade, quindi deve essere il caso che qualsiasi gruppo di Nf i partecipanti possono calcolare il risultato finale. Ma questo significa anche una coalizione maligna di Nf i partecipanti possono prevedere il risultato in anticipo simulando privatamente il meccanismo di recupero. Questo può accadere anche durante il primo round del protocollo, durante il quale una tale coalizione potrebbe modificare le proprie scelte di casualità e influenzare il risultato. 

In altre parole, questo significa qualsiasi coalizione di Nf i nodi devono includere almeno un nodo onesto. Per semplice algebra, Nf > f, Così f < N/2e questi protocolli richiedono intrinsecamente una maggioranza onesta. Questa è una differenza significativa rispetto al modello di sicurezza originale di commit-reveal, che richiede solo f<N (almeno un partecipante onesto).

Questi protocolli spesso richiedono anche notevoli costi di comunicazione per condividere le informazioni PVSS extra tra tutti i nodi in ogni esecuzione del protocollo. La comunità di ricerca ha svolto un lavoro considerevole su questo problema negli ultimi anni, con proposte di ricerca tra cui Rand Condividi, Raschiare, Sec Rand, HERB, o Albatro, ma nessuno sembra aver visto la distribuzione nel mondo reale.

Protocolli verificabili basati su funzioni casuali

Rendendosi conto che un gruppo di Nf i partecipanti possono calcolare il valore del beacon casuale nel protocollo di cui sopra porta a un approccio un po' più semplice: condividere una chiave segreta a lungo termine tra N parti e farli utilizzare per valutare a funzione casuale verificabile (VRF). La chiave segreta è condivisa tramite a t-fuori da-N schema di soglia, in modo che qualsiasi t i partecipanti possono calcolare il VRF (ma una coalizione più piccola non può). Per t=Nf, questo fornisce la stessa resilienza a f nodi dannosi come i protocolli commit-reveal-recover discussi sopra.

DFINITY ha aperto la strada a questo approccio come parte del loro protocollo di consenso utilizzando le firme BLS di soglia (che funzionano come VRF). Il autonomo Drand randomness beacon utilizza essenzialmente lo stesso approccio, con una serie di partecipanti con soglia BLS che firmano un contatore in ogni round. Il Lega dell'entropia è un'istanza open source di drand che produce casualità ogni 30 secondi utilizzando 16 nodi partecipanti (a settembre 2022), gestita da un mix di aziende e gruppi di ricerca universitari. 

Uno svantaggio di questi approcci è che l'inizializzazione della chiave di soglia è relativamente complessa, così come la riconfigurazione della chiave quando i nodi si uniscono o escono. Nel caso comune, però, i protocolli sono molto efficienti. 

Come descritto sopra, la semplice firma di un controvalore non aggiunge alcuna nuova casualità per round, quindi se un numero sufficiente di chiavi dei partecipanti viene compromesso, il protocollo sarà prevedibile in ogni round futuro.

VRF a catena combina questo approccio (usando il NSEC5 VRF) con una fonte esterna di casualità specificata dalle parti che richiedono la casualità, in pratica tipicamente un'intestazione blockchain recente. Questi dati vengono quindi alimentati tramite un VRF gestito da una delle parti o limitato a un gruppo.

Ethereum di Catena del faro attualmente utilizza VRF basati su BLS: il proponente di ogni round aggiunge il proprio valore VRF al mix. Ciò consente di risparmiare un giro di comunicazione rispetto al paradigma commit-reveal (supponendo che una chiave pubblica BLS a lungo termine sia registrata una volta), sebbene questo design erediti alcuni avvertimenti dell'approccio commit-reveal inclusa la possibilità di influenzare l'output del beacon trattenendo l'output .

Protocolli basati su funzioni di ritardo verificabili

Infine, una nuova direzione promettente sta usando la crittografia basata sul tempo, in particolare funzioni di ritardo verificabili (VDF). Questo approccio promette di fornire una buona efficienza e robustezza della comunicazione con resilienza a N-1 nodi dannosi. 

Tornando al protocollo di rivelazione del commit originale, gli impegni tradizionali possono essere sostituiti impegni a tempo eliminare il problema dei partecipanti che rifiutano di rivelare il loro contributo casuale. Gli impegni a tempo possono essere aperti in modo efficiente dal committente originale o da chiunque sia disposto a calcolare una funzione lenta (essenzialmente un VDF). Pertanto, se un partecipante abbandona un protocollo di rivelazione del commit, il suo impegno può comunque essere aperto da altri. È essenziale che il tempo minimo per aprire l'impegno sia sufficientemente lungo da non poterlo fare durante il primo round (fase di commit) del protocollo, altrimenti i partecipanti malintenzionati potrebbero aprire gli impegni degli altri abbastanza velocemente da modificare il proprio contributo e falsare il risultato .

Un protocollo one-round ancora più elegante è possibile con i moderni VDF: abbandonare completamente l'impegno. Ogni partecipante può semplicemente pubblicare il proprio contributo casuale r_i, e il risultato finale è una combinazione del contributo di ciascun partecipante, eseguito attraverso un VDF. Il ritardo nel calcolo del VDF garantisce che nessuno possa scegliere il proprio impegno in un modo che distorce l'output finale. Questo approccio è stato proposto come UNICORN di Arjen Lenstra e Benjamin Wesolowski nel 2015, e in effetti è stata un'applicazione motivante chiave nel sviluppo di VDF.

Questo approccio ha visto una diffusione pratica. Chia implementa una versione di questo come parte del suo protocollo di consenso, utilizzando VDF a quadrati ripetuti nei gruppi di classi. Starkware implementato a beacon basato su VDF proof-of-concept utilizzando VDF basati su SNARK. Ethereum anche piani usare questo approccio, costruendo un ASIC dedicato per il calcolo dei VDF per generare casualità a livello di consenso.

***

La casualità pubblica è una componente essenziale di molti protocolli, ma manca ancora un DRB standard che fornisca un'elevata sicurezza. Lo spazio di progettazione è ampio e sono possibili molti ibridi e combinazioni degli approcci di cui sopra. Ad esempio, è possibile combinare un protocollo basato su VRF con un protocollo basato su VDF, che aggiunge nuova entropia, ad esempio, come proposto da Rand Runner. La Beacon Chain di Ethereum attualmente utilizza VRF, anche se in futuro potrebbe aggiungere VDF per eliminare la possibilità di pregiudizi da attacchi con ritenuta di blocco.

È anche una questione aperta quando i protocolli a maggioranza onesta sono accettabili. Per un gruppo di partecipanti relativamente piccolo e controllato, come la League of Entropy, un'ipotesi di maggioranza onesta è ragionevole. D'altra parte, i protocolli che richiedono un solo partecipante onesto hanno un vantaggio intrinseco: più partecipanti possono solo migliorare la sicurezza. Ciò significa che questi protocolli possono essere potenzialmente implementati con una partecipazione aperta e senza autorizzazione.

Nella parte II, discuteremo l'applicazione specifica dell'elezione randomizzata dei leader nei protocolli di consenso, che ha obiettivi di progettazione leggermente diversi e, di conseguenza, ha visto ancora più protocolli e approcci proposti.

***

Joseph bonneau è un partner di ricerca presso a16z crypto. La sua ricerca si concentra sulla crittografia applicata e sulla sicurezza blockchain. Ha tenuto corsi di criptovaluta presso l'Università di Melbourne, NYU, Stanford e Princeton, e ha conseguito un dottorato di ricerca in informatica presso l'Università di Cambridge e una laurea magistrale a Stanford.

Valeria Nikolaenko è un partner di ricerca presso a16z crypto. La sua ricerca si concentra sulla crittografia e sulla sicurezza blockchain. Ha anche lavorato su argomenti come attacchi a lungo raggio nei protocolli di consenso PoS, schemi di firma, sicurezza post-quantistica e calcolo multipartitico. Ha conseguito un dottorato di ricerca in crittografia presso la Stanford University sotto la consulenza del professor Dan Boneh e ha lavorato sulla blockchain di Diem come parte del team di ricerca principale.

***

Editor: Tim Sullivan

***

Le opinioni qui espresse sono quelle del personale di AH Capital Management, LLC ("a16z") citato e non sono le opinioni di a16z o delle sue affiliate. Alcune informazioni qui contenute sono state ottenute da fonti di terze parti, incluse società in portafoglio di fondi gestiti da a16z. Sebbene tratti da fonti ritenute affidabili, a16z non ha verificato in modo indipendente tali informazioni e non fornisce dichiarazioni sull'accuratezza duratura delle informazioni o sulla loro adeguatezza per una determinata situazione. Inoltre, questo contenuto può includere pubblicità di terze parti; a16z non ha esaminato tali annunci pubblicitari e non approva alcun contenuto pubblicitario in essi contenuto.

Questo contenuto viene fornito solo a scopo informativo e non deve essere considerato come consulenza legale, commerciale, di investimento o fiscale. Dovresti consultare i tuoi consulenti in merito a tali questioni. I riferimenti a qualsiasi titolo o risorsa digitale sono solo a scopo illustrativo e non costituiscono una raccomandazione di investimento o un'offerta per fornire servizi di consulenza in materia di investimenti. Inoltre, questo contenuto non è diretto né destinato all'uso da parte di investitori o potenziali investitori e non può in alcun caso essere invocato quando si decide di investire in qualsiasi fondo gestito da a16z. (Un'offerta per investire in un fondo a16z sarà fatta solo dal memorandum di collocamento privato, dal contratto di sottoscrizione e da altra documentazione pertinente di tale fondo e dovrebbe essere letta nella sua interezza.) Eventuali investimenti o società in portafoglio menzionati, citati o descritti non sono rappresentativi di tutti gli investimenti in veicoli gestiti da a16z, e non si può garantire che gli investimenti saranno redditizi o che altri investimenti effettuati in futuro avranno caratteristiche o risultati simili. Un elenco degli investimenti effettuati da fondi gestiti da Andreessen Horowitz (esclusi gli investimenti per i quali l'emittente non ha autorizzato a16z a divulgare pubblicamente e gli investimenti non annunciati in asset digitali quotati in borsa) è disponibile all'indirizzo https://a16z.com/investments /.

Grafici e grafici forniti all'interno sono esclusivamente a scopo informativo e non dovrebbero essere presi in considerazione quando si prende una decisione di investimento. I rendimenti passati non sono indicativi di risultati futuri. Il contenuto parla solo a partire dalla data indicata. Eventuali proiezioni, stime, previsioni, obiettivi, prospettive e/o opinioni espresse in questi materiali sono soggette a modifiche senza preavviso e possono differire o essere contrarie alle opinioni espresse da altri. Si prega di consultare https://a16z.com/disclosures per ulteriori informazioni importanti.