Qu'est-ce qu'un DAG (Directed Acyclic Graph) ?

1. Qu'est-ce qu'un DAG ?
2. Quelques applications du DAG dans l'industrie des cryptomonnaies
3. Comment fonctionnent les DAG ? 
4. Avantages et inconvénients de l'utilisation d'un DAG
5. Conclusion sur les DAG

Qu'est-ce qu'un DAG ?

Le DAG, acronyme de « Directed Acyclic Graph », signifiant « graphe orienté acyclique » en français, est un type de graphe qui trouve son origine dans l'Histoire avant même que la théorie des graphes ne soit définie. En effet, un DAG est un ensemble de noeuds représentant quelque chose, qui sont reliés entre eux directement de manière à ce qu'il n'y ait aucune boucle.

En 1736, Leonhard Euler, un mathématicien suisse, parvient à résoudre le problème des sept ponts de Koenigsberg en utilisant ce qui est considéré comme le premier théorème de la théorie des graphes.

Ce problème consistait à déterminer s'il existait un chemin dans les rues de la ville par lequel il était possible de passer pour n'emprunter qu'une seule fois chacun des sept ponts et revenir au point de départ.

Figure 1 : Illustration du problème des sept ponts de Koenigsberg

À partir de là, la théorie des graphes est devenue un domaine d'étude s'intéressant aux relations entre les objets représentés par des structures mathématiques (graphes).

Les types de graphes sont nombreux, et le Directed Acyclic Graph (DAG) est l'un d'entre eux.

L'un des plus anciens modèles de DAG est simplement l'arbre généalogique. Ce modèle est utilisé depuis la Rome antique pour illustrer les liens familiaux entre les individus.

L'arbre généalogique est un graphe qui est orienté puisqu'il se dirige vers une seule direction (des ancêtres vers les descendants) via des liens directs, et acyclique puisque personne ne peut être son propre parent : pas de retour en arrière possible.

Un autre modèle de DAG très ancien est simplement la planification des tâches. La complexité du graphe varie selon l'ampleur de ce que l'on cherche à accomplir, que ce soit une recette de cuisine ou la planification d'une guerre.

Le DAG n'est donc pas une invention de ces dernières années, c'est une méthode ancienne pour résoudre divers problèmes, et c'est notamment beaucoup utilisé en informatique pour modéliser les données. Ce qui nous intéresse particulièrement ici est l'application du DAG dans le cadre de la technologie des registres distribués.

Figure 2 : Schéma d'un DAG

Un DAG possède donc une structure arborescente, qui n'a que des liens directs entre ses nœuds et aucun cycle, c'est-à-dire que vous ne pouvez pas retomber sur le même nœud au fil de la navigation dans le graphe. Cela permet donc une navigation directe de nœud à nœud par le biais des liaisons de ces derniers.

Figure 3 : Schéma simplifié d'un DAG avec ses liens directs et sa nature acyclique

Nous voyons que dans la figure 3 représentant une simplification du DAG, la direction est claire : du noeud en bas à droite vers le noeud en haut à gauche, reliés par des liens directs. Il est donc orienté vers une seule direction et acyclique puisqu'il ne revient pas en arrière.

Cela permet au DAG de traiter des transactions en simultanées, offrant à cette technologie un niveau élevé de scalabilité, car c'est là l'un des arguments principaux de l'utilisation d'un DAG dans l'industrie des cryptomonnaies.

👉 Pour en savoir plus : Qu'est-ce que la scalabilité ?

Quelques applications du DAG dans l'industrie des cryptomonnaies

Fantom (FTM)

Fantom est une plateforme de smart contracts utilisant un DAG pour résoudre le problème de scalabilité des blockchains.

IOTA (MIOTA)

Cette cryptomonnaie repose sur un DAG nommé Tangle, et utilise un consensus de la Proof of Work (PoW). Ce DAG est conçu pour enregistrer et exécuter les transactions entre les machines et les appareils de l'Internet of Things (IoT), mais aussi pour proposer un moyen d'en monétiser les données. L'Internet des Objets requiert une scalabilité très élevée, ce qui explique le choix du DAG pour ce projet.

Figure 4 : Représentation du DAG de IOTA

Nano (NANO)

Le Nano est une cryptomonnaie ayant pour ambition d'être une alternative aux monnaies fiat grâce à ses transactions instantanées et sans frais, ainsi qu'une faible consommation énergétique. Pour cela, elle s'appuie sur un DAG pour tenter d'atteindre ces objectifs.

Avalanche (AVAX)

Avalanche est une plateforme dédiée au déploiement de smart contracts. Son consensus éponyme se sert d'un DAG afin de traiter de multiples transactions en parallèle et ainsi améliorer la scalabilité du réseau.

Hedera Hashgraph (HBAR)

Ce réseau s'appuie sur son système de transmission d'informations, le protocole Gossip, qui est concrètement un DAG, afin de tenter de résoudre le trilemme de la blockchain (sécurité, scalabilité et décentralisation) auquel font face les blockchains.

Comment fonctionnent les DAG ?

Les DAG sont donc des structures composées de deux types d'éléments différents, les nœuds et les liaisons entre ces derniers. Cela peut être utilisé dans le cadre de la conservation d'un historique de données comme les versions d'un logiciel ou les interactions entre des utilisateurs.

Cela permet notamment d'éviter les conflits liés à l'utilisation d'un historique linéaire dans lesquels l'ajout d'un nouvel élément doit être directement lié à l'élément le plus récent et uniquement ce dernier.

Dans le cadre des versions d'un logiciel, la version 5 ne peut être liée qu'à la version 4 dans un cadre linéaire. En utilisant un DAG, cette version peut être liée à la version 3 alors que la version 6 reliera les versions 4 et 5.

Il suffit de spécifier le ou les nœuds parents pour ajouter de nouvelles données à un DAG et définir les liaisons entre ces derniers. En ce qui concerne le parcours d'un DAG, il existe différents algorithmes qui possèdent chacun leurs propres spécificités. L'utilisation d'un DAG facilite l'utilisation de certains algorithmes par rapport à d'autres graphes plus généralistes, c'est le cas notamment de la recherche des chemins les plus courts ou plus longs entre deux noeuds spécifiques.

Quelles différences entre un DAG et une blockchain ?

Certains considèrent le DAG comme une technologie rivale de la blockchain, puisqu'il s'agit d'un autre type de registre distribué. Quelles sont les différences entre ces deux systèmes ?

Figure 4 : Représentation d'une blockchain et d'un DAG

Comme nous le voyons sur la figure 3, la blockchain est un registre distribué qui forme une chaîne de blocs dans un ordre chronologique. Les transactions sont groupées dans un bloc qui est validé et ajouté à la suite de blocs précédemment validés.

Bien que deux blocs (ou plus) puissent théoriquement être validés en même temps par les mineurs, seulement l'un des deux sera rattaché à la chaîne principale, l'autre étant ce que l'on appelle un bloc périmé (blocs violets sur le schéma).

À cause de cela, s'il y a plus de transactions effectuées que la limite de transactions qu'un bloc peut incorporer dû à la limite d'espace de stockage, il est nécessaire d'attendre le bloc suivant, ce qui cause un délai dans la confirmation des transactions, cela mène potentiellement à une congestion du réseau si de trop nombreuses transactions sont en attentes.

Un DAG n'est pas confronté à ces problèmes puisqu'il n'y a pas de blocs à proprement parler. Un DAG est un réseau de transactions individuelles reliées à de multiples autres transactions. Les transactions sont donc directement ajoutées au registre, il n'y a quasiment aucun délai donc l'exécution des transactions est très rapide.

Les transactions individuelles se valident les unes les autres à travers un procédé qui confirme les transactions précédentes avec les nouvelles transactions.

Avec un DAG, pour qu'une nouvelle transaction A soit ajoutée au registre, elle doit faire référence à plusieurs transactions antérieures. Ensuite, il faudra attendre une nouvelle transaction B qui référence notamment la transaction A pour que celle-ci soit confirmée. Cela explique aussi les frais de transactions très bas dans un DAG, mais également qu'un DAG a besoin d'un niveau d'adoption adéquat pour fonctionner correctement.

Pour éviter le problème de la double dépense sur un DAG, lorsqu'une transaction précédente est confirmée, le noeud vérifie la totalité d'un chemin à partir de cette transaction jusqu'à la première transaction du DAG. Ainsi, si un chemin ne remonte pas jusque là, aucun noeud ne voudra le valider.

Chaque transaction possède un poids cumulé différent, c'est-à-dire un nombre de transactions confirmées cumulées différent. Ainsi, celles qui possèdent un poids plus élevé seront favorisées par un algorithme pour que le DAG se développe autour et améliore la sécurité du réseau.

Enfin, la plupart des cryptomonnaies basées sur un DAG opèrent sur une variante de la Proof of Stake (PoS) puisqu'il n'est pas nécessaire d'avoir des mineurs, à l'exception de Iota et sa Proof of Work (PoW) partielle afin d'améliorer la sécurité du réseau.

La blockchain pourrait être simplement résumée à une liste de blocs tandis qu'un DAG pourrait être assimilé à un arbre de transactions.

Avantages et inconvénients de l'utilisation d'un DAG

Avantages

Un DAG n'a pas besoin de dépendre de la Proof of Work classique afin de valider les transactions. Ce qui signifie qu'il n'a pas besoin de blocs et donc de chaîne, ce qui est un gain certain en termes de consommation énergétique.

Un DAG permet d'offrir un haut niveau de scalabilité au réseau de par son architecture puisqu'il n'est pas limité par les blocs. Cela, couplé à des frais de transactions extrêmement bas, voire inexistants, et des transactions rapides, en font l'argument principal de l'application d'un DAG dans un registre distribué.

Inconvénients

Le manque de décentralisation est le défaut principalement mentionné lorsque l'on parle d'un DAG. La plupart des protocoles opérant sur un DAG ont besoin de maintenir certains éléments qui font de ce dernier une technologie relativement centralisée. Les DAG ont encore tout à prouver pour déterminer s'ils peuvent évoluer de façon indépendante, car cela pose un risque au niveau de la sécurité du réseau qui est potentiellement plus vulnérable aux attaques.

? Plus d'infos sur la notion de décentralisation

Enfin, un DAG n'a encore jamais été soumis à un niveau très élevé de volume de transactions. Il y a bien entendu plusieurs cryptomonnaies opérant sur un DAG depuis plusieurs années, mais celles-ci ont encore beaucoup de chemin à faire avant d'atteindre une adoption suffisamment élevée pour éprouver la technologie sur une grande échelle.

Conclusion sur les DAG

Les cryptomonnaies opérant sur un DAG sont encore peu nombreuses, mais cette technologie peut s'avérer particulièrement utile dans des domaines qui requièrent un haut niveau de scalabilité comme les micro-paiements ou l'Internet des Objets.

Il sera également important d'observer dans le futur si le DAG a la capacité d'offrir un niveau élevé de décentralisation à mesure qu'il évolue. Cela dit, il reste une alternative intéressante à la blockchain pour les registres distribués.

👉 Retrouvez tous nos guides pour en savoir plus sur l'écosystème des cryptomonnaies

Cet article a été mis à jour Jessy Aouali

Sources - Figure 1, 2 et 3 : Medium de Fantom Foundation ; Figure 4 : Blog de Iota

Passionné par les crypto-monnaies, j’ai rapidement appris à développer des outils dans le domaine des technologies blockchain. J’aime partager mes connaissances sur le sujet et je participe activement au rayonnement des aspects techniques de la blockchain au sein de la communauté crypto. Je suis principalement intéressé par Ethereum et par son code Solidity.

Guillaume Chanut

62 articles

Tous ses articles