Dans cet article, je vais vous parler du DAG (Directed Acyclic Graph, graphique acyclique dirigé) et de son application dans les registres distribués, et nous allons le comparer à la blockchain.
Le DAG n'est pas quelque chose de nouveau dans le monde des cryptomonnaies. Vous en avez peut-être déjà entendu parler comme d'une solution aux problèmes de scalabilité des blockchains. Mais aujourd'hui, nous ne parlerons pas de scalabilité, mais de ce qui rend les cryptomonnaies différentes du reste : la décentralisation, l'absence d'intermédiaires et la résilience à la censure.
Je vais également vous montrer que le DAG est en réalité plus résilient à la censure et qu'il n'y a pas d'intermédiaires pour accéder au registre.
Dans les blockchains que nous connaissons, les utilisateurs n'ont pas un accès direct au registre lui-même. Lorsque vous souhaitez ajouter une transaction au registre, vous devez demander au producteur de blocs (block producer, aussi appelé « mineur ») de le faire. Ce sont les mineurs qui décident quelle transaction ajouter au prochain bloc et laquelle exclure. Les mineurs ont un accès exclusif aux blocs et ont le droit de décider quelle transaction accepter pour ajout au registre.
Les mineurs sont les intermédiaires qui se trouvent entre vous et le registre distribué.
En pratique, généralement un petit nombre de pools de mineurs contrôlent collectivement plus de la moitié de la puissance de calcul du réseau. Pour le Bitcoin, il y a quatre pools, pour Ethereum - deux. En cas de collusion, ils peuvent bloquer n'importe quelle transaction qu'ils souhaitent.
Au cours des dernières années, de nombreuses variations de blockchains ont été proposées, se distinguant par les principes de sélection des producteurs de blocs. Mais les producteurs de blocs eux-mêmes ne disparaissent pas, ils sont toujours « au barrage » : chaque transaction doit passer par un producteur de blocs, et s'il ne l'accepte pas, alors la transaction n'existe en fait pas.
C'est un problème inévitable avec la blockchain. Et si nous voulons le résoudre, nous devons modifier radicalement la conception et nous débarrasser complètement des blocs et des producteurs de blocs. Au lieu de construire une chaîne de blocs, nous allons relier les transactions elles-mêmes, en incluant dans chaque transaction les hachages de plusieurs précédentes. En conséquence, nous obtiendrons une structure connue en mathématiques sous le nom de graphique acyclique dirigé – DAG.
Maintenant, chacun a un accès direct au registre, sans intermédiaires. Lorsque vous souhaitez ajouter une transaction au registre, vous l'ajoutez simplement. Vous sélectionnez plusieurs transactions parentes, ajoutez vos données, signez et envoyez votre transaction dans le réseau. C'est tout. Il n'y a personne pour vous en empêcher, donc votre transaction est déjà dans le registre.
C'est la méthode la plus décentralisée et la plus résiliente à la censure pour ajouter des transactions au registre sans intermédiaires. Parce que chacun peut ajouter ses transactions au registre sans avoir à demander la permission de qui que ce soit.
Le DAG peut être considéré comme la troisième étape de l'évolution des registres. Au départ, il y avait des registres centralisés, où une seule entité contrôlait l'accès. Puis sont venus les blockchains, où il y avait plusieurs contrôleurs qui enregistraient les transactions dans le registre. Enfin, dans un DAG, il n'y a absolument aucun contrôleur, les utilisateurs ajoutent leurs transactions directement.
Maintenant que nous avons cette liberté, elle ne doit pas conduire au chaos. Nous devons avoir un accord sur l'état du registre. Et cet accord, ou consensus, signifie généralement un accord sur deux choses :
- Que s'est-il passé?
- Dans quel ordre cela s'est-il produit ?
Pour la première question, nous pouvons facilement répondre : dès qu'une transaction correctement créée a été ajoutée au registre, elle a eu lieu. Point final. L'information peut parvenir à tous les participants à des moments différents, mais à la fin, tous les nœuds recevront cette transaction et sauront qu'elle a eu lieu.
Si c'était une blockchain, les mineurs décideraient de ce qui se passe. Tout ce que le mineur choisit d'inclure dans le bloc se produit. Tout ce qu'il n'inclut pas dans le bloc ne se produit pas.
Dans les blockchains, les mineurs résolvent également le deuxième problème de consensus : l'ordre. Ils sont autorisés à organiser les transactions à l'intérieur du bloc comme ils le souhaitent.
Comment définir l'ordre des transactions dans un DAG ?
Il y a déjà un certain ordre simplement parce que notre graphe est orienté. Chaque transaction fait référence à une ou plusieurs transactions précédentes, parentes. Les parents, à leur tour, font référence à leurs propres parents, et ainsi de suite. Les parents apparaissent évidemment avant les transactions enfants. Si quelque transaction peut être atteinte par des transitions suivant les liens « parent-enfant », nous savons exactement l'ordre entre les transactions dans cette chaîne de transactions.
Mais l'ordre entre les transactions ne peut pas toujours être déterminé uniquement à partir de la forme du graphe. Par exemple, lorsque deux transactions se trouvent sur des branches parallèles du graphe.
Pour résoudre l'ambiguïté dans de tels cas, nous nous appuyons sur ce que l'on appelle des fournisseurs d'ordre. Nous les appelons également « témoins ». Ce sont des utilisateurs ordinaires dont la tâche est d'envoyer en permanence des transactions dans le réseau dans le respect de l'ordre, c'est-à-dire de manière à ce que chaque transaction précédente puisse être atteinte par des transitions suivant les liens « parent-enfant ». Les fournisseurs d'ordre – des utilisateurs de confiance, et tout le réseau compte sur le fait qu'ils ne violeront pas cette règle. Pour leur faire confiance de manière rationnelle , nous exigeons que chaque fournisseur d'ordre soit une personne ou une organisation connue (non anonyme) et possède quelque chose qu'il peut perdre s'il enfreint les règles, par exemple, sa réputation ou une entreprise basée sur la confiance.
Les fournisseurs d'ordre sont choisis par les utilisateurs, et chaque utilisateur inclut la liste de ses fournisseurs d'ordre de confiance dans chaque transaction qu'il envoie dans le réseau. Cette liste est composée de 12 fournisseurs. C'est un nombre assez petit pour que quelqu'un puisse vérifier l'identité et la réputation de chacun d'eux, et suffisant pour que le réseau continue de fonctionner en cas de problèmes inévitables avec une minorité de fournisseurs d'ordre.
Cette liste de fournisseurs varie d'un utilisateur à l'autre, mais les listes des transactions adjacentes peuvent différer au maximum d'un fournisseur.
Maintenant que nous avons des fournisseurs d'ordre, nous pouvons isoler leurs transactions dans le DAG et organiser toutes les autres transactions autour de l'ordre qu'ils ont créé. Il est possible de créer un tel algorithme (voir pour les détails techniques).
Cependant, l'ordre dans tout le réseau ne peut pas être déterminé instantanément, nous avons besoin de temps pour que les fournisseurs d'ordre envoient suffisamment de leurs transactions afin de nous assurer de l'ordre final des transactions passées.
Et, puisque l'ordre est déterminé uniquement par les positions des transactions des fournisseurs dans le DAG, tous les nœuds du réseau finiront par recevoir toutes les transactions et arriveront à la même conclusion concernant l'ordre des transactions.
Ainsi, nous avons un consensus sur ce que nous considérons comme étant arrivé : toute transaction qui a été intégrée dans le DAG s'est produite. Nous avons également un consensus sur l'ordre des événements : cela est soit visible à partir des relations parent-enfant des transactions, soit déduit de l'ordre des transactions envoyées par les fournisseurs d'ordre. Cela signifie que nous avons un consensus.
Ce type de consensus est celui que nous avons dans Obyte. Bien que l'accès au registre Obyte soit complètement décentralisé, le consensus concernant l'ordre des transactions reste encore centralisé, car 10 des 12 fournisseurs sont contrôlés par le créateur (Anton Churyumov), et seulement deux d'entre eux sont indépendants. Nous recherchons des candidats souhaitant devenir l'un des fournisseurs d'ordre indépendants pour nous aider à décentraliser l'établissement de l'ordre dans le registre.
Récemment, un troisième candidat indépendant est apparu, souhaitant établir et maintenir un nœud de fournisseur d'ordre - l'Université de Nicosie.
Comment contrôlons-nous les doubles dépenses ?
Selon les règles, lorsqu'il y a deux transactions dépensant la même pièce, la transaction qui est arrivée en premier dans l'ordre final de toutes les transactions l'emporte. La seconde est alors invalidée par l'algorithme de consensus.
S'il est possible d'établir un ordre entre deux transactions dépensant la même pièce (par les relations parent-enfant), alors tous les nœuds rejettent immédiatement une telle tentative de double dépense.
Cependant, si l'ordre n'est pas visible à partir des relations parent-enfant entre ces deux transactions, elles sont toutes deux acceptées dans le registre, et nous devrons attendre le consensus et l'établissement de l'ordre entre elles par les fournisseurs d'ordre. Alors, la transaction la plus ancienne l'emportera, et la seconde deviendra invalide.
Bien que la deuxième transaction devienne invalide, elle reste néanmoins dans le registre, car elle a déjà des transactions suivantes qui s'y réfèrent, n'ayant violé aucune règle et ignorant que cette transaction deviendrait invalide dans le futur. Sinon, nous serions obligés de supprimer le parent des bonnes transactions suivantes, ce qui violerait le principe fondamental du réseau : toute transaction valide est acceptée dans le registre.
C'est une règle très importante qui permet à l'ensemble du système d'être résilient face aux tentatives de censure.
Imaginons que tous les fournisseurs d'ordre s'entendent pour tenter de « censurer » une transaction spécifique. Ils peuvent l'ignorer et ne jamais la choisir comme « parent » pour leurs transactions, mais cela ne suffira pas, car cette transaction peut toujours être incluse indirectement comme parent d'une autre transaction émise par n'importe quel utilisateur du réseau qui ne participe pas à l'entente. Avec le temps, cette transaction obtiendra de plus en plus d'enfants, de petits-enfants et d'arrière-petits-enfants de la part d'utilisateurs ordinaires, se développant comme une boule de neige, et tous les fournisseurs d'ordre convenus devront aussi ignorer ces transactions. Finalement, ils devront censurer l'ensemble du réseau, ce qui équivaut à un sabotage.
Ainsi, le DAG reste résistant à la censure, même en cas de collusion des fournisseurs d'ordre, surpassant ainsi la blockchain en terme de résilience à la censure, où nous ne pouvons rien faire si les mineurs décident de ne pas inclure certaines transactions. Cela découle de la principale caractéristique du DAG : la participation au registre est absolument indépendante et sans intermédiaires, et les transactions sont irréversibles.
Source : habr.com
