Dans mes expérimentations sur les datapods ipfs (cf IPFS pour les datapods v2), j’ai développé une structure de donnée qui combine plusieurs aspects :
- Merkle tree comme chaque nœud est identifié par un cid, c’est un Merkle Directed Acyclic Graphs (DAG) | IPFS Docs
- AMT c’est un Array Mapped Trie comme
https://en.wikipedia.org/wiki/Array_mapped_triedonc sans le Hash de HAMT - Radix tree on évite les niveaux hiérarchiques inutiles Radix tree - Wikipedia
- Timestamp j’utilise un timestamp comme clé, ça je n’ai vu personne d’autre le faire
Les avantages sont les suivants :
- AMT → permet d’itérer facilement sur les éléments, et en plus par ordre chronologique vu que la clé est un timestamp
- Merkle → permet de faire un diff efficace et sûr, puisqu’on n’a besoin de rentrer que dans les nœuds qui ont changé d’une version à l’autre
- Radix → permet de limiter la profondeur de l’arbre pour un stockage efficace
- Timestamp → c’est là le plus intéressant et innovant à mon avis, je détaille ci-dessous
Avantage d’un timestamp comme clé
Utiliser un timestamp comme clé permet de conserver une grande partie de l’arbre inchangée et de grouper les modifications par paquets (par exemple de 4 secondes) pour éviter de recalculer le hash du root node à chaque insertion. Ça facilite donc d’autant la synchronisation et la correction des éventuels problème de diffusion du message sur le réseau p2p.
Cela permet également un traitement différencié relativement à l’ancienneté des données, par exemple on peut extrêmement facilement dés-épingler les données datant de plus de deux ans de son nœud IPFS pour le concentrer sur les données récentes. Ça devient donc trivial de faire quelques nœuds “archive” et beaucoup de nœuds “live” pour soutenir le réseau là où il y en a le plus besoin.
Cela permet de se prémunir d’attaque par rejeu de trop grande ampleur car le set de documents qui peuvent être rejoués est limité par la fenêtre de temps acceptée et l’ensemble des clés publiques de confiance.
Inconvénients d’un timestamp comme clé
Cela place le contrôle de la clé côté utilisateur, ce qui lui donne la possibilité de déséquilibrer l’arbre en surchargeant une partie, par exemple une feuille avec un timestamp donné. Mais cet inconvénient est mitigé par l’utilisation d’une liste de clé publique de confiance. Si malgré cela il y a un attaquant, on peut lui compliquer la tâche de prévoir les timestamps des autres participants en choisissant une fenêtre d’acceptation suffisamment courte (de l’ordre du transport sur le réseau). Et il reste toujours facile d’élaguer l’arbre a posteriori (après l’attaque), donc ce n’est pas critique.
Je n’en ai pas trouvé d’autre, donc à vos claviers ><
Pour l’instant, j’ai réalisé une implementation souple donc fragile (dag-cbor) et incomplète (pas de suppression déterministe, pas d’interface de Map…), mais même en l’état elle me paraît suffisante pour être utilisée en production et améliorée par la suite. En effet, il n’y a pas de problème à ré-indexer toutes les données d’une version vers une autre, d’ailleurs je compte le faire pour les données Cesium+ à titre d’exemple.
Autre références