El abuelo de los consensos BFT: PBFT (1999) y sus tres pasos

En De PBFT a cadenas trazamos la línea evolutiva del consenso BFT. Para entender qué cambió HotStuff en 2019, primero hay que estudiar al protocolo sobre cuyos hombros se construyó esa línea: PBFT (Practical Byzantine Fault Tolerance), presentado por Miguel Castro y Barbara Liskov en OSDI 1999. [1]

Antes de PBFT, buena parte de la literatura bizantina se apoyaba en sincronía o se consideraba demasiado costosa para un servicio real. La contribución de Castro y Liskov fue un algoritmo de replicación de máquinas de estados (SMR) que es seguro en un sistema asíncrono, que tolera réplicas bizantinas y que incorpora optimizaciones suficientes para que el costo frente a un servicio no replicado fuera moderado en su evaluación. [1] Este capítulo reconstruye el mecanismo, sus invariantes y el precio que pagó por ellos.

Modelo de fallas: por qué n = 3f + 1

PBFT supone $n$ réplicas, de las cuales a lo sumo $f$ pueden ser bizantinas: pueden mentir, callar, enviar mensajes distintos a distintos pares o coludirse. La red puede perder, retrasar, duplicar o reordenar mensajes. Lo único que el adversario no puede hacer es romper la criptografía: no puede falsificar la autenticación de una réplica correcta ni encontrar colisiones del digest. [1]

Con ese adversario, el protocolo usa $n = 3f + 1$ réplicas y quórums de tamaño $q = 2f + 1$. El argumento es aritmético. Una réplica solo puede esperar respuesta de $n - f$ pares, porque $f$ pueden no contestar nunca; pero entre los que sí contestan puede haber hasta $f$ bizantinos. Para que las respuestas correctas superen a las maliciosas hace falta $n - 2f > f$, es decir, $n > 3f$. Con $n = 3f + 1$, dos quórums cualesquiera de $2f + 1$ se intersecan en al menos $f + 1$ réplicas, y al menos una de ellas es correcta.

El umbral de un tercio tiene una genealogía clara. Lamport, Shostak y Pease mostraron que, con mensajes orales, el problema de los generales bizantinos no tiene solución si un tercio o más de los generales son traidores. [2] PBFT trabaja en un modelo distinto, asíncrono y con mensajes autenticados, pero conserva esa resiliencia óptima de $n = 3f + 1$. [1]

Hay una segunda frontera igual de importante: FLP. Ningún protocolo determinista puede garantizar terminación en un sistema completamente asíncrono con una sola falla. [3] Castro y Liskov lo asumen explícitamente: safety no depende de sincronía, pero liveness requiere una hipótesis débil de sincronía, en la que los retardos no crezcan indefinidamente más rápido que el tiempo. [1]

El camino normal: vistas, primario y número de secuencia

PBFT organiza la ejecución en vistas. En cada vista $v$ existe un único líder, el primario, determinado como $p = v \bmod n$; el resto de las réplicas actúan como respaldos. En este artículo usamos $s$ para el número de secuencia y reservamos $n$ para el número de réplicas; el paper original usa $n$ para la secuencia y $|R|$ para el conjunto de réplicas. [1]

Cuando un cliente envía una solicitud $m$ al primario, se desencadenan tres fases de mensajes:

La escena sigue esas fases con $n = 4$ y la réplica R3 en falla, contando los mensajes de cada una.

1. Fase Pre-Prepare

El primario calcula el digest $d = D(m)$, asigna un número de secuencia $s$ y envía a todas las réplicas:

$\langle\text{PRE-PREPARE}, v, s, d\rangle_{\sigma_p}$

Una réplica acepta el mensaje si la autenticación del primario es válida, si está en la vista $v$, si no aceptó antes otro Pre-Prepare para la misma vista y secuencia con un digest distinto, y si $s$ cae entre dos marcas de agua, $h$ y $H$, que impiden que un primario malicioso agote el espacio de secuencias. [1]

2. Fase Prepare

Al aceptar el Pre-Prepare, la réplica $i$ difunde a todas las demás:

$\langle\text{PREPARE}, v, s, d, i\rangle_{\sigma_i}$

Cuando reúne el Pre-Prepare más $2f$ mensajes Prepare coincidentes de réplicas distintas, alcanza el predicado $\text{Prepared}(m, v, s)$. Ese conjunto de mensajes es el certificado preparado.

3. Fase Commit

Estar Prepared no basta para ejecutar. La réplica sabe que existe un orden acordado dentro de la vista $v$, pero no sabe si ese conocimiento sobreviviría a un cambio de primario. Por eso difunde:

$\langle\text{COMMIT}, v, s, d, i\rangle_{\sigma_i}$

Cuando está Prepared y acepta $2f + 1$ mensajes Commit coincidentes, alcanza $\text{Committed-Local}(m, v, s)$ y ejecuta $m$ una vez ejecutadas todas las solicitudes con secuencia menor. Después responde al cliente, que acepta el resultado al recibir $f + 1$ respuestas idénticas de réplicas distintas: al menos una de ellas proviene de una réplica correcta. [1]

Un detalle de implementación: la notación $\sigma$ sugiere firmas, y así se presenta el algoritmo para simplificar. En el sistema original, los mensajes del camino normal se autentican con vectores de MACs, llamados authenticators, y las firmas de clave pública se reservan para el cambio de vista, porque un MAC es mucho más barato de calcular que una firma. [1]

Qué certifica cada quórum

Las dos fases de votación no son redundantes: cada una protege un invariante distinto.

Prepare ordena dentro de una vista. Si una réplica correcta está $\text{Prepared}(m, v, s)$ y otra réplica correcta está $\text{Prepared}(m', v, s)$, entonces $D(m) = D(m')$. Ambos certificados contienen $2f + 1$ réplicas que avalaron el par $(v, s)$; sus conjuntos se intersecan en al menos una réplica correcta, y una réplica correcta nunca acepta dos Pre-Prepare distintos para la misma vista y secuencia. [1]

Commit hace que el orden sobreviva al cambio de vista. Si una réplica correcta está $\text{Committed-Local}(m, v, s)$, entonces al menos $f + 1$ réplicas correctas están $\text{Prepared}(m, v, s)$. Ese conjunto es lo bastante grande como para que cualquier quórum futuro de $2f + 1$ réplicas contenga al menos una que conserve el certificado preparado. Es la propiedad que permite que la decisión sea final sin esperar a que todas las réplicas la conozcan.

Sin la fase Commit, una réplica podría ejecutar tras ver su certificado preparado mientras casi nadie más lo tiene; un cambio de vista en ese momento podría elegir otro valor para la misma secuencia. La segunda ronda de votos convierte un conocimiento local en un hecho que el siguiente primario está obligado a descubrir.

El cambio de vista: transportar certificados preparados

Si el primario falla o actúa de forma maliciosa, los respaldos lo detectan con temporizadores: una réplica que tiene una solicitud pendiente y no la ve ejecutada a tiempo deja de aceptar mensajes de la vista $v$ y difunde un mensaje VIEW-CHANGE para la vista $v + 1$. [1]

Ese mensaje es la memoria de la réplica. Incluye el número de secuencia de su último checkpoint estable con la prueba correspondiente, y un conjunto con el certificado preparado de cada solicitud que alcanzó Prepared con secuencia posterior a ese checkpoint. Cada certificado, a su vez, contiene un Pre-Prepare y $2f$ mensajes Prepare.

El primario de la vista $v + 1$ espera $2f$ mensajes VIEW-CHANGE válidos de otras réplicas, que junto con el suyo forman un quórum de $2f + 1$, y difunde un mensaje NEW-VIEW. Ese mensaje contiene los VIEW-CHANGE recibidos y un conjunto de nuevos Pre-Prepare: para cada secuencia en la que algún VIEW-CHANGE trae un certificado preparado, el nuevo primario vuelve a proponer el digest del certificado de vista más alta; para los huecos, propone una solicitud nula. Las réplicas no confían en esa reconstrucción: la recalculan a partir de los mismos VIEW-CHANGE y rechazan el NEW-VIEW si no coincide. [1]

Aquí se cierra el argumento de seguridad. Si $m$ quedó Committed-Local en alguna réplica correcta, al menos $f + 1$ réplicas correctas guardan su certificado; el quórum del NEW-VIEW interseca ese conjunto, así que el nuevo primario no puede omitir $m$ sin que las réplicas lo detecten.

Los checkpoints completan el cuadro. Periódicamente las réplicas difunden un digest de su estado; con $2f + 1$ mensajes coincidentes el checkpoint se vuelve estable, pueden descartar los mensajes anteriores y avanzar las marcas de agua $h$ y $H$. Sin ellos, los registros y los mensajes de cambio de vista crecerían sin límite. [1]

El talón de Aquiles: intercambios todos contra todos

Observa el patrón de comunicación. En Prepare y en Commit, cada réplica difunde a todas las demás, de modo que cada fase cuesta del orden de $n^2$ mensajes:

$\text{mensajes por fase} = \mathcal{O}(n^2)$

Con $n = 4$ réplicas ($f = 1$), cada fase cuesta como mucho $n(n - 1) = 12$ mensajes. Con $n = 1000$, la misma fórmula da del orden de un millón de mensajes por fase. La aritmética no depende de la implementación: es consecuencia de que cada réplica necesita escuchar directamente a un quórum.

El cambio de vista es todavía más pesado. Cada réplica difunde su VIEW-CHANGE a todas, lo que vuelve a dar $\mathcal{O}(n^2)$ mensajes, y cada uno transporta certificados preparados que contienen a su vez $2f + 1$ mensajes; el NEW-VIEW reenvía $2f + 1$ de esos VIEW-CHANGE. El tamaño total de la evidencia crece más rápido que el número de réplicas.

Esa es la deuda que HotStuff se propuso saldar. Su camino feliz usa un líder que agrega votos en un certificado de quórum (QC) compacto, y su cambio de líder evita reenviar los certificados de todas las réplicas, de modo que el costo de comunicación por vista con líder correcto es lineal en $n$. [4] El precio es una fase adicional de votación respecto a las dos de PBFT, una decisión que se analiza en QC, highQC y la regla de tres cadenas y en View-change y pacemaker en HotStuff.

Siguiente lectura

Continúa con PBFT, Tendermint y Streamlet para ver cómo las familias posteriores reorganizaron estas fases, o salta a Tendermint: locks vistos desde HotStuff para comparar el certificado preparado con un lock.