Problema de los Generales Bizantinos

Un sistema informático fiable debe ser capaz de hacer frente al fallo de uno o varios de sus componentes. Un componente averiado puede mostrar un tipo de comportamiento que a menudo se pasa por alto: enviar información contradictoria a distintas partes del sistema. El problema de hacer frente a este tipo de fallo se expresa de forma abstracta como el Problema de los Generales Bizantinos - The Byzantine Generals Problem, Leslie Lamport et. al 1982

Lo que fundamentalmente resuelven los protocolos de consenso es el problema de los generales bizantinos, en el que tenemos un grupo de actores divididos entre los que hay traidores, y que solo se pueden comunicar via mensajes para decidir un plan de acción.

Este es un problema sumamente complejo en sistemas distribuidos, y su solución fue clave para la invención de Bitcoin y todas las cadenas nacidas después. Al final del día la visión que mi nodo tiene de la red esta limitada a los mensajes que envía y recibe de una cantidad limitada de peers, que pueden ser mensajes correctos o erróneos y malintencionados, y aún así tiene que ser capaz de acabar con la misma versión del estado de la cadena que el resto de los nodos.

Si bien es verdad que la visión de la cadena de un nodo siempre difiere de los demás de alguna forma (ya sea por que recibes los bloques antes o después que otros, o en un orden diferente, etc), hay que prestarle especial atención a los generales traidores, que intentan evitar que los leales lleguen a un acuerdo. Para esto hay que conseguir un algoritmo que asegure que:

A. Todos los generales leales toman el mismo plan de acción (ej. "atacar" o "retractarse"), y

B. Un número pequeño de traidores no pueden conseguir que los generales leales tomen un mal plan.

Algunos de los protocolos de consenso que consiguen estas propiedades son:

• Practical Byzantine Fault Tolerance (PBFT) por Miguel Castro y Barbara Liskov en 1999. PBFT usa un set pequeño y limitado de participantes en el consenso a los que llaman replicas; se considera como un protocolo seguro (describiremos seguridad en el contexto de consenso más adelante), y no tiene forks.

• Nakamoto Consensus, por Satoshi Nakamoto en 2008. No limita el set de validadores, pero usa Proof of Work para seleccionar un líder temporal; este protocolo si se forkea y no es formalmente "seguro".

• Tendermint por Jae Kwon en 2014. Similar a PBFT, Tendermint utiliza un set limitado de validadores activos que se encargan de producir nuevos bloques; ofrece finalidad instantánea y no tiene forks siempre y cuando menos de 1/3 de los validadores tengan problemas. CometBFT es la implementación de Tendermint usada por la gran mayoría de cadenas en el ecosistema de Cosmos.

• Gasper por Vitalik Buterin et. al en 2020. Como el de Nakamoto, no limita el set de validadores pero usa Proof of Stake para evitar sybiles y escoge un líder temporal de forma aleatoria; si se forkea y es formalmente seguro.