La vie passée et présente de MEERDAG

Préface

La perspective de développement de la blockchain 3.0 a déjà fait l'objet de vives discussions, parmi lesquelles DAG est considérée comme la nouvelle génération de technologie de blockchain la plus prometteuse après Bitcoin et Ethereum. Quelle est donc l'origine de la blockchain DAG ? Quel est son concept technique ?

DAG et blockchain étaient à l'origine deux technologies différentes, mais la combinaison des deux, le concept de "DAG blockchain" et sa première apparition sous les projecteurs, a été rendue possible par deux Israéliens, Yonatan Sompolinsky et Aviv Zohar, les pionniers de ce concept pionnier. .

Le protocole GHOST proposé par Aviv Zohar a été adopté par Ethereum à ses débuts. Ce protocole résout les problèmes de sécurité causés par les fourches de chaîne. La structure de données de la blockchain bifurquée évolue d'une chaîne unique à une chaîne arborescente. Plus tard, Aviv Zohar a en outre proposé le protocole inclusif. Selon les règles du protocole Inclusive, la structure de données de la blockchain évolue vers un graphe acyclique dirigé (DAG). Avec l'exploration continue de DAG par DAGlabs, le concept de framework BlockDAG et l'architecture technique ont été progressivement établis, au cours desquels le protocole SPECTRE, le protocole PHANTOM et le protocole GHOSTDAG ont été successivement publiés.

Qitmeer explorait des protocoles de consensus qui traitent de l'évolutivité (disponibilité) sans sacrifier la décentralisation (partitionnement de la tolérance aux pannes) et la sécurité (cohérence) au début du projet, et a constaté que cela coïncidait avec la philosophie de conception de BlockDAG.

Au sens étroit, BlockDAG peut être compris comme un cadre technique d'un protocole de consensus, qui vise à améliorer encore la technologie DAG avec des performances de concurrence élevées sous le principe d'assurer la décentralisation et la sécurité. Le mécanisme de consensus PoW basé sur la preuve de travail peut garantir que le réseau de blockchain est suffisamment décentralisé, de sorte que l'extraction de blocs pour générer des blocs est devenue une caractéristique technique importante, c'est pourquoi il s'appelle BlockDAG.

L'équipe Qitmeer a effectué de nombreuses optimisations au niveau de l'ingénierie pour les algorithmes de consensus de GHOSTDAG et SPECTRE, et a créé un protocole MeerDAG avec ses propres caractéristiques en conservant les avantages des deux protocoles.

1. Structure de base du DAG

1.1 À quoi ressemble un DAG ?

Nous connaissons tous très bien la structure de données de l'arbre de Merkle. À l'intérieur de chaque bloc de Bitcoin, l'arbre Merkle est utilisé pour enregistrer les informations de transaction, voir l'image ci-dessous

On peut voir que l'arbre de Merkle appartient à une structure arborescente dirigée, chaque sommet de l'arbre ne peut pointer que vers un sommet précédent et l'ensemble des données a une direction de flux évidente. La structure DAG permet à chaque sommet de pointer vers plusieurs sommets précédents, et l'ensemble du flux de données a également une direction évidente. Une autre structure de données est un graphe orienté. Contrairement à DAG, un graphe orienté permet aux données de refluer, et le flux de données de l'ensemble de la structure n'est pas très évident. Voir l'image 2 pour la différence entre les trois.

1.2 La blockchain est une structure DAG spéciale

Après avoir compris intuitivement la structure DAG, voyons pourquoi la blockchain est considérée comme une structure DAG spéciale ?

Si les fourches de la blockchain sont liées à la vitesse de génération de blocs et à la vitesse de diffusion. Lorsque la vitesse de production de blocs dépasse la vitesse de diffusion, plusieurs blocs seront diffusés en même temps et des fourches se produiront. Plus il y a de fourches, plus la sécurité est mauvaise. Afin de réduire les forks, Bitcoin trouve un équilibre entre performance et sécurité : un bloc est généré toutes les dix minutes. Supposons maintenant que le temps pour chaque bloc est suffisamment long pour qu'aucun nouveau bloc ne soit miné avant que le bloc précédent ne soit diffusé. Ensuite, la structure de cette blockchain est une chaîne unique, voir image 3

En fait, en raison des retards du réseau et d'autres raisons, des bifurcations se produiront inévitablement, de sorte que la structure réelle de la blockchain sera comme indiqué dans l'image 4, et une seule des chaînes principales valides (blanche) sera sélectionnée via le principe de la chaîne la plus longue du consensus du grand livre. Les informations de transaction dans les blocs restants (rouges) ne sont pas valides et ne seront pas adoptées.

Maintenant, mettez de côté le consensus du grand livre, c'est-à-dire ignorez comment sélectionner une chaîne principale efficace. Du point de vue de la structure de réseau sous-jacente, une structure de chaîne de blocs typique est illustrée à l'image 5 et une structure DAG typique est illustrée à l'image 6.

On peut voir que la seule différence entre les deux structures est que le bloc DAG peut pointer vers plusieurs blocs précédents, tandis que la blockchain ne peut pointer que vers le seul bloc précédent. Plus précisément, l'en-tête de bloc de la blockchain ne peut contenir que la valeur de hachage d'un bloc, pointant vers le seul bloc parent ; tandis que l'en-tête de bloc du bloc sous la structure DAG peut contenir les valeurs de hachage de plusieurs blocs, pointant vers différents blocs précédents. Comme le montre l'image 7.

Nous introduisons maintenant le coefficient de fourche K, qui fait référence au nombre de fourches que le réseau peut autoriser.

Lorsque K = 0, l'ensemble du réseau n'autorise pas les fourches, comme le montre l'image 3.

Ce réseau qui n'autorise pas les forks est la blockchain.

Bitcoin répond à cette définition ; bien qu'Ethereum ait des fourches de blocs oncles, ces blocs oncles ne sont utilisés que pour juger du poids de la chaîne principale, et ils ne seront pas ajoutés à la chaîne principale à la fin (enregistrements de blocs oncles Les informations de transaction ne sont pas incluses dans la chaîne principale ), donc Ethereum répond également à cette définition.

La valeur K du réseau DAG doit être un entier supérieur à 0. Ainsi, d'un point de vue structurel, DAG est une extension de la structure de la blockchain, et la blockchain est un DAG spécial et simplifié.

1.3 L'impact de la structure du DAG sur les performances

Pour le dire simplement, nous pouvons considérer DAG comme une structure de réseau qui autorise les fourches, et le nombre de fourches autorisées est déterminé par le coefficient de fourche K.

Alors, que signifie exactement un réseau qui autorise les fourches ? Cela signifie que la vitesse de génération de blocs peut dépasser la vitesse de diffusion. D'une part, cela conduit à plus de transactions packagées par unité de temps ; d'autre part, lorsqu'un bloc A est diffusé par l'ensemble du réseau, un autre bloc bifurqué B est également diffusé par l'ensemble du réseau, et finalement certains nœuds ne confirmeront que A, d'autres nœuds ne confirmeront que B, donc DAG autorise les nœuds dans le réseau pour enregistrer différentes informations en même temps. La combinaison de ces deux aspects fait que DAG présente les caractéristiques d'une concurrence élevée et d'une synchronisation faible.

DAG est une sorte de comptabilité asynchrone, qui peut considérablement améliorer la vitesse de traitement des informations du réseau, c'est-à-dire TPS.

La blockchain est un réseau de comptabilité synchrone solide, qui oblige chaque nœud du réseau à enregistrer les mêmes informations en même temps. Cependant, cette exigence limite souvent la capacité du réseau blockchain à traiter les informations, ce qui rend le TPS relativement faible.

La question est donc de savoir quel type de consensus doit être utilisé pour ce réseau de comptabilité asynchrone qui autorise les fourches ? Dans l'article précédent, nous mentionnerons en détail le mécanisme de consensus basé sur le DAG. Le mécanisme de consensus est divisé en consensus de bloc et consensus de grand livre. Le consensus de bloc du DAG peut être le même que celui de la blockchain. Par exemple, POW est également utilisé. Puisque les fourches sont autorisées, le temps de génération de bloc peut être très court. Le consensus de bloc peut également être différent de la blockchain. Par exemple, le projet IOTA annule directement le processus de conditionnement et de génération de blocs. Tant qu'une transaction se produit, elle sera écrite sur le réseau immédiatement (chaque bloc du diagramme DAG n'est pas un bloc mais un stylo. transaction), obtenant ainsi la capacité de traitement des transactions à ultra-haute vitesse.

Le consensus du grand livre DAG est beaucoup plus complexe que la blockchain. Comment empêcher les nœuds de faire le mal ? Comment filtrer lorsqu'il y a deux transactions contradictoires ? Comment éviter les « doubles dépenses » ? Avec la complexité de la structure de réseau sous-jacente, le consensus du grand livre est également soumis à des exigences plus élevées. Il sera mis en évidence dans les articles suivants.

1.4 TXDAG et BlockDAG

La différence entre le BlockDAG généralisé (bloc graphique) et le TxDAG (Transactional DAG, DAG transactionnel). De manière générale ou en termes de structures de données, BlockDAG et TxDAG ne sont que deux structures de données différentes. La différence est que le premier regroupera plusieurs transactions en blocs et que le grand livre est organisé par blocs; tandis que ce dernier n'a pas de concept de blocs, et le grand livre est composé de transactions, qui peuvent également être comprises comme une seule transaction dans un bloc. Étant donné que la transaction comporte de nombreuses informations descriptives de transaction communes, c'est-à-dire les informations d'en-tête, cette partie des informations peut être stockée dans le bloc, et la transaction n'a besoin que de sauvegarder les différentes parties de la transaction, de sorte que le processus HASH (extraction) est sauté et la chaîne téléchargée directement. Étant donné que BlockDAG conserve non seulement la haute simultanéité de DAG,

1.5 Avantages du DAG

Comparé à la blockchain, DAG est en fait la différence entre un graphe et une chaîne. Pour une chaîne, il ne peut pas traiter qu'une seule partie, car il n'y a qu'un seul degré d'entrée et un seul degré de sortie de la chaîne, et les nœuds de la chaîne ne peuvent pas être divisés en plusieurs nœuds à traiter, mais c'est possible pour les graphes, étant donné que les graphiques peuvent avoir plusieurs degrés sortants, les nœuds connectés par plusieurs degrés sortants peuvent être traités en même temps.

Pour le réseau en chaîne, ce n'est pas que la capacité de traitement des nœuds n'est pas forte, mais la structure de la chaîne ne peut pas être calculée en parallèle, et le temps perdu est principalement du temps d'attente : l'un consiste à initier une transaction, qui doit être synchronisée. avec tous les nœuds ; l'autre est le temps de confirmation, lorsqu'il y a une confirmation de nœud qui doit être synchronisée avec l'ensemble du réseau. Pour DAG, il n'y a pas un tel problème. Lorsque le portefeuille initie une transaction, il n'a pas besoin d'attendre le nombre de transactions qu'il a déjà effectuées. Il suffit de passer par une vérification partielle, une diffusion sur le réseau et une autre vérification partielle, ce qui équivaut à décentraliser la confirmation de la transaction. Les nœuds font un travail similaire à des énigmes, en fusionnant leurs propres transactions avec celles confirmées par d'autres.

Par conséquent, il est conclu que DAG présente les avantages suivants :

(1). Vitesse de transaction rapide

Tout en atteignant le même niveau de décentralisation et de sécurité que Bitcoin et Ethereum, le traitement local DAG et le règlement parallèle peuvent considérablement augmenter la vitesse des transactions, ce qui favorise le débit des transactions (TPS) et le délai final de plus de deux ordres de grandeur.

(2). Forte extensibilité

Étant donné que DAG prend en charge la comptabilité asynchrone, les nœuds du réseau peuvent traiter de nouvelles transactions en parallèle sans attendre la synchronisation des données des autres nœuds, évitant ainsi la perte de temps, améliorant l'efficacité des transactions et permettant à chaque nœud participant à la comptabilité d'être considérablement étendu rapidement. Par conséquent, DAG convient parfaitement aux projets de paiement, tels que le micropaiement transfrontalier et les scénarios d'entreprise financière inclusive préconisés par l'équipe Qitmeer.

(3). Plus difficile à modifier de manière malveillante

Par rapport à la structure de la chaîne, il est beaucoup plus difficile de modifier de manière malveillante dans un DAG car le DAG a de nombreux degrés sortants et entrants, et si un nœud est modifié, les degrés entrants correspondants doivent être modifiés.

2. Passé et présent du MEERDAG

2.1 Origine de la technologie DAG

En 2013, sur bitcointalk.org, le célèbre berceau de la blockchain, un chercheur de l'Université hébraïque israélienne avec l'ID Avivz78 a proposé d'introduire le concept DAG en tant qu'algorithme de consensus dans la structure de la blockchain et a créé le protocole GHOST.

Après la proposition du protocole GHOST, Yonatan Sompolinsky a proposé une autre nouvelle idée où les blocs nouvellement générés pointent vers tous les blocs d'extrémité fourchus connus, c'est-à-dire qu'un bloc a plusieurs pères, à quel point

la chaîne de blocs passe d'une chaîne unique à une structure composée de plusieurs chaînes fourchues ensemble, et une telle structure de chaîne est appelée DAG (graphe acyclique dirigé).

En 2016, le document de protocole technique SPECTRE a été publié, qui a encore amélioré les détails de l'architecture technique, formé le prototype du protocole blockDAG de première génération et proposé la grande idée du retard du réseau sans paramétrage (ou adaptation des paramètres de retard).

En 2018, DAGlabs a lancé le protocole PHANTOM. Résolution du problème selon lequel le protocole SPECTRE ne peut pas échanger le tri linéaire et poursuite de son optimisation pour former le protocole GHOSTDAG, qui est le premier protocole BlockDAG de qualité industrielle et marque également la maturité de BlockDAG.

À la fin du document sur le protocole GHOSTDAG, Yonatan Sompolinsky a envisagé un protocole possible combinant GHOSTDAG + SPECTRE, mais ne l'a pas présenté en détail

3. Réflexions sur le choix technologique de MEERDAG

3.1 Réflexion sur le choix de la technologie MEERDAG

Dans la première étape de Qitmeer Network, Mecca Network, cela a coïncidé avec la recrudescence de l'exploration des technologies d'expansion, face à de nombreuses solutions d'expansion grand public en chaîne et hors chaîne, lors de la sélection de la technologie de la chaîne publique Qitmeer, il a également été confronté à un choix difficile.

En termes de choix de technologie d'expansion, l'industrie est généralement confrontée à un problème de triangle impossible. Il est impossible d'atteindre l'évolutivité (Scalability), la décentralisation (Decentralization) et la sécurité (Security) en même temps, et seulement deux des trois peuvent être atteints. L'équipe de Qitmeer à cette époque était également confrontée à un tel problème. Après avoir étudié de nombreuses solutions d'extension, une technologie appelée BlockDAG a finalement été privilégiée par l'équipe.

3.2 Brève introduction au protocole SPECTRE

SPECTRE est un protocole blockDAG qui prend en charge la confirmation rapide. L'algorithme de consensus de SPECTRE est un algorithme de vote. Une fois qu'une transaction en conflit est trouvée, le bloc contenant la transaction en conflit sera utilisé comme candidat pour accepter les votes de tous les blocs, avec un vote pour chaque bloc. Le vote de SPECTRE a un effet d'amplification. Par exemple, un bloc suivra la majorité des votes sur lesquels il s'est concentré dans le passé, donc la vitesse de convergence est très rapide, et une légère différence dans le nombre de votes peut entraîner un énorme avantage pour le vainqueur. Laissez les blocs honnêtes voter pour les blocs honnêtes, et les derniers blocs honnêtes donneront le pouvoir d'empilement précédent, de sorte que les attaques malveillantes échoueront et que la sécurité du réseau sera garantie.

SPECTRE ne peut garantir qu'une confirmation rapide des blocages honnêtes. Pour deux blocs en conflit dont l'heure de libération est proche, l'heure de confirmation de SPECTRE est incertaine. C'est le concept d'activité faible proposé par SPECTRE, c'est-à-dire qu'il ne peut être garanti que tous les blocs puissent être confirmés définitivement dans un délai raisonnable.

SPECTRE est un protocole de consensus basé sur le système de transaction. Dans le système de transaction, seuls les malfaiteurs peuvent créer des transactions à double dépense. C'est-à-dire que les transactions à double dépense n'auront pas beaucoup d'impact sur les blocs honnêtes. De plus, effectuer des transactions à double dépense est très strict sur le contrôle du temps et il est difficile de provoquer des attaques dans des circonstances normales. Par conséquent, l'équipe Qitmeer estime que le problème de la faible activité de SPECTRE est acceptable dans les projets réels.

3.3 Brève introduction au protocole GHOSTDAG

Comme vous pouvez le voir sur le profil SPECTRE ci-dessus, SPECTRE est très efficace pour dépanner les transactions conflictuelles et se défendre contre les attaques. Si un projet n'est utilisé qu'à des fins de paiement comme Bitcoin, la confirmation rapide du protocole SPECTRE est suffisante. Mais si vous souhaitez intégrer des contrats intelligents, SPECTRE ne peut pas le faire.

Parce que SPECTRE ne peut faire qu'un tri relatif des transactions en conflit (en jugeant l'ordre des transactions en conflit), mais il ne peut pas faire un tri absolu pour tous les blocs. Parce que le langage du contrat intelligent doit être Turing complet, tout comme nous écrivons un morceau de programme informatique, nous devons effectuer diverses opérations dans un ordre strict, de sorte que le réseau avec la fonction de contrat intelligent a une caractéristique : les transactions dans le réseau peuvent être chronométré Effectuez un tri linéaire (chronologique) l'un après l'autre.

En réponse, Yonatan Sompolinsky a récemment conçu le protocole GHOSTDAG pour former un ordre linéaire vers les blocs DAG. SPECTRE et GHOSTDAG sont deux protocoles complets et indépendants, l'un ne se complétant pas.

Le mécanisme de minage de GHOSTDAG est le même que celui de SPECTRE, qui va générer le même type de structure DAG. La différence est que GHOSTDAG juge si le bloc est honnête ou malveillant en analysant la connectivité du bloc, trie les blocs en fonction de la classification et génère un bloc DAG strict. L'ordre linéaire de la transaction conflictuelle est jugé par l'ordre linéaire.

Le protocole GHOSTDAG permet non seulement à DAG d'obtenir des capacités de commande linéaire des transactions, mais résout également le problème de faible activité du protocole SPECTRE. Le protocole GHOSTDAG est également le premier protocole blockDAG qui prend en charge l'ordre linéaire des transactions.

3.4 Protocole MEERDAG

Le protocole possible combinant GHOSTDAG + SPECTRE que Yonatan Sompolinsky envisageait à la fin du document de protocole GHOSTDAG consiste davantage à fournir des conseils en termes d'idées, et l'accent est mis sur la démonstration de la rigueur de l'algorithme, qui implique de nombreux problèmes de pratique d'ingénierie et doit être basé sur la réalité La situation est constamment pratiquée et testée, et l'un des problèmes les plus typiques est la performance. S'il est implémenté directement selon l'algorithme de référence dans le texte original, les performances sont presque inacceptables.

L'équipe Qitmeer considère que les scénarios d'application sous-jacents de la chaîne publique sont principalement la finance inclusive, les transactions d'actifs numériques et la gestion de la chaîne d'approvisionnement.

En tenant compte du mécanisme de récompense en bloc et des exigences de consensus du grand livre pour les capacités de tri linéaire, et en même temps en tenant compte de la vitesse de confirmation des transactions qui est plus importante pour l'expérience d'échange de valeur.

L'ensemble bleu (bloc honnête) de GHOSTDAG est plus difficile à stabiliser et le temps de confirmation sera bien plus long que celui de SPECTRE. Cependant, comme la récompense de bloc ne nécessite pas de temps de confirmation élevé, elle n'affectera pas le réseau. Le protocole GHOSTDAG est choisi comme protocole de consensus de base et le protocole SPECTRE est choisi comme protocole de consensus assisté.

MeerDAG, une solution de consensus hybride combinant SPECTRE et GHOSTDAG, est une solution de mise à l'échelle BlockDAG qui se conforme aux paramètres de blockchain classiques (ouvert, équitable, sécurisé, évolutif) et est le plus compatible avec le modèle de blockchain classique UTXO. Alors que la blockchain classique supprime tous les blocs en dehors de la chaîne la plus longue, MeerDAG est un modèle coopératif qui conserve le protocole SPECTRE et conserve tous les blocs, de sorte qu'il peut atteindre un débit élevé et fournir un débit élevé au niveau de la transaction, ainsi qu'une confirmation rapide de la transaction blockchain. prestations de service. Deuxièmement, BlockDAG est basé sur la règle de chaîne la plus lourde et peut atteindre une tolérance aux pannes de 51% comparable à Bitcoin. De plus, le réseau BlockDAG n'a pas de nœuds spéciaux et ne nécessite pas que les nœuds soient en ligne ou non. Dans les mines,

Pendant la période de Qitmeer Network Medina, le réseau a introduit des tests d'environnement de puissance de calcul réels. L'équipe a continuellement itéré l'algorithme PoW et amélioré l'efficacité de l'algorithme, conservé pleinement les avantages du protocole GHOSTDAG + SPECTRE et réduit continuellement la difficulté de mise en œuvre du protocole dans la mise en œuvre de l'ingénierie. Par exemple : selon la première version des articles sur l'algorithme GHOSTDAG, le calcul des cônes inverses doit être exhaustif et la complexité de l'algorithme est O(n^3). Après un grand nombre de tests de niveau ingénierie, la complexité est réduite de deux ordres de grandeur à O(n), ce qui répond largement aux exigences d'utilisabilité. Dans le cadre des exigences fondamentales de sécurité, de décentralisation et d'équité, les performances du TPS sont maximisées.

L'équipe Qitmeer a combiné de manière innovante le protocole GHOSTDAG + SPECTRE pour former son propre protocole caractéristique MeerDAG, qui est devenu le prototype technique de la nouvelle génération de BlockDAG. Le positionnement central du réseau sous-jacent BlockDAG de Qitmeer est de servir de réseau de circulation de valeur. Sur la couche de couche 2, il combine le système de machine virtuelle enfichable piloté par MeerEVM pour créer des applications de blockchain riches et embrasser l'ensemble de l'écologie de la blockchain.

Référence：
[1] De la blockchain au DAG (2) -- la structure de base du DAG,https://mp.weixin.qq.com/s/Mc2uEOLtT_Z3OMapNh1TGg
[2] Des Blockchains aux blockDAG，https://www.youtube.com/watch?v=tk38AAV_whw
[3] Jeff Zhou：Technologie blockchain asynchrone haute vitesse DAG，https://www.jianshu.com/p/45d73e0e74ec
[4] Théorie technique FANTÔME, SPECTRE, FANTÔME,https://mp.weixin.qq.com/s/nGR0ld73oXgs_p_MtDcv-Q
[5]Équipe Qitmeer - "Livre blanc de Qitmeer"