1. Accueil
  2. /
  3. Infrastructure
  4. /
  5. Cardano Multiverse

Cardano Multiverse

Comment gérer les branches éphémères de Cardano de la manière la plus efficace.
Milkomeda a le plaisir d’ouvrir le Multiverse, qui est une bibliothèque multi-plateforme spécialement conçue pour gérer le rollback de courte durée de Cardano (branches de courte durée).

Le consensus de Cardano

Cardano utilise un outil cryptographique pour déterminer qui va créer un bloc à un moment donné : la fonction aléatoire vérifiable (VRF). Il s’agit essentiellement d’un schéma cryptographique permettant de générer des nombres aléatoires et d’être en mesure de prouver que ces nombres ont été générés de manière aléatoire. Ce qui est intéressant, c’est la façon dont cette fonction est utilisée pour Cardano. Cardano divise le temps en époques. Il y a 432 000 créneaux dans chaque époque et chaque créneau dure une seconde. Chaque slot est une opportunité pour un groupe de joueurs de soumettre un bloc et d’identifier si le groupe de joueurs a été élu pour soumettre un bloc. Pour un slot donné, ils utilisent le VRF (leur chance est proportionnelle à la mise totale). Le calendrier des blocs est privé pour chaque groupe de joueurs.

Trois choses peuvent se produire :

  1. Personne n’est autorisé à créer un bloc pour ce slot.
  2. Une seule personne est autorisée à créer un bloc pour ce créneau.
  3. Plusieurs personnes sont autorisées à créer un bloc pour cet emplacement.

Les deux premiers cas sont faciles, tandis que le dernier cas peut générer des conflits, auquel cas le réseau devra décider de la branche à prendre. Maintenant, le nœud a déjà un algorithme pour prendre cette décision, mais comme vous pouvez le voir, cela crée déjà quelques problèmes :

En outre, la propagation des blocs peut connaître des problèmes. Une stake pool a une seconde pour recevoir les derniers blocs, créer le nouveau bloc et ensuite propager le bloc à l’ensemble du réseau. C’est le cas parce qu’à la fin de cette seconde, un nouveau bloc peut être créé et ils voudront s’assurer qu’il fait référence à leur bloc.

Quelles sont les solutions disponibles ?

Le réseau prendra une décision. Toutefois, il peut arriver que la décision prise par mon nœud local ne soit pas celle prise par le réseau. Dans ce cas, mon nœud local détectera qu’il s’est écarté du consensus du réseau concernant la branche à prendre et effectuera un « rollback ». Si vous utilisez cardano-db-sync comme nous le faisons, cela signifie que vous connaîtrez une pause pendant qu’il supprime les informations de la branche rejetée et applique les blocs de la nouvelle branche sélectionnée.

Lorsque cela se produit, vous pouvez vous sentir un peu gêné que certaines données aient été supprimées de votre base de données et vous devez concevoir votre code en tenant compte de l’incertitude. Habituellement, vous faites cela en appliquant un délai avant la confirmation d’un objet donné dans la base de données.

Cela crée un retard pour toutes les personnes qui dépendent de cet outil. Je peux créer une transaction avec des UTxO comme entrées qui seront invalides au moment où ma transaction atteindra le réseau parce que j’ai fait l’erreur de ne pas attendre les trois à cinq minutes nécessaires pour atteindre 10 blocs confirmant la transaction.

Nous pouvons faire mieux. Je ne devrais pas avoir à attendre trois à cinq minutes pour avoir un bon niveau de confiance dans la confirmation de ma transaction. Je ne devrais pas non plus avoir à craindre que l’indexeur fasse une pause pendant qu’il applique un rollback. En fait, par le biais de la Fondation Milkomeda, nous avons fait une proposition catalytique pour concevoir et mettre en œuvre un meilleur algorithme pour gérer les branches à courte durée de vie : Le Multivers.

Le multivers

Le multivers est un outil qui garde la trace de chaque branche de la blockchain : Chaque variante de la ligne de temps. C’est assez simple, en fait. L’astuce consiste à ne pas considérer la blockchain comme une liste liée de blocs mais plutôt comme un arbre (c’est pourquoi nous appelons ces bifurcations des « branches »). Idéalement, ces branches sont de courte durée (quelques blocs tout au plus) et une seule branche croît en permanence.

Maintenant, nous ne voulons pas maintenir la blockchain entière et toutes les branches en mémoire. L’une des premières exigences que nous nous fixons est donc de ne gérer qu’une fenêtre donnée.

Le multivers prend en compte les branches.

Nous nous assurons que cette vue est suffisamment large pour gérer l’instabilité de la blockchain. Au-delà de cette vue, nous supposons que la probabilité d’un fork est proche de 0.

Définissons quelques concepts :

  • Les « feuilles » (« tips » dans le schéma) sont les blocs qui n’ont pas de bloc enfant ;
  • Les racines sont les blocs dont les parents ont été ramassés (ils sont tombés en dehors de la vue).

L’ajout d’un nouveau bloc en tant qu’enfant de l’une des feuilles peut déclencher le glissement de la vue vers la droite : les racines tomberont en dehors de la vue et seront collectées.

Vue décalée sur la droite.

Maintenant que nous avons une vue de la tête de la blockchain, nous pouvons commencer à ajouter différents outils qui nous seront utiles.

Lors de l’écriture du pont Milkomeda, nous avions besoin de garder la trace des UTxO que nous contrôlons, mais pas nécessairement de tous les blocs. Ainsi, au lieu de stocker l’état complet de la blockchain pour chaque bloc, nous stockons simplement un sous-ensemble du grand livre. Chaque instantané contient la liste des UTxOs que nous contrôlons à ce moment précis.

Nous avons pensé à les stocker dans une base de données. Cependant, il était trop difficile de représenter efficacement les différents états entre deux branches données : certaines UTxO sont disponibles si nous sommes à l’état s7 mais pas à s7′. Nous avons donc décidé qu’il serait plus efficace de les conserver en mémoire. L’approche naïve est d’utiliser un HashMap : UTxOPointer -> UTxO. Très rapidement, cette approche commence à utiliser beaucoup de mémoire. En effet, pour chaque nouveau bloc, nous copions l’état du parent, puis nous enlevons/ajoutons des UTxO afin de créer le nouvel état.

Heureusement, il existe une structure de données parfaite pour ce genre de situation : Hash Array Mapped Tries (HAMT). Certaines opérations peuvent être un peu plus lentes mais le gain d’espace est largement supérieur. Cette structure de données a l’avantage de partager les mémoires entre deux copies. Par conséquent, l’ajout et la suppression d’entrées dans les deux copies vont muter la copie locale, tout en gardant l’intersection partagée.

C’est la manière la plus optimale de stocker l’état entre deux blocs. Nous ne payons que le coût de la différence entre deux blocs.

Applications

Portefeuille
Il est possible de tirer parti du multivers pour confirmer une transaction plus rapidement qu’en attendant l’ajout de blocs. Maintenant que nous surveillons toutes les branches de la blockchain, nous pouvons vérifier si notre transaction se trouve sur toutes ces branches. Par exemple, deux mineurs de blocs en concurrence pour le même emplacement peuvent avoir ajouté notre transaction dans leurs blocs respectifs.

Si notre transaction, T, se trouve sur toutes les branches possibles comme suit, alors il est probable que notre transaction sera confirmée sur la chaîne :

ou

Explorateur
Un élément qui manque souvent dans l’explorateur de blockchain est qu’il n’est pas possible d’identifier les blocs qui ont été rejetés. La possibilité de voir comment le réseau se comporte actuellement et de suivre les forks au fur et à mesure qu’ils se produisent (ou se sont produits) démontrera la robustesse de la blockchain. Les utilisateurs seront en mesure de comprendre pourquoi une transaction, qui était il y a un instant sur l’explorateur, a été supprimée. Les opérateurs de stakepool seront en mesure de comprendre pourquoi leur bloc a été rejeté par le réseau.

La source de cette traduction est un article de Nicolas Di Prima, contributeur de Milkomeda : https://medium.com/@milkomedafoundation/cardano-multiverse-1146266c30c