Un graphe orienté acyclique, ou Directed Acyclic Graph (DAG) en anglais, est une structure de données très utilisée en informatique (traitement de données, réseaux neuronaux, robotique...) Les DAG sont aussi utilisés dans certaines technologies de registre distribué (DLT) pour valider les transactions sans recourir à la création de blocs.
Bien que leur nom paraisse complexe, les DAG sont des structures simples à conceptualiser, et sont apparus bien avant la théorie des graphes. Par exemple, un arbre généalogique est un graphe orienté acyclique basique.
Structure d'un DAG
Un DAG prend la forme d'un graphe arborescent :
Dans le contexte des DLT et des cryptomonnaies, il permet de relier les transactions les unes aux autres.
Cette structure est acyclique : en effet, elle ne présente jamais pas de « boucles » ou de « cycles ». Elle est également orientée, signifiant que les transactions sont reliées les unes aux autres dans une même direction, ce qui permet de les orienter dans le temps. Chaque « nœud » du graphe correspond à un sommet, et représente une transaction. Les transactions se construisent donc les unes sur les autres selon un ordre chronologique. Ainsi, sans recourir à un regroupement en blocs, un DAG permet de valider et confirmer les transactions au fur et à mesure de leur exécution.
Dans un DAG, il existe donc plusieurs chemins possibles. L'émission d'une nouvelle transaction nécessite de s'attacher à plusieurs transactions antérieures. Un algorithme peut permettre de sélectionner les transactions antérieures à privilégier, généralement en choisissant celles qui ont accumulé le plus de transactions confirmées sur leur chemin.
La confirmation de la transaction implique qu'une nouvelle transaction s'est attachée à la transaction en attente de confirmation. Dès lors, la transaction est confirmée, et les confirmations s'effectuent ainsi transaction après transaction. Publier une transaction implique de confirmer des transactions plus anciennes.
Il peut néanmoins exister des problèmes de conflits puisque plusieurs transactions peuvent être confirmées simultanément. Les DAG sont par ailleurs très complexes et donc difficile à mettre en place sur un réseau d'envergure.
DAG et cryptomonnaies
Plusieurs cryptomonnaies utilisent des graphes orientés acycliques.
IOTA
IOTA est un réseau de paiement dédié à l'IoT (Internet des objets). Son DAG est appelé Tangle (enchevêtrement en anglais) :
Pour chaque nouvelle transaction, deux transactions aléatoires non confirmées sont validées dans le Tangle. Chaque validation augmente la probabilité que la transaction soit authentique, jusqu'à atteindre un seuil. Une fois que le seuil est atteint, elle est confirmée. Dans le schéma ci-dessus, les transactions vertes sont confirmées, les transactions rouges sont validées mais n'ont pas atteint le seuil, et les transactions grises n'ont pas encore reçu de validation.
Le Tangle d'Iota fut vivement critiqué, car bien que les utilisateurs puissent valider les transactions, il fut longtemps centralisé par un nœud coordinateur unique. Désormais, il est remplacé par un comité de validateurs.
Hedera Hashgraph (HBAR)
Le mécanisme de consensus d'Hedera repose sur trois éléments : son DAG (le hashgraph), un protocole de bavardage pour propager les transactions, et un système de vote.
Avec le protocole Hashgraph, les nœuds échangent des informations. Ces ensembles d'informations sont appelés événements, et chaque événement doit avoir au moins deux parents pour être valide.
D'autres réseaux biens connus utilisent des DAG au sein de leur architecture, comme Avalanche (AVAX) et Nano (NANO).
Les point forts des DAG
Les DAG présentent des performances supérieurs aux blockchains classiques :
- Traitement parallèle : les réseaux basés sur des DAG n'ont pas besoin de traiter les transactions dans un ordre particulier. Ainsi, la validation et l'exécution des transactions est répartie uniformément dans le temps, ce qui réduit les périodes d'inactivité des nœuds. De plus, une grande quantité de transactions peuvent être traitées en même temps. La parallélisation des tâche permet de réduire les coûts en calculs et la congestion du réseau. En d'autres termes, les DAG présentent une bien meilleure scalabilité que les blockchains.
- Validation continue : le processus de validation des transactions est continu, ce qui optimise l'utilisation des ressources.
- Pas d'intermédiaires : il n'y a pas de mineurs. Les utilisateurs soumettent directement leurs transactions au mécanisme de consensus du réseau. La résistance à la censure est totale.
- Utilisateurs acteurs du consensus : les systèmes de validation sont mieux distribués, car tout utilisateur peut participer au processus.
Critiques
L'utilisation des DAG plutôt que des blockchains pour maintenir le consensus d'un réseau de paiement crypto est une innovation. Cependant, la sécurité de ces architectures est régulièrement remise en cause. Bien qu'aucun DAG n'ait été piraté (falsification de transactions ou double-dépenses), certains éléments externes (smart contracts, wallets) ont déjà présenté des défaillances.
Il est important de mentionner que les algorithmes de consensus basés sur des DAG sont aussi sûrs que les algorithmes PBFT classiques : ils tolèrent jusqu'à 33 % de nœuds défaillants. Tous les piratages ayant eu lieu sur des plateformes DAG reposent sur l'exploitation de failles qui n'ont rien à voir avec l'architecture en DAG du registre de transactions.
