En este artículo, les hablaré sobre DAG (Gráfico acíclico dirigido) y su aplicación en libros de contabilidad distribuidos, y lo compararemos con blockchain.
DAG no es nada nuevo en el mundo de las criptomonedas. Es posible que haya oído hablar de él como una solución a los problemas de escalabilidad de blockchain. Pero hoy no hablaremos de escalabilidad, sino de lo que diferencia a las criptomonedas de todo lo demás: descentralización, falta de intermediarios y resistencia a la censura.
También les mostraré que DAG en realidad es más resistente a la censura y no hay intermediarios para acceder al libro mayor.
En las cadenas de bloques que conocemos, los usuarios no tienen acceso directo al libro mayor. Cuando desee agregar una transacción al libro mayor, debe "pedirle" al productor del bloque (también conocido como "minero") que lo haga. Son los mineros quienes deciden qué transacción agregar al siguiente bloque y cuál no. Son los mineros quienes tienen acceso exclusivo a los bloques y el derecho a decidir qué transacción se aceptará para su inclusión en el libro mayor.
Los mineros son intermediarios que se interponen entre usted y el libro mayor distribuido.
En la práctica, normalmente un pequeño número de grupos de mineros controlan colectivamente más de la mitad de la potencia informática de la red. Para Bitcoin, estos son cuatro grupos, para Ethereum, dos. Si se confabulan, pueden bloquear cualquier transacción que quieran.
En los últimos años, se han propuesto muchas variaciones de blockchains, que difieren en los principios de elección de los productores de bloques. Pero los propios productores de bloques no van a ninguna parte, todavía están "parados en la barrera": cada transacción debe pasar por el productor de bloques, y si él no la acepta, entonces la transacción, de hecho, no existe.
Este es un problema inevitable con blockchain. Y si queremos solucionarlo, tenemos que cambiar radicalmente el diseño y deshacernos por completo de los bloques y de los productores de bloques. Y en lugar de construir una cadena de bloques, conectaremos las propias transacciones, incluyendo los hashes de varias anteriores en cada transacción. Como resultado, obtenemos una estructura conocida en matemáticas como gráfico acíclico dirigido: DAG.
Ahora todo el mundo tiene acceso directo al registro, sin intermediarios. Cuando desee agregar una transacción al libro mayor, simplemente agréguela. Usted selecciona varias transacciones principales, agrega sus datos, firma y envía su transacción a sus pares en la red. Listo. No hay nadie que le impida hacer esto, por lo que su transacción ya está en el libro mayor.
Esta es la forma más descentralizada y a prueba de censura de agregar transacciones al libro mayor sin intermediarios. Porque todo el mundo simplemente añade sus transacciones al registro sin pedir permiso a nadie.
Los DAG pueden considerarse la tercera etapa en la evolución de los registros. Primero hubo registros centralizados, donde una parte controlaba el acceso a ellos. Luego vinieron las cadenas de bloques, que ya contaban con varios controladores que registraban las transacciones en el libro mayor. Y finalmente, no hay ningún controlador en el DAG; los usuarios agregan sus transacciones directamente.
Ahora que tenemos esta libertad, no debería llevarnos al caos. Debemos llegar a un acuerdo sobre el estado del registro. Y este acuerdo, o consenso, normalmente significa acuerdo en dos cosas:
- ¿Qué ha pasado?
- ¿En qué orden sucedió esto?
Podemos responder fácilmente a la primera pregunta: una vez que una transacción creada correctamente se ha agregado al libro mayor, se ha producido. Y punto. La información sobre esto puede llegar a todos los participantes en diferentes momentos, pero eventualmente todos los nodos recibirán esta transacción y sabrán que sucedió.
Si fuera una cadena de bloques, los mineros decidirían qué sucede. Lo que sea que el minero decida incluir en un bloque es lo que sucede. Todo lo que no incluye en el bloque no sucede.
En blockchains, los mineros también resuelven un segundo problema de consenso: el orden. Se les permite ordenar las transacciones dentro del bloque como deseen.
¿Cómo determinar el orden de las transacciones en un DAG?
Sólo porque nuestra gráfica está dirigida, ya tenemos cierto orden. Cada transacción se refiere a una o más transacciones principales anteriores. Los padres, a su vez, se refieren a sus padres, y así sucesivamente. Los padres obviamente aparecen antes que las transacciones infantiles. Si se puede llegar a alguna de las transacciones mediante transiciones de enlace padre-hijo, sabemos exactamente el orden entre las transacciones en esa cadena de transacciones.
Pero el orden entre las transacciones no siempre puede determinarse únicamente a partir de la forma del gráfico. Por ejemplo, cuando dos transacciones se encuentran en ramas paralelas del gráfico.
Para resolver ambigüedades en tales casos, recurrimos a los llamados proveedores de pedidos. También los llamamos "testigos". Se trata de usuarios comunes cuya tarea es enviar constantemente transacciones a la red de manera ordenada, es decir. de modo que se pueda llegar a cada una de sus transacciones anteriores mediante transiciones a lo largo de los enlaces padre-hijo. Los proveedores de pedidos son usuarios confiables y toda la red depende de ellos para no violar esta regla. Con el fin de racionalmente Confíe en ellos, requerimos que cada proveedor de pedidos sea una persona u organización conocida (no anónima) y tenga algo que perder si infringe las reglas, como reputación o negocios basados en la confianza.
Los proveedores de pedidos son elegidos por los usuarios, y cada usuario incluye una lista de sus proveedores de confianza en cada transacción que envía a la red. Esta lista consta de 12 proveedores. Se trata de un número suficientemente pequeño para que una persona pueda verificar la identidad y la reputación de cada uno de ellos, y suficiente para garantizar que la red siga funcionando en caso de problemas inevitables con una minoría de proveedores de pedidos.
Esta lista de proveedores varía de un usuario a otro, pero las listas de transacciones vecinas pueden diferir hasta en un proveedor.
Ahora que tenemos proveedores de órdenes, podemos aislar sus transacciones en un DAG y ordenar todas las demás transacciones en torno a la orden creada por ellos. Es posible crear dicho algoritmo (ver. para detalles técnicos).
Pero el orden de toda la red no se puede determinar instantáneamente; necesitamos tiempo para que los proveedores de pedidos envíen una cantidad suficiente de sus transacciones para verificar el orden final de las transacciones pasadas.
Y, dado que el orden está determinado únicamente por las posiciones de las transacciones de los proveedores en el DAG, todos los nodos de la red tarde o temprano recibirán todas las transacciones y llegarán a la misma conclusión con respecto al orden de las transacciones.
Entonces, estamos de acuerdo sobre lo que consideramos que sucedió: cualquier transacción que termine en el DAG sucedió. También tenemos acuerdo sobre el orden de los eventos: esto es evidente a partir de las relaciones de las transacciones o se infiere del orden de las transacciones enviadas por los proveedores de órdenes. Entonces tenemos un consenso.
Tenemos esta versión de consenso en Obyte. Aunque el acceso al libro mayor de Obyte está completamente descentralizado, el consenso sobre el orden de las transacciones sigue centralizado porque 10 de cada 12 proveedores están controlados por el creador (Anton Churyumov) y sólo dos de ellos son independientes. Estamos buscando candidatos dispuestos a convertirse en uno de los proveedores de pedidos independientes para ayudarnos a descentralizar los pedidos del libro mayor.
Recientemente, ha surgido un tercer candidato independiente dispuesto a instalar y mantener un nodo proveedor de pedidos: la Universidad de Nicosia.
Ahora bien, ¿cómo controlamos el doble gasto?
De acuerdo con las reglas, si se encuentran dos transacciones gastando la misma moneda, gana la transacción que ocupa el primer lugar en el orden final de todas las transacciones. El segundo queda invalidado por el algoritmo de consenso.
Si es posible establecer un orden entre dos transacciones que gastan la misma moneda (a través de conexiones padre-hijo), entonces todos los nodos rechazan inmediatamente tal intento de duplicar el gasto.
En caso de que el orden no sea visible desde las relaciones principales entre dos de dichas transacciones, ambas se aceptan en el libro mayor y tendremos que esperar el consenso y el establecimiento del orden entre ellas utilizando los proveedores de órdenes. Entonces la transacción anterior ganará y la segunda dejará de ser válida.
Aunque la segunda transacción deja de ser válida, aún permanece en el registro porque ya tiene transacciones posteriores que hacen referencia a ella, que no violaron nada y no sabían que esta transacción dejaría de ser válida en el futuro. De lo contrario, tendríamos que eliminar el padre de las transacciones posteriores buenas, lo que violaría el principio fundamental de la red: cualquier transacción correcta se acepta en el libro mayor.
Esta es una regla muy importante que permite que todo el sistema sea resistente a los intentos de censura.
Imaginemos que todos los proveedores de pedidos se confabulan en un intento de "censurar" una transacción específica. Pueden ignorarlo y nunca elegirlo como "padre" para sus transacciones, pero eso no es suficiente, la transacción aún puede incluirse indirectamente como padre de alguna otra transacción emitida por cualquier usuario de la red que no esté en connivencia. Con el tiempo, una transacción de este tipo recibirá cada vez más hijos, nietos y bisnietos de usuarios comunes, creciendo como una bola de nieve, y todos los proveedores de pedidos acordados también tendrán que ignorar estas transacciones. Al final, tendrán que censurar toda la red, lo que equivale a un sabotaje.
De esta manera, el DAG sigue siendo resistente a la censura incluso si hay colusión entre los proveedores de pedidos, superando así la cadena de bloques resistente a la censura en la que no podemos hacer nada si los mineros deciden no incluir ninguna de las transacciones. Y esto se desprende de la propiedad principal del DAG: la participación en el registro es completamente independiente y sin intermediarios, y las transacciones son irreversibles.
Fuente: habr.com