La semana pasada cubrimos los preliminares técnicos para comprender el consenso en profundidad. Esta semana, daremos una descripción general de alto nivel del algoritmo de consenso PBFT (Practical Byzantine Fault Tolerant). Si bien consideramos que los protocolos más nuevos, incluido PaLa, son una actualización estricta sobre PBFT, comprender PBFT sigue siendo crucial. Muchas de las terminologías e ideas detrás de los protocolos de consenso clásicos más nuevos provienen de este protocolo.
Utilizamos PBFT como una herramienta de aprendizaje a partir de la cual estableceremos el lenguaje y las ideas sobre las que se construirán los protocolos PaLa y Thunderella. No cubrimos otros protocolos de consenso clásicos seminales como los protocolos de compromiso de 3 fases y Paxos que emplean ideas similares. Finalmente, tenga en cuenta que el protocolo de consenso presentado aquí está ligeramente modificado para ser aplicable para el consenso de .
Fuente: Tolerancia práctica a fallas bizantinas, OSDI, 1999
El algoritmo se modela como una máquina de estado en un sistema distribuido que se replica en diferentes réplicas, entre las cuales una de las réplicas es la principal y el resto son copias de seguridad.
En un nivel muy alto, PBFT consta de los siguientes pasos en la operación de caso normal:
Solicitud: el usuario envía transacciones a la primaria. Preparación previa: la primaria produce una propuesta que contiene transacciones y la reenvía a todas las réplicas. Preparación: al recibir una propuesta, las copias de seguridad la verificarán y, si tiene éxito, transmitirán el mensaje de preparación a Todas las demás réplicas. Las copias de seguridad no hacen nada si la verificación falla. Esta es la primera ronda de votación. Comprometerse: Al recibir mensajes de preparación de ⅔ de todas las copias de seguridad, las réplicas ahora transmitirán mensajes de confirmación. Esta es la segunda ronda de votación. Respuesta: el cliente ve el resultado del consenso.
En la mayoría de las circunstancias, se cumplen los requisitos de operación de caso normal y el primario puede procesar rápidamente nuevas transacciones. Dado que solo ⅔ de las copias de seguridad deben estar de acuerdo en la fase de preparación y confirmación, PBFT ya puede tolerar hasta ⅓ de las copias de seguridad en marcha o incluso actuando de forma bizantina. Pero, ¿qué pasa si la primaria baja?
Si el primario ha fallado, se realizará una subrutina llamada cambio de vista. En un nivel alto, el El protocolo view-change proporciona vitalidad al permitir que el sistema designe un nuevo primario cuando el primero falla. Cuando las réplicas no ven un nuevo progreso después de un tiempo, transmiten un mensaje de cambio de vista que indica que desean avanzar a la siguiente vista. El cambio de vista comienza cuando se recopilan los mensajes de cambio de vista de ⅔ de todas las réplicas.
Durante un cambio de vista, las réplicas pueden no estar de acuerdo con el último estado de consenso: recuerde que la primaria fue responsable de liderar el consenso hasta ahora. Dado que estamos en la configuración de red parcialmente sincrónica, no podemos garantizar que todas las réplicas vean un voto de mayoría in en la primera ronda si existe. Una réplica que ve un voto de mayoría ⅔ a favor de una propuesta en la primera ronda no puede asumir que otros también la han visto y, por lo tanto, no hay acuerdo.
Afortunadamente, PBFT requirió 2 rondas de votación donde las réplicas no votan en la segunda ronda hasta que hayan visto los resultados de la primera ronda. Por lo tanto, al ver vote mayoría de votos en la segunda ronda, la réplica se garantiza que al menos ⅔ de las réplicas han visto resultados de la primera ronda. Este conocimiento sobre el conocimiento reemplaza el supuesto de sincronía donde se supone simplemente que los nodos han visto un mensaje (una ronda de votos en este caso) después de que haya pasado un cierto tiempo.
Con este mecanismo, la nueva primaria puede continuar desde la última propuesta que recibió ⅔ voto mayoritario en la segunda ronda. Los mensajes de cambio de vista también incluyen la última propuesta que una copia de seguridad ha visto ⅔ voto mayoritario en la primera ronda. Suponiendo que menos de ⅓ nodos son bizantinos, se puede demostrar que si alguien ha visto un voto de mayoría in en la segunda vuelta, debe haber al menos 1 respaldo honesto que haya transmitido con éxito un mensaje de cambio de vista que indique que ha visto vote voto mayoritario en la primera ronda para esa propuesta. La prueba es solo una aplicación del principio del casillero, sin embargo, el razonamiento es más complejo y se describe en detalle en 4.5.1 del documento PBFT.
PBFT es un protocolo de consenso clásico seminal que emplea 2 rondas de votación para la finalidad. Está en la red parcialmente síncrona y logra la tolerancia óptima a fallas optimal. Comprender a un alto nivel cómo 2 rondas de votación permiten cambios de vista seguros es la base de todos los protocolos de consenso clásicos. Los detalles de PBFT no son tan importantes y pronto veremos cómo PaLa es una mejora estricta sobre el protocolo PBFT.
PBFT es un algoritmo de mensajes pesados. Hay 3 rondas de mensajes y cada mensaje debe enviarse a todas las demás réplicas. Por lo tanto, tiene una sobrecarga de mensajes O (n2) donde n es el número de réplicas.
PBFT emplea el enfoque de consenso basado en la vista, donde cada vista es dirigida por un líder principal que se encarga de crear nuevas propuestas. El enfoque basado en la boleta electoral se basa en el protocolo de consenso de Paxos y se utiliza en los protocolos del Acuerdo Bizantino Federado (FBA), como el Protocolo de consenso estelar (SCP). En el enfoque basado en la votación, no hay un líder explícito. En cambio, cualquiera puede compartir una propuesta para un espacio y, después del consenso, el valor final para ese espacio se crea a partir de todas las propuestas acordadas (por ejemplo, la unión de todas las transacciones de todos los bloques propuestos). Este enfoque evita los problemas de censura de tener un solo nodo responsable de crear nuevas propuestas a corto plazo. El enfoque basado en la votación aún emplea dos rondas de votación para finalizar una decisión. Como ThunderCore prioriza el desempeño de los enfoques basados en la vista, no entramos en detalles del enfoque basado en la boleta. Para obtener más información sobre FBA y el enfoque basado en la boleta, consulte el documento SCP y el documento histórico atemporal de Paxos.