BFT en Computación en el Borde (Edge/IoT): Consenso con conectividad intermitente

Los capítulos anteriores daban por hecho servidores con buena CPU, memoria y enlaces estables. Un despliegue de Internet de las Cosas rompe esos tres supuestos a la vez: los dispositivos tienen poco almacenamiento, poca energía y poca capacidad de cómputo, y los enlaces son estrechos. Yuan y coautores lo plantean como el punto de partida de su trabajo y señalan al algoritmo de consenso como una de las causas del problema. [1]

Este capítulo no promete una arquitectura de referencia para el borde. Hace algo más modesto y más útil: explica qué parte del consenso BFT es cara, y luego lee con cuidado una propuesta publicada, EBRC, separando lo que propone, lo que mide y lo que queda sin demostrar.

Por qué el consenso BFT pesa en un dispositivo limitado

PBFT tolera $f$ réplicas bizantinas con $n = 3f + 1$ réplicas, y su caso normal tiene tres fases: el líder difunde un pre-prepare, y en las fases prepare y commit cada réplica envía su mensaje a todas las demás. [2] Esas dos fases todos-contra-todos son la fuente del costo: por cada decisión circulan del orden de $n^2$ mensajes, y cada réplica tiene que recibir y autenticar del orden de $n$ mensajes por fase.

En un centro de datos ese costo se paga con ancho de banda. En un nodo IoT se paga también con radio encendida y ciclos de CPU dedicados a verificar autenticadores. Los autores de EBRC enumeran cuatro problemas de PBFT para este contexto: no evalúa la fiabilidad de los nodos, no castiga a los maliciosos, funciona bien en redes pequeñas y fijas, y genera mucho tráfico por su comunicación $n^2$. [1]

HotStuff ataca el mismo costo por otra vía. En lugar de que todos hablen con todos, las réplicas envían su voto al líder, que agrega $n - f$ votos en un único certificado (QC) con una firma umbral y lo difunde en la fase siguiente; así cada fase tiene comunicación lineal en $n$. [3] Con $n = 3f + 1$, ese QC equivale a $2f + 1$ votos.

Hay dos caminos, entonces, para abaratar el consenso. Uno cambia el patrón de comunicación manteniendo a todas las réplicas, como hace HotStuff. El otro reduce cuántas réplicas votan, que es la apuesta de EBRC. No son excluyentes, pero tienen consecuencias distintas para la seguridad, como veremos al final.

La propuesta EBRC: reputación, sorteo y comité

EBRC (Efficient Byzantine Reputation-based Consensus) se compone de cinco piezas: evaluación de reputación, evaluación de la tasa de crecimiento de esa reputación, elección aleatoria con VRF, el protocolo de consenso propiamente dicho y un protocolo de entrada y salida dinámica de nodos. [1] La figura las recorre en orden.

Figura 1

De la tabla de comportamiento al comité en EBRC

Fuentes:

[1]

Cómo leer esta figura

Cuatro columnas. En la primera hay ocho nodos, uno de ellos en rojo por mal historial, y una tabla de comportamiento con depósito, consensos no completados, mensajes erróneos reportados, actividad y latencia, y volumen procesado. En la segunda, la reputación R_i en el intervalo de cero a uno se calcula como suma ponderada de los cinco factores, junto con su tasa de crecimiento; un nodo nuevo empieza en 0,5 y los valores se recalculan y acuerdan al final de cada época. En la tercera, el derecho a ser elegido depende del ranking de reputación y de su crecimiento, y un sorteo VRF con semilla derivada del hash del bloque previo se compara con un umbral omega. En la cuarta, los mejores forman los nodos de consenso, el siguiente tramo queda como candidatos que sustituyen a un caído, y el comité decide con prepare y commit y 2f + 1 confirmaciones, sobre el comité y no sobre los N nodos.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Cada nodo tiene una reputación $R_i \in (0, 1]$, que empieza en $0{,}5$ para los recién llegados, y para aspirar al comité debe pagar un depósito que se reduce si se comporta mal. [1] La reputación combina cinco factores registrados en una tabla de comportamiento que mantiene toda la red: la proporción de depósito, la tasa de consensos no completados, la tasa de mensajes erróneos reportados por otros nodos, un índice de actividad basado en desconexiones y latencia, y un factor de volumen de transacciones inspirado en el índice h. [1]

Los pesos que proponen son 0,3 para las tasas de consensos incompletos y de mensajes erróneos, 0,2 para la actividad y 0,1 para el depósito y el volumen. [1] Ojo con un detalle de lectura: la fórmula, tal como aparece impresa, suma esas tasas con signo positivo, y el texto no explica cómo se invierten para que más fallas impliquen menos reputación. Quien quiera reimplementar EBRC tendrá que resolver esa ambigüedad por su cuenta.

La red funciona por épocas de 20 rondas, con un bloque por ronda, y al final de cada época el líder vigente propone la actualización de reputaciones, que los nodos acuerdan con el mismo protocolo de consenso. [1] Luego viene la elección. Solo los nodos bien clasificados por reputación y por crecimiento tienen derecho a ser elegidos, y entre ellos un sorteo con función aleatoria verificable (VRF), alimentado por una semilla derivada del hash del bloque anterior, decide quién entra al conjunto de consenso. [1] Según el texto, la mitad superior por reputación forma los nodos de consenso y el tramo entre el 50 % y el 85 % queda como candidatos de reemplazo. [1]

Cómo decide el comité y cómo se renueva

Dentro del comité, EBRC conserva la aritmética de PBFT. El líder de cada vista se elige como $p = (h + v) \bmod (3f + 1)$, donde $h$ es la altura del bloque y $v$ la vista, de modo que el líder rota con cada bloque. [1] El protocolo tiene dos fases, prepare y commit: el líder difunde la propuesta, cada nodo la verifica y envía su confirmación, y se alcanza consenso cuando los nodos reúnen $2f + 1$ confirmaciones idénticas; si no, se inicia el cambio de vista y el nodo sospechoso queda anotado en la tabla de comportamiento. [1]

El quórum de $2f + 1$ sobre $3f + 1$ es el mismo que usa PBFT para garantizar que dos certificados se crucen en una réplica correcta. [2] Lo que cambia es el universo sobre el que se cuenta: $n$ ya no es el total de dispositivos, sino el tamaño del comité.

El protocolo de entrada y salida dinámica cubre el caso que más preocupa en el borde: nodos que se van. Si tras una salida el comité sigue teniendo al menos $3f + 1$ miembros, basta un intercambio de confirmación; si queda por debajo, el líder ofrece el puesto al candidato con mejor reputación, que solicita la entrada y es confirmado por el comité. [1]

Sobre la complejidad, el paper da dos versiones que conviene leer juntas. Su tabla comparativa atribuye a EBRC una complejidad $O(m^2)$ con $m < n$, es decir, cuadrática en el tamaño del comité; la lista de conclusiones afirma que, en una red estable, la complejidad se reduce de $O(n^2)$ a $O(n)$. [1] La lectura más prudente es la primera: el ahorro viene de votar entre menos nodos, no de cambiar el patrón de mensajes como hace HotStuff. [3]

Qué evaluaron los autores y qué no

El prototipo se construyó sobre Hyperledger Sawtooth, comparando EBRC con el PBFT original. Los experimentos corrieron en servidores de un clúster con CPU Intel Core i7 de dos núcleos a 2,2 GHz y 16 GB de memoria, usados para simular dispositivos IoT, con un comité inicial de 4 nodos y un máximo de 40. [1]

Con esa configuración, los autores reportan menor latencia de transacción y mayor throughput que PBFT al crecer el número de nodos, y conservan la ventaja en throughput y en número de mensajes cuando $(n - 1)/3$ nodos son maliciosos. [1] En el experimento de elección, con 20 nodos de reputación inicial idéntica y 1000 repeticiones, cada nodo fue elegido entre 48 y 51 veces; al subir la tasa de error de algunos nodos, estos fueron elegidos bastante menos, y el texto habla de dos a cuatro veces menos según el caso. [1] La entrada y salida dinámica, con 25 nodos, añadió en promedio 1 ms cuando solo hubo salida y 28 ms cuando hubo salida y entrada. [1]

Estas son afirmaciones de un único artículo de revista, y conviene leerlas con sus límites:

• No hay dispositivos reales. Los nodos son servidores que simulan dispositivos, de modo que la evaluación no mide energía, radio ni memoria restringida, que eran la motivación del trabajo. [1]
• El adversario es pasivo. En el experimento con nodos maliciosos, estos reciben mensajes pero no responden ni reenvían; no se prueban equivocaciones, mensajes contradictorios ni manipulación de la propia reputación. [1]
• La escala es pequeña. Hasta 40 nodos, lejos de los despliegues masivos que el artículo usa como motivación.
• Hay inconsistencias de presentación. Además de las dos complejidades citadas, la figura de throughput etiqueta su eje en milisegundos.

Nada de esto invalida la idea, pero sí define su estatus: es una propuesta con una evaluación preliminar, no un resultado establecido.

Lo que la reputación no resuelve

La seguridad de un protocolo tipo PBFT no depende de la historia de los nodos, sino de que, en el conjunto que vota, a lo sumo $f$ de $3f + 1$ sean bizantinos. [2] Un comité pequeño hace más barato cada voto, pero también hace más barato capturar el umbral: un adversario necesita colocar menos nodos para superar un tercio de un comité de diez que un tercio de toda la red.

La reputación filtra a quien se ha portado mal, pero un nodo puede construir buena reputación con paciencia y cambiar de comportamiento cuando entra al comité. EBRC mitiga ese riesgo con depósito, sorteo verificable y rotación por épocas, y el análisis del paper es empírico, no una prueba formal de que el comité respete el umbral. [1] Para un sistema donde la safety importa, esa es la pregunta que habría que responder antes de desplegar.

El otro camino, mantener a todas las réplicas y abaratar el patrón de mensajes, conserva el umbral sobre la red completa. HotStuff muestra que se puede lograr comunicación lineal por fase, aunque a cambio de firmas umbral cuyo costo criptográfico también pesa en hardware limitado. [3] Elegir entre ambos depende de qué es más escaso en el despliegue concreto: mensajes, cómputo o confianza en el proceso de selección.

Siguiente lectura

Para ver cómo un conjunto de réplicas puede cambiar sus propias reglas mediante consenso, continúa con Gobernanza on-chain y votos BFT. Si quieres repasar el patrón de mensajes que EBRC intenta abaratar, vuelve a PBFT en tres pasos.