Solana (SOL), pour aller plus loin : entrevue de la technologie Tower BFT

Dans l’article précédent sur Solana, nous vous présentions son innovation technologique majeure, la preuve d’histoire (proof of history). Elle permet au réseau de s’accorder sur le temps et sur l’ordre des événements, et ceci avant que le mécanisme de consensus de sa blockchain n’intervienne. Dans cette deuxième partie, nous découvrons Tower BFT, l’algorithme de consensus de Solana.

Cet article promotionnel vous est proposé en collaboration avec Solana.

Tower BFT, le mécanisme de consensus de Solana

Comme nous l’avons vu précédemment, la proof of history est le système d’horodatage innovant de la blockchain Solana. Ce mécanisme utilise les fonctions de hachage afin de mesurer l’écoulement du temps, et de dater les différents événements survenant sur le réseau – comme les requêtes de transactions.

L’algorithme de consensus de Solana, nommé Tower BFT, est conçu pour tirer parti de la proof of history afin d’améliorer grandement le débit de transactions que le réseau est capable de traiter.

Comme son nom l’indique, Tower BFT est un algorithme dit PBFT (practical byzantine fault tolerant, résistant aux fautes byzantines en pratique). Avant d’explorer son fonctionnement dans le détail, voici un petit rappel sur la signification de ce terme barbare.

Le problème des généraux byzantins

Il s’agit d’une analogie historique pour décrire un problème classique de l’algorithmique : comment garder l’intégrité d’une information et assurer sa transmission au sein d’un réseau comportant des acteurs malicieux ?

Imaginons une cité assiégée par plusieurs corps d’armées, dirigés par leurs généraux respectifs. Ces derniers ne peuvent communiquer que par le biais de messagers, se déplaçant à dos de chameau. Ils doivent s’entendre sur l’heure et les modalités de l’attaque finale : elle ne pourra réussir que si les troupes tombent parfaitement d’accord et attaquent de façon coordonnée. Le problème, c’est qu’il y a au sein des généraux, tout comme parmi leurs messagers, des traîtres, qui vont tenter de fausser l’information.

Comment trouver un mécanisme permettant de maintenir le consensus entre les généraux loyaux ?

En informatique, il s’agit de s’assurer qu’au sein de réseau d’ordinateurs, une majorité suffisante d’entre eux assure le bon fonctionnement du protocole – et ceci malgré la présence éventuelle d’éléments défectueux. Une solution formelle fut proposée en 1982 par Leslie Lamport, Robert Shostak et Marshall Pease.

Vous l’aurez compris, dans le cas d’un réseau blockchain, il s’agit de s’assurer que tous les nœuds maintenant la comptabilité du système suivent un ensemble de règles communes (consensus), tout en se protégeant des attaques diverses ou des pannes.

Tolérance aux fautes byzantines et consensus

Lorsqu’un nœud d’un réseau distribué ne se comporte pas comme il le devrait, qu’il s’agisse d’une panne ou d’une attaque, on parle de faute byzantine. Les algorithmes de consensus sont donc conçus pour y résister : on parle de tolérance aux fautes byzantines. Concrètement, cela signifie que l’algorithme maintiendra le consensus même en cas d’un grand nombre de nœuds défaillants.

Bitcoin, grâce au consensus de Satoshi Nakamoto, offre la meilleure tolérance aux fautes byzantines (~49 %). Cependant, la preuve de travail est très énergivore et de nombreux algorithmes fonctionnent différemment. Les algorithmes PFBT résistent en pratique à 33 % de nœuds défectueux.

L’idée générale de Tower BFT est de “préférer la disponibilité à la consistance« . L’algorithme de consensus s’appuie sur la proof of history pour valider les blocs de transactions. Les nœuds du réseau ne sont pas synchronisés et vont voter pour de multiples forks de la blockchain. L’algorithme doit permettre d’arriver à finaliser les transactions malgré ces nombreuses variantes du registre.

Fonctionnement de Tower BFT

Intégration de la proof of history de Solana

L’algorithme Tower BFT utilise donc la proof of history comme une horloge intervenant avant le consensus. Cela réduit la charge de messages que le réseau doit traiter et le délai de validation des blocs.

Rappelons que la structure de données du registre de la proof of history permet à n’importe quel nœud de connaître l’état des autres nœuds du système distribué, même sans communiquer avec eux.

En pratique :

• Les nœuds possédant le registre de la proof of history parviendront aux mêmes calculs sans avoir à communiquer les uns avec les autres ;
• Chaque hash de la PoH identifie une version (fork) unique du registre ;
• Lors du processus de validation, un vote est valide si le hash pour lequel le nœud a voté est présent dans le registre.

Objectifs de l’algorithme Tower BFT

Les objectifs de l’algorithme de consensus sont les suivants :

• Certaines forks peuvent ne pas être acceptées par la super-majorité : les validateurs doivent pouvoir se rétracter et annuler leur vote sur ces forks ;
• Différents validateurs peuvent voter pour de nombreuses forks, et chaque validateur peut avoir un ensemble différent de forks pour lesquels voter. Les forks sélectionnées doivent converger.
• Les votes sont basés sur les récompenses, et comportent un risque associé. Les électeurs doivent avoir la possibilité de configurer le niveau de risque qu’ils prennent.
• Le coût d’un rollback (retour à un état antérieur de la blockchain) doit être calculable.
• Le mécanisme de consensus doit être résistant aux attaques sur le registre de la proof of history.

Pour y parvenir, Tower BFT utilise un système de lockout (délai de verrouillage). Il s’agit d’une période, assortie à chaque vote, durant laquelle un électeur ne peut pas l’annuler.

Délai de verrouillage et retour en arrière (lockouts et rollbacks)

Il est important de comprendre l’objectif de ce mécanisme. Il s’agit d’obliger un validateur à engager un certain coût d’opportunité pour une fork spécifique.

Le validateur vote pour une fork du registre. Un délai de verrouillage (lockout – mesuré en slots de 400 ms) s’applique alors pour ce vote, durant lequel le validateur ne peut revenir dessus. Le validateur s’engage également à ne voter que pour des forks issus du fork pour lequel il a voté durant cette période. S’il faillit à ses engagements, le mécanisme du slashing le puni : il perd une partie de son stake.

Le système de vote de Tower BFT

Les validateurs sont donc incités à voter pour les forks légitimes de la blockchain, grâce à l’appui du registre de la proof of history. L’algorithme va empiler ces votes au sein du stack :

• Chaque vote représente la confirmation d’une fork ;
• Chaque fork confirmé devient l’ancêtre de la fork suivante ;
• Tout vote est assorti d’un délai de verrouillage durant lequel le validateur ne peut voter pour une fork qui ne descend pas du vote précédent.

À chaque nouveau vote, le lockout pour les anciens votes du stack double. Ainsi, l’engagement du validateur croît avec le temps (par puissance de 2 précisément). On considère donc qu’il est impossible de revenir en arrière sur l’état de la chaîne après 32 votes. En effet, 2³² slots de 400 ms représentent… 54 années.

L’algorithme purge du stack tous les votes ayant un lockout supérieur ou égal à 32. Le validateur est récompensé lorsque son vote quitte le stack. Mais si un vote expire avant le délai de 32 slots, ce vote ainsi que tous les votes subséquents sont éliminés du stack.

Le retour en arrière (rollback)

Les validateurs s’assurent de ne voter que pour des forks issus de slots ayant acquis la super-majorité du réseau. Chaque vote a un délai de verrouillage et un délai d’expiration, quantifié en slots.

À chaque nouveau slot, il est possible de revenir en arrière (rollback) quant à son vote et donc à l’état de la blockchain. Cependant, chaque vote subséquent va doubler la durée nécessaire au réseau pour déverrouiller un vote donné.

• Les votes qui sont envoyés dans le stack ont un délai de déverrouillage de 2 slots ;
• Lorsqu’un validateur envoie son vote dans le stack, tous ses votes ayant un délai d’expiration inférieur sont purgés ;
• En cas de rollback, le délai de verrouillage des votes encore présents dans le stack ne double pas tant que le délai d’expiration du vote à rollback n’a pas été dépassé par celui du dernier vote.

Exemple

Afin de visualiser le système, imaginons l’état du stack suivant. Il y a 4 votes, et le validateur souhaite roll back jusqu’au vote 2. Il doit attendre 5 slots, soit le temps 9.

Vote	Temps en slots	Délai de verrouillage	Délai d’expiration
4	4	2	6
3	3	4	7
2	2	8	10
1	1	16	17

Le vote 5 arrive 5 slots plus tard, au temps 9.

Vote	Temps en slots	Délai de verrouillage du vote	Délai d’expiration du slot
5	9	2	11
2	2	8	10
1	1	16	17

Le vote 6 arrive juste après au temps 10.

Vote	Temps en slots	Délai de verrouillage du vote	Délai d’expiration du slot
6	10	2	12
5	9	4	13
2	2	8	10
1	1	16	17

Au temps 10, les nouveaux votes rattrapent les anciens. Et le vote 2 expire au temps 10 : le vote 7, au temps 11 prend le dessus et tous les votes situés au-dessus sont évacués.

Vote	Temps en slots	Délai de verrouillage du vote	Délai d’expiration du slot
7	11	2	13
1	1	16	17

Le délai de verrouillage du vote 1 n’augmentera pas à 32 tant que le stack ne contiendra pas 5 votes.

Ainsi, nous commençons à comprendre pourquoi Tower BFT préfère la disponibilité à la consistance. Les nœuds du réseau vont émettre des blocs de façon continuelle sans pour autant saturer le registre. Une fois que la super-majorité du réseau s’accorde sur la même version de la chaîne grâce au système des délais d’expiration, les transactions sont finalisées.

Chaque nœud du réseau peut connaître l’état des autres nœuds grâce au proof of history, sans pour autant communiquer avec eux : Tower BFT est un algorithme de consensus asynchrone.

Récompenses et punitions

Comme chaque algorithme de consensus basé sur la preuve d’enjeu, Tower BFT va punir les nœuds défaillants. Le mécanisme de punition est appelé slashing :

• En cas de mauvais comportement, une partie du stake du validateur (son collatéral mis en jeu pour participer au consensus) est brûlée.
• En cas de bon comportement, il est récompensé.

L’algorithme assigne également un coût aux rollbacks : il s’agit tout simplement de la durée d’inactivité qui sera nécessaire pour pouvoir voter à nouveau (c’est-à-dire pour une fork n’étant pas issu de la fork à annuler). À l’inverse, le coût d’opportunité d’un vote est déterminé par la somme des récompenses allouées aux votes pour cette fork, qui augmentent de façon exponentielle avec le temps.

Conclusion

Sur Solana, la finalité des blocs n’est donc pas déterminée de manière probabiliste comme avec la preuve de travail. Dès que la super-majorité des nœuds a voté pour un hash du proof of history, ce hash est “canonisé”, et on ne peut pas revenir à un état antérieur. Les nœuds vont alors voter pour de nombreuses forks, de manière asynchrone. On ne peut que saluer l’ingéniosité des développeurs de Solana, qui ont adapté un algorithme de consensus très simple à leur innovation majeure, la preuve d’histoire, pour obtenir un débit record pour leur blockchain.

Solana est un projet extrêmement complexe, qui est actuellement à la pointe de la technologie dans le secteur des systèmes distribués. Ne peut pas se vanter d’être la blockchain la plus rapide du monde qui veut ! Ces deux articles ont présenté les innovations majeures de Solana, mais afin d’en avoir une vision technique exhaustive, il faudra explorer ses innovations mineures. Nous parlons de son système de propagation des blocs, de sa gestion du mempool, de l’exécution parallèle des smart contracts, et autres réussites !