Une introduction à Blockflow : L’algorithme de sharding d’Alephium

C’est la quatrième d’une série d’innovations techniques apportées par Alephium. Retrouvez les précédentes ici (PolW), ici (sUTXO), et ici (VM Alphred). Cet article se penche sur les concepts de sharding et sur le fonctionnement interne de Blockflow pour expliquer comment il améliore les performances de la blockchain Alephium.

TL;DR — Alephium est une blockchain shardée : son état est divisé en groupes, et les transactions sont traitées en parallèle par plusieurs blockchains pour augmenter le débit. Son algorithme de sharding est appelé Blockflow, et permet d’énormes améliorations UX avec des transactions cross-shard en une seule étape. Il gère également la relation entre les blocs dans toutes les chaînes, ce qui permet un nombre élevé de transactions par seconde tout en préservant l’intégrité du grand livre.

Le sharding dans le contexte de la blockchain

Le sharding est une technique de gestion de base de données qui consiste à diviser de grands ensembles de données en éléments plus petits et plus faciles à gérer. Lorsqu’il s’agit de grandes bases de données, il n’est pas pratique de traiter toutes les données sur une seule machine ou dans une seule table. Le sharding permet de répartir la base de données sur plusieurs machines en créant plusieurs tables plus petites, ce qui permet de paralléliser les tâches afin d’améliorer le débit.

C’est la même chose dans le contexte d’une blockchain : le sharding augmente le débit en parallélisant les transactions. Cela se fait au prix d’une plus grande complexité, car il devient plus difficile de maintenir un grand livre sécurisé et cohérent. Chaque blockchain shardée aborde ces compromis de différentes manières :

Polkadot, une plateforme multi-chaînes développée par la Fondation Web3, introduit un mécanisme de partage connu sous le nom de “parachains”. Les parachains sont des chaînes individuelles qui fonctionnent en parallèle, interconnectées par une chaîne de relais centrale appelée “chaîne de relais Polkadot”.

Zilliqa met en œuvre le sharding différemment. Il utilise le sharding au niveau du réseau pour faire évoluer la blockchain en divisant les transactions en blocs plus petits. Toutefois, il ne prend pas en charge le partage des états, l’état global de la blockchain devant être partagé par tous les blocs, ce qui limite son évolutivité.

Kadena réalise le sharding en introduisant le “chainweb”, une structure de blockchain tressée qui consiste en de multiples chaînes interconnectées qui collaborent pour former un réseau unique.

Alephium adopte une approche unique pour diviser la blockchain : il s’agit d’utiliser un DAG et un algorithme de division appelé Blockflow. Cette approche est avantageuse car elle ne repose pas sur une chaîne de coordination (par exemple, une beacon chain), il n’y a pas de perte de sécurité pour les shards individuels et elle permet des transactions inter-shards en une seule étape (nous y reviendrons plus tard).

Comment fonctionne Blockflow ?

Blockflow est l’algorithme de partage d’Alephium. Il vise à améliorer l’évolutivité et l’efficacité de la blockchain en divisant le réseau en chaînes parallèles gérables ou “shards”, tout en maintenant une sécurité élevée et une communication efficace entre elles pour un traitement transparent des transactions.

Dans le cas d’une blockchain unique, toutes les relations entre les blocs sont unidimensionnelles, comme une ligne droite : un bloc est lié au précédent, etc… jusqu’au premier bloc, généralement appelé bloc de genèse. Ces relations linéaires sont appelées “dépendances”.

Contrairement à une blockchain non-shardée, où un bloc suit un autre de manière linéaire avec une simple dépendance dans le temps, Alephium possède 16 blockchains parallèles (appelées shards chain), chacune produisant de nouveaux blocs en parallèle sans bloquer les autres chaînes.

En termes simples, Blockflow est (comme son nom l’indique) le livre de règles pour maintenir le “flux de blocs” et l’exactitude de la blockchain dans une matrice DAG bidimensionnelle, avec la dimension supplémentaire du temps.

Un graphe orienté acyclique est une structure de données qui peut représenter conceptuellement une série d’activités et leurs interrelations. Composé de nœuds interconnectés par des arêtes dirigées, il garantit le traitement ordonné de séquences de transactions, empêche la double dépense de pièces et protège contre les rejets du réseau. Il s’agit en quelque sorte d’un contrôle de sécurité destiné à maintenir des transactions équitables et sûres ou d’un arbre généalogique des transactions.

Plongeons plus profondément dans les dépendances

La complexité consiste ici à comprendre comment ces blocs sont connectés aux blocs précédents, afin de maintenir un ensemble cohérent de dépendances garantissant l’exactitude de la blockchain. Pour cela, un peu de contexte :

Les shards d’autres blockchains shardées sont appelés groupes sur Alephium. Ces groupes sont une division logique de l’état de la blockchain et de toutes les adresses créées sur celle-ci. Les groupes conservent des enregistrements de l’état de tous les shards/chaînes qui leur sont connectés, y compris les actifs, les états des contrats et la logique des contrats. Il s’agit du premier niveau du sharding.

Chaque blockchain est responsable du traitement des transactions d’un groupe à un autre groupe. Nous utilisons la notation (“from”, “to”). Bien que cela semble difficile à comprendre, vous devez vous rendre compte que chaque chaîne (appelée “shard” dans Alephium) provient d’un groupe et que dans chaque groupe, il y a un shard qui se connecte à tous les autres groupes et un autre qui est interne à ce groupe. C’est le deuxième niveau du sharding.

Ainsi, à partir d’aujourd’hui, vous obtenez (chaque (x,x) est une chaine shardée) :

Groupe 0 est : (0,0) — (0,1) — (0,2) — (0,3)
Groupe 1 est : (1,1) — (1,0) — (1,2) — (1,3)
Groupe 2 est : (2,2) — (2,0) — (2,1) — (2,3)
Groupe 3 est : (3,3) — (3,0) — (3,1) — (3,2)

Chaque chaine shardée est entre parenthèses et gère un flux de transactions unidirectionnel différent : (0,1) traite toutes les transactions du groupe 0 vers le groupe 1, et (1,0) gère les transactions dans la direction opposée, du groupe 1 vers le groupe 0.

(0,0) gère le flux de transactions internes du groupe 0, (1,1) gère les transactions internes du groupe 1, etc… Ce sont les shards intragroupes.

Par conséquent, chaque chaine shardée est soit un shard intergroupe (0,1), soit un shard intragroupe (1,1). Ceci est important car lorsque les blocs sont extraits, ils sont reliés par des dépendances à tous les shards du même groupe et à un shard (le shard intragroupe) de chaque autre groupe.

Pour vous donner un exemple, pour un bloc miné sur le shard (1,0), il y a 7 dépendances :

Quatre dépendances de chaque autre shard à l’intérieur du groupe, donc (1,0) — (1,1) — (1,2) — (1,3).
Trois dépendances de chaque autre groupe (les shards intragroupes) : (0,0) — (2,2) — (3,3).

Ces dépendances sont placées dans l’en-tête du nouveau bloc, ce qui les intègre naturellement dans la structure du bloc. C’est ce qui se passe pour chacun des nouveaux blocs extraits sur les 16 chaînes : grâce à la matrice DAG, ils sont tous connectés à un autre groupe, ce qui permet de préserver l’intégrité du grand livre tout en augmentant le débit.

Transactions cross-shard en une seule étape

Cela permet quelque chose d’unique : les transferts d’actifs entre les shards de groupe en une seule étape ! Notez qu’il n’y a pas besoin de transferts d’actifs entre les chaînes shardées en raison de la structure unique de sharding bidimensionnel d’Alephium.

Voici un exemple :

Bob a une adresse dans le groupe 0. Il veut envoyer $ALPH (ou un NFT) à Alice, dont l’adresse se trouve dans le groupe 3. Il crée la transaction sur le superbe wallet de bureau, saisit l’adresse d’Alice et appuie sur “send”. Que se passe-t-il ?

Cette transaction est incluse dans un bloc sur le shard (0,3), qui est le shard reliant les groupes 0 et 3 dans cette direction. Elle déclenche un changement de solde sur l’adresse de Bob et met à jour l’état du groupe 0.

Un nouveau bloc dans l’une des quatre chaînes du groupe 3 vérifiera les dépendances avec tous les autres groupes et constatera qu’un nouveau bloc du groupe 0 a été engagé, transférant des actifs du groupe 0 vers le groupe 3. L’état local du groupe 3 sera mis à jour pour refléter le fait que l’adresse d’Alice dans le groupe 3 a reçu des actifs du groupe 0, qui sont maintenant disponibles pour être utilisés.

C’est essentiellement ainsi que se déroule la transaction cross-shard en une seule étape : lorsqu’un nouveau bloc du groupe de destination vérifie les dépendances de tous les autres groupes et s’assure qu’il n’y a pas de double dépense, il recueille les informations relatives au transfert d’actifs et met à jour l’état du groupe de destination.

Cela permet d’effectuer une transaction en une seule étape, au lieu de procéder à de multiples vérifications dans les chaînes de source et de destination, comme c’est le cas dans de nombreuses autres blockchains.

En conclusion…

En tant que blockchain shardée, Alephium peut augmenter son débit en ajoutant des shards. Actuellement, elle compte 400 transactions par seconde (et elle peut atteindre 10 000 TPS avec 1024 shards). Blockflow est la technologie de base d’Alephium qui permet une telle évolutivité de la blockchain. D’ailleurs, BlockFlow était le premier nom d’Alephium !

En s’appuyant sur les règles de consensus au sein de la structure DAG, BlockFlow garantit l’exactitude et la sécurité des transactions sur l’ensemble du réseau. Il se distingue ainsi des algorithmes de sharding traditionnels, car il offre une expérience plus efficace et meilleure aux développeurs et aux utilisateurs grâce à des transactions cross-shard en une seule étape.

Si vous avez des questions sur ce sujet, vous êtes invités à nous rejoindre sur Discord, ou Telegram. N’oubliez pas de suivre @alephium et @Alephiumfr sur Twitter pour rester informé.