La máquina de la confianza – La Tangle Un Protocolo de Votación Generalizado Digital

286

Diseñando la capa de confianza de la humanidad para el mundo

En la última entrega de nuestra serie de blogs introdujimos un nuevo modelo de ledger que permite a los nodos comprender las relaciones causales entre los conflictos. En esta parte vamos a ampliar los modelos teóricos utilizados para describir los sistemas distribuidos con una nueva primitiva -el protocolo de votación generalizado- y, a continuación, proporcionaremos la especificación de una instancia de esta primitiva, que utiliza la libertad recién adquirida para lograr el rendimiento óptimo del protocolo.

Modelo teórico

En un intento de desarrollar un modelo teórico de los componentes utilizados en los sistemas distribuidos, el campo de la investigación en computación distribuida ha identificado una colección de bloques de construcción fundamentales.

Estas primitivas de computación distribuida son abstracciones generalizadas de alto nivel de los protocolos que son completamente agnósticas a su diseño e implementación real.
Esta abstracción no sólo permite a los investigadores comparar y estudiar el rendimiento de diferentes soluciones que resuelven un problema similar, sino que también permite crear software modular, en el que los elementos individuales del sistema pueden intercambiarse cuando se dispone de nuevas y mejores soluciones.

Transmisión atómica

Una de las primitivas más destacadas de la informática distribuida, relacionada con el campo del consenso, es la difusión atómica.
Describe un protocolo que garantiza que todos los nodos de una red distribuida reciban el mismo conjunto de mensajes -por tanto, la difusión- exactamente en el mismo orden. Se llama atómica porque el protocolo puede tener éxito en todos los participantes o detenerse para todos ellos.

Nota: Hay varios protocolos diferentes que implementan esta primitiva, pero los más destacados son probablemente Hashgraph y HoneyBadger.

Votación generalizada

Ya hemos hablado de cómo el establecimiento de un orden total es directamente responsable de las limitaciones de las DLTs contemporáneas y, por tanto, queremos proponer una primitiva diferente, más generalizada, que no dependa de un orden total.
Llamamos a esta primitiva votación generalizada y describe un protocolo que garantiza que todos los participantes en una red distribuida reciban finalmente el mismo conjunto de mensajes y, en presencia de conflictos en estos mensajes, decidan finalmente por una única versión de la verdad.

Esta primitiva es lo suficientemente genérica como para cubrir todas las formas de consenso (incluyendo el diseño original de la blockchain de Satoshi) lo que es un buen indicador de que es una primitiva verdadera.

Nota: El protocolo de transmisión atómica resulta ser una versión especializada del protocolo de votación generalizado y, por tanto, «no es realmente» una verdadera primitiva, ya que hace suposiciones sobre el diseño subyacente (concretamente, resolver conflictos estableciendo un orden total).

Después de haber introducido los fundamentos teóricos de nuestro nuevo protocolo de votación, continuaremos proporcionando las partes que faltan de la especificación.
Introduciremos los conceptos paso a paso de forma ascendente, empezando por la capa de red y ampliando después los conceptos para cubrir también el consenso.

Capa de red

Al igual que en otras DLT, utilizamos una red de pares en la que los nodos se comunican con un número fijo de vecinos.

El nodo verde tiene 5 vecinos

La selección de los vecinos puede realizarse a través de un peering mutuo manual, utilizando un descubrimiento automático de pares o una combinación de ambos.

Nota: IOTA proporciona una estrategia de peering por defecto que permite a los nodos encontrar vecinos automáticamente y sin intervención del usuario.

Protocolo Gossip

Dado que nuestro protocolo se basa en los principios de la contabilidad de entrada cuádruple, escribir en el ledger es tan fácil como transmitir una transacción a la red.

Así, un nodo que quiere emitir una transacción, envía un mensaje con la transacción a todos sus vecinos, que actualizarán su libro de contabilidad y transmitirán el mensaje recursivamente.

Los nodos intercambian mensajes con transacciones

Esta forma de comunicación se denomina protocolo gossip y, dado que se basa en el intercambio de información con sólo una cantidad fija de vecinos, se adapta a una cantidad ilimitada de participantes.

Tolerancia a los fallos

Hasta ahora nuestro protocolo es escalable, pero todavía no es fiable, ya que hay varias situaciones que pueden impedir que un nodo reciba todos los mensajes (por ejemplo, si está desconectado o tiene un mal funcionamiento).

Para resolver este problema, vamos a utilizar la idea de Satoshi Nakamoto de hacer que los mensajes formen un DAG (Grafo Acíclico Dirigido), donde los mensajes posteriores hacen referencia a los anteriores. A diferencia de una cadena de bloques en la que cada bloque hace referencia a un solo bloque, un mensaje en IOTA hace referencia a dos padres, lo que nos permite deshacernos de la necesidad de establecer un orden total.

cada mensaje referencia a dos mensajes anteriores

 

Un nodo que recibe un mensaje que hace referencia a un padre desconocido puede solicitar el mensaje que falta a sus vecinos. Este sencillo mecanismo garantiza que incluso los nodos que han estado desconectados durante algún tiempo podrán solicitar recursivamente los mensajes que les faltan, tan pronto como vuelvan a estar conectados y reciban mensajes recientes.

El acto de solicitar recursivamente los mensajes que faltan se llama solidificación y un mensaje que no tiene huecos en sus ancestros directos o indirectos se llama sólido.

La capacidad de un sistema distribuido para hacer frente a participantes no fiables que se comunican a través de un medio no fiable se denomina tolerancia a fallos de colisión.

La Tangle

Dado que el DAG resultante tiene un aspecto un poco diferente al de una blockchain, queremos tomarnos un tiempo e introducir algo de terminología adicional.

El primer mensaje que pone en marcha la red se llama mensaje de génesis y los nodos hacen referencia a él cuando no hay otros mensajes a los que hacer referencia. Está marcado como sólido por defecto.

la red comienza con un mensaje génesis (azul)

Los mensajes que aún no han sido referenciados por otros mensajes, se llaman tips y el proceso de configuración de estas referencias mientras se emite un mensaje se llama selección de tips.

los mensajes morados son los tips del DAG

Todos los mensajes que son referenciados directa o indirectamente por un mensaje se llaman su cono pasado.

los mensajes morados forman el cono pasado del mensaje azul

En consecuencia, todos los mensajes que hacen referencia directa o indirecta a un mensaje se denominan su cono futuro.

los mensajes morados forman el cono futuro del mensaje azu

l
Los mensajes que sólo son vistos por una cantidad muy pequeña de nodos tienen una menor probabilidad de ser referenciados por mensajes posteriores y, en raros casos límite, puede ocurrir que el mensaje no sea referenciado en absoluto.

A estos mensajes los llamamos huérfanos y se limpian una vez que queda claro que nadie va a hacer referencia a ellos.

el mensaje rojo no fue recogido por otros y no tendrá ningún efecto – es huérfano

Conclusión

Hemos especificado un protocolo de difusión muy simple que asegura que cada nodo va a tener finalmente una percepción similar de los mensajes que han sido procesados por la red (los huérfanos son ignorados).

En lugar de supervisar constantemente a cada participante y detener la red si demasiados nodos tienen problemas -como en un protocolo de difusión atómica-, damos a los nodos la posibilidad de ponerse al día.

Nota: Esta idea tan simple de dar a los nodos la capacidad de ponerse al día fue uno de los mayores avances de Satoshi Nakamotos.

No sólo permite a los nodos superar de forma fiable los momentos en los que las condiciones de la red no son óptimas, sino que también permite a cualquiera abandonar o unirse a la red cuando lo desee: es realmente abierta y sin permisos.

Capa de consenso

Hasta ahora, nuestro protocolo es extremadamente sencillo y sólo requiere enviar dos hashes adicionales con cada transacción, pero tampoco hemos abordado realmente el difícil problema del consenso, todavía.

Mientras que alcanzar el consenso se considera normalmente un tema realmente complejo, veremos que nuestro protocolo ya está hecho en realidad y sólo necesita algunos ajustes menores para proporcionar también el consenso.

Entendiendo a Satoshi

Para entender las siguientes secciones, primero tenemos que cambiar la forma en que vemos las cadenas de bloques.
En lugar de verlas como una única cadena más larga, pueden verse como un árbol en el que todas las bifurcaciones abandonadas siguen siendo visibles y en el que el resultado de la votación sobre qué bifurcación debe prevalecer se cuenta en la longitud de las cadenas en competencia.

En realidad, la cadena más larga no es más que una rama (branch) de un árbol de bifurcaciones que compiten entre sí.

Una blockchain de Nakamoto no es sólo una secuencia de mensajes que contienen cambios de estado, sino que también es un mecanismo de votación en el que cada bloque vota por una bifurcación específica.

Este pequeño cambio de perspectiva nos lleva a una observación realmente importante:

Cada referencia en la blockchain Satoshi  vota por un número potencialmente ilimitado de bifurcaciones con un hash de tamaño pequeño y constante que hace que la complejidad de la mensajería sea completamente constante e independiente de factores como, por ejemplo, el tamaño de la red.

Esta forma de votación virtual – en la que los nodos expresan su opinión a través de una referencia en una estructura de datos replicada en lugar de intercambiar mensajes adicionales – es tan eficiente, que incluso los proyectos que ya no utilizan el consenso Satoshi siguen utilizando estos principios para informar al resto de la red sobre los cambios de estado y es muy poco probable que alguna vez encontremos una forma más eficiente de comprimir las opiniones.

Nota: Dar a los hashes que conectan los mensajes un significado y a los nodos una forma de entender este significado fue la segunda mayor revolución de Satoshi Nakamoto.

Votación virtual

Como nuestro modelo de ledger podría crear una gran cantidad de conflictos y la votación suele ser una operación costosa, decidimos copiar las ideas de Satoshi y convertir cada mensaje en una votación.

Para poder hacer que nuestros mensajes voten en las ramas de nuestro libro de contabilidad de cuatro entradas, primero tenemos que proyectar la información del libro de contabilidad a la Tangle y luego dar un significado a nuestras referencias.

En consecuencia, hacemos los siguientes ajustes a nuestro protocolo:

  • Un nodo que emite un mensaje que contiene una transacción, vota por la rama o branch a la que pertenece esta transacción.
  • Las referencias entre los mensajes significan aprobación, de modo que cada mensaje vota recursivamente por las ramas (branches) de los mensajes a los que hace referencia directa o indirectamente (los votos se heredan a lo largo de las aristas de la Tangle.
  • Un mensaje que vota por dos ramas contradictorias entre sí se considera inválido.

Las ramas o branch por las que vota un mensaje se determinan concatenando las ramas de sus padres y su transacción contenida.

Ejemplo

La forma más fácil de entender cómo funciona todo esto es viendo un ejemplo.
Supongamos que tenemos una maraña sin conflictos, en la que todos los mensajes contienen transacciones honestas y, en consecuencia, votan por la rama principal de nuestro libro de contabilidad de cuatro entradas.

En ausencia de conflictos, los mensajes simplemente son testigos de otros mensajes y votan por la rama maestra

Supongamos ahora que un atacante emite un gasto doble, es decir, un mensaje que contiene una transacción que entra en conflicto con uno de los otros mensajes que se han emitido antes.

Lo que ocurre ahora es que las dos transacciones en conflicto se registrarán en su rama correspondiente y estas ramas recién introducidas se propagarán automáticamente a los mensajes de la maraña de acuerdo con las reglas que acabamos de definir.

Las ramas se propagan a todos los mensajes que aprueban directa o indirectamente los mensajes en conflicto.

Todos los mensajes del futuro cono de un mensaje conflictivo, votan por la rama correspondiente para que sea aceptada por la red.

Rama DAG: la rama verde ha recibido más aprobadores y votos que la rama roja

La regla de consenso es muy sencilla: La rama que haya recibido más aprobaciones, gana. Si hay un empate, los nodos elegirán la rama con el hash más bajo.

Al igual que en una blockchain, en la que los bloques posteriores refuerzan las decisiones anteriores uniéndose a la cadena ganadora, los nodos de nuestro protocolo también siguen haciendo referencia a los mensajes de la rama ganadora, lo que hace cada vez más difícil revertir las decisiones.

En contraste con una cadena de bloques, que sólo publica una única declaración de validación con cada bloque, los nodos en IOTA comparten constantemente su opinión con cada transacción emitida.

Esto resuelve uno de los mayores problemas del diseño original de la blockchain de Satoshi, ya que permite a la red operar en un modelo de red asíncrona y recoger una gran cantidad de confirmaciones en paralelo para alcanzar la finalidad lo más rápido posible.

De hecho, cuantas más transacciones haya, más votos podremos recoger y más rápido llegaremos a la finalidad: la red se vuelve más rápida con más usuarios.

Identidades descentralizadas

Hasta ahora, nuestro protocolo es muy genérico y no hace ninguna suposición sobre la protección sibilina utilizada, pero como queremos construir un mecanismo de consenso basado en la identidad, donde los diferentes nodos tienen una influencia ponderada en el proceso de consenso, tenemos que hacer otro ajuste a nuestro protocolo.

 

Para poder asociar cada mensaje con el peso de su emisor, hacemos que cada nodo firme sus mensajes.

Además de los dos hashes, añadimos a cada mensaje la identidad y la firma del nodo emisor

De este modo, cada mensaje puede asociarse objetivamente a un emisor concreto con cierta influencia en el proceso de consenso.

Nota: En tiempos de baja adopción, los nodos más influyentes emitirán mensajes vacíos en intervalos regulares para asegurar la red.

Cargas útiles de los mensajes y capas

Para permitir casos de uso centrados en los datos, permitimos que los mensajes no sólo lleven transacciones, sino cargas útiles de datos arbitrarias.

Los primeros bytes de cada carga útil codifican su tipo, que puede utilizarse para cambiar dinámicamente la forma en que se analiza y traduce en su representación en memoria.

De la misma manera que TCP/IP permite definir protocolos adicionales sobre su segmento de datos genérico, esto nos permite crear protocolos de mayor nivel.

Nota: Las cargas útiles que no son de transacción siempre estarán asociadas a la rama maestra, ya que no tienen un concepto inherente y compartido de conflictos en la capa1.

Aplicaciones descentralizadas y máquinas virtuales

Los nodos pueden instalar plugins que definen una máquina virtual específica para la carga útil que analiza y procesa los diferentes tipos de carga útil para crear una aplicación descentralizada que replica su estado entre todos los demás nodos que tienen el mismo plugin instalado.

Los plugins utilizan una arquitectura basada en eventos para escuchar los mensajes que contienen los tipos de carga útil correspondientes.

Dado que cualquier DLT utiliza mensajes que se replican entre los nodos para alcanzar el consenso, es incluso posible ejecutar DLTs adicionales con algoritmos de consenso específicos para cada caso dentro de estas máquinas virtuales.

Los nodos pueden decidir individualmente qué cargas útiles procesar, pero para lograr un buen nivel de descentralización la aplicación descentralizada necesita tener una cantidad razonable de participantes.

Los mensajes que contienen cargas útiles en las que un nodo no está interesado se siguen gossipeando, pero requieren muy poca sobrecarga computacional, ya que se manejan como fragmentos de datos genéricos.

Nota: Proporcionamos una prueba de concepto para una aplicación de chat descentralizada y resistente a la censura en el repositorio de GitHub.

Tipos de parents (padres)

Dado que incluso un mecanismo de votación virtual sigue siendo un mecanismo de votación en el que el resultado no está claro de antemano, puede ocurrir, y ocurrirá, que los nodos honestos adjunten sus mensajes a una parte del DAG que resulte no ser la ganadora, y las cargas útiles de estos mensajes tendrían que volver a adjuntarse posteriormente.

Esto crea un problema de teoría del juego en el que los nodos se verían incentivados a adjuntar sus mensajes a mensajes más antiguos que ya se han decidido.

Si todos los nodos fueran racionales y modificaran su selección de tips en consecuencia, no podríamos avanzar en la votación, ya que no llegarían nuevos mensajes que aprobaran los conflictos y llevaran al sistema a una conclusión.

La razón por la que los mensajes honestos que contienen cargas útiles válidas no pueden ser aprobados si hacen referencia a la parte equivocada del DAG es porque la aprobación siempre se dirige a todo el cono pasado de un mensaje y un mensaje que aprueba dos gastos dobles se considera inválido.

Para resolver este problema introducimos diferentes tipos de referencias a los padres que significan cosas diferentes:

  • Parent fuerte: Vota por el mensaje referenciado y por todo su cono pasado.
  • Parent débil: Vota por el mensaje referenciado y nada en su cono pasado.
  • Como parent: Vota por el mensaje referenciado y todo en su cono pasado (y si hay ramas conflictivas en el otro padre, entonces prevalecerán las especificadas en este padre).

Estos nuevos tipos de referencia permiten ahora que los nodos hagan referencia a otros mensajes honestos independientemente de sus referencias.

Conclusión

Hemos proporcionado la especificación de alto nivel para un nuevo protocolo de votación de la capa base que se basa puramente en las ideas de Satoshis Nakamotos y que permite a los nodos procesar transacciones de forma completamente asíncrona y en tiempo real.
El protocolo resultante no sólo es conceptualmente muy sencillo, sino que también tiene otras propiedades deseables:

  1. El protocolo es escalable (soporta una cantidad ilimitada de nodos y validadores).
  2. El protocolo es robusto (sigue funcionando incluso si los validadores desaparecen repentinamente; lo único que necesitamos para tomar decisiones es una percepción relativa del peso).
  3. El protocolo es rápido (los tiempos de confirmación son casi en tiempo real).
  4. El protocolo es seguro (es resistente a los atacantes bizantinos).
  5. El protocolo proporciona tolerancia a los fallos (los nodos que funcionan mal tienen una forma de ponerse al día)
  6. El protocolo proporciona inmutabilidad (dado que los mensajes están vinculados entre sí a través de hashes, las decisiones pasadas no pueden cambiarse si asumimos que los nodos pueden acordar el conjunto correcto de tips).
  7. El protocolo es eficiente (no tiene sobrecarga innecesaria en ninguna parte del protocolo, ni siquiera envía votos).
  8. El protocolo es lo más resistente a la censura (ninguna entidad controla el acceso de escritura al ledger, ni siquiera un minero).
  9. El protocolo es flexible (compatible con cualquier tipo de protección contra ataques Sybil – por ejemplo, PoW, PoS, dPoS, VDFs, comités con permiso, etc.).

Aunque los conceptos son muy sencillos desde un punto de vista conceptual, sigue siendo un enorme reto de ingeniería, ya que hay muchas capas y niveles interdependientes que tienen que trabajar todos juntos.

Hemos tenido que inventar varias estructuras de datos y tipos de índice nuevos que nos permiten gestionar todo esto de forma eficiente y ejecutar en más o menos O(1) y todavía estamos optimizando partes de la base de código.

Creo que es razonable asumir que los conceptos introducidos aquí forman el protocolo de votación más simple y eficiente que se pueda construir. Es muy poco probable que lleguemos a mejorar lo que es añadir dos hashes a cada transacción (realmente me sorprendería que se pudiera hacer con uno solo).

Pero el mecanismo de votación más eficiente no es el mecanismo de consenso más eficiente, todavía y seguiremos mejorando y ampliando nuestro protocolo en las próximas partes de esta serie.

ELI5

Hemos diseñado un protocolo que permite a los nodos escribir directamente en un ledger distribuido, sin intermediarios y simplemente compartiendo transacciones con sus vecinos.

Cada transacción lleva una pequeña etiqueta de unos pocos bytes y los nodos pueden llegar a un consenso simplemente mirando las etiquetas y sin tener que intercambiar mensajes adicionales.

El protocolo es igual de robusto y seguro que la blockchain de Satoshis y seguirá funcionando incluso si se desconecta una gran cantidad de nodos.


Post original: The Trust Machine — Part4: The Tangle — a generalized voting protocol

Comentarios

comentarios

pasarela de pagos con criptomonedas