El Problema de los Generales Bizantinos estudia si los procesos correctos pueden acordar una decisión cuando los defectuosos actúan arbitrariamente y envían mensajes contradictorios a distintos destinatarios. La formulación de Lamport, Shostak y Pease de 1982 demuestra el límite de 3m+1 participantes para tolerar m traidores con mensajes orales sin firmas y presenta algoritmos recursivos para mensajes orales y firmados. Son resultados bajo supuestos precisos, no un sinónimo de todo consenso de cadenas de bloques.
Lamport, Shostak y Pease publicaron la alegoría en ACM TOPLAS en julio de 1982 para explicar la consistencia interactiva de sistemas replicados. Los generales separados deben elegir un plan mientras un traidor puede afirmar cosas distintas a destinatarios distintos. Un fallo bizantino es más fuerte que una caída: puede mentir, omitir, enviar valores contradictorios o parecer correcto solo a una parte del sistema. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
El artículo distingue IC1: todos los tenientes leales obedecen la misma orden, e IC2: si el comandante es leal, todos obedecen la orden que envió. En terminología moderna se relacionan con acuerdo o seguridad, validez y terminación o vivacidad. Ninguna garantía tiene sentido sin especificar modelo de red, autenticación y número máximo de fallos. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
Con mensajes orales se conoce al remitente directo, se detecta una ausencia y todos pueden comunicarse, pero el traidor puede enviar valores diferentes. OM(m) reenvía recursivamente los valores y aplica una mayoría determinista. Tolerar m procesos bizantinos exige al menos 3m+1 participantes: más de dos tercios leales. Con tres procesos, un receptor leal no distingue entre comandante mentiroso y compañero mentiroso. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]
Las firmas infalsificables revelan el envío de valores contradictorios e impiden alterar una orden firmada por un participante leal. El algoritmo reenvía valores firmados aún no vistos y decide sobre el conjunto recibido. Bajo las hipótesis ideales del artículo admite cualquier número de traidores. Pero una firma prueba origen, no verdad, entrega puntual ni honestidad de una clave comprometida; Dolev y Strong precisaron después las rondas necesarias. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]
Garantizar el progreso depende del tiempo. El resultado Fischer–Lynch–Paterson de 1985 muestra que un sistema determinista completamente asíncrono con mensajes, aun permitiendo la caída de un solo proceso, admite una ejecución donde el consenso nunca termina. FLP no afirma que los sistemas reales nunca acuerden. Garantizar vivacidad exige supuestos adicionales, como límites temporales posteriores o un detector de fallos con propiedades precisas, o cambiar a un protocolo aleatorio. Nombrar un líder no basta. Durante una partición larga, un protocolo seguro puede dejar de completar operaciones. [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
PBFT de Miguel Castro y Barbara Liskov (1999) aplica acuerdo bizantino a una máquina de estados replicada. Con la configuración básica n = 3f+1 tolera f réplicas bizantinas. Estar preparado incluye un pre-prepare de la réplica primaria y 2f mensajes prepare coincidentes; el compromiso local exige estar preparado y 2f+1 mensajes commit coincidentes. Las intersecciones de quórums y las reglas de cambio de vista impiden compromisos contradictorios. Autenticación, secuencias, puntos de control y cambios de vista gestionan falsificación, repetición, crecimiento del registro y líder defectuoso. Miembros conocidos y finalidad determinista difieren de una red abierta Proof of Work. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]
Bitcoin no ejecuta OM ni PBFT y no cuenta nodos identificados. Proof of Work, resistente a identidades Sybil, pondera historias por trabajo acumulado; cada Full Node rechaza independientemente los bloques que violan el consenso y sigue la cadena válida con más trabajo. Se esperan bifurcaciones temporales. Bajo supuestos de mayoría de trabajo honesta y comunicación, la probabilidad de sustitución disminuye con la profundidad, sin irreversibilidad matemática. Bitcoin Backbone formaliza prefijo común, crecimiento y calidad con supuestos explícitos sobre trabajo adversario y red. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]
Decir que Bitcoin resolvió el problema oculta un cambio de modelo. El acuerdo clásico parte de un grupo fijo con identidades conocidas y límite f; Bitcoin admite participantes seudónimos cambiantes y un recurso externo escaso. Sus garantías aún requieren supuestos concretos de entrega. Proof of Work limita identidades Sybil, pero no impide ataques eclipse, censura, minería egoísta, errores de software o reorganizaciones con mayoría de potencia de cálculo. El modelo debe precisar adversario, tiempo, miembros y finalidad; la etiqueta BFT no basta. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
Para obtener la imagen más completa, lee esta entrada junto con Consenso de Nakamoto, Proof of Work, Reglas de consenso, Doble gasto, Bitcoin, Finalidad probabilística.