Construction des manifestes & Merkle DAG dag Décidé

Comment une arborescence de fichiers devient un graphe de nœuds adressés par le contenu. Quatre décisions tranchées : convergence différenciée, découpage des manifestes par le contenu, CBOR canonique, fichiers à flux nommés.

Chaque nœud est nommé par le hash de son contenu chiffré (adresse = BLAKE3(chiffré)) → immuable, auto-vérifiable, déduplicable.

Le modèle objet — cinq types de nœuds

Comme Git (blob / tree / commit), adapté au chiffrement.

• Chunk — un morceau de données brut, la feuille. Adresse = BLAKE3(chiffré).
• Manifeste de fichier — la recette d'un flux de contenu : la liste ordonnée des références de ses chunks.
• Arbre de manifestes — pour un gros fichier, le manifeste est lui-même découpé en sous-manifestes.
• Nœud répertoire — une liste nom → référence plus les métadonnées de chaque entrée.
• Racine de snapshot — pointe vers le répertoire de tête plus les métadonnées du snapshot.

Pourquoi un DAG, pas un arbre

Dans un arbre pur, chaque nœud a un seul parent. Ici, grâce à la dédup, un même nœud est référencé par plusieurs parents — deux fichiers qui partagent un bloc, deux snapshots qui partagent un fichier. Ces nœuds partagés font un graphe orienté acyclique (DAG), exactement comme les objets Git. Ce partage est la déduplication.

Décision 1 — Qui est convergent, qui est aléatoire

La décision crypto traitait « les métadonnées » d’un bloc : tout en nonce aléatoire. En y regardant de près, les métadonnées n’ont pas toutes le même profil — on tranche donc par type de nœud, selon deux questions : que gagne-t-on à déduplicer ? et que risque-t-on à laisser deviner ?

Pourquoi les manifestes peuvent être convergents — l’oracle est déjà payé. Une recette, c’est la liste des adresses et clés de tous les morceaux du fichier. Pour fabriquer une recette candidate à deviner, il faut donc… posséder le fichier entier. Mais qui possède le fichier entier peut déjà le confirmer morceau par morceau, via l’oracle des chunks qu’on a accepté. Rendre les manifestes convergents ne donne rien de plus à l’attaquant — et offre une vraie dédup : la recette ne contenant ni nom ni date, deux machines qui ont le même fichier partagent la même recette même si leurs répertoires diffèrent par ailleurs. C’est le cas commercial type — la flotte de machines semblables — où l’onboarding de la N-ième machine ne coûte presque rien.

Pourquoi les répertoires restent aléatoires — tout risque, zéro gain. L’annuaire porte les noms (« existe-t-il un dossier licenciements-2026/ ? » — très devinable, très sensible) et les dates. Et il ne dédupliquerait presque jamais : les mtimes diffèrent toujours un peu d’une machine à l’autre. Convergence inutile et dangereuse → nonce aléatoire. Les racines de snapshot sont uniques par construction (date, hôte) : zéro valeur de dédup → aléatoire aussi. L’incrémental n’en souffre pas : le client stateless récupère de toute façon l’arbre du snapshot parent pour détecter les changements, et réutilise par référence les sous-arbres inchangés.

Deux propriétés qui verrouillent le raisonnement :

• La convergence se compose vers le haut. Un nœud ne peut être convergent que si les références de ses enfants sont déterministes. Manifestes convergents → référençables de façon stable. Répertoires aléatoires → référencés par leurs parents (aléatoires aussi). Aucun conflit : le convergent ne référence que du convergent.
• Le point de comparaison. borg, restic et kopia dédupliquent toutes leurs métadonnées, noms compris (adressage par hash/HMAC du clair). Notre choix est plus conservateur que les trois — on ne rend convergent que l'indevinable — tout en gardant l'essentiel du gain.

Le manifeste de fichier

À cause du chiffrement convergent des chunks, la recette ne liste pas que des hashes : il faut aussi la clé de chaque chunk, impossible à re-dériver à la restauration sans le clair. C’est le surcoût métadonnées 2×.

FileManifest {                                   // un flux de contenu, rien d'autre
  entries: [
    { addr: 32 o, clé: 32 o, len_clair: varint } // un chunk
    | { hole: varint }                           // un trou (fichier sparse)
    …                                            // ordre = ordre du fichier
  ]
}

• addr pour aller chercher le blob, clé pour le déchiffrer, len_clair pour les frontières.
• L’offset de chaque chunk se déduit par somme préfixe des len — inutile de le stocker, et ça permet le seek (restaurer une plage d’octets sans tout lire).
• Une entrée hole dit « ici, N octets de vide » : un disque de VM de 100 Go rempli à 20 % ne stocke aucun chunk de zéros, et se restaure à l’identique.
• Le flag de compression (brut|zstd) est dans le payload chiffré du chunk, pas dans le manifeste.
• Rien d’autre : ni nom, ni date, ni droits — voir la règle d’or de la décision 4.

Décision 2 — Gros fichiers : l’arbre de manifestes, découpé par le contenu

Un fichier de 1 Tio à 2 Mio de chunk ≈ 500 000 entrées → une recette plate de ~32 Mo, à télécharger et déchiffrer en entier pour restaurer le moindre octet. Trop lourd : on découpe la recette en pages (sous-manifestes), avec un sommaire qui pointe vers les pages — récursivement si besoin. Reste à décider où couper les pages.

Coût réel : nul pour presque tout le monde. À 2 Mio de chunk moyen, un fichier < ~2 Gio tient en une seule page — l’arbre ne s’active que pour les fichiers réellement énormes.

Décision 3 — Sérialisation : CBOR canonique

Écartés : protobuf (explicitement non-déterministe entre implémentations — disqualifiant pour de l’adressage par hash), MessagePack (pas de profil canonique normalisé : à réinventer), format maison (gagne ~10–20 % d’octets — sans intérêt face à des chunks de 2 Mio, au prix d’une spec et d’un outillage à maintenir).

Décision 4 — Nœud répertoire & métadonnées : flux nommés, et la règle d’or

DirEntry {
  nom, type,
  flux: [ { nom_flux, ref: {addr, clé}, taille } ],   // "data" + ADS Windows / forks macOS
  meta: { mode, uid, gid, user, group,                 // numéros ET noms
          mtime_ns, ctime_ns,
          cible_symlink?, dev?, groupe_hardlink?,
          xattrs?, acl?, … }                           // champs optionnels versionnés
}
DirNode { entries: [DirEntry] triées par nom }          // tri = sérialisation déterministe

Trois choix structurent ce modèle :

• Un fichier = un tiroir à compartiments. Windows autorise des flux cachés en plus du contenu principal (les Alternate Data Streams) ; macOS a ses resource forks. Plutôt que de les boulonner plus tard, chaque fichier est d'emblée un ensemble de flux nommés, chacun avec sa propre recette. Un fichier Linux ordinaire a un seul flux — coût zéro ; le jour du support Windows sérieux, la case existe déjà.
• Propriétaire en double. uid/gid numériques et noms (user/group) — sur une autre machine, « l'utilisateur 1000 » n'est pas forcément le même ; à la restauration on choisit le mapping. Liens durs regroupés (même dev+inode → contenu stocké une fois, liens recréés). Champs optionnels versionnés pour étendre (ACL, xattrs, SID/DACL Windows, flags Finder) sans casser le format.
• La règle d'or : les métadonnées ne vont jamais dans la recette. Alice et Bob ont le même fichier, modifié à des dates différentes. Si la date était dans le manifeste, leurs recettes différeraient d'un octet → adresses différentes → plus aucun partage — toute la décision 1 s'évapore. Donc : recette = pur contenu ; date, droits, propriétaire = dans l'annuaire (chiffré aléatoire). C'est le verrou de l'édifice.

Petites métadonnées inline dans l’entrée ; grosses valeurs (ACL/xattrs volumineux) débordées en blobs référencés, à nonce aléatoire. À raffiner avec le sujet Fichiers spéciaux (sparse déjà couvert par les entrées hole).

Racine de snapshot

Snapshot {
  tree:    { addr, clé },            // le répertoire de tête
  date, hôte, chemins_source[],
  parent?: { addr, clé },            // snapshot précédent (historique + réutilisation)
  profils: { chunker_id, compression_id, manifest_split_id },
  version_outil, tags[]
}

profils fige quels paramètres de découpage, de compression et de hashsplit ont produit ce snapshot. L’ensemble des racines d’un tenant = les racines du GC : le mark-and-sweep des points ouverts part de là.

Construction & restauration

On construit enfants avant parents : un parent référence ses enfants par adresse, qu’on ne connaît qu’après les avoir hachés. La mémoire reste bornée par la profondeur du chemin courant — bon pour les NAS. À la restauration, on descend le DAG : racine → répertoire → manifeste → chunks → déchiffrer → décompresser → réassembler ; restauration partielle en ne descendant que la branche voulue, seek dans les gros fichiers via l’arbre de manifestes. Et comme chaque adresse est le hash de son contenu, télécharger et rehacher vérifie l’intégrité de haut en bas — inviolable.

Les quatre décisions en une ligne

• 1 · Convergence différenciée — recettes partagées (indevinables sans posséder le fichier), annuaires et racines aléatoires (les noms se devinent). Plus prudent que borg/restic/kopia, qui dédupliquent tout.
• 2 · Hashsplit récursif — les recettes des gros fichiers sont découpées par le contenu, même astuce que FastCDC un étage plus haut. Paramètres épinglés.
• 3 · CBOR canonique — mêmes octets partout, règles déjà normalisées (RFC 8949), validation stricte partagée.
• 4 · Flux nommés + règle d'or — fichier = compartiments (ADS/forks prêts), trous explicites, et jamais de métadonnées dans les recettes.

Cohérence d’ensemble : chaque nœud reçoit le régime crypto que son entropie justifie, le principe « content-defined » s’applique aux deux étages, tout paramètre influençant les adresses vit dans le profil épinglé du tenant, et un seul GC traite tous les nœuds pareil.