Le consensus par GHOST-DAG présenté par Eureka Certification

11
21

Thomas Zoughebi et Alexandre David sont formateurs chez Eureka, organisme de formation certifié et certifiant sur le sujet « blockchain » depuis 2014. Eureka a lancé un cursus scolaire « blockchain » en 2017 en partenariat avec l’ESGI. Aujourd’hui, Eureka travaille avec des entreprises prestigieuses tels que Accenture et dernièrement EDF. Retrouvez l’actualité de Eureka sur Twitter, découvrez les grandes conférences organisées par Eureka sur YouTube. Pour vous former à la « blockchain », contactez l’équipe pédagogique de Eureka.

Ce que peu de gens savent, lorsqu’ils font l’amalgame entre le protocole Bitcoin et celui d’Ethereum, en les résumant à des « blockchains », c’est que ces deux technologies sont drastiquement différentes. Et pas seulement sur l’aspect idéologique, mais également sur l’aspect technique comme en atteste le protocole de validation d’Ethereum.

En effet, le protocole « GHOST », signifiant « Greedy Heaviest Observed Subtree », adopté par l’équipe de développement d’Ethereum a été introduit en décembre 2013 par les chercheurs de l’Université Hébraïque de Jérusalem Yonatan Sompolinsky et Aviv Zohar.

Bien qu’Ethereum utilise une version modifiée (jusqu’à sept générations de blocs « oncles » et une « récompense » pour les validateurs selon un barème très précis), la proposition initiale de GHOST suggérait une alternative à la règle de la chaîne la plus « lourde » de Bitcoin. Celui-ci ordonne la sélection de la chaîne la plus « lourde » enracinée au moment du « fork » de la chaîne principale. En résumé, GHOST permet un consensus au sein d’Ethereum sans forcément pénaliser les petit mineurs contraints à un temps de propagation long et une puissance de calcul faible.

Cette année, Aviv Zohar est venu présenter « GHOST-DAG » (nom inspiré du célèbre film « Ghost Dog » à la Scaling Bitcoin qui s’est tenue à Tokyo en octobre dernier (et dont Eureka Certification a publié un rapport détaillé). Il a étudié comment scaler à partir d’un protocole basé sur un DAG (Directed Acyclic Graph ; Graphe orienté acyclique) une généralisation de Preuve de Travail (la chaîne avec le plus de travail cumulé est la bonne).

Il est toujours question de minage et de Proof-of-Work, mais au lieu d’observer le travail cumulé des blocs, on observe ce qu’on appelle le plus grand « K-Cluster« . Même en faisant ce changement, on conserve les promesses de Bitcoin.

GHOST-DAG

L’idée, puisque l’on est en présence d’un graphe dirigé de blocs, est de se baser sur l’ordre de ces derniers. Ainsi on distingue des cônes (en deux dimensions) pour le passé (les blocs connus du bloc observé), le futur (les blocs influencés par le bloc observé), et l’anti-cône, pour les blocs parallèles au bloc observé qui ne font donc ni partie de son passé, ni de son futur. C’est dans cet anti-cône que le débat aura lieu.

GHOST-DAG

Un « K-Cluster » est un ensemble (graphe) de blocs dont chaque bloc a « K » autres blocs maximum dans son anti-cône. Un « 0-cluster » est donc en particulier une blockchain.

Le protocole « GHOST-DAG » consiste à trouver le plus grand k-cluster. Théoriquement, si l’on cherche vraiment le plus grand dans cette configuration, on est confronté à un problème « P = NP »… Pour éviter ce problème, on emploie la technique probabiliste de l’avidité des acteurs, comme dans une large palette de protocoles y compris Bitcoin. Ainsi, au lieu de chercher le plus grand des k-clusters, on en cherche un qui est suffisamment grand, produit par des mineurs honnêtes (qui ont intérêts à le produire), et dont le « k » est le plus petit possible (le plus petit anti-cône possible).

GHOST-DAG

Il reste à ordonner les blocs du k-cluster (pour les blocs parallèles on peut utiliser leurs hashs, par exemple).

L’important est de bien comprendre qu’alors on bénéficie de l’intégralité du travail de tous les blocs valides d’un anti-cone. La propagation des blocs se réalise donc par paquets (avec au maximum « k + 1 » blocs) !

Dans ce système, Aviv Zohar termine en démontrant que les propriétés de prévention de double dépense ou de self-mining sont préservées.

Ce protocole GHOST-DAG permettrait un passage à l’échelle impressionnant car le débit de transactions augmente proportionnellement à la grandeur de « k ». On imagine aisément l’utilisation d’un tel protocole à l’échelle inter-planétaire.

Thomas et moi-même avons été stupéfait de l’accueil enthousiaste par la communauté des travaux de Yonatan et Aviv en fin de conférence. Il y a avait un tel attroupement autour d’Aviv que l’intéressé était lui-même surpris. Il nous aura pas fallu attendre longtemps avant la publication du livre blanc à consulter via ce lien.

Bonne lecture.