Tolerancia práctica a fallas bizantinas (pBFT)

La tolerancia práctica a fallas bizantinas es un algoritmo de consenso introducido a finales de los 90 por Barbara Liskov y Miguel Castro. pBFT fue diseñado para funcionar de manera eficiente en sistemas asincrónicos (sin límite superior sobre cuándo se recibirá la respuesta a la solicitud). Está optimizado para un bajo tiempo de sobrecarga. Su objetivo era resolver muchos problemas asociados con las soluciones de tolerancia a fallas bizantinas ya disponibles. Las áreas de aplicación incluyen computación distribuida y blockchain.

¿Qué es la tolerancia a fallas bizantinas?
La tolerancia a fallas bizantinas (BFT) es la característica de una red distribuida para llegar a un consenso (acuerdo sobre el mismo valor) incluso cuando algunos de los Nodes de la red no responden o responden con información incorrecta. El objetivo de un mecanismo BFT es protegerse contra las fallas del sistema empleando la toma de decisiones colectiva (Nodes correctos y defectuosos) cuyo objetivo es reducir la influencia de los Nodes defectuosos. BFT se deriva del problema de los generales bizantinos.

El problema de los generales bizantinos
El problema se explicó adecuadamente en un artículo de LESLIE LAMPORT, ROBERT SHOSTAK y MARSHALL PEASE en Microsoft Research en 1982:

Imagine que varias divisiones del ejército bizantino están acampadas fuera de una ciudad enemiga, cada división comandada por su propio general. Los generales pueden comunicarse entre sí solo por mensajero. Después de observar al enemigo, deben decidir un plan de acción común. Sin embargo, algunos de los generales pueden ser traidores, tratando de evitar que los generales leales lleguen a un acuerdo. Los generales deben decidir cuándo atacar la ciudad, pero necesitan una gran mayoría de su ejército para atacar al mismo tiempo. Los generales deben tener un algoritmo para garantizar que (a) todos los generales leales decidan sobre el mismo plan de acción, y (b) un pequeño número de traidores no puede hacer que los generales leales adopten un mal plan. Todos los generales leales harán lo que el algoritmo diga que deben hacer, pero los traidores pueden hacer lo que quieran. El algoritmo debe garantizar la condición (a) independientemente de lo que hagan los traidores. Los generales leales no solo deben llegar a un acuerdo, sino que deben ponerse de acuerdo sobre un plan razonable.

La tolerancia a fallas bizantinas se puede lograr si los Nodes que funcionan correctamente en la red llegan a un acuerdo sobre sus valores. Puede haber un valor de voto predeterminado otorgado a los mensajes que faltan, es decir, podemos suponer que el mensaje de un Node en particular es ‘defectuoso’ si el mensaje no se recibe dentro de un límite de tiempo determinado. Además, también podemos asignar una respuesta predeterminada si la mayoría de los Nodes responden con un valor correcto.

Leslie Lamport demostró que si tenemos 3m+1 procesadores funcionando correctamente, se puede llegar a un consenso (acuerdo sobre el mismo estado) si al menos m procesadores están defectuosos, lo que significa que estrictamente más de dos tercios del número total de procesadores deberían ser honestos.

Tipos de fallas bizantinas:
Hay dos categorías de fallas que se consideran. Una es la detención por falla (en la que el Node falla y deja de funcionar) y la otra es la falla de un Node arbitrario. Algunas de las fallas de Nodes arbitrarios se dan a continuación:

• No devolver un resultado
• Responder con un resultado incorrecto
• Responder con un resultado deliberadamente engañoso
• Responder con un resultado diferente a diferentes partes del sistema

Ventajas de pbft:

• Eficiencia energética : pBFT puede lograr un consenso distribuido sin realizar cálculos matemáticos complejos (como en PoW). Zilliqa emplea pBFT en combinación con cálculos complejos similares a PoW para cada bloque número 100.
• Finalidad de la transacción : las transacciones no requieren confirmaciones múltiples (como en el caso del mecanismo PoW en Bitcoin, donde cada Node verifica individualmente todas las transacciones antes de agregar el nuevo bloque a la string de bloques; las confirmaciones pueden demorar entre 10 y 60 minutos dependiendo de cuántas entidades confirmen el nuevo bloque) una vez finalizados y acordados.
• Variación de recompensa baja : cada Node de la red participa en la respuesta a la solicitud del cliente y, por lo tanto, cada Node puede ser incentivado, lo que lleva a una variación baja en la recompensa de los Nodes que ayudan en la toma de decisiones.

¿Cómo funciona pBFT?
pBFT intenta proporcionar una replicación de máquina de estado bizantina práctica que puede funcionar incluso cuando Nodes maliciosos están operando en el sistema.
Los Nodes en un sistema distribuido habilitado para pBFT se ordenan secuencialmente, siendo un Node el principal (o el Node líder) y otros denominados secundarios (o los Nodes de respaldo). Tenga en cuenta aquí que cualquier Node elegible en el sistema puede convertirse en el principal mediante la transición de secundario a principal (normalmente, en el caso de una falla del Node principal). El objetivo es que todos los Nodes honestos ayuden a llegar a un consenso sobre el estado del sistema utilizando la regla de la mayoría.
Un sistema tolerante a fallas bizantinas práctico puede funcionar con la condición de que el número máximo de Nodes maliciosos no sea mayor o igual a un tercio de todos los Nodes del sistema. A medida que aumenta el número de Nodes, el sistema se vuelve más seguro.

Las rondas de consenso de pBFT se dividen en 4 fases (consulte la imagen a continuación):

• El cliente envía una solicitud al Node principal (líder).
• El Node principal (líder) transmite la solicitud a todos los Nodes secundarios (respaldo).
• Los Nodes (primario y secundario) realizan el servicio solicitado y luego envían una respuesta al cliente.
• La solicitud se atiende con éxito cuando el cliente recibe respuestas ‘m+1’ de diferentes Nodes en la red con el mismo resultado, donde m es el número máximo de Nodes defectuosos permitidos.


El Node primario (líder) se cambia durante cada vista (rondas de consenso de pBFT) y se puede sustituir por un protocolo de cambio de vista si ha pasado una cantidad de tiempo predefinida sin que el Node líder transmita una solicitud a las copias de seguridad (secundarias). Si es necesario, la mayoría de los Nodes honestos pueden votar sobre la legitimidad del Node líder actual y reemplazarlo con el siguiente Node líder en línea.

Limitaciones de pBFT:
el modelo de consenso pBFT funciona de manera eficiente solo cuando la cantidad de Nodes en la red distribuida es pequeña debido a la alta sobrecarga de comunicación que aumenta exponencialmente con cada Node adicional en la red.

• Ataques Sybil : Los mecanismos pBFT son susceptibles a los ataques Sybil , donde una entidad (parte) controla muchas identidades. A medida que aumenta el número de Nodes en la red, los ataques sybil se vuelven cada vez más difíciles de llevar a cabo. Pero como los mecanismos pBFT también tienen problemas de escalabilidad, el mecanismo pBFT se usa en combinación con otros mecanismos.
• Escalado : pBFT no se escala bien debido a su sobrecarga de comunicación (con todos los demás Nodes en cada paso). A medida que aumenta el número de Nodes en la red (aumenta como O(n^k), donde n son los mensajes yk es el número de Nodes), también aumenta el tiempo necesario para responder a la solicitud.

 
Plataformas que utilizan variantes de pBFT:

• Zilliqa – pBFT en combinación con consenso PoW
• Hyperledger Fabric: versión autorizada de pBFT
• Tendermint – pBFT + DPoS (prueba de participación delegada)

 
Variaciones de pBFT:
para mejorar la calidad y el rendimiento de pBFT para casos de uso y condiciones específicos, se propusieron y emplearon muchas variaciones. Algunos de ellos son :

• RBFT – BFT redundante
• RESUMENES
• P/U
• HQ: protocolo de quórum híbrido para BFT
• Adaptar
• Zyzzyva: tolerancia especulativa a fallas bizantinas
• Cerdo hormiguero