Dans cet article, je vais vous parler du DAG (Directed Acyclic Graph) et de son application dans les registres distribués, et nous le comparerons à la blockchain.
DAG n’a rien de nouveau dans le monde des crypto-monnaies. Vous en avez peut-être entendu parler comme d’une solution aux problèmes d’évolutivité de la blockchain. Mais aujourd’hui, nous ne parlerons pas d’évolutivité, mais de ce qui différencie les crypto-monnaies de tout le reste : la décentralisation, le manque d’intermédiaires et la résistance à la censure.
Je vais également vous montrer que DAG est en réalité plus résistant à la censure et qu'il n'y a aucun intermédiaire pour accéder au grand livre.
Dans les blockchains que nous connaissons, les utilisateurs n’ont pas d’accès direct au registre lui-même. Lorsque vous souhaitez ajouter une transaction au grand livre, vous devez « demander » au producteur de blocs (alias « mineur ») de le faire. Ce sont les mineurs qui décident quelle transaction ajouter au bloc suivant et laquelle non. Ce sont les mineurs qui ont un accès exclusif aux blocs et le droit de décider quelle transaction sera acceptée pour inclusion dans le grand livre.
Les mineurs sont des intermédiaires entre vous et le grand livre distribué.
En pratique, un petit nombre de pools de mineurs contrôlent collectivement plus de la moitié de la puissance de calcul du réseau. Pour Bitcoin, il s'agit de quatre pools, pour Ethereum, de deux. S’ils s’entendent, ils peuvent bloquer toutes les transactions qu’ils souhaitent.
Au cours des dernières années, de nombreuses variantes de blockchains ont été proposées, différant par les principes de choix des producteurs de blocs. Mais les producteurs de blocs eux-mêmes ne vont nulle part, ils sont toujours « à la barrière » : chaque transaction doit passer par le producteur de blocs, et s'il ne l'accepte pas, alors la transaction, en fait, n'existe pas.
C’est un problème inévitable avec la blockchain. Et si nous voulons le résoudre, nous devons changer radicalement la conception et nous débarrasser complètement des blocs et des producteurs de blocs. Et au lieu de construire une chaîne de blocs, nous connecterons les transactions elles-mêmes, y compris les hachages de plusieurs précédentes dans chaque transaction. En conséquence, nous obtenons une structure connue en mathématiques sous le nom de graphe acyclique orienté - DAG.
Désormais, tout le monde a un accès direct au registre, sans intermédiaires. Lorsque vous souhaitez ajouter une transaction au grand livre, il vous suffit de l'ajouter. Vous sélectionnez plusieurs transactions parents, ajoutez vos données, signez et envoyez votre transaction à vos pairs sur le réseau. Prêt. Personne ne vous en empêche, votre transaction est donc déjà inscrite au grand livre.
Il s’agit du moyen le plus décentralisé et le plus résistant à la censure d’ajouter des transactions au grand livre sans intermédiaires. Parce que tout le monde ajoute simplement ses transactions au registre sans demander la permission à personne.
Les DAG peuvent être considérés comme la troisième étape de l’évolution des registres. Il y avait d’abord des registres centralisés, dont un seul parti contrôlait l’accès. Puis vinrent les blockchains, qui disposaient déjà de plusieurs contrôleurs qui enregistraient les transactions dans le grand livre. Et enfin, il n’y a aucun contrôleur dans le DAG ; les utilisateurs ajoutent directement leurs transactions.
Maintenant que nous avons cette liberté, cela ne devrait pas conduire au chaos. Nous devons nous mettre d'accord sur l'état du registre. Et cet accord, ou consensus, signifie généralement un accord sur deux choses :
- Qu'est-il arrivé?
- Dans quel ordre cela s’est-il produit ?
Nous pouvons facilement répondre à la première question : une fois qu’une transaction correctement créée a été ajoutée au grand livre, elle a eu lieu. Et point final. Les informations à ce sujet peuvent parvenir à tous les participants à des moments différents, mais finalement tous les nœuds recevront cette transaction et sauront qu'elle s'est produite.
S’il s’agissait d’une blockchain, les mineurs décideraient de ce qui se passe. Tout ce que le mineur décide d'inclure dans un bloc, c'est ce qui se passe. Tout ce qu'il n'inclut pas dans le bloc n'arrive pas.
Dans les blockchains, les mineurs résolvent également un deuxième problème de consensus : l’ordre. Ils sont autorisés à ordonner les transactions au sein du bloc à leur guise.
Comment déterminer l’ordre des transactions dans un DAG ?
Juste parce que notre graphique est orienté, nous avons déjà un certain ordre. Chaque transaction fait référence à une ou plusieurs transactions parentes précédentes. Les parents, à leur tour, font référence à leurs parents, et ainsi de suite. Les parents apparaissent évidemment avant les transactions enfants. Si l'une des transactions peut être atteinte par des transitions de lien parent-enfant, nous connaissons 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é à partir de la seule forme du graphique. Par exemple, lorsque deux transactions se situent sur des branches parallèles du graphique.
Pour lever toute ambiguïté dans de tels cas, nous faisons appel à ce que l'on appelle des fournisseurs d'ordres. Nous les appelons aussi « témoins ». Il s'agit d'utilisateurs ordinaires dont la tâche est d'envoyer constamment des transactions au réseau de manière ordonnée, c'est-à-dire afin que chacune de leurs transactions précédentes puisse être atteinte par des transitions le long des liens parent-enfant. Les fournisseurs de commandes sont des utilisateurs de confiance et l’ensemble du réseau compte sur eux pour ne pas enfreindre cette règle. Pour rationnellement faites-leur confiance, nous exigeons que chaque fournisseur de commandes soit une personne ou une organisation connue (non anonyme) et qu'il ait quelque chose à perdre s'il enfreint les règles, comme la réputation ou les activités basées sur la confiance.
Les fournisseurs de commandes sont choisis par les utilisateurs, et chaque utilisateur inclut une liste de ses fournisseurs de confiance dans chaque transaction qu'il envoie au réseau. Cette liste comprend 12 fournisseurs. C'est un nombre suffisamment réduit pour qu'une personne puisse vérifier l'identité et la réputation de chacun d'entre eux, et suffisant pour garantir que le réseau continue de fonctionner en cas de problèmes inévitables avec une minorité de fournisseurs d'ordres.
Cette liste de fournisseurs varie d'un utilisateur à l'autre, mais les listes de transactions voisines peuvent différer jusqu'à un fournisseur.
Maintenant que nous avons des fournisseurs de commandes, nous pouvons isoler leurs transactions dans un DAG et ordonner toutes les autres transactions autour de la commande qu'ils ont créée. Il est possible de créer un tel algorithme (voir. pour les détails techniques).
Mais l’ordre de l’ensemble du réseau ne peut pas être déterminé instantanément ; il faut du temps pour que les fournisseurs d’ordres envoient un nombre suffisant de leurs transactions afin de vérifier l’ordre final des transactions passées.
Et comme l'ordre est déterminé uniquement par les positions des transactions des fournisseurs dans le DAG, tous les nœuds du réseau recevront tôt ou tard toutes les transactions et parviendront à la même conclusion concernant l'ordre des transactions.
Nous sommes donc d’accord sur ce que nous considérons comme s’étant produit : toute transaction qui aboutit dans le DAG a eu lieu. Nous sommes également d'accord sur l'ordre des événements : cela est soit évident à partir des relations entre les transactions, soit déduit de l'ordre des transactions envoyées par les fournisseurs d'ordres. Nous avons donc un consensus.
Nous avons cette version du consensus dans Obyte. Même si l'accès au registre Obyte est totalement décentralisé, le consensus sur l'ordre des transactions reste centralisé car 10 fournisseurs sur 12 sont contrôlés par le créateur (Anton Churyumov), et seuls deux d'entre eux sont indépendants. Nous recherchons des candidats désireux de devenir l'un des fournisseurs de commandes indépendants pour nous aider à décentraliser la commande du grand livre.
Récemment, un troisième candidat indépendant est apparu, disposé à installer et à maintenir un nœud de fournisseur de commandes : l'Université de Nicosie.
Maintenant, comment contrôler les doubles dépenses ?
Selon les règles, si deux transactions dépensent la même pièce, la transaction qui arrive en premier dans l’ordre final de toutes les transactions gagne. Le second est invalidé par l’algorithme de consensus.
S'il est possible d'établir un ordre entre deux transactions dépensant la même pièce (via des connexions parent-enfant), alors tous les nœuds rejettent immédiatement une telle tentative de double dépense.
Dans le cas où l'ordre n'est pas visible dans les relations parentes entre deux de ces transactions, elles sont toutes deux acceptées dans le grand livre et nous devrons attendre le consensus et l'établissement de l'ordre entre elles à l'aide des fournisseurs d'ordres. Ensuite, la transaction précédente gagnera et la seconde deviendra invalide.
Même si la deuxième transaction devient invalide, elle reste toujours dans le registre car elle contient déjà des transactions ultérieures qui y font référence, qui n'ont rien violé et ne savaient pas que cette transaction deviendrait invalide à l'avenir. Sinon, nous devrions supprimer le parent des bonnes transactions ultérieures, ce qui violerait le principe principal du réseau : toute transaction correcte est acceptée dans le grand livre.
Il s’agit d’une règle très importante qui permet à l’ensemble du système de résister aux tentatives de censure.
Imaginons que tous les fournisseurs d'ordres s'entendent pour tenter de « censurer » une transaction spécifique. Ils peuvent l'ignorer et ne jamais le choisir comme « parent » pour leurs transactions, mais cela ne suffit pas, la transaction peut toujours être incluse indirectement comme parent d'une autre transaction émise par n'importe quel utilisateur du réseau qui n'est pas de connivence. Au fil du temps, une telle transaction recevra de plus en plus d'enfants, de petits-enfants et d'arrière-petits-enfants d'utilisateurs ordinaires, grandissant comme une boule de neige, et tous les fournisseurs de commandes convenus devront également ignorer ces transactions. A terme, ils devront censurer l’ensemble du réseau, ce qui équivaut à du sabotage.
De cette manière, le DAG reste résistant à la censure même en cas de collusion entre les fournisseurs d’ordres, dépassant ainsi la blockchain résistante à la censure dans laquelle nous ne pouvons rien faire si les mineurs décident de n’inclure aucune des transactions. Et cela découle de la propriété principale de DAG : la participation au registre est totalement indépendante et sans intermédiaires, et les transactions sont irréversibles.
Source: habr.com