Byzantine Generals Problem

Imagina varias unidades alrededor de una ciudad. Deben atacar juntas o retirarse juntas; actuar por separado podría resultar desastroso. El comandante envía órdenes, pero alguien puede traicionar al grupo y contar versiones diferentes. ¿Cómo consiguen los participantes fiables actuar de la misma manera? No es el relato de una batalla real, sino un ejemplo para entender ordenadores que necesitan registros coherentes. Por ejemplo, varios servidores, los ordenadores que prestan un servicio compartido, deben decidir de forma consistente si un pago ya se ha procesado. Recibir alguna respuesta no basta: esas respuestas deben encajar en una decisión común. [1] [9]

Leslie Lamport, Robert Shostak y Marshall Pease presentaron la formulación conocida en julio de 1982, después de su trabajo de 1980 sobre el acuerdo ante fallos. El traidor representa un componente cuyo comportamiento ya no podemos prever. Un ordenador no tiene por qué limitarse a detenerse: puede contestar correctamente a un vecino e incorrectamente a otro, omitir mensajes o afirmar que ha visto otra cosa. Puede deberse a un ataque o a un error de software. Un fallo bizantino describe lo que observan los demás, no la intención del dispositivo. BFT (Byzantine Fault Tolerance), tolerancia a fallos bizantinos, designa la capacidad de soportar ese comportamiento bajo condiciones definidas. [1] [2]

El problema original impone dos condiciones. IC1 exige que todos los subordinados fiables acepten la misma orden. IC2 añade que, si el comandante también es fiable, deben aceptar la orden que realmente envió. Sin esta segunda condición, «retirarse siempre» parecería resolverlo, aunque ignoraría a un comandante honesto. En informática se distingue la seguridad, que impide resultados incompatibles, de la vivacidad, que permite llegar a un resultado. Otras reglas determinan qué resultados son válidos. Un registro coherente no demuestra por sí solo que una afirmación introducida fuera cierta en el mundo exterior. [1] [9]

Llamemos A al comandante y B y C a sus subordinados. C recibe de A la orden de atacar, pero B le dice que el comandante ordenó retirarse. ¿Miente B o envió A una orden distinta a cada uno? Sin una firma verificable después de reenviar el mensaje, C puede no distinguir ambas situaciones. B puede encontrarse con la misma incertidumbre. Obedecer siempre al comandante permite que un A deshonesto los divida; ignorarlo siempre incumple la condición para un comandante honesto. En este problema con tres participantes y un posible traidor no existe un procedimiento sin firmas que funcione siempre. Faltan datos que permitan distinguir los casos, no ordenadores más rápidos. [1] [9]

En el modelo clásico sin firmas, tolerar m posibles traidores requiere al menos n ≥ 3m+1 participantes: cuatro para uno. Aquí n es el número total de participantes y m, el máximo de traidores que se pretende tolerar. No basta con añadir un voto y contar la mayoría una vez. OM(m) hace que los participantes transmitan repetidamente lo que han oído y evalúen los mensajes con reglas comunes; el caso base OM(0) adopta el valor del comandante o uno predeterminado. El modelo supone participantes conocidos, conexiones directas, entrega correcta de los mensajes enviados, conocimiento del remitente inmediato y capacidad para detectar mensajes ausentes. «Sin firmas» no significa, por tanto, «sin ninguna autenticación del origen». Sin estos supuestos, el número cuatro no garantiza nada. [1] [9]

Con una firma digital verificable, Digital Signature, B puede demostrar a C qué firmó realmente el comandante. Un programa crea la firma con una clave privada, un valor numérico secreto. Los demás la comprueban con la clave pública correspondiente, sin necesidad de conocer la privada. Un traidor no puede alterar sin dejar rastro la orden de un participante fiable ni imitar su firma. El algoritmo de mensajes firmados difunde valores firmados y aplica una regla común de selección. Este modelo elimina el requisito anterior de mayoría honesta, pero conserva los supuestos sobre firmas infalsificables, entrega y tiempos de las rondas. Dolev y Strong estudiaron en 1983 el número de rondas necesario. Una firma válida tampoco garantiza un contenido verdadero ni una entrega puntual, y no demuestra que la clave privada no haya sido robada. Acredita el origen de un mensaje concreto, no la fiabilidad general del remitente. [1] [3]

Cuando un servidor no responde, los demás no saben si se ha detenido o si su conexión es muy lenta. El resultado FLP, publicado en 1985 por Michael Fischer, Nancy Lynch y Michael Paterson, precisa esta incertidumbre. Un proceso es aquí un programa en ejecución. Un procedimiento determinista da el mismo siguiente paso ante el mismo estado y la misma entrada; no lo elige al azar. En un sistema totalmente asíncrono, sin un límite superior conocido para los retrasos, un procedimiento determinista no puede garantizar que el acuerdo termine en todas las ejecuciones admisibles si incluso un solo proceso puede detenerse por un fallo. Esto vale aun con entrega fiable y retrasos sin cota. No significa que el acuerdo nunca llegue. Los sistemas prácticos añaden supuestos temporales, un detector de fallos adecuado o aleatoriedad. Ante una partición de red, esperar puede ser más seguro que confirmar resultados incompatibles. [4] [13] [8]

Miguel Castro y Barbara Liskov describieron en 1999 Practical Byzantine Fault Tolerance, PBFT, para un servicio ejecutado en varias réplicas conocidas. Estas réplicas son copias del servicio que funcionan en distintos servidores y procesan continuamente las mismas solicitudes. No son archivos de copia de seguridad guardados para más tarde. La configuración básica n = 3f+1 tolera f réplicas defectuosas. Con cuatro servidores, uno puede ser bizantino; dos grupos de tres comparten al menos dos servidores y al menos uno debe ser fiable. Ese conjunto requerido de aprobaciones se llama cuórum. La intersección no basta: también cuentan las fases del protocolo y los cambios de líder. En concreto, el estado prepared requiere la solicitud, un mensaje pre-prepare y 2f mensajes prepare coincidentes de réplicas distintas que no sean la principal. La confirmación local necesita además 2f+1 mensajes commit, posiblemente incluido el propio. Autenticación, números de secuencia y puntos de control combaten falsificaciones, repeticiones y crecimiento ilimitado del registro. La seguridad no depende de límites temporales, pero el progreso necesita condiciones adicionales sobre los retrasos. [5] [10] [11] [12]

Bitcoin no tiene una lista cerrada de servidores fijada de antemano. Si cada cuenta nueva tuviera un voto, un atacante podría fabricar una mayoría: eso es un Sybil Attack. Proof of Work vincula la producción de bloques al trabajo computacional. Un bloque es un lote de transacciones que se añade al historial compartido. Un Full Node, un ordenador con software que comprueba las reglas por sí mismo, primero descarta bloques inválidos y después sigue la rama válida con más trabajo acumulado. Bitcoin no ejecuta OM ni PBFT; las bifurcaciones temporales forman parte de su funcionamiento. Con suficiente potencia honesta y unas condiciones de comunicación adecuadas, más confirmaciones reducen el riesgo de reescribir la historia, pero no crean irreversibilidad absoluta. Bitcoin Backbone estudia esas condiciones: la coincidencia entre historiales, el crecimiento de la cadena y la proporción de bloques que pueden producir participantes honestos. [6] [7]

Ante la afirmación «la red alcanza consenso», conviene buscar respuestas concretas: quién puede participar, qué controla el atacante, cuánto pueden tardar los mensajes y cuándo puede cambiar una decisión. Ni siquiera Proof of Work elimina todos los problemas. Un Eclipse Attack aísla un nodo de interlocutores honestos, la censura excluye transacciones y Selfish Mining utiliza la retención de bloques minados. También quedan los errores de software y la posibilidad de reescribir parte del historial con suficiente potencia atacante. Aun así, ni una mayoría de potencia puede obligar a un Full Node que funciona correctamente a aceptar un bloque contrario a sus reglas. La historia enseña a examinar las condiciones del acuerdo, en lugar de confiar en el nombre de una tecnología. [6] [7] [8]