Qu’est-ce qu’un DAG ou graphe orienté acyclique ? (Directed Acyclique Graph)

directed acyclic graph dag graphe oriente acyclique

Introduction

Depuis l’arrivée du protocole Bitcoin, beaucoup de blockchains ont adopté la même architecture de réseau et pour cause, jusqu’à aujourd’hui, elle est reconnue comme l'une des plus fiable et sécurisé. 

Son concept est basé sur une chaine de bloc relié entre eux par des Hash avec une mempool dans laquelle les transactions patientent en attendant d’être intégrées aux blocs. 

Bien que parfois, il faille attendre de plusieurs minutes à plusieurs heures pour qu’une transaction soit incluse dans un bloc, c'est une architecture qui semble être très appréciée par les utilisateurs. 

Cependant, les innovations technologiques ont fait émerger une nouvelle architecture au sein des réseaux distribués appelés DAG (Directed Acyclique Graphe) ou graphe orienté acyclique en français. 

Qu’est-ce qu’un DAG ?

Un DAG ou Directed Acyclique Graph est une ancienne structure mathématique qui s’est démocratisée dans le domaine de l’informatique. Elle est utilisée pour créer un modèle de réseaux reliant les nœuds qui le compose. 

Pour commencer, attardons-nous sur chacun de ces termes. 

Un Graphe est un modèle de réseau reliant des nœuds appelés “sommet” qui les composent.  

Les graphes sont composés de plusieurs familles comme les arbres (merkles tree), mais aussi les chaines de nœuds ou de blocs dans le cadre de Bitcoin. 

Un DAG est donc composé de nœuds appelés sommet, mais aussi d’arêtes qui les relient entre eux

Le mot “dirigé” dans son nom signifie que chaque arrête à une direction bien définie de sorte que chaque arête représente nécessairement un flux directionnel comme le représente les flèches sur le schéma ci-dessous. 

Structure d'un DAG

En d'autres termes, toutes les arêtes sont dirigées dans le même sens. 

Le mot “acyclique” lui signifie que le graphe est non cyclique et que donc vous ne pourrez jamais repasser 2 fois par le même sommet au fil de la navigation dans le graphe. 

On dit d’un graphe qu’il est acyclique lorsqu’il ne possède pas de cycle de déplacement, mais nous y reviendrons. 

Les DAGs sont utiles pour représenter de nombreux types de flux différents, y compris les flux de traitement des données. Dans un modèle de registre distribué, ils seront utilisés afin d’obtenir un consensus

Comment fonctionnent les DAGs ?

Contrairement à une blockchain classique qui elle aura une structure linéaire, le DAG lui adoptera une architecture de parallélisation. 

Pour faire simple, une blockchain classique reliera ses blocs de manière linéaire, ce qui signifie qu’un bloc est uniquement relié au bloc précédent et ainsi de suite.

En revanche un DAG lui fonctionne de manière à éviter tout conflit lié à l’utilisation d’un historique linéaire. Les nœuds présents dans un DAG contrairement à une blockchain peuvent avoir plusieurs nœuds parents. 

Par exemple, si nous comparons ça à des mises à jour sur un jeu vidéo, une version 3.0 de ce jeu ne pourrait être liée qu’à la version précédente soit la 2.0. Le DAG lui permet de lier la version 3.0 à la une et la 6.0 relira la 3.0 et la 2.0 par exemple. 

comparaison DAG vs  Blockchain

Les DAG ont un point de départ appelé “origine” et un point d’arrivée appelé “puits” 

En effet, un des grands points forts du DAG est sa capacité à paralléliser les transactions. Cela optimise sa capacité à vérifier la relation entre les sommets et les informations qu’ils peuvent contenir. C’est ainsi que le consensus fonctionne au cœur d’un DAG. 

Une autre spécificité du DAG qui en fait ça force est sa capacité à être réductible. Cela signifie que la structure d’un DAG peut être réduite à un point optimal ou les chemins rencontrent toutes les relations qui y sont spécifiées sans aucune perte. 

En d'autres termes, il est possible de réduire les relations entre les sommets ou blocs à un point minimum qui n’affectera pas sa capacité à vérifier les informations d’un sommet à n’importe quel moment.

Les inconvénients des DAG 

Lorsque l’on parle de DAG, le défaut le plus évoqué est celui de la centralisation. En effet, si ces éléments qui centralisent le réseau persistent, alors les réseaux fonctionnant en DAG nécessiteront toujours l’intervention d’un tiers pour fonctionner. Cet aspect est relativement important, car étant donné la nature plus centralisée des DAG, leur sécurité en est par conséquent plus limitée. 

Également, cette technologie bien que déjà utilisé sur certains réseaux comme IOTA depuis quelque temps n’a encore jamais été soumis à de forts volumes de transaction ce qui, après quoi, pourrait justifier la pertinence de son utilisation.  

Conclusion

Les projets établis autour d’un DAG sont encore peu nombreux. Il est donc difficile d’établir un jugement autour de cette technologie. Cependant, elle a montré une certaine capacité à répondre à certaines problématiques bien que pas encore appliqué à grande échelle. 

Il sera intéressant dans les années à venir d’observer son adoption par certains projets ainsi que de voir si cette technologie sera capable de résoudre tous les challenges qui l’attendent dans le monde des crypto monnaies et des réseaux distribués.