Abandonner la preuve de travail grâce a la toile de confiance?


#1

La preuve de travail est actuellement la méthode la plus éprouvée et la plus efficace pour obtenir un consensus entre plusieurs machines ayant toutes les même droits d’écriture, ce qui permet donc la création de systèmes non-pyramidaux (nommés aussi holomidaux).

Mais la preuve de travail à aussi de nombreux inconvénients, dont la course au calcul que nous contournons dans Duniter grâce a un système de difficulté personnalisée. Difficulté personnalisée indispensable sans laquelle un membre propriétaire d’une très grosse ferme de calcul pourrait prendre le contrôle total de la blockchain et donc de la monnaie.

Cependant nous disposons d’un outil incroyable que les autres projets avec blockchain n’ont pas : une toile de confiance intégrée. Et il me semble que grâce a cette toile de confiance nous pourrions créer un protocole de synchronisation des données sans preuve de travail.

C’est en réfléchissant sur le projets de nouvelle API WS2P hier que m’est venu c’est idée folle, sauf que plus je l’analyse plus elle me semble applicable :

Le besoin c’est d’avoir un processus déterministe qui fixera qui sera l’écrivain du prochain block, afin que tout les noeuds du réseau suivant ce même processus soit forcément d’accord entre eux, et donc synchronisés.

Voici l’idée d’algorithme qui m’est venu :

C’est un algorithme pour lequel chaque nœud membre aurait 2 types de HEAD : le HEAD de sa chaîne locale et le HEADp d’un bloc pending qu’il soumet au réseau.

Chaque nœud chercherai d’abord a se construire une vision complété du réseau (possible a seulement 3 degrés de profondeur d’après les discutions sur le thread WS2P), puis lorsqu’il a connaissance de l’ensemble des HEADp soumis au réseau il en sélectionnerai 1 et un seul selon le processus déterministe suivant :
Si tout les HEADp correspondent a des membres ayant déjà écrit au moins 1 bloc :
choisir le HEADp du membre dont le numéro du dernier bloc écrit est le plus faible
Sinon
Sélectionner parmi les membres n’ayant jamais écrit de block ceux dont la date d’entrée dans la toile est la plus récente et choisir parmi ces membres celui dont la clé publique est la plus “petite” dans l’ordre alphabétique.
Si le membre sélectionné a soumis plusieurs HEADp différents, choisir celui dont le hash est le plus “petit” dans l’ordre alphabétique.
Vérifier la validité du block correspondant au HEADp finalement retenu. Et s’il n’est pas valide tester avec le 2ème HEADp puis le 3ème (donc il faudrait stocker par exemple les 5 ou 10 HEADp les mieux classés)

L’atout majeur de cet algo c’est que pour un groupe de HEADp donné on en arrive toujours a la même conclusion.
Et donc en cas de fork, le noeud duniter peut lorsqu’il détecte un autre branche dont le HEAD est mieux classé que le sien selon cet algo, switcher automatiquement sur cette branche là, et donc naturellement tout les noeuds swithceront sur la même branche.
Plus besoin de critère comme le nombre de blocks d’avance ou quoi, c’est sur le contenu de la branche elle même que la sélection se ferai :slight_smile:

L’idée c’est qu’au lieu de passer 5 min a calculer, les noeuds qui estiment avoir une chance d’être sélectionnes soumettrais tous leur HEADp au réseau (qui correspondrait au numéro-hash d’un block au meme format qu’actuellement sans le champ nonce, donc générer sans délai).
Puis les nœuds qui n’ont pas de soumis de HEADp sectionnerait parmis les HEADp qu’il ont reçu le mieux classé, vérifierai la validité du block correspondant, et s’il est valide propagerai ce seul HEADp (inutile de faire rebondir les HEADp moins bien classés ils flood le réseau pour rien).
Et si aucun HEADp n’est soumis car tout les nœuds actifs estiment avoir écrit récemment, il pourrait au bout d’une certaine durée sans recevoir de HEADp (par exemple 4min) décider de baisser la limite et donc de soumettre le leur.

Il reste un problème de spam a gérer :
Un même membre pourrait soumettre plein de HEADp différents a différent nœud du réseau pour empêcher la monnaie de fonctionner, il faut donc que tout les HEADp soumis soit systématiquement signés par le nœud membre qui le soumet ce qui permettrait d’avoir une preuve incontestable du nombre de HEADp différents soumis par un même membre.
Le protocole pourrait alors fixer que si un nœud récolte plus de 10 HEADp différents d’un même membre il écrit cette preuve en blockchain et l’écriture de cette preuve entraînerai de facto l’exclusion du membre concerné pour 500 blocs. (Les valeurs 10 et 500 sont adaptables, ce sont des paramètres libres a choisir).

Il y aussi la gestion du temps : afin de garder un temps régulier entre deux block l’on pourrai imposer qu’un nouveau HEADp ne peut être soumis que s’il fait avancer medianTime d’au moins 4 ou 5 min, ce que laisserai des trou ou le réseau serait inactif dans ce domaine et ou la charge serait assignée a la gestion des requêtes de l’API publique (BMA puis future api client?) ainsi qu’a la résolution des fork, (tien ce nœud est sur une autre branche et le point de bifurcation correspond a un bloc plus prioritaire que le mien d’après l’algo si-dessus -> je switch sur sa branche).

Pour éviter des rolling back trop long (genre dépiler 300 blocs…) il faudrait que les nœuds duniter légitimes (cad qui ne contiennent pas de code modifié) se refuse a empiler un block supplémentaire tant qu’il ne se sont pas fait remonter la vision du réseau à profondeur 3 selon le process décrit par cgeek pour l’api WS2P.

Et pour les nœuds miroirs ils pourraient décider de ne pas empiler de bloc supplémentaire tant qu’il n’ont pas reçu les HEAD de tout les blocs membres qu’il connaissent et qui sont UP ou l’ont été dans les 5 dernières minutes.

Il y a sans doute d’autres petits problèmes techniques d’implémentation mais là n’est pas la question pour le moment, la question est de savoir est ce que j’ai louper un point théorique fondamental qui fait que ça ne peut pas fonctionner ? Et si oui merci de m’expliquer en détail lequel, par ce que j’y est réfléchi toute la nuit en franchement je ne voit rien qui soit insurmontable.

Si je ne me trompe pas, alors cela signifierai que nous pourrions avoir un consensus absolu dans un réseau duniter sans qu’il n’y est aucun centre ni aucune preuve de travail, ce qui serait considérablement plus écologique, et permettrait a de simples téléphones d’être des nœuds du réseau !

Peut-être qu’il existe déjà des concepts similaires mais je n’ai rien trouver de semblable sur internet, je pense qu’il y a deux barrières fondamentales qui empêchent les gens qui réfléchissent a ces sujets d’avoir cette idée :

  1. Ils n’ont pas de toile confiance intégré et ne projette pas d’en mettre en place.
  2. Ils restent bloqués dans la croyance que l’écriture d’un block doit être accompagnée d’une “récompense” ou/et d’une “création de monnaie”.

Si’l faut donner un nom a cet algo, je proposerai Preuve de Patience (PoP), car c’est le membre le plus patient (celui qui n’a pas écrit depuis le plus longtemps) qui est retenu.


Block issuance distribution
Difficulté personnalisée minimale
Difficulté personnalisée minimale
#2

Tu aboutis grosso-modo à un algorithme de vote tel que je l’avais imaginé à mes débuts de uCoin, en bien plus avancé toutefois je dois bien l’avouer :slight_smile:

Alors avant de discuter de cet algo, je voudrais juste rappeler les points les plus essentiels auxquels j’ai dû faire face à cette époque dans le cadre d’une chaîne de blocs et qui m’ont fait sélectionner la preuve de travail :

  • sélectionner l’instant d’écriture : c’est être capable de se mettre d’accord sur le moment physique où un nouveau bloc doit être ajouté.

Première difficulté : il est tout sauf évident de se mettre d’accord sur l’heure courante : car au-delà de toute considération de physique relativiste (on suppose ici un fonctionnement sur référentiel galiléen), toutes les machines n’ont pas précisément la même horloge à la seconde près, parfois on a carrément des minutes de décalage (je constate régulièrement 1 minute de décalage entre 2 smartphones pourtant identiques).

Alors comment se mettre d’accord sur le fait qu’il faut émettre un bloc toutes les 5 minutes, si déjà soi-même on a très certainement des décalages de 1, 2 ou 3 minutes avec de nombreux nœuds ?

  • sélectionner qui parle : déjà il faut définir qui est ce « qui », c’est-à-dire l’ensemble des éléments qui ont le droit de causer (cela n’a rien d’évident : sont-ce juste ceux que je vois sur le réseau, ou est-ce plus large ?), et ensuite parmi ceux-là il faut gérer les nombreux cas qui peuvent se produire pour chacun : est-ce que tout cet ensemble a parlé ? que se passe-t-il si un élément a dit plusieurs choses à la fois ? que faire s’il est à la bourre pour parler, alors qu’il était le plus légitime ? et qu’arrive-t-il si un élément encore plus légitime arrive quelques secondes plus tard ? quelques secondes plus tard par rapport à l’horloge de qui ? et en cas d’égalité ? et en cas d’un mec à la bourre qui arrive juste après le calcul de l’égalité ?

Alors voilà, je crois que ce sont les 2 problèmes à résoudre. Tout le reste est du détail.

Duniter solutionne ces problèmes de façon extrêmement efficace car grâce à la preuve de travail, car il n’y a le plus souvent qu’un seul point de l’espace-temps qui agit : c’est celui qui a trouvé une preuve valide. Et donc :

  • sélectionner l’instant d’écriture : l’instant est sélectionné de fait lorsqu’un bloc valide arrive
  • sélectionner qui parle : l’élément est sélectionné de fait lorsqu’un bloc valide arrive

Le bloc venant de la preuve de travail est une sorte de sémaphore spatio-temporelle. Vous ne vous rendez peut-être pas compte, mais c’est un truc vraiment très, très, TRÈS fort ! Et ce n’est pas moi qui l’ai inventé, hein ! Bitcoin m’a révélé cela.

Alors face à cette problématique, les points qui me paraissent vraiment délicats dans la PoP (Proof of Patience) sont :

  • l’assurance que les nœuds ont bien, à quelques secondes près, la même heure pour sélectionner l’instant d’écriture
  • l’assurance que tout nœud voit bien l’ensemble des participants pour l’écriture du prochain bloc (que faire s’il en manque 1 par exemple ? que faire si finalement il se pointe ?)

Je ne dis pas que c’est mission impossible, mais ça me paraît franchement coton.


#3

Merci pour ta réponse détaillée :slight_smile:
J’avais déjà connaissance de ces problèmes de temps et de “qui parle” mais j’ai l’impression que ce sont en fait des faux problèmes.

En fait je pensais garder le même système de temps qu’actuellement, c’est à dire que le temps resterai le temps moyen des 24 derniers blocks.
Seulement en imposant par une règle du protocole qu’un nouveau bloc ne peut être valide que si sont medianTime est supérieur de plus de 5 minutes au medianTime du bloc précédent, la génération de bloc étant immédiate sans prevue de travail, les nœuds soumettrons leur block des qu’il le pourront, et donc nous aurons bien en moyenne un bloc toutes les 5 minutes :slight_smile:
Quand a temps exact qui l’emportera, et bien c’est la valeur du champ medianTime du nœud qui a générer le block dont le HEADp est finalement retenu c’est tout.
Il n’est pas nécessaire que tout les nœuds ce mettent d’accord sur l’instant d’écriture, mais ils doivent se mettre d’accord sur l’écriture de la même donnée afin d’avoir tous la même blockchain, et effectivement ce mettre d’accord sur l’avancer du temps commun pour la création du DU, d’ou l’idée d’imposer qu’un bloc en pourra etre retenu que s’il fait avancer medianTime d’au moins avgGenTime secondes.
Ainsi si la blockchain a avancée trop vite le réseau sera bloqué jusqu’a ce que suffisamment de temps passe, ce qui empêchera la blockchain d’avancée trop vite indéfiniment.

La aussi ce n’est pas une nécessite, c’est justement le rôle de l’algo de résolution des fork que de mettre a jour la branche locale du nœud s’il reçoit plus tard un HEADp plus prioritaire. Comme il y a un nombre limité possible de HEADp par membre il arrivera forcément un moment ou l’on ne recevra plus de nouveau HEADp.
Et au cas ou un membre n’ayant jamais calculé propose soudainement un HEADp pour un bloc qui est 300 blocs en arrière on peut ajouter une contrainte qui est de ne rolling back sur plus de 6 blocs que si l’on trouve au moins X nœuds membres qui ont intégré ce nouveau HEADp, donc personne ne l’intégrera.
X pouvant être le CEIL d’une proportion du nombre d’écrivain sur les dtDiffEval dernier blocs, par exemple 15%.

Les problèmes que tu énonce ne sont donc pas insurmontables, après il est vrai que c’est peut être plus difficile a coder, mais je ne dit pas qu’on doit le faire, je dit juste que sans preuve de travail c’est possible et que c’est mieux, et si tel est la cas alors j’ai bon espoir que ça finira par être développer un jours :slight_smile:


#4

Je ne suis pas vraiment inquiété par ce qui est inscrit dans la blockchain. Oui les histoires de time et medianTime fonctionneront tout pareil.

C’est un point que je vois comme délicat : en réalité n’importe quel membre dont le dernier bloc est “vieux” peut faire pointer quand il veut un nouveau bloc, et ce sans même attendre “5 minutes” avant de le soumettre. Et un autre qui sera dans des conditions similaires (vieux bloc encore plus prioritaire) pourra faire soumettre un bloc sans attendre. Il est alors compliqué de faire émerger un consensus clair.

Non bien sûr ils ne sont pas insurmontables, disons que je les trouve plus difficile à résoudre dans le cadre d’un réseau dont on ne peut pas avoir confiance et qu’on ne maîtrise pas.

Mais encore une fois, peut-être que je me trompe. Notamment, entre “aucune confiance” et “une confiance totale” il y a une infinité de nuances, et on peut penser que la toile de confiance nous éloigne quand même fortement du “aucune confiance”.

Bon bref, je laisse d’autres te répondre, je suis trop dans le guidon pour apporter des réfutations correctes.


#5

C’est très long donc je ne pourrais pas répondre avant la semaine prochaine le temps de digérer tout ça.

Quelques premiers éléments :

Sur la PoW et la blockchain

Je voudrais faire remarquer que ça ressemble au proof of stake sur le principe : https://en.m.wikipedia.org/wiki/Proof-of-stake . Pas de PoW et prochain écrivain qui dépend de l’âge des coins + montant du compte.
Il faudrait voir comment font NxT ou Peercoin dans la pratique pour faire fonctionner ça. Ou voir côté Ethereum, leur algo qui se base sur un consensus type Byzanthine qui ressemble à ce que tu proposes : https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ

Sur la forme de l’algo

Il faut, je crois, absolument éviter les algos qui reposent sur une vue du réseau pour résoudre des forks et créer un consensus. C’est beaucoup trop sensible à la qualité du réseau, demande de maintenir beaucoup trop de connexions, et ouvre plein de biais d’attaques en faisant croire à un noeud ce qu’il voit du réseau, ou en mentant aux autres noeuds sur ce qu’on voit soit-même.

La création d’un consensus se forme parce que pour X blocs donnés, les noeuds sélectionnent l’agancement des blocs suivant les même règles localement au noeud. C’est bien le noeud qui tout seul, décide de ce qu’est pour lui la chaine de bloc. Il ne se base pas sur ce que pense les autres noeuds. C’est très important de rester sur ce principe !

Sur le fond de l’algo

Ya une idée intéressante en tout cas. On peut effectivement, localement à chaque noeud, choisir de manière déterministe le bloc suivant la clé qui a écrit il y a le plus longtemps. Si la clé broadcast plusieurs blocs valide, prendre le bloc dont le hash est le plus petit (c’est un nombre après tout).

Pour le problème du spam, on peut imaginer que dans les blocs, on référence tous les blocs valides (pubkey d’origine + blockuid du bloc + signature du hash) qui ont été ignorés dans la branche sélectionnée. Et que ça fasse baisser le poids du noeud dans la règle de sélection des branches (sous une forme exponentielle, plus un noeud créé des blocs qui “forme des forks”, plus il est puni. C’est ce que fait Ethereum avec ses dunkles)


Pour finir

L’avantage de rester sur un type de fonctionnement sans vote mais avec une sélection du prochain bloc localement au noeud, relativement à la chaine de blocs, c’est qu’on ne s’éloigne pas trop de ce que fait Duniter aujourd’hui (pas de sondage du réseau etc, on se concentre sur la sélection locale au noeud). Ce qui donne une plus forte probabilité à un tel algo d’etre testé un jour tout en étant rétro-compatible facilement :slight_smile:


#6

J’allais mentionner le Proof of Stake, mais je me suis fait doubler :smiley:. Il y a une assez bonne description de comment ils font dans Tezos ici https://www.tezos.com/static/papers/white_paper.pdf (section 3.2).

Maintenant je ne suis pas sûr que se baser sur la quantité de monnaie détenue pour définir la probabilité est dans l’esprit duniter. J’aurais plutôt vu une équi-probabilité, éventuellement pondérée par une fiabilité (ceux qui minent les blocs dans les temps auraient plus de chances d’être sélectionnés).


#7

Tout à fait, ce qui importe c’est l’usage d’une probabilité relativement à une clé publique donnée.

Dans la PoS, ils utilisent une proba sur le taux de monnaie allouée à la PoS sur une clé publique donnée.
Dans une PoP Duniter, on utiliserait une équi-proba sur les clés pondérée par l’age du dernier bloc calculé par la clé.


Article sur la preuve de travail Duniter
De la lecture sur Proof Of Stake
#8

Du neuf sur le sujet ?


#9

Pas à court terme à mon avis. Il y a d’autres travaux de lancés :

  • Stabilisation WS2P v1
  • Développement WS2P v2
  • Développement du protocol v11 (format binaire, meilleure robustesse du protocole, etc)

#10

heu c’est déjà stabilisé ça :sweat_smile:

En revanche il y a aussi :

  • Développement de la nouvelle API Client GraphQL
  • Développement de l’implementation duniter-rs
  • Intégration de wotb-rs dans duniter-ts
  • Passage a node 10 pour duniter-ts
  • et bien d’autres choses encore…

mais au delà de ça @1000i100 on se dirige plutôt dans un premier temps vers une réadaptation de la pow avec un mécanisme de bonus aléatoire et un mode économie d’énergie (merci @Vincent_Rousseau) pour la 1.7.

Donc passer a la PoS ce ne sera pas avant plusieurs années dans le meilleur des cas !


#11

The Network Time Protocol (NTP) is widely used to synchronize computer clocks in the Internet.
https://tools.ietf.org/html/rfc5905
https://fr.wikipedia.org/wiki/Network_Time_Protocol
https://en.wikipedia.org/wiki/Marzullo's_algorithm

Raft is a consensus algorithm ( déjà évoqué sur ce forum )
https://raft.github.io/
http://thesecretlivesofdata.com/raft/ <- pour visualiser :ok_hand:

peut être un petit mix a faire ? :slight_smile:


#12

Le vecteur d’attaque que je vois à la première lecture @elois c’est une attaque via un sybil de la toile de confiance.

Il faudrait inclure dans l’algo qui décide si un membre est prioritaire ou non pour la création d’un bloc le fait qu’il soit ou non éloigné du centre. Ainsi on aurai une certaine légitimité des membres jouant dans les règles de la toile de confiance et on exclurait ceux qui tenterai une attaque.

My 2 Cts, :slight_smile:


#13

Il n’y a pas de centre dans la toile de confiance. Il y a par contre une notion qu’on appelle la “centralité” et que se calcule de plusieurs manière différente selon la définition et l’algo. L’idéalo serait de choisir une définition rapide a calculer (dans la perspective ou c’est un calcul qui doit pouvoir se faire en un temps ,raisonnable même pour plusieursmillions de membres). Je penche plutot pour la Centralité d’intermédiarité (https://fr.wikipedia.org/wiki/Centralité_intermédiaire) qui a l’avantage de pouyvoir sqe calculer très vite avec l’algo d’Ulrik brandes :slight_smile:


#14

On a tout de même notre genesis block qui créé ex-nihilo 56 membres, ces membres ce trouvent de facto au centre de la toile.

Etant les membres créateurs, on peut partir du principe qu’ils sont de confiance, ça rejoint un peu la notion d’ancienneté sur laquelle travaillait @aguy :slight_smile:

C’est drôle comment tout se recoupe parfois.


#15

Non point du tout, certains des 59 membres co-fondateurs ont une centralité très faible. De plus toutes les certifications de la toile du bloc genesis vont expirer le 8 mars 2019, après cette date ce sera comme si la toile genesis n’avais jamais existée, donc non les membres co-fondateurs ne sont pas au centre et le seront encore moins demain, d’ailleurs j’insiste il n’y a pas de centre de la toile, c’est un point fondamental :slight_smile:

Pas plus de confiance a priori que les autres membres, nous sommes soumis aux membres règles, d’ailleurs certains membre fondateurs vont perdre leur statut de membre le 8 mars prochain.


#16

Oui tu as raison, je ne me souviens plus si il peut y avoir continuité dans les certifications (renouveler avant qu’elle expire ?).

Si tous les membres du bloc 0 périmait, est ce que la toile persisterai, j’ai du mal à visualiser ces membres centraux (au moins les premières années en tout cas) devenir non centraux. :smiley:

Autre pensée : sachant que ce sont les membres qui initient la création de la toile, j’ai tendance à vouloir les voir comme une référence, que certains membres, périment, soient absent plusieurs années, puis reviennent, ils existent toujours dans le bloc 0, donc pour calculer une distance au centre, ce point de départ me parait intuitivement bon.

Si les 59 membres sont corrompu, ça ne semble pas changer l’équation ? Libre a eux de mettre des bâtons dans les roue de leur création.

Je divague ^^


#17

Il n’y a pas de centre dans la toile, pas plus qu’il n’y a de centre sur une sphère.

La Toile peut d’ailleurs être positionnée graphiquement aussi bien sur une sphère que sur un plan.

Il se trouve même miraculeusement que le lieu où se trouvent les êtres humains est lui-même une sphère, qui n’a donc pas de centre.


#18

Bien sûr qu’une sphère a un centre qui est le point situé à égale distance de tous les points de la surface de la sphère.
Les humains vivent tous à environ 6 000 km du centre de la Terre (tant mieux car il y fait chaud),
leur lieu de vie est la surface de la sphère.

Je pense que tu voulais dire que la surface d’une sphère n’a pas de centre.


#19

Certes oui.


#20

Techniquement une sphère est déjà la surface extérieure d’une boule (qui elle est pleine et contient donc son centre). #jesuisfunensoirée
SUR une sphère il n’y a donc pas son centre.