Rigorous and Generalized Proof of Security of Bitcoin Protocol with Bounded Network Delay

Resumen Técnico: Prueba Rigurosa y Generalizada de la Seguridad del Protocolo Bitcoin con Retardo de Red Acotado

1. Planteamiento del Problema

El protocolo Bitcoin, introducido por Satoshi Nakamoto, garantiza su seguridad asumiendo que los nodos honestos poseen más del 50% del poder de hash. Sin embargo, la seguridad formal de este protocolo frente a ataques sofisticados (como la minería egoísta o ataques de balance) en modelos de red con retardos ha sido objeto de debate y análisis incompleto en la literatura previa.

Los problemas específicos que aborda este trabajo son:

• Errores en pruebas anteriores: La prueba presentada en el trabajo [7] (concurrente con [8]) contenía un error fundamental: asumía incorrectamente que la diferencia entre la longitud de la cadena del adversario y la de los nodos honestos seguía un paseo aleatorio (random walk). El artículo demuestra mediante un contraejemplo que esta suposición es falsa.
• Falta de generalización: Las pruebas existentes a menudo se limitan al modelo de Bitcoin estándar donde todos los bloques tienen el mismo valor. No abordaban modelos donde los bloques pueden tener diferentes puntuaciones (scores), lo cual es crucial para protocolos derivados como Merged Bitcoin.
• Complejidad y falta de intuición: Las pruebas alternativas (como la de [8]) son largas y poco intuitivas, dificultando su verificación y aplicación a nuevos protocolos.

El objetivo es proporcionar una prueba rigurosa, simplificada y generalizada que demuestre que, bajo un modelo de red con retardo acotado ($\Delta$), el protocolo es seguro si la tasa de crecimiento de puntuación de los bloques honestos supera a la del adversario.

2. Metodología y Modelo

A. Modelo de Red con Retardo Acotado ($\Delta$-bounded delay)

• Se considera un modelo donde un adversario puede retrasar la transmisión de bloques honestos hasta un tiempo $\Delta$.
• El adversario también puede retrasar sus propios bloques, pero una vez que un bloque es transmitido a un minero honesto, la información se propaga a todos los demás con un retraso máximo de $\Delta$.
• Este modelo simula una red asíncrona donde los mineros honestos transmiten constantemente su visión de la cadena.

B. Generalización del Protocolo

• Se permite que los mineros (honestos y deshonestos) generen bloques de diferentes tipos, donde cada tipo tiene un puntuación (score) $c_i > 0$.
• La regla de elección de la cadena (fork-choice rule) es minar sobre la cadena con la puntuación total más alta, no necesariamente la más larga en número de bloques.
• Se definen las tasas de crecimiento de puntuación:
  • $\lambda_h$: Tasa de crecimiento de puntuación de los bloques honestos bajo retardo completo (peor caso).
  • $\lambda_a$: Tasa de crecimiento de puntuación de los bloques del adversario.

C. Nuevas Herramientas Analíticas

• Rechazo del Paseo Aleatorio: Se demuestra que el proceso de diferencia de longitudes no es un paseo aleatorio, invalidando la técnica usada en [7].
• Proceso de Llegada "Percutido" (Punctured Arrival Process): Para remediar el error, los autores introducen un proceso donde se eliminan (percuten) bloques en intervalos de tiempo específicos ($\Delta$) para crear un proceso de llegada que sí constituye un verdadero paseo aleatorio. Esto permite aplicar teoremas robustos de teoría de paseos aleatorios.
• Intervalos Nakamoto: Se redefine el concepto de "bloque Nakamoto" como un bloque honesto que cae dentro de un "intervalo Nakamoto" (un intervalo de tiempo $2q$ donde ocurre un bloque honesto aislado, sin bloques honestos cercanos ni bloques del adversario en ventanas de tiempo extendidas).

3. Contribuciones Clave

1. Corrección de un Error Fundamental: Se identifica y corrige la suposición errónea sobre los paseos aleatorios en la literatura previa, utilizando un proceso de llegada percutido para garantizar la independencia y la distribución idéntica de las variables aleatorias necesarias para la prueba.
2. Generalización del Modelo: La prueba se extiende a un modelo de múltiples tipos de bloques con puntuaciones variables. Esto hace que la prueba sea aplicable no solo a Bitcoin, sino también a variantes como Merged Bitcoin.
3. Simplificación y Rigor: Se ofrece una prueba más intuitiva y autocontenida que evita la complejidad de enfoques anteriores, utilizando un argumento de inducción y propiedades de procesos de Poisson.
4. Definición de la Región de Seguridad: Se establece formalmente que la condición de seguridad es $\lambda_a < \lambda_h$. Es decir, la tasa de crecimiento de puntuación del adversario debe ser estrictamente menor que la tasa de crecimiento de puntuación de los nodos honestos bajo el peor escenario de retardo.

4. Resultados Principales

• Lema de Crecimiento Mínimo: Se demuestra que la puntuación de la cadena honesta más alta crece al menos tan rápido como la "cadena honesta totalmente retrasada" (donde todos los bloques honestos sufren el retardo máximo $\Delta$).
• Existencia de Bloques Nakamoto: Se prueba que, si $\lambda_h > \lambda_a$, existe una probabilidad estrictamente mayor a cero de que cualquier intervalo de tiempo contenga un "bloque Nakamoto".
• Persistencia en la Cadena: Se demuestra que un bloque Nakamoto, una vez generado, permanecerá en la cadena canónica para siempre. Esto se debe a que, en el momento de su generación y en el futuro, la cadena honesta domina a cualquier cadena alternativa del adversario debido a la diferencia en las tasas de crecimiento de puntuación.
• Teorema Principal (Convergencia a 1): Mediante un argumento de "bootstrap" (inducción sobre intervalos de tiempo), se demuestra que la probabilidad de que un intervalo de tiempo $t$ no contenga bloques honestos permanentes decae exponencialmente con $t$.
  • Corolario: Si $\lambda_h > \lambda_a$, la probabilidad de que existan infinitos bloques honestos en la cadena canónica es 1 (casi seguro).
• Región de Inseguridad: Se demuestra que si $\lambda_a > \lambda_h$, el protocolo es inseguro y un adversario puede ejecutar un ataque de minería privada para dominar la cadena canónica con probabilidad 1.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

• Fundamento Teórico Sólido: Proporciona la primera prueba rigurosa y libre de errores de la seguridad de Bitcoin bajo un modelo de red con retardos acotados, corrigiendo fallos críticos en trabajos previos.
• Aplicabilidad a Futuros Protocolos: Al generalizar el modelo para incluir bloques con diferentes puntuaciones, la prueba sirve como base teórica para protocolos avanzados como Merged Bitcoin, asegurando que sus variantes hereden la propiedad de seguridad.
• Claridad Metodológica: La introducción del "proceso de llegada percutido" ofrece una nueva herramienta matemática para analizar sistemas distribuidos asíncronos, evitando las trampas de asumir propiedades de paseo aleatorio donde no existen.
• Condiciones de Seguridad Precisas: Define claramente el límite de seguridad ($\lambda_a < \lambda_h$), lo cual es crucial para la configuración de parámetros de red y la evaluación de la resistencia de la red ante ataques de latencia.

En conclusión, el artículo cierra una brecha importante en la criptografía teórica de blockchain, validando la robustez de Bitcoin y sus derivados frente a adversarios con capacidad de retraso de red, siempre que la mayoría del poder de hash (ponderado por puntuación) permanezca en manos honestas.