Resumen Técnico: Adquisición Adversarial en Blockchains

Enunciado del Problema

El artículo aborda el desafío de la adquisición adversarial en protocolos de blockchain, específicamente en el contexto de diseños emergentes que aprovechan la asimetría computacional entre la ejecución y la verificación de tareas (por ejemplo, pruebas de conocimiento cero, o SNARKs). En estos sistemas, un protocolo debe subcontratar tareas computacionales costosas (como generar una prueba de validez para un bloque) a un conjunto de $n$ verificadores pseudónimos y no confiables.

El problema central es diseñar un mecanismo que:

1. Incentive al menos a un verificador a realizar la tarea (garantizando la vivacidad).
2. Minimice la pérdida económica en el peor de los casos, donde hasta $n-h$ verificadores son adversarios (bizantinos) y pueden desviarse del protocolo para causar un fallo de vivacidad (no se entrega prueba) o inducir un sobrepago.
3. Opere sin confianza, ya que los verificadores no tienen reputación y no pueden comprometerse creíblemente a acciones futuras.

Los autores modelan esto como un problema de diseño de mecanismos donde el diseñador del protocolo busca minimizar la suma de los pagos realizados y la penalización $C$ incurrida si no se entrega ninguna prueba, asumiendo que un adversario controla un subconjunto de verificadores y actúa para maximizar la pérdida del protocolo.

Metodología

Los autores formalizan el problema utilizando un marco teórico de juegos:

• Configuración: Hay $n$ verificadores, de los cuales $h$ son honestos. El costo de generar una prueba se normaliza a 1. Si no se produce ninguna prueba, el protocolo incurre en una penalización de vivacidad $C$.
• Modelo de Adversario: El adversario puede corromper hasta $a = n-h$ verificadores. El adversario observa el mecanismo y elige el comportamiento del peor de los casos (ya sea negarse a entregar pruebas para activar la penalización $C$, o entregar pruebas para manipular los pagos).
• Objetivo: Minimizar la pérdida del peor de los casos $\ell(p, s)$, definida como el costo total esperado (pagos + penalización) bajo la estrategia adversaria del peor de los casos, sujeto a la restricción de que el mecanismo sea compatible con incentivos (los verificadores honestos maximizan su utilidad siguiendo el protocolo).

Para hacer el problema tratable, los autores:

1. Derivan una función de cota inferior $g(s)$ sobre la pérdida óptima del protocolo, parametrizada por el vector de estrategia $s$ (la probabilidad de que cada verificador entregue una prueba). Esta cota asume un adversario "debilitado" que elige entre dos estrategias extremas: actuar completamente honesto o negarse completamente a entregar.
2. Analizan los minimizadores de esta cota inferior, caracterizándolos como Equilibrios de Comité Uniforme Designado (un líder determinista + un comité de randomizadores) o Equilibrios de Comité Simétrico (un comité de randomizadores sin líder designado).
3. Investigan la implementabilidad: determinar si existe una regla de pago que induzca estos equilibrios mientras se logra el costo de la cota inferior.
4. Extienden el análisis para incluir pagos negativos (quema/apostamiento), donde los verificadores depositan colateral que puede ser confiscado si el protocolo detecta un ataque.

Contribuciones y Resultados Clave

1. Caracterización de Equilibrios Óptimos

El artículo demuestra que los minimizadores de la cota inferior $g(s)$ son exclusivamente de dos tipos:

• Equilibrios Designados: Un verificador está designado para entregar con probabilidad 1, mientras que un comité de tamaño $k$ entrega con probabilidad $s \in (0, 1)$.
• Equilibrios Simétricos: Un comité de tamaño $k$ entrega con probabilidad $s$, y ningún verificador individual está designado.

2. Garantías de Aproximación

• Aproximación Aditiva 1: Los autores demuestran que para cualquier regla de pago y equilibrio, existe un equilibrio designado cuya pérdida es como máximo 1 unidad (el costo de una sola prueba) superior a la pérdida óptima (Teorema 3.1).
• Implementabilidad: Todos los equilibrios designados son implementables con una regla de pago simple (Lema 3.4). Por el contrario, los equilibrios simétricos solo son implementables bajo condiciones específicas (por ejemplo, cuando $C$ es suficientemente grande en relación con $n$ y $h$), y a menudo requieren estructuras de pago complejas o pagos negativos para ser viables.

3. Escalado Asintótico

• Escalado Logarítmico: La pérdida del peor de los casos del equilibrio designado óptimo escala como $O(\frac{\log C}{\tau})$, donde $\tau = h/n$ es la fracción de verificadores honestos. Esto indica que incluso con una fracción fija de adversarios, el costo del protocolo crece solo logarítmicamente con la severidad de la penalización de vivacidad.
• Impacto del Apostamiento: Introducir un apostamiento total $B$ (colateral) mejora significativamente el escalado. Si $B$ es proporcional a $C$, la pérdida escala como $O(1/\tau)$, volviéndose efectivamente constante en relación con $C$.

4. Dinámicas de Transición

El artículo analiza la transición entre la optimalidad designada y simétrica como función de $C$ (magnitud de la penalización) y $\tau$ (fracción de honestidad).

• Para $C$ pequeña o $\tau$ alta, el mecanismo designado es óptimo.
• Para $C$ muy grande, el mecanismo simétrico se vuelve óptimo en el análisis de la cota inferior.
• Sin embargo, debido a las restricciones de implementabilidad, el mecanismo designado a menudo sigue siendo la opción práctica incluso en regímenes donde la cota inferior simétrica es menor, porque la solución simétrica puede requerir pagos negativos que son inviables o complejos de implementar.

Significado y Recomendaciones Prácticas

El artículo argumenta que los resultados teóricos proporcionan orientación accionable para los diseñadores de protocolos de blockchain, particularmente para zk-EVM (Máquina Virtual Ethereum de Conocimiento Cero) y otros mercados de subcontratación verificable.

• Recomendación: Los autores recomiendan encarecidamente adoptar el equilibrio óptimo de comité uniforme designado. Este diseño designa a un único "líder" (o trabajador principal) para producir la prueba de manera determinista, respaldado por un comité de "respaldos" que producen pruebas con una probabilidad calculada $s$.
• Justificación:
  1. Simplicidad: La regla de pago es intuitiva y se asemeja a los mecanismos de consenso existentes (por ejemplo, consenso basado en líderes con comités de certificación).
  2. Cercanía a la Optimalidad: La pérdida es como máximo un costo de prueba alejada del óptimo teórico, lo cual es despreciable dados los costos actuales de generación de pruebas (a menudo fracciones de un dólar).
  3. Robustez: Maneja efectivamente el comportamiento adversario del peor de los casos, escalando logarítmicamente con la penalización $C$.
  4. Viabilidad: A diferencia de los mecanismos simétricos, que pueden requerir estructuras de pago complejas al estilo de lotería o pagos negativos (quema) para ser óptimos, los mecanismos designados son siempre implementables con pagos positivos.

El artículo concluye que, aunque los mecanismos simétricos son teóricamente interesantes y óptimos en regímenes asintóticos específicos, el mecanismo designado ofrece el mejor equilibrio entre optimalidad teórica, implementabilidad y familiaridad para la comunidad de blockchain. Los autores señalan que su modelo se aplica ampliamente a cualquier problema de delegación sin permiso que involucre fallos de vivacidad, incluyendo inferencia de IA verificable y cálculos basados en TEE.