Costes computacionales en BFT: Firmas agregadas BLS vs. Ed25519

En Firmas en BFT: threshold, agregadas y AggQC separamos qué significa cada familia de firmas: qué mensaje se firma, con qué claves y qué prueba el objeto resultante. Este artículo toma esa taxonomía como dada y mira otra cara: el coste. Cuántos bytes ocupa un certificado de quórum, cuántas operaciones criptográficas hacen falta para verificarlo y quién paga cada una.

La pregunta práctica suele formularse como "BLS o Ed25519". Es una abreviatura engañosa, porque mezcla dos decisiones: qué primitiva de firma usa cada réplica y cómo se empaqueta un quórum de votos. Las separamos.

El objeto que pagamos: un QC de 2f + 1 votos

En HotStuff, un certificado de quórum (QC) reúne los votos de $n - f$ réplicas sobre la misma propuesta y vista; con $n = 3f + 1$ eso son $2f + 1$ votos. [4] Cada propuesta lleva un QC, cada réplica lo verifica y, en cambio de vista, el nuevo líder recibe QCs de muchas réplicas. Por eso su tamaño y su coste de verificación se multiplican por todo el protocolo.

El paper de HotStuff mide la complejidad en autenticadores, es decir, en firmas o firmas parciales que viajan. Su resultado de comunicación lineal supone que un QC puede representarse con un único autenticador gracias a firmas de umbral; con una lista de firmas individuales, cada QC reenviado cuesta $2f + 1$ autenticadores. [4]

Si llamamos $s$ al tamaño de una firma individual, una lista ocupa aproximadamente

$|QC_{\text{lista}}| \approx (2f + 1)\cdot s$

más los identificadores de los firmantes. Es aritmética, no una medición: el tamaño crece linealmente con el comité. Y verificarlo cuesta $2f + 1$ verificaciones independientes.

BLS: la firma corta y el precio de los emparejamientos

Boneh, Lynn y Shacham propusieron un esquema en el que la firma es un único punto de una curva elíptica: se aplica un hash al mensaje para obtener un punto y se multiplica por la clave privada. Su firma mide aproximadamente la mitad que una firma DSA de seguridad comparable. [1]

La contrapartida está en la verificación. Para comprobar una firma BLS hay que evaluar un emparejamiento bilineal, una función que relaciona puntos de dos grupos, y comprobar una igualdad entre dos emparejamientos: uno que involucra la firma y otro que involucra la clave pública y el hash del mensaje. [1] Como referencia general, evaluar un emparejamiento es bastante más costoso que las operaciones de grupo que usa un esquema de curva elíptica convencional.

Como contexto, sin cifras: Ed25519 es un esquema tipo Schnorr sobre una curva de Edwards. No usa emparejamientos y suele verificarse más rápido que BLS, pero no ofrece la agregación algebraica que hace atractivo a BLS. Un QC con Ed25519 vuelve, en esencia, al caso de la lista. Las cifras de rendimiento dependen de la biblioteca, la curva concreta y el hardware, así que conviene medirlas en el propio sistema antes de decidir.

Tres maneras de compactar un QC con BLS

La gracia de BLS es que su estructura algebraica permite combinar firmas. Hay tres variantes relevantes para un QC, y cada una paga distinto.

Firma de umbral. El comité comparte una clave pública y cada réplica posee una parte de la clave privada. Cada voto es una firma parcial sobre el mismo mensaje; con suficientes parciales, cualquiera las combina por interpolación en una firma que verifica contra la clave del comité exactamente como una firma BLS normal. [3] El QC ocupa una sola firma y su verificación cuesta lo mismo que la de una firma BLS. El precio está en otra parte: hace falta repartir la clave del comité y el QC no dice quién firmó.

Multifirma. Cada réplica tiene su propia clave y todas firman el mismo mensaje. Las firmas se combinan en una y las claves públicas de los firmantes también, de modo que la verificación vuelve a ser la de una sola firma más el coste de combinar las claves. [3] El QC debe indicar qué réplicas firmaron, por ejemplo con un mapa de $n$ bits, para que el verificador sepa qué claves combinar. Además, cualquier multifirma que combine claves públicas debe defenderse de claves maliciosas construidas a partir de las claves honestas (ataques de clave falsa); una defensa habitual es exigir que cada clave se registre junto con una prueba de que su dueño conoce la clave secreta.

Firma agregada sobre mensajes distintos. Boneh, Gentry, Lynn y Shacham mostraron cómo agregar $k$ firmas de $k$ usuarios sobre $k$ mensajes distintos en una sola firma. [2] El tamaño se compacta, pero la verificación necesita $k + 1$ emparejamientos, porque cada par de clave y mensaje debe comprobarse por separado. [2] Es la herramienta natural cuando cada réplica reporta algo distinto, como los highQC en un AggQC, pero no abarata la verificación.

Comparar tamaño y verificación en una sola tabla mental

La tabla deja ver el trade-off. Pasar de una lista a una firma de umbral o a una multifirma cambia un coste que crece con el comité por uno casi constante, tanto en bytes como en verificación del certificado. [3] Pero cada verificación se paga en emparejamientos, de modo que para comités pequeños una lista de firmas sin emparejamientos puede verificarse en menos tiempo total que una sola firma BLS. Dónde está el punto de cruce depende de las bibliotecas y del hardware; no existe un umbral universal de tamaño de comité.

El coste que no desaparece: verificar votos antes de agregar

Hay una asimetría que las tablas suelen ocultar. Para formar el QC, el líder recibe $2f + 1$ votos individuales. Si combina una parte inválida, el certificado resultante no verifica, y el líder no sabe cuál falló. Lo prudente es validar cada voto o cada firma parcial antes de combinarlo, y en BLS cada una de esas validaciones vuelve a costar emparejamientos. [1] [3]

Es decir, la compactación desplaza el coste. El agregador sigue haciendo un trabajo proporcional al quórum; quienes ganan son los receptores del QC: las réplicas que validan la propuesta siguiente, los nodos que se sincronizan desde cero o los clientes ligeros que verifican certificados antiguos. En HotStuff eso importa porque cada propuesta carga el QC de la anterior y todas las réplicas lo verifican. [4]

Una táctica habitual es verificar primero el agregado y solo comprobar los votos uno por uno si falla. Funciona bien cuando las réplicas bizantinas son raras, pero una réplica maliciosa puede forzar la ruta cara enviando partes inválidas a propósito. Esto es un razonamiento general de ingeniería, no un resultado de los papers citados.

Cómo decidir sin cifras importadas

La elección depende de tres preguntas. Primera: ¿cuántas veces se verifica cada QC y por quién? Si el certificado se reenvía y se archiva, compactarlo paga. Segunda: ¿los votos son sobre el mismo mensaje? Si lo son, umbral o multifirma dan verificación constante; si no, la agregación ahorra bytes pero no emparejamientos. [2] [3] Tercera: ¿necesitas saber quién votó? El umbral lo oculta; la multifirma y la lista lo conservan.

Siguiente lectura

Para ver cómo un certificado agregado sobre reportes distintos cambia el cambio de vista, sigue con Fast-HotStuff, AggQC y two-chain. Si quieres conectar estos costes con el número de nodos que participan, continúa con Firmas criptográficas y reducción de nodos.