La guida

Blockchain, gli algoritmi del consenso: che cosa sono e a cosa servono

Analizziamo tre algoritmi di consenso individuando i loro utilizzi nell’ambito della tecnologia blockchain, descrivendone le caratteristiche

30 Gen 2020
Cristiano Paris

Senior Cybersecurity Expert at European Central Bank

blockchain-e-reddito

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”.

WHITEPAPER
Perché impostare una strategia di manutenzione dei server?
Datacenter
Sicurezza

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.

@RIPRODUZIONE RISERVATA

Speciale PNRR

Tutti
Incentivi
PA
Sostemibilità
Analisi
Formazione
Salute digitale
Sicurezza
Sostenibilità
Digital Economy
Formazione
Trasferimento tecnologico, il Mise mette sul piatto 7,5 milioni
Strategie
PSN e Strategia Cloud Italia: a che punto siamo e come supportare la PA in questo percorso
Dispersione idrica
Siccità: AI e analisi dei dati possono ridurre gli sprechi d’acqua. Ecco gli interventi necessari
PNRR
Cloud, firmato il contratto per l’avvio di lavori del Polo strategico
Formazione
Competenze digitali, stanziati 48 milioni per gli Istituti tecnologici superiori
Iniziative
Digitalizzazione delle reti idriche: oltre 600 milioni per 21 progetti
Competenze e competitività
PNRR, così i fondi UE possono rilanciare la ricerca e l’Università
Finanziamenti
PNRR, si sbloccano i fondi per l’agrisolare
Sanità post-pandemica
PNRR, Missione Salute: a che punto siamo e cosa resta da fare
Strategie
Sovranità e autonomia tecnologica nazionale: come avviare un processo virtuoso e sostenibile
La relazione
Pnrr e PA digitale, l’alert della Corte dei conti su execution e capacità di spesa
L'editoriale
Elezioni 2022, la sfida digitale ai margini del dibattito politico
Strategie
Digitale, il monito di I-Com: “Senza riforme Pnrr inefficace”
Transizione digitale
Pnrr: arrivano 321 milioni per cloud dei Comuni, spazio e mobilità innovativa
L'analisi I-COM
Il PNRR alla prova delle elezioni: come usare bene le risorse e centrare gli obiettivi digitali
Cineca
Quantum computing, una svolta per la ricerca: lo scenario europeo e i progetti in corso
L'indice europeo
Desi, l’Italia scala due posizioni grazie a fibra e 5G. Ma è (ancora) allarme competenze
L'approfondimento
PNRR 2, ecco tutte le misure per cittadini e imprese: portale sommerso, codice crisi d’impresa e sismabonus, cosa cambia
Servizi digitali
PNRR e trasformazione digitale: ecco gli investimenti e le riforme previste per la digitalizzazione della PA
Legal health
Lo spazio europeo dei dati sanitari: come circoleranno le informazioni sulla salute nell’Unione Europea
Servizi digitali
PNRR e PA digitale: non dimentichiamo la dematerializzazione
Digital Healthcare transformation
La trasformazione digitale degli ospedali
Governance digitale
PA digitale, è la volta buona? Così misure e risorse del PNRR possono fare la differenza
Servizi digitali
Comuni e digitale, come usare il PNRR senza sbagliare
La survey
Pnrr e digitale accoppiata vincente per il 70% delle pmi italiane
Missione salute
Fascicolo Sanitario Elettronico alla prova del PNRR: limiti, rischi e opportunità
Servizi pubblici
PNRR: come diventeranno i siti dei comuni italiani grazie alle nuove risorse
Skill gap
PNRR, la banda ultra larga crea 20.000 nuovi posti di lavoro
Il Piano
Spazio, Colao fa il punto sul Pnrr: i progetti verso la milestone 2023
FORUMPA2022
PNRR e trasformazione digitale: rivedi i Talk di FORUM PA 2022 in collaborazione con le aziende partner
I contratti
Avio, 340 milioni dal Pnrr per i nuovi propulsori a metano
Next Generation EU
PNRR, a che punto siamo e cosa possono aspettarsi le aziende private
Fondi
Operativo il nuovo portale del MISE con tutti i finanziamenti per le imprese
Servizi comunali
Il PNRR occasione unica per i Comuni digitali: strumenti e risorse per enti e cittadini
Healthcare data platform
PNRR dalla teoria alla pratica: tecnologie e soluzioni per l’innovazione in Sanità
Skill
Competenze digitali, partono le Reti di facilitazione
Gli obiettivi
Scuola 4.0, PNRR ultima chance: ecco come cambierà il sistema formativo
Sistema Paese
PNRR 2, è il turno della space economy
FORUM PA 2022
FORUM PA 2022: la maturità digitale dei comuni italiani rispetto al PNRR
Analisi
PNRR: dalla Ricerca all’impresa, una sfida da cogliere insieme
Innovazione
Pnrr, il Dipartimento per la Trasformazione digitale si riorganizza
FORUM PA 2022
PA verde e sostenibile: il ruolo di PNRR, PNIEC, energy management e green public procurement
Analisi
PNRR, Comuni e digitalizzazione: tutto su fondi e opportunità, in meno di 3 minuti. Guarda il video!
Rapporti
Competenze digitali e servizi automatizzati pilastri del piano Inps
Analisi
Attuazione del PNRR: il dialogo necessario tra istituzioni e società civile. Rivedi lo Scenario di FORUM PA 2022
Progetti
Pnrr, fondi per il Politecnico di Torino. Fra i progetti anche IS4Aerospace
Analisi
PNRR, Colao fa il punto sulla transizione digitale dell’Italia: «In linea con tutte le scadenze»
La Svolta
Ict, Istat “riclassifica” i professionisti. Via anche al catalogo dati sul Pnrr
Analisi
Spazio, Colao fa il punto sul Pnrr: i progetti verso la milestone 2023
FORUM PA 2022
Ecosistema territoriale sostenibile: l’Emilia Romagna tra FESR e PNRR
Il Piano
Innovazione, il Mise “centra” gli obiettivi Pnrr: attivati 17,5 miliardi
Analisi
PNRR: raggiunti gli obiettivi per il primo semestre 2022. Il punto e qualche riflessione
Analisi
PNRR: dal dialogo tra PA e società civile passa il corretto monitoraggio dei risultati, tra collaborazione e identità dei luoghi
Webinar
Comuni e PNRR: un focus sui bandi attivi o in pubblicazione
Analisi
Formazione 4.0: cos’è e come funziona il credito d’imposta
PA e Sicurezza
PA e sicurezza informatica: il ruolo dei territori di fronte alle sfide della digitalizzazione
PA e sicurezza
PNRR e servizi pubblici digitali: sfide e opportunità per Comuni e Città metropolitane
Water management
Water management in Italia: verso una transizione “smart” e “circular” 
LE RISORSE
Transizione digitale, Simest apre i fondi Pnrr alle medie imprese
Prospettive
Turismo, cultura e digital: come spendere bene le risorse del PNRR
Analisi
Smart City: quale contributo alla transizione ecologica
Decarbonizzazione
Idrogeno verde, 450 milioni € di investimenti PNRR, Cingolani firma
Unioncamere
PNRR, imprese in ritardo: ecco come le Camere di commercio possono aiutare
I fondi
Industria 4.0: solo un’impresa su tre pronta a salire sul treno Pnrr
Formazione
Trasferimento tecnologico, il Mise mette sul piatto 7,5 milioni
Strategie
PSN e Strategia Cloud Italia: a che punto siamo e come supportare la PA in questo percorso
Dispersione idrica
Siccità: AI e analisi dei dati possono ridurre gli sprechi d’acqua. Ecco gli interventi necessari
PNRR
Cloud, firmato il contratto per l’avvio di lavori del Polo strategico
Formazione
Competenze digitali, stanziati 48 milioni per gli Istituti tecnologici superiori
Iniziative
Digitalizzazione delle reti idriche: oltre 600 milioni per 21 progetti
Competenze e competitività
PNRR, così i fondi UE possono rilanciare la ricerca e l’Università
Finanziamenti
PNRR, si sbloccano i fondi per l’agrisolare
Sanità post-pandemica
PNRR, Missione Salute: a che punto siamo e cosa resta da fare
Strategie
Sovranità e autonomia tecnologica nazionale: come avviare un processo virtuoso e sostenibile
La relazione
Pnrr e PA digitale, l’alert della Corte dei conti su execution e capacità di spesa
L'editoriale
Elezioni 2022, la sfida digitale ai margini del dibattito politico
Strategie
Digitale, il monito di I-Com: “Senza riforme Pnrr inefficace”
Transizione digitale
Pnrr: arrivano 321 milioni per cloud dei Comuni, spazio e mobilità innovativa
L'analisi I-COM
Il PNRR alla prova delle elezioni: come usare bene le risorse e centrare gli obiettivi digitali
Cineca
Quantum computing, una svolta per la ricerca: lo scenario europeo e i progetti in corso
L'indice europeo
Desi, l’Italia scala due posizioni grazie a fibra e 5G. Ma è (ancora) allarme competenze
L'approfondimento
PNRR 2, ecco tutte le misure per cittadini e imprese: portale sommerso, codice crisi d’impresa e sismabonus, cosa cambia
Servizi digitali
PNRR e trasformazione digitale: ecco gli investimenti e le riforme previste per la digitalizzazione della PA
Legal health
Lo spazio europeo dei dati sanitari: come circoleranno le informazioni sulla salute nell’Unione Europea
Servizi digitali
PNRR e PA digitale: non dimentichiamo la dematerializzazione
Digital Healthcare transformation
La trasformazione digitale degli ospedali
Governance digitale
PA digitale, è la volta buona? Così misure e risorse del PNRR possono fare la differenza
Servizi digitali
Comuni e digitale, come usare il PNRR senza sbagliare
La survey
Pnrr e digitale accoppiata vincente per il 70% delle pmi italiane
Missione salute
Fascicolo Sanitario Elettronico alla prova del PNRR: limiti, rischi e opportunità
Servizi pubblici
PNRR: come diventeranno i siti dei comuni italiani grazie alle nuove risorse
Skill gap
PNRR, la banda ultra larga crea 20.000 nuovi posti di lavoro
Il Piano
Spazio, Colao fa il punto sul Pnrr: i progetti verso la milestone 2023
FORUMPA2022
PNRR e trasformazione digitale: rivedi i Talk di FORUM PA 2022 in collaborazione con le aziende partner
I contratti
Avio, 340 milioni dal Pnrr per i nuovi propulsori a metano
Next Generation EU
PNRR, a che punto siamo e cosa possono aspettarsi le aziende private
Fondi
Operativo il nuovo portale del MISE con tutti i finanziamenti per le imprese
Servizi comunali
Il PNRR occasione unica per i Comuni digitali: strumenti e risorse per enti e cittadini
Healthcare data platform
PNRR dalla teoria alla pratica: tecnologie e soluzioni per l’innovazione in Sanità
Skill
Competenze digitali, partono le Reti di facilitazione
Gli obiettivi
Scuola 4.0, PNRR ultima chance: ecco come cambierà il sistema formativo
Sistema Paese
PNRR 2, è il turno della space economy
FORUM PA 2022
FORUM PA 2022: la maturità digitale dei comuni italiani rispetto al PNRR
Analisi
PNRR: dalla Ricerca all’impresa, una sfida da cogliere insieme
Innovazione
Pnrr, il Dipartimento per la Trasformazione digitale si riorganizza
FORUM PA 2022
PA verde e sostenibile: il ruolo di PNRR, PNIEC, energy management e green public procurement
Analisi
PNRR, Comuni e digitalizzazione: tutto su fondi e opportunità, in meno di 3 minuti. Guarda il video!
Rapporti
Competenze digitali e servizi automatizzati pilastri del piano Inps
Analisi
Attuazione del PNRR: il dialogo necessario tra istituzioni e società civile. Rivedi lo Scenario di FORUM PA 2022
Progetti
Pnrr, fondi per il Politecnico di Torino. Fra i progetti anche IS4Aerospace
Analisi
PNRR, Colao fa il punto sulla transizione digitale dell’Italia: «In linea con tutte le scadenze»
La Svolta
Ict, Istat “riclassifica” i professionisti. Via anche al catalogo dati sul Pnrr
Analisi
Spazio, Colao fa il punto sul Pnrr: i progetti verso la milestone 2023
FORUM PA 2022
Ecosistema territoriale sostenibile: l’Emilia Romagna tra FESR e PNRR
Il Piano
Innovazione, il Mise “centra” gli obiettivi Pnrr: attivati 17,5 miliardi
Analisi
PNRR: raggiunti gli obiettivi per il primo semestre 2022. Il punto e qualche riflessione
Analisi
PNRR: dal dialogo tra PA e società civile passa il corretto monitoraggio dei risultati, tra collaborazione e identità dei luoghi
Webinar
Comuni e PNRR: un focus sui bandi attivi o in pubblicazione
Analisi
Formazione 4.0: cos’è e come funziona il credito d’imposta
PA e Sicurezza
PA e sicurezza informatica: il ruolo dei territori di fronte alle sfide della digitalizzazione
PA e sicurezza
PNRR e servizi pubblici digitali: sfide e opportunità per Comuni e Città metropolitane
Water management
Water management in Italia: verso una transizione “smart” e “circular” 
LE RISORSE
Transizione digitale, Simest apre i fondi Pnrr alle medie imprese
Prospettive
Turismo, cultura e digital: come spendere bene le risorse del PNRR
Analisi
Smart City: quale contributo alla transizione ecologica
Decarbonizzazione
Idrogeno verde, 450 milioni € di investimenti PNRR, Cingolani firma
Unioncamere
PNRR, imprese in ritardo: ecco come le Camere di commercio possono aiutare
I fondi
Industria 4.0: solo un’impresa su tre pronta a salire sul treno Pnrr

Articoli correlati