Block issuance distribution

Le protocole en version 0.6 est désormais exploitable. Nous pourrons donc voir dès demain l’impact du retour de l’ancienne règle de difficulté 0.4 (légèrement modifiée toutefois).

A sample on the last 24H:

An interesting thing would be mesure this relatively to the handicap, which is not shown here. Pafzedog issues more blocks than others, but his personal difficulty is also higher.

9 « J'aime »

Suite à notre discussion sur le chat, je reprends les trois points de tortue qui me semblent corrects :

  • le déni de service lui est réglé par le fait que seuls les membres peuvent miner + le protocole d’exclusion de la 0.40.

  • la double dépense par l’envoi de 2 TX simultané doit être réglé par un mécanisme de consensus plutôt rapide (et pas 1667 bloc) afin d’être sur que tout le réseau est OK pour dire que ces coins reçus sont bien a moi (6 blocs me semblent bien)

  • la réécriture d’une chaine à part, plus rapide, pour la publier plus tard, afin de supprimer une transaction préalable, est le gros point noir d’aujourd’hui. Car facilement réalisable avec le piratage de la clef de quelques identités membres, et extrêmement facilité par la preuve de travail personnalisé qui réduit fortement la complexité moyenne de la blockchain.

Et je cite cgeek :

Ce peut être tout simplement ça l’algorithme : rejoindre systématiquement la branche où l’on observe le plus de calculateurs sur le réseau (à raison de 1 par membre). Aujourd’hui Duniter n’a pas de vision du réseau façon Sakia, mais c’est assez simple à ajouter.

Qui d’un algo de la forme suivante :

  • Quand un noeud ajoute un block sur son HEAD, il broadcast le block ET ajoute sa signature au broadcast
  • Quand un noeud reçoit un block d’un fork différent, il switch si les signatures accumulées sur ce block sont plus nombreuses

Dans cette forme, pas besoin de connaître tous le réseau pour observer la majorité : le broadcast de signatures et leur accumulations permet de savoir de manière isolée quel block est majoritaire dans le réseau.

Aujourd’hui quand un nœud change son HEAD, c’est-à-dire quand il reçoit un nouveau bloc qui s’ajoute parfaitement au HEAD actuel, il le propage sur le réseau. On pourrait donc en effet ajouter une signature supplémentaire pour “propager son propre état du HEAD”.

Sauf que cet algorithme, tel quel, risque de provoquer des engorgements réseau comme cité par Tortue dans son post sur les 10.000 connexions.

Pourquoi cela n’arrive pas dès aujourd’hui ? Après tout, chaque nœud propage dores et déjà son HEAD : c’est dû au fait que l’on partage uniquement le HEAD, pas la signature supplémentaire. Et donc quand un nœud a déjà reçu ce nouveau bloc, il refuse une 2ème réception et donc stoppe la 2ème propagation. Tandis que si l’on ajoutait la signature supplémentaire, alors c’est comme si, à chaque nouveau bloc et en imaginant un réseau de 5.000 nœuds, on devait broadcaster 5.000 documents.

On peut imaginer que le noeud s’abstienne de broadcaster directement le HEAD signé qu’il connait déja. Il peut par exemple ne broadcaster son HEAD contre-signé que si il a atteint (10% des membres) signatures supplémentaires par rapport au dernier broadcast.

On notera que l’ajout d’une telle fonction que j’appellerai “vote” permet de rendre utile même les noeuds ne participant pas à la PoW.

Bon je viens de relire entièrement le thread Block issuance distribution, et je crois avoir trouver une méthode déterministe de résolution des fork qui corrige les problèmes connus et qui ne demande pas d’avoir une vision du réseau :slight_smile:
De plus cette méthode peut s’appliquer avec ou sans pow, attention c’est complexe :

On se situe dans le contexte local d’un nœud duniter qui reçoit un HEAD ou un Block et qui se rend compte que ce head ou block n’est pas empilable sur sa chaîne locale, il vas donc le stocker avec fork = F != 0 et demander au nœud dont il a reçu l’info tout les blocks précédents jusqu’à trouver le dernier bloc commun, de sorte a pouvoir calculer la longueur du rolling back que produirait le switch sur cette branche. La longueur du rolling back c’est le nombre de blocks entre le HEAD du nœud et le dernier block commun entre les branches fork = 0 et fork = F.

Deux cas sont alors possible :
1. Switcher sur F nécessite un rolling back de moins de 6 blocks
2. Switcher sur F nécessite un rolling back de 6 blocks ou plus

Dans le cas 1 :
avec pow : on switch si la branche F a plus de 3/6* blocks d’avance ET plus de 15/30* min d’avance sur la branche O et si l’on est exclu du calcul des blocks (si la diff perso du noeud est actuellement trop élevée.). (ce que je nomme branche O c’est la branche locale principale du noeud, celle pour laquelle fork=0)
sans pow (avec pop) : Notons R le numéro du dernier bloc commun.
Si le bloc F(R+1) n’est pas prioritaire sur le block O(R+1) : on supprime F.
Sinon si le nœud a écrit l’un des 6 derniers blocs de la branche O on switche sur F. Sinon, on tag la branche F(Hf) comme “fork trop jeune a réévaluer plus tard”. (Prioritaire selon les critères de la PoP)

*3/6 ou 15/30 selon qu’on applique la règle “3-3” ou la règle “6-6”, je n’ai pas d’avis tranché sur ce point.

Dans le cas 2 :
avec pow : si la branche F a moins de 3/6* blocks d’avance OU moins de 15/30* min d’avance, on ne switche pas, on ne fait rien. Sinon, on applique l’algo du nombre d’écrivains pour s’avoir s’il faut ou non switcher sur la branche F (voir paragraphe suivant).
sans pow (avec pop) : Si le block F(R+1) est prioritaire sur le block O(R+1), on applique l’algo du nombre d’écrivains pour s’avoir s’il faut ou non switcher sur la branche F (voir paragraphe suivant). Sinon, on supprime la branche F de la bdd locale.

Algo du nombre d’écrivains :
On a une branche locale principale O et n branches alternatives notés F1, F2, … Fn
On note que pour le cas avec PoP sans pow : pour tout entier i dans [1;n] on a Fi(Ri+1) est prioritaire sur le block O(Ri+1), sinon la branche Fi aurait été supprimée avant d’appliquer le présent algo.

On traite d’abord la branche Fi dont le point de jonction Ri à le numéro de block le plus faible, puis quand on aura fini, soit l’on en déduira qu’il faut switcher sur Fi et on sort de l’algo, soit l’on supprimera Fi de la bdd locale et l’on passera a la branche Fi+1.
Notons F la branche Fi actuellement traitée et F(H) le dernier bloc de la branche F que le nœud a en mémoire dans sa bdd locale. Notons R le dernier bloc commun entre mes branches F et O.

On liste les auteurs des blocs F(R+1:Hf). (Pas besoin de requêter le réseau, il suffit de lire les champ issuer des blocks) et pour chaque auteur on mémorise temporairement le numéro du dernier bloc qu’il a écrit dans la branche F. On fait de même pour les blocs O(R+1:H).
On cherche ensuite les auteurs commun entre les deux branches et pour chaque auteur commun on prend le minimum entre les numéros des derniers blocs qu’il ont écrit dans chaque branche. On dépile ensuite virtuellement chaque branche pour annuler le dernier switch de chaque auteur.
On a deux nouveaux heads F(H’) et O(H’).
On calcule le nombre d’auteurs (d’issuers) différents sur la plage F(R+1:H’) et sur la plage O(R+1:H’).

On calcule le nombre d’auteurs (d’issuers) différents sur la plage F(R+1:Hf) et sur la plage O(R+1:Ho).
S’il y a plus d’auteurs sur la plage F(R+1:Hf) que sur la plage O(R+1:Ho) on switche sur F,
S’il y a exactement le même nombre d’auteur on choisi arbitrairement la branche donc le bloc R+1 a le plus petit hash // afin d’éviter un ping-pong du réseau
S’il y a moins d’auteurs sur la plage F(R+1:Hf) que sur la plage O(R+1:Ho), on note F(Hf) comme “branche minoritaire” et on la garde en mémoire jusqu’a ce que H-R soit supérieur au rolling back maximal (cgeek suggère 100 blocks je pense au contraire qu’il faut que ce soit beaucoup plus).
Fin de l’algo.

Ça mériterai que je formalise tout cas dans un langage plus proche d’un code, je prévois de le faire, mais dans un premier temps il fallait que je couche le concept par écrit. L’idée c’est de reprendre la proposition de choisir la branche sur laquelle il y a une majorité de nœuds membres, mais sans avoir besoin d’une vue du réseau, on choisi la branche ou le plus de membres ont écrits (uniquement depuis la bifurcation, ce qui est écrit avant la bifurcation ne compte pas).
Et pour éviter de nous faire influencer par les autres nœuds qui viendrais de switcher, on dépile virtuellement les deux branches jusqu’à annuler le dernier switch de chaque membre qui serait sur les deux branches.

Cet algo nous protège notamment de l’attaque qui consiste a soumettre au réseau une blockchain précalculée qui changerai le cours de l’histoire, car il faudrait que cette blockchain précalculée contienne plus d’auteurs que la branche principale, ce qui est possible pour une branche très courte mais plus la branche est longue moins c’est possible :slight_smile:

Il permet aussi de ne pas être piéger dans un cycle ou l’on reswitcherai par ping-pong entre deux fork car chaque branche est testée dans l’ordre de l’ancienneté de son point de bifurcation.

Je peut me tromper mais Il me semble que si l’on souhaite un réseau stable alors les critères de type 3-3 ou 6-6 ainsi que tout ce qui se base sur la vision du réseau n’est pas suffisants, a mon avis le nœud doit trancher en fonction du contenu du fork.

EDIT : quelques améliorations substantielles :

  1. j’ai supprimer le dépilement virtuel qui avait pour but d’éviter d’être influencé par le switch récent d’autres membres afin que le consensus soit plus rapide, en effet si des membres switches de O sur F alors cela va diminuer le nombre d’auteurs spécifiques a O (cad présents sur O et absents sur F) et vas donc entrainer un appel d’air sur F, tout les noeuds vont donc converger d’autant plus rapidement sur la nouvelle branche.
  2. pour résoudre le problème des attaques qui consiste a soumettre une branche a rolling back faible , j’ai créer un point d’ancrage : Un nœud qui peut faire avancer la branche O restera sur la branche O tant qu’il n’aura pas écrit un bloc même si F est prioritaire selon l’algo, dés qu’il a écrit un bloc et qu’il est donc exclu du calcul alors là il réévaluera F. L’idée c’est que si des attaquants soumettent une branche précalculée sur un point de bifurcation proche du head de la branche principale, on force la branche principale a avancée jusque l’a ou elle peut avancée afin de recomparer F et O “a la loyale”. et ça ne bloque personne car ne reste sur O que les nœuds qui peuvent effectivement faire avancer la branche O, ce qui augmente le nombre d’auteurs sur la plage O(R+1:H) :slight_smile:
  3. Ne pas supprimer F mais noté le bloc F(H) comme “fork minoritaire” afin de ne pas réévaluer la même situation plusieurs fois.
1 « J'aime »

En fait, je trouve ça tellement plus propre de se baser sur le nombre de calculateur de la chaine que je me demande pourquoi on traite deux cas ?

Je serais d’avis de partir sur l’algo du nombre d’écrivains dans tous les cas, qu’on ait 6 blocks de plus ou non.

Ca demande d’indexer le nombre de calculateur de chaque branche de fork au fur et à mesure qu’on les reçoit pour des questions de performances, mais sinon ça me semble beaucoup plus cohérent avec le principe de 1 calculateur = 1 vote. De plus, au fur et à mesure que nos discussions avancent, on voit bien que la vrai solidité de Duniter repose sur les signatures et pas sur les hash calculés pour la PoW (à la différence de BTC).

1 « J'aime »

Tu dis vrai, mais j’ai l’impression que cela ne change pas grand-chose.
Car un attaquant ne cherche pas à réécrire l’histoire sur 50 blocs. Et quand bien même, s’il le désire, il lui suffit de pirater 50 comptes membres pour avoir un nouvel auteur à chaque bloc…

PS: plus la taille de la branche générée par le pirate est longue moins une forte puissance de calcul n’est nécessaire
(pour une branche courte de 6 blocs il faut aller 2 fois plus vite que la pow min, mais sur une branche longue il faut aller a la même vitesse que le réseau + 3 blocs [ou 6 pour ton algo] )

Pour le moment, j’ai tendance à rejoindre @Inso avec le principe de 1 calculateur (membre) = 1 vote.

En fait jamais Duniter n’a résolu ses forks sur la base de la vision du réseau. L’algo 6-6 opérerait la résolution en consultant le réseau, mais les critères de sélection n’étaient pas « ce que voit le réseau ».

Oui enfin j’ai toujours présenté la PoW de Duniter comme un mécanisme de synchronisation, pas de résolution de fork. Le fait qu’on suive la branche la plus longue (6-6 ou 3-3) se repose sur le fait que la difficulté personnalisée assure une certaine rotation d’écriture, et que la plus longue branche semble aussi la plus légitime.

D’ailleurs je n’ai pas suivi la branche avec le plus grand nombre d’auteurs, car sinon cela donne un poids fort à un nouvel auteur. Et il y en a un paquet : ce sont tous les membres qui n’ont pas encore leur nœud, ou qui l’allument épisodiquement.

Point de détail : je préfère au contraire la conserver, car si je reçois à nouveau le bloc F(R+1), je vais le stocker car c’est bien un bloc de fork potentiel à tester. Au moins si je l’ai en base, je pourrais directement refuser la réception. Je peux le flaguer “invalide” histoire de pas retester le bloc sans arrêt.

Et à un moment, quand le bloc sortira de notre fenêtre de fork (par exemple 100 blocs), alors on pourra effectivement le supprimer car on ne pourra à ce moment plus jamais rebrancher sur F(R+1) car on sera déjà à O(R+102) et le plus vieux bloc dépilable sera F(R+2), ce qui nous empêche formellement l’empilage de F(R+1).

Si tu cherches simplement à savoir quelle branche a le plus d’auteurs, tu peux directement utiliser le champ issuersCount présent dans chaque bloc, non ?

Si je comprends bien c’est : si la branche précalculée n’a pas plus d’auteurs, alors elle est rejetée.

Mais si les attaquants n’ont calculé aucun bloc récemment (disons qu’ils ont patienté pour sortir de la fenêtre d’auteurs), alors ils sont nécessairement des nouveaux auteurs. Donc s’ils ont suffisamment de puissance, leur branche sera prioritaire et ils pourront forcer le switch.

Cela reste une attaque momentanée, avec effet dans le temps de la fenêtre d’auteurs. Et donc plus celle-ci est large, plus réitérer l’attaque devient longue. Aujourd’hui cette fenêtre est définie comme 5*nombre d’auteurs. Donc si l’on est 116 auteurs, ça signifie une une fenêtre de 2 jours => une attaque possible tous les 2 jours, le temps de sortir de la fenêtre et devenir nouvel auteur. Disons que je ne trouve pas cela très gênant, pourquoi pas.

Mais est-ce vraiment plus souhaitable qu’un simple algo +xblocks/+xmedianTime, tels l’algo 3-3 d’aujourd’hui ?

C’est intéressant, mais alors qu’est-ce qu’on privilégie :

  • le nombre d’auteurs, favorisant une “attaque” de tous ceux qui calculent épisodiquement ou qui se font pirater leur clé
  • les vieux auteurs : on favorise la branche où l’on a un maximum de blocs d’auteurs réguliers

Car si dans les 2 cas on a 1 auteur = 1 vote, on n’a pas du tout le même résultat à la fin !

Ce que je voulais dire c’est que pour le moment, j’ai tendance à privilégier la vue réseau. (grâce a un système de cache)
Où l’on sélectionne le fork qui a le plus de nœuds membre branchés dessus.

Dans ce cas, pour réaliser l’attaque, il faut donc pirater autant de clef membres qu’il y a de calculateurs avant l’attaque sur le réseau +1.

PS: Il y a probablement des facteurs facilitant cette attaque, si l’on arrive à faire splitter le réseau avant de réaliser l’attaque, par exemple, grâce à un mécanisme d’émission de 2 blocs valides différents (avec le même numéro) à 2 extrémités du réseau.
Mais comme on a une bonne vue du réseau, le commerçant pourrait alors attendre que le réseau se stabilise pour que celui-ci considère la transaction valide.

il y a peut-être d’autres solutions encore meilleures, je cherche…

C’est aussi ça la difficulté qu’on a : est-ce qu’on privilégie un algo de résolution de dérivée première, la blockchain, ou de dérivée seconde, la vue réseau ?

On peut faire l’analogie avec l’allure d’une voiture : sa vitesse est l’équivalent de notre blockchain (une distance par rapport au temps, l’une en km l’autre en blocs) et son accélération l’équivalent de notre vue réseau (une variation de la distance).

La vitesse est une donnée qui varie de façon à peu près constante, tandis que l’accélération peut être vraiment brutale (des nœuds qui changent de HEAD comme de chemise par exemple, surtout s’ils le basent eux-même sur le HEAD des autres nœuds qu’ils voient).

Il faut déjà savoir si l’on veut se baser sur l’une ou l’autre. L’accélération a cet avantage d’une résolution possiblement rapide mais cet inconvénient d’avoir un système possiblement explosif, si le contrôle-commande se base et influe lui-même dessus. Tandis que la vitesse a cet avantage d’une forte stabilité, mais cet inconvénient d’une résolution plus lente.

Me semble-t-il.

1 « J'aime »

Tu as bien sûr raison.

Supprimons la POW personnalisée alors… :cry:

Ou peut être un subtil mélange des 2, la blockchain et la vue réseau.

Ou encore un tout autre mécanisme autre que la POW.

Ou l’on ignore simplement le problème, et au commerçant d’attendre suffisamment de blocs pour se sentir en sécurité (relatif au nombre de membres et au montant engagé )

Il y a encore plein de solutions imaginables, je ne m’en fais pas !

Je ne comprends pas trop le point que tu évoques ici. On est aujourd’hui 12 à calculer la chaine. Il faut que les attaquants soient plus de 12 et précalculent une nouvelle chaine plus vite que le réseau.

Tu pars ici du principe que l’attaquant est capable d’avoir plus d’une centaine de clés valides. Si c’est une menace qu’on juge plausible, ce n’est pas simplement cette attaque qui est envisageable mais carrément la prise de contrôle du réseau…

L’algo se basant sur les clés permet justement de ne pas se baser sur la puissance de calcul du tout, mais simplement sur les clés des utilisateurs.

1 « J'aime »

Déjà pas besoin de pré-calculer : tu peux partir d’un bloc précédent. Ensuite il leur suffit d’être au moins 6 si l’on parle du cas 2. “rolling back de 6 blocs” où ces individus provoquent un fork de la chaîne. Et ce indépendamment du nombre d’auteurs actuels. Il leur faut tout de même au moins autant de puissance que le reste du réseau.

Non non, cf ma réponse ci-dessus.

1 « J'aime »

De toute façon si un attaquant pirate un nombre de clé membres plus grand que le nombre de membres légitimes qui écrivent des blocs il prendra le contrôle de la monnaie dans tout les cas, ce cas là me semble donc incongru.

Oui moi aussi mais a condition que la manière de calculer le nombres de calculateurs sur une branche se base sur le nombre d’issuers de cette branche et pas sur le head de leur noeud membre car celui ci peut etre très instable et notre vision du réseau peut etre très partielle, alors que notre vision du contenu de la branche évaluée est forcément correcte, au pire elle sera trop courte (la vrai branche a avancée de plus de bloc que ce que l’on a en mémoire), mais dans ce cas on finira par recevoir ces blocs et donc par réévaluer cette branche :slight_smile:

Ce principe n’est effectivement valable que dans le cas avec pow. Sans pow la longueur d’une branche ne doit pas être un critère de sélection. ce qui est d’ailleurs le cas dans mon algo.

Oui exact c’est une excellente amélioration, je note vais actualiser ça :slight_smile: .

Justement non, car le champ issuerCount est basé sur la fenêtre courante et cette fenêtre courante ne commence pas a la bifurcation, de plus cette notion n’a plus de sens sans pow. Il faut vraiment lister et recenser l’issuer de chaque block de R+1 jusqu’a H, c’est un point fondamental.
Et il ne faut pas mélanger les problèmes comme dirai Stéphane, issuerCount et la fenentreCourante, c’est pour la diff. perso, pas pour la résolution des fork !

Il ne pourront le faire que pour un point de bifurcation proche du head de la branche principale, c’est a dire seulement pour un rolling back faible, et c’est justement ce point qui est fondamental, ce qu’on cherche c’est la stabilité du réseau, dont il faut que plus un fork demande un rolling back important il soit “difficile” d’y switcher.

Face aux attaques a rolling back faible il faut effectivement envisager une protection supplémentaire, je suis en train d’y réfléchir :slight_smile:

Je suis convaincu que oui. Car avec ton nouvel algo 3-3 on peut (comme avec l’ancien algo) se retrouver piéger en ping-pong entre deux branches, dont tantôt l’une dépasse l’autre, et ou certaines nœuds switchent sur une branche pendant que les autres nœuds switches sur l’autre et on se retrouve dans un cycle infini. D’autant plus quand la vision réseau est très partielle. Je pense que le seul moyen d’assurer une stabilité dans un contexte de vue réseau partielle (ce qui est plus réaliste) c’est de se baser sur le contenu des blocks pour choisir la branche a suivre.

Ça fait dépendre le choix de la branche de la vue que l’on a du réseau, qui vas beaucoup changer le temps que l’on se fasse la vue complète, et surtout avec des nœuds menteurs ça peut être la pagaille totale, je pense qu’il faut partir du principe que le head d’un nœud membre n’est ps une donnée fiable, seul la signature d’un block l’est !

1 « J'aime »

Elle commence au bloc juste précédent (HEAD~1) et finit plus loin (HEAD~(1+tailleFenetre)).

Mais surtout, tu parles du cas sans PoW ? Je croyais que c’était un cas pour dans 10 ans ! Tu as déjà un truc en préparation ?

Oui mais justement çà n’est pas adapter a la résolution de fork ça. Ce qu’on veut étudier c’est la plage de blocks R+1:H, je ne comprend pas pourquoi tu veut appliquer le fenêtre courante ici, c’est un concept qui sert a la pow et qui ne doit pas servir a la résolution des fork !

Je parle des deux, avec ou sans pow les problemes de résolution des fork sont souvent les mêmes, il y a quelques différences mais je précise toujours quand je parle d’un cas spécifique :wink:

Je prépare un algo un peu plus formel oui, et ensuite j’aimerais coder un simulateur qui teste l’algo en simulant des faux nœuds hein, pas des vrai nœuds duniter, je n’ai pas le niveau pour ça.
Actuellement je suis sur d’autres projets donc ce ne serait pas avant plusieurs mois mais si les simulations sont concluantes pourquoi pas coder un duniter_pop basé sur la PoP. Seulement je n’ai pas envie de me lancer dans un aussi gros chantier si le concept n’est pas solide et approuvé par plusieurs dev maîtrisant bien le sujet. C’est pour cela que j’en parle activement, je ne me lancerai dans le développement de cette idée que si vous l’approuvez majoritairement ! Et si tel est le cas alors c’est plutôt l’affaire de 2 ans que de 10 ans :slight_smile:

Et en quoi ce concept « ne doit pas » servir à la résolution, tandis que le n° de bloc oui ? Pourtant ce dernier concept n’a pas été pensé pour la résolution en particulier et tu l’utilises bien.