Blockchain

Taxonomie des Consensus

26 juillet 2019

1. Introduction

On parle souvent de blockchain, comme si celle-ci était une technologie homogène. Cependant, elle n’est souvent pas définie de manière précise et constructive mais juste comme étant tout protocole qui résout le problème du consensus en s’appuyant sur une structure de blocs chaînés.

Ceci fait que le consensus est la pierre angulaire de la blockchain et qu’il y a potentiellement autant de blockchains que de façons de le résoudre. Mais aussi que la performance de la blockchain (taux de transactions par seconde, vulnérabilité aux attaques) est intimement liée au consensus utilisé. Il est donc primordial de détailler une taxonomie des consensus en exposants leurs conditions d’existence ainsi que leurs limites afin d’avoir un benchmark et un cadre précis pour comparer ces différentes technologies.

Ce qui suit fait cela, en passant les détails techniques et en se focalisant sur l’intuition.

 

2. Modèle distribué et consensus

Les problèmes de consensus apparaissent dans les systèmes distribués; ou plusieurs ordinateurs collaborent pour  effectuer une tâche donnée. Un réseau d’ordinateurs par exemple peut collaborer pour fournir la réponse à une requête de votre navigateur internet, sous forme de page web. Comme cette page web est unique, on dit qu’elle doit faire consensus parmi tous les ordinateurs. Dans les cas ou cette collaboration ne passe pas par un ordinateur central, on dit que le système est distribué. La blockchain est donc selon cette définition un système distribué dans lequel les ordinateurs du réseau doivent atteindre un consensus sur le prochain bloc de transactions à inclure dans la chaîne.

Ce système peut alors pendant son exécution subir des fautes / pannes de différentes natures dues à son environnement (défaillances matérielles, hackers …etc).  Celles-ci peuvent résulter en l’arrêt définitif ou partiel de certains ordinateurs – on parle alors de fautes de crashs –  jusqu’à des comportements malveillants pendant l’exécution appelés byzantins.

En blockchain, une fraude d’un des ordinateurs du réseau est une faute byzantine et une déconnexion est une faute de crash.

Dès lors on peut se poser la question de savoir s’il est toujours possible de programmer les ordinateurs de sorte à ce qu’ils atteignent un consensus sur un bloc juste  (non frauduleux) en présence de fautes, byzantines et de crashs ?

La réponse dépend aussi d’un autre paramètre du réseau qu’on appelle synchronicité. C’est la différence de vitesses de traitement qu’il y a entre les différents ordinateurs. Si tout le monde a la même vitesse de traitement, on parle de réseau synchrone, sinon on est dans un cas asynchrone.

Les premiers travaux sur le consensus se sont donc concentrés sur le cas des réseaux synchrones avec des pannes de crashs uniquement. En effet c’est la configuration la plus simple dans laquelle peut se trouver un réseau. Ces travaux fournissent des algorithmes qui résolvent le consensus en tolérant des proportions de crashs variées et proportionnelles à la vitesse de l’algorithme. (Exemple: si on veut tolérer 6 crashs, l’algorithme atteindra le consensus en 6 unités de temps).

Cependant, dès qu’on sort de ce cadre on se heurte à plusieurs résultats d’impossibilité. Le cas synchrone ou on a au moins un tiers du réseau qui se comporte de manière frauduleuse (byzantine) est par exemple impossible.  Et en 1985, Fischer, Lynch et Paterson montrent que la seule propriété d’asynchronie dans un réseau est une barrière qui rend la résolution du consensus impossible. Ce résultat sera par la suite un classique de la littérature connu sous le nom du théorème FLP. On est donc déjà loin de la vision idyllique de la blockchain miraculeuse qui fournirait un consensus dans n’importe quelles conditions.

Plusieurs blockchains n’offrent alors une garantie de fonctionnement que quand le nombre d’ordinateurs frauduleux ne dépasse pas les 33% (le fameux tiers). C’est le cas de Hyperledger d’IBM et Corda de R3 qui utilisent des algorithmes comme RAFT , PAXOS et PBFT. Cependant, ces algorithmes souffrent de problèmes de scalabilité (faible taux de transactions par seconde) et sont donc souvent utilisés dans des contextes fermés ou on a le contrôle sur qui rejoint le réseau.

D’autres blockchains, comme Bitcoin et Ethereum augmentent ce ratio de 33% à 50% mais attention, on ne viole toujours pas le théorème mais en faisant une concession, le consensus n’est garanti qu’avec une grande probabilité et non de manière déterministe. L’intuition de cette famille d’algorithmes est de désigner de manière probabiliste un leader dans le réseau dont tout le monde vérifie, valide et copie les actions. Ce sont les fameux mécanismes Proof-of-X, comme la Proof-of-Work ou le premier qui trouve le bon hash est leader.

Des blockchains combinant les deux formes de consensus citées plus haut existent aussi. Elles sont dites hybrides. Dans celles-ci, on utilise un algorithme d’élection de leader pour élire un consortium ou un ensemble de leader, qui par la suite exécutent un algorithme de consensus classique. C’est le cas d’Algorand par exemple.

 

3. Conclusion

En somme, une blockchain est caractérisée par son consensus qui dépend de sa synchronie et de la nature de sa tolérance aux pannes. Ces deux facteurs déterminent la sécurité de la blockchain (quand est-ce que le consensus est possible et à quelles pannes il est robuste) mais aussi sa performance. Par conséquent, toute nouvelle blockchain doit avoir sa place quelque part sur le diagramme suivant qui donne une manière de classifier la technologie.

 

Khaled Maâmra, Responsable du Lab’ Nexeo

 

Ajouter un commentaire


Votre commentaire sera modifié par le site si besoin.

À lire également

Détection de fautes garanties à posteriori   Introduction Le consensus entre un ensemble de n processus est…

1. Introduction On parle souvent de blockchain, comme si celle-ci était une technologie homogène. Cependant, elle n’est…

Bien que partiellement utilisée par la nouvelle plateforme prometteuse « NowCP », la technologie blockchain pourrait permettre…