¿Por qué mienten las computadoras? Del error de hardware al boicot

Tendemos a pensar en las computadoras como máquinas que no se equivocan. Si le pides a un procesador sano calcular $2 + 2$, la respuesta será $4$. El problema aparece cuando una réplica deja de ser sana o cuando lo que ejecuta no es exactamente lo que el diseñador del protocolo creía que ejecutaba.

"Mentir" es una palabra fuerte, pero útil. En un sistema replicado, una réplica miente cuando sus mensajes no corresponden a una ejecución correcta del protocolo: dice que votó algo que no votó, reporta un estado que no tiene o le cuenta una historia distinta a cada vecino. No hace falta malicia para eso. Basta un bug, un disco corrupto o una clave robada.

Tres formas de apartarse del protocolo

La literatura clásica de consenso ordena las fallas según cuánta libertad le dan a la réplica defectuosa. Dwork, Lynch y Stockmeyer analizan varios modelos en el mismo marco: procesos que se detienen (fail-stop), procesos que omiten enviar mensajes y procesos bizantinos, con o sin autenticación. [3] Conviene verlos como capas: cada modelo permite todo lo que permite el anterior y algo más.

Parada. La réplica funciona bien hasta un instante y después no hace nada más. Un corte de energía o un proceso que termina por una excepción no manejada encajan aquí. Lo importante es que nunca envía información falsa: si algo llegó de ella, era correcto.

Omisión. La réplica sigue ejecutando, pero algunos de sus mensajes no salen o se pierden. Un búfer lleno que descarta paquetes o un proceso que pierde un mensaje por un error de manejo son ejemplos razonables. Lo que sí envía sigue siendo correcto; el daño es el silencio intermitente, que para los demás se parece mucho a una red lenta.

Bizantina. La réplica puede hacer cualquier cosa: enviar valores inventados, contradecirse, coordinarse con otras réplicas defectuosas o callar en el peor momento. En el artículo de los generales bizantinos, los traidores no tienen ninguna restricción de comportamiento, y el objetivo del algoritmo es que los leales acuerden a pesar de ellos. [1]

Bugs y ataques producen el mismo síntoma

Es tentador asociar "bizantino" con "hacker". Pero el modelo no pregunta por la intención, solo por el comportamiento observable. Lamport, Shostak y Pease presentan el problema precisamente como una cuestión de sistemas confiables: componentes que funcionan mal y entregan información contradictoria a distintas partes del sistema. [1] Un chip defectuoso que corrompe un bit antes de enviar un mensaje no tiene malicia, pero para el receptor es indistinguible de un adversario.

Castro y Liskov motivan PBFT con el mismo diagnóstico desde la práctica: los ataques maliciosos y los errores de software son cada vez más comunes, y pueden hacer que un nodo defectuoso exhiba un comportamiento arbitrario. [2] Por eso su algoritmo no intenta clasificar qué tipo de error ocurrió: asume que hasta $f$ réplicas pueden comportarse de cualquier manera y garantiza el servicio mientras no se supere ese número. [2]

Hay una razón de ingeniería detrás de esta elección. Si el protocolo asume solo caídas, su corrección depende de que ninguna réplica emita jamás un mensaje incorrecto. Esa suposición se rompe con una actualización con errores, una configuración divergente entre nodos o una clave filtrada. Asumir fallas arbitrarias cuesta más réplicas y más mensajes, pero convierte la corrección en una propiedad que no depende de adivinar cómo va a fallar el sistema.

Tres generales: por qué la contradicción cuesta réplicas

El ejemplo más pequeño del artículo de 1982 muestra el costo de la contradicción. Hay un comandante y dos tenientes, y uno de los tres puede ser traidor. Los mensajes son "orales": el receptor sabe quién le habla, pero no puede probarle a nadie qué le dijeron. [1]

Primer escenario: el comandante es leal y ordena "atacar", pero el segundo teniente es traidor y le cuenta al primero que recibió "retirarse". Segundo escenario: el comandante es traidor, le dice "atacar" al primer teniente y "retirarse" al segundo, y el segundo teniente, leal, repite fielmente "retirarse". Desde el punto de vista del primer teniente, ambos escenarios son idénticos: escuchó "atacar" del comandante y "retirarse" del otro teniente.

En el primer escenario debe obedecer al comandante leal y atacar; como no distingue un caso del otro, también ataca en el segundo. Pero el mismo razonamiento, aplicado al segundo teniente del segundo escenario, lo lleva a retirarse. Los dos tenientes leales terminan en desacuerdo. Lamport, Shostak y Pease usan esta indistinguibilidad para mostrar que, con mensajes orales, tres generales no bastan para tolerar un traidor, y generalizan el resultado: hacen falta más de $3m$ generales para tolerar $m$ traidores. [1]

Con caídas, este dilema no aparece. Una réplica caída no dice "retirarse" a nadie; simplemente calla. El problema de las fallas bizantinas no es el silencio sino la presencia de dos versiones plausibles de la misma historia, y descartar una de ellas exige suficientes testigos correctos para superar a los que mienten.

Cuántas réplicas cuesta cada modelo

La pregunta "¿cuántas réplicas necesito?" no tiene una única respuesta: depende del modelo de fallas y del modelo de tiempo. Bajo sincronía parcial, que es el modelo de los protocolos de la familia HotStuff, Dwork, Lynch y Stockmeyer muestran que el consenso que tolera $f$ fallas por parada u omisión es posible si y solo si $n \ge 2f + 1$, y que para fallas bizantinas la cota es $n \ge 3f + 1$, tanto con autenticación como sin ella. [3]

Ese último matiz importa. Las firmas digitales impiden que una réplica falsifique mensajes de otra, pero no impiden que una réplica bizantina firme dos votos contradictorios ni que la red retrase a las réplicas correctas. En el modelo síncrono la historia es distinta: con mensajes firmados, el algoritmo de Lamport, Shostak y Pease funciona con cualquier número de generales. [1] Ese contraste se desarrolla en detalle más adelante en la serie.

PBFT es el ejemplo práctico del extremo bizantino: usa $n = 3f + 1$ réplicas, que es el mínimo para tolerar $f$ fallas arbitrarias en su modelo, y avanza cada fase cuando reúne $2f + 1$ mensajes coincidentes. [2] Con $f = 1$, eso significa cuatro réplicas, frente a las tres que bastarían si solo hubiera que tolerar una caída. La diferencia no es un margen de seguridad arbitrario: son las $f$ réplicas extra que permiten que cualquier par de quórums comparta una réplica correcta.

Criterios clave

Siguiente lectura

Para ver cómo esas cotas se convierten en quórums concretos, sigue con Consenso BFT desde cero y luego con Quórums en acción, donde se demuestra por qué dos quórums de $2f + 1$ votos siempre comparten una réplica correcta.