El problema del gasto doble y los generales bizantinos

Curiosidad

1. Si un archivo digital puede copiarse perfecta e instantáneamente, ¿qué impide que se utilice dos veces?
2. ¿Cómo puede un grupo de extraños sin una identidad compartida ponerse de acuerdo sobre una única historia sin un líder que arbitre las disputas?
3. ¿Qué hace que un voto en una red abierta sea más valioso que la palabra de otra persona?

Explorar

1. Un token digital no es más que un archivo. A diferencia del efectivo físico, puede duplicarse bit a bit sin costo alguno y sin degradación. Si Alice envía diez unidades a Bob, ella conserva el archivo original y puede enviar esas mismas diez unidades a Charlie simultáneamente. Hasta 2008, todos los sistemas de dinero digital funcionales dependían de un emisor de confianza: los esquemas en línea verificaban cada pago de forma centralizada, mientras que los esquemas fuera de línea solo podían identificar a quienes realizaban gastos dobles después de los hechos.
2. DigiCash, de David Chaum, requería que cada beneficiario depositara monedas en el banco, el cual verificaba cada número de serie contra su lista de monedas ya gastadas. Las Pruebas Reutilizables de Trabajo (Reusable Proofs of Work) de Hal Finney se basaban en un único servidor que ejecutaba código de código abierto en hardware seguro para rastrear los tokens ya empleados. b-money, de Wei Dai, proponía servidores que publicaban depósitos y podían ser multados por trampa, pero nunca llegó a implementarse. Cada diseño mantenía una parte de confianza o un grupo conocido en su centro.
3. En 1982, Leslie Lamport, Robert Shostak y Marshall Pease formalizaron el Problema de los Generales Bizantinos en ACM Transactions on Programming Languages and Systems. Los generales que rodean una ciudad deben acordar si atacar o retirarse, pero algunos generales son traidores que envían mensajes contradictorios; los mensajeros en sí mismos son fiables. Con mensajes sin firmar, el acuerdo solo es posible si menos de un tercio de los generales son traidores (n ≥ 3f+1); con un tercio o más, ningún protocolo puede garantizarlo.
4. Los protocolos clásicos tolerantes a fallos como PBFT requieren un conjunto conocido y fijo de participantes. Esto funciona para los libros contables internos de los bancos, pero falla en redes abiertas donde cualquiera puede unirse. John Douceur identificó el ataque Sybil en 2002: un adversario puede generar identidades falsas ilimitadas para diluir los votos honestos o controlar los quórumes. En una red peer-to-peer abierta, la identidad es barata e infinita, por lo que cualquier esquema que cuente las identidades puede ser tomado por un único actor.
5. El whitepaper de Satoshi Nakamoto abordó esto directamente. Su resumen presenta a Bitcoin como una solución al gasto doble sin necesidad de un tercero de confianza. En lugar de depender de la identidad o de la confianza institucional, el sistema vincula cada bloque con una prueba de trabajo acumulativa. Los votos están ponderados por el cómputo realizado, lo cual no puede multiplicarse inventando identidades; un atacante debe superar en capacidad de cálculo a la red honesta para reescribir la historia.
6. El resultado es una finalización probabilística. Una transacción no es permanentemente definitiva en sentido matemático, pero se vuelve cada vez más segura a medida que cada nuevo bloque extiende la cadena. Mientras un atacante controle menos de la mitad del poder de hash, la probabilidad de reversión disminuye exponencialmente con cada confirmación. Este compromiso acepta la posibilidad teórica de reversión para lograr una inmutabilidad práctica sin control centralizado. Abre un explorador de bloques y observa cómo el trabajo acumulado crece con cada altura de bloque; este costo acumulativo es lo que ancla el libro mayor a la realidad física.

Datos clave

Ejercicio nueve, seis, tres, uno

Verificación de hechos

Fechas, cifras y afirmaciones verificadas con las fuentes publicadas que se enumeran a continuación.

• L. Lamport, R. Shostak, M. Pease, 'The Byzantine Generals Problem', ACM TOPLAS (1982)
• J. Douceur, 'The Sybil Attack', Peer-to-Peer Systems (2002)
• S. Nakamoto, 'Bitcoin: A Peer-to-Peer Electronic Cash System' (2008)
• M. Castro & B. Liskov, 'Practical Byzantine Fault Tolerance', OSDI (1999)