Quórums en acción: ¿Por qué 2f+1 votos garantizan que las mayorías se crucen?

En Consenso BFT desde cero aparecieron tres números que se repiten en toda la literatura: $n = 3f + 1$ réplicas, quórums de $q = 2f + 1$ votos y la capacidad de tolerar $f$ fallas bizantinas. Memorizarlos es fácil. Saber defenderlos frente a un diseño alternativo es otra cosa, y es lo que separa a quien configura un comité de quien lo entiende.

¿Por qué exactamente $2f + 1$? ¿Qué se rompe si exigimos $2f$? ¿Por qué no subir a $3f$ para estar "más seguros"? Este artículo responde las tres preguntas con una sola herramienta, la inclusión-exclusión de conjuntos, y muestra cómo PBFT y HotStuff convierten esa aritmética en un invariante de safety.

Del umbral de Lamport al tamaño de quórum

El punto de partida histórico es el problema de los generales bizantinos. Lamport, Shostak y Pease demostraron que, con mensajes orales (no firmados), ningún algoritmo resuelve el acuerdo si un tercio o más de los participantes son traidores; hacen falta más de $3m$ generales para tolerar $m$ traidores. [2] El mismo trabajo muestra que con mensajes firmados el umbral cambia, de modo que conviene recordar que $3f + 1$ depende del modelo y no es una constante universal. [2]

Para los protocolos que nos interesan, el modelo relevante es la sincronía parcial. Dwork, Lynch y Stockmeyer probaron que, en ese modelo y con fallas bizantinas, el consenso es posible si y solo si $n \ge 3f + 1$, incluso cuando las réplicas pueden autenticar sus mensajes. [4] Es decir, las firmas ayudan a detectar equivocaciones, pero no permiten bajar del umbral de un tercio cuando la red puede retrasar mensajes de forma arbitraria antes de estabilizarse.

PBFT tomó ese límite y lo convirtió en ingeniería: con $n = 3f + 1$ réplicas, cada fase del protocolo avanza cuando una réplica reúne $2f + 1$ mensajes coincidentes, y ese conjunto funciona como certificado. [1] HotStuff conserva exactamente la misma regla, aunque la empaqueta en un objeto explícito: un QC es un conjunto de $n - f$ votos firmados sobre la misma propuesta y la misma vista. [3] Con $n = 3f + 1$, $n - f$ es precisamente $2f + 1$.

La demostración algebraica del solapamiento

Imaginemos un conjunto de réplicas de tamaño $n = 3f + 1$. Supongamos que el protocolo exige formar un quórum de $q$ respuestas para validar un bloque o una transacción.

Si dos quórums $Q_1$ y $Q_2$ aprueban dos decisiones (por ejemplo, $Q_1$ aprueba la transacción $A$ y $Q_2$ aprueba la transacción $B$), queremos acotar el tamaño de su intersección $|Q_1 \cap Q_2|$.

Por el principio de inclusión-exclusión de conjuntos:

$|Q_1 \cup Q_2| = |Q_1| + |Q_2| - |Q_1 \cap Q_2|$

Dado que el número total de réplicas en la red es $n$, la unión de cualquier par de quórums no puede exceder $n$:

$|Q_1 \cup Q_2| \le n$

Sustituyendo la desigualdad:

$|Q_1| + |Q_2| - |Q_1 \cap Q_2| \le n$

$|Q_1 \cap Q_2| \ge |Q_1| + |Q_2| - n$

Sustituyendo el tamaño de cada quórum $q = 2f + 1$ y el tamaño del comité $n = 3f + 1$:

$|Q_1 \cap Q_2| \ge (2f + 1) + (2f + 1) - (3f + 1)$

$|Q_1 \cap Q_2| \ge 4f + 2 - 3f - 1$

$|Q_1 \cap Q_2| \ge f + 1$

La cota es ajustada: existen pares de quórums que comparten exactamente $f + 1$ réplicas, de modo que el protocolo no puede contar con un margen mayor. Con $f = 1$ hay $4$ réplicas, quórums de $3$ y un cruce mínimo de $2$. Con $f = 2$ hay $7$ réplicas, quórums de $5$ y un cruce de al menos $3$. Con $f = 3$ hay $10$ réplicas, quórums de $7$ y un cruce de al menos $4$, el caso de la analogía parlamentaria del inicio.

Por qué una réplica correcta en el cruce impide la bifurcación

El punto crítico no es solo cuántos nodos se cruzan, sino quiénes se cruzan.

Si el cruce fuera de $f$ nodos o menos, el adversario podría controlar a todos los nodos de la intersección. Un nodo bizantino puede equivocar: firmar un voto para $A$ que entrega al líder que arma $Q_1$ y otro voto para $B$ que entrega a quien arma $Q_2$. Ambos certificados quedarían completos y dos réplicas correctas podrían ejecutar historias incompatibles, que es exactamente la forma de un doble gasto.

Al forzar $|Q_1 \cap Q_2| \ge f + 1$:

1. El adversario puede controlar a lo sumo $f$ nodos en el solapamiento.
2. Queda obligatoriamente al menos un nodo correcto ($h$) en el solapamiento.
3. Las réplicas correctas siguen las reglas del protocolo: en PBFT aceptan a lo sumo un pre-prepare por vista y número de secuencia, y en HotStuff votan a lo sumo por una propuesta en cada fase de una vista. [1] [3]

Por lo tanto, $h$ no aportará su voto a la segunda propuesta en conflicto, y el quórum $Q_2$ no puede completarse. Nótese la forma de la prueba: no razonamos sobre lo que hace el adversario, sino sobre lo que no puede hacer una sola réplica correcta. Ese patrón, "encontrar un testigo correcto en la intersección", reaparece en casi todas las pruebas de safety de la familia BFT.

La ventana entre safety y liveness

¿Por qué no elegimos un quórum más grande, como $q = 3f$, para estar aún más seguros? Porque el consenso distribuido debe equilibrar safety (no decidir cosas incompatibles) con liveness (seguir decidiendo).

Las dos propiedades imponen cotas opuestas sobre $q$. Para safety necesitamos que la intersección supere a los bizantinos:

$2q - n \ge f + 1 \quad \Longleftrightarrow \quad q \ge \frac{n + f + 1}{2}$

Para liveness necesitamos que el quórum pueda formarse aunque $f$ réplicas callen para siempre, porque un nodo bizantino puede simplemente no votar:

$q \le n - f$

La ventana es no vacía solo si $\frac{n + f + 1}{2} \le n - f$, es decir, si $n \ge 3f + 1$. Este cálculo no reemplaza la prueba de imposibilidad de los papers, pero muestra de dónde sale intuitivamente el umbral: con $n = 3f + 1$ ambas cotas coinciden en $q = 2f + 1$, y no queda margen para elegir otro valor. [4]

Con $q = 3f$ en una red de $3f + 1$ nodos, estaríamos asumiendo que como máximo una réplica falla. Si $f$ nodos sufren una caída o un ataque de denegación de servicio, solo responderán $2f + 1$ réplicas, y para $f \ge 2$ eso es menos que $3f$. La red no viola safety, pero queda paralizada. Por ende, $q = 2f + 1$ es el único punto que cumple ambas condiciones a la vez:

• Suficientemente grande para garantizar $|Q_1 \cap Q_2| \ge f + 1$ (safety).
• Suficientemente pequeño para formarse con las $2f + 1$ réplicas correctas sin esperar a las $f$ restantes (liveness).

La intersección es una propiedad puramente combinatoria: vale con cualquier patrón de retrasos. La formación del quórum, en cambio, necesita que los mensajes de $2f + 1$ réplicas correctas lleguen a tiempo, y eso solo está garantizado después de GST en el modelo de sincronía parcial. [4] Esa asimetría explica por qué en Sincronía parcial y quórums safety no espera a la red y liveness sí.

Intersección entre vistas: lo que el cruce no resuelve solo

La regla "una réplica correcta no vota dos propuestas distintas en la misma vista y fase" protege contra dos certificados en conflicto dentro de la misma vista. Pero los protocolos cambian de líder, y una réplica correcta sí puede votar $A$ en la vista $v$ y $B$ en la vista $v + 1$. Si nada más la restringiera, la intersección por sí sola no impediría revertir una decisión ya tomada.

La solución es transportar la memoria de la intersección a través del cambio de vista. En PBFT, el nuevo líder debe reunir mensajes de cambio de vista de $2f + 1$ réplicas, y cada uno incluye los certificados preparados que esa réplica conoce. [1] Como cualquier decisión anterior fue certificada por $2f + 1$ réplicas, ese conjunto de cambio de vista se cruza con el quórum de la decisión en al menos una réplica correcta, que reporta el certificado y obliga al nuevo líder a respetarlo.

HotStuff aplica la misma aritmética con otros objetos. Cada réplica guarda un lockedQC, y el predicado safeNode solo permite votar una propuesta que extienda ese bloqueo o que traiga un QC de vista más alta. [3] El argumento de safety vuelve a apoyarse en un testigo correcto: si un bloque se confirmó, un quórum quedó bloqueado en él, y cualquier QC conflictivo posterior necesitaría el voto de alguna réplica correcta de ese quórum, que su regla de bloqueo le prohíbe emitir. Los detalles están en QC, highQC y three-chain.

Lo importante para este artículo es la separación de responsabilidades. La intersección de quórums aporta el testigo; los locks y las reglas de cambio de vista aseguran que el testigo recuerde lo que vio. Sin intersección, los locks no alcanzan a nadie; sin locks, la intersección solo protege una vista aislada.

Siguiente lectura

Para ver cómo la intersección convive con GST y los timeouts, continúa con Sincronía parcial y quórums. Si quieres seguir el mismo testigo correcto a través de PBFT, Tendermint y Streamlet, el puente está en PBFT, Tendermint y Streamlet.