Vai al contenuto
Financial Context Wiki

Problema dei generali bizantini: accordo con messaggi incompatibili

Il problema chiede come possano concordare i partecipanti onesti quando quelli guasti inviano informazioni incompatibili. Compito, canali, autenticazione, limite dei guasti, soglia, algoritmo e installazione vanno distinti.

Aggiornato

Solo a scopo educativo; non costituisce consulenza né raccomandazione d’investimento. Gli investimenti possono comportare perdite.

Risposta diretta

Il problema dei generali bizantini chiede come partecipanti non guasti che comunicano tramite messaggi possano prendere una decisione coerente quando alcuni agiscono arbitrariamente, anche inviando affermazioni diverse a destinatari diversi. La storia militare è un’analogia della coerenza interattiva nei sistemi distribuiti, non un evento storico né uno specifico algoritmo di consenso blockchain.

Nella formulazione comandante-luogotenenti, IC1 richiede che tutti i luogotenenti leali eseguano lo stesso ordine, mentre IC2 richiede che eseguano l’ordine del comandante quando è leale. Il solo accordo non basta: scegliere sempre RITIRATA crea accordo, ma viola un valido ordine di ATTACCO di un comandante leale.

Nel modello dei “messaggi orali” dell’articolo, con al massimo m traditori esiste una soluzione solo quando n>3m, equivalente per partecipanti interi a n>=3m+1. Il modello presume che i messaggi inviati dai leali siano consegnati correttamente, il destinatario conosca il mittente e l’assenza di un messaggio atteso sia rilevabile. “Orale” significa che contenuto non autenticato può essere falsificato come resoconto altrui, non che un messaggero possa sparire per sempre senza rilevazione.

Il modello dei “messaggi firmati” aggiunge firme non falsificabili e verificabili pubblicamente, cambiando il risultato di resilienza. Non rende vero il contenuto, non garantisce consegna o terminazione interamente asincrona, non protegge chiavi rubate né prova un protocollo moderno. Problema bizantino, due generali o attacco coordinato, FLP, BFT, Proof of Work e Proof of Stake sono modelli o costruzioni correlati ma distinti.

Come analizzarlo

  1. Definire il compito di accordo. Indicare partecipanti, input, output e proprietà esatte di accordo, validità e terminazione. Nella forma col comandante, scrivere IC1 e IC2 invece di dire soltanto “raggiungere il consenso”.
  2. Definire identità e canali. Indicare autenticazione, consegna affidabile, ordine, protezione dal replay e attribuzione dei messaggi; rilevabilità dell’omissione; broadcast come primitiva o invii ripetuti.
  3. Definire i tempi. Separare sincronia con ritardo limitato, sincronia parziale dopo stabilizzazione ignota e piena asincronia. Non aggiungere messaggeri scomparsi a un modello conservando un teorema di un altro.
  4. Definire il budget dei guasti. Registrare partecipanti totali n, massimo bizantino m, corruzione statica o adattiva e inclusione di omissione, equivocazione, collusione, furto di chiavi o canali guasti.
  5. Seguire ricorsivamente le informazioni. Per ogni leale elencare affermazioni dirette e inoltrate, percorsi dei mittenti, valore per assenza e parità deterministica; confrontare le esecuzioni distinguibili dalle viste locali.
  6. Controllare insieme teorema e algoritmo. Collegare limiti e sufficienza al preciso modello orale o firmato, connettività e budget. Una disuguaglianza non è implementazione né prova.
  7. Mappare sull’installazione. Verificare OM(m), SM(m) o altro meccanismo reale, domini, turni, blocchi, certificati, cambi dei membri, scadenze, client, finalità e politica di conferma.

La tecnica centrale è l’indistinguibilità. Un leale vede soltanto messaggi locali; se due esecuzioni appaiono uguali ma la validità richiede decisioni diverse, nessuna regola deterministica può scegliere sempre bene. I protocolli aggiungono partecipanti indipendenti, prove autenticate, ipotesi temporali, casualità o altra struttura per distinguere le esecuzioni necessarie o cambiare la garanzia.

Esempi calcolati

1. Perché tre generali con messaggi orali non tollerano un traditore

Siano n=3 e m=1. La condizione n>3m diventa 3>3, falsa. Il comandante A dica ATTACK a B e RETREAT a C. B non distingue se A è traditore e ha inviato ordini incompatibili o se C è traditore e mente su A; C affronta l’incertezza simmetrica.

Qualsiasi scelta deterministica che preservi l’ordine di A nelle esecuzioni in cui A è leale può obbligare B e C a decidere diversamente quando A è traditore. L’inoltro non crea una quarta fonte indipendente, quindi IC1 e IC2 non sono garantibili insieme.

2. Quattro generali con messaggi orali e un traditore

In OM(1), n=4 e m=1. Il comandante invia a tre luogotenenti; ciascuno inoltra il valore agli altri due; ogni leale usa la stessa maggioranza e lo stesso valore predefinito. Se il comandante è leale e invia v, un leale vede v, v e un possibile x del traditore, scegliendo v.

Se il comandante è l’unico traditore, i tre luogotenenti sono leali e inoltrano esattamente quanto ricevuto. Ricostruiscono lo stesso insieme di affermazioni del comandante e applicano la stessa regola. Non recuperano necessariamente la sua “vera intenzione”, ma soddisfano l’accordo.

3. Limite generale dei messaggi orali

Con n=7 e m=2, 7>6 vale, quindi il conteggio soddisfa la condizione e la costruzione ricorsiva tollera due traditori sotto le altre ipotesi. Per n=6, 6>6 è falso. Per n=10 e m=3, 10>9 vale. La disuguaglianza è necessaria; servono anche turni, inoltro, maggioranza, valori predefiniti e canali corretti.

4. Cosa cambiano le firme

In un esempio con tre generali SM(1), il comandante traditore firma ATTACK per B e RETREAT per C. I leali inoltrano entrambe, ricevono lo stesso insieme {ATTACK, RETREAT} e usano lo stesso valore specificato, per esempio RETREAT. L’equivocazione è attribuibile.

Nel modello, le firme impediscono falsificazione o modifica non rilevata dell’ordine di un leale. Non rivelano la “vera intenzione” del traditore, non garantiscono consegna puntuale e non impediscono a chi controlla una chiave legittima di firmare entrambi.

Rischi ed errori di verifica

Problema e modello

  • Ripetere l’allegoria senza condizioni precise di accordo, validità e terminazione.
  • Trattare il problema come assedio storico, singolo algoritmo o sinonimo di blockchain.
  • Confonderlo con i due generali, incentrato sulla conoscenza comune attraverso un canale inaffidabile.
  • Aggiungere perdita permanente non rilevabile e citare un teorema orale che la esclude.
  • Applicare n>3m a ogni protocollo autenticato, asincrono, ponderato, senza permessi o basato su risorse.
  • Equiparare arresto, omissione, equivocazione, calcolo arbitrario, canale guasto e chiave compromessa.
  • Presumere che partecipanti equivalgano a entità indipendenti, stake, potenza o peso di comitato.
  • Omettere la differenza fra comandante leale e traditore nella validità.

Algoritmo e implementazione

  • Guardare solo la maggioranza finale senza seguire percorsi ricorsivi e ogni vista locale.
  • Usare valori per assenza, parità, fotografie dei membri o ordini diversi tra implementazioni.
  • Accettare messaggi non legati a protocollo, catena, compito, altezza, turno, valore, mittente ed epoca.
  • Riprodurre o unire messaggi tra esecuzioni, turni, biforcazioni, reti o cambi dei membri.
  • Presumere che le firme provino verità, attualità, contesto autorizzativo, consegna, disponibilità o custodia onesta.
  • Citare OM(m) o SM(m) senza implementare turni, inoltro, verifica e connettività richiesti.
  • Provare una sola posizione del traditore e non comandante, luogotenente, collusione, omissione ed equivocazione.

Installazione e interpretazione

  • Affermare che un consenso “risolve Bisanzio” senza precise ipotesi di sicurezza, vitalità e rete.
  • Trattare l’accordo sui byte come prova di esecuzione o fatto esterno corretto.
  • Ignorare guasti correlati per client, operatori, cloud, sistemi di chiavi o governance comuni.
  • Accreditare depositi, coniare criptoattività tramite bridge o regolare azioni irreversibili prima della finalità richiesta.
  • Dedurre decentralizzazione, sicurezza delle attività, verità giuridica o valore del token da un’etichetta di tolleranza.

Idee sbagliate comuni

  • Il problema è solo un attacco del 51%. Tratta condotta arbitraria e incompatibile in un modello di accordo; le maggioranze di risorse appartengono a protocolli specifici.
  • Una maggioranza lo risolve sempre. Nel modello orale classico, tollerare m traditori richiede oltre tre volte quel numero di partecipanti totali, non solo un leale in più.
  • Le firme digitali dimostrano che il messaggio è vero. Autenticano la chiave e proteggono l’integrità; una chiave malevola o compromessa firma contenuti falsi o incompatibili.
  • Il risultato orale originale copre già la consegna inaffidabile. Include ipotesi esplicite di consegna, identità e omissione rilevabile; altri modelli richiedono altri risultati.
  • Accordo significa conoscere la realtà. Senza convalida separata, nodi leali possono concordare un output non valido o un dato esterno errato.

Argomenti correlati

Fonti

Navigazione

Cerca nella wiki...