[Pavé !] Ajout pour la RFC5 : Des noeuds qui ne stockent pas les UTXOs

v11
rfc
scaling

#1

Attention : le post qui suit est un véritable pavé, prenez votre temps pour le lire. Merci de ne pas commenter sur un point sans avoir lu l’ensemble du document, vu que des problèmes apparaissent et sont résolus ensuite. Cependant si vous voyez un problème qui n’est pas résolu dans la suite du document, n’hésitez pas à en parler, et surtout n’hésitez pas à dire ce que vous en pensez. Merci de votre attention et bonne lecture. :slight_smile:

Définition d’UTXO : sortie d’une transaction qui n’a pas encore été dépensée (Unspent Transaction Output)

L’ensemble des UTXOs est une structure de donnée qui va croitre au cours du temps, qui a besoin d’être stockée continuellement en mémoire par tous les noeuds, même ceux qui ne calculent pas.

Je propose une utilisation des Merkle-tree qui permettrait aux noeuds de ne pas garder en mémoire la base des UTXOs, et qui donnerais un nouveau rôle interessant aux noeuds mirroirs tout en diminuant leur cout.

Structure de stockage des UTXOs dans RFC5

Actuellement dans la RFC5 la liste des UTXO est triée par le hash de chaque UTXO et rangée dans un Merkle-tree.

Ici 1, 2, 3, ... sont les UTXOs triées par leur hash, et a, b, c, ... sont des branches de Merkle. A chaque modification de l’ensemble des UTXOs, cet arbre est recalculé intégralement, et cet ensemble doit être stocké sur le disque et en mémoire.

Nouvelle structure proposée

La nouvelle structure insère les UTXOs dans leur ordre d’insertion, et pour 8 UTXOs le schema elle le même qu’avant sauf que les UTXOs sont numérotés par ordre d’insertion et ne sont pas triées par leur hash. La profondeur de l’arbre est fixée, et les nouvelles UTXO sont toujours ajoutées au plus profond de l’arbre. Il est donc construit comme ceçi :



Les noeuds vides sont tous identiques et pourraient avoir un hash de 000000... pour être facilement identifiable

Et ainsi de suite. Quand cette arbre (appelé ici epoch) est entièrement rempli, on en commence un nouveau et on les attache ensemble :

Quand un UTXO est consommée, on la remplace par un noeud vide.

L’arbre est recalculé à chaque changement et la nouvelle racine de Merkle représente l’intégralité de l’ensemble des UTXOs.

Fonctionnement

A partir de maintenant, les noeuds oublient complètement le contenu de l’arbre et ne stockent que :

  • la liste des rootX et epochX
  • le strict nécéssaire dans l’arbre en cours de remplissage (ici epoch3) pour ajouter de nouvelles entrées. Dans le dernier graphe qui montrait l’insertion de 3, il stockera alors 3, c, a ce qui lui permettra d’insérer 4 et de recalculer la racine, puis de recommencer.

Quand un utilisateur veut faire une transaction en utilisant des UTXOs, il va donner la preuve de Merkle que l’UXTO qu’il utilise est bien dans l’arbre jusqu’a un rootX ou epoch1. S’il utilise l’UTXO 4 maintenant insérée, il fournira alors comme preuve 3,c,b vide et le noeud aura bien la preuve que l’UXTO existe bien sans l’avoir stockée.

Si la transaction est valide, il va ajouter les nouvelles sorties à la fin de l’ensemble, et remplacer les UTXOs utilisées par une valeur vide. Grace à la preuve de Merkle donnée par l’utilisateur, il peut recalculer le nouvel arbre sans avoir besoin des autres informations. La preuve de Merkle permet donc de vérifier et de modifier l’arbre.

Vu que la transaction peut être réaliser à un moment t et qu’au moment de sa publication t + 1 l’epoch peut avoir augmenté, il fourni avec sa preuve jusqu’a quel epoch il remonte, et le noeud peux bien vérifier que cet epoch correspond. (cette information ne sera plus nécéssaire plus tard)

On peut rajouter que les preuves de chaque UTXO peuvent être regroupées en combinant les parties communes.

Mise à jour de la preuve des transactions suivante

Cette technique ne fonctionne pour l’instant qu’une seule fois. En effet dès que l’arbre est mis à jour avec les UTXOs supprimée et ajoutées, la preuve contenue dans une autre transaction n’est plus valide. La solution est qu’a chaque mise à jour de l’abre, on met à jour la preuve des autres transactions en corrigeant un hash qui vient d’être modifié. Si avec la transaction le hash A d’une branche deviens B, alors toute occurence de A dans les autres preuves stockées sont remplacées par B. Les nouvelles preuves sont alors valides avec la derniere version de l’arbre.

Stockage des preuves

Il est maintenant évidant que la preuve de la présence d’une UTXO est une information vitale, et que si elle disparait complètement cette UTXO est maintenant perdue et indépensable. Il faut donc qu’il y ai toujours des noeuds ou clients qui stocke cette information.

  1. Des noeuds d’achives peuvent stocker tout l’ensemble des UTXO, et les clients peuvent leur demander la preuve. C’est pratique mais demande de stocker tout l’ensemble ce qui ne sera pas faisable par tout le monde au vu de la taille qu’il pourra prendre, et du coup amène un problème de confiance que les noeuds voudront bien coopérer et donner ces preuves.
  2. L’utilisateur (ou un ensemble d’utilisateur qui se font confiance) peuvent faire tourner un noeud (mirroir ou calculant, peu importe) qui va stocker les preuves des UTXOs concernant ces utilisateurs. Cela permet au client de ne pas stocker les preuves, mais aussi de mettre à jour la preuve à chaque mise à jour de l’arbre.

Un client n’est pas connecté h24 au réseau, et ne peux donc pas assurer cette mise à jour. Un noeud peut le faire, mais une interruption de son service rendrait les preuves obsolètes. La solution pour les clients est d’avoir un ensemble assez grand de noeuds qui stockent leurs UTXOs pour que la probabilité qu’ils soient tous hors service au même moment soit faible. Un noeud qui serait relancé pourrait par la synchronisation pas à pas de la chaine mettre à jour les preuves. Tout ce qu’il faut, ce que tous les noeuds stockant les preuves n’arrêtent tous pas de fonctionner plus longtemps que la fenetre de fork, sinon ils ne pourront plus se synchroniser pas a pas et donc mettre à jour les preuves.

On note donc qu’un noeud ne va stocker uniquement l’ensemble de preuves de ses utilisateurs, ce qui est ridiculeusement petit comparé au stockage de l’ensemble des UTXOs. De ce fait les conditions matérielles pour faire tourner un noeud sont très petite, et n’importe qui avec une connection internet un (mini)ordinateur peut faire tourner un noeud qui stockera les preuves. Il peut aussi demander à des personnes de confiance et des services “altruistes” de stocker eux aussi les preuves pour qu’elle ne puissent pas être perdues.

Ce système impose alors une limite importante : un débit maximum d’informations insérées dans la blockchain pour que la très grande majorité des utilisateurs puissent faire tourner un noeud chez eux, avoir le temps télécharger les nouveaux blocs et d’appliquer les mise à jour de preuve. C’est cette limite que l’on devra définir “acceptable” qui définira le nombre maximum de transactions/seconde que Duniter sera capable de gérer. Cette limite pourrait bien évidement être un paramètre du système et être mis à jour au fur et à mesure que le débit augmente dans les foyers. Duniter sera alors largement plus scalable que les autres cryptomonnaies actuelles.

En résumé : impact sur l’écosystème

  • Faire tourner un noeud (calculateur ou mirroir) est beaucoup moins gourmant en espace de stockage et en mémoire, et donc plus de personnes peuvent le faire, ce qui diminue encore plus le risque d’une preuve soit perdue
  • Les noeuds peuvent stocker les preuves à la demande de clients et les mettre à jour. Ca pourrait être configurable pour qu’un noeud accepte de stocker les preuvent que de certains utilisateurs (stockage privé) ou avec un processus d’inscription (stockage public).
  • Un noeud calculateur peut valider des transactions et écrire des blocs sans jamais stocker les UTXOs ni les preuves autres que celles de la piscine. Il peut servir de noeud de stockage de preuves s’il le souhaite, mais rien de l’y oblige.
  • Les logiciels clients permettent de se connecter à différents noeuds de stockage (via un login ou une signature) et peuvent leur demander de stocker et de fournir plus tard les preuves.
  • Rend beaucoup plus difficile de voir “les comptes” des autres utilisateurs et de tracer d’où vient l’argent, ce qui améliore l’anonymité et la fongibilité de la monnaie.

Voila voila. C’est une longue explication pour un fonctionnement qu’il me semble reste plutôt simple quand on a compris l’idée, et qui permettrait de rendre l’execution de noeuds abordable pour n’importe quelle machine avec un petit peu de stockage (les preuvent sont très légères et demandent 2log2(n) hashes par UTXO, avec n le nombre d’UXTO depuis le lancement de la blockchain. Cependant les parties communes des preuves peuvent être stockées une seule fois, réduisant encore drastiquement la taille des preuves.

Merci d’avoir eu le courage de lire cette explication, et j’attends avec impacience votre avis.


Commentaires sur la blockchain Duniter G1
#2

Bonjour,

c’est à dire 3, a, c puis le UTXO n°17 ?

Tu veux dire 3, a, d, vide ?


#3

Pourquoi UTXO 17 ?

Pas besoin de d, car il peut être calculé à partir de 3 et du hash de la transaction inséré (replace 4 vide). On a besoin de passer c pour montrer que le hash de c et d donne bien a, sinon il n’y a plus de lien entre a et d et ce n’est plus une preuve. On a du coup pas besoin de passer a, car on utilisera le hash obtenu comme a avec b vide et on trouvera bien le bon root.


#4

ok, j’ai compris. tu calcul les hash en remontant. je pensait que c’était une suite. autant pour moi :slight_smile:


#5

Oui désolé je n’ai pas précisé.

HashParent = SHA256(HashEnfant0 ++ HashEnfant1). Une autre fonction de hashage peut être utilisée.


#6

En gros, c’est du sharding si je ne m’abuse :slight_smile: C’est clairement expliqué en tout cas.

Le sharding c’est quelque chose de très intéressant pour permettre le passage à l’échelle des blockchains. Par contre, je pense qu’il manque une couche dans ta proposition. On a le mécanisme pour faire du sharding du consensus entre les noeuds du réseaux, mais on n’a pas le mécanisme pour permettre aux noeuds honnêtes de se répartir les UTXO d’eux même.

En effet, je pense qu’en pratique c’est ingérable de demander aux utilisateurs de connaitre quel noeud possède leurs données. Ca rend ça trop compliqué. Il faudrait à mon avis compléter ça avec un protocole réseau pour que les clients puissent simplement demander au réseau “qui peut me fournir la preuve de telle UTXO”.

Alors, sans que les noeuds ne stockent tous les UTXO, on peut envisager que pour 100 noeuds, chacun stock 10% des UTXO par exemple. Ainsi, les données sont bien réparties, et suffisamment répliquées pour qu’elles ne soient pas perdues.

Instinctivement, je me dirigerais vers :

  • une DHT pour chercher les données dans le réseau
  • un réseau en anneau pour distribuer les données

Par exemple en se basant sur OpenDHT : https://blog.savoirfairelinux.com/fr-ca/2015/opendht-une-table-de-hachage-distribuee-au-coeur-de-ring/


#7

J’ai conçu ça moi même, peut être que ça s’apparente à du sharding au niveau du stockage oui.

Merci, j’ai pris pal mal de temps pour faire les schemas et le pavé m’a permi de faire une explication détaillé, ce qui n’est pas souvent acceptable dans une réponse à des questions.

Il n’y a pas besoin. Ils n’ont pas à se répartir les UTXO, vu qu’ils n’ont pas à les stocker. En tant qu’utilisateur, j’ai juste à lancer mon Cesium RFC5 et m’inscrire sur différents noeuds pour stocker mes preuves. Je peux même me faire un noeud rien qu’a moi et stocker les preuves dessus. N’importe qui peut le faire, et proposer à ses amis/connaissance d’utiliser son noeud pour stocker leurs preuves. Et vu que les preuves ne permette pas directement de dépenser les fonds, il n’y a pas de risque à cela.

Quand l’utilisateur veux faire une transaction, il demande à ses noeuds enregistrés la preuve des UTXOs qu’il utilise, signe la transaction et peut l’envoyer à n’importe quel noeud du réseau qui n’a pas besoin de connaitre ces UTXO, vu que la preuve permet de montrer qu’elles sont valides.

Edit : des services pourront se faire pour stocker des grands ensembles d’UTXOs, mais ce n’est pas nécéssaire au protocole et pourra être fait par dessus :wink:


#8

Ben ça veut dire que tu as bien intégré les arbres de merkle alors, bravo :stuck_out_tongue: Tu aboutis à des solutions très similaires à ce que propose ethereum. Tu devrais surement lire leur FAQ, peut être que ça t’inspirerais encore plus :slight_smile: https://github.com/ethereum/wiki/wiki/Sharding-FAQ

Après, il me semble que sur Ethereum, ils font plus que du sharding de données. Bref.

Je pense que ce n’est pas jouable cette manière de faire. Les utilisateurs non-techniques ne veulent pas savoir que “tel noeud stock leur données”, ou que si ce noeud s’éteint il faut “qu’ils demandent à un autre noeud de stocker leurs UTXO”…

Les utilisateurs, ce qu’ils veulent, c’est en gros un “cloud”. Quelque soit l’endroit d’où ils se connectent, ils veulent avoir accès à leurs données. Sans avoir à se rappeler d’autres éléments que leurs identifiants.

C’est pour ça que je pense que sans le protocole de distribution et de répartition des segments automatique, ça ne sera fonctionnellement pas viable, et il vaudra alors mieux rester sur la méthode précédente.

Comment tu justifies à un utilisateur qu’il a perdu toutes ses UTXO parce que les noeuds qui le stockait se sont éteint ? … :confused:


#9

C’est justement le morceau qui me manquais avant et qui me faisait dire que ma RFC5 était incomplète :stuck_out_tongue: Je suis sur que si on pousse cette idée plus loin il sera encore possible d’avoir des améliorations, c’est déjà une avancée concidérable je pense.

Je vois ce que tu veux dire, mais sans cette partie “distribution” dont tu parles.

Le client stocke la liste des serveurs, et on pourrait avoir une liste de serveurs publiques gérés par Duniter qui se partagent cette ensemble d’UTXO. Mais il peut en utiliser d’autres. Je voyais ça un peu comme un système d’instance (à la Mastodon) :stuck_out_tongue: J’installe mon application client, par défaut il utilise les serveurs de Duniter mais je peux choisir d’utiliser mon/mes propres serveurs ou ceux de mon groupe d’utilisateur pour les avoirs au cas où ces “serveurs centraux” sont inaccessibles.

Aucun problème si n’importe qui peut offrir ce service, et surtout si l’information est redondante sur plusieurs noeuds.


#10

Oui, mais tu ne donnes aucun mécanisme permettant de garantir que l’information est redondante sur plusieurs noeuds. C’est bien là que ça me bloque :slight_smile: Tu espère que les humains vont d’eux même s’organiser pour répartir des UTXO… Il faut que les humains s’organisent pour déployer le réseau (c’est déja suffisament compliqué). Le réseau une fois déployé doit être en capacité de se répartir les UTXO de lui même par la suite.

Quand on met en oeuvre une BDD distribuée, on ne définit pas manuellement quel noeud possède quel segment… Ce serait ingérable sinon :slight_smile:


#11

Je comprends bien. Je pense que ça sera le but d’un autre protocole de s’en occuper, mais ce n’est pas le rôle de celui-ci. En plus ces UTXOs permettent de calculer la somme de tout l’argent que j’ai, ce que je ne voudrais pas forcement public. Le fait de le faire “manuellement”, ou en tout cas de choisir où on veut le stocker et par qui me semble meilleur à ce niveau là. Si quelqu’un découvre la monnaie libre via un apéro par exemple, il est très problème qu’au moins un des membres ai un noeud (vu que les noeuds ont des conditions de fonctionnements beaucoup plus simple) et il pourra les stocker. N’importe quelle personne en qui je fait confiance et qui a un noeud peut stocker cette information, et pourrait me laisser les stocker dessus. Ce côté humain et local dans Duniter me semble fournir des propriétés proche d’un DHT.


#12

Oui, rien n’empêche de prévoir cette structure tout en programmant les noeuds pour que dans un premier temps ils stockent “tout” (mode full) ou “rien” (mode léger).

La structure étant là, il pourra être possible de faire évoluer le réseau autour d’une vraie décentralisation avec les versions suivantes.


#13

Exactement, et ce sans rien modifier à la structure de donnée, donc ni soft-fork ni hard-fork :wink: Juste une couche par dessus.

Un noeud leger peut quand même valider les blocs, et même les calculer tant qu’on lui donne les preuves.

Tu penses donc que je peux rajouter ça dans la RFC ?


#14

Quelques questions :

  • La profondeur des arbres epoch est fixée. A combien est placée cette valeur ? Comment la déterminer ?
  • Est-ce que un même principe ne peut pas être utilisé pour les autres arbres de merkle de la RFC5 ?

Sinon, oui, je pense que c’est intégrable à la RFC5. Il va falloir faire un topo résumé de cette RFC quelque part, je sens que les devs ont du mal à suivre toutes ces discussions…


#15

Je pense que ça sera un paramètre à la création de la monnaie, mais qui pourra être changé plus tard. Ce qui est important c’est que ces arbres ne sont pas potentiellements infinis, ce qui rends les collisions cryptographiques encore plus difficiles à trouver. La valeur peut changer d’un arbre à un autre, et on la choisira par rapport à la longueur des preuves que l’on veut utiliser pour les UTXOs plutot recentes. Celles très recentes seront d’environ 2 * profondeur, et les anciennes 2 * profondeur + différence d’epoch.

Justement je suis en train d’y reflechir, mais je ne suis pas sur que ça soit possible. En effet à part les UTXOs, les autres données peuvent être utilisées automatiquement, par exemple après l’expiration d’un delai. Du coup il faut que tous les noeuds stockent ces données.

Je viens de me rendre compte que cette nouvelle structure supprime la nécéssité de supprimer les montants inférieur au minimum possible. Si quelqu’un donne en source une UTXO dont le montant est plus petit que possible, alors la transaction n’est pas valide. A voir si ça ne peux pas non plus réduire le problème des spams de transactions ayant des petites valeurs, et supprimer cette limite.


#16

Comment est-ce que les arbres évoluent lorsque la valeur est modifiée ? Seul la création des prochains epoch est impacté ?

Je ne vois pas en quoi c’était pas possible avant ?


#17

Yeap

Avant on devait supprimer les UTXOs qui “ne valent casiment plus rien” pour gagner de la place. Ici ils sont tout simplement oublié au fin fond de l’arbre, et il n’y a pas de place a gagner puisque qu’on a juste besoin du Merkle hash à stocker.


#18

Ah c’est pour ça que tu parles t’interdire les sources trop petites plutôt que les outputs. C’est malin oui. Ca résoud plein de problèmes cette structure finalement :slight_smile:

Le comportement des noeuds full n’aura plus qu’à être “cette branche est constituée de sources trop petites, je l’efface et je ne stock que le hash de la branche”. Malin !


#19

Je n’avais même pas pensé à ça mais oui en effet :wink:

En fait je reste vraiment sur mon idée de “plus besoin de full nodes” ^^


#20

Parce que tu ne vois que le consensus réseau. Il faut regarder l’impact utilisateur avant tout. Sans full node, l’impact sur les clients et les fonctionnalités utilisateurs est trop élevé. Il y aurait trop de choses technique que l’utilisateur devrait maitriser pour avoir toutes les fonctionnalités de base dont il a besoin. Les logiciels sont déja assez complexe comme ça avec la WoT et la gestion décentralisée des identités…