L’algoritmo del consenso è elemento essenziale della tecnologia blockchain. In questo articolo cercheremo di dare una panoramica delle sue differenti implementazioni, approfondendo le descrizioni di tre tipologie in particolare: Nakamoto Consensus, BFT, Avalanche.
Il problema del consenso
Sebbene, spesso, le Blockchain siano associate ad applicazioni finanziarie, le cui radici affondano nel campo specifico della moneta elettronica, in realtà le soluzioni su cui sono basati Bitcoin o Ethereum fanno riferimento a un campo dell’informatica che è sorprendentemente lontano dagli approcci tradizionali, ovvero quello relativo ai sistemi distribuiti. In un sistema informatico distribuito il problema maggiormente studiato è quello del mantenimento della coerenza tra i nodi che lo costituiscono. Consideriamo ad esempio un sistema molto noto come Facebook, in cui una persona invia un contenuto che viene ricevuto “istantaneamente” da (potenzialmente) due miliardi di utenti. Implementare un sistema come Facebook su un singolo calcolatore è, evidentemente, impossibile per via di problematiche legate a prestazioni e capacità di memorizzazione. Di conseguenza Facebook è implementato da decine di migliaia di nodi di calcolo distribuiti per il mondo, a cui ciascun utente può collegarsi trovando, indifferentemente dal nodo a cui si collega, sempre la stessa “visione” del mondo. Mantenere coerente questa visione tra tutti i nodi di calcolo è un problema non banale, studiato ormai da quasi cinquant’anni e che va sotto il nome del “problema del consenso”.
In pratica, gli algoritmi del consenso hanno l’obiettivo di far sì che un insieme di nodi “concordino” circa lo stato complessivo del sistema in ogni istante di tempo. Questo stato è rappresentato dall’insieme dei post in un’applicazione come Facebook. In Bitcoin ed Ethereum, invece, tale stato è rappresentato dalla storia delle transazioni. Pertanto, i nodi che appartengono alla rete Bitcoin non fanno altro che eseguire una complicata coreografia per mantenere la coerenza della storia delle transazioni. Rispetto a Facebook, tuttavia, in Bitcoin c’è un’importante differenza: i nodi possono comportarsi in modo malizioso ed eseguire il protocollo in modo volutamente errato al fine di violare la coerenza del sistema a proprio vantaggio (ad es. effettuando un double spending). Quando tipo di comportamenti viene definito “bizantino” e la coreografia (i.e. l’algoritmo del consenso) deve far si che i nodi onesti della rete non vengano influenzati dai nodi maliziosi in modo da raggiungere comunque uno stato coerente.
Infine, sempre rispetto a sistemi come Facebook, un altro tratto essenziale della rete Bitcoin è che tale algoritmo di consenso deve essere decentralizzato, ovvero nessun nodo, nel complesso, deve avere un ruolo “primario” diverso da quello degli altri nodi. Tale specifica caratteristica ha reso famoso Bitcoin in quanto, differentemente da soluzioni precedenti di moneta elettronica, esso rappresenta la prima implementazione che non si basa su un’autorità centrale per il mantenimento dell’integrità. Chiarito quindi il contesto in cui ci muoviamo, proviamo ora ad analizzare tre algoritmi di consenso pradigmatici, usati oggi in contesti Blockchain.
L’algoritmo Nakamoto Consensus
Il Nakamoto Consensus è l’algoritmo presentato da Satashi Nakamoto nel suo paper “Bitcoin: A Peer-to-Peer Electronic Cash System” del 2008 e rappresenta la vera innovazione su cui si fonda Bitcoin e tutte le altre criptovalute derivate, come Ethereum. Come ogni altro algoritmo di consenso, anche il Nakamoto Consensus è un algoritmo che si basa su un meccanismo di voto. In pratica, i nodi della rete sono chiamati a votare circa la storia delle transazioni, affermando il proprio consenso su una specifica sequenza. La sequenza che ha ricevuto più voti sarà quindi quella vincente e rappresenterà lo stato del sistema per tutti i nodi onesti della rete.
Oltre a ciò, e similarmente a quanto accade in altri algoritmi, il Nakamoto Consensus è un algoritmo di tipo “leader-based”. In un certo istante di tempo, infatti, un nodo della rete viene selezionato “a caso” (tramite il meccanismo del Proof-of-Work) e gli viene conferita la facoltà di annunciare il blocco di transazioni successivo. Com’è noto, tale blocco viene “agganciato” al blocco precedente tramite il meccanismo dell’hash, determinando una catena di blocchi (appunto, la Blockchain) che ha proprietà molto forti di integrità. Quello che però è meno noto ed evidente è che il “leader”, nel momento in cui aggancia il proprio blocco alla catena definita fino a quell’istante, sta contestualmente esprimendo il proprio consenso (i.e. sta votando) sul fatto che quella catena di blocchi sia, in effetti, quella giusta. E altrettanto faranno tutti i leader che verranno eletti successivamente con il meccanismo del Proof-of-Work. Ogni blocco precedente riceverà quindi un voto (in gergo Bitcoin, una conferma) ogni qual volta un leader aggancerà un nuovo blocco alla catena di cui fa parte. A questo punto sarebbe da chiedersi: quando terminano le votazioni e una particolare sequenza viene dichiarata vincente?
La risposta è sorprendete: mai. Nel Nakamoto Consensus, infatti, la “finalità” (o irrevocabilità) di un blocco non si raggiunge mai. Quindi, se vogliamo, l’algoritmo del consenso di Bitcoin non è veramente tale perché il consenso definitivo attorno a una sequenza, in realtà, non si raggiunge mai. È infatti possibile (ma improbabile) che, in qualsiasi momento, una parte “maliziosa” della rete competa con la parte “onesta” affinché faccia prevalere la propria sequenza, in cui, magari, alcune transazioni non sono mai avvenute.
Come si supera questa situazione? Satoshi fornisce una risposta “probabilistica” a questa domanda, affermando nel suo paper che, se i nodi maliziosi della rete non posseggono più del 50% della capacità di calcolo complessiva, la probabilità che essi possano cambiare uno specifico blocco della sequenza diventa esponenzialmente più bassa man mano che tale blocco sprofonda nella catena. Per questo, nel mondo Bitcoin, esiste una regola empirica che suggerisce di attendere sei conferme (i.e. sei voti) per avere la ragionevole (ma non assoluta) certezza che una transazione in un blocco non possa più essere cambiata. Tale formulazione “probabilistica” del consenso, seppure più debole rispetto a una di natura “deterministica”, consente di implementare un algoritmo di consenso che scala facilmente su milioni di nodi e che funziona in condizioni di rete molto degradate, senza una identificazione precisa dei nodi che compongono la rete.
Algoritmi BFT (Byzantine Fault Tolerant)
Il fatto che il Nakamoto Consensus fosse, in effetti, diverso dagli altri proposti in precedenza, è rilevabile dalla soglia di nodi onesti presenti sulla rete, pari, come detto, al 50%. Esiste infatti un risultato molto importante nella teoria dei sistemi distribuiti, scoperto da Leslie Lamport nel 1982, il quale stabilisce che, indipendentemente da quale sia l’algoritmo di consenso utilizzato, esso non potrà mai funzionare se i nodi maliziosi della rete superano il 33% della capacità di voto complessiva (o di calcolo, nel caso di Bitcoin) del sistema.
Come mai allora il Nakamoto Consensus funziona anche in presenza di una percentuale di nodi maliziosi superiore al 33% (ma inferiore al 50%)? La differenza sostanziale consiste, appunto, nel fatto che nel Nakamoto Consensus la finalità delle transazioni non si raggiunge mai. Diverso è il caso di una classe di algoritmi, chiamati BFT, che invece garantiscono l’irrevocabilità dei blocchi entro un tempo finito. Tale caratteristica allettante si ottiene però al costo di tollerare al massimo il 33% di nodi maliziosi sulla rete. Tali algoritmi, noti sin dai tempi del risultato di Lamport, sono anch’essi basati sulla presenza di un “leader” che propone un blocco e si riferiscono tutti al medesimo schema di funzionamento:
- Un leader propone un blocco agli altri nodi.
- I nodi che sono d’accordo con questo blocco rispondono esprimendo il proprio voto al leader.
- Il leader, ricevuto un certo numero di voti sulla propria proposta, la finalizza, comunicando l’esito della votazione agli altri nodi.
Poiché il processo ha un numero finito di passi, esso si conclude in un tempo finito, oppure non si conclude affatto (ad esempio perché il leader è disonesto) e, dopo un timeout, si procede a selezionare un nuovo leader e a ripetere il processo. In tal modo, ogni blocco viene finalizzato in modo deterministico e l’esito della votazione non può più essere cambiato (irrevocabilità). Gli iniziali algoritmi BFT erano estremamente inefficienti in termini di quantità di informazioni scambiate tra i nodi. Tutta la ricerca di questi decenni si è quindi rivolta a rendere più efficienti questi algoritmi. Nel 2001, Castro ed altri ricercatori dei laboratori Microsoft, trovarono un’implementazione particolarmente efficiente del BFT, che chiamarono Practical BFT (pBFT) e che consentiva una buona scalabilità su un centinaio di nodi. Tale algoritmo è ad esempio disponibile, insieme ad altri, nel framework Hyperledger di IBM.
È interessante osservare come il pBFT sia stato inventato 7 anni prima del paper di Nakamoto, quando i due campi applicativi dei sistemi distribuiti e della moneta elettronica erano ancora molto distanti. Ed è proprio dopo l’invenzione di Bitcoin che la ricerca sugli algoritmi BFT ottiene un grande impulso, vista l’applicabilità al settore della moneta elettronica. Oggi, una variante molto efficiente del BFT è utilizzata in Libra, il sistema di pagamento studiato da Facebook. Sebbene lo schema implementato sia lo stesso descritto sopra, il LibraBFT utilizza particolari primitive crittografiche (come le Verifiable Random Function) per renderlo estremamente efficiente.
Avalanche
Infine, Avalanche, una nuova classe di algoritmi di consenso radicalmente diversi da Nakamoto Consensus e BFT e che oggi viene proposto nella omonima cryptovaluta. In pratica Avalanche è un algoritmo di consenso non basato su leader. Ogni nodo della rete, infatti, interroga un campione scelto a caso di altri nodi della rete e, in base alle risposte che ottiene, determina autonomamente quale sia la sequenza corretta di transazioni, senza bisogno che un leader la indichi ex-ante. Tali interrogazioni vengono effettuate continuamente e le regole applicate dai nodi consentendo ai nodi onesti della rete di convergere, entro un tempo relativamente breve (qualche secondo), sulla stessa storia delle transazioni, sebbene la finalità, come nel Nakamoto Consensus, non si raggiunga mai.
Avalanche sembra essere molto promettente, consentendo di raggiungere un throughput delle transazioni molto elevato, senza sprechi di risorse (non c’è mining) e con una scalabilità molto elevata sul numero di nodi presenti nella rete.
