La pesadilla del View-Change cuadrático en PBFT: Por qué cambiar de líder apaga la red

Un protocolo BFT no se juzga solo por cómo funciona cuando todo va bien, sino por cómo sobrevive cuando el líder cae o se vuelve malicioso. En PBFT, ese momento lo gobierna el protocolo de view change: las réplicas abandonan la vista $v$, eligen al primario de la vista $v+1$ y reconstruyen el estado de las solicitudes que estaban a medio camino. [1]

Es en ese mecanismo donde PBFT paga su mayor costo de comunicación. No porque el diseño sea descuidado, sino porque la seguridad entre vistas se sostiene con expedientes completos de evidencia en lugar de con un certificado compacto y portable. Vamos a ver qué viaja, cuánto pesa y por qué HotStuff decidió reorganizar el problema.

Qué protege el cambio de vista en PBFT

En el camino normal, una solicitud pasa por pre-prepare, prepare y commit. Una réplica considera una solicitud prepared cuando tiene el pre-prepare del primario y $2f$ prepares coincidentes de otras réplicas para la misma vista, número de secuencia y digest. [1]

El problema aparece si el primario falla justo después de que alguna réplica correcta ejecutó una solicitud. Esa ejecución ocurrió porque un quórum de $2f + 1$ réplicas la tenía preparada. El nuevo primario no puede ignorar esa historia: si asignara otro contenido al mismo número de secuencia, dos réplicas correctas ejecutarían operaciones distintas en la misma posición del log.

Por eso el cambio de vista tiene una sola obligación de safety: toda solicitud que pudo comprometerse en la vista anterior debe reaparecer con el mismo número de secuencia en la vista nueva. La pregunta es cómo demostrarlo sin confiar en la palabra del nuevo primario, que también podría ser bizantino. [1]

La respuesta de PBFT es transparente y costosa: cada réplica entrega su evidencia, y el nuevo primario reenvía esa evidencia para que todos puedan auditar su decisión.

Anatomía del mensaje VIEW-CHANGE

Cuando el temporizador de una réplica expira mientras espera ejecutar una solicitud, la réplica deja de participar en la vista $v$ y multidifunde a todas las réplicas un mensaje firmado: [1]

$\langle\text{VIEW-CHANGE}, v+1, n, C, P, i\rangle_{\sigma_i}$

Sus campos son:

• $v+1$: la vista a la que la réplica quiere migrar.
• $n$: el número de secuencia del último checkpoint estable que conoce la réplica $i$.
• $C$: el conjunto de $2f + 1$ mensajes de checkpoint que prueba que ese checkpoint es correcto.
• $P$: un conjunto $P_m$ por cada solicitud $m$ que quedó preparada en la réplica con número de secuencia mayor que $n$.

Cada $P_m$ contiene un pre-prepare válido y $2f$ prepares firmados por réplicas distintas. [1] Es decir, cada solicitud en vuelo arrastra un certificado de tamaño proporcional a $n$. Si en la ventana entre checkpoints hay $k$ solicitudes preparadas, el mensaje transporta del orden de $k \cdot n$ firmas, más las $2f + 1$ del checkpoint.

Figura 1

La sobrecarga del mensaje VIEW-CHANGE en PBFT

Fuentes:

[1]

Cómo leer esta figura

El diagrama contrapone dos paneles con cuatro réplicas. En el camino feliz, la réplica primaria envía flechas a las otras tres. En el cambio de vista, todas las réplicas se conectan con todas mediante flechas bidireccionales, porque cada una multidifunde su mensaje VIEW-CHANGE con su checkpoint y sus certificados Prepared. El nuevo primario luego empaqueta 2f + 1 de esos expedientes en NEW-VIEW.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Conviene subrayar algo: $k$ no crece sin límite. PBFT acota las solicitudes en vuelo con marcas de agua entre checkpoints, así que el tamaño del expediente depende de esa ventana y de $n$. Para hablar de escalabilidad con el número de réplicas, se suele tratar la ventana como constante y mirar cómo crece el costo con $n$.

NEW-VIEW: el expediente que el nuevo primario debe reenviar

El primario de la vista $v+1$ espera $2f$ mensajes VIEW-CHANGE válidos de otras réplicas. Con ellos y el suyo propio arma el conjunto $\mathcal{V}$ y difunde: [1]

$\langle\text{NEW-VIEW}, v+1, \mathcal{V}, \mathcal{O}\rangle_{\sigma_{p}}$

$\mathcal{O}$ es el conjunto de nuevos pre-prepare. El primario lo calcula así: toma el último checkpoint estable que aparece en $\mathcal{V}$ como límite inferior y el número de secuencia preparado más alto como límite superior. Para cada número intermedio, si algún certificado de $\mathcal{V}$ muestra una solicitud preparada, la vuelve a proponer en la vista $v+1$; si no hay ninguna, propone una operación nula. [1]

La clave está en la verificación. Una réplica que recibe NEW-VIEW no acepta $\mathcal{O}$ por fe: comprueba que los mensajes de $\mathcal{V}$ sean válidos y que $\mathcal{O}$ sea correcto repitiendo el mismo cálculo. Para poder repetirlo necesita los expedientes completos, no un resumen. [1]

Esa decisión de diseño es elegante desde safety: un primario bizantino no puede omitir una solicitud preparada sin que el cálculo de las réplicas lo delate. Pero obliga a que el mensaje NEW-VIEW cargue $2f + 1$ expedientes, cada uno con $O(n)$ firmas.

Contando autenticadores: de cuadrático a cúbico

El paper de HotStuff propone medir estos protocolos por complejidad de autenticadores: cuántas firmas o MACs reciben en total las réplicas para alcanzar una decisión. Bajo esa métrica, reporta que el reemplazo de líder en PBFT cuesta $O(n^3)$, mientras que el camino normal con un líder correcto es cuadrático. [2]

Podemos reconstruir el orden de magnitud con la anatomía anterior:

1. VIEW-CHANGE todos contra todos. Cada una de las $n$ réplicas envía a las demás un mensaje con $O(n)$ firmas. Eso suma $n \cdot n \cdot O(n) = O(n^3)$ autenticadores recibidos.
2. NEW-VIEW de uno a todos. El primario envía a $n$ réplicas un mensaje con $2f + 1$ expedientes de $O(n)$ firmas: $n \cdot O(n^2) = O(n^3)$.

$\text{costo del view change} = n \cdot \underbrace{(2f+1)}_{\text{expedientes}} \cdot \underbrace{O(n)}_{\text{firmas por expediente}} = O(n^3)$

Este conteo no depende de una mala calibración. Aun con un temporizador perfecto, cada reemplazo de líder paga ese orden. Lo que sí empeora la situación es encadenar varios cambios de vista: el paper de HotStuff analiza también el caso de varios líderes fallidos consecutivos, donde el costo acumulado crece todavía más. [2]

¿Bastan las firmas umbral para arreglarlo? Ayudan, pero no eliminan el problema. Si cada certificado Prepared se comprime en una sola firma, cada VIEW-CHANGE baja a $O(1)$ autenticadores por solicitud. Sin embargo, el nuevo primario sigue reenviando los reportes de $n - f$ réplicas a $n$ destinatarios, y el costo queda cuadrático. El cuello de botella no es solo el tamaño de cada certificado, sino la necesidad de reenviar la evidencia de muchas réplicas. [2]

Por qué el expediente no se puede simplemente borrar

La tentación obvia es pedir que el nuevo primario envíe solo el certificado más alto que conoce, sin justificar por qué es el más alto. El problema es que una réplica correcta puede tener un certificado preparado más reciente que ninguno de los $n - f$ reportes que llegaron al primario. Si esa réplica actúa como si estuviera bloqueada en ese certificado, rechazará la propuesta, y el sistema puede quedarse sin quórum. [3]

Hay tres maneras clásicas de resolver esa tensión:

• Probarlo todo, como PBFT: el primario reenvía los expedientes y cada réplica verifica. Es responsivo, pero cuadrático o cúbico en comunicación. [1]
• Esperar, como Tendermint o Casper: el nuevo líder aguarda el retraso máximo de red conocido antes de proponer, para asegurarse de haber oído el certificado más alto de toda réplica correcta. Es lineal, pero pierde responsividad. [2]
• Agregar una fase, como HotStuff: cambia qué significa estar bloqueado, de modo que el certificado más alto entre $n - f$ reportes siempre basta. [2]

La comparación de Malkhi y Nayak sobre PBFT, Tendermint, HotStuff y HotStuff-2 organiza precisamente estas opciones como un compromiso entre fases, comunicación del cambio de vista y responsividad. [3]

La alternativa de HotStuff: un único highQC por réplica

HotStuff ataca el problema desde la forma de la evidencia. En lugar de un expediente con un certificado por solicitud, cada réplica guarda un Quorum Certificate (QC) que resume $n - f$ votos en un solo objeto verificable, y con firmas umbral ese QC es un único autenticador. [2]

En un cambio de vista de HotStuff:

• cada réplica envía al siguiente líder un mensaje new-view con su highQC, el QC más alto que conoce;
• el líder elige el highQC de vista más alta entre $n - f$ mensajes;
• el líder propone un bloque que extiende ese QC y lo difunde junto con ese único certificado.

Ese flujo es lineal: $n$ mensajes de tamaño constante hacia el líder y $n$ de vuelta. [2] La razón por la que basta un solo QC es la tercera fase: una réplica correcta solo se bloquea en un QC cuando ya existe evidencia de que $n - f$ réplicas lo conocen, así que cualquier conjunto de $n - f$ reportes contiene al menos un highQC tan alto como cualquier lock correcto. El análisis completo de esa regla vive en la regla de tres cadenas con QC y highQC y en el pacemaker y el cambio de vista de HotStuff.

El precio es explícito: una fase lógica más en el camino de commit. HotStuff la acepta porque, a cambio, obtiene simultáneamente cambio de vista lineal y responsividad optimista. [2] Los protocolos de dos fases posteriores intentan recuperar esa fase sin perder lo ganado, y la discusión sobre qué cuesta recortar a dos cadenas es el siguiente paso natural.

Siguiente lectura

Continúa con Tendermint visto desde HotStuff: locks, unlocks y evidencia, donde la opción de esperar el retraso máximo de red aparece en un protocolo real.