# Timestamp array mapping merkle trie in IPLD

**URL:** https://forum.duniter.org/t/timestamp-array-mapping-merkle-trie-in-ipld/12146
**Category:** R&D
**Tags:** ipld, merkle-tree, ipfs
**Created:** [3 April 2024 10:08 UTC](https://forum.duniter.org/t/timestamp-array-mapping-merkle-trie-in-ipld/12146 "2024-04-03T10:08:43Z")
**Posts on this page:** 1
**Page:** 1

<div class="post-metadata">

### Author: ![HugoTrentesaux](https://forum.duniter.org/user_avatar/forum.duniter.org/hugotrentesaux/32/6396_2.png) [@HugoTrentesaux](https://forum.duniter.org/u/HugoTrentesaux)
#### Post date: [3 April 2024 10:08 UTC](https://forum.duniter.org/t/timestamp-array-mapping-merkle-trie-in-ipld/12146/1 "2024-04-03T10:08:43Z")

</div>

Dans mes expérimentations sur les datapods ipfs (cf [IPFS pour les datapods v2](https://forum.duniter.org/t/ipfs-pour-les-datapods-v2/12119)), 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](https://docs.ipfs.tech/concepts/merkle-dag/)
- **AMT** c’est un Array Mapped Trie comme `https://en.wikipedia.org/wiki/Array_mapped_trie` donc sans le Hash de [HAMT](https://en.wikipedia.org/wiki/Hash_array_mapped_trie)
- **Radix tree** on évite les niveaux hiérarchiques inutiles [Radix tree - Wikipedia](https://en.wikipedia.org/wiki/Radix_tree)
- **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

- [https://cedric.cnam.fr/vertigo/Cours/GRBD/searchtries.pdf](https://cedric.cnam.fr/vertigo/Cours/GRBD/searchtries.pdf)