Dans le cadre de fyyg j’ai cherché de nouveaux algorithmes de consensus basé sur un ensemble d’identité uniques (ce que produit la toile de confiance), et une proposition me semble tout à fait utilisable sur Duniter sans introduire beaucoup de code. Il fait toujours appel à une preuve de travail uniquement pour assurer un temps constant entre les blocs, mais celle-ci peut être entièrement supprimée si ce temps constant n’est pas voulu ou qu’une autre méthode “d’attente” est trouvée.
Chaque membre possède une clé publique P, et le bloc 0 (ou le premier à passer à cet algo) possède un nonce N
On calcule pour le nouveau bloc N = SHA256(previous N)
Chaque membre peut calculer la “distance” D = SHA256(P | N) (où | est la concaténation, pourrait être remplacée par P xor N pour travailler avec des variables de taille fixe). Cette étape permet de “mélanger” les membres. (pour limiter de trop grands écarts de distances on pourrait utiliser log(D) ou similaire)
Plus D est petit, plus le bloc est privilégié. Si un noeud voit arriver plusieurs blocs concurrents, il prendra le bloc avec D le plus petit.
Pour éviter de pouvoir proposé un D plus petit pour des blocs passés, on définit une fonction prenant en compte la distance du bloc courant ainsi que ceux passés, et donnant moins d’importance aux D au fur et à mesure qu’ils sont passés. On pourrait inscrire dans le bloc la “distance cumulée” C comme C = a * previousC + b * D, a et b étant des réels compris entre 0 et 1; a controlant “l’atténuation” des distances passées et b le poids de la derniere distance, et pouvoir déterminer après X blocs quel fork à la plus petite distance cumulée.
Avec un petit programme ou un tableur on pourrait trouver des valeurs de a et b pour lesquelles les forks sont résolus en un nombre acceptable de blocs X, nombre de blocs qu’il faut attendre pour être sur que sa transaction est confirmée.
Pour le temps en blocs, soit
on garde une preuve de travail définissant un interval fixe. En regardant la distance maximum dans une fenetre de bloc, un membre ayant une distance trop grande peut ne pas faire de preuve de travail, sachant qu’il y a très peu de chance qu’elle soit utile
on garde une petite preuve de travail de quelques secondes pour éviter les spams, on a un temps entre chaque bloc petit et variable, mais en utilisant les dates inscrites dans un “grand” nombre de blocs précédents on peut quand même approximer la date courante. Avoir un temps inter-bloc plus court ne sera pas un problème avec l’utilisation des arbres de Merkle (Duniter 1.7 ?) qui permettra de ne pas stocker l’historique.
on trouve une autre technique “d’attente”, comme par exemple demander à un certain nombre de membres aléatoires de signer à leur tour le bloc issu s’il est valide, utilisant ainsi la latence réseau pour retarder le bloc (et en ajustant le nombre de membres pour obtenir le temps voulu en moyenne). (augmente la taille des blocs et demande du temps pour vérifier les signatures, mais peut-être que d’autres auront de meilleures idées)
Enfin, il faut inciter les membres à ne pas produire des blocs sur plusieurs forks en même temps. En effet, puisque le nonce ne dépends pas du contenu du bloc, il sera le même sur n’importe quel fork pour un bloc de même id. Si on reçoit 2 blocs différents de même id signés par le même membre (peut importe les forks), on peut inclure ces 2 en têtes dans un bloc suivant et “banir” le membre de l’algorithme pendant un certain nombre de blocs. (vu qu’il n’y a pas de recompense de bloc, je ne vois pas comment inciter autrement un membre à coopérer ) Cette inclusion d’un double bloc pourrait aussi être faite par un autre membre dans un bloc de même id, qui aurait alors un bonus. Ainsi, quelqu’un qui propose 2 blocs concurrents avantagerait avantagerait les autres membres, faisant que ses blocs ont peu de change de faire parti du consensus. (peut-être que ça retirerai le besoin de le banir, mais je ne suis pas sur)
Merci d’avoir lu, et n’hésitez pas à donner votre avis ou des suggestions d’améliorations.
Haha c’est trop fort je réfléchissais justement ces jours-ci a une possibilité d’élection pour remplacer la PoW suite a ce que j’ai lu sur la crypto Ark que @poka m’a fait découvrir
Concernant le temps étant donné, qu’on ne signe que le inner_hash + nonce, le temps de signature ne varie pas avec la taille du bloc
mais si l’on part sur un intervalle très court entre deux blocs ce qui va devenir significatif c’est le temps de validation du bloc, et ça ce sera fortement variable selon al taille du bloc.
Plutôt que de forcer un calcul de quelque chose qui prendrais du temps on peut aussi ne plus fixer d’intervalle fixe entre deux blocs, et faire confiance en le fait que la majorité des nœuds membres ne mentent pas sur leur horloge . Il faudrait dans ce cas repasser a la médiane pour être robuste aux attaques de faux timestamp et sur une intervalle contenant beaucoup d’issuers différents, par exemple sur la fenêtre courante.
On pourrait d’ailleurs conserver les concept actuel de fenêtre courante et de difficulté personnalisé, on utiliserai alors la difficulté personnalisée comme un coefficient qui diviserai le “poids” de la distance de l’issuer correspondant, ainsi on forcerai davantage la rotation (car si des échantillons de petite taille le hasard n’est pas assez rotatif).
Le point génial c’est ton idée de pondérer le poids des distance des blocs passés et de faire un algo de fork basé sur la branche ayant la plus petite distance cumulée, ça me plaît beaucoup et me redonne l’espoir de voir un jours un Duniter sans PoW
Le problème que j’exposait était que si on se base sur la latence réseau pour avoir un temps d’attente, si on veut obtenir plusieures secondes il faut passer par un certain nombre de membre, chaqu’u ajoutant sa signature qui devra être vérifiée par tout le monde ensuite.
Pour fygg, je me demande s’il ne serait pas possible d’insérer la date avec un oracle, empêchant ainsi les faux timestamps. Sinon mon problème n’est pas celui de l’horloge (il suffit d’interpoler avec plus de valeurs), mais bien le fait que les blocs peuvent s’enchaîner aussi vite que possible, ce qui fait que des ordis puissants pourraient émettre des blocs plus vite que les ordis moins puissant puisse vérifier. Si on rajoute un temps à peu près constant et assez grand pour permettre à tout noeud de recevoir et vérifier plusieurs blocs concurrents, alors le problème est reglé, d’où l’idée d’utiliser la latence réseau en demandant des signatures de membres aux hasard (a nouveau via ce système de distance).
Pourquoi pas au vu du peu de nœuds calculateurs que l’on à, mais quand le nombre augmentera je ne pense pas que ça sera nécessaire.
Et j’en ai absolument besoin pour que fygg soit agnostique de tout algorithme de preuve de travail qui ne pourra jamais être plus optimisé dans une VM qu’en natif. Sans PoW, il pourrait être possible d’avoir un protocole unique pour n’importe quelle blockchain fygg, peut importe si elle modifie l’algo proposé tant qu’elle ne fait pas appel à du code spécifique “non commun”.
Se baser sur le réseau pour quoi que ce soit me semble être une très mauvaise idée. En plus cette proposition engorgerai fortement le réseau inutilement, on en a pas besoin, je m’explique plus bas.
Il faut partir du principe que la majorité des nœuds membres (plus de 50 %) sont légitimes et agissent de bonne foi. Ainsi il est tout a fait possible de fixer un intervalle de temps et de dire au noeud de calculer des nouvelles distances (avec son nonce) jusqu’a ce que le temps soit écoulé pour lui. Exemple.
Le noeud reçoit un bloc, a une date t1 qu’il relève.
Il vérifie toute les règles du protocole sur ce bloc ce qui prend un certain temps.
Une fois qu’il a validé et empilé le bloc, il génère le nouveau ce qui prend encore un certain temps.
Alors la il peut mesurer la durée écoulée depuis t1, si elle est supérieure ou égale a l’intervalle cible alors il envoi la distance avec le nonce zéro. Sinon on calcule des distances de bloc jusqu’a ce que l’intervalle cible soit écoulé puis on envoi le bloc avec la plus courte distance.
Avec cette solution, c’est bien chaque bloc local qui vérifie l’intervalle de temps avec son propre temps local. Donc t1 est le temps local de réception du bloc, pas le temps inscrit dans le bloc !
Les nœuds menteurs peuvent tricher envoyant leur nouveau bloc sans attendre que l’intervalle soit écoulée, d’où l’importance de maintenir un processus de difficulté personnalisée pour donner un handicap a ces nœuds la, afin de permettre aux nœuds de faible puissance d’avoir le temps de traiter les blocs.
Avec la règle du tiers exclu, si au moins les deux tiers du réseau respectent l’intervalle de temps cible on est bon
Par BlockID un membre n’a qu’une seule distance par rapport a l’objectif commun (que j’ai appelé nonce) qui est calculé uniquement a partir du nonce précédent. Il ne peux pas “calculer de nouvelles distances”. S’il le peut avec un nonce qui influe sur sa distance, alors c’est une preuve de travail, car il va essayer plein de possibilités avant d’en trouver une qui marche.
Par contre si l’on suppose plus de 50%+1 des membres sont honnêtes alors on peut les laisser gérer par eux même un temps d’attente. Pas besoin de faire des calculs pour ça, pas non plus besoin d’exploiter la latence réseau ni de difficulté personnalisée.
Cependant même si elle n’est pas utilisée pour Duniter je pense que la latence réseau est une idée a creuser pour des blockchain sans bijection individu-clé et qui utiliserait une proof of stake, la stake agissant comme un facteur sur la distance calculée (de manière logarithmique pour qu’il faille être posséder de plus en plus de stake pour gagner de moins en moins).
D’ailleurs, les noeuds honnetes pourraient volontairement attendre plus longtemps si les blocs précédents étaient trop rapide pour équilibrer les timestamps et permettre au reste du réseau de rattraper un éventuel retard. X% du réseau honnête signifie X% des blocs avec un temps d’attente correcte, qui peut compenser le pourcentage malhonnête jusqu’a un certain point (mais la ce ne sera plus seulement le temps interbloc qui posera problème je pense).
Edit : par contre avec ce système il faudra un rythme de blocs plus soutenus, vu que ils y aura des forks à chaque bloc et qu’il faudra alors attendre plusieurs blocs pour être sûr que la transaction est passée. Après je pense qu’un petit gain de vitesse ne serait pas une mauvaise chose pour la G1, payer sans confirmation c’est pas top et attendre 5 mins (voir plus) au comptoir ça ne l’est pas non plus x)
) Cette inclusion d’un double bloc pourrait aussi être faite par un autre membre dans un bloc de même id, qui aurait alors un bonus. Ainsi, quelqu’un qui propose 2 blocs concurrents avantagerait avantagerait les autres membres, faisant que ses blocs ont peu de change de faire parti du consensus. (peut-être que ça retirerai le besoin de le banir, mais je ne suis pas sur)
