Problema de los generales bizantinos

En 1982 Leslie Lamport, Robert Shostak y Marshall Pease^[4] proporcionaron distintos algoritmos de solución en función de condiciones adicionales.

La estrategia se basa, con el fin de detectar si el comandante es el traidor, en que los tenientes se reenvíen entre sí la información que el comandante les ha mandado. Si el teniente es leal la información que transmitirá el teniente será la que le envió el comandante. La consecuencia de usar mensajes orales (no firmados) es que un general traidor puede decir que el comandante le ha mandado cierta información cuando no es así.

Analicemos el caso en el que tenemos tres generales (m=3).

• Supongamos que el comandante es un traidor. Si el comandante envía una orden distinta a cada teniente entonces habrá un teniente que no sepa qué acción realizar:

• Supongamos que un teniente es el traidor. Entonces este retransmite al otro teniente información distinta a la que recibió del comandante. Por tanto el otro teniente no sabrá qué acción realizar:

La conclusión es que no existe solución que garantice que se cumplan las condiciones del problema si se permite que con tres generales uno sea un traidor. Esto se debe a que no hay suficientes generales para formar una opinión consensuada.

Si tuviéramos 4 generales (m=4) sí sería posible el acuerdo a través del siguiente algoritmo:

Al recibir la orden del comandante y los mensajes de los otros 2 tenientes, los tenientes leales decidirán la orden de consenso según la siguiente función de mayoría:

${\displaystyle M(v_{1},v_{2},v_{3}):}$ Devolver el valor de v que sea mayoría entre ${\displaystyle v_{1},v_{2},v_{3}}$.

Donde el valor de ${\displaystyle v_{i}}$ es la orden mandada desde los distintos generales al general al que estamos evaluando su decisión.

Veamos el esquema si el comandante es leal y un teniente es traidor:

Veamos el esquema si el comandante es traidor y los tenientes leales:

Generalizando a m generales se puede decir que si tenemos t traidores necesitamos que m sea al menos 3t+1. Al algoritmo generalizado se le llama OM(m) (donde las siglas OM vienen del inglés Oral Messages) y viene descrito por usar la siguiente función de mayoría:

${\displaystyle M(v_{1},v_{2},\ldots ,v_{n}):}$ Devolver el valor de v que sea mayoría entre ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$

Donde el valor de ${\displaystyle v_{i}}$ es la orden mandada desde los distintos generales al general al que estamos evaluando su decisión.

En este escenario los mensajes van firmados (se trata de mensajes escritos). Al ir firmados no son modificables y por tanto los traidores no pueden modificarlos y decir que provienen del comandante. En esta situación es posible resolver el problema con sólo tres generales y uno de ellos traidor. El algoritmo de este tipo de problemas se llama SM(m) (donde SM viene del inglés Signed Messages) y es el siguiente:

Primero el comandante envía una orden firmada a todos los tenientes. Cada vez que un teniente recibe un mensaje firmado lo guarda, hace una copia, la firma y la reenvía a todos los tenientes que no venían en la firma del documento. Según este algoritmo los generales no recibirán más mensajes cuando tengan todas las posibles combinaciones. Una vez recibidas, cada nodo toma la decisión basándose en la orden transmitida por la mayoría.

En este escenario los comandantes traidores son descubiertos inmediatamente ya que han firmado órdenes contradictorias.

Si falta alguno de los caminos de comunicación las cosas se complican. Veamos los requerimientos tanto cuando hay mensajes orales como mensajes firmados.

• Con mensaje orales el algoritmo OM(m) solo funciona bajo la condición de que el grafo de caminos posibles entre generales sea 3m-regular (cada nodo tiene al menos 3m vecinos), lo que implica 3m+1 nodos (generales). A esta versión del algoritmo se le llama OM(m,p), donde p es el número de vecinos.
• Para mensajes firmados la única condición es que todos los generales leales estén conectados, para que así los traidores no puedan bloquearle y evitar que le pasen o pase la orden firmada.

• El problema de los generales bizantinos es el mismo que se tiene cuando se realiza una transmisión de dinero sin un intermediario confiable.^[1] Bitcoin ofreció la primera solución práctica a este problema.
• En el mundo real las líneas fallan de forma no deliberada. Para detectarlas se pueden usar códigos de detección de errores. En un escenario con mensajes orales, una línea que falla puede considerarse como un nodo traidor. Si se utilizan mensajes firmados entonces un fallo en una línea se detectaría de forma irrefutable.
• Para reconocer al emisor de un mensaje empleando mensajes orales, se deberían tener líneas fijas y no redes de comunicaciones. Con mensajes firmados no hay problema para reconocer al emisor.
• La ausencia de mensajes se suele detectar usando time-out (límites de tiempo).
• En el mundo real nunca está garantizado que un error aleatorio no pueda falsear una firma. Sin embargo esto tiene una probabilidad muy baja con métodos de firma adecuados.
• Evitar fraudes deliberados se convierte en un problema criptográfico. Por tanto es importante elegir algoritmos de firma seguros.
• Se debe detectar si un mensaje se envía dos veces, mediante la comprobación de su firma. De tal modo que una firma no puede ser generada si el proceso ya ha visto esa misma firma en otro instante.