Ca marche avec n’importe quel autre protocol sans autorité, non ?
Pas faux, moi aussi ^^
C’est le but de cette discussion, puis des RFC.
Je suis en train de modéliser un premier model d’arbre “simple” pour voir si on est bien sur la même longueur d’onde.
Oui. Mais dans un réseau majoritairement honnête, ce problème de mensonge par omission n’arrive pas car tu peux comparer les résultats entre les noeuds. Si les noeuds sont identifiés et considérés honnêtes en majorité, pas de problème donc.
Dans un réseau où les noeuds ne sont pas identifiés, l’attaque sybille est possible, et cette comparaison n’est plus aussi certaine que dans l’autre cas 
Dans cette situation, l’attaque par omission devient envisageable.
C’est bien pour ça que sur le principe, ça m’embête de ne plus pouvoir identifier les noeuds, même si je comprends vos arguments
En quoi tu ne peux pas identifier les noeuds dans mon modèle ?
Ce n’est pas “ton modèle”, c’est plutôt l’autre topic (avoir la possibilité de dissimuler / anonymiser les noeuds membres qui calculent des blocs)
Ah d’acc.
Edit : c’est galère pour dessiner des gros graphes correctement. Quelqu’un connait un truc pas trop compliqué pour dessiner des graphes orientés ? J’ai essayé Graphviz mais j’arrive pas à gerer l’ordre et les alignements.
@nanocryk je ne sais pas quel type de graphe tu cherche a faire mais sache que @vit a installer un module sur le site pelican qui permet de générer des graphes, peut etre que ça peut t’aider :
Bon j’essaye de me débrouiller avec Graphviz en faisant plusieurs vues différentes.
En attendant, voila un résumé de ce qui serait stocké dans l’arbre (etat) :
(hash,emeteur,recepteur) par exemple. Vu qu’il y a 1 et 1 seul document de ce type par membre, il n’est pas possible de l’omettre. Un nœud est forcement capable de créer et d’envoyer ce document, donc s’il ne le fait pas c’est qu’il n’est pas honnête.
Remarque : il n’est pas nécessaire de stocker ce document récapitulatif sur le disque. On peut faire une requête dans la base de données de toutes les certifications actives liée a un membre, puis reconstruire ce document, et donc retrouver le même hash que dans l’arbre, ce qui prouve sa validité.
Ensuite dans l’arbre de transformation on retrouve tous les documents signés par les utilisateurs (transactions, certifications, etc) ainsi que certains évènements (expiration d’une certification, DU, etc). Ces évènements sont déterministes et ne dépendent que du temps. Enfin on stocke le nouvel état après transformations, et n’importe quel nœud pourra appliquer lui même les transformations et trouver le même résultat. D’ailleurs, seuls la partie “transformation” doit être transmise intégralement sur le réseau, vu que l’état précédent est déja connu, et que le nouveau peux être calculé localement.
Les clients eux récupèrent uniquement les premières couches pour vérifier que la preuve de travail et la signature sont valides, et peuvent demander à plusieurs nœuds ces informations pour vérifier qu’elles sont validées par plusieurs et donc ont beaucoup plus de chances d’être consensuelles.
Les anciens blocs ne sont stockés que pour la résolution de fork voir pour garder un historique pour ceux qui veulent, mais ils peuvent être supprimés après une periode où la probabilité d’un fork est considérée comme négligeable. Pour montrer que la preuve de travail est accumulée depuis le bloc genesis, il suffit seulement de garder la première couche de chaque bloc, c’est à dire : la racine du bloc précédent, l’éméteur, le nonce, la signature, et la racine des données (edit : + le timestamp). Rien qu’avec ça on peut alors vérifier qu’un bloc est bien un descendant du bloc genesis.
Autre point : vu que les transformations sont signées, et qu’elles sont appliquées et vérifiées par chaque noeud, il ne me semble pas nécéssaire de stocker les signatures dans l’état : elle ne peuvent être dans cet etat que si elles sont apparues via transformation, et donc qu’elles étaient signées.
Si vous voyez quelque chose qui cloche ou à rajouter, n’hésitez pas
Edit : un client pourrait aussi télécharger toute une partie de l’arbre qui l’interesse (uniquement les hashs), et vérifier en local que les hashs qu’il produit sont bien dans l’arbre.
Alors je ne suis pas sur de comprendre 
En tout les cas il faut tout de même que les signatures de chaque document rentre en compte dans le calcul des hashs des nœuds de merkel !
Oui bien sur, mais uniquement dans la partie transaction/transformation, les utilisateurs prouvant qu’ils ont le droit de faire ces modifications. Mais quand ces modifications sont appliquées (et qu’elles peuvent être vérifiées par tout le monde), l’état en lui meme n’a pas besoin de leur signature. Le premier cas que je vois c’est les UTXO. Un utilisateur publie sa transaction (signée) qui consomme des sources et en produit d’autres. Cette transaction se retrouve dans l’arbre de transformation. Cette transaction à pour effet de rendre consommées les sources, et d’ajouter les nouvelles sources. Cette nouvelle information n’a plus besoin de la signature du membre.
En résumé, l’état n’est modifiable qu’en passant par des transformations, et seules ces dernières contiennent des signatures. L’état lui est protégé par la vérification des transformations par les noeuds, la signature du createur du bloc et la proof of work. On met à jour l’état, et la transaction en elle même peut être oubliée.
Pour permettre à un client de voir si une source a été consommée, on ne la supprime pas immédiatement de l’état mais on la marque consommée avec un compteur qui, quand il depassera une certaines valeur, autorisera cette perte d’information qui est maintenant trop vieille pour être vraiment utile. On a donc un système qui empeche les doubles depenses et la création de monnaie malicieuse, mais qui oublie les vieilles transactions, ce qui economise de la place et efface le cheminement de l’argent. La monnaie devient donc fongible, vu qu’on ne peux pas discriminer une source plutot qu’une autre parcequ’elle serait passé par un compte d’un voleur par exemple.
Je suis en train de rédiger un document donnant un petit exemple pratique de cette structure, avec différentes techniques pour stocker des données vrai/faux, des listes de documents et des dictionnaires (telle identité/clé publique est associée a tel document).
Première esquisse de la structure de l’arbre, avec quelques “structures de données” et comment elles peuvent être utilisées pour répondre aux problématiques de la G1.
https://framabin.org/?d63d35bc0fec1fd6#IcI+Mw9smZnWzo6MiJRnuOqJ0RghwNbL4j94q4/bekc=
J’espère que ma vision vous sera plus claire et qu’on sera sur de penser à la même chose 
Edit : lien mis a jour, quelques corrections. La méthode des “radix tree” pourra être adaptée selon les cas, peut-être que 8 division ça fait beaucoup, et que ça demande de retourner plus de hash que 4 sans offrir un meilleur rangement.
Edit 2 : il manque un morceau de commentaire à propos de ud_block_yes : “client can compute hash for “ud_block_yes” or “ud_block_no” and query a node. One of this 2 values must be in the block”.
Edit 3 : Aussi, pour avoir des classements avec 8 divisions, c’est 3 bit (octal). Mais je pense que 4 divisions pourraient suffire et réduire le nombre de hash à fournir. Il faudra faire des simulations avec un certain nombre d’informations pour trouver les optimum.
Il n’est pas au format graphviz ce schéma ?
Quelques choses que je ne trouve pas très claires :
0:members 0:membership 0:list -- contains the list of all hashes contained in this (radix tree) subtree -- each document is stored in a subdirectory based on the sequences of 4bits (0-7) -- a document starting with 0x4b3d could be stored in <U+202D>4/5/4/7/5. -- to avoid unecessary subdivisions, levels with a small number of documents -- are not subdivised again and host directly the documents. -- since this algorithm depends only of this `list`, it can be computed deterministicaly -- from this list and the 0..7 branches are pruned from disk<U+202C>. 0 .. 7 ... 0:alice_member_yes 2:carole_member_yes
Bon là je dois t’avouer, en fait j’ai absoluement pas compris le format décrit ici 
Je ne comprends pas les 4 bytes, le 0…7 etc. Tu saurais exprimer ça autrement ? Avec un schéma dessiné par exemple ?
En fait je comprends bien que tu t’appuie sur les radix tree, mais je ne vois pas absoluement pas comment. Donc si tu pouvais revenir dessus… Ca a l’air très clair dans ton esprit mais perso ça ne l’est pas du tout pour moi 
Au passage, je crois que certaines phrases sont incomplètes :
if a client want to know all certifications a member receives and gave, a query a group document document containing the list of certifications. The node can’t omit certifications
Non, c’était trop le bazar. Je posterais des schemas plus petit plus tard.
4 bits pas bytes … enfin plutot 3, vu que j’ai corrigé.
L’idée est que tu vas hasher chaque document que tu veux indéxer, et les stocker dans l’arbre de Merkle. Mais si tu les met tous au même niveau, il faudra tous les hashs pour vérifier que le parent est valide. Il faut donc trouver un moyen de les séparer en groupes, et toujours de la même manière avec la même liste pour qu’il soit simple de les retrouver, et que n’importe qui ayant les documents obtienne le même arbre.
Pour simplifier je ne vais pas prendre 3 bits mais 4, ce qui correspond à l’ecriture en hexa.
Si j’ai les hashs 0xa2b5…, 0xa598…, 0x27d2…, 0xa257.
Si je prend la première lettre (les 4 premiers bits), je peux séparer 2 groupes :
0xa2b5…, 0xa598…, 0xa257 et 0x27d2
Dans le premier, je peux encore séparer 2 groupes
0xa2b5…, 0xa257 et 0xa598
Je peux donc avoir l’arbre suivant :
----------------
| |
-------------- 0x27d2
| |
----------- 0xa598
| |
0xa2b5 0xa257
A chaque groupement on prend son hash, et on l’utilisera pour calculer celui du dessus (Merkle Tree). Avec un grand nombre de documents, selon permet de donner les hashs de seulements quelques documents (plus les parents) au lieu de donner les hashs de tous les documents. C’est vraiment un radix tree, mais au lieu de prendre des lettres ont prend les X premiers bits de chaque donnée.
Si tu ne comprends toujours pas je pourrais prendre un exemple pratique, mais ça me demanderais un peu de temps pour préparer les données (a la main vu que ce n’est pas encore codé)
Oui, j’ai eux quelques problèmes de formatage qui m’ont fait perdre des lignes, c’est ce qui est arrivé a une autre phrase que j’ai noté en edit.
En gros il existera toujours au meme endroit dans l’arbre un document par membre contenant la liste des hashes des certifications qu’il a recu et emis. Il est obligatoire, donc un noeud ne peux pas mentir par omission. C’est un seul document, un seul hash dans le merkle tree, donc pour répondre un noeud doit fournir le document et la preuve de merkle qui va avec. S’il repond qu’il n’existe pas, il ment. Avec ce document le client connait maintenant le hash des certifications, et il peut les demander. Vu que ce document contient obligatoirement toutes les certifications qui correspondent à ce membre et qui sont dans l’arbre, le membre doit pouvoir lui fournir les documents. S’il ne les donnent pas, on sait qu’il n’est pas coopératif, et on demande a quelqu’un d’autre. A la fin, on a obtenu tous les documents voulus et la preuve qu’ils font bien parti de l’arbre (vu qu’avec la preuve on optient le Merkle root), et ce sans possibilité de faire une attaque par omission.
Tu veux que j’essaye de faire un petit document expliquant chaque structure une par une ?
(Elois, je te vois aimer mes posts 
Tu n’as pas d’avis à donner ? )
Yes ok, compris. J’aurais représenté l’arbre comme ça, ce qui aurait été plus clair je trouve
-------0x--------
| |
------a------- 27d2
| |
-----2------ 598
| |
b5 57
J’amagine qu’à petite échelle, l’arbre prendra plus de place qu’une simple liste du fait des pointeurs vers les enfants/parents, mais qu’avec des millions de membre dans la WoT. ça fait sens.
Encore faut-il être certain que l’identité est membre. Est-ce qu’un noeud ne pourrait pas mentir là dessus, et répondre “Cette identité n’est pas membre, je ne peux pas te donner de preuve de merkle” ?
C’est peut-être évitable avec un radix tree décrivant les membres en fonction de leur UID ceci dit. Il suffit de télécharger ce radix tree et de le parcourir pour voir si notre UID est dedans.
En effet, je le noterais comme ça maintenant, même si en pratique on ferais pas 16 subdivisions. ( mettant les hashs complets en feuille par contre)
Dans l’exemple que j’ai donné il y a une partie disant si une indentité est membre ou non (jusqu’a un certain temps).
On peux aussi appliquer le type “map” que j’ai décris en dessous : on a un document qui liste pour chaque identité quel est le hash du document contenant les hashs des certifications.
Edit : en fait l’arbre ne serait pas exactement comme ça, on ne peut avoir que des subdivisions ou que des feuilles finales, mais pas de mélange. Dans 0x tu aurais 0 1 2 3 4 5 6 7 8 9 a b c d e f, et dans 2 tu aurais eu 27d2. C’est pour ça qu’un radix de 4 bits me semble beaucoup. Après on pourrait rendre ce choix de radix dynamique en fonction du nombre d’objets a lister. Le but étant bien entendu d’avoir en moyenne le plus petit nombre de hashs à retourner comme preuve.
J’ai pas compris ce que tu souhaites exprimer ici.
Edit : Il vaudrait mieux parler de noeuds, de feuilles, d’enfants et de parents plutôt que de “subdivision” dont je ne vois pas trop ce que ça peut être dans un arbre
Si on fait le parallèle avec un système de fichier je disais qu’on ne peux pas avoir des dossiers ET des fichiers dans un même dossier. Mais en y réfléchissant je pense qu’il n’y a pas besoin de cette limitation, et que ton arbre pourrait tout à fait être utilisé comme ça. Si on a pas assez de documents qui rentrent dans le même panier (radix), alors on les met en vrac. On pourrait alors trouver un algorithme qui puisse determiner le nombre optimal de radix et a partir de combien on les applique pour obtenir le moins de hashs possibles.
Il me semble que c’est le principe d’un radix tree d’optimiser l’espace. Si je comprends bien, pour toi on l’utilisait seulement pour retrouver les hash des documents mais pas pour optimiser l’espace ?
Pourquoi pas. Personnellement, je considère que le bien est l’ennemi du mieux. Ou encore : early optimization is the root of all evil. Je préférerai qu’on parte sur la solution la plus facile à concevoir, developper, maintenir.
À partir de la, pour recadrer la réflexion :
EDiT : je pense qu’il faudrait penser aux Patricia trees en fait : https://stackoverflow.com/questions/14708134/what-is-the-difference-between-trie-and-radix-trie-data-structures/40567517#40567517
C’est utilisé dans ethereum, ça semble particulièrement adapté aux données binaires comme les hash, voire même pour mapper des données du type “UID/identity document hash”.
EDIT2 :
Je reprends ta proposition, et je te propose quelques différences. Je vais prendre en compte:
[Sha hash, Index, Amount, Base]
Pubkey
[Block number, Amount, Base]
C’est surtout pour optimiser la taille de la preuve de Merkle, je vais revenir dessus après.
C’est justement en cherchant des usages avancés des Merkles tries que je suis tombé sur les Patricia tries d’Ethereum dont je me suis inspiré pour mes arbres. Je n’ai pas trop compris les operateurs qu’ils appliquaient dessus, mais je trouve que ma version simplifié à l’air fonctionnelle.
En effet, même si tu noterais que ça servira juste pour structurer le Patria tree, mais que son contenu (des hashs) doit rester les hashs optenus depuis ses enfants (sinon on pert tout interet des Merkle tries). Sinon, l’UID est un hash des différentes informations uniques du membre, donc il fait la même taille.
Aie aie aie, je ne pense pas non. Avec 600 membres, chaque jour le nombre d’UTXO va augmenter de 600 ? Avec 10 000 membres, +10 000 par jour ? Quand le bloc est marqué comme produisant le DU, on peut mettre à jour les “UD non dépensés” ce qui est fait de manière atomique dans un bloc. De plus le nouvel état final comlplet n’est pas communiqué quand un bloc est publié, seulement son hash. Les autres noeuds vous alors vérifier et appliquer les transformations données par le noeuds (et vérifiées par le Merkle tree de transformation) et vont obtenir leur nouvel état, qui donnera le même Merkle root si tout est valide. Rien de très complexe là dedans et ça evite une explosion du nombre d’UTXO. Quand aux utilisateurs qui veulent utiliser leurs DU, ils ne doivent en aucun cas donner le hash dans l’arbre, seulement la quantité qu’ils veulent dépenser. Les noeuds peuvent ensuite vérifier qu’il a assez dans ses “UD non dépensés”, valeur qui est consensuelle et connues par tous car elle figure dans le Merkle tree et est a tout moment vérifiable.
C’est ce que j’ai appliqué dans la branche truths tu remarqueras 
J’ai bien été cherché mes radix tries quelque part
Si une feuille qui contient c’est infos là, ça me semble correct. (voir aussi la réponse d’en dessous)
Yeap, mais il va falloir faire attentions à quelques trucs : est-ce qu’on utilise le set des UID connus pour générer cet arbre ? Est-ce qu’il y a un nombre de niveaux maximal ?
Ce n’est pas un problème de stockage, vu que ces information là peuvent être générées à la volée, mais de minimisation de la preuve de Merkle, c’est à dire retourner le moins de hashs possible en moyenne. L’optimum que je vois c’est d’avoir quelque part la liste des UID pris en compte (membre de la toile au présent, plus les membres qui ont quitté la toile depuis moins d’un certain temps), de trier cette liste, et ensuite de classer les information dans un arbre binaire équilibré. On aura donc une preuve de Merkle de n hash pour log2(n) identités.
C’est une technique qui serait plus difficile à utiliser pour les UTXO, vu que leur nombre peut rapidement croitre et que le tri de liste pourrait devenir trop couteux (quoique, il me semble que les algorithmes de tri scale plutôt bien), on peut alors les stocker dans un Patricia tree avec une profondeur qui dépend du nombre d’UTXO. Le problème avec cette solution, c’est que la preuve qu’une UTXO est bien dans l’arbre va demander les hashs de pas mal de frères, surement plusieurs centaines. S’il s’avère qu’il est plus simple d’ordonner les UTXO puis de les stocker dans un Merkle tree binaire trié, cette même relation n → log2(n) s’appliquerai. Je pense personnelement que ce tri ne serait pas trop compliqué a faire, surtout qu’on part à chaque fois de la liste triée de l’état précédant. On a juste à prendre cet état (trié), supprimer (ou marquée consommée d’une certaines manière) les UTXO consommées (toujours trié), puis d’ajouter à la fin les nouveaux UTXO puis de lancer un tri. Il suffit alors d’utiliser un algorithme de tri qui soit rapide pour un set (trié; non trié) et c’est gagné.
Oui on peut séparer certifications émises et envoyées. Ca me semble correct en appliquant mes autres remarques.
Je vois qu’on commence à être sur la même longueur d’onde, c’est cool Je vais essayer de rédiger un petit document (hors RFC mais qui pourrait être intégré dans la RFC 5 si on décide de l’utiliser) qui spécifie la construction de cet arbre et de toutes les structures dont nous avons parlé.
C’est ce que tu cherches à faire ?
Tu peux éditer le schéma en ligne.
Plantuml fonctionne sur le wiki du site duniter.org, tu peux regarder les exemples déjà sur le site.
Super merci, je vais utiliser ça du coup !