GRANDPA: finalizar cadenas, no bloques

Un exchange acredita depósitos de una cadena construida con Substrate (Polkadot SDK). Hasta ahora esperaba "suficientes bloques" encima de la transacción, como se hacía con Bitcoin. Un día, durante una partición de red, dos ramas crecen en paralelo durante varios minutos. Cuando la red se repara, una rama desaparece y con ella un depósito que ya figuraba como confirmado. La pregunta del equipo de riesgo es directa: ¿existe un punto a partir del cual un bloque no puede revertirse?

En Substrate la respuesta es sí, y se llama GRANDPA. Los capítulos sobre Aura y BABE mostraron cómo se producen bloques y cómo se elige la mejor rama, pero ninguno de los dos promete que un bloque sea definitivo. Este capítulo explica cómo GRANDPA convierte "probablemente definitivo" en "demostrablemente definitivo", bajo qué supuestos, y qué ve un operador cuando esos supuestos fallan.

Un finality gadget: producir y finalizar por separado

GRANDPA no produce bloques. Es un finality gadget: un protocolo que corre al lado de la producción y va marcando qué prefijo de la cadena ya es definitivo. El paper que lo define lo describe así: "A finality gadget allows for transactions to always optimistically commit but informs the clients that these transactions might be unsafe." [1] Las transacciones entran en bloques de inmediato; la finalidad llega después y se lo comunica a quien necesite certeza.

La especificación de Polkadot lo dice desde el punto de vista del nodo: "Validators execute GRANDPA finality process in parallel to Block Production as an independent service." [2] Aura o BABE siguen produciendo a su ritmo; GRANDPA vota sobre lo que ya existe.

La separación tiene una ventaja operativa que el paper hace explícita. Si la red se parte, el protocolo "does not stop": "only the finalization stops, but the blocks keep getting created and propagated to everyone." [1] Y cuando las condiciones mejoran, el gadget "only needs to finalize the head of the chain", en lugar de repetir consenso bloque por bloque. [1] De ahí el título: GRANDPA finaliza cadenas, no bloques. Una sola ronda exitosa puede finalizar cientos de bloques acumulados.

Los autores lo presentan como una decisión de diseño general: mostrar "that the protocol designer can decouple safety and liveness in order to speed up recovery from failures." [1] La producción aporta la vitalidad (la cadena siempre avanza) y GRANDPA aporta la seguridad (lo finalizado no se revierte).

El modelo: n votantes, f < n/3, sincronía parcial

Toda garantía de finalidad depende de supuestos. Los de GRANDPA son dos. El primero, sobre los participantes: "at most f < n/3 voters are Byzantine. We need n − f of voters to agree on finality." [1] Un votante bizantino puede hacer cualquier cosa: callar, mentir, votar dos veces. Con cuatro votantes, tolera uno; con cien, treinta y tres.

El segundo supuesto es sobre la red: GRANDPA usa el modelo de sincronía parcial. Todo mensaje llega en un tiempo T, "but possibly only after some Global Synchronisation Time GST". [1] Antes de GST la red puede comportarse arbitrariamente mal; después, se porta bien. El capítulo sobre sincronía parcial y quórums desarrolla este modelo.

¿Por qué no pedir menos? Porque el paper demuestra que el problema "is impossible to solve it deterministically in full asynchrony (even though it is stronger than consensus)". [1] Es la misma familia de resultados que el teorema FLP: sin ningún límite de tiempo, un protocolo determinista no puede garantizar a la vez seguridad y terminación.

Una nota sobre fuentes. Una página de la documentación de Polkadot afirma que GRANDPA "Can handle up to 1/5 Byzantine (malicious) nodes". [3] Esa cifra no coincide con el paper, que demuestra seguridad con f < n/3. En este capítulo seguimos el paper. Además, la investigación de Web3 Foundation aclara que lo desplegado es "Polite GRANDPA", con optimizaciones que "are not covered in the papers"; los principios de diseño son los mismos. [4]

Supermayorías y la función 2/3-GHOST

El paper define cuándo un conjunto de votos S tiene supermayoría para un bloque B: cuando los votantes que votaron por B o por un descendiente de B, más los que equivocaron, suman al menos (n + f + 1)/2. [1] Con n = 3f + 1, eso da 2f + 1. Las equivocaciones cuentan como votos para todo, de modo que ver más votos nunca quita una supermayoría ya vista.

¿Por qué ese número? Porque dos conjuntos de 2f + 1 votantes, dentro de un total de 3f + 1, comparten al menos f + 1. Como solo hay f bizantinos, al menos uno de los compartidos es honesto, y un honesto no vota por dos ramas incompatibles en la misma etapa. El capítulo sobre quórums en acción desarrolla esta intersección con más ejemplos.

Sobre esa definición se apoya la función central: "2/3-GHOST function g(S) takes a set S of votes and returns the block B with highest block number such that S has a supermajority for B." [1] Un voto por un bloque cuenta también para todos sus antecesores. Si los votantes apuntan a puntas distintas de un árbol de forks, g(S) es el bloque más profundo en el que todavía se juntan 2f + 1 de ellos.

La figura 1 lo muestra con cuatro votantes y un fork. Dos votan por B4, uno por B3', y el cuarto no vota. Los tres votos pasan por B2, pero ningún hijo de B2 reúne tres. Entonces g(V) = B2.

Figura 1

Una ronda de GRANDPA con n = 4 y f = 1

Fuentes:

[1]

Cómo leer esta figura

Una cadena con el bloque finalizado F, luego B1 y B2, que se bifurca en B3 seguido de B4 y en B3 prima. Junto a B4 se anota que votan v1 y v2; junto a B3 prima, que vota v3; v4 no vota porque está caído. Una flecha azul señala B2 desde un recuadro que dice que g(V) es B2 porque tres de cuatro prevotes están en cadenas que contienen B2 y ningún hijo suma tres. Una flecha verde lleva a otro recuadro: tres precommits para B2 o descendientes finalizan B2 y, con él, B1. Abajo: con n igual a 4 y f igual a 1, la supermayoría es tres, y dos supermayorías se cruzan en al menos un votante honesto.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Una ronda: prevote, precommit, finalizar

GRANDPA avanza en rondas. Cada ronda tiene un primario y dos etapas de voto, y cada votante honesto vota una sola vez por etapa y por ronda. [1] La descripción del paper tiene cuatro pasos, que resumimos con su lógica.

Primero, el primario de la ronda difunde su estimación de lo que pudo finalizarse en la ronda anterior. Segundo, cada votante espera un margen de tiempo (2T en el paper) o a que la ronda sea "completable", y emite un prevote por la punta de la mejor cadena que contiene esa estimación; si el primario propuso un bloque compatible, usa la mejor cadena que lo contiene. [1]

Tercero, cuando g de los prevotes recibidos alcanza al menos la estimación anterior y se cumple alguna condición de espera, el votante emite un precommit por g(V). Cuarto, si g de los precommits es posterior al último bloque finalizado y los prevotes tienen supermayoría, el bloque se finaliza; el votante puede difundir un mensaje de commit con el bloque y los precommits que lo respaldan. [1]

Ese conjunto de firmas es una justificación. La especificación la define como un vector de votos firmados de una ronda, y precisa que una justificación válida "must only contain up to one valid vote from each voter and must not contain more than two equivocatory votes from each voter." [2] Con ella, cualquiera que conozca el conjunto de votantes puede comprobar la finalidad sin haber participado en la ronda. El capítulo 14 aprovecha exactamente eso.

Accountable safety: si algo sale mal, se sabe quién fue

¿Qué pasa si los supuestos fallan y hay más de f bizantinos? Entonces dos bloques incompatibles podrían finalizarse. GRANDPA no puede impedirlo, pero sí garantiza que el daño deja huellas: "Accountable Safety: If blocks on different chains are finalised, then we can identify at least f + 1" votantes bizantinos. [1]

Esa propiedad cambia la conversación económica. Si cada votante tiene stake en juego, una finalización conflictiva no es solo un fallo técnico: es una prueba contra al menos f + 1 votantes, que el runtime puede castigar. El capítulo sobre slashing e incentivos BFT explica por qué esa prueba importa tanto como la propia seguridad.

Un detalle que suele sorprender: cuando falla la vitalidad, la cadena no se detiene. Si caen más de f votantes, no se reúne la supermayoría y la finalidad se para; Aura o BABE siguen produciendo, y el último bloque finalizado queda cada vez más atrás. Cuando los votantes vuelven, una ronda puede finalizar de golpe todo lo acumulado. Ese es el comportamiento que el laboratorio propuesto busca medir.

Cambiar de votantes sin detener la finalidad

Un conjunto de votantes no es eterno: entran y salen validadores, se rotan claves. El crate de GRANDPA explica la idea: "we obtain agreement for some maximum block height that the current set can finalize, and once a block with that height is finalized the next set will pick up finalization from there." [5] Un bloque señala el cambio con una demora de N bloques, y los votantes no votan por cadenas más allá del punto de traspaso hasta finalizarlo.

Las señales viajan como logs de consenso en la cabecera. Además del cambio programado existe un cambio forzado, pensado para recuperarse cuando la finalidad está trabada: "Forced changes are applied after a delay of imported blocks, while pending changes are applied after a delay of finalized blocks." [6] Un cambio programado necesita finalidad para aplicarse; uno forzado, no. El capítulo sobre reorganización dinámica de validadores trata el problema general.

Integrar GRANDPA en un nodo

En el código, GRANDPA se engancha en dos lugares. Primero, un wrapper de block import, con una advertencia en mayúsculas: "All blocks imported (from network or consensus or otherwise) must pass through this wrapper, otherwise consensus is likely to break in unexpected ways." [5] Ese wrapper detecta las señales de cambio de autoridades y procesa justificaciones. Segundo, una tarea de fondo, el votante, que participa en las rondas.

El solochain template muestra el cableado: crea el block import de GRANDPA y se lo pasa a la cola de importación de Aura, también como importador de justificaciones, con GRANDPA_JUSTIFICATION_PERIOD = 512. [7] El crate aclara qué controla ese número: el período mínimo con el que se importan justificaciones, para evitar "slowing down sync by a peer serving us unnecessary justifications". [5] Conviene saber también que el crate se declara inestable: "This crate is unstable and the API and usage may change." [5]

Qué cambia respecto de Ethereum

Ethereum también separa producción y finalidad: LMD-GHOST elige la cabeza y Casper FFG finaliza. El capítulo sobre Casper FFG como gadget de finalidad es la comparación natural. Las dos reglas comparten la aritmética de supermayorías de dos tercios y la idea de que una violación deja pruebas para castigar.

Cambia la unidad de voto. Casper FFG vota enlaces entre checkpoints, uno por epoch, y un checkpoint se finaliza cuando él y su sucesor directo quedan justificados; la finalidad avanza a ritmo de epochs, como vimos en finalidad, slashing e inactivity leak. GRANDPA vota sobre bloques arbitrarios, sin calendario de checkpoints, y una ronda puede finalizar cualquier cantidad de bloques.

Cambia también la respuesta a una caída masiva. Ethereum tiene el inactivity leak, que reduce el saldo de los validadores ausentes hasta que los presentes recuperan los dos tercios. GRANDPA, por sí mismo, simplemente espera; la recuperación pasa por que los votantes vuelvan o por un cambio forzado del conjunto. El siguiente capítulo, sincronización y light clients, muestra cómo las justificaciones de GRANDPA permiten a un nodo nuevo ponerse al día sin re-ejecutar toda la historia.

Laboratorio propuesto

Estado: propuesta. Este laboratorio todavía no está publicado en lab.trautslab.dev; se ejecutará en local, sin red pública ni fondos reales.

Objetivo. Ver la separación entre producción y finalidad: la cadena avanza aunque la finalidad se detenga, y se pone al día de golpe cuando vuelve el quórum.

Pasos propuestos.

1. Levantar una red local de cuatro validadores con GRANDPA, con el nodo kitchensink o con el solochain template.
2. Apagar dos validadores. Con n = 4, la supermayoría es 3, así que la finalidad debe detenerse mientras la producción continúa.
3. Encender los dos validadores y medir cuántos bloques finaliza la siguiente ronda exitosa de una sola vez.

Evidencia esperada. Con dos validadores apagados, el número del mejor bloque sigue creciendo y el del último finalizado queda fijo. Al volver, el finalizado salta hasta cerca de la punta en una sola ronda. Con Aura, ojo: dos autoridades apagadas también dejan la mitad de los slots vacíos. Los tiempos exactos de recuperación dependen de la versión del nodo y de la red, y quedan a validar al construir el laboratorio.