Introducción
Los sistemas informáticos tienen componentes que por una razón u otra pueden llegar a fallar y presentar un comportamiento inestable, en particular, en la blockchain, tenemos una red de nodos de los cuales depende el consenso y la validación de las transacciones que ocurren dentro de la misma. Dichos nodos al ser en muchos casos usuarios del sistema pueden llegar a presentar un comportamiento mal intencionado, proveyendo datos falsos a la red con el fin de evitar el consenso o de generar un acuerdo favorable a sus propios beneficios.
Es necesario entonces pensar en un algoritmo que permita el funcionamiento del sistema con la tolerancia más grande posible a las fallas de los nodos, por lo cual vamos a formular un problema equivalente que nos sea más cómodo resolver.
Licensed under Creative Commons Attribution-Share Alike 4.0 International license. Link
Planteamiento del problema
(este problema es totalmente equivalente al de los generales bizantinos):
- Todos los mensajes enviados llegan a su destino
- Quien recibe el mensaje sabe quien lo envía
- La ausencia de un mensaje puede ser detectada
El dueño de la empresa a decidido que uno de los directivos elegido al azar decidirá entre un proyecto A o un proyecto B, que se debe llevar a cabo para salvar a la compañía de la quiebra. Con el fin de maximizar la probabilidad de éxito del proyecto es necesario pensar en un algoritmo que garantice que:
I. Todos los gerentes leales ejecutan el mismo proyecto
II. Si el directivo que propone el proyecto es leal, entonces todos los gerentes leales siguen el proyecto que él propone.
Es importante notar que si nuestro algoritmo cumple II entonces se maximiza la probabilidad de éxito del proyecto debido a que todas las sucursales que contribuirán a su buen desenvolvimiento serán capaces de coordinar y ponerse de acuerdo entre sí, además II implica I.
La condición I garantiza que uno de los planes será ejecutado con total participación de los gerentes leales, lo cual nuevamente maximiza su probabilidad de éxito y además ayuda a identificar a los infiltrados quienes actúan en muchos casos de manera distinta.
(Las propiedades 1,2,3 definen a los “mensajes orales” en el problema de los generales bizantinos mientras que las condiciones I y II son llamadas condiciones de consistencia interactiva, ambos conceptos fueron definidos en el paper de Leslie Lamport, Robert Shostak, y Marshall Pease titulado The Bizantine Generals Problem)
En la búsqueda del algoritmo
Limitaciones
A simple vista se puede llegar a pensar que el algoritmo que buscamos es capaz de funcionar con la mitad o incluso más de los ejecutivos infiltrados, sin embargo no existe un algoritmo que funcione con mensajes orales capaz de garantizar que se cumplan las condiciones I y II con m infiltrados y menos de 3m ejecutivos la demostración de esta proposición se puede encontrar en el paper The Bizantine Generals Problem antes mencionado, y no tengo intención de publicarla por este medio, sin embargo en mi afán por hacer de este post algo más serio realicé una demostración (con errores lógicos) bastante interesante que podría entretener a todos aquellos amantes de la ciencia que quieran corregirme y a la vez pensar un rato sobre este tema, dejare dicha demostración en mi siguiente post.
Volviendo a hablar sobre la blockchain, la proposición descrita en el párrafo de arriba nos dice que si utilizamos mensajes que cumplan solo 1),2) y 3) para comunicar a los nodos de la red entonces es necesario garantizar que menos de 1/3 de ellos sean corruptos, de otra manera será imposible proporcionar un consenso confiable, veremos en el siguiente post que existe una manera de mejorar estos resultados utilizando otro tipo de mensajes conocidos como “mensajes firmados”, para el caso que tratamos hoy Leslie Lamport, Robert Shostak y Marshall Pease encontraron el siglo pasado un algoritmo capaz de cumplir las condiciones I y II para m infiltrados y 3m+1 ejecutivos, en otras palabras fue demostrado que el problema tiene solución bajo esas condiciones y ademas son las peores condiciones para las que se puede resolver de forma teórica.
Solución y bitcoin
Referencias
Leslie Lamport, Robert Shostak y Marshall Pease. Bizantine Generals Problems. ACM Transactions on Programming Languages and Systems, Julio 1982.
Cristina Perez-Solà, Jordi Herrera-Joancomartí, Bitcoins y el problema de los generales bizantinos. RECSI 2014. Febrero 2014