El problema de los generales bizantinos es uno de los problemas más conocidos y clásicos que enfrentan las redes descentralizadas. Resolver este problema fue uno de los desarrollos clave en la creación de Bitcoin y, por extensión, todas las demás criptomonedas. En este artículo, veremos cuál es el problema de los generales bizantinos y cómo Bitcoin se las arregla para resolver este desconcertante problema.
¿Qué es el consenso bizantino?
El problema de los generales bizantinos fue teorizado por primera vez por los matemáticos Leslie Lamport, Marshall Pease y Robert Shostak. Los generales son una metáfora de los nodos en una red descentralizada. La idea central detrás de este experimento mental es la siguiente: ¿cómo se asegura de que una red distribuida de igual a igual sin una autoridad central pueda tomar decisiones correctas, incluso si algunos de los nodos en ella se vuelven deshonestos? ¿Podemos crear un sistema distribuido que sea “sin confianza” y que no asuma automáticamente que los participantes van a actuar éticamente y trabajarán en interés del grupo?
¿Qué es un ataque bizantino?
Imagina este escenario:
Tenemos un castillo en el medio, que está muy bien abastecido y fortificado.
Los tenientes han rodeado el castillo. El general (simbolizado por la corona) planea lanzar un ataque. Sin embargo, dado que el ejército está tan disperso, el general no tiene un control centralizado.
La única forma en que el castillo podría ser derrotado es si el ejército bizantino lanza un ataque planeado y sincronizado. Si hay alguna falta de comunicación, la infracción fallará.
Hablando de comunicación, la única forma en que los generales pueden sincronizar un ataque es enviando mensajes a través de mensajeros.
Ahora, esto conduce a varios escenarios de falla:
¿Imagina que los mensajeros son traidores y transmiten información contraria a la estrategia del ejército?
¿Supongamos que un mensajero de cada cuatro es un traidor, y que transmite el mensaje de “RETIRO” a algunos tenientes cuando la estrategia real es “ATAQUE”?
¿Qué pasa si el mensajero es capturado por el enemigo y su mensaje es alterado?
Reflexione si algunos de los tenientes bizantinos son traidores y planean traicionar al ejército.
¿Qué pasa si el mismo general es corrupto y busca sembrar la discordia entre los generales?
Con el contexto de las cadenas de bloques, cada teniente es un nodo en la red, y estos nodos deben llegar a un consenso para determinar el estado actual del protocolo. Para que algo suceda, una supermayoría (> 2/3) de la red en un sistema distribuido deberá llegar a un consenso. Lo que esto también significa es que si una gran mayoría de la red es maliciosa (como en el caso de un ataque del 51%), el sistema es vulnerable a fallas.
¿Se puede resolver el problema de los generales bizantinos para 3 nodos?
Una cosa interesante a tener en cuenta sobre los sistemas distribuidos es que más de dos tercios de los participantes deben ser “leales” para que funcione. De hecho, Berkely.edu hizo un interesante experimento mental para comprobar si un sistema con tres nodos puede eludir el problema de los generales bizantinos o no.
NOTA: Este experimento usa el término “comandantes” en lugar de “generales” como lo hemos usado hasta ahora.
El experimento tiene las siguientes suposiciones predefinidas:
Todos los lugartenientes leales obedecerán la misma orden.
Si el comandante es leal, entonces el teniente leal obedece la orden que se les envía.
El contenido del mensaje enviado está completamente bajo el control del remitente.
Solo se pueden enviar dos mensajes: “ataque” o “retirada”.
Caso # 1: Uno de los tenientes es deshonesto
El comandante leal ordena a los tenientes que ataquen.
Dado que el teniente 2 es un traidor, le informa al teniente 1 que recibieron una orden de retirarse.
Sin embargo, dado que declaramos en nuestras suposiciones predefinidas que el teniente honesto obedecería la orden de un comandante, el teniente 1 atacará.
Caso # 2: El comandante es deshonesto
El comandante deshonesto envía mensajes contradictorios a ambos tenientes.
Los tenientes 1 y 2 no tienen idea de que han recibido mensajes diferentes.
Como tal, el teniente 1 atacará, mientras que el teniente 2 se retirará.
En los dos casos definidos anteriormente, el consenso se rompe (el sistema no ataca ni se retira como un todo) porque no logra una mayoría superior a 2/3.
Ahora, hagamos algo divertido. Aumentemos el total de participantes de la red a cuatro agregando un teniente más. [Imágenes tomadas de este artículo]
Vamos a repetir el mismo experimento mental que hicimos antes, pero esta vez vamos a obtener una clara mayoría de 2/3. Entonces, si tres de los cuatro nodos llegan a un consenso, entonces obtendremos una clara mayoría. Exploremos los dos casos que hemos explorado anteriormente del POV del Teniente 2.
Caso # 1: Uno de los tenientes es deshonesto
El teniente 3 (L3) es deshonesto, mientras que todos los demás en la red son honestos.
L3 planea sembrar discordia en la comunidad alimentando a L2 con información falsa.
El comandante honesto da el mensaje “v” a todos los tenientes.
L1 envía el mensaje “v” a L2.
L3 intenta confundir a L2 enviando el mensaje “x”.
L2 recibe los siguientes mensajes: (v, v, x). Al obtener una mayoría de 2/3, L2 concluye que el mensaje correcto es “v”.
Como puede ver, la mayoría de 2/3 permite que el sistema sea tolerante a fallas bizantino. Entonces, incluso si uno de los nodos se corrompe, todo el sistema aún puede funcionar.
Caso # 2: El comandante es deshonesto
Ahora, aquí es donde las cosas se complican un poco. ¿Qué pasa si el centro de mando de este sistema general está corrupto? Veamos qué pasa:
El comandante corrupto envía diferentes mensajes x, y, z a L1, L2 y L3, respectivamente.
Como los tenientes son todos honestos, según las condiciones predefinidas, ya que creen que el comandante es honesto, transmitirán el mensaje palabra por palabra.
Después de que todos los nodos hayan transferido sus mensajes, cada nodo recibirá (x, y, z).
Por la regla de la mayoría, el consenso final será una mayoría (x, y, z). Dado que esta mayoría es consistente entre todos los nodos, el sistema se vuelve tolerante a fallas.
Ahora que tenemos una comprensión básica del mecanismo, vayamos un paso más allá.
El algoritmo de generales bizantinos de Lamport, Pease y Shostak
Cuando Lamport, Pease y Shostak identificaron el problema por primera vez, crearon un algoritmo para mitigar este problema. El algoritmo asume que:
Hay n nodos totales.
Hay m nodos maliciosos.
N> 3 m, lo que garantiza que se mantenga una mayoría de 2/3.
El algoritmo tiene dos etapas:
Etapa 1: Esta es la etapa de recopilación de datos, que tiene rondas m + 1. Durante esta etapa, los nodos envían y reciben mensajes continuamente.
Etapa 2: esta es la etapa de toma de decisiones. Sobre la base de los datos recopilados en la etapa 1, el sistema, en su conjunto, toma una decisión.
Ahora, echemos un vistazo a cómo funciona esto en la práctica. Observaremos un sistema con un general corrupto (P1) y seis tenientes honestos (P2-P7).
Nota: Las imágenes utilizadas en las secciones de la Etapa 1 y la Etapa 2 a continuación se han tomado de este artículo.
Etapa 1: recopilación de datos
En la primera etapa, el algoritmo realiza rondas de mensajería m + 1 entre los nodos:
El general corrupto P0 envía órdenes a sus lugartenientes. El general no envía más mensajes después de esta ronda y tampoco recibe ningún mensaje.
Dado que solo hay un elemento malicioso (m), el algoritmo se ejecutará durante m + 1 = 2 rondas.
El comandante da un valor “0” a los tenientes P2, P3 y P4. Por otro lado, P5, P6 y P7 reciben el valor “1”. Esto sucede en la Ronda 0.
En las rondas restantes, cada teniente crea un lote de mensajes, que consiste en el valor y una ruta. Entonces, {0,12} -> significa que P1 ha enviado un mensaje a P2 con el valor “0”.
Entonces, al final de la ronda 1, los mensajes recibidos se ven así:
Ahora, veamos lo que sucede al final de la ronda 2:
Cada nodo tenía seis mensajes cada uno al final de la ronda 1. En la segunda ronda, cada nodo volverá a enviar estos seis mensajes a los seis nodos, lo que significa que cada nodo envía 36 mensajes en la segunda ronda.
Durante la primera ronda, P2 recibió los siguientes mensajes: {0,12}, {0,13}, {0,14}, {1,15}, {1,16} y {1,17}.
En esta nueva tupla, {0,132} se leerá así: P2 dice que en la ronda 1, llegó a saber que P3 recibió el valor “0” en la ronda 0.
Ahora, P2 enviará cada uno de estos mensajes a todos los tenientes, lo que significa que las nuevas salidas de P2 serán: 0,122}, {0,132}, {0,142}, {1,152}, {1,162} y {1,172} . {0,122} es redundante, por lo que significa que P2 está hablando consigo mismo. Entonces, se cancela.
Etapa 2: Toma de decisiones
Cada nodo acumula varios mensajes al final de cada ronda. Los mensajes dentro de cada nodo se almacenan en formato de árbol. Aquí hay algunas propiedades del árbol que debe tener en cuenta:
Cada ronda de mensajes ocupa un rango correspondiente dentro del árbol.
Cada componente del árbol tiene tres puntos de datos: un valor de entrada, una ruta y un valor de salida.
Durante la Etapa 1, ya identificamos el valor de entrada y la ruta. Determinaremos el valor de salida, también conocido como el valor que el sistema acuerda mediante una mayoría de 2/3 en la etapa 2.
El siguiente diagrama es la representación en árbol de un sistema con seis nodos generales con cinco lugartenientes honestos y un general corrupto.
Etapa 2: Representación del árbol
Este árbol tiene las siguientes características:
La parte de salida en cada conjunto de datos, también conocido como el tercer valor en el conjunto de datos, se ha establecido inicialmente en “?”. Esto se debe a que aún no conocemos el valor de salida de la red.
Dado que solo hay un elemento malicioso (m), habrá dos rondas de mensajería (m + 1). Es por eso que el árbol que se muestra arriba tiene dos niveles.
En la primera ronda, el general envía un valor al teniente. En la segunda ronda, cada teniente transmite el valor recibido entre sí.
Cada nodo hoja copia su valor de entrada a su valor de salida. El valor que ocurre con mayor frecuencia se asigna al nivel superior.
Este proceso continúa hasta que se asigna un valor mayoritario a todo el árbol.
En la imagen de arriba, los valores de entrada de los nodos hoja son {1,1,1,0,0}. Debido a que el valor mayoritario es “1”, se determina que el valor de salida del nivel superior, también conocido como nivel 0, es “1”.
Teniendo en cuenta que no hay otros niveles más allá de eso, el valor de salida general de un árbol de tenientes en particular es “1”
En el sistema, todos los tenientes son honestos, todos obtendrán el mismo valor de salida: “1”. Entonces, incluso si el general es deshonesto, los tenientes aún estarán de acuerdo en el mismo valor, volviéndose tolerantes a las fallas bizantinas.
¿Cómo Blockchain resuelve el problema de los generales bizantinos?
Ahora, miremos más allá de los generales y las metáforas de la guerra y comprendamos este problema con respecto a las cadenas de bloques y las criptomonedas. Uno de los temas fundamentales que debe resolver un sistema de pagos descentralizado es el tema del “doble gasto”.
Cuando un usuario gasta la misma instancia de una criptomoneda más de una vez, se conoce como problema de doble gasto. Para tener una idea más clara de esto, imagine gastar el mismo billete de $ 10 para realizar dos transacciones diferentes al mismo tiempo. Como puede imaginar, esto es imposible en transacciones basadas en efectivo. Sin embargo, para las monedas digitales, esta es una posibilidad real. No siempre podemos confiar en que los usuarios actúen en interés del sistema. Los ataques repetidos de doble gasto pueden hacer que todo el sistema sea irrelevante.
Entonces, ¿cómo se evita el problema de los generales y el doble gasto? La solución está en los algoritmos de consenso bizantinos tolerantes a fallas.
¿Qué es un algoritmo de tolerancia a fallas bizantino?
La tolerancia a fallas bizantina significa que el algoritmo debe permitir que el sistema tome una decisión coherente y uniforme, incluso si hay algunos elementos corruptos presentes en la red. La forma en que lo hace es buscando el consenso dentro del grupo distribuido. El consenso es un proceso dinámico para lograr un acuerdo dentro de un grupo, y el método con el que pueden llegar a un consenso se conoce como “mecanismo de consenso”.
Las propiedades de un mecanismo de consenso ideal son las siguientes:
Debe procurar lograr el mayor acuerdo posible del grupo.
Todos los participantes deben colaborar para lograr la mejor solución posible para la mayoría.
El voto de cada participante debe tener la misma ponderación.
La mayor cantidad de personas posible debe participar en el proceso para que se dirija a la verdadera mayoría.
Antes de Bitcoin, hubo varios intentos de crear una moneda digital descentralizada como DigiCash de David Chaum, B-Money de Wei Dai y Bit Gold de Nick Szabo. Sin embargo, todos fallaron porque no pudieron implementar con éxito un algoritmo tolerante a fallas de los generales bizantinos. Cuando Satoshi Nakamoto creó Bitcoin, mitigó este problema al integrar el protocolo con una clase especial de mecanismos de consenso llamado “Consenso de Nakamoto”.
¿Cuál es la solución al problema de los generales bizantinos y cómo aborda el doble gasto?
En términos simples, en el consenso de Nakamoto, los nodos deben tener algo de “piel en el juego” para incentivarlos a participar honestamente en el sistema. El consenso de Nakamoto utilizado en Bitcoin se llama “prueba de trabajo (POW)”, también conocido como “minería”. En este sistema, los participantes o “mineros” gastan una gran cantidad de recursos informáticos para resolver acertijos criptográficamente difíciles. Este gasto de recursos también se conoce como “trabajo”. Esta es la piel que tienen los mineros en el juego.
¿Cómo extraer criptomonedas?
Así es como funciona el proceso de minería:
La red distribuida acuerda una métrica llamada “dificultad”. El valor de esta métrica cambia según la facilidad de extracción dentro del sistema.
Los mineros recogen las transacciones que están esperando en el mempool y las ensamblan en un bloque.
El contenido del bloque tiene hash.
Se agrega un valor hexadecimal pseudoaleatorio llamado “nonce” desde el hash y el valor general se vuelve a agregar al hash.
A continuación, este valor se compara con la dificultad. Si el valor es menor que la dificultad, la red acepta el bloque y lo agrega a la cadena de bloques principal. A cambio, el minero recibe una recompensa en bloque.
Si el valor hash es mayor que la dificultad, el minero elige un nuevo nonce y el proceso se repite hasta encontrar un valor menor que la dificultad.
Este proceso de encontrar el nonce y compararlo con la dificultad es extremadamente difícil (especialmente en Bitcoin) y requiere mucha potencia computacional.
POW con respecto al ejército bizantino
Ahora, recuperemos el problema de los generales bizantinos y veamos cómo POW mitiga el problema original.
El general y su ejército deciden una métrica de dificultad. Supongamos que esta métrica establece que el valor hash final debe ser menor que “00001000”.
El general crea un mensaje y lo codifica hasta que el valor es menor que la métrica de dificultad.
El general luego pasa el nonce, el mensaje y el valor hash final al mensajero y les dice que se lo transmitan a los tenientes.
Si el mensajero intenta alterar el mensaje, el hash final cambiará drásticamente. Esta es una de las propiedades de las funciones hash criptográficas llamadas “efecto bola de nieve”. La idea es que un ligero cambio en la entrada puede provocar un cambio drástico en la salida.
La única otra opción que tienen los traidores es encontrar otro nonce que resulte en un hash final que sea menor que la métrica de dificultad. Como ya sabemos que se trata de un proceso que consume muchos recursos, los traidores no podrán encontrar un nuevo hash.
Cuando los tenientes reciben el mensaje, pueden probar fácilmente la validez del mismo mediante el hash del nonce y el mensaje y cotejándolo con el hash final proporcionado. Esta es la teoría central detrás de POW: el proceso de obtención del hachís es difícil; sin embargo, comprobar la validez de la solución es sencillo.
Lidiar con el doble gasto
Ahora, veamos cómo Bitcoin utiliza la cadena de bloques para remediar el doble gasto. Suponga que Alice tiene 1 BTC y quiere enviarlo a dos direcciones públicas simultáneamente. Ambas transacciones terminan en el mempool, después de lo cual ocurre una de las siguientes situaciones:
La primera transacción que recibe suficiente confirmación se acepta en el bloque. La segunda transacción se reconoce como inválida.
Si ambas transacciones se extraen simultáneamente del mempool, la que tiene la mayor cantidad de confirmación se incluye en la cadena de bloques.
Cabe señalar que el algoritmo POW no es bizantino tolerante a fallas debido a alguna magia matemática o algorítmica. Es seguro solo porque el proceso de minería en sí es extremadamente caro. Para un atacante hacerse cargo de más del 50% del poder de hash de la red, le costaría la friolera de $ 1.4 mil millones. Incluso si alguien logra obtener tanto poder de hash y realiza un ataque del 51% y comienza a gastar el doble de monedas, se devaluará instantáneamente. Entonces:
El ataque en sí es extremadamente caro.
La recompensa posterior será comparativamente insignificante.
Resumen del problema de los generales bizantinos
Bitcoin logra una tolerancia a fallas bizantina a través de su algoritmo POW y mitiga hábilmente las trampas tradicionales de los sistemas descentralizados. Al incentivar económicamente a los mineros asegurándose de que tengan algo de piel en el juego, Bitcoin se ha asegurado de que su protocolo sea lo más seguro posible. Al resolver este dilema, tanto Satoshi Nakamoto como Bitcoin nos han introducido en el fenómeno de cambio de juego conocido como economía descentralizada. Desde entonces, han surgido varios otros algoritmos de consenso como Prueba de participación (POS), Prueba de participación delegada (DPOS), etc., que no son tan inútiles como POW.
A medida que los casos de uso y las innovaciones continúen creciendo, las criptomonedas y la tecnología blockchain dejarán una marca indeleble en las finanzas globales. Ahora más que nunca, debe hacer todo lo posible para equiparse con el mayor conocimiento posible sobre este espacio. En Ivan on Tech Academy, tenemos varios cursos acreditados de alto valor sobre blockchain y criptomonedas que han sido creados por nuestros entrenadores internos y expertos de la industria. La información proporcionada en los cursos es apta para principiantes y lo preparará para la fuerza laboral en una industria que se ha convertido en uno de los sectores de más rápido crecimiento en el mundo actual. Si desea saber más sobre estos cursos, haga clic aquí.
