La vida pasada y presente de MEERDAG

Prefacio

Una vez se discutió acaloradamente la perspectiva de desarrollo de blockchain 3.0, entre los cuales se considera que DAG es la nueva generación más prometedora de tecnología blockchain después de Bitcoin y Ethereum. Entonces, ¿cuál es el origen de la cadena de bloques DAG? ¿Cuál es su concepto técnico?

DAG y blockchain eran originalmente dos tecnologías diferentes, pero la combinación de las dos, el concepto de "DAG blockchain" y su primera aparición en el centro de atención, fue posible gracias a dos israelíes, Yonatan Sompolinsky y Aviv Zohar, los pioneros de este concepto pionero. .

El protocolo GHOST propuesto por Aviv Zohar fue adoptado por Ethereum en la etapa inicial. Este protocolo resuelve los problemas de seguridad causados ​​por las horquillas de cadena. La estructura de datos de la cadena de bloques bifurcada evoluciona de una sola cadena a una cadena de árbol. Más tarde, Aviv Zohar propuso además el protocolo Inclusivo. Bajo las reglas del protocolo Inclusivo, la estructura de datos de la cadena de bloques se convierte en un gráfico acíclico dirigido (DAG). Con la exploración continua de DAG por parte de DAGlabs, el concepto de marco y la arquitectura técnica de BlockDAG se han establecido gradualmente, durante los cuales se lanzaron sucesivamente el protocolo SPECTRE, el protocolo PHANTOM y el protocolo GHOSTDAG.

Qitmeer estaba explorando protocolos de consenso que abordan la escalabilidad (disponibilidad) sin sacrificar la descentralización (tolerancia a fallas de partición) y la seguridad (coherencia) al comienzo del proyecto, y descubrió que coincidía con la filosofía de diseño de BlockDAG.

En sentido estricto, BlockDAG puede entenderse como un marco técnico de un protocolo de consenso, cuyo objetivo es mejorar aún más la tecnología DAG con un alto rendimiento de concurrencia bajo la premisa de garantizar la descentralización y la seguridad. El mecanismo de consenso PoW basado en la prueba de trabajo puede garantizar que la red blockchain esté lo suficientemente descentralizada, por lo que la extracción de bloques para generar bloques se ha convertido en una característica técnica importante, por lo que se llama BlockDAG.

Qitmeer Team ha realizado muchas optimizaciones a nivel de ingeniería para los algoritmos de consenso de GHOSTDAG y SPECTRE, y ha creado un protocolo MeerDAG con sus propias características conservando las ventajas de ambos protocolos.

1. Estructura básica de DAG

1.1 ¿Cómo es un DAG?

Todos estamos muy familiarizados con la estructura de datos del árbol de Merkle. Dentro de cada bloque de Bitcoin, el árbol Merkle se usa para registrar la información de la transacción, vea la imagen a continuación

Se puede ver que el árbol de Merkle pertenece a una estructura de árbol dirigida, cada vértice del árbol solo puede apuntar a un vértice anterior y todos los datos tienen una dirección de flujo obvia. La estructura DAG permite que cada vértice apunte a múltiples vértices anteriores, y todo el flujo de datos también tiene una dirección obvia. Otra estructura de datos es un gráfico dirigido. A diferencia de DAG, un gráfico dirigido permite que los datos fluyan hacia atrás y el flujo de datos de toda la estructura no es muy obvio. Ver imagen 2 para la diferencia entre los tres.

1.2 Blockchain es una estructura DAG especial

Después de tener una comprensión intuitiva de la estructura DAG, averigüemos por qué blockchain se considera una estructura DAG especial.

Si las bifurcaciones de blockchain están relacionadas con la velocidad de generación de bloques y la velocidad de transmisión. Cuando la velocidad de producción del bloque excede la velocidad de transmisión, se transmitirán varios bloques al mismo tiempo y se producirán bifurcaciones. Cuantos más tenedores, peor es la seguridad. Para reducir las bifurcaciones, Bitcoin encuentra un equilibrio entre rendimiento y seguridad: se genera un bloque cada diez minutos. Ahora supongamos que el tiempo para cada bloque es lo suficientemente largo como para que no se extraiga ningún bloque nuevo antes de que se transmita el bloque anterior. Entonces la estructura de esta cadena de bloques es una sola cadena, ver imagen 3

De hecho, debido a retrasos en la red y otras razones, inevitablemente ocurrirán bifurcaciones, por lo que la estructura real de la cadena de bloques será como se muestra en la imagen 4, y solo se seleccionará una de las cadenas principales válidas (blanca) a través del principio de cadena más larga de la cadena. consenso del libro mayor. La información de la transacción en los bloques restantes (rojo) no es válida y no se adoptará.

Ahora deje de lado el consenso del libro mayor, es decir, ignore cómo seleccionar una cadena principal efectiva. Desde la perspectiva de la estructura de red subyacente, en la imagen 5 se muestra una estructura típica de cadena de bloques y en la imagen 6 se muestra una estructura típica de DAG.

Se puede ver que la única diferencia entre las dos estructuras es que el bloque DAG puede apuntar a múltiples bloques anteriores, mientras que la cadena de bloques solo puede apuntar al único bloque anterior. Específicamente, el encabezado del bloque de la cadena de bloques solo puede contener el valor hash de un bloque, apuntando al único bloque principal; mientras que el encabezado del bloque del bloque bajo la estructura DAG puede contener los valores hash de múltiples bloques, apuntando a diferentes bloques anteriores. Como se muestra en la imagen 7.

Ahora introducimos el coeficiente de bifurcación K, que se refiere al número de bifurcaciones que puede permitir la red.

Cuando K=0, toda la red no permite bifurcaciones, como se muestra en la imagen 3.

Esta red que no permite bifurcaciones es la blockchain.

Bitcoin cumple con esta definición; aunque Ethereum tiene bifurcaciones de bloques de tío, estos bloques de tío solo se usan para juzgar el peso de la cadena principal, y no se agregarán a la cadena principal al final (registros de bloque de tío La información de la transacción no está incluida en la cadena principal ), por lo que Ethereum también cumple con esta definición.

El valor K de la red DAG debe ser un número entero mayor que 0. Entonces, desde un punto de vista estructural, DAG es una extensión de la estructura de la cadena de bloques, y la cadena de bloques es un DAG especial y simplificado.

1.3 El impacto de la estructura DAG en el rendimiento

En pocas palabras, podemos considerar a DAG como una estructura de red que permite bifurcaciones, y la cantidad de bifurcaciones permitidas está determinada por el coeficiente de bifurcación K.

Entonces, ¿qué significa exactamente una red que permite bifurcaciones? Significa que la velocidad de generación de bloques puede exceder la velocidad de transmisión. Por un lado, esto conduce a más transacciones empaquetadas por unidad de tiempo; por otro lado, cuando toda la red transmite un bloque A, toda la red también transmite otro bloque B bifurcado y, finalmente, algunos nodos solo confirmarán A, otros nodos solo confirmarán B, por lo que DAG permite que los nodos en la red para registrar información diferente al mismo tiempo. La combinación de estos dos aspectos hace que DAG presente las características de alta concurrencia y sincronización débil.

DAG es un tipo de contabilidad asincrónica, que puede mejorar en gran medida la velocidad de procesamiento de la información de la red, es decir, TPS.

La cadena de bloques es una red de sólida contabilidad síncrona, que requiere que cada nodo de la red registre la misma información al mismo tiempo. Sin embargo, este requisito a menudo limita la capacidad de la red blockchain para procesar información, lo que hace que el TPS sea relativamente bajo.

Entonces, la pregunta es, ¿qué tipo de consenso se debe usar para esta red de contabilidad asincrónica que permite bifurcaciones? En el artículo anterior, mencionaremos en detalle el mecanismo de consenso basado en DAG. El mecanismo de consenso se divide en consenso de bloque y consenso de libro mayor. El consenso de bloque de DAG puede ser el mismo que el de blockchain. Por ejemplo, también se utiliza POW. Dado que se permiten bifurcaciones, el tiempo de generación de bloques se puede establecer muy corto. El consenso de bloque también puede ser diferente de la cadena de bloques. Por ejemplo, el proyecto IOTA cancela directamente el proceso de empaquetado y generación de bloques. Siempre que ocurra una transacción, se escribirá en la red de inmediato (cada bloque en el diagrama DAG no es un bloque sino una transacción de bolígrafo), obteniendo así la capacidad de procesamiento de transacciones a velocidad ultra alta.

El consenso del libro mayor de DAG es mucho más complejo que la cadena de bloques. ¿Cómo evitar que los nodos hagan el mal? ¿Cómo filtrar cuando hay dos transacciones contradictorias? ¿Cómo evitar el "doble gasto"? Con la complejidad de la estructura de red subyacente, el consenso del libro mayor también tiene mayores requisitos. Se destacará en artículos posteriores.

1.4 TXDAG y BlockDAG

La diferencia entre el BlockDAG generalizado (gráfico de bloques) y TxDAG (DAG transaccional, DAG transaccional). En términos generales o en términos de estructuras de datos, BlockDAG y TxDAG son solo dos estructuras de datos diferentes. La diferencia es que el primero empaquetará múltiples transacciones en bloques, y el libro mayor está organizado por bloques; mientras que este último no tiene concepto de bloques, y el libro mayor está compuesto por transacciones, que también pueden entenderse como una sola transacción en un bloque. Dado que la transacción tiene mucha información descriptiva de transacción común, es decir, la información del encabezado, esta parte de la información se puede almacenar en el bloque, y la transacción solo necesita guardar las diferentes partes de la transacción, de modo que el proceso HASH (minería) se salta y se sube directamente cadena. Dado que BlockDAG no solo conserva la alta concurrencia de DAG,

1.5 Ventajas de DAG

En comparación con blockchain, DAG es en realidad la diferencia entre un gráfico y una cadena. Para una cadena, no puede tratar solo con una parte, porque solo hay un grado de entrada y un grado de salida de la cadena, y los nodos de la cadena no se pueden dividir en varios Nodos para procesar, pero es posible para gráficos, debido a que los gráficos pueden tener varios grados de salida, los nodos conectados por varios grados de salida pueden procesarse al mismo tiempo.

Para la red en cadena, no es que la capacidad de procesamiento de los nodos no sea fuerte, pero la estructura de la cadena no se puede calcular en paralelo, y el tiempo perdido es principalmente tiempo de espera: uno es para iniciar una transacción, que debe sincronizarse con todos los nodos; el otro es el tiempo de confirmación, cuando hay una confirmación de nodo que debe sincronizarse con toda la red. Para DAG, no existe tal problema. Cuando la billetera inicia una transacción, no necesita esperar cuántas transacciones tiene antes. Solo necesita pasar por verificación parcial, transmisión de red y otra verificación parcial, lo que equivale a descentralizar la confirmación de la transacción. Los nodos están haciendo un trabajo similar a los rompecabezas, empalmando sus propias transacciones con las confirmadas por otros.

Por lo tanto, se concluye que DAG tiene las siguientes ventajas:

(1). Velocidad de transacción rápida

Si bien logra el mismo nivel de descentralización y seguridad que Bitcoin y Ethereum, el procesamiento local DAG y la liquidación paralela pueden aumentar considerablemente la velocidad de las transacciones, lo que hace que el rendimiento de las transacciones (TPS) y el retraso final promuevan más de dos órdenes de magnitud.

(2). Gran capacidad de expansión

Dado que DAG admite la contabilidad asíncrona, los nodos de la red pueden procesar nuevas transacciones en paralelo sin esperar la sincronización de datos de otros nodos, lo que evita la pérdida de tiempo, mejora la eficiencia de las transacciones y permite que cada nodo que participa en la contabilidad se amplíe rápidamente. Por lo tanto, DAG es muy adecuado para proyectos de pago, como micropagos transfronterizos y escenarios de negocios financieros inclusivos defendidos por Qitmeer Team.

(3). Más difícil de modificar maliciosamente

En comparación con la estructura de cadena, es mucho más difícil modificar maliciosamente un DAG porque el DAG tiene muchos grados de entrada y salida, y si se modifica un nodo, los grados de entrada correspondientes deben modificarse.

2. Pasado y presente de MEERDAG

2.1 Origen de la tecnología DAG

En 2013 en bitcointalk.org, el famoso lugar de nacimiento de la cadena de bloques, un académico de la Universidad Hebrea de Israel con ID Avivz78 propuso introducir el concepto DAG como un algoritmo de consenso en la estructura de la cadena de bloques y creó el protocolo GHOST.

Después de que se propuso el protocolo GHOST, Yonatan Sompolinsky propuso otra nueva idea en la que los bloques recién generados apuntan a todos los bloques finales bifurcados conocidos, es decir, un bloque tiene múltiples padres, en cuyo punto

la cadena de bloques cambia de una sola cadena a una estructura que consta de múltiples cadenas bifurcadas juntas, y dicha estructura de cadena se denomina DAG (gráfico acíclico dirigido).

En 2016, se publicó el documento de protocolo técnico SPECTRE, que mejoró aún más los detalles de la arquitectura técnica, formó el prototipo del protocolo blockDAG de primera generación y propuso la gran idea del retardo de red sin parametrización (o adaptación de parámetros de retardo).

En 2018, DAGlabs lanzó el protocolo PHANTOM. Se resolvió el problema de que el protocolo SPECTRE no puede negociar la clasificación lineal y continuó optimizándolo para formar el protocolo GHOSTDAG, que es el primer protocolo BlockDAG de grado industrial y también marca la madurez de BlockDAG.

Al final del documento de protocolo GHOSTDAG, Yonatan Sompolinsky imaginó un posible protocolo que combinaba GHOSTDAG + SPECTRE, pero no lo presentó en detalle.

3. Reflexiones sobre la selección de tecnología de MEERDAG

3.1 Reflexión sobre la selección de tecnología MEERDAG

En la primera etapa de Qitmeer Network, Mecca Network, coincidió con el aumento de la exploración de tecnología de expansión, frente a muchas soluciones de expansión convencionales dentro y fuera de la cadena, al seleccionar la tecnología de cadena pública de Qitmeer, también se enfrentó a una elección difícil.

En términos de selección de tecnología de expansión, la industria generalmente enfrenta un problema de triángulo imposible. Es imposible lograr escalabilidad (Scalability), descentralización (Descentralización) y seguridad (Seguridad) al mismo tiempo, y solo se pueden lograr dos de los tres. El equipo de Qitmeer en ese momento también enfrentó ese problema. Después de estudiar muchas soluciones de expansión, el equipo finalmente se decantó por una tecnología llamada BlockDAG.

3.2 Breve introducción al protocolo SPECTRE

SPECTRE es un protocolo blockDAG que admite confirmación rápida. El algoritmo de consenso de SPECTRE es un algoritmo de votación. Una vez que se encuentra una transacción en conflicto, el bloque que contiene la transacción en conflicto se utilizará como candidato para aceptar votos de todos los bloques, con un voto para cada bloque. La votación de SPECTRE tiene un efecto de amplificación. Por ejemplo, un bloque seguirá la mayoría de votos en los que se ha concentrado en el pasado, por lo que la velocidad de convergencia es muy rápida y una ligera diferencia en el número de votos puede resultar en una gran ventaja para el ganador. Deje que los bloques honestos voten por los bloques honestos, y los bloques honestos posteriores le darán el poder de apilamiento anterior, de modo que los ataques maliciosos fallarán y la seguridad de la red estará garantizada.

SPECTRE solo puede garantizar una confirmación rápida de bloques honestos. Para dos bloques en conflicto cuyo tiempo de lanzamiento está cerca, el tiempo de confirmación de SPECTRE es incierto. Este es el concepto de actividad débil propuesto por SPECTRE, es decir, no se puede garantizar que todos los bloques puedan ser Confirmación final en un tiempo razonable.

SPECTRE es un protocolo de consenso basado en el sistema de transacciones. En el sistema de transacciones, solo los malhechores pueden crear transacciones de doble gasto. Es decir, las transacciones de doble gasto no tendrán mucho impacto en los bloques honestos. Además, realizar transacciones de doble gasto es muy estricto en el control de tiempo y es difícil provocar ataques en circunstancias normales. Por lo tanto, Qitmeer Team cree que el problema de la actividad débil de SPECTRE es aceptable en proyectos reales.

3.3 Breve introducción al protocolo GHOSTDAG

Como puede ver en el perfil de SPECTRE anterior, SPECTRE es muy bueno para solucionar problemas de transacciones en conflicto y defenderse de los ataques. Si un proyecto solo se utiliza con fines de pago como Bitcoin, la confirmación rápida del protocolo SPECTRE es suficiente. Pero si desea integrar contratos inteligentes, SPECTRE no puede hacerlo.

Porque SPECTRE solo puede hacer una clasificación relativa de las transacciones en conflicto (juzgando el orden de las transacciones en conflicto), pero no puede hacer una clasificación absoluta para todos los bloques. Debido a que el lenguaje del contrato inteligente debe ser Turing completo, al igual que escribimos un programa de computadora, necesitamos realizar varias operaciones en un orden estricto, por lo que la red con función de contrato inteligente tiene una característica: las transacciones en la red pueden ser cronometrados Hacer una clasificación lineal (cronológica) uno tras otro.

En respuesta, Yonatan Sompolinsky diseñó recientemente el protocolo GHOSTDAG para formar un orden lineal en los bloques DAG. SPECTRE y GHOSTDAG son dos protocolos completos e independientes, ninguno complementa al otro.

El mecanismo de minería de GHOSTDAG es el mismo que el de SPECTRE, que generará el mismo tipo de estructura DAG. La diferencia es que GHOSTDAG juzga si el bloque es honesto o malicioso analizando la conectividad del bloque, clasifica los bloques según la clasificación y genera un bloque DAG estricto. El orden lineal de la transacción en conflicto se juzga por el orden lineal.

El protocolo GHOSTDAG no solo permite que DAG obtenga capacidades de ordenamiento lineal de transacciones, sino que también resuelve el problema de actividad débil del protocolo SPECTRE. El protocolo GHOSTDAG también es el primer protocolo blockDAG que admite la ordenación lineal de transacciones.

3.4 Protocolo MEERDAG

El posible protocolo que combina GHOSTDAG+SPECTRE que Yonatan Sompolinsky imaginó al final del documento de protocolo GHOSTDAG tiene más que ver con brindar orientación en términos de ideas, y se enfoca en demostrar el rigor del algoritmo, que involucra muchos problemas de práctica de ingeniería y necesita basarse en situaciones reales La situación se practica y prueba constantemente, y uno de los problemas más típicos es el rendimiento. Si se implementa directamente de acuerdo con el algoritmo de referencia en el texto original, el rendimiento es casi inaceptable.

Qitmeer Team considera que los escenarios de aplicación subyacentes de la cadena pública son principalmente finanzas inclusivas, transacciones de activos digitales y gestión de la cadena de suministro.

Teniendo en cuenta el mecanismo de recompensa en bloque y los requisitos de consenso del libro mayor para las capacidades de clasificación lineal y, al mismo tiempo, teniendo en cuenta la velocidad de confirmación de la transacción que es más importante para la experiencia de intercambio de valor.

El conjunto azul (bloque honesto) de GHOSTDAG es más difícil de estabilizar y el tiempo de confirmación será mucho más largo que el de SPECTRE. Sin embargo, dado que la recompensa en bloque no requiere un tiempo de confirmación elevado, no afectará a la red. El protocolo GHOSTDAG se elige como protocolo de consenso base y el protocolo SPECTRE se elige como protocolo de consenso asistido.

MeerDAG, una solución de consenso híbrida que combina SPECTRE y GHOSTDAG, es una solución de escalado BlockDAG que se ajusta a la configuración clásica de blockchain (abierta, justa, segura, escalable) y es más compatible con el modelo clásico de blockchain UTXO. Mientras que la cadena de bloques clásica descarta todos los bloques fuera de la cadena más larga, MeerDAG es un modelo cooperativo que conserva el protocolo SPECTRE y mantiene todos los bloques, por lo que puede lograr un alto rendimiento y proporcionar un alto rendimiento a nivel de transacción real, así como una confirmación rápida de la transacción de la cadena de bloques. servicios. En segundo lugar, BlockDAG se basa en la regla de la cadena más pesada y puede lograr una tolerancia a fallas del 51 % en comparación con Bitcoin. Además, la red BlockDAG no tiene nodos especiales y no requiere que los nodos estén en línea o no. en minería,

Durante el período de Qitmeer Network Medina, la red introdujo pruebas de entorno de potencia informática real. El equipo iteró continuamente el algoritmo PoW y mejoró la eficiencia del algoritmo, retuvo por completo las ventajas del protocolo GHOSTDAG+SPECTRE y redujo continuamente la dificultad de la implementación del protocolo en la implementación de ingeniería. Por ejemplo: según la primera versión de los documentos del algoritmo GHOSTDAG, el cálculo de los conos inversos debe ser exhaustivo y la complejidad del algoritmo es O (n ^ 3). Después de una gran cantidad de pruebas de nivel de ingeniería, la complejidad se reduce en dos órdenes de magnitud a O(n), lo que cumple en gran medida con los requisitos de usabilidad. Bajo los requisitos básicos de garantizar la seguridad, la descentralización y la equidad, se maximiza el rendimiento del TPS.

Qitmeer Team combinó de manera innovadora el protocolo GHOSTDAG+SPECTRE para formar su propio protocolo característico MeerDAG, que se convirtió en el prototipo técnico de la nueva generación de BlockDAG. El posicionamiento central de la red subyacente BlockDAG de Qitmeer es servir como una red de circulación de valor. En la capa 2, combina el sistema de máquina virtual conectable impulsado por MeerEVM para crear aplicaciones ricas de cadena de bloques y abarcar toda la ecología de la cadena de bloques.

Referencia:
[1] De blockchain a DAG (2) -- la estructura básica de DAG,https://mp.weixin.qq.com/s/Mc2uEOLtT_Z3OMapNh1TGg
[2] De Blockchains a blockDAG,https://www.youtube.com/watch?v=tk38AAV_whw
[3] Jeff Zhou：Tecnología de cadena de bloques asíncrona de alta velocidad DAG，https://www.jianshu.com/p/45d73e0e74ec
[4]Teoría técnica FANTASMA, ESPECTRO, FANTASMA，https://mp.weixin.qq.com/s/nGR0ld73oXgs_p_MtDcv-Q
[5]Equipo de Qitmeer: ​​“Libro blanco de Qitmeer”