Byzantine Generals Problem: Proof of Work, The Solution

Traduzione dall’originale su Bitcoin Magazine - pubblicato il 27 set 2023

Nota del traduttore : nel testo sottostante la sigla PdGB e/o le parole “il problema” identificano la locuzione Problema dei Generali Bizantini.

Introduzione

Il Problema dei Generali Bizantini è un problema di teoria dei giochi che rivela le difficoltà di raggiungere il consenso tra un gruppo di entità reciprocamente sospettose che utilizzano canali di comunicazione inaffidabili. La teoria dei giochi si riferisce alla migliore strategia adottata da attori indipendenti e in competizione nel processo decisionale.

Questo articolo esplora il concetto di PdGB, le sue basi, il modo in cui si applica ai sistemi in rete e al denaro e il modo in cui la combinazione di diversi elementi di Bitcoin consente di ottenere il consenso migliore per risolvere il problema.

Il PdGB è particolarmente sentito nell'informatica distribuita, dove è più difficile per le parti decentralizzate raggiungere un consenso senza affidarsi a una parte centrale fidata.

L'analogia della teoria dei giochi si basa su un gruppo di generali che assediano Bisanzio, con ogni generale responsabile di una divisione dell'esercito. Devono coordinarsi per attaccare la città o ritirarsi; se il coordinamento riesce, tutti i generali attaccano simultaneamente e vincono, ma se non sono coordinati, perdono.

Come possono i generali coordinarsi per attaccare simultaneamente se devono affidarsi a messaggeri che possono essere intercettati o corrotti dai difensori di Bisanzio?

Devono progettare un protocollo che permetta ai generali fedeli di raggiungere un solido consenso per combattere i generali disonesti di Bisanzio.

Sistemi centralizzati e decentralizzati

Il PdGB non si verifica nei sistemi centralizzati, perché le decisioni sono sempre prese dalle autorità centrali coinvolte nel processo decisionale dell'organizzazione.

Pertanto, la sfida consiste nel garantire l'affidabilità e l'integrità della comunicazione tra l'autorità e le entità subordinate, piuttosto che raggiungere il consenso tra più parti indipendenti, come nel caso dei sistemi distribuiti. In questi sistemi, i messaggi o i comandi inviati dall'autorità non devono essere manomessi o alterati maliziosamente durante la trasmissione.

Il PdGB è comune solo ai sistemi decentralizzati, dove raggiungere un accordo è più difficile. La rete deve essere progettata con canali di comunicazione sicuri, in modo che nessun servizio di messaggistica venga intercettato o interrotto per evitare il successo di un attacco.

Contesto storico

L'influenza dell'Impero Bizantino

Sebbene il termine "Problema dei Generali Bizantini" non sia direttamente collegato allo storico Impero Bizantino, alcuni parallelismi e potenziali influenze possono aver portato all'origine del concetto.

La tolleranza bizantina ai guasti, a cui si fa riferimento nell'informatica distribuita, implica la capacità di un sistema di tollerare componenti difettosi o dannosi. In questo contesto, il termine "bizantino" si ispira alle sfide storiche dell'Impero Bizantino nel coordinare le azioni e le comunicazioni tra i suoi generali, alcuni dei quali potevano essere traditori o inaffidabili.

Inoltre, l'Impero bizantino aveva una struttura altamente gerarchica con un processo decisionale decentralizzato, in cui vari generali e comandanti erano responsabili della guida dei rispettivi eserciti. Allo stesso modo, i nodi o le entità dei sistemi distribuiti possono avere capacità decisionali indipendenti e il raggiungimento del consenso tra loro pone sfide paragonabili al coordinamento delle azioni tra più generali bizantini.

Il parallelo con l'impero bizantino nel problema in oggetto fornisce un quadro simbolico per comprendere le difficoltà incontrate nel raggiungere il consenso e la tolleranza ai guasti nei sistemi distribuiti. Le complesse dinamiche decisionali e il potenziale di comportamento malevolo che si riscontrano nelle storiche campagne militari bizantine rappresentano le sfide che l'informatica distribuita deve affrontare.

L'origine del Problema dei Generali Bizantini

Il termine Byzantine Generals Problem è stato introdotto per la prima volta dagli informatici Leslie Lamport, Robert Shostak e Marshall Pease in un articolo pubblicato nel 1982.

La National Aeronautics and Space Administration, il Ballistic Missile Defense Systems Command e l'Army Research Office hanno in parte sostenuto la ricerca. Questi finanziamenti sottolineano l'importanza della questione e il fatto che il concetto può essere applicato alle comunicazioni militari, oltre che a tutti i tipi di sistemi informatici.

Nell'informatica moderna, il PdGB deve essere risolto se un gruppo disperso di nodi (ad esempio, computer o altri dispositivi fisici) deve ottenere comunicazioni affidabili.

Analogie con l'informatica moderna

Il problema riguarda principalmente l'informatica distribuita, in quanto il raggiungimento del consenso in una rete in cui i nodi possono essere difettosi o maligni rappresenta una sfida. Ha applicazioni in vari settori, tra cui i sistemi fault-tolerant, i database distribuiti e la tecnologia blockchain. Il problema ha sollecitato lo sviluppo di protocolli e algoritmi di consenso a tolleranza di errore bizantina, che sono fondamentali per garantire l'affidabilità e la coerenza dei sistemi distribuiti.

Nei sistemi blockchain, il PdGB è affrontato nei protocolli di consenso come il proof of work (PoW) per raggiungere un accordo tra più nodi in un ambiente privo di fiducia. La tolleranza bizantina ai guasti rappresenta una caratteristica essenziale delle reti blockchain decentralizzate.

Nell'ambito della sicurezza informatica e del rilevamento delle intrusioni, l'analogia con tale problema aiuta a comprendere le sfide della sicurezza delle reti informatiche contro gli attori malintenzionati che possono tentare di interrompere le comunicazioni, manomettere i dati o lanciare attacchi, e aiuta a identificare e mitigare queste potenziali minacce.

Il PdGB trova applicazione nelle reti dell'Internet delle cose (IoT), dove numerosi dispositivi devono comunicare e cooperare per svolgere le proprie attività. Garantire il consenso e il coordinamento tra i dispositivi IoT, soprattutto in presenza di nodi inaffidabili o compromessi, è fondamentale per mantenere l'integrità e la sicurezza dei sistemi IoT.

E’ essenziale anche nel cloud computing per garantire l'affidabilità e la tolleranza ai guasti negli ambienti cloud distribuiti. I protocolli di tolleranza bizantina ai guasti possono gestire guasti e comportamenti dannosi all'interno dei sistemi di cloud computing.

Algoritmi di tolleranza bizantina ai guasti

Per garantire che un piccolo gruppo di attori maligni non possa interrompere un sistema distribuito, è necessario un algoritmo che fornisca la soluzione. Ne sono stati sviluppati diversi, come i protocolli di consenso con tolleranza bizantina ai guasti, per consentire un'elaborazione distribuita affidabile in grado di gestirne i relativi problemi.

Practical Byzantine Fault Tolerance (PBFT):

E’ un algoritmo di consenso nei sistemi distribuiti che tollera fino a un terzo del numero totale di nodi bizantini, ovvero che possono esibire un comportamento arbitrario e potenzialmente dannoso senza influenzare la rete.

L'algoritmo garantisce che il sistema raggiunga un accordo sull'ordine delle richieste nel minor tempo possibile e mantiene la coerenza anche in caso di guasti bizantini. Utilizzando una combinazione di firme digitali, timeout e riconoscimenti, PBFT garantisce che il processo di consenso proceda anche se alcuni nodi sono difettosi o maligni e che il sistema possa continuare a progredire finché la maggioranza dei nodi è onesta.

Federated Byzantine Agreement (FBA):

E’ un altro algoritmo di consenso nei sistemi distribuiti, progettato per una rete decentralizzata di nodi che possono raggiungere il consenso senza fare affidamento su un'autorità centralizzata.

FBA si basa sulla federazione di nodi indipendenti in gruppi (federazioni). Ogni federazione consiste in un insieme di nodi che si fidano reciprocamente. L'algoritmo garantisce che i nodi all'interno di una federazione siano d'accordo sull'ordine e sulla validità delle transazioni o degli eventi, consentendo alle diverse federazioni di avere processi di consenso separati. Fedimint è la federazione più conosciuta e il protocollo open source per transare e custodire bitcoin, e utilizza l'algoritmo di consenso honey badger Byzantine fault-tolerant (HBBFT).

La soluzione di Bitcoin: Proof-Of-Work:

Il meccanismo di consenso PoW (proof of work) di Bitcoin non è tecnicamente un algoritmo a tolleranza d'errore bizantina, ma viene comunque utilizzato per rendere Bitcoin a tolleranza d'errore bizantina. I nodi della rete non possono dichiarare valido un blocco a meno che non contenga un hash proof-of-work, che indica che è stato fatto del lavoro per produrlo.

La tolleranza bizantina ai guasti richiede di tollerare un certo numero di nodi difettosi o maligni nella rete mentre si raggiunge il consenso. Il meccanismo di consenso PoW di Bitcoin offre una finalità probabilistica, il che significa che più lunga diventa la blockchain, più difficile diventa per un avversario eseguire un attacco e riscrivere o alterare la storia.

Confronto tra gli algoritmi BFT:

Sono disponibili diversi algoritmi di Byzantine fault-tolerant (BFT), ciascuno con le proprie caratteristiche, i propri compromessi e l'idoneità a diversi casi d'uso.

La scelta di un algoritmo BFT dipende da fattori quali le prestazioni, la tolleranza ai guasti, la scalabilità, la finalità delle transazioni, le caratteristiche della rete e i presupposti di fiducia che si adattano alle diverse blockchain, dalle reti permissioned o permissionless ai database distribuiti o ai file system.

Byzantine Generals Problem nelle reti di computer

Le ragioni per cui un sistema informatico distribuito potrebbe avere inevitabili guasti bizantini sono molteplici e non sempre si tratta di attacchi maligni coordinati. Da un difetto del software a un malfunzionamento dell'hardware, i nodi possono presentare diverse difficoltà che impediscono loro di raggiungere un consenso sulle reti distribuite.

Le reti ragionevolmente sicure sono in grado di sopportare alcuni nodi offline o maligni senza compromettere l'intera rete, e la tolleranza bizantina ai guasti è la capacità di gestire tali condizioni. Nel 2008 il white paper di Bitcoin proponeva una soluzione al problema dei generali bizantini dell'informatica:

"Una versione puramente peer-to-peer del denaro elettronico consentirebbe di inviare pagamenti online direttamente da una parte all'altra senza passare attraverso un'istituzione finanziaria", affermava Satoshi Nakamoto nel documento.

Egli ha creato un sistema monetario globale che per la prima volta nella storia poteva essere privo di fiducia, programmato per disincentivare i comportamenti scorretti e incoraggiare invece i nodi e i minatori ad agire onestamente.

Il denaro e il Problema dei Generali Bizantini

L'analogia con il PdGB può essere estesa al denaro e alle transazioni finanziarie, in particolare nel contesto delle valute digitali decentralizzate come il bitcoin.

Come si possono eseguire transazioni finanziarie in un ambiente sicuro e privo di fiducia senza la necessità di un'autorità centrale che verifichi e finalizzi il trasferimento di valore, anche in presenza di un comportamento bizantino?

Per risolvere il PdGB, il denaro deve essere completamente privo di fiducia. Pertanto, deve essere verificabile, sicuro, trasparente, decentralizzato e resistente alla contraffazione. Bitcoin è stato progettato con questi attributi come principi fondamentali e ha portato a una soluzione innovativa al PdGB.

La soluzione di Bitcoin

• Blockchain risolve il problema della doppia spesa

Bitcoin gestisce la proprietà degli utenti e previene la doppia spesa in modo privo di fiducia utilizzando una blockchain, il libro mastro pubblico e distribuito, che memorizza la storia di tutte le transazioni e la verità che tutte le parti (i nodi) devono approvare per risolvere il PdGB.

La doppia spesa si riferisce alla possibilità di spendere la stessa unità di moneta digitale più di una volta, il che comprometterebbe l'integrità e il valore della moneta.

Questa rete di nodi è necessaria per verificare la proprietà dei bitcoin attraverso meccanismi di consenso e tecniche crittografiche (come le firme digitali), risolvendo il problema della doppia spesa senza un'autorità centrale.

I protocolli di consenso a tolleranza bizantina di errore nei sistemi blockchain aiutano a prevenire la doppia spesa stabilendo un accordo sull'ordine e la validità delle transazioni. La fiducia è riposta nel protocollo sottostante e nel consenso di rete piuttosto che in un intermediario centrale.

• La prova di lavoro (PoW) risolve il PdGB

La prova di lavoro richiede molta energia, lavoro e spese per produrre un nuovo blocco. La prova di lavoro computazionale aiuta a proteggere la rete dagli attacchi sibillini, garantendo che l'aggiunta di nuovi blocchi alla catena richieda molte risorse e costi.

I membri della rete che pubblicano informazioni false vengono immediatamente individuati da tutti i nodi che le riconoscono come non valide e le ignorano. Bitcoin è un sistema privo di fiducia, poiché ogni nodo può verificare tutte le informazioni sulla rete senza doversi fidare degli altri membri della rete.

Conclusione

Poiché la società si muove sempre più verso sistemi distribuiti e adotta denaro decentralizzato come il bitcoin, l'approccio al PdGB diventa essenziale per coordinare le azioni di più parti indipendenti senza affidarsi ad autorità centrali.

Per avere successo, i sistemi devono assicurare la tolleranza bizantina ai guasti e garantire la resilienza e la sicurezza - anche in presenza di informazioni errate - in modo da poter raggiungere un consenso nonostante la possibilità di inganno e tradimento da parte di alcuni soggetti.

Bitcoin è ideale per fornire un ambiente privo di fiducia per gestire gli attacchi. Il suo algoritmo proof-of-work ha protetto la sicurezza della rete promuovendo la competizione tra i minatori, rendendo computazionalmente impossibile il controllo della rete da parte di una singola entità. La natura decentralizzata di Bitcoin, sostenuta dalla tolleranza bizantina agli errori, mostra un modello robusto per garantire il consenso e la sicurezza in mezzo a potenziali disinformazioni e intenti malevoli.

Come acquistare Bitcoin?

Personalmente, reputo il miglior servizio quello offerto da Relai.

Per acquistare bitcoin risparmiando lo 0,5% in commissioni puoi usare il codice “REL3166”.

Si tratta di un’applicazione sviluppata da un’azienda svizzera che applica una politica di KYC light: a differenza dei grandi exchange non richiede registrazioni o dati personali, tutto ciò che serve per acquistare è il tuo IBAN.

E’ lo strumento ottimale per impostare dei piani di accumulo (DCA).

Per ridurre al massimo le commissioni di acquisto, ti consiglio di:

• effettuare acquisti maggiori di 100€ (-0,5%)
• impostare un piano di accumulo settimanale o mensile (-0,5%)
• applicare il codice invito REL3166 (-0,5%)

Una delle migliori caratteristiche è il servizio non-custodial. Gli euro bonificati a Relai vengono convertiti automaticamente in bitcoin e trasferiti su un wallet di cui sei solo tu ad avere il controllo. I grossi exchange, al contrario, non forniscono le chiavi private ai clienti. In più Relai non vende centinaia di inutili criptovalute, ma solo bitcoin.

Cosa ci guadagno? Quello che fanno guadagnare i referral code. In questo caso se acquisti usando il codice “REL3166” risparmi lo 0,5% sulle commissioni e io ricevo (in bitcoin) lo 0,5% dell’importo che hai deciso di investire.

Per ulteriori informazioni, o per effettuare il primo acquisto, premi sul pulsante sottostante e ti verrà mostrata una dettagliata guida in italiano.

NOTA - Questo NON è un messaggio pubblicitario. Relai è un servizio che utilizzo personalmente e che reputo tra i migliori sul mercato in termini di affidabilità, sicurezza e facilità d’uso. Lo consiglio spesso ad amici e parenti.