Introducción

Al ver la iniciativa del usuario jasb de Steemit de realizar una investigación cuyo fin último sea el desarrollo de una blockchain he quedado encantado y muy motivado a participar en este proyecto, ya que el poder participar en una investigación científica seria, que permita la creación de algo útil a la sociedad fue en principio la razón por la que me uní a Steemit, y con una blockchain existen muchos procesos que pueden ser automatizados de una forma confiable y segura. Este post va dirigido tanto a aquellas personas interesadas en la blockchain que quieran unirse a nosotros en esta aventura como a todos aquellos curiosos o amantes de la ciencia, que quieran pensar un rato sobre temas interesantes o simplemente aprender cosas nuevas. # 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.

# https://cdn.steemitimages.com/DQmRLJCm4dsGFy5CeDyrxfRfgUJrzo6LsVQMfr1ts9qTUcR/Blockchain_Black.jpg ###### Licensed under Creative Commons Attribution-Share Alike 4.0 International license. [Link](https://commons.wikimedia.org/wiki/File:Blockchain_Black.jpg) #

Planteamiento del problema

(este problema es totalmente equivalente al de los generales bizantinos):

#

Imaginemos que una empresa con un gran número de sucursales se encuentra en un problema financiero y desea ejecutar un nuevo proyecto, para ello necesitan ponerse de acuerdo y ejecutar un mismo plan de acción al día siguiente. Sin embargo se cree que una empresa rival ha infiltrado en algunas sucursales y entre los directivos a algunos de sus integrantes con el fin de arruinar el proyecto, además de ello, debido a la urgencia de la operación los gerentes y directivos solo pueden comunicarse por correo electrónico, podemos asumir además que este medio cumple con las siguientes propiedades: # 1) Todos los mensajes enviados llegan a su destino 2) Quien recibe el mensaje sabe quien lo envía 3) 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) # https://cdn.steemitimages.com/DQmabfCwLKMkQHnSt4PDUcUxSY6jHcrCyv572qK1wBqs5dM/Minimal-Negro.png

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

A pesar de que una solución al problema fue propuesta el siglo pasado, no fue sino hasta el invento de la blockchain cuando se le asignó su primera aplicación práctica, en este caso para que el protocolo de consenso conocido como Proof of Work funcione es necesario intercomunicar muchas computadoras entre sí, sin la supervision de una estructura central que las regule, estas computadoras pasan a simular el comportamiento de los gerentes, algunos de ellos serán "infiltrados" y los llamaremos así si por motivos malintencionados o fallas técnicas proporcionan datos que no contribuyan al buen funcionamiento del sistema. Por ejemplo, Imaginemos que la Sra Martha quiere enviar 700 btc al Sr Juan, pero sólo tiene 500 btc en su billetera, sin embargo la Sra Martha es una experta en computación y además tiene a muchos amigos dentro de la red, entonces decide emitir una transacción por 700 btc de todas formas, al no existir un ente central que regule este proceso quienes deciden si esta transacción es válida o no son los nodos de la red, en este caso Martha representa a nuestro Directivo infiltrado que emite un mensaje falso, los gerentes leales serán aquellos nodos que se darán cuenta de que la transacción es inválida mientras que los gerentes infiltrados serán los amigos de Martha quienes buscan apoyarla en su cometido. Por toda la teoría que vimos antes, es evidente que Martha no triunfará en su cometido a menos que conozca a 1/3 o mas personas de la red, y aunque los conozca no podemos estar seguros de que lo tendrá.

https://cdn.steemitimages.com/DQmabfCwLKMkQHnSt4PDUcUxSY6jHcrCyv572qK1wBqs5dM/Minimal-Negro.png

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