Elezione del leader da segnali di casualità e altre strategie

L'elezione del leader in un ambiente blockchain mira a selezionare il partecipante che determinerà il blocco successivo da aggiungere alla blockchain. In genere, viene scelto un validatore per slot dall'insieme di validatori e ottiene il diritto di estendere la catena con un nuovo blocco in quello slot. (Presumiamo che i validatori mantengano l'ora esatta e concordino sul numero di slot corrente.) In questo articolo esploriamo le strategie per elezione casuale del leader nei protocolli di consenso. (Per ulteriori informazioni sulla casualità in generale, vedere il nostro precedente articolo, Segnalazioni pubbliche di casualità e casualità, Dove abbiamo esaminato protocolli autonomi per generare casualità pubblicamente verificabile e imprevedibile.) 

Perché l'elezione del leader è importante

L'elezione di leader onesti e attivi è fondamentale per la sana crescita della filiera. I validatori malintenzionati non dovrebbero essere in grado di influenzare il processo di elezione del leader per diventare leader più frequentemente. In caso contrario, la produzione di blocchi potrebbe cadere nelle mani di parti che possono censurare le transazioni o bloccare del tutto la blockchain. Nei protocolli di consenso in stile catena più lunga, un leader che produce un blocco non valido (o nessun blocco) potrebbe causare il fork temporaneo della catena. Nei protocolli di consenso in stile BFT, un cattivo leader attiva un sottoprotocollo di cambio di visualizzazione che comporterà un sovraccarico di comunicazione. 

L'alternativa elettorale del comitato

L'elezione del comitato è un problema correlato, in cui l'obiettivo è selezionare un sottoinsieme uniformemente casuale dei validatori di una certa dimensione fissa k. Questa funzionalità è utile di per sé perché i sottocomitati sono spesso necessari nelle impostazioni blockchain per ridurre la dimensione del set di validatori per rendere più veloce il consenso (tra i molti esempi ci sono L'ordinamento di Algorand ed Selezione del comitato di Ethereum). Ma l'elezione del comitato è utile anche per l'elezione del leader, consentendo ai validatori di evitare di ripetere un protocollo di elezione del leader se il leader eletto non si presenta. Se, invece di un capogruppo, viene eletto un comitato con un ordine fisso, il secondo membro del comitato può diventare capogruppo se il primo non è disponibile. 

Le proprietà di un buon protocollo elettorale

In un protocollo elettorale di leader, i leader dovrebbero essere imprevedibili. Se un utente malintenzionato scopre chi è il prossimo leader, potrebbe lanciare un attacco Denial of Service (DoS) contro di loro per impedire loro di pubblicare un blocco. L'attaccante potrebbe quindi abbattere il leader successivo e così via, arrestando la blockchain. L'imprevedibilità potrebbe anche essere rafforzata per garantire che il validatore stesso non apprenda quando guiderà, il che potrebbe essere importante per la prevenzione della corruzione.

Il processo di elezione del leader dovrebbe avere le seguenti tre proprietà:

• Equità: ogni validatore onesto ha una probabilità di 1/N essere eletto da un insieme di N validatori (una nozione rilassata di l'equità teorica del gioco lo consente costruendo l'elezione del capogruppo anche in presenza di una maggioranza maliziosa seppure con un limite inferiore non costante sul numero di turni).
• imprevedibilità: l'avversario non impara il prossimo leader fino a qualche tempo T prima che il leader annunci il blocco successivo.
• Unicità: viene scelto esattamente un leader in ogni slot.

Elezione segreta del leader

L'elezione del leader segreto è un'elezione imprevedibile con T = 0. In questo processo, il leader non è noto a nessuno finché non pubblica il blocco. Ciò elimina completamente la finestra per un attacco DoS: prima che il leader si riveli, l'attaccante non sa chi attaccare, facendo della sua migliore strategia un'ipotesi casuale. E dopo che il leader ha pubblicato il suo blocco, è troppo tardi per attaccare perché il leader ha già adempiuto alle proprie responsabilità nei confronti del protocollo. 

La nozione di "dopo che il leader ha pubblicato il suo blocco" è in realtà una semplificazione, perché non abbiamo una trasmissione istantanea nel mondo reale. Un utente malintenzionato con una posizione di rete forte potrebbe notare prima un leader che trasmette un blocco ed essere in grado di corrompere rapidamente il leader, creare un blocco diverso ed eseguire in anticipo la trasmissione originale. 

Sebbene questo sia un modello di attacco molto forte, sono state proposte difese contro di esso. Algorand ha proposto il modello di cancellature, in cui il leader è effettivamente in grado di cancellare la chiave necessaria per firmare il blocco nel suo slot prima trasmettendolo, quindi è davvero troppo tardi per attaccare quando il leader intraprende un'azione pubblica. Thaddeus Dryja, Quanquan C. Liu e Neha Narula, tre ricercatori del MIT Media Lab, proposto che il leader calcoli un VDF sul suo blocco prima della trasmissione, assicurandosi che un attaccante adattivo non possa costruire un blocco valido alternativo in tempo per farlo accettare per lo slot desiderato.

Altri metodi elettorali 

Il processo di elezione del leader più semplice è round robin, dove i leader sono eletti in ordine deterministico. Nonostante questo approccio sia prevedibile e quindi soggetto ad attacchi DoS, è adatto per sistemi autorizzati in cui i validatori hanno una buona protezione DoS.

Un leader può anche essere eletto utilizzando un'uscita di un esterno segnale di casualità, se uno è disponibile e considerato sicuro. Sfortunatamente, è complicato per i partecipanti al consenso eseguire da soli un protocollo DRB (Distributed Randomness Beacon), poiché questi in genere presuppongono una nozione di trasmissione o consenso affidabile, che a sua volta richiede nuovamente l'elezione del leader, introducendo una dipendenza circolare.

Corrente elezione del leader in Ethereum è un buon caso di studio. Ogni nuovo leader calcola un output VRF (Verifiable Randomness Function) (una firma BLS sul numero di epoca) e XOR il valore nel mix. Il valore del mix alla fine dell'epoca i definisce i dirigenti ei sottocomitati per la durata d'epoca i+2. I leader e il loro programma sono prevedibili con un'epoca di anticipo (attualmente ~ 6.4 min). Il protocollo è soggetto ad attacchi di equità, poiché l'ultimo leader può scegliere di pubblicare o nascondere il proprio contributo al mix e quindi influenzare di un po' il risultato delle prossime elezioni. Se l'ultimo  k i leader colludono, possono presentare k  bit di pregiudizi e rendere più probabile l'elezione di utenti malintenzionati. La Ethereum Foundation sta lavorando attivamente a tecniche più avanzate per l'elezione del leader che discuteremo di seguito.

Elezione del leader basata su VRF

Un altro approccio, sperimentato da Algorand, è un Elezione del leader basata su VRF, che prevede che ciascun validatore calcoli privatamente un output VRF e controlli se l'output scende al di sotto di una soglia. Questa procedura filtra già la maggior parte dei validatori, poiché la soglia è scelta in modo tale che sia improbabile che scenda al di sotto di essa. I pochi validatori rimasti rivelano i loro output VRF e viene eletto quello con il valore VRF più basso. Questo approccio raggiunge la perfetta imprevedibilità (o segretezza), ma non garantisce l'unicità. Alcuni dei validatori potrebbero non ricevere messaggi da tutti i potenziali leader e potrebbero presumere che il leader sbagliato abbia vinto le elezioni, causando il fork di questi validatori dalla catena principale. 

La valutazione VRF viene periodicamente seminata con l'output di un segnale di casualità per rendere meno prevedibile per i validatori stessi vedere quali slot guideranno. Questa proprietà impedisce a un utente malintenzionato che comprometta silenziosamente il validatore di apprendere lo slot quando il validatore diventerebbe un leader e di lanciare un attacco quando il validatore sta per annunciare un blocco. Questo approccio aiuta anche a prevenire gli attacchi di corruzione, in cui un validatore dimostra a parti esterne che sarà un leader in un particolare slot e raccoglie tangenti in cambio del completamento di alcune attività come leader (ad esempio, il blocco di una transazione).

Vengono chiamati tali approcci, in cui il numero di leader eletti è una variabile casuale Elezione probabilistica del leader (PL). Il PLE può comportare che nessun leader venga eletto per un determinato slot. Ciò equivale a eleggere un leader malintenzionato o offline in quanto lo slot finirà per essere saltato, riducendo l'efficienza del protocollo di consenso.

Ma il più grande avvertimento con PLE è che potrebbero essere eletti più leader, rendendo necessaria una sorta di procedura di spareggio. I pareggi rappresentano un rischio per il consenso, poiché un validatore con un input vincente può segnalarlo solo a metà della rete, causando potenzialmente disaccordo nel leader scelto. Inoltre, i processi per la risoluzione dei problemi possono richiedere più tempo e comunicazioni, danneggiando l'efficienza. Dfinity, discusso più dettagliatamente in il primo post di questa serie, utilizza un segnale di casualità basato su VRF per eleggere un singolo leader; tuttavia, sacrifica l'imprevedibilità per farlo. Idealmente, qualsiasi processo per la scelta di un leader dovrebbe evitare del tutto i legami ed essere comunque imprevedibile, il che ci porta al Santo Graal di quest'area di ricerca: l'elezione del leader segreto singolo.

Elezione del leader segreto unico 

L'obiettivo di Elezione del leader segreto unico (SSLE) consiste nel selezionare un leader unico da un insieme di validatori mantenendo l'equità e l'imprevedibilità. Protocol Labs ha presentato l'idea come a problema di ricerca, e Dan Boneh, scienziato informatico di Stanford e consulente per la ricerca sulle criptovalute a16z, con Saba Eskandarian, Lucjan Hanzlik e Nicola Greco, in seguito hanno offerto una definizione formale di SSLE. Questa proprietà di unicità evita i rischi di consenso ei costi di efficienza derivanti dalle procedure di pareggio. In concreto, Sarah Azouvi, di Protocol Labs, e Danielle Cappelletti, del Politecnico di Torino, mostrare attraverso le sue creazioni che quando SSLE viene utilizzato rispetto a PLE in un protocollo a catena più lunga, i blocchi possono essere finalizzati molto più velocemente (il 25% più velocemente con un avversario che controlla un terzo della puntata). Pertanto, lo sviluppo di un protocollo SSLE pratico è un problema importante.

Nell'approccio più comune, che chiameremo basato su shuffle (utilizzato sia nella carta SSLE originale che in una proposta SSLE di Ethereum), ogni validatore registra a nonce che sembra casuale, ma che possono dimostrare che appartiene a loro. I nonce vengono quindi compilati in un elenco. L'elenco viene rimescolato in modo tale che i nonce vengano scollegati dai validatori che li hanno inviati; cioè, dato l'elenco rimescolato, nessun avversario può dire quale validatore ha inviato quale nonce. Viene quindi scelto un indice di elenco in base a un pubblico segnale di casualità, e il leader si rivela dimostrando che il nonce in quell'indice della lista rimescolata appartiene a loro. 

Poiché viene scelto un solo indice, il protocollo basato su shuffle emette sempre a unico capo. Poiché il random beacon è costruito per emettere valori uniformemente casuali, lo è anche il protocollo fiera: ogni validatore ha pari possibilità di essere eletto. Inoltre, se lo shuffling viene eseguito correttamente (ovvero, uniformemente a caso) e i nonce diventano non collegabili alle identità dei validatori, questo protocollo raggiunge anche imprevedibilità.

Lo shuffling è necessario perché mentre la semplice scelta di un indice dall'elenco non mescolato sulla base di un beacon casuale darebbe già unicità ed equità, l'imprevedibilità è più difficile da ottenere: se un avversario sa quale validatore ha inviato quale nonce, sa chi ha inviato il nonce al prescelto indice e può identificare il leader. 

Questi due approcci seguenti rimescolano l'elenco in modi diversi. Il più semplice è il Proposta SSLE di Ethereum, In cui n i validatori inviano i loro nonce tramite Tor per scollegare le identità dei validatori dai loro nonce. Una volta che tutti i validatori si sono registrati, l'elenco viene rimescolato utilizzando un beacon pubblico di casualità e i validatori diventano i leader nell'ordine dell'elenco rimescolato. Sebbene questo schema sia pratico, le elezioni devono essere eseguite solo una volta per n slot: questa dipendenza da Tor potrebbe essere indesiderabile (come nel caso dell'affidamento alla sicurezza di qualsiasi protocollo esterno). Inoltre, non è perfettamente imprevedibile: dopo il primo n-1 capolista si svela, finale nth leader è noto.

Invece di usare Tor, il documento SSLE originale prevede che ogni validatore si registri per l'elezione in sequenza aggiungendo il suo nonce all'elenco, mescolando l'elenco e ri-randomizzazione le nonce. Questa ri-randomizzazione significa che ogni nonce viene mappato su una nuova stringa non collegabile in modo tale che il validatore a cui appartiene possa ancora provare la proprietà del nonce ri-randomizzato. La ri-randomizzazione fa in modo che un avversario non possa dire in quale posizione sia finito un particolare nonce dopo lo shuffle, assumendo che almeno uno shuffler sia onesto.

Sebbene questo approccio di mescolamento sequenziale del documento SSLE originale eviti di fare affidamento su Tor e raggiunga le proprietà formali di SSLE, è costoso: ogni volta che un nuovo validatore si registra, deve pubblicare l'intero elenco mescolato sulla blockchain, ri-randomizzare tutti i nonce e fornire una prova che lo hanno fatto onestamente, il che si traduce in una quantità lineare di comunicazioni per validatore. Con un insieme immutabile di validatori, questo deve essere fatto (ammortizzato) una volta per elezione, poiché il leader si registra nuovamente una volta rivelata la prova del nonce. Il documento fornisce un compromesso sintonizzabile tra efficienza e prevedibilità: possiamo invece mescolare solo un sottoinsieme più piccolo dell'elenco, riducendo i costi, se siamo disposti a consentire una piccola quantità di prevedibilità. Raggiungere un buon equilibrio tra efficienza e sicurezza è impegnativo e, di conseguenza, i protocolli SSLE devono ancora essere ampiamente utilizzati nella pratica. 

Convenientemente, questo approccio di mescolamento sequenziale può anche essere utilizzato per risolvere il problema dell'elezione del comitato, utilizzando il segnale casuale per scegliere k indici distinti dall'elenco come membri del comitato. Questo è un bel risultato, poiché il problema non è banalmente risolto dagli approcci basati su VRF, poiché l'esecuzione di un protocollo probabilistico basato su VRF k i tempi possono eleggere una dimensione del comitato variabile a seconda della casualità. 

Altri approcci a SSLE

Un altro approccio basato sullo shuffle è SSLE protetto in modo adattivo da DDH. Questa costruzione è leggermente più complicata ma raggiunge una nozione di sicurezza più forte, proteggendo da un avversario adattivo nel modello delle cancellature di Algorand. Questo avversario è adattivo in quanto può scegliere quali validatori corrompere durante il protocollo, invece che prima dell'inizio del protocollo. 

Un'ulteriore sfida in SSLE è l'elezione di ogni validatore con probabilità proporzionale alla loro puntata, piuttosto che uniformemente a caso. I protocolli basati sullo shuffling possono ingenuamente raggiungere questo obiettivo consentendo a ciascun validatore di registrare più nonce: un nonce per ogni unità di puntata che detiene. Tuttavia, il costo del rimescolamento aumenta linearmente con il numero di unità di puntata S, diventando molto costoso anche per distribuzioni di puntate realistiche. Un elegante SSLE basato su MPC approccio ha complessità crescente solo con log S, ed evita anche la necessità di una configurazione attendibile o di un beacon di casualità. Tuttavia, rispetto agli approcci basati sullo shuffling, richiede più cicli di comunicazione (logaritmici nel numero di partecipanti) per leader eletto

***

Abbiamo riassunto la nostra analisi in questa comoda tabella.

	Equità	Imprevedibilità/ Segretezza*	Unicità
Girone all'italiana	✓	✗	✓
Faro di casualità ideale	✓	✗	✓
Elezione del leader di Ethereum (attuale)	✗	✗	✓
Elezione del leader basata su VRF (Algorand)	✓	✓	✗
SSL	✓	✓	✓

* Il beacon round-robin è completamente prevedibile, ma nel resto dei beacon ✗ significa che la nozione è raggiunta fino a un certo grado limitato: il segnale di casualità ideale è imprevedibile ma l'avversario apprende l'uscita contemporaneamente al leader eletto, quindi il leader eletto può essere attaccato prima che annunci un blocco; Il beacon di Etherum è imprevedibile fino a ~6 min e può essere leggermente distorto per danneggiare l'equità; Algorand elegge più leader con una piccola probabilità.

SSLE è una direzione promettente, che raggiunge equità, imprevedibilità e unicità. Due sfide importanti per la sua adozione sono l'efficienza e la capacità di accogliere distribuzioni di puntate non uniformi. Inoltre, gli approcci SSLE basati su shuffle che evidenziamo presuppongono l'esistenza di un segnale casuale imparziale, che non è semplice da ottenere nella pratica. Poiché SSLE è stato definito formalmente solo di recente, è probabile che nel prossimo futuro vedremo protocolli migliorati per affrontare le sue sfide. 

***

Miranda Cristo è una dottoranda in Informatica presso la Columbia University, dove è membro del Theory Group e Presidential Fellow. È anche una stagista di ricerca presso a16z crypto.

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.