Por qué las firmas criptográficas (autenticación) reducen los nodos necesarios para el consenso

El título de este artículo es cierto, pero solo en un modelo. En 1982, Lamport, Shostak y Pease presentaron dos algoritmos para el problema de los generales bizantinos: $OM(m)$, con mensajes orales, y $SM(m)$, con mensajes firmados. [1] El primero necesita más de $3m$ generales para tolerar $m$ traidores; el segundo funciona con cualquier número.

Seis años después, Dwork, Lynch y Stockmeyer mostraron que, cuando la red es parcialmente síncrona, la cota bizantina es $n \ge 3f + 1$ con autenticación y sin ella. [2] Los dos resultados no se contradicen: responden a modelos de tiempo distintos. Entender esa diferencia evita uno de los malentendidos más frecuentes sobre BFT, y explica por qué HotStuff usa firmas aunque no le ahorren réplicas.

Mensajes orales: lo que un traidor puede inventar

En el modelo oral, Lamport, Shostak y Pease asumen que todo mensaje enviado se entrega correctamente, que el receptor sabe quién se lo envió y que la ausencia de un mensaje se puede detectar. [1] Lo que no hay es forma de probar a un tercero qué te dijeron.

Ese hueco es suficiente para el traidor. Supongamos que el comandante $A$ envía la orden 1 al teniente $B$, y $B$ es traidor:

1. $B$ le dice al teniente $C$: "el comandante me ordenó 0".
2. $C$ no tiene manera de comprobar si $A$ dijo 0 o si $B$ inventó la orden.
3. Si además el comandante puede ser el traidor, $C$ tampoco sabe a quién creerle.

Con tres generales y un traidor, esa indistinguibilidad hace imposible el acuerdo. El artículo generaliza el resultado: con mensajes orales, ninguna solución con $3m$ generales o menos tolera $m$ traidores, y el algoritmo $OM(m)$ la resuelve cuando hay más de $3m$. [1] La redundancia de generales leales es lo único que permite descartar los relatos falsos por mayoría.

Figura 1

Mensajes orales vs Mensajes firmados criptográficamente

Fuentes:

[1]

Cómo leer esta figura

El diagrama compara dos paneles. En el panel izquierdo (Oral), el nodo A envía 'Voto A' al nodo B; B retransmite a C 'A votó B', engañando a C. En el panel derecho (Firmado), A adjunta la firma σ_A(Voto A). B no puede modificar el voto sin invalidar la verificación de clave pública de C.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Mensajes firmados: el algoritmo SM(m)

El modelo firmado añade un supuesto: la firma de un general leal no se puede falsificar, cualquier alteración del contenido de sus mensajes firmados se detecta, y cualquiera puede verificar la autenticidad de una firma. [1] Los traidores pueden seguir mintiendo sobre sus propias órdenes, pero ya no pueden atribuir a otro una orden que ese otro no firmó.

En $SM(m)$, el comandante firma su orden y cada teniente que la reenvía añade su propia firma. Cada teniente acumula el conjunto de órdenes válidas que le llegan con firma del comandante. Si el comandante es leal, solo existe una orden firmada y todos la reciben. Si es traidor y firmó dos órdenes distintas, las cadenas de firmas hacen que los tenientes leales terminen viendo el mismo conjunto, y aplican la misma regla de decisión sobre él.

Con esas reglas, $SM(m)$ resuelve el problema para cualquier número de generales siempre que haya a lo sumo $m$ traidores. [1] La cota de más de $3m$ desaparece porque ya no hace falta superar en número a los relatos falsos: los relatos falsos sobre otros no se pueden construir.

La letra pequeña: el modelo síncrono

Hay un supuesto que es fácil pasar por alto: que la ausencia de un mensaje se puede detectar. El propio artículo explica que eso exige un tiempo máximo conocido para generar y transmitir mensajes, y relojes razonablemente sincronizados, de modo que un receptor pueda dar por ausente lo que no llegó a tiempo. [1] Es decir, $OM(m)$ y $SM(m)$ son algoritmos para un sistema síncrono.

En ese sistema, un general que no responde a tiempo es, por definición, defectuoso, y el algoritmo puede reemplazar su mensaje por un valor por defecto. Esa capacidad de distinguir "callado" de "lento" es la que deja de existir cuando la red solo es parcialmente síncrona, y con ella se cae la ventaja de las firmas en el número de nodos.

Sincronía parcial: por qué la cota 3f + 1 vuelve aun con firmas

En el modelo parcialmente síncrono, los mensajes pueden retrasarse de forma arbitraria hasta un tiempo de estabilización global desconocido. Para ese modelo, DLS demuestra que el consenso tolerante a $f$ fallas bizantinas es posible si y solo si $n \ge 3f + 1$, y esa cota es la misma para el modelo autenticado que para el no autenticado. [2]

Una forma intuitiva de verlo: antes de GST, ninguna réplica puede esperar más de $n - f$ respuestas, porque $f$ réplicas podrían no responder nunca. Entre las respuestas recibidas, hasta $f$ pueden venir de réplicas bizantinas, y las que faltan pueden ser de réplicas correctas retrasadas. Para que dos conjuntos de $n - f$ respuestas compartan una réplica correcta hace falta $n \ge 3f + 1$, la misma cuenta que se desarrolla en Quórums en acción.

Las firmas no ayudan en esa cuenta por dos razones. Primero, una réplica bizantina puede firmar válidamente dos votos contradictorios; la firma prueba quién votó, no que votó una sola vez. Segundo, el problema antes de GST es el silencio, y una firma no hace llegar antes un mensaje retrasado. Este razonamiento es una lectura informal; la demostración está en el artículo de DLS. [2]

Qué sí compran las firmas en HotStuff

Si no reducen las réplicas, ¿por qué todos los protocolos de la familia HotStuff firman sus votos? Porque convierten un hecho local, "recibí $2f + 1$ votos para este bloque", en evidencia que cualquier otra réplica puede verificar sin repetir la conversación.

HotStuff asume $n = 3f + 1$ réplicas y sincronía parcial, y define un Quorum Certificate como un conjunto de $n - f$ votos firmados sobre la misma propuesta y la misma vista; el artículo usa firmas de umbral para que ese QC sea un único objeto compacto. [3] Un líder nuevo puede presentar el QC más alto que conoce y las demás réplicas pueden comprobarlo sin confiar en él. Esa transferibilidad es la que permite que el cambio de vista y las reglas de bloqueo se apoyen en un único certificado por mensaje, con una cantidad de autenticadores lineal en el número de réplicas. [3]

El costo de esa evidencia depende del esquema criptográfico. Boneh, Lynn y Shacham propusieron una firma basada en emparejamientos cuya longitud es aproximadamente la mitad de una firma DSA de seguridad comparable. [4] Esa construcción es la base de las firmas BLS; cómo se agregan o se combinan por umbral para formar un QC se trata en Firmas de umbral, agregadas y AggQC.

Siguiente lectura

Para ver cómo se usan los QCs en las reglas de voto y de commit, continúa con QC, highQC y three-chain. Si te interesa la parte criptográfica, el siguiente paso es Firmas de umbral, agregadas y AggQC.