Résolution de fork « 3-3 »

Nodes Duniter-v1
,
1

Je me suis décidé à lancer une petite série de billets techniques sur les développements de Duniter. Le principe est simple : si je dois développer une fonction dans Duniter, j’en fais l’explication au préalable.

Cet exercice est intéressant à plusieurs titres :

  • On montre qu’ici on glande pas.
  • Expliquer à d’autres, c’est affiner sa propre compréhension.
  • Conserver une trace des raisonnements sous-tendant le code.
  • Recueillir les avis, pour affiner l’algorithme ou juger de son intérêt.

Je souhaite redévelopper la gestion des forks dans Duniter. Car aujourd’hui, elle n’est vraiment pas efficace à mes yeux :

  • en v1.3.x, un fork naissant met plusieurs heures à se résorber
  • en v1.4.x, la résolution est beaucoup plus rapide (de l’ordre de 20 minutes), mais un fork naissant peut entraîner des nœuds dans une voie sans issue, et donc les bloquer

On peut considérer que la 1.4.x est une régression du point de vue du comportement long terme. J’aimerais bien avoir le meilleur des deux versions, à savoir : obtenir un fork rapide et sans blocage.

Rappels

Rappel 1 : blockchain et forks

Comme vous le savez, une blockchain c’est avant tout un enchaînement de blocs :

[] - B#20 - B#21 - B#22 - B#23

Dans le cas nominal, à l’instant 24, arrive un block B#24 qui étend la blockchain courante :

[] - B#20 - B#21 - B#22 - B#23 - B#24

Mais il se peut aussi qu’en observant le réseau, on voit :

                 ,-C#22 - C#23           <-- Nœud 'C'
[] - B#20 - B#21 - B#22 - B#23 - B#24    <-- Nœud 'B','J','K',[...]
                 |             `-E#24    <-- Nœud 'E'
                 `-D#22 - D#23           <-- Nœud 'D'
[] - F#20 - F#21                         <-- Nœud 'F'

C’est-à-dire que l’on a une blockchain B partagée par, mettons, une majorité, puis d’autres nœuds qui ont une blockchain différente. Ici :

  • le nœud ‘C’ a une blockchain différente de ‘B’ à partir du bloc 22
  • le nœud ‘E’ a une blockchain différente de ‘B’ à partir du bloc 24
  • le nœud ‘D’ a une blockchain différente de ‘B’, ‘C’ et ‘E’ à partir du bloc 22
  • le nœud ‘F’ a une blockchain différente de ‘B’, ‘C’, ‘D’, et ‘E’ depuis très longtemps

Rappel 2 : la piscine de blocs

Historiquement, Duniter n’a pas de piscine pour ses blocs contrairement aux identités, certifications, adhésions et transactions. C’est-à-dire que si Duniter reçoit un bloc, il vérifie que celui-ci s’ajoute bien à sa blockchain et si c’est le cas, il l’enregistre. Sinon il le refuse et ne l’enregistre pas, il n’y en gardera aucune trace.

Algo v1.3.x

Dans cette version de Duniter, le logiciel utilise un algorithme que je pourrais nommer « 6-6 pull » pour résoudre les forks réseau observés.

Un fork réseau, c’est tout simplement l’observation qu’il existe une blockchain différente de la nôtre. Par exemple, la blockchain C (portée par le nœud ‘C’) est un fork du point de vue de ‘B’.

Plaçons-nous donc dans le cas du nœud ‘B’, qui possède la blockchain B, et imaginons que ‘C’ possède une blockchain C allant jusqu’à C#30.

L’algo « 6-6 pull » est une tâche récurrente, toutes les 4 minutes environ, où ‘B’ effectue un léger scan du réseau pour connaître le bloc courant de ses pairs. Cet algo dit que si ‘B’ découvre la blockchain C, et que celle-ci est plus haute d’au moins 6 blocs en numéro et 6 blocs en temps, et que ‘C’ est un nœud membre, alors ‘B’ doit tenter de suivre cette blockchain C.

Bien entendu, la blockchain C ne peut pas être appliquée telle quelle : les bloc C#22 à C#24 sont en conflit avec B#22 à B#24. B#22 le point de fork. Pour que ‘B’ puisse empiler les blocs C#22 à C#30, il lui faut préalablement dépiler les blocs B#22 à B#24, c’est-à-dire retirer ces blocs et invalider les changements qu’ils ont introduit.

Une fois le dépilement opéré, ‘B’ tente d’appliquer C#22 à C#30. Si un accroc survient durant l’application (par exemple parce que le bloc C#23 ne respecterait pas les règles du protocole suivies par ‘B’), ‘B’ dépile les blocs C déjà empilés, puis rempile ses propres blocs dépilés (ici, B#22 à B#24). Mais si l’opération d’empilement de C s’est bien déroulée, alors ont dit que ‘B’ a switché sur la branche C.

Note : “switcher” est mon terme. Vous pourriez tout aussi bien dire “merger” mais ce terme venant du monde Git me paraît incorrect car il opère aussi une fusion des branches, ce qui n’est pas le cas ici. Je préfère donc le terme “switcher” qui indique qu’on a changé de branche.

Et au bout de 4 minutes, on recommence.

Faits notables

Ah mais en fait il y a une piscine de blocs !

Les blocs B dépilés sont toujours enregistrés en base de donnée, mais ils sont flaggués avec le champ fork = 1. J’ai dit dans le Rappel 2 qu’il n’y avait pas de piscine de blocs, mais on est bien là face à une piscine de blocs, de fait.

Cette mémorisation, cette piscine est en réalité nécessaire : sans ce mécanisme, comment rempiler les blocs B au cas où C serait une blockchain invalide ?

Le switch dépend du réseau !

Eh oui : dans Duniter 1.3.x, les forks ne sont détectés et suivis qu’à travers cet algorithme intervenant toutes les 4 minutes et sous réserve que le fork observé provienne d’un nœud membre.

Il suffit donc que les nœuds hébergeant C soit injoignables, ou que l’on ne tombe pas sur eux lors du pull pour totalement ignorer l’existence de C. Cela est une des causes de la durée interminable nécessaire aux nœuds 1.3.x pour résoudre un fork.

Algo v1.4.x (version courante)

C’est l’algorithme que j’appelle « 3-3 pull ». C’est le même qu’en 1.3.x, sauf deux points :

  1. Ce n’est plus 6 blocs d’avance en numéro et en temps qui déclenchent le switch, mais 3 et 3.

  2. La piscine est désormais officiellement reconnue : lorsqu’un bloc de fork arrive, celui-ci n’est plus refusé : au contraire, il est enregistré en base de données et déclenche une résolution de fork.

Note : un bloc de fork peut tout de même être refusé dans les cas où ce bloc a déjà été reçu, ou s’il est considéré trop ancien.

Avantages

La détection de fork est très rapide

Car le déclenchement se fait sur réception du bloc, donc au plus tôt de son émission sur le réseau.

Le suivi de la branche n’est pas conditionné par son hôte

Ainsi, toute blockchain valide peut être suivie indépendamment de quel nœud l’héberge.

La résolution de fork devient indépendante du réseau

La résolution de fork se fait sans aucun accès à la couche réseau.

Inconvénients

Il reste toujours l’algorithme hérité de la 1.3.x, le « pull » qui interagit avec ce nouveau mécanisme de résolution. Et comme ce comportement hybride n’a pas vraiment été pensé, les deux mécanismes se perturbent et provoquent des bugs (le pull cherche à télécharger des blocs de forks, mais ceux-ci ont déjà été reçus en piscine et cela déclenche une erreur « fork block already known » qui interrompt la résolution).

C’est un problème purement technique de code. Théoriquement les deux algos ne se gênent pas l’un l’autre.

Algo >= v1.5.x

Toutefois on peut noter que le pull peut tout à fait réduire son rôle au téléchargement des blocs inconnus sur le réseau, tandis que l’algorithme de résolution de blocs se concentre sur sa tâche de résolution à partir des blocs connus localement.

C’est l’algorithme que j’appelle « 3-3 ».

Donc cette fois, je détaille l’algorithme de résolution qui se fait sans accès réseau, uniquement avec les blocs en piscine :

  • Soit avgGenTime le temps de génération visé d’un bloc (= 5 minutes dans Ğ1)
  • Soit HEAD(I) le bloc courant au début de procédure
  • Soit Hn = HEAD(I).number
  • Soit Tn = HEAD(I).medianTime
  • Soit forkWindowSize le nombre maximums de blocs qui peuvent être dépilés depuis Hn
  • Soit S un tableau de chaînes de blocs

    S va contenir les suites de blocs trouvés en piscine qui forment des chaînes entières et dont le dernier bloc est commun avec la chaîne locale (= un point de fork). Ce sont donc des chaînes potentiellement applicables sur lesquelles on peut switcher !

  • Soit P (= blocs Potentiels) un tableau contenant tous les blocs en piscine avec (number >= Hn + 3) ET (medianTime >= Tn + 3*avgGenTime), triés par number décroissant (important !)

    Ce sont tous les blocs qui peuvent former la tête d’un fork. Il sont forcément à 3-3 de Hn. C’est la condition absolue pour suivre le fork.

  • Pour chaque candidat C de P :

    On essaye de former des chaînes complètes pour les ajouter à S

    • Si C n’appartient pas déjà à S :
      • Récupérer la suite s de blocs descendante partant de C (inclus) jusqu’à ce que :
        • soit (a) un bloc de la chaîne s appartienne déjà à la blockchain principale
        • soit (b) un bloc de la chaîne s n’ait pas été trouvé en piscine
        • soit (c ) un bloc b de s ait comme propritété b.number <= Hn - forkWindowSize

      S’il n’y a pas de point de fork suffisamment récent, ou qu’il manque un bloc, alors tous ces blocs sont inexploitables en l’état. On les retire donc de P en plus de ne pas les ajouter à S, afin de ne pas faire des tours de candidats pour rien (ils mènent forcément à une impasse ! les blocs étant liés entre eux).

      • Si (b) ou (c ) est vrai, retirer tous les blocs de s présents dans P

      Mais si ça passe, bingo ! On a une chaîne potentielle complète, avec point de fork commun à notre blockchain locale.

      • Sinon, ajouter s à S, et retirer C de P

Il se peut que l’on ai plusieurs chaînes potentielles dans S, alors on les teste toutes et on sélectionnera la plus longue.

  • Soit MM un tableau de blocs
  • Pour chaque suite possible s de S :

    On va dépiler jusqu’au point de fork, et se rappeler de ce qu’on a dépilé pour revenir à un état propre ensuite.

    • Soit REV un tableau de blocs
    • Dépile les blocs de la blockchain locale jusqu’au point de fork avec s, et les mémoriser dans REV

    On essaye d’appliquer les blocs, en vérifiant bien que ceux-ci respectent les règles du protocole (on n’a pas pu le faire avant, c’est coûteux)

    • Appliquer tous les blocs de s, mais arrêter l’application en cas d’erreur
    • Mémoriser le dernier bloc ajouté s’il y en a un, à MM

    On revient à l’état propre.

    • Dépiler les blocs de s qui viennent d’être ajoutés, et rempiler les blocs de REV

Si l’on a des chaînes qui ont fonctionné au moins en partie, on va sélectionner la plus longue

  • Si MM n’est pas vide :
    • Sélectionner F = MAX(MM)

    Mais on vérifie bien sûr que cette chaîne n’a pas échoué au bout de 1 ou 2 essais, sinon on ne respecte pas le 3-3 !

    • Si (F.number >= Hn + 3) ET (F.medianTime >= Tn + 3*avgGenTime) :
      • Soit f la suite s contenant F
      • Dépiler la blockchain locale jusqu’au point de fork avec f
      • Appliquer la suite f

Et voilà ! Maintenant il ne reste plus qu’à coder cet algo, le couvrir par de jolis Tests Unitaires, et à l’intégrer dans Duniter !

Merci pour votre lecture attentive.

10 Likes
2

Allez hop ! L’algorithme dans son Test Unitaire : https://github.com/duniter/duniter/commit/809b413e706baf86d1b56dc131f148477d308a80

Reste plus qu’à pousser ce code dans Duniter, et ça roule !

3 Likes
3

Nice, ça bosse dur :slight_smile: et ça écrit de la doc en plus :wink:

Comme les forks sont la seule faille que j’observe conceptuellement sur Duniter, je me permet de revenir sur notre précédente discutions qui commence à dater maintenant ^^

à cause de la POW personnalisée, avons-nous aujourd’hui, grâce à ces modifications de méthode de résolution de fork, une protection, contre un regroupement de 6 membres pirates qui possèderait une forte puissance de calcul (2 fois plus que la POW min du réseau à vue de nez), pour supprimer avec un fork une transaction précédemment validée (par 3 blocs) ?

Au vu de ta documentation, il me semble que cette attaque a été simplifiée. Mais comme je n’ai hélas pas été très présent parmi vous ces derniers temps (mille excuses), je pose la question pour savoir si j’aurais raté quelque chose :slight_smile:

Thread de la précédente discussion ici

:roll_eyes::relaxed:

1 Like
4

A post was merged into an existing topic: Block issuance distribution