Un article survolant l’approche https://bitcoinmagazine.com/articles/interview-cryptographer-silvio-micali-bitcoin-ethereum-and-proof-stake/ et l’article scientifique https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf. Comme un des auteurs est spécialiste des algos byzantins, a inventé les 0-knowledge proofs et a un prix Turing, je pense que cela vaut le coup d’être lu, ce que je vais faire dès que j’ai 5 minutes^W heures.
1 Like
A mettre en lien avec Abandonner la preuve de travail grâce a la toile de confiance?
Je dirai que non, c’est fondamentalement différent même si un peu s’en inspirer 
Notamment on ne peut pas simplement remplacer le poids du solde par le poids WoT, la question n’est pas tant “comment décider quel sera le prochain bloc”, ça c’est une question qui relève de la résolution des fork, et on peut arbitrairement appliquer les règles qu’on veut tant qu’elles mènent a une convergence des nœuds.
Non la vrais question c’est “comment décider QUAND sera le prochain bloc ?”, à cela je n’ai pas trouver de réponse, et il semble que les crypto-monnaies Proof of Stake n’ont pas le souci de mesurer le temps aussi fidèlement que nous, nous on à ce souci pour deux raisons :
- Respecter la fréquence de création du DU
- Respecter les délais d’expiration des actes wot en blockchain (msValidity, etc)
Actuellement le concept de PoP que j’ai proposé répond au premier problème (quel nouveau bloc) mais pas au second (mesure du temps), et j’ai beau chercher mon impression est qu’aujourd’hui il n’existe pas d’autre moyen de mesure du temps que la réalisation d’un calcul, calcul dont le résultat ne doit pas pouvoir être connu a l’avance pour éviter la triche.
La triche sur le temps pouvant être potentiellement critique sur le fonctionnement d’une monnaie duniter : plus de versement du DU, ou versement du DU trop fréquent ce qui transforme la monnaie en monnaie de test…
L’article prétend qu’il n’y a pas de forks possibles, justement. Je suis en train de vérifier cette affirmation.
1 Like
Ça me semble bien prétentieux en effet 
Pour être tout à fait précis, ils disent “que c’est négligeable”.
Le temps fait partie intégrante des blockchains proof of stake à cause des smart contract, donc non, je ne pense pas que ce problème soit ignoré par l’algorithme proposé.
Mais ce n’est pas le calcul qui est utilisé pour mesurer le temps, mais bien le temps inscrit dans le bloc, qui est choisi de manière arbitraire par chaque noeud. Les noeuds honnêtent inscrivent un temps cohérent, des noeuds malhonnêtes peuvent tout à fait mettre la valeur max possible pour accélérer le temps.
2 Likes
Ce qu’on fait déjà dans duniter quoi, mais est ce suffisant ? Je crois que seul l’expérimentation nous le dira.
Oui ce que j’ai décris correspond à ce qui est fait dans Duniter, pour l’algo proposé, j’en sais rien 
Mais j’imagine que le fonctionnement serait assez proche.
Après une après-midi de lecture, mes 1ères impressions.
D’abord pour cette histoire de forks : en réalité il y en a bien. Il y a même tout un paragraphe dessus. Donc à ce niveau là, rien de nouveau sous le soleil : il nous faut quand même un algorithme de résolution de forks en cas de pépin.
Toutefois pour le reste, j’admets avoir été séduit sur plusieurs aspects.
D’abord ils réutilisent des idées auxquelles j’ai moi-même pensé au début de uCoin sans avoir voulu les poursuivre par manque de compétence sur le sujet : notamment la sélection aléatoire de « comité de vote ». Ceci fait appel à une fonction dite « VRF » dont je n’imaginais pas l’existence. Et puis ils vont vraiment loin dans leurs histoires de votes, où fondamentalement l’idée c’est « il est possible de se mettre d’accord sans PoW sous certaines conditions, et en cas de pépin on a une solution de repli », le tout basé des principes qui me semblent acceptables. De sorte qu’on n’est jamais bloqué mais que si vraiment pépin il y a, la résolution de fork permet de mettre un terme aux problèmes. Je note aussi l’idée de résolution par moindre hash, déjà suggéré par Eloïs.
De plus, dans leur implémentation sont utilisés SHA256 et Curve25519, donc a priori les mêmes fonctions que Duniter (j’ai un léger doute quant à la différence entre Ed25519 et Curve25519, mais bon). D’où une compatibilité possible sans effort.
Alors bien sûr il y a encore plusieurs inconnues, j’ai moi-même besoin d’étudier à nouveau leur idée pour détecter les points d’ombre, mais aussi voir où l’on peut introduire la toile de confiance là-dedans car c’est vraiment un atout considérable qu’il serait dommage de ne pas exploiter. De plus cela implique possiblement des modifications du protocole, au niveau du format des blocs.
Mais dans l’idée cela permettrait de libérer la puissance CPU pour faire d’autres choses plus utiles la plupart du temps, tout en permettant d’avoir de nouveaux blocs de façon plus régulière (si fixé à 5 minutes, ça ne sera pas au bout de 20 comme ça arrive aujourd’hui). Aussi, étant donné qu’on n’a pas vraiment besoin de faire confiance à l’émetteur du bloc et aux votants, cela permettrait de concrétiser l’idée des clés déléguées au calcul de blocs sans mettre en danger toute la toile.
Également, je n’aime pas trop cette idée de « Stake » où les plus légitimes sont ceux possédant le plus de monnaie. C’est peut-être un point à revoir. Mais je note quand même que dans leur exemple, la création monétaire = Bitcoin. Tandis que dans le cas d’une monnaie libre, les utilisateurs créent en permanence de la monnaie … et donc l’équilibre monétaire y est bien plus grand ! La probabilité d’accaparement de 20% de la masse totale de monnaie en une entité ou conglomérat hostile y est finalement très peu probable :
En effet aujourd’hui dans la Ğ1 : M = 380.000, N = 339, M/N = 1120. Posséder (20% de M) = 76.000 Ğ1, soit l’équivalent de 67 membres sur 339.
Et quand bien même, cela ne signifierait pas que ce conglomérat soit hostile.
Bref, l’idée est à creuser quand même, à mon avis.
1 Like
Je suis en phase globalement sur ton poste. Mais pour profiter un maximum de la toile de confiance, je serais d’avis de ne pas baser le réseau sur le “stake”. C’est comme la taxation aux transactions qu’on n’a pas voulu implémenter : il ne faut pas mélanger l’aspect technique et l’aspect économique !
Dans cet algorithme, le stake sert à gérer le cas des attaques sybilles. La monnaie est en nombre d’unités limitée, pour participer il faut allouer de la monnaie sur une clé publique donnée. Pour éviter que les utilisateurs dispersent leurs unités sur plein de clés publiques tout en risquant de noyer le réseau, ceux qui allouent un maximum d’unités sur une seule clé publique ont plus de chance d’être sélectionnés en tant que Commitee member ou en tant que Proposeur de block.
Nous, on a la toile de confiance pour gérer les attaques sybilles. Il suffit donc a priori de donner une pondération de égale entre chaque clés publiques membres de la WoT, et l’algorithme me semble utilisable tel quel.
On peut aussi choisir une autre politique, tel que :
- Ceux dont le noeud a été le plus actif récemment ont un poids plus élevés (pour inciter à rester online, ce qui me semble assez intéressant)
- Ceux dont le noeud a été participant récemment ont un poids plus faible (pour s’assurer de faire tourner le vote… mais bon c’est déja aléatoire donc je ne vois pas trop l’intéret
) - etc.
2 Likes
Oui je crois qu’on est plusieurs à penser que le stake n’est pas la bonne voie quand on a la WoT.
Mais je dois encore étudier un peu l’algorithme utilisé actuellement en stake, car il y a une notion de sub-user qui représente chaque unité de monnaie détenue … alors ce n’est pas très clair pour moi, ni comment la WoT peut se placer à ce niveau.
Ensuite oui, on fait bien les règles qu’on veut. On peut établir la priorité sur plein de critères autres que la détention de monnaie.
Comme ça, je dirais que l’équivalence algorithmique est la suivante
- U Algorand = N membres Ğ1
- Que une unité algorand u = 1 individu membre
Oui c’est possiblement cela.
Mais il faut étudier plus encore, car on ne voudrait pas non plus qu’aucun nœud qui tourne réellement ne soit sélectionné.
1 Like
Après réflexion, pour s’aligner sur un équivalent “plusieurs unités allouées par utilisateurs” , il s’agirait plutôt de :
- U = N x 1000
- u = 1000 unité / membre
À vérifier et tester dans un tableur dans un premier temps.
J’ai pas mal étudié Algorand ces dernières semaines, et j’ai même codé 2-3 POCs par-ci par là pour me rendre compte de la viabilité de la chose.
Alors personnellement je vais abandonner cette voie, beaucoup trop sensible à la communication réseau et à la synchronisation des horloges à mon goût. Je trouve finalement le système peu robuste comparé à une PoW sur la partie consensus, car celui-ci demande une participation réseau constante et fiable des membres afin que le système fonctionne. Cela manque de souplesse à mes yeux, j’ai peur qu’un tel système se bloque trop facilement :
- en cas d’attaque réseau
- en cas de fluctuations importantes du nombre de votants (nœuds diurnes, …)
- en cas de bug sur les votes
Alors je peux me tromper, mais je laisse d’autres explorer la piste 
Ces développements n’auront toutefois pas été faits en vain, car j’en retire :
- la découverte d’un mécanisme de tirage au sort très efficace (tirage au sort secret)
- l’implémentation des clés déléguées, qui pourraient voir le jour dans les blocs en version 11
Vous pouvez retrouver les POCs suivants :
- projet d’implémentation d’Algorand en TypeScript : https://dev.cgeek.fr/cgeek/algorand-test
- début d’intégration d’Algorand dans Duniter : https://dev.cgeek.fr/duniter/duniter/commits/algorand
- projet de cryptographie avec fonctions VRF pour NodeJS : https://dev.cgeek.fr/cgeek/vrf-duniter
3 Likes
Autant j’imagine assez facilement l’impact des communications réseaux, autant j’ai du mal à voir celui des horloges système ? Ce temps est utilisé pour le vote ?
L’horloge est utilisée pour attendre un certain temps à chaque étape, mais aussi pour le protocole de récupération.
Par exemple tout participant attend 1 minute ferme pour la réception des blocs avant de faire quoi que ce soit. Il n’y a aucune autre issue que l’attente, pas d’autre déclencheur. Ce qui fait que par exemple si un nœud voyait sa communication réseau coupée pendant 2 minutes puis rétablie, alors il pourrait accuser un retard systématique pour les prochains votes s’il ne fait pas en sorte de rattraper son retard en récupérant les votes existants pour les blocs suivants.
Mais à la limite, ça se gère. L’horloge est surtout critique est cas d’attaque réseau prolongée :
Finally, Algorand assumes loosely synchronized clocks
across all users (e.g., using NTP) in order to recover liveness
after weak synchrony. Specifically, the clocks must be close
enough in order for most honest users to kick off the recovery
protocol at approximately the same time. If the clocks are
out of sync, the recovery protocol does not succeed
1 Like
C’est effectivement je très grosse limitation pour le fonctionnement de Duniter et son aspect “tout à chacun peut participer depuis chez soit”
C’est gênant oui, mais ce qui m’embête le plus c’est vraiment la communication réseau ultra-présente à des instants précis, très régulièrement. Ça demande la concentration d’un ensemble d’événements non-anodins en une période de temps réduite, et de répéter cela à chaque bloc.
Alors bien sûr en cas de pépin il y a le bloc vide. Ça c’est une bonne idée. Mais bon, si c’est pour avoir une blockchain vide, ça n’est pas beaucoup mieux.
Bon bref j’ai perdu mes convictions pour cette solution, c’est trop instable à mes yeux.