Resumen Técnico: Resúmenes que Preservan la Distancia para el Consenso BFT

1. Declaración del Problema

Los protocolos de consenso tolerante a fallos bizantinos (BFT), incluidos HotStuff, PBFT y Ethereum 2.0, dependen de hashes resistentes a colisiones (por ejemplo, SHA-256) para comparar los estados de los validadores. Aunque efectivos para prevenir la falsificación, este enfoque destruye la información de "distancia". Si dos validadores están de acuerdo en 19 de 20 transacciones, sus hashes son completamente ajenos entre sí, indistinguibles de validadores que no comparten ninguna transacción. Esta limitación impone tres restricciones estructurales en la literatura BFT:

1. Sincronización Obligatoria del Estado: Los validadores deben sincronizar completamente el estado antes de votar, ya que los hashes no pueden medir el acuerdo parcial.
2. Calidad del Acuerdo Immedible: Los protocolos no pueden detectar un acuerdo unánime hasta que se completan todas las rondas de votación, lo que obliga a latencias fijas de múltiples rondas incluso en condiciones ideales.
3. Comités Jerárquicos Grandes: Para garantizar la seguridad en consensos con estructura de árbol, los grupos de hojas deben ser lo suficientemente grandes (por ejemplo, 128 validadores en Ethereum) para satisfacer independientemente el umbral de tolerancia bizantina de $2N/3$, lo que limita la profundidad del árbol y la escalabilidad.

2. Metodología: Resúmenes que Preservan la Distancia

El artículo introduce un primitivo llamado Resúmenes que Preservan la Distancia para reemplazar los hashes resistentes a colisiones en la comparación de estados. La construcción implica:

• Vectorización: Cada transacción se hash usando SHA-512. La salida de 64 bytes se divide en 8 segmentos.
• Mapeo de Coordenadas: Cada segmento se trata como un entero sin signo, se reduce módulo 10,000 y se divide por 10,000 para producir una coordenada en el rango $[0, 1)$.
• Suma Conmutativa: El resumen de un validador para un conjunto de transacciones $T$ es la suma vectorial $D(T) = \sum_{tx \in T} v(tx)$ en un espacio de 8 dimensiones.

Este primitivo posee tres propiedades que carecen los hashes:

1. Distancia Proporcional: La distancia euclidiana entre dos resúmenes es proporcional al número de transacciones diferentes.
2. Resumen Exacto: La media ponderada de un grupo de resúmenes es una representación exacta del estado agregado del grupo, permitiendo que un grupo de validadores se resuma en un único valor compacto (76 bytes) sin pérdida de información.
3. Identificación de Diferencias de Conjuntos: Cuando los resúmenes difieren, una diferencia de filtro de Bloom permite al agregador identificar exactamente qué transacciones faltan en la visión de un validador, habilitando una sincronización dirigida sin intercambio completo del estado.

3. Contribuciones Clave y Aplicaciones

El artículo demuestra tres aplicaciones principales de este primitivo dentro de un nuevo protocolo llamado Proxima:

A. Protocolo BFT de Dos Fases (Proxima)

Proxima opera en dos fases:

• Fase 1 (Filtrado por Distancia): Los validadores envían resúmenes y filtros de Bloom a un agregador. El agregador agrupa a los validadores dentro de un umbral de distancia. Si la varianza del grupo está cerca de cero (indicando un alto acuerdo), el protocolo emite un certificado de finalidad de una sola ronda (ruta rápida). Si no, empuja las transacciones faltantes mediante la diferencia de Bloom.
• Fase 2 (Compromiso): Los miembros del grupo firman el hash del bloque utilizando firmas BLS. El agregador produce una firma agregada.
• Resultado: A diferencia de HotStuff, que requiere tres rondas independientemente del acuerdo, Proxima logra finalidad de una sola ronda cuando los validadores están de acuerdo.

B. Consenso con Estructura de Árbol con Grupos Pequeños

Dado que el filtrado por distancia opera a nivel individual en lugar de requerir BFT a nivel de grupo, Proxima permite un consenso jerárquico con grupos pequeños (por ejemplo, 10 validadores).

• Mecanismo: Los líderes de hojas filtran a los validadores bizantinos (que están lejos de la referencia) e informan la media ponderada de los validadores honestos.
• Resultado: Esto elimina la necesidad de comités grandes (128 validadores) para garantizar la seguridad, permitiendo árboles más profundos (5 niveles frente a 2–3 niveles) y reduciendo la complejidad de los mensajes.

C. Verificación de Consistencia entre Fragmentos (Shards)

Los resúmenes permiten una verificación de costo constante entre fragmentos.

• Mecanismo: Los fragmentos vecinos intercambian resúmenes de las transacciones de la zona de superposición. Si la distancia es cero, los estados coinciden. Si es distinta de cero, la diferencia de Bloom identifica transacciones divergentes específicas para su resolución.
• Resultado: Esto reemplaza la coordinación por transacción del Compromiso de Dos Fases (2PC) o las cadenas de recibos, reduciendo la sobrecarga entre fragmentos en un 99% en comparación con el 2PC a tasas de propagación del 95%.

4. Resultados y Evaluación

El artículo evalúa Proxima frente a HotStuff, PBFT y la estructura de comités de Ethereum utilizando simulaciones con $N=100,000$ validadores y un 30% de fallos bizantinos.

• Complejidad de Mensajes: Proxima Tree utiliza 2.2 veces menos mensajes que HotStuff. Esta es una propiedad estructural no afectada por el paralelismo, derivada de la ejecución en dos fases, el pre-filtrado de nodos bizantinos y el enrutamiento en árbol con resúmenes compactos.
• Latencia:
  • Núcleo Único: Proxima logra finalidad de núcleo único en ~0.9 segundos (902 ms) en comparación con ~18 segundos para HotStuff. La estructura de árbol distribuye la agregación BLS, manteniendo el procesamiento de la ruta crítica bajo (9.9 ms).
  • Multi-núcleo: Aunque la agregación BLS multi-núcleo reduce la brecha (HotStuff baja a ~940 ms, Proxima Flat a ~220 ms), el árbol mantiene una ventaja en el tiempo BLS de la ruta crítica porque los nodos de hoja procesan muy pocas firmas.
• Sobrecarga entre Fragmentos: A una propagación del 95%, la verificación basada en resúmenes utiliza un 99% menos de mensajes que el 2PC y un 95% menos que los enfoques basados en recibos (NEAR Nightshade).
• Seguridad: La seguridad se demuestra independiente del agrupamiento de la Fase 1. Menos de $N/3$ validadores bizantinos no pueden causar finalizaciones conflictivas. La Fase 1 puede excluir validadores honestos (riesgo de vivacidad), pero esto está acotado por la desigualdad de Hoeffding para ser insignificante ($<10^{-9}$ en $N$ práctico).

5. Significado y Afirmaciones

El artículo afirma que los resúmenes que preservan la distancia eliminan las tres restricciones fundamentales impuestas por el hashing resistente a colisiones en BFT. Al permitir la medición de la calidad del acuerdo, el primitivo permite:

1. Rutas Rápidas Optimistas: Los protocolos pueden finalizar en una ronda cuando el consenso es alto.
2. Jerarquías Escalables: Los árboles de consenso pueden utilizar grupos pequeños (tamaño 10) y estructuras profundas, ya que la seguridad se mantiene mediante filtrado por distancia en lugar de votación por grupo.
3. Fragmentación Eficiente: La consistencia entre fragmentos puede verificarse a un costo constante por par de fragmentos, escalando con la divergencia real en lugar del volumen total de transacciones.

Los autores enfatizan que, aunque el primitivo es una aplicación conocida de Hashing Sensible a la Localidad (LSH) en estructuras de datos, su aplicación al acuerdo bizantino es novedosa. La seguridad del sistema depende de supuestos criptográficos estándar (firmas BLS y SHA-512), siendo el filtro de distancia un mecanismo de vivacidad y optimización en lugar de un mecanismo de seguridad. El artículo concluye que este enfoque ofrece una mejora general para cualquier protocolo BFT que compare estados mediante hashes.