# Maximiser un sous-DAG sans conflit

Quentin Bramas

► To cite this version:

Quentin Bramas. Maximiser un sous-DAG sans conflit. ALGOTEL 2025 – 27èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2025, Saint Valéry-sur-Somme, France. hal-05029394

HAL Id: hal-05029394

https://hal.science/hal-05029394v1

Submitted on 10 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Maximiser un sous-DAG sans conflit

Quentin Bramas<fnref n="1" />

¹ Université de Strasbourg, ICube, CNRS

Les registres distribués basés sur des graphes acycliques dirigés (DAG) constituent une alternative prometteuse aux blockchains traditionnelles, notamment pour améliorer le passage à l'échelle. Dans ce cadre, la sélection d'un sous-ensemble de blocs sans conflit est un enjeu clé. Le problème consiste à trouver un sous-DAG sans conflit dont le poids est maximum. Ce problème généralise celui de la recherche de la chaîne la plus lourde dans une blockchain traditionnelle. Ce dernier étant trivial dans un arbre, nous montrons qu'il est NP-complet dans un DAG. Ensuite, nous présentons un algorithme qui est polynomial lorsque le nombre maximum de blocs conflictuels concurrents est borné. Cet algorithme est donc très efficace lorsque peu de conflits arrivent simultanément. Nos résultats montrent des améliorations significatives par rapport aux stratégies existantes.

**Mots-clefs** : Blockchain, Livre de compte distribué, Sécurité

## 1 Introduction

Les technologies de registre distribué (DLT) permettent de maintenir une structure de données ne permettant que l'ajout de données de manière décentralisée. Dans Bitcoin, cette structure est une chaîne de blocs où chaque bloc référence un unique prédécesseur, formant ainsi une chaîne linéaire. Cependant, en cas de conflits, un bloc peut avoir plusieurs successeur. La structure est alors un arbre et pour garantir la cohérence du registre en présence de conflits, Bitcoin applique une règle simple : étendre la branche la plus lourde, c'est-à-dire celle maximisant la somme des poids (la quantité de travail réalisée par la preuve de calcul) des blocs. Cette règle sert à la fois à « décider » l'état actuel du registre et aussi à permettre une convergence vers un état cohérent commun à tous les participants.

Les DLT basés sur des graphes acycliques dirigés (DAG), généralisent cette approche en permettant à un bloc de référencer plusieurs prédécesseurs. Cette flexibilité améliore la scalabilité mais complexifie la gestion des conflits. Avec une telle technologie, les blocs forment un DAG et la règle de sélection de l'état courant doit être généralisée. Dans le cas d'une chaîne de bloc la règle de sélection peut s'exprimer d'une autre manière : à chaque embranchement de l'arbre, on ne conserve que la branche la plus lourde. Lorsque cette méthode est appliquée en commençant par les feuilles, la chaîne finale obtenue vérifie la règle énoncée plus haut. Lorsque cette méthode est appliquée en commençant par la racine (le bloc genesis), alors on obtient la variante GHOST. Dans le protocole IOTA, qui exploite une structure en DAG, l'algorithme de sélection utilise une version itérative probabiliste similaire. D'autres algorithmes, comme GHOSTDAG, ont des approches similaires dans le but de construire un sous-DAG sans-conflit ayant certaines propriétés.

Dans ce travail, nous proposons une approche directe visant à sélectionner le sous-DAG sans conflit le plus lourd, pour généraliser la règle de la chaîne la plus lourde aux DAGs. Nous montrons que ce problème est NP-complet et analysons les sources de cette complexité. Nous proposons ensuite un algorithme optimal dont la complexité est polynomial sous le paramètre du nombre de blocs conflictuels concurrents. Nous démontrons ses performances par rapport aux solutions existantes, notamment GHOSTDAG.<fnref n="1" />

<footnote n="1">¹Les résultats présentés ici ont été acceptés à la conférence BRAINS 2023 et le journal ACM-DLT. La version complète est disponible à cette url : https://hal.science/hal-04203000/document</footnote>
## 2 Modèle et Motivations

**Définitions.** Un Bloc-DAG (BDAG) est un graphe orienté acyclique $G = (V, E)$ avec un noeud genesis noté $g$. Chaque noeud, aussi appelé bloc possède un ou plusieurs parents et ont un poids qui représente généralement la quantité de travail fourni pour le créer, mais peut aussi représenter une importance quelconque dans un système basé sur les votes. Un sous-BDAG $G' = (V', E')$ d'un BDAG $G = (V, E)$ est un BDAG de même genesis, tel que si un bloc est dans $G'$ alors tous ses ancêtres dans $G$ sont aussi dans $G'$. Ainsi, on représente généralement un sous-BDAG uniquement par l'ensemble de ses arcs. Dans les figures (ex. Figure 1) les flèches pointent vers les parents d'un bloc qui correspondent aux successeurs dans le graphe orienté (les ancêtres sont donc les nœuds atteignables).

On suppose que l'on a accès à l'ensemble des conflits du BDAG $G$ noté Conflicts($G$), où un conflit $C \in$ Conflicts($G$) est un ensemble de blocs en conflit direct. Cela signifie généralement qu'ils contiennent une transaction conflictuelle et qu'au plus un seul bloc de l'ensemble peut faire partie d'un état cohérent. Comme un bloc valide implicitement tous ses ancêtres, alors les blocs descendants de deux blocs en conflit sont indirectement en conflit. Il est clair que les parents d'un bloc ne doivent pas être en conflit (sinon ils ne sont simplement pas ajoutés au BDAG). Mise à part cette restriction, aucune autre règle n'est imposée sur les parents d'un bloc.

Le poids d'un bloc $b$ est noté $w(b)$, et le poids d'un ensemble de blocs $S$ est la somme des poids des blocs qui le compose $w(S) = \sum_{b \in S} w(b)$. Le poids cumulé d'un bloc $b$ dans un sous-BDAG $S$, noté $w_{S(b)}$ est la somme des poids de ses descendants (qui dépend donc de $S$). Le poids de $S$ est donc le poids du genesis dans $S$. Étant donné un BDAG $G$ avec conflits Conflicts($G$), le **problème du sous-BDAG sans conflit le plus lourd** consiste à trouver un sous-BDAG $S$ tel que Conflicts($S$) = $\emptyset$ et pour tout sous-BDAG $S'$ de $G$ avec Conflicts($S')$ = $\emptyset$ on a $w(S') \le w(S)$.

**État de l'art et motivation.** Dans le DLT Iota [Pop18], l'algorithme de sélection courant choisit, en partant du genesis, les nœuds dont le poids cumulé est le plus grand jusqu'à arriver à une extrémité (un bloc sans enfant). Ces extrémités sont utilisées pour choisir le parent des nouveaux blocs, ce qui implicitement sélectionne l'ensemble des ancêtres comme étant l'état cohérent du système. Cependant, cela élimine potentiellement une grande partie du BDAG, comme le montre la Figure 1. Dans cette figure, les deux blocs carrés sont en conflits, donc choisir le nœud carré noir comme parent élimine la chaîne du bas, alors qu'il est possible de choisir comme état courant l'ensemble $U$ et ses ancêtres, un nouveau bloc (le bloc étoile) permet alors de rassembler deux branches qui n'étaient pas en conflit et ainsi maximiser le poids du BDAG obtenu.

<figure><img src="image_2.png" /><figcaption>Figure 1. – Un BDAG contenant deux blocs en conflits. L'ensemble $U$ correspond aux extrémités du sous-BDAG sans conflits le plus lourd et donc à l'ensemble privilégié pour choisir les parents d'un nouveau bloc.</figcaption></figure>

<caption>Figure 2. – Le BDAG utilisé dans la preuve de NP-compléterie</caption>
## 3 Complexité dans le cas général

Le premier résultat que nous montrons est que le problème de savoir s'il existe un sous-BDAG sans conflit de taille $k \in \mathbb{N}$ est NP-complet. La preuve repose sur une simple réduction depuis 3-SAT. Soit $F$ une formule 3-SAT avec variables $x_1, ..., x_n$ et clauses $C_1, ..., C_m$. Nous construisons un BDAG $G = (V, E)$ où les nœuds sont répartis en trois ensembles, visibles dans la Figure 2 :

$$V = \{g\} \cup V_x \cup V_C$$

$V_x$ contient $2n$ nœuds représentant les variables. $V_C$ contient $7m$ nœuds représentant les clauses.

Les nœuds de $V_x$ sont notés $u_{x_1}, u_{\bar{x}_1}, ..., u_{x_n}, u_{\bar{x}_n}$, chacun ayant pour unique parent $g$. Pour chaque variable $x_i$, les nœuds $u_{x_i}$ et $u_{\bar{x}_i}$ sont en conflit, ce qui force le choix d'une seule valeur de vérité pour chaque variable dans un sous-BDAG sans conflit. $V_C$ est l'union de $m$ ensembles $V_{C_i}$ contenant chacun 7 nœuds associés à une combinaison de valeurs de vérité pour les trois littéraux de la clause $C_i$. Pour chaque clause $C_i$, un nœud $u_{C_i(a,b,c)}$ de $V_{C_i}$ a pour parents les nœuds correspondant aux littéraux $a, b$ et $c$ dans $V_x$ qui satisfont $C_i$. Par exemple, une clause $C_l = \bar{x}_i \lor x_j \lor x_k$ est associée au 7 affectations possibles des littéraux $x_i, x_j, x_k$ qui satisfont $C_l$, c'est-à-dire, quand ils sont tous vrais ($\bar{x}_i \land x_j \land x_k$), quand deux sur trois sont vrais ($\bar{x}_i \land x_j \land \bar{x}_k$), ($\bar{x}_i \land \bar{x}_j \land x_k$), et ($x_i \land x_j \land x_k$)) ou quand un seul est vrai. Ainsi, un seul nœud de $V_{C_i}$ peut être inclus dans un sous-BDAG sans conflit, et cela uniquement s'il y a 3 littéraux parents de la clauses qui font aussi partie du sous-BDAG et tels que la clause $C_i$ est satisfaite.

On peut ainsi prouver l'équivalence suivante. $F$ est satisfiable si et seulement s'il existe un sous-BDAG sans conflit de poids $1 + n + m$. Si $F$ est satisfiable, alors il existe une affectation des variables telle que chaque clause est satisfaite. En sélectionnant les $n$ nœuds correspondants dans $V_x$ et un nœud par $V_{C_i}$ de manière cohérente, on construit un sous-BDAG sans conflit de taille $1 + n + m$. Réciproquement, si un sous-BDAG $S$ sans conflit de taille $1 + n + m$ existe, alors il contient obligatoirement $n$ nœuds de $V_x$ et $m$ nœuds de $V_C$ (il ne peut de toute manière pas en contenir plus). Ainsi, $S$ contient un nœud par ensemble $V_{C_i}$ (il ne peut pas en contenir plus car ils sont en conflits). Ce qui implique qu'au moins un littéral par clause a été ajouté au sous-BDAG. L'affectation correspondante des variables prouve que $F$ est satisfiable.
Le problème de décision étant clairement dans NP, il est donc NP-complet.

## 4 Algorithme paramétré

Nous montrons maintenant qu'il existe un algorithme polynomial paramétré par le nombre maximum de conflits concurrents. Commençons par définir la concurrence des conflits. On dit qu'un ensemble de conflits $\mathcal{C}$ est en concurrence avec un conflit $C$ s'il existe deux extrémités $u_1$ et $u_2$ de $G$ et un bloc $b \in C$ tels que : (i) $u_1$, respectivement $u_2$, est un descendant d'un bloc d'au moins un conflit de $\mathcal{C}$, (ii) $u_1$ est un descendant de $b$, et (iii) $u_2$ n'est pas un descendant de $b$. Un ensemble de conflits est clos par concurrence lorsqu'il n'existe pas d'autres conflits en concurrence. La clôture concurrente d'un conflit peut être calculée avec l'algorithme CLÔTURE présenté ci-après.

CLÔTURE $(G, C)$:

$$\mathcal{C} = \{C\}$$

répéter

Commun $\leftarrow$ ancêtres commun des blocs de $\mathcal{C}$

1. **pour** toute extrémité $u$ des descendants de $\mathcal{C}$

$\mathcal{C} \leftarrow \mathcal{C} \cup \text{ conflits impactant } u$

$\mathcal{C} \leftarrow \mathcal{C} \setminus \text{ Commun}$

si $\mathcal{C}$ n'a pas changé **retourner** $\mathcal{C}$

SEHES $(G)$:

si Conflicts($G$) = $\emptyset$:

retourner $G$

1. $\mathcal{C} \leftarrow$ plus petit ensemble concurrent clos

$G' \leftarrow$ Résoudre($G, \mathcal{C}$)

retourner SEHES($G'$)

Le point clé de notre algorithme SEHES défini ci-dessus est que les conflits non-concurrents peuvent être résolus de manière indépendante et dans n'importe quel ordre. Ainsi, après avoir trouvé un sous-BDAG $G'$ le plus lourd ne contenant plus de conflit parmi un ensemble de conflits concurrent-clos (en utilisant l'algorithme CLÔTURE sur chaque conflit pour trouver le plus petit possible), le sous-BDAG $G'$ obtenu contient obligatoirement une solution au problème initial (tout en contenant moins de conflits). On peut ainsi répéter l'opération jusqu'à supprimer tous les conflits. L'opération la plus coûteuse est la résolution
d'un ensemble de conflits $\mathcal{C}$ (ligne 4) car elle nécessite de tester toutes les combinaisons possibles de choix de blocs dans les conflits de $\mathcal{C}$. Cette opération est exponentielle en le nombre de blocs en conflits. Cependant, sous le paramètre $M$ (la taille maximum des clôtures concurrentes du BDAG), chaque itération de notre algorithme a une complexité polynomiale et le nombre d'itérations est bornée par le nombre de conflits (donc le nombre de noeuds), d'où une complexité globale polynomiale.

# 5 Évaluation des performances

Nous avons comparé notre algorithme avec GhostDAG [SWZ21], qui est, parmi les travaux existants, celui dont l'objectif est le plus proche du nôtre. L'algorithme GhostDAG est un algorithme glouton cherchant un sous-BDAG le plus lourd qui est un $k$-cluster. Nous avons aussi comparé notre algorithme avec deux heuristiques que nous avons créées et qui résolvent les conflits itérativement en commençant par le plus léger ($greedy_min$) ou le plus lourd ($greedy_max$, équivalent à un algorithme appelé Conflux [Li+18]).

Étudier les performances d'un algorithme de sélection de sous-BDAG est assez difficile. En effet, les données réalistes mesurées dans les DLTs basés sur des DAG ne contiennent que très rarement des conflits et dans de tels BDAG les solutions naïves retournent facilement une solution optimale. Pour tester et mettre en évidence les comportements des algorithmes, nous avons créé un algorithme de génération de BDAG ajoutant des blocs un à un avec une certaine probabilité de conflit. Il faut bien noter que les performances présentées sont très dépendantes de cet algorithme. Cependant, il est important de rappeler que notre algorithme est le premier à garantir l'optimalité de la solution et que ses performances resteront excellentes dans des environnements réalistes avec peu de conflits.

Pour chaque BDAG généré, nous avons mesuré la taille du sous-BDAG sans conflits obtenu (comme un ratio par rapport à la taille maximum possible), ainsi que le temps d'exécution de l'algorithme. Sur les deux figures présentées, chaque point est une moyenne sur 200 BDAG générés aléatoirement selon une méthode décrite dans la version longue de cet article. En faisant varier la taille des BDAG de 100 à 600 par incrément de 100, on peut voir que l'algorithme existant GhostDAG retourne des BDAG qui sont proches de l'optimal (entre 98% et 99%) mais que son temps d'exécution dépasse largement celui de notre algorithme.

Par ailleurs, on voit que nos solutions basées sur des heuristiques sont très rapides et l'une d'entre elles, $greedy_min$, retourne des sous-BDAG très proches de l'optimal. L'étude de ces heuristiques et la raison de leur bonne performance n'est pas aisée et dépend probablement très fortement de la topologie du BDAG, elle est laissée pour des travaux futures.

<figure><img src="image_3.png" /></figure>

**Conclusion.** Dans cet article, nous avons étudié le problème de la sélection d'un sous-DAG sans conflit maximisant le poids total des blocs. Nous avons démontré que ce problème est NP-complet et avons proposé un algorithme paramétré qui reste polynomial sous la contrainte du nombre maximal de conflits concurrents. Nos expérimentations montrent que notre approche surpasse les stratégies existantes, telles que GhostDAG, en garantissant une sélection optimale des blocs tout en maintenant une efficacité computationnelle satisfaisante.
Bibliographie

[Pop18] S. Popov, « The tangle », *White paper*, vol. 1, n° 3, p. 30, 2018.

[SWZ21] Y. Sompolinsky, S. Wyborski, et A. Zohar, « PHANTOM GHOSTDAG: a scalable generalization of Nakamoto consensus: September 2, 2021 », in *Proceedings of the 3rd ACM Conference on Advances in Financial Technologies*, 2021, p. 57-70.

[Li+18] C. Li, P. Li, D. Zhou, W. Xu, F. Long, et A. Yao, « Scaling nakamoto consensus to thousands of transactions per second », *arXiv preprint arXiv:1805.03870*, 2018.