Explicando el Algoritmo de Control de Congestión de IOTA

738

Este artículo explica con cierto detalle técnico el Algoritmo de Control de Congestión IOTA (ICCA por sus siglas en inglés) utilizado en el protocolo IOTA 2.0 (Coordicide). Hemos querido ofrecer esta visión general para aclarar la relación entre access y el mana que se planteó en nuestro anterior post sobre el mana. Además, somos conscientes de que muchos están deseosos de aprender más sobre Coordicide, y quienes son participantes del ecositema IOTA se beneficiarán de este conocimiento. Dicho esto, la información que aparece en este artículo no es «conocimiento necesario», esto quiere decir que no es necesario saber esto para poder utilizar IOTA. Además, todos los aspectos tratados en este artículo formarán parte de nuestra especificación completa. Si tienes preguntas, visita nuestro Discord para discutirlas con nuestros desarrolladores e investigadores. El control de la congestión es un aspecto importante y fascinante de Coordicide, así que esperamos que disfrutes de esta explicación.

Nos gustaría expresar nuestra gratitud a Bob Shorten y su equipo del Imperial College de Londres por su trabajo en el desarrollo conjunto de este importante algoritmo. Su trabajo ha sido fundamental para desarrollar este importante componente y validar su comportamiento.

Para una explicación más detallada, véase nuestro primer artículo sobre este tema, que ha sido aceptado para su presentación en el 7º Taller IEEE/IFIP sobre Seguridad para Tecnologías de Redes Distribuidas Emergentes.

¿Qué es el control de la congestión y por qué lo necesitamos?

En la mayoría de las DLT, la información se transmite a través de la red mediante un proceso denominado «gossiping», en el que los nodos participantes reciben mensajes de un vecino y los reenvían a otros vecinos. Naturalmente, los nodos reciben muchos mensajes, por lo que deben decidir cuáles de ellos retransmitir a sus vecinos y en qué orden hacerlo. Un algoritmo de control de congestión es el encargado de tomar estas decisiones.

La congestión se produce cuando una red tiene más tráfico del que puede soportar. Sin un control adecuado de la congestión, la red puede saturarse y dejar de funcionar porque los nodos pueden abrumar a sus vecinos con más mensajes de los que puede manejar un nodo individual. Un algoritmo de control de congestión evita la sobresaturación al decidir qué mensajes se reenvían. En una DLT sin sharding, el problema es especialmente grave porque cada participante de la red («nodo») debe procesar todas las transacciones válidas. Por tanto, el rendimiento total de la red (conocido informalmente como transacciones por segundo) está limitado en última instancia por los recursos disponibles, como la conectividad a Internet, el procesamiento de los dispositivos y la capacidad de almacenamiento.

Sin embargo, como un algoritmo de control de congestión decide qué mensajes gossipean, determina esencialmente quién tiene acceso a la red; el algoritmo de control de congestión tiene un profundo efecto en la experiencia del usuario. Para dilucidar el «Coordicide», los autores quieren explicar el ICCA (IOTA Control Congestion Algorithm) que se utilizará en el protocolo IOTA 2.0 (Coordicide).

El control de congestión es un tema algo antiguo que se estudió intensamente a medida que se desarrollaba la infraestructura de Internet. Sin embargo, a diferencia de la mayoría de las redes, las DLT tienen requisitos muy estrictos que hacen del control de congestión un problema especialmente difícil de abordar. En particular, deben satisfacerse los siguientes requisitos (hay otros requisitos que detallamos más adelante, pero estos son los más importantes)

  • Acceso justo: el acceso a la red debe concederse de forma proporcional a algún «recurso escaso»
  • Resistencia a los ataques: los nodos maliciosos no pueden interrumpir la red
  • Consistencia: todos los nodos deben escribir los mismos mensajes en su libro de contabilidad local

Las blockchains resuelven el control de congestión utilizando algunos mecanismos para elegir a los líderes que minan los bloques. El acceso es justo, ya que la tasa de elección de un líder es proporcional a la cantidad de participación o al poder de hashing que tenga. Dado que el acceso está limitado sólo a los líderes, la congestión nunca es posible, ni siquiera durante un ataque. Por último, como las blockchains tienen un módulo de consenso para elegir a un líder, se consigue el consenso. Limitar el acceso a los «líderes» facilita las arquitecturas PoS y PoW, pero centraliza el acceso.

Dado que IOTA utiliza un DAG, y no una blockchain, no podemos (y no queremos) utilizar ningún tipo de proceso de elección de líderes. En su lugar, ICCA utiliza lo que se llama un programador, que selecciona los mensajes que están «programados». Los mensajes programados se escriben en laTangle local y se reenvían a los vecinos del nodo. El programador, programa los mensajes a un ritmo constante, lo que garantiza que ninguno de los vecinos se vea desbordado.

Ahora podemos discutir cómo el ICCA logra nuestros tres requisitos clave mencionados anteriormente, el acceso justo, la resistencia a los ataques y consistencia. En primer lugar, podemos ver que, localmente, cada nodo programa el tráfico de forma justa según el mana. Resulta que esto también es cierto a nivel global y que el acceso se concede de forma justa según el mana.

En segundo lugar, ¿qué ocurre si un atacante intenta hacer spam en la red? Localmente, los nodos no procesarán los mensajes del atacante más rápido que su tasa permitida. Así que los mensajes del atacante se acumularán y su cola crecerá. Todos los nodos lo detectarán y expulsarán al atacante de la red. Por supuesto, existen otros numerosos métodos de ataque que hemos estudiado, pero el «programador» (scheduler) es difícil de engañar, por lo que el algoritmo es bastante resistente a los atacantes.

Por último, dado que el programador nunca borra los mensajes honestos, el algoritmo garantiza que finalmente lleguen a todos los nodos. Si un atacante es expulsado de la red, ¿qué ocurre con los mensajes que emitió? Como el comportamiento del atacante es detectable, la mayoría de los nodos lo desterrarán en el mismo momento, lo que garantiza que los ledgers sean casi iguales. Entonces, el protocolo gossip cuenta con un mecanismo llamado solidificación que puede rectificar diferencias mínimas en las tangles.

A continuación se ofrece una visión más técnica del ICCA, ya que se presenta un análisis más profundo de los requisitos.

Requisitos para cualquier DLT

Existen algunos requisitos generales y algunos de ellos son clave en el éxito de cualquier algoritmo de control de congestión de una DLT: consistencia, acceso justo, utilización, latencia justa y resistencia a los ataques.

Consistencia

Consistencia significa que cada nodo escribe exactamente los mismos mensajes en el ledger. Cuando la red está congestionada, los nodos pueden verse obligados a abandonar algunos mensajes, lo que provoca incoherencias. El objetivo del ICCA es reducir al mínimo las caídas de mensajes y arreglar las incoherencias restantes mediante peticiones de solidificación. Sin esto, no hay consenso.

Acceso justo

Dado que los recursos de red disponibles son finitos, el acceso (o lo que es lo mismo, el rendimiento) tiene que estar restringido de alguna manera. En las DLT, esto suele garantizarse restringiendo el acceso mediante un «recurso escaso». Muchas DLT utilizan la energía como recurso escaso exigiendo a los mineros que hagan PoW. Las DLTs Proof of Stake a menudo utilizan el propio token como recurso escaso; IOTA utiliza el mana (ver el blog sobre el mana).

El acceso justo significa que todos los nodos deben obtener una parte justa del rendimiento. Es importante tener en cuenta que este acceso debe ser linealmente proporcional con respecto a la cantidad de mana: si el acceso se da de forma sublineal – dando cada vez menos acceso con más mana – entonces los grandes actores dividirán su mana en nodos más pequeños y tendrán un acceso injusto. Si el acceso es superlineal -dando más acceso con más mana- entonces los grandes poseedores tienen ventaja. Esto incentiva a los nodos a poner en común sus recursos, como ocurre con los pools de minería. Tanto las asignaciones de acceso sublineales como las superlineales son injustas en general y promueven un comportamiento que podría perjudicar a la red a largo plazo.

Utilización

Si hay demanda, se utilizará todo el potencial de la red.

Por ejemplo, piense en un control de acceso trivial en el que el rendimiento de cada nodo esté limitado por su porcentaje de mana, digamos que un 10% de mana permite a un usuario un máximo del 10% del ancho de banda. Esto sería justo, pero ineficaz: de hecho, si, por ejemplo, el 95% del mana está desconectado, la red funcionaría al 5% de su capacidad. Un mecanismo eficiente de control de la congestión tendrá que reutilizar esa capacidad no utilizada.

Combinar la utilización y la equidad es complicado. La pregunta «¿Cuánto mana necesito para X TPS?» es difícil de responder. Pero recuerda que la utilización es algo bueno. La red sería inutilizable sin ella.

La utilización y la equidad forman un concepto llamado «Max-min fairness». Se trata de un concepto importante de las redes clásicas. Los routers que retransmiten el tráfico de Internet necesitan exactamente estas propiedades (imagina que tus routers locales no tuvieran estas propiedades, tu Internet doméstica sería inutilizable).

Latencia justa

Todos los usuarios honestos deberían experimentar una latencia similar. La latencia es el tiempo que tarda un mensaje emitido en propagarse a todos los nodos. Esta latencia debe ser pequeña tanto para una buena experiencia de usuario como para la estabilidad del protocolo.

La experiencia del usuario debe hablar por sí misma; a nadie le gustan los retrasos. Sin embargo, para la estabilidad del protocolo, si la latencia fuera dramáticamente diferente para los distintos usuarios, entonces introduciría incentivos perversos para desviarse del algoritmo. Castigar la latencia de los nodos maliciosos es bueno, desde la perspectiva de la teoría de juegos, por lo que si las latencias de los nodos aumentaran cuando se comportan mal, entonces estarían recibiendo un castigo, y por tanto se les anima a comportarse.

Resistente a los ataques

Estas propiedades mencionadas anteriormente deben mantenerse para los nodos honestos incluso si un atacante intenta romper el sistema. Los nodos tienen un incentivo para aumentar su acceso y disminuir su latencia. Las desviaciones deben ser imposibles o castigadas.

Algoritmo de Control de Congestión IOTA (ICCA)

El Algoritmo de Control de Congestión de IOTA (ICCA) agiliza el proceso de transacción para minimizar el impacto de la posible congestión y para regular el acceso de escritura al ledger. El ICCA logra esto a través de sus tres partes: el programador, el fijador de tasas y el blacklister (lista negra).

El programador determina qué transacciones se escriben en el ledger y se gossipean. El programador de tasas utiliza un algoritmo clásico de aumento aditivo y disminución multiplicativa (AIMD) para ajustar la tasa de cada individuo. El blacklisting censura los nodos que atacan la red.

Hasta donde sabemos, éste es el primer algoritmo de control de congestión que no utiliza  Proof of Work y basado en DAG que se ha publicado en el campo de las criptomonedas. Es el componente más novedoso de Coordicide y una piedra angular del protocolo IOTA 2.0.

Modelo de nodo

Desde la capa de red (ver este enlace sobre terminología), los mensajes llegan a través de gossiping de los vecinos, se filtran para evitar duplicados y mensajes no válidos, y llegan a la bandeja de entrada donde se ponen en cola por el ID del nodo emisor. La bandeja de entrada también recibe los mensajes creados localmente por el fijador de tarifas del nodo. El blacklister supervisa las colas de la bandeja de entrada en busca de comportamientos maliciosos, y el programador decide qué mensajes pueden salir de la bandeja de entrada. Después de programar un mensaje, se producen simultáneamente las siguientes tareas:

  • El mensaje se gossipea a todos los vecinos menos a aquel del que lo hemos recibido (se devuelve a la capa de red)
  • Se llama a la aplicación correspondiente (de la capa de aplicación) para que analice la carga útil
  • El mensaje se «escribe» en la tangle local, donde puede ser considerado como un consejo, votado por el FPC, anotado en el ledger, etc.

Programador

En el ICCA, proponemos el uso de una versión modificada de un programador de Round Robin deficitario. Aparte del hecho de que dicho programador cumple con todos los requisitos mencionados (es decir, consistencia, utilización, equidad y resistencia a los ataques), lo elegimos por el hecho de que es ligero. Por ejemplo, es la opción por defecto para manejar eficientemente un gran número de hilos para el kernel de Linux.

El planificador funciona así: después de recibir los mensajes, se colocan en la bandeja de entrada. A cada mensaje se le asigna una «puntuación de trabajo» basada en la cantidad de recursos que consume. Los mensajes más grandes tienen puntuaciones mayores, ya que utilizan más ancho de banda. Un mensaje con una transacción que contenga 100 firmas tiene una puntuación más alta que una transacción con una sola firma, porque se necesitan más recursos para validar las firmas. Básicamente, el programador se asegura de que se consuma un número máximo de recursos por segundo. Los investigadores e ingenieros que lo desarrollan tienen total libertad para definir esta función de trabajo con el fin de adaptar el algoritmo a las necesidades exactas de la red IOTA.

Cuando se reciben los mensajes, se clasifican por su nodo emisor en diferentes colas. El programador visita cada cola, programa un número de mensajes basado en el mana (el «recurso escaso» utilizado en IOTA) que tiene el nodo emisor, y luego pasa a la siguiente cola. Si una cola está vacía, se la salta; el programador entonces programa desde otras colas. De este modo, todos los nodos tienen sus mensajes procesados a un ritmo proporcional a su mana, a menos que su cola se vacíe.

La bandeja de entrada de un nodo se divide en colas o filas, con una cola por cada nodo de la red; un programador Deficit Round Robin puede manejar eficazmente decenas de miles de colas. Los mensajes se colocan en la cola del nodo que los emitió. El planificador visita cada cola no vacía en un orden determinista. A cada cola se le asigna una cantidad llamada «crédito» para ese nodo. Cuando el planificador visita una cola, añade un determinado valor de prioridad proporcional al maná del ID del nodo correspondiente. A continuación, programa los mensajes de la cola de ese nodo. Cada vez que se programa un mensaje y se sigue procesando, la «puntuación de trabajo» del mensaje se deduce del crédito. Cuando no se pueden programar más mensajes de la cola de N o el crédito se vuelve negativo, el programador pasa a la siguiente cola.

Actualmente, programamos los mensajes a un ritmo fijo/máximo preestablecido. Y en este momento, estamos analizando y estudiando diferentes medios para hacer que este umbral sea dinámico y que la fragmentación permita que la red escale de forma natural.

Pero, ¿qué ocurre si un atacante o un nodo egoísta no sigue las reglas del programador? Supongamos que un nodo egoísta decide reenviar sólo sus propias transacciones. Eso llevaría a inflar su cola correspondiente en los búferes de entrada de los nodos honestos, lo que provocaría grandes retrasos sólo para sus propias transacciones. Lo mismo ocurre con los nodos maliciosos: mientras los nodos honestos sigan el programador de Round Robin deficitario, las transacciones de los atacantes no se reenviarán.

Setteador de Rate

¿Cómo sabe un nodo cuántos mensajes puede emitir? Utiliza el Rate Setter. En función de la longitud de la cola, el fijador de rate utiliza el algoritmo AIMD para regular su propia tasa de generación de transacciones. Los routers de Internet utilizan un algoritmo similar para ajustar el tráfico.

Un nodo puede controlar la longitud de su propia cola. Cuando esta cola se alarga demasiado, sabe que está emitiendo demasiados mensajes. Un nodo aumenta su rate o tasa de emisión lentamente (aumento aditivo) hasta que su cola se alarga demasiado. En este punto, el nodo disminuye rápidamente su rate de emisión (disminución multiplicativa) para evitar la próxima congestión. Con el tiempo, esto hace que el seteador de tarifas converja a una tasa de emisión justa, dependiendo de las condiciones de tráfico actuales.

Como beneficio adicional, el fijador de tasas se asegura de que la latencia de las transacciones emitidas por los nodos que siguen el protocolo sea baja. Los nodos que no sigan este algoritmo inundarán sus colas y aumentarán su latencia. De este modo, se incentiva a los nodos a utilizar el seteador de rate.

¿Qué ocurre si los nodos maliciosos no utilizan el seteador de rate? ¿Y si no les importa aumentar la latencia, por ejemplo en un ataque de spam? Las siguientes secciones contienen las medidas de seguridad que hemos establecido para que se activen antes de que un atacante pueda dañar la consistencia.

Blacklisting

¿Qué ocurre si el nodo no utiliza el seteador de rate o tasas? Entonces no reducirá su tasa cuando su cola crezca y así su cola seguirá creciendo. Como los otros nodos honestos sólo tienen una cantidad de memoria, no se puede permitir que la cola crezca indefinidamente. Por eso, el ICCA tiene el registro negro para limitar la longitud de las colas. Dependiendo del mana, a un nodo se le permite tener un cierto número de mensajes en cola. Cuando este número supera un determinado umbral, el nodo entra temporalmente en la blacklist, lo que significa que no se añaden otras transacciones de ese nodo a la bandeja de entrada durante algún tiempo. Si la cola de un nodo comienza a explotar, los nuevos mensajes entrantes para ese nodo determinado se descartan.

Rate Control (Control de rate)

Un atacante puede intentar inundar la red con grandes cantidades de spam, tratando directamente de sobrecargar cientos de nodos a la vez. Para protegernos de este tipo de ataques, utilizamos un mecanismo llamado control de rate (Rate Control), que limita físicamente la cantidad de mensajes que puede emitir un nodo. Para ello, utilizamos un PoW adaptativo como mecanismo de control de rate. Para los nodos honestos, la dificultad del PoW es relativamente baja. Pero si un nodo empieza a hacer spam, la dificultad aumenta exponencialmente, impidiendo físicamente que emita más mensajes. Así, este mecanismo evitaría que el sistema se sobrecargara por completo.

Por muy útil que sea el mecanismo de rate control, puede que no sea necesario. El ICCA tiene el potencial de ser lo suficientemente fuerte como para que este módulo sea redundante. Sin embargo, en la primera versión del protocolo Coordicide queremos garantizar la máxima protección, y la posible disminución o eliminación posterior de cualquier PoW se deja como una optimización futura. En la red de prueba de GoShimmer, estudiaremos la interacción entre el control de la tasa de PoW adaptable y el ICCA.

Mensajes de mana cero

Desgraciadamente, el ICCA requiere que los nodos tengan algo de mana para emitir mensajes, porque los nodos con 0 mana nunca recibirán crédito y, sin crédito, sus mensajes no se programarán. Esto es importante para evitar ataques de bajo coste: sin él, los nodos con poco mana podrían crear ráfagas de transacciones, congestionando así la red y afectando la consistencia del ledger.

Podemos ofrecer varias opciones para que los nodos de mana cero puedan emitir sus transacciones. Una forma es a través de un grifo en el que cualquier nodo puede ofrecer voluntariamente su mana no utilizado a nuevas personas dispuestas a probar la red, para cualquier caso de uso que tengan en mente. Otra opción es utilizar un mercado de mana, en el que se puede determinar cómo y cuándo alquilar mana según las necesidades. Además, otro método consiste en comprar tokens y transferirlos asignandolos al nodo.

Por último, estamos investigando una forma de adaptar dinámicamente el umbral mínimo de mana en función del porcentaje de mana activo y de las condiciones de tráfico actuales.

Durante los periodos de baja congestión, los «nodos validados de bajo mana» pueden emitir sus transacciones y serán programados por los nodos honestos. Un «nodo de mana bajo validado» es un nodo que cumple las dos condiciones siguientes: una, su mana es inferior al umbral mínimo de mana; y dos, el nodo ha realizado recientemente un PoW grande. Cuando la congestión es baja, los nodos honestos permitirán temporalmente la programación de estos nodos validados de mana bajo. Una vez que la congestión es grande, los nodos de maná bajo validados no pueden emitir sus transacciones; tienen que esperar a que haya periodos de baja congestión.


Post original: https://blog.iota.org/explaining-the-iota-congestion-control-algorithm/

Comentarios

comentarios

pasarela de pagos con criptomonedas