Bitcoin a marqué un tournant dans l'histoire du monde en proposant une manière simple mais probabilistique (économique) de résoudre le problème des généraux byzantins, et en fournissant par là un moyen de créer un système robuste de monnaie numérique. Devant le succès de Bitcoin, la recherche dans le domaine de la crypto-économie a explosé. Le développement d'anciennes idées a été ravivé ; Bitcoin a été copié, modifié, amélioré ; et certains ont même été jusqu'à repenser complètement son modèle de consensus. Parmi ces idées nouvelles, fascinantes, et potentiellement disruptrices, on trouve Avalanche.
Avalanche est un nouvel algorithme de consensus dont le fonctionnement diffère fortement de celui des algorithmes utilisés aujourd'hui dans le monde des cryptomonnaies. Il a été dévoilé le 16 mai 2018 par une équipe de recherche inconnue se faisant appeler la Team Rocket. Son livre blanc est intitulé Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies (« De Snowflake à Avalanche : une nouvelle famille de protocoles de consensus métastables pour les cryptomonnaies » en français) et a été initialement publié par le biais d'IPFS.
Le protocole Avalanche a été popularisé au cours de la dernière année par Emin Gün Sirer, professeur de science informatique à l'Université de Cornell dans l'État de New York. Ce professeur possède une certaine expérience dans le milieu des systèmes distribués et des algorithmes de consensus : en 2002, il avait même inventé un système appelé Karma qui permettait d'inciter au partage dans les protocoles pair-à-pair de transfert de données comme Bittorrent. Emin Gün Sirer est derrière le projet Ava, une implémentation protocolaire d'Avalanche utilisant la preuve d'enjeu, qui devrait voir le jour prochainement.
Dans cet article, nous examinerons tout d'abord les deux grandes familles de protocoles de consensus qui existent et comment Avalanche diffère de ces deux familles. Puis nous nous intéresserons au fonctionnement d'Avalanche et des différents éléments qui le composent. Enfin, nous regarderons comment Avalanche peut être implémenté, notamment au sein des systèmes crypto-économiques existants comme Bitcoin Cash.
Les protocoles de consensus
Les protocoles de consensus servent à résoudre ce qu'on appelle problème des généraux byzantins et qui peut être énoncé comme suit :
Des généraux de l'armée byzantine campent autour d'une cité ennemie. Ils ne peuvent communiquer qu'à l'aide de messagers et doivent établir un plan de bataille commun, faute de quoi la défaite sera inévitable. Cependant un certain nombre de ces messagers peuvent s'avérer être des traîtres, qui essaieront de semer la confusion parmi les autres. Le problème est donc de trouver un algorithme pour s'assurer que les généraux loyaux arrivent tout de même à se mettre d'accord sur un plan de bataille. (Wikipédia)
En d'autres termes, il s'agit de parvenir à un accord au sein d'un ensemble distribué de participants. C'est ce qu'on appelle la tolérance aux pannes byzantines (Byzantine fault tolerance ou BFT) : les participants honnêtes (non-fautifs) doivent finir par converger vers un consensus. Cela peut être utilisé dans des systèmes distribués divers ayant différents objectifs, mais ce qui nous intéresse ici c'est d'avoir un système qui permette d'échanger de la valeur, c'est-à-dire de se mettre d'accord sur qui possède quoi.
Bitcoin n'est pas le premier système à tenter de résoudre le problème des généraux byzantins. En effet, avant sa création il existait déjà une famille de protocoles de consensus dits « traditionnels » ou « classiques », qui étaient développés depuis les années 1980 par des personnes comme Leslie Lamport et Barbara Liskov. Ces algorithmes, qui existent encore aujourd'hui, ont les propriétés suivantes :
- La communication entre les nœuds du réseau doit être quadratique (chaque nœud doit communiquer avec tous les autres), ce qui fait qu'il est difficile de dépasser les 10 000 nœuds.
- Les nœuds doivent donc connaître l'ensemble du réseau.
- Il faut que les deux tiers des participants soient honnêtes.
- Les transactions sont garanties comme valides par l'engagement des nœuds : une fois qu'une transaction est acceptée, il n'y a pas de demi-tour possible.
- La finalité des transactions est atteinte très rapidement : typiquement, quelques secondes.
- Enfin, ce type de protocole permet de traiter un très haut volume de transactions.
Ces protocoles ont donc un avantage majeur : ils peuvent accueillir un très grand nombre de transactions. En revanche, on voit tout de suite qu'ils manquent de robustesse : un attaquant peut en effet s'attaquer aux différents nœuds et parvenir à perturber grandement le système. Ces protocoles ne sont donc pas adaptés à des applications aussi sensibles que celle de la monnaie.
De plus, dans ce type de protocole, la participation est très restreinte en raison de leur vulnérabilité aux attaques Sybil : les nœuds doivent donc être soigneusement sélectionnés. Ceux-ci sont par exemple désignés par une autorité (comme cela est fait dans
Heureusement, Bitcoin est apparu en 2009 et a apporté avec lui ce qu'on appelle le protocole de consensus de Nakamoto. Ce type d'algorithme fait intervenir une chaîne de blocs : des validateurs produisent des blocs (notamment par preuve de travail) et la plus longue chaîne l'emporte. L'algorithme de Nakamoto possède les propriétés suivantes :
- Il est robuste : les nœuds n'ont pas besoin de connaître tous les nœuds du réseau pour que le système marche.
- Le réseau peut donc comporter un nombre très important de participants sans que son fonctionnement soit sévèrement impacté.
- Il faut que plus de 50 % des participants soient honnêtes, ce qui est une amélioration par rapport aux 66 % des algorithmes classiques.
- La garantie de sécurité des transactions est probabilistique : la confiance dans une transaction évolue en fonction du nombre de confirmations.
- La finalité des transactions met très longtemps à être atteinte : pour Bitcoin, on devra attendre entre 10 et 60 minutes selon la garantie souhaitée.
- Le volume de transactions qu'il est possible de traiter est assez faible, du moins bien plus faible que celui traité par les algorithmes classiques.
- Dans le cas de la preuve de travail, le protocole de consensus consomme beaucoup d'énergie, ce qui a un impact économique sur son fonctionnement, notamment par le phénomène de centralisation des validateurs.
Le protocole de consensus de Nakamoto a été inventé avec la preuve de travail et est utilisé sous cette forme par beaucoup de systèmes comme Bitcoin, Bitcoin Cash, Litecoin ou Monero. Cependant, le travail n'est pas l'algorithme lui-même : il s'agit d'un mécanisme de résistance aux attaques Sybil. Le protocole de consensus de Nakamoto peut donc utiliser d'autres mécanismes comme la preuve d'enjeu, où la possession de jetons est utilisée comme critère de sélection : Tezos en est un exemple.
Avalanche permettrait, d'après le livre blanc, de combiner le meilleur des deux mondes. Toujours selon le livre blanc, cet algorithme de consensus atteindrait sans problème une charge transactionnelle de 1300 transactions par seconde, et garantirait la finalité d'une transaction en moins de 4 secondes.
Avalanche n'a pas de meneur en charge de décider ce qui est valide ou non : tout se fait, comme on le verra plus bas, par un modèle épidémique de chuchotements. Cela contraste avec les algorithmes traditionnels et avec celui de Nakamoto. En effet, dans les algorithmes traditionnels, ces meneurs sont désignés à l'avance par une autorité (ou par un système de preuve d'enjeu déléguée) et ils sélectionnent tour à tour les bonnes transactions. Dans le système de preuve de travail de Satoshi Nakamoto, les meneurs sont les mineurs qui utilisent leur puissance de calcul pour résoudre le problème mathématique lié au bloc construit : chaque fois qu'un mineur trouve une solution, il est désigné par les autres membres du réseau comme meneur et son bloc est considéré comme valide.
De plus, Avalanche est plus efficace que le protocole de consensus de Nakamoto, dans le sens où il n'est actif que lorsqu'une nouvelle transaction est diffusée sur le réseau et où il est particulièrement adapté à la preuve d'enjeu, moins énergivore que la preuve de travail.
Une nouvelle famille de protocoles
Avalanche est la combination de plusieurs éléments et est le protocole plus évolué d'une famille de quatre protocoles. Avalanche se fonde sur une prise de décision métastable (en équilibre précaire) qui utilise un procédé de chuchotement au sein du réseau pair-à-pair. Il s'agit d'un modèle épidémique qui s'inspire du fonctionnement des colonies d'insectes sociaux comme les fourmis et les abeilles.
Avalanche est l'algorithme le plus évolué d'une famille de quatre protocoles de consensus, dont chacun est l'amélioration d'un autre. Par ordre de complexité, cette famille se compose de : Slush (neige fondue en français), Snowflake (flocon de neige), Snowball (boule de neige) et Avalanche. Nous allons voir ici quels sont ces algorithmes.
Slush
Slush introduit la métastabilité sur le réseau et constitue l'idée de base derrière la famille de protocoles dont fait partie Avalanche.
Pour l'exposé, on décrira ici les opérations qui sont effectuées dans Slush pour prendre une décision entre deux transactions conflictuelles, dites de « double dépense » car elles dépensent les mêmes fonds. Ces deux transactions seront respectivement représentées par la couleur bleue et la couleur rouge.
On part d'un réseau neutre, composé de nœuds qui ne sont pas colorés. En recevant une transaction, un nœud met à jour sa couleur (disons bleue). Il amorce ensuite un processus d'interrogation avec les nœuds avec qui il est connecté : plus précisément il en sélectionne un échantillon aléatoire d'une taille prédéfinie par le protocole (ici nous supposerons 3).
Si les nœuds qu'il questionne sont non colorés, alors ces nœuds prendront sa couleur (le bleu) et amorceront eux-mêmes un processus d'interrogation.
| Avant | Après |
|---|---|
 |
 |
Si les nœuds qu'il interroge répondent en majorité être de sa couleur, alors sa couleur ne change pas.
| Avant | Après |
|---|---|
 |
 |
Si les nœuds qu'il interroge répondent en majorité être de la couleur opposée (le rouge), alors il change de couleur et devient rouge.
| Avant | Après |
|---|---|
 |
 |
Le procédé est répété, encore et encore, jusqu'à ce que la situation se stabilise. Grâce au facteur aléatoire, cette stabilisation a toujours lieu au bout d'un moment, même en partant d'une situation où chaque couleur occupe la moitié du réseau. La convergence se fait généralement en quelques secondes, même si le nombre de nœuds est très grand.
Snowflake
Slush est donc métastable dans le sens où il garantit d'atteindre un équilibre précaire sur le réseau. Cependant, il n'est pas, en soi, tolérant aux pannes byzantines, car les nœuds n'ont pas d'état final défini. Snowflake est un second algorithme qui implémente Slush en lui ajoutant une obligation pour chaque nœud de posséder un compteur qui permet de résoudre ce défaut.
Chaque nœud entretient ce compteur qui sert à mesurer la force de conviction du nœud dans la couleur qu'il partage. À chaque tour d'interrogation :
- Si sa couleur est confirmée, alors le compteur est incrémenté de 1 ;
- S'il doit changer de couleur, alors le compteur est réinitialisé.
Une fois que le compteur dépasse un certain seuil (délibérément haut), alors la couleur du nœud est verrouillée. Ainsi, une fois que le système a convergé, il ne peut plus être retourné.
Snowball
Snowball améliore Snwoflake en lui incorporant une notion de confiance plus permanente. Des compteurs de confiance sont mis en place pour chacune des couleurs et le nœud les incrémente en fonction du résultat de l'interrogation. Le nœud ne change de couleur que si sa confiance est plus grande dans la couleur opposée.
Une démonstation animée de Snowball est accessible en ligne. Elle donne notamment la possibilité de modifier les différents paramètres de l'algorithme.
Avalanche
Enfin vient Avalanche, le sujet de cet article. Avalanche utilise le modèle des UTXO de Bitcoin qui possède une propriété intéressante : sauf dans le cas des transactions de récompense, une transaction va toujours consommer les sorties non dépensées d'autres transactions, et fait donc nécessairement référence aux transactions précédentes.
Grâce à cette propriété, il est possible de construire un graphe orienté acyclique (directed acyclic graph ou DAG en anglais) dont les sommets sont les transactions. En effet le graphe obtenu est orienté du passé vers l'avenir et ne peut pas former de cycle à cause de cette flèche du temps.
Par exemple, dans la figure ci-dessus on voit que la transaction 7 a dépensé deux sorties transactionnelles : l'une provenant de la transaction 4, l'autre de la transaction 5. Cette transaction 7 a elle même créé plusieurs sorties, dont deux d'entre elles ont été consommées par les transactions 9 et 10. Les sorties non dépensées (UTXO) ne sont pas représentées sur le graphe.
Avalanche consiste à généraliser Snowball à ce graphe orienté acyclique. Les nouvelles transactions, et en particulier les transactions conflictuelles, passent par l'algorithme Snowball. Cela améliore les choses sur deux points :
- Premièrement, l'efficacité, puisqu'un vote sur une seule transaction est un vote implicite pour toutes les transactions parentes qui la précèdent dans le graphe ;
- Secondement, la sécurité, puisque Avalanche entremêle le destin des transactions, comme le protocole de Nakamoto le fait pour les blocs dans Bitcoin.
Tout ceci fait d'Avalanche un protocole de consensus léger qui pourrait fonctionner sur des configurations informatiques relativement petites.
Avalanche dans la vraie vie
Le papier de recherche décrivant le fonctionnement d'Avalanche n'a été publié que l'année dernière et on peut donc dire qu'Avalanche est très nouveau dans le domaine du consensus décentralisé. Pour l'instant, il n'a pas été testé en grandeur nature sur un réseau public (même si cela ne saurait tarder), et on peut s'attendre, lors de la mise en pratique, à l'apparition de problèmes qui n'auront pas été envisagé. Toutefois, le protocole n'en est pas moins prometteur et il convient de regarder comment il pourrait être implémenté.
Remarquons que, comme les méthodes classiques et la méthode de Nakamoto, la participation au consensus dans Avalanche ne peut pas être « gratuite » car cela permettrait aux attaquants d'utiliser autant de nœuds qu'ils le souhaitent pour perturber la prise de décision. Avalanche a donc besoin d'un mécanisme de résistance aux attaques Sybil. La preuve d'enjeu est particulièrement adaptée à ce nouvel algorithme, mais la preuve de travail peut également être utilisée dans un contexte un peu différent. Nous allons voir comment ces deux mécanismes devraient potentiellement êtres mis en place, à travers les cas de Ava et de Bitcoin Cash.
L'implémentation en preuve d'enjeu : Ava
Ava est une implémentation en pure preuve d'enjeu de Avalanche. Elle est développée par Ava Labs, une entreprise fondée pour l'occasion par Emin Gün Sirer. De plus, il est prévu qu'Ava ait à l'avenir un système de gouvernance interne lui permettant de s'auto-amender comme le fait Tezos.
Toutefois, Ava n'en est pour l'instant qu'au stade du produit minimum viable : le prototype fonctionne depuis quelques semaines sur un réseau de test privé et il est trop tôt pour en retirer quoi que ce soit. Le mode de distribution initial du jeton (ICO, etc.) n'a également pas encore été décidé.
L'implémentation en preuve de travail : Bitcoin Cash
S'il y a quelque part où Avalanche rencontre un certain succès, c'est dans le communauté de Bitcoin Cash (BCH). Les développeurs de Bitcoin Cash prévoient en effet de l'implémenter partiellement au sein du protocole, même si cela représente un changement majeur. Avalanche est notamment défendu par Amaury Séchet de Bitcoin ABC, et Chris Pacia de bchd.
Pourquoi ce succès ? Certainement en raison de ce que pourrait apporter ce nouveau type de consensus. En effet, l'adoption d'Avalanche aurait un but double : servir de méthode de pré-consensus et renforcer la sécurité post-consensus en rendant les attaques des 51 % beaucoup plus difficiles à mettre en œuvre.
Comment Avalanche serait-il implémenté ? Avalanche serait ajouté au consensus de Nakamoto de la façon la plus rétro-compatible possible. Comme on l'a dit, la preuve de travail serait utilisée comme mécanisme de résistance aux attaques Sybil : seuls les mineurs (par exemple les mineurs des 100 derniers blocs) formeraient le groupe des nœuds participant à Avalanche. Le procédé serait utilisée pour les nouvelles transactions. Dans le cas d'une transaction conflictuelle (« double dépense »), les participants se metteraient d'accord sur la transaction à considérer comme honnête. Seule la transaction choisie serait alors valide aux yeux du protocole et seule celle-ci pourrait être incluse dans un bloc. Il n'y aurait pas d'obligation d'inclusion mais toute transaction dépensant le même UTXO que la transaction choisie serait invalidée.
Cela permettrait, comme on l'a vu, d'atteindre une finalité beaucoup plus rapidement pour les transactions (de l'ordre de quelques secondes comme on l'a dit) et ainsi les problèmes liés à l'acceptation des transactions non confirmées (« 0-conf ») par les marchands. Initialement, d'autres méthodes de pré-consensus (weak blocks, Bitcoin-NG) étaient envisagées, mais le protocole Avalanche semble maintenant privilégié par les développeurs.
Outre cette amélioration de la garantie des transactions non confirmées, Avalanche offrirait également un moyen efficace d'éviter les attaques des 51 %. Comme on le sait, Bitcoin Cash est assez vulnérable à ce genre d'attaque puisqu'il partage le même algorithme de minage que Bitcoin (BTC) qui accapare environ 20 fois plus de taux de hachage que BCH. Heureusement, les mineurs et les opérateurs des coopératives de minage, font preuve de rationnalité et, par calcul économique, ne se servent pas de la puissance de calcul à leur disposition pour attaquer. Cependant, il se peut qu'un attaquant ait des motivations complètement autres que le profit direct et se mette à attaquer quand même : c'est d'ailleurs ce qu'ont menacé de faire Craig Wright et Calvin Ayre, les promoteurs principaux de Bitcoin SV (BSV), en novembre 2018.
Avalanche interviendrait ici pour servir de seconde couche de sécurité contre ce type d'attaque. Il faudrait alors que l'attaquant possède la majorité de la puissance de minage et une proportion encore plus grande de nœuds participant au consensus Avalanche pour parvenir à ses fins.
Conclusion
Pour conclure, Avalanche est un nouveau protocole de consensus qui commence tout juste à se faire une place. Ses propriétés sont très attrayantes : il offre une finalité quasi-instantanée des transactions et une résistance à de fortes charges transactionnelles tout en garantissant une décentralisation du réseau. Pour Bitcoin Cash, Avalanche pourrait également servir à régler une partie des problèmes qu'il rencontre, sans pour autant que la transition soit trop difficile.
Cependant, il est pour l'instant difficile d'évaluer la fiabilité d'un tel protocole, d'autant plus que le domaine de la crypto-économie regorge de projets soi-disants « novateurs » mais qui en réalité ne fonctionnent pas comme prétendu. De nombreuses recherches et expérimentations devraient être réalisées à l'avenir, et garder un œil, sceptique mais curieux, dessus pourrait être bénéfique.
Sources
Miguel Castro et Barbara Liskov, Practical Byzantine Fault Tolerance, février 1999.
Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, 2008.
Team Rocket, Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies, 16 mai 2018.
Chris Pacia, Avalanche Pre-Consensus: Making Zeroconf Secure, 10 décembre 2018.
Chris Pacia, The Problems Solved By Avalanche, 26 décembre 2018.
0 Comments