Stellar Consensus Protocol


#1

Salut à tous,

comme j’ai une grande sympathie pour le projet duniter je reviens à la charge parce que je ne suis toujours pas bien satisfait de l’architecture technique de ce bazar :wink: (cf mon post sur la toile de confiance). Ce qui me tracasse, c’est que duniter utilise la blockchain et qui plus est la preuve par le travail alors que ces deux choses, bien qu’elles aient pas mal fait avancer les bases de données distribuées, sont du point de vue théorique très mauvaises. Pour rappel, le seul avantage d’un système blockchain, c’est qu’il est très bien distribué mais il ne fournit pas:

  • de la consistence forte, c’est à dire la garantie que tout le monde voit la même chose au même moment et donc de fait la certitude qu’une transaction est bien enregistrée
  • des temps d’attente et une consommation de puissance de calcul raisonnables (quelle que soit la manière dont l’utilise duniter, je sais comment ça marche)
  • le fait de pouvoir décider nous même en qui ont a confiance

Il y a peu de temps je suis tombé sur stellar qui est un nouveau protocol de consensus (SCP). Il y a une chose que j’aime bien au premier abord: contrairement à quasiment toutes les dérivées de blockchain, ce protocol est développé en lien étroit avec le milieu académique, qui se penche sur ces questions de consensus byzantins depuis très longtemps (~1980 avec paxos) (David Mazières est plutôt une pointure de l’informatique théorique). J’ai pas mal potassé le whitepaper, s’il y en a que ça motive, c’est lisible, même si ça aide beaucoup de connaître un peu le fonctionnement de paxos (ou de raft, plus simple).

Concrètement, Stellar est un système de cryptomonnaie, mais il est basé sur SCP, qui est un protocol de consensus générique, qui pourrait donc servir à décentraliser n’importe quelle base de donnée (les DNS ou encore les CA racines!). SCP n’utilise absolument pas les même concepts que la blockchain et ne dépend donc pas de la preuve par le travail (ou de n’importe quelle preuve d’ailleurs) et permet de gérer efficacement une vraie base de donnée (pas juste une suite de blocs, on doit pouvoir faire nativement une key-value store ou une base de donnée SQL). La principale idée qui permet de se passer de PoW et de couper l’herbe sous le pieds d’une attaque genre Sybil c’est que chaque noeud décide en qui il a confiance (le quorum-slice), c’est-à-dire l’ensemble des noeuds qui vont le convaincre si ils sont tous d’accord sur quelque chose. Ainsi, le liveness (est-ce qu’on peut progresser dans le consensus) et la sécurité (est-ce que on est bien d’accord avec le consensus) est une caractéristique de chaque noeud et non du réseau entier. Donc le fait que beaucoup de noeuds fassent n’importe quoi ne gène absolument pas les autres si ils ne dépendent pas d’eux pour se convaincre et faire progresser le consensus.

En fait SCP est je trouve vraiment une très belle généralisation des protocols classique style paxos, car chaque noeud peut décider lui-même du compromis entre sécurité (on ne croit pas n’importe quoi) et liveness (on ne reste pas bloqué si on arrive à parler à personne) et de fait le système ne peut jamais vraiment crasher. Le protocol passe sans marche d’une architecture centralisée à complètement décentralisée en passant par un système de tier (des tops tier comme des banques ou des ONGs, des middle tier comme les états, puis les autres), ce sont les noeuds qui décident à qui ils font confiance.

Pour l’instant, SCP n’a été implémenté que par Stellar pour leur système de cryptomonnaie. Ce qui m’intéresse personnellement, c’est SCP pour distribuer une base de donnée quelconque et pour ça il faudrait réécrire une librairie qui fait uniquement SCP sans toutes les histoires de comptes/transactions etc, mais pour duniter, ça serait probablement juste une histoire de plugger le dividende universel et le WoT (qui du coup pourrait d’ailleurs être directement intégré au protocol de consensus).

Qu’en dites-vous?


Difficulté personnalisée minimale
#2

Bon je n’ai pas lu le whitepaper, mais disons que pour Duniter on va rester sur en terrain connu pour cette partie. Qui plus est, nous ne sommes pas forcément intéressés par les temps d’attente longs ou court, tout ce que l’on veut c’est une monnaie libre. Le délai pour être d’une journée que ce ne serait pas le plus important, bien qu’un peu lent étant donné ce que montrent les cryptomonnaies actuelles.

J’ai déjà l’impression de me comporter comme un vieux qui rejette tout, ça vient vite !

A la limite l’histoire de consistance forte est intéressante, mais encore une fois ce n’est pas nécessaire. Donc bon, ce ne sera pas pour nous.

Cela dit c’est très bien que tu ne sois pas satisfait, il y a sûrement plein de choses possibles à faire mieux que ce qu’on développe aujourd’hui. Mais pour nous je pense que c’est trop tard :slight_smile:


#3

Oui, Duniter se propose de générer une monnaie libre P2P. Après que d’autres logiciels fondés sur d’autres architectures puissent faire mieux d’une façon ou d’une autre c’est très bien, il faut le faire !

Même mieux, si d’autres architectures se développent pour générer une monnaie libre et qu’elles soient en mesure de reprendre une monnaie libre existante pour la continuer sur un autre fondement technique, ce serait encore mieux !

Mais à ce jour, aucune monnaie libre P2P n’a jamais été générée nulle part. Donc avant de faire un pas plus loin dans 10 ans, 20 ans, 40 ans, ou 80 ans, il faut déjà faire le premier pas. Que d’autres préparent le second pas ce serait très bien bien entendu.


#4

Mouais, enfin je comprend votre position (mais amha il faut relativiser, on en est même pas à la version 1, vous avez de la marge de maneuvre). Après l’idée c’est quand même d’avoir une monnaie utilisable et même mieux, user-friendly pour faciliter l’adoption, donc le temps d’attente me paraît pas crucial mais relativement important (j’ai pas trop envie d’attendre 1 jour pour payer à la caisse ou même faire un virement).

Je vais repréciser l’histoire de consistence forte parce que le fait est qu’une crypto-monnaie a besoin de la consistence forte pour marcher. Un livre de compte distribué c’est une base de donnée distribuée, c’est-à-dire une machine à état répliquée. Sans consistance forte, il n’y a aucune garantie que ces machines sont dans le même état (racontent la même chose) et donc aucune garantie qu’on ne peut pas dépenser plusieurs fois le même argent. On pourrait penser qu’avec une blockchain c’est pareil en pratique, mais pas du tout, en effet, tout se base sur l’idée qu’en pratique il est impossible (ou plutôt improbable) que plusieurs personnes maintiennent longtemps plusieurs versions différentes (des forks). De plus, duniter affaibli cette architecture car la PoW est peu utilisée: comme il n’y a pas de minage ça ne pose pas de soucis de ce côté là, mais je pense que du coup une attaque sur les transactions est beaucoup plus faisable (mettre le bousin dans le réseau avec des doubles dépenses).

Il y a un deuxième concept intéressant (mais pas trop pour les monnaies) c’est la consistence éventuelle, c’est-à-dire qu’au bout d’un certain temps, si personne n’émet de transaction, tout va rentrer dans l’ordre et les noeuds vont se mettre d’accord. Ce genre de garantie est la seule que peut offrir une blockchain (avec de la PoW) mais encore une fois, c’est uniquement s’il y a beaucoup de noeuds dans le réseau et uniquement en pratique (en espérant que tout ne se passe pas mal). En fait, tout le parti pris de la blockchain, c’est de faire un gros réseau pour rendre une attaque impossible et pour cela, d’encourager les gens à prendre part au réseau avec une récompense. Ce parti pris entraine des garanties très médiocre car c’est tout probabiliste (il y a de grandes chances pour que tout se passe bien…) mais si on enlève les récompenses, c’est plus cohérant et on casse le semblant de sécurité.

edit: désolé pour le délai de réponse :pensive:


#5

https://forum.duniter.org/t/presentation-de-remuniter/1074


#6

Certes, j’avais vu passer ça mais ça m’était sorti de la tête. Ceci dit, le reste de mon argumentation reste valide (tldr; la blockchain n’a quasiment aucune garantie de sécurité (dans le sens les noeuds sont tous d’accord) et encore moins si elle comporte peu de noeuds).


#7

Certes, il y a des bugs partout, on peut trouver des améliorations de partout.
Mais les bugs que résout la monnaie libre sont tellement plus immenses comparés aux améliorations d’une meilleure technologie de base de données décentralisée.
De plus, plusieurs cryptomonnaies fonctionnent plutôt bien avec la PoW + blockchain. Pourquoi retarder le lancement d’une monnaie libre pour des bricoles ?
Désolé, mais Duniter se contentera d’une monnaie libre sur une “vielle techno“. C’est déjà bien non ?


#8

Le temps d’attente est de 5 minutes, c’est déjà très largement satisfaisant comparé à 1 journée. Qui plus est, rien n’empêche des sur-systèmes tels des banques d’apporter des paiements à la seconde, en ayant un compte de monnaie chez eux (en plus d’apporter une certaine anonymité).

Il n’y a jamais aucune garantie absolue de toute façon, peu importe le système. On peut penser que tel ou tel système en apporte une meilleure qu’une autre selon ses propres critères, mais ça s’arrête là.

Quant à la consistance, c’est marrant car à l’époque où j’ai découvert Bitcoin je me suis dit « ah mais en fait on fait juste confiance à une liste d’adresses IP ! », ce que je trouvais en fait ultra-léger. Dans Duniter au moins, ce sont des identités bien déterminées qui agissent, ainsi le réseau peut aussi assurer sa consistance par coopération. Cette caractéristique change beaucoup de choses, et permet notamment, je cite :

Ainsi les noeuds peuvent déjà implémenter SCP entre eux par dessus la blockchain.

edit : tu noteras d’ailleurs que, essentiellement, rien n’empêche quelqu’un de modifier le code de son propre noeud Duniter pour refuser tout bloc qui n’aurait pas été écrit par d’une liste de noeuds autorisée. Et donc, non seulement SCP est possible dès maintenant, mais mieux, ce ne sont pas les développeurs de Duniter qui décident seuls de comment va se comporter le réseau, mais bien ses utilisateurs !


#9

Je ne vais pas chipoter sur le temps d’attente parceque ce n’est pas le fond de mon propos.

Bah pas vraiment :wink: … enfin ça dépend de ce que tu entends par absolu. Par exemple il y a en recherche sur la réplication des bases de données quelques résultats théoriques qui sont démontrés (le théorème d’impossibilité de FLP, le théorème CAP). De même, il y a des protocols de consensus qui, sous certaines hypothèses clairement définies, apportent des garanties (propriétés) sur l’état de la base de donnée. Ce n’est pas le cas du protocol blockchain, qui est juste un gros réseau ou tout le monde publie ce qu’il veut n’importe comment avec la seule contrainte de résoudre un petit puzzle, ce qui ralenti la publication des blocs et donc on espère qu’il n’y aura pas trop de personnes qui ajouterons un nouveau bloc en même temps.

Non, il y a effectivement des choses qui se ressemblent (l’histoire de toile de confiance) et c’est pour ça que je suis venu en parler ici: pour moi, les concepts de duniter collent beaucoup plus à SCP qu’à une blockchain. Mais ça ne va pas plus loin, SCP est beaucoup plus complexe que juste accepter des blocs publiés par certaines personnes. Déjà il n’y a pas vraiment de blocs, ce qu’on accepte ce sont des votes et il y a plusieurs tours de vote à propos d’assertions différentes pour acter une transaction sur la base de donnée. Donc non, SCP est bel et bien un protocol différent qui n’a pas grand chose à voir avec les concepts d’une blockchain, ça n’a pas vraiment de sens de vouloir combiner les deux.

D’ailleurs pour rebondir sur la modification du code des noeuds (et aussi pour détendre en peu l’atmoshpère parce que je ne suis ni venu pour vous embêter ni pour m’imposer :heart:): même modifier le code de son noeud dans un réseau distribué, ce n’est pas anodin et c’est probablement pas faisable tout seul dans son coin. Il y a un très bel essai des développeurs de urbit sur la gouvernance des réseaux distribué (au passage, urbit est un projet complètement barré mais assez intéressant et marrant).


#10

Que le vote représente un chiffre, une lettre, un bloc, une transaction financière ou autre chose ne me semble pas impossible. Donc on peut par exemple implémenter SCP pour les données des piscines Duniter (données non inscrites en blockchain, donc avec de grandes probabilités de ne pas être communes aux noeuds du réseau). Ce point peut être intéressant, justement.

Sinon, à propos du vote : c’était ma position initiale à l’époque où Duniter s’appelait encore uCoin, au tout début du projet. J’ai fini par quitter cette voie principalement pour deux raisons :

  1. Je suis vite tombé sur le problème de synchronisation (ou consistance), j’ai tenté une approche similaire à SCP mais, faute de connaissances sur le sujet (août 2013), je suis passé à la blockchain dont le principe est simple et a déjà montré que ça fonctionnait.
  2. Le temps et les expériences aidant, je remarque je suis de plus en plus farouchement opposé à tout système de vote où il faut d’une part partir du principe qu’on pourra être d’accord (ce qui est loin d’être évident), et où il faut accepter de subir les décisions des autres (des noeuds, en l’occurrence).

Etant donné que SCP répond au point 1). Ce qui m’importe presque le plus, une fois 1) résolu (même de façon non optimale), c’est bien le point 2). Et je trouve que la blockchain y répond particulièrement bien : elle ne part pas du principe qu’on sera d’accord, mais plutôt des principes que « chacun peut maintenir sa propre version de la blockchain » et « il se peut que, par le jeu du hasard, les blockchains concordent ». Le truc étant bien sûr que, pour que l’on puisse considérer le système comme fonctionnel, que l’on voit effectivement un consensus émerger. Mais ce n’est qu’une conséquence éventuelle, pas une garantie.

Bon je pourrais très certainement épiloguer beaucoup là-dessus, faire le lien avec les principes d’une monnaie libre, mais je pense que tu vois déjà l’idée :slight_smile:


#11

Je crois que je vois où tu veux en venir, mais je ne pense pas que ce soit possible. Comme t’as déjà réfléchis à des trucs comme ça je te fait un résumé un peu plus détaillé de comment marche le “vote” dans SCP (qui n’a rien a voir avec un vote habituel), ça peut probablement t’intéresser.

En fait dans SCP, un vote à propos d’une assertion A c’est juste un message qui dit je suis d’accord avec A. Juste avant, je définit ce qu’est un quorum: c’est un ensemble de noeuds qui suffit à s’auto-convaincre, c’est à dire que chaque noeud de cet ensemble a un quorum-slice inclut dans ce même ensemble. En fait les votes sont totalement déterministes, c’est-à-dire que l’on vote pour A si et seulement si A est cohérant avec notre base de donnée, si on a jamais voté contre A et si on promet de ne jamais le faire. Quand un quorum a voté pour A (ou pour non-A), le vote est réussi et le quorum ratifie A.

En pratique, il y a 2 tours pour prendre une décision A:

  • D’abord les gens votent pour A (ou non-A).
  • Mais qu’un quorum ratifie l’assertion A ne suffit pas. En effet si un noeud a voté contre A alors qu’un quorum a ratifié cette assertion, se noeud se bloque. On fait donc un deuxième tour de vote sur l’assertion accepter A. On vote pour accepter A si et seulement si tout les membres d’un quorum auquel on appartient on accepté A ou voté pour A ou alors tout les membres d’un ensemble bloquant (qui a une intersection non-vide avec tout nos quorum-slice) ont accepté A.
  • Alors seulement, quand un quorum ratifie l’assertion accepter A on dit que A est confirmé.

Un petit schéma vaut mieux que du blabla:

Il y a une subtilité parce que le consensus peut encore se bloquer entre l’acception et la confirmation donc il faut faire des assertions (A dans mon exemple) qui sont soit irréfutables (un noeud valide ne peut pas voter contre, par exemple un noeud a accepté A est irréfutable, c’est ce à quoi sert le deuxième vote), soit neutralisables (c’est pas grave de ne pas tomber d’accord, ça ne va pas bloquer la base de donnée globale). Pour obtenir des assertions neutralisables les noeuds proposent des décisions A selon des règles (pas utile de préciser plus), puis on utilise l’algorithme de vote en 2 tours sur les assertions préparer A puis une fois que c’est confirmé on fait de même pour commit A. Quand un quorum a confirmé commit A alors c’est bon, on peut propager la décision. A tout moment pendant préparer A et commit A on peut voter pour annuler A et ça va le neutraliser.

Comme je n’ai pas détaillé vraiment les histoires de propositions de décisions, le préparation et le commit, c’est probablement pas très clair tout ça, mais c’était juste pour avoir une idée globale de comment ça marche.


Tout ça pour dire que ce n’est (normalement) pas un vote à la majorité où chacun vote pour ce qui lui plait. C’est juste des envois de messages principalement basé sur le fait qu’une assertion soit cohérante ou pas avec notre base de donnée. De plus comme on fixe nous même notre quorum-slice, on a absolument pas a subir des noeuds que l’on aime pas.


#12

C’est bien là le 1er problème majeur sur lequel je suis tombé : si je me sers du vote pour synchroniser mes données, qu’est-ce qui synchronise les données du vote lui-même ?

Autrement dit, comment puis-je m’assurer :

  • que j’ai bien reçu tous les votes au moment de prendre ma décision ?
  • que chaque noeud a bien reçu les mêmes votes, ou si je reçois des votes contradictoires (mais pas incohérents), lequel je dois prendre ?
  • que fais-je si je ne reçois jamais les votes, ou pas suffisamment ?

Cela m’a amené à la conclusion qu’il existait probablement un élément plus fondamental que le vote lui-même, puisque manifestement Bitcoin se synchronisait très bien sans jamais bloquer. C’est là que j’ai réalisé, à tort ou à raison, que la définition d’un protocole de communication P2P était encore plus fondamental que le reste.

Or la preuve de travail permet de créer un tel canal : celui-ci est de type broadcast avec une probabilité acceptable de collision dans les messages. Ce qui, je trouve, est absolument génial.

edit : ça ne veut pas dire que le protocole SCP n’est pas un protocole de communication P2P utilisable, seulement je le trouve moins simple/moins élégant que celui d’une blockchain avec preuve de travail.

edit 2 : d’ailleurs si l’on voulait être plus précis, je dirais que c’est surtout la preuve de travail qui crée ce canal de communication logique, la blockchain est simplement un concept reflétant un enchaînement historisé de données “par bloc” et n’a rien à voir avec ce canal.


En tous les cas, pour cette histoire de vote, j’ai commencé à lire le whitepaper de Swirlds et j’ai effectivement pu voir qu’il ne s’agissait pas de subir les décisions des autres. M’enfin, ça ne me satisfait toujours pas :slight_smile: