Résolution de fork, algo « issuersCount 3-3 »

Nodes Duniter-v1
1

Suite aux récentes discussions sur le thread block issuance distribution, je propose ci-après une version améliorée de l’algo de résolution de fork « 3-3 » qu’a conçu @cgeek.

C’est très proche de l’algo d’origine de cgeek et ne demande pas de modifier duniter d’avantage que ce qui est déjà prévu pour la version 1.6.x, enfin je crois :slight_smile:

Il y a sans doute des erreurs, voici en substance les quelques changements :

  • on traite a part les cas de fork demandant un petit rolling back, avec l’idée de ne pas forker si on peut faire avancer la branche locale
  • pour les forks qui demandent un rolling back plus élevé on traite les branches une a une en commençant par celles dont le point de fork est le plus loin dans le passé. Et au lieu de choisir la branche la plus longue parmis toutes les branches possibles ont évalue les branches une a une et l’on switche sur une branche si issuersCount est plus élevée dans cette branche.
  • et pour avoir un comportement déterministe si les deux branches ont exactement les mêmes issuersCount a chaque fois on choisi la branche dont le hash du 1er bloc qui diffère est le plus petit.

Algo de résolution des fork « issuersCount 3-3 »

Voici le détail de 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 dans l’ordre de l’ancienneté de leur point de fork

  • On tri les suites s de S par ordre croissant de numéro de bloc de leur point de fork
    • Pour chaque suite possible s de S :

      • 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

      • Si REV.length <= 3 :

        • Si le noeud est membre et n’est actuellement pas exclu du calcul des blocs :
          • On note le bloc s(H) comme “fork trop jeune, a réévalué plus tard, au moins quand le head du noeud aura changé”
          • rempiler les blocs de REV
        • Sinon :

          on switche sur s

          • Soit f une chaîne de bloc
          • Vérifier puis empiler dans f tous les blocs de s, mais arrêter l’application en cas d’erreur (on n’a pas pu vérifier les blocs avant, c’est coûteux)
          • Récupérer le head de Hf de f
          • Si (Hf.number >= Hn + 3) ET (Hf.medianTime >= Tn + 3*avgGenTime) :
            • Appliquer la suite f
            • sortir de la boucle S et reconstruire S (certaines chaines s n’ont peut etre plus de sens)
          • Sinon :
            • Supprimer de la piscine les blocs invalides (les blocs dans s mais pas dans f)
            • rempiler les blocs de REV

      • Si REV.length > 3 :

        • Soit la variable decision = null
        • Soit currentFrameSize la taille de la fenêtre courante au dernier bloc commun (au point de fork)
        • Si s.length < REV.length ET s.length < CEIL(currentFrameSize/3) alors noté le bloc s(H) comme “fork trop court” et passer chaîne s suivante de S
        • Sinon :

          On calcule la moyenne du champ issuersCount sur les CEIL(currentFrameSize/3) premiers blocs de chaque fork

          • Soit deux entiers Mo=0 et Mf =0
          • Parcourir REV a l’envers (de la fin au début, cad du point de fork jusqu’au head de la branche locale), pour chaque bloc Bi de REV (i = nombre de blocs après le point de fork) :
            • Si i >= CEIL(currentFrameSize/3), on sort de la boucle
            • Sinon
              • Mo += s(i).issuersCount
              • Mf += Bi.issuerCount
          • Fin de la boucle REV
          • Si Mo == Mf, on tranche la question en swichant sur s si s(1).hash < REV.last.hash
          • Sinon si Mo > Mf, on note le block s(H) comme “fork minoritaire”, et on rempile les blocs de REV
          • Sinon : // Mo < Mf
            • Soit f une chaîne de bloc
              • Vérifier puis empiler dans f tous les blocs de s, mais arrêter l’application en cas d’erreur (on n’a pas pu vérifier les blocs avant, c’est coûteux)
              • Récupérer le head de Hf de f
              • Si (Hf.number >= Hn + 3) ET (Hf.medianTime >= Tn + 3*avgGenTime) :
                • Appliquer la suite f
                • sortir de la boucle S et reconstruire S (certaines chaines s n’ont peut etre plus de sens)
              • Sinon :
                • Supprimer de la piscine les blocs invalides (les blocs dans s mais pas dans f)
                • rempiler les blocs de REV

Concernant les “fork trop jeune” on peut les réévaluer a chaque changement de head du noeud, donc lorsque le noeud empile un nouveau bloc dans sa chaine locale il doit retirer la mention “fork trop jeune” de tout les blocs en piscine qui ont cette mention.

Concernant les “fork minoritaires”, on les gardes en piscine tant que leur point de fork est a moins de forkWindowSize blocs du head local, juste pour se souvenir de ne pas les réévaluer.

@cgeek si après relectures et corrections l’on abouti a un algo qui te conviens je veut bien t’aider a l’implémenter dans duniter mais je vais avoir besoin d’être guidé un peu :slight_smile:

2

Si tu veux tenter l’expérience, c’est assez simple : tu as deux fichiers :

Le fichier de test parle de lui-même, il te faudra simplement en créer un nouveau.

Quant au Switcher, je te conseille aussi d’en faire une copie et de le nommer autrement, « SwitcherIssuersCount33 » par exemple. Ainsi on pourra changer l’algorithme utilisé simplement en changeant de composant de Switch.

Le contenu du fichier Switcher ne correspond pas directement à l’algo qu’on a codé sur le forum, alors c’est un peu difficile de l’y repérer. Je te conseille donc simplement de partir de la méthode publique tryToFork qui contient la logique générale et appelle les logiques particulières.

Tu devrais t’y retrouver quand même, le fichier fait 219 lignes, commentaires et “lignes accolades” incluses.

Je te conseille vivement VSCode et son mode debug pour parvenir à tes fins !

Bon courage :slight_smile:

1 Like
3

Ok je tenterai l’écriture d’un fichier de test ce we, j’ai parcouru ton fichier de test fork-resolution-3-3.ts il est effectivement assez compréhensible :slight_smile: