El propósito de esta publicación es comprender claramente la idea detrás de los Gráficos Acíclicos Dirigidos o DAG.
La mejor manera de comprender completamente los DAG a un nivel profundo es razonando: por qué las cosas son como son. Entonces, comenzaremos con un DAG realmente básico y luego intentaremos construir una red DAG robusta y segura mediante la introducción lógica de cosas más complejas de una manera que tenga sentido.
Para este tutorial, vamos a ver cómo maraña (un DAG) de IOTA funciona
Para entender la maraña, necesitamos aprender sobre lo que los informáticos llaman gráfico dirigido. Un gráfico dirigido es una colección de vértices (cuadrados), que están conectados entre sí por bordes (flechas) Este es un ejemplo de un dirigido acíclico grafico:
La propiedad de un dirigido acíclico gráfico es que las flechas solo fluye en una dirección y nunca "ciclo" o formar un bucle. De ahí el nombre:
- Dirigido: Fluye en una sola dirección.
- Acíclico: No forma un "ciclo" en ningún caso
- Grafico: Bueno, es un gráfico 😉
La Enredo, que es la estructura de datos detrás IOTA, es un tipo particular de gráfico acíclico dirigido, que contiene transacciones. Cada transacción se representa como un vértice en el gráfico. Cuando una nueva transacción se une a la maraña, elige dos transacciones anteriores para aprobar, agregando (señalando) dos nuevas aristas al gráfico.
En el ejemplo anterior, la transacción número 5 aprueba las transacciones número 2 y 3. Las transacciones son más o menos lo que cabría esperar, información del formulario “la persona A le dio a la persona B diez IOTA”. En esta etapa, no nos preocuparemos demasiado sobre lo que queremos decir al aprobar una transacción, ya que lo veremos más adelante.
Llamamos transacciones no aprobadas recomendaciones. En el ejemplo, la transacción número 6 es un consejo, porque nadie lo aprobó todavía. Cada transacción entrante debe elegir dos consejos para aprobar (¡siempre hay al menos uno!). La estrategia para elegir qué dos consejos aprobar es muy importante y es la clave de la tecnología única de IOTA. Sin embargo, para facilitarnos la vida, comenzaremos con la estrategia más simple: elegir al azar entre todos los consejos disponibles. Cada transacción entrante analiza todas las transacciones no aprobadas actualmente, y simplemente elige dos al azar.
Para ver cómo se ve el enredo cuando todos usan esta estrategia de selección aleatoria (técnicamente llamada "selección de punta aleatoria uniforme"), puedes jugar con esto simulación visual de eso. Esta simulación genera enredos aleatorios, con la primera transacción (llamada génesis) a la izquierda y las transacciones más recientes a la derecha. Las puntas están marcadas con un cuadrado gris. Cuando coloca el mouse sobre una transacción, todas las transacciones aprobadas por ella se resaltan en rojo y todas las que lo aprueban se vuelven azules.
En la simulación anterior, es posible que haya notado que las transacciones no se distribuyen de manera uniforme a lo largo del tiempo, pero algunos períodos están más ocupados que otros. Esta aleatoriedad, que hace que el modelo sea más realista, se logra mediante el uso de un Proceso de punto de Poisson para modelar cómo llegan las transacciones. Este modelo es muy común para analizar cuántos clientes entran a una tienda en un período de tiempo determinado o cuántas llamadas telefónicas se hacen a un centro de llamadas. Podemos ver este comportamiento en el ejemplo enredado a continuación. Las transacciones 4, 5 y 6 llegaron casi simultáneamente, y después de la transacción 6 hubo una larga pausa.
Para nuestros propósitos, solo necesitamos saber una cosa sobre este proceso de puntos de Poisson: en promedio, la tasa de transacciones entrantes es constante y se establece mediante un número que llamamos λ. Como ejemplo, si establecemos λ = 2, y el número de transacciones será 100, el tiempo total de simulación será de aproximadamente 50 unidades de tiempo. Pruébalo!
Una cosa más interesante para señalar, antes de continuar: si establecemos λ en una cantidad muy pequeña (digamos 0.1), obtenemos una "cadena". Una cadena es una maraña donde las transacciones solo aprueban una transacción previa, en lugar de dos. Esto sucede porque las transacciones se realizan tan lentamente que en un momento dado solo hay un solo consejo para aprobar. Esto es lo que realmente sucede en una cadena de bloques. Por lo tanto, los DAG son básicamente una forma generalizada de blockchain. En el otro extremo, con una gran λ, todas las transacciones llegan tan rápido que la única punta que ven es la génesis (punta 0). Esto es solo una limitación de la simulación: con grandes λ y un número fijo de transacciones, estamos simulando un período de tiempo muy corto.
Entonces, ¿qué queremos decir con la transacción no "ver" una anterior? En el modelo, hacemos que cada transacción sea invisible durante un cierto período después de que llegue. Marcamos este período de retraso con la carta h. Este retraso representa el tiempo que tarda la transacción en prepararse y propagarse a través de la red. En nuestra simulación, siempre establecemos h = 1. Esto significa que solo podemos aprobar transacciones que son al menos una unidad de tiempo en el pasado. Este retraso no es solo un detalle menor que se aportó para un realismo adicional, sino una propiedad fundamental de la maraña, sin la cual siempre obtendremos una cadena muy aburrida. También acerca la maraña al mundo real, donde las personas tardan un tiempo en comunicarse entre sí sobre nuevas transacciones.
Finalmente, es hora de hablar sobre un algoritmo de selección de propinas más avanzado: el caminata aleatoria no ponderada. Usando este algoritmo, ponemos un andador en la transacción de génesis, y que comience a "caminar" hacia las puntas. En cada paso, salta a una de las transacciones que aprueba directamente la que estamos realizando actualmente. Elegimos a qué transacción saltar con igual probabilidad, que es donde el término no ponderado viene de. Aquí hay un simulación eso muestra cómo sucede esto.
Puede ver que el camino que sigue el caminante está marcado en rojo, y en cada cruce se muestran los diferentes caminos posibles
marcado en azul. Las transacciones muy recientes, que son "invisibles" para el paseo aleatorio actual, se muestran como transparentes.
Comencemos con alguna motivación para estudiarlo. Una de las cosas que queremos que haga nuestro algoritmo de selección de propinas es evitar consejos perezosos. Una sugerencia perezosa es aquella que aprueba las transacciones antiguas en lugar de las recientes. Es perezoso porque no se molesta en mantenerse al día con el estado más reciente de la maraña, y solo transmite sus propias transacciones basadas en datos antiguos. Esto no ayuda a la red, ya que no se confirman nuevas transacciones.
En el ejemplo anterior, la transacción 14 es una sugerencia diferida, que aprueba algunas transacciones muy antiguas. Si utilizamos el algoritmo uniforme de selección aleatoria de propinas, es probable que la transacción 14 sea aprobada como cualquier otra, por lo que no se penaliza en absoluto. Utilizando la caminata no ponderada, este mal comportamiento incluso se fomenta, al menos en la simulación anterior.
¿Cómo podemos lidiar con este problema? Una cosa que no podemos hacer es obligar a los participantes a aprobar solo transacciones recientes, ya que eso chocaría con la idea de descentralización. Las transacciones pueden aprobar a quien quieran. Tampoco tenemos una forma confiable de saber exactamente cuándo entró cada transacción, por lo que no podemos hacer cumplir dicha regla. Nuestra solución es construir nuestro sistema con incentivos incorporados contra tal comportamiento, de modo que sea poco probable que nadie dé la aprobación a los consejos flojos.
Nuestra estrategia será parcialidad nuestra caminata aleatoria, por lo que es menos probable que elijamos consejos perezosos. Usaremos el término peso acumulado para denotar cuán importante es una transacción. Es más probable que caminemos hacia una transacción pesada que una ligera. La definición del peso acumulado es muy simple: contamos cuántos aprobadores tiene una transacción y agregamos uno. Contamos los aprobadores directos e indirectos. En el siguiente ejemplo, la transacción 3 tiene un peso acumulado de cinco, porque tiene cuatro transacciones que lo aprueban (5 directamente; 7, 8 y 10 indirectamente).
¿Por qué funciona esto? Echemos un vistazo a otra situación de propina perezosa. En el ejemplo a continuación, la transacción 16 es una sugerencia perezosa. Para que 16 sea aprobado, el caminante aleatorio debe llegar a la transacción 7 y luego elegir la transacción 16 en lugar de la transacción 9. Pero es poco probable que esto suceda, porque la transacción 16 tiene un peso acumulado de 1 y la transacción 9 tiene un peso acumulado de 7! Esta es una forma efectiva de desalentar el comportamiento perezoso.
En este punto podríamos preguntarnos: ¿necesitamos aleatoriedad? Podemos inventar el caminata aleatoria super ponderada, donde en cada cruce elegimos la transacción más pesada, sin probabilidades involucradas. Entonces obtendremos algo como esto:
Los cuadrados grises son puntas, con cero aprobadores. Si bien es normal tener algunos consejos en el extremo derecho del diagrama, es un problema ver que muchos de ellos se extienden por la línea de tiempo. Estos consejos son transacciones que son dejado atrás, y nunca será aprobado. Esta es la desventaja de sesgar demasiado nuestro camino: si insistimos en elegir solo la transacción más pesada en un momento dado, un gran porcentaje de las propinas nunca será aprobado. Solo nos queda un corredor central de transacciones aprobadas y consejos olvidados al margen.
Necesitamos un método para definir qué tan probable es que caminemos hacia un aprobador particular en un cruce dado. La fórmula exacta que elegimos no es importante, siempre y cuando otorguemos cierto sesgo a las transacciones más pesadas y tengamos un parámetro para controlar qué tan fuerte es este sesgo. Esto introduce nuestro nuevo parámetro α, que establece la importancia del peso acumulado de una transacción. Su definición exacta se puede encontrar en los IOTA detalles de la moneda, y si hay demanda, podría escribir una publicación futura con más detalles al respecto.
Si establecemos α a cero, volvemos a la caminata no ponderada. Si establecemos α para estar muy alto, tenemos la caminata súper ponderada. En el medio, podemos encontrar un buen equilibrio entre castigar el comportamiento perezoso y no dejar demasiados consejos. Determinar un valor ideal para α Es un tema de investigación importante en IOTA.
Este método de establecer una regla para decidir la probabilidad de cada paso en una caminata aleatoria se llama Cadena Markov Monte Carlo técnica, o MCMC. En una cadena de Markov, cada paso no depende del anterior, sino que se deriva de una regla que se decide de antemano.
Como siempre, tenemos un simulación para demostrar estas nuevas ideas. Recomiendo jugar con los valores de α y λ, y ver qué tipo de enredos interesantes puedes cocinar.
Hasta ahora hablamos de DAG, caminatas aleatorias y varios mecanismos de selección de propinas; esta vez hablaremos de dinero. Ha llegado el momento de explicar a qué nos referimos cuando decimos que la transacción A aprueba transacción B.
Como se mencionó anteriormente, cada transacción contiene información de la forma "Alice le dio a Bob 10 IOTA". El trabajo del aprobador es asegurarse de que Alice realmente tenido esos 10 IOTA para dar en primer lugar.
Quizás se pregunte en este momento: ¿de dónde provienen estos IOTA? La respuesta es que todos fueron creados en la primera transacción en la maraña, llamada génesis transaccional. No se crearán IOTA adicionales. Desde la génesis, los IOTA se transfirieron a las cuentas de los inversores originales en el proyecto, en proporción a la cantidad que ingresaron. Posteriormente, vendieron parte de su IOTA a otros, y finalmente se estableció una red comercial.
Volviendo a Alice y Bob, veamos un ejemplo simple. El cuadro representa una transacción. Para mayor comodidad, también anotamos los saldos en las cuentas de Alice y Bob antes y después de que se haya realizado la transacción. Vemos que al principio Alice tenía 10i, que le dio a Bob, después de lo cual Bob tiene 10i y Alice no tiene nada.
Evento
aliado alguien, digamos Charlie, quiere hacer su propio pago. Ejecuta el algoritmo de selección de propinas y resulta que necesita aprobar la transacción de Alice. Para hacer eso, debe verificar que Alice realmente tenga los 10i que gastó. Es mejor que Charlie se tome esta tarea en serio: si aprueba una mala transacción, ¡su propia transacción nunca será aprobada!
Para estar absolutamente seguro, Charlie tiene que enumerar todas las transacciones aprobadas directa e indirectamente por la transacción de Alice, desde la génesis. Él termina con una larga lista, que puede verse así:
- Génesis crea 15i
- Génesis le da a Bob 2i
- Génesis le da a Alice 8i
- Génesis le da a Charlie 5i
- Charlie le da a Donna 3i
- Bob le da a Alice 2i
Esta es solo una opción, por supuesto; cualquier lista que termine con 10i en la cuenta de Alice y 0 en la de Bob es aceptable. Charlie también tiene que hacer un seguimiento de todas las otras cuentas en el sistema, para asegurarse de que no vayan por debajo de cero: si alguno de los saldos en las secciones "antes" o "después" son negativos, su transacción no es válida.
Echemos un vistazo a un caso en el que Alice intenta dar más IOTA de las que tiene:
Alice le pagó a Bob 100i a pesar de que solo tenía 10. La transacción considera que la transacción de Alice y cualquier transacción futura que lo apruebe son inválidas. Los saldos negativos no están permitidos.
La situación se vuelve más interesante cuando aprobamos dos transacciones en lugar de una:
Bob estuvo en lo correcto al aprobar las transacciones de Alice, porque ella tenía suficiente dinero en su cuenta para pagar las dos sin ir por debajo de cero.
¿Qué pasaría si el total es más de lo que ella tiene? Esto se muestra a continuación. En este caso, Bob. no puede aprueba ambas transacciones de Alice, porque resultan en un saldo negativo para Alice. Si Bob hace esto, está rompiendo las reglas del protocolo IOTA, y nadie aprobará su nueva transacción.
Esta última situación se llama doble gastoporque Alice gastó su dinero dos veces. Tenga en cuenta que no rompió el protocolo, porque tenía suficiente dinero para cada transacción individual. Quizás ni siquiera quiso gastar el doble, sino que envió su transacción dos veces por error. Ella sin embargo creó dos sucursales en la maraña que no se puede reconciliar. Esto crea un problema para los usuarios honestos de IOTA: ¿qué rama deberían aprobar?
La solución a este problema es una vez más la caminata ponderada que aprendimos la semana pasada. Eventualmente, una de las ramas crecerá más pesada que la otra, y la más ligera será abandonada. Esto también implica que una transacción no puede considerarse confirmada inmediatamente después de su emisión, incluso si tiene algunos aprobadores, ya que podría ser parte de una sucursal que eventualmente se abandonará. Para asegurarse de que se confirme su transacción, debe esperar confirmación de confianza ser lo suficientemente alto
Acabamos de mencionar el doble gasto problema, que surge cuando Alice intenta gastar su dinero más de una vez. Ahora, mostraremos cómo se resuelve este problema en Tangle, y cómo decidimos qué historial es el válido.
Para ilustrar el problema, examinaremos el siguiente escenario de doble gasto:
Como puede ver, Alice tiene 5i, que le da a ambas Charlie y Bob. Esto es claramente un problema: no podemos tratar ambas transacciones como válidas. Usando la terminología Tangle, no podemos tener una transacción futura aprobándolos a ambos, ya que terminará con un saldo negativo en la cuenta de Alice.
Hemos aprendido que usando el algoritmo de caminata aleatoria ponderada, eventualmente una de las ramas se volverá mucho más grande. Así un consenso se forma alrededor de qué transacción es válida. Sin embargo, desde la perspectiva de Bob o Charlie, hay un problema: ¿cómo saben si realmente conseguiste el dinero de Alice?
Imagina que Bob y Charlie son traficantes de dinosaurios, y Alice compró una mascota T-Rex de cada uno de ellos. Si ambos le envían el T-Rex inmediatamente después de ver su transacción en el Enredo, eventualmente uno de ellos descubrirá que no le han pagado. ¿Cómo pueden saber cuándo es seguro enviar el lagarto?
Este es un problema grave y, de hecho, Bitcoin fue la primera tecnología en tratarlo con éxito, en 2009. Para mostrar cómo lo resuelve Tangle, presentamos un concepto llamado confirmación de confianza. Esta confianza es una medida del nivel de aceptación de una transacción por parte del resto de la maraña.
La confianza de confirmación de una transacción se calcula de la siguiente manera:
- Ejecute el algoritmo de selección de propinas 100 veces.
- Cuente cuántos de esos 100 consejos aprueban nuestra transacción y llámela A.
- La confianza de confirmación de nuestra transacción es "A por ciento".
En otras palabras, la confianza de una transacción es el porcentaje de propinas que la aprueban. No todos los consejos se consideran por igual; Consejos más probables se les da más importancia. Para ilustrar este punto, agreguemos confianza de confirmación a la simulación. Las transacciones con una confianza superior al 95% se muestran con un borde grueso a su alrededor.
En el enredo anterior, la transacción 9 es aprobada por dos de los cuatro consejos. Si estuviéramos utilizando una selección de punta aleatoria uniforme, tendría una confianza de exactamente el 50%. Sin embargo, los consejos que lo aprueban son aparentemente más probables que los que no lo hacen, lo que aumenta un poco la confianza.
Ahora está claro cómo Bob y Charlie pueden saber cuándo es seguro enviar su T-Rex a Alice. Una vez que la transacción de Alice alcanza un umbral de confianza muy alto, digamos el 95%, es muy poco probable que se elimine del consenso. Deberíamos tener cuidado y decir muy poco probable, en lugar de imposible; Si Alice quiere hacer trampa y tiene suficiente poder computacional, puede intentar gastar el doble.
Para hacer eso, ella emitirá una transacción pagando a Charlie, en lugar de Bob. Ella tendrá que aprobar dos los ancianos transacciones con él, que no hacen referencia a su pago a Charlie. Luego comenzará a emitir tantas transacciones como pueda, tratando de aumentar el peso acumulado de su nueva sucursal. Si tiene suficiente poder computacional, puede hacer que toda la red de IOTA le crea y siga su nueva rama, reescribiendo el historial y duplicando con éxito el gasto. Si observamos el nivel de confianza de su transacción con Bob, veremos que disminuye del 95% a eventualmente cero.
Este ataque se ilustra en la maraña a continuación, con el tiempo yendo hacia abajo:
Este escenario es solo un riesgo si Alice puede enviar más transacciones que todos los demás comb
ined, o cerca de él. Si bien no es un riesgo importante en una red madura y activa, es un problema real para la IOTA actual. No hay suficientes transacciones en el sistema para que esté a salvo de un ataque concentrado de doble gasto.
Desde que IOTA se creó para escalar, empleamos un mecanismo de consenso diferente voluntario y temporal por razones de seguridad: el coordinador. Cada dos minutos, un hito La transacción es emitida por la Fundación IOTA, y todas las transacciones aprobadas por ella se consideran con una confianza de confirmación del 100%, de inmediato. Usando el coordinador, la segunda transacción de Alice nunca habrá sido aprobada en primer lugar. Esto actúa como un mecanismo de protección, mientras que la red IOTA sigue creciendo hacia la actividad necesaria desde la adopción necesaria para mantener la red segura de manera 100% descentralizada, donde se activa el algoritmo de consenso distribuido completo de Tangle. En ese momento, la Fundación IOTA se cerrará el Coordinador y deja que el enredo evolucione por sí solo. Esto sucederá en fases iterativas. Cuando la red es lo suficientemente madura como para deshacerse del Coordinador, la red también se convertirá instantáneamente en órdenes de magnitud más eficientes.
La forma en que los DAG son diferentes de Blockchains es que cambia la estructura inherente de la forma en que almacenamos las transacciones. Este cambio, por pequeño que parezca, cambia la forma en que vemos las cosas que suceden en la red. Hace que el sistema general sea mucho más robusto que una cadena de bloques. Pero siempre hay una trampa. Este aumento en la escalabilidad viene con una menor seguridad, mayor probabilidad de centralización e incapacidad para soportar inherentemente contratos inteligentes. Discutiremos más sobre Blockchains vs DAG en la próxima publicación. ¡Manténganse al tanto!
