PD-54 — Construction d’Arbres de Merkle Périodiques à Feuilles Partagées¶

1. Objectif¶

La présente spécification définit, de manière canonique, contractuelle et testable, le mécanisme de construction d’arbres de Merkle périodiques à partir d’un ensemble fini d’événements, incluant le partage de feuilles entre arbres distincts, sans référence croisée entre arbres.

L’objectif est de produire, pour chaque fenêtre temporelle close, une racine de Merkle déterministe engageant l’intégralité des événements valides de la fenêtre, utilisable ultérieurement comme unique entrée d’horodatage et/ou d’ancrage externe.

Cette spécification ne décrit aucune implémentation, uniquement des règles normatives.

2. Périmètre¶

2.1 Inclus¶

• Canonicalisation déterministe des événements.
• Construction d’arbres de Merkle binaires périodiques.
• Définition des règles de tri, de duplication et de calcul des nœuds.
• Gestion de batchs temporels clos.
• Persistance des racines, preuves d’inclusion et métadonnées associées.
• Partage de feuilles entre arbres indépendants (Merkle DAG conceptuel).

2.2 Exclus (hors périmètre)¶

• Horodatage eIDAS (RFC 3161).
• Ancrage blockchain.
• Signature cryptographique des racines.
• Transport, stockage physique ou mécanismes de réplication.

3. Définitions¶

• Événement : donnée logique validée, appartenant à une fenêtre temporelle donnée.
• events[] : liste finie, ordonnée arbitrairement à l’entrée, et close d’événements.
• Représentation canonique : forme normalisée, déterministe et non ambiguë d’un événement.
• Feuille (leaf) : hash cryptographique d’un événement canonique.
• Arbre de Merkle : arbre binaire dont chaque nœud interne est le hash de la concaténation de ses deux enfants.
• Preuve d’inclusion : ensemble minimal de hashes permettant de vérifier l’appartenance d’une feuille à une racine.
• Fenêtre temporelle : intervalle de temps fixe, non chevauchant, associé à un arbre.
• Merkle DAG : ensemble conceptuel d’arbres indépendants partageant potentiellement des feuilles identiques.

4. Invariants¶

Les invariants suivants sont obligatoires et testables :

• I1. À entrée identique, la racine produite est strictement identique.
• I2. Toute modification d’un événement entraîne une racine différente.
• I3. Aucun événement ne peut être ajouté ou retiré après clôture de la fenêtre.
• I4. Chaque arbre est conceptuellement et juridiquement indépendant.
• I5. Le partage de feuilles n’altère ni la racine ni la vérifiabilité des arbres concernés.

5. Règles Normatives¶

5.0 Références normatives et règles de détermination¶

La construction des arbres de Merkle définie par la présente spécification repose exclusivement sur des règles normatives, figées et opposables.

La représentation canonique des événements, le critère d’ordonnancement des feuilles, l’algorithme de hachage autorisé, ainsi que le format des preuves d’inclusion et des métadonnées de vérification sont définis par des identifiants versionnés (canonicalization_id, leaf_ordering_id, hash_algorithm_id/version) référencés dans les métadonnées de chaque arbre. Ces identifiants doivent correspondre à des définitions normatives stables, publiques ou fournies avec la preuve, permettant une vérification indépendante de toute implémentation spécifique de ProbatioVault. Toute évolution de version de ces identifiants DOIT être rétrocompatible : à ensemble d’événements identique, la racine produite reste identique.

Les fenêtres temporelles sont définies par les paramètres window_start, window_end et window_timezone et sont interprétées comme des intervalles [window_start, window_end) non chevauchants, exprimés dans le fuseau indiqué. window_timezone DOIT être un identifiant de la base IANA TZ (ex. Europe/Paris). Un événement appartient à une unique fenêtre si et seulement si sa valeur event_time, exprimée dans le même fuseau, satisfait cette condition.

Un événement valide au sens de la présente spécification est un événement pour lequel : (i) un identifiant est présent, (ii) une valeur temporelle permet une attribution non ambiguë à une fenêtre définie, et (iii) une représentation canonique conforme peut être produite. Toute validation métier ou sémantique supplémentaire est explicitement hors périmètre de la présente spécification.

Toute divergence dans l’application de ces règles est réputée constituer une non-conformité contractuelle, dès lors qu’elle peut conduire à la production d’une racine différente à partir d’un même ensemble d’événements.

5.1 Entrée et validation¶

• R1. events[] DOIT être une liste finie et close.
• R2. Aucun arbre NE DOIT être construit si events[] est vide.
• R3. Seuls des événements validés peuvent être inclus.

5.2 Canonicalisation¶

La canonicalisation et la construction DOIVENT être insensibles à l’ordre d’entrée des événements.

• R4. Chaque événement DOIT être transformé en une représentation canonique déterministe.
• R5. Les règles de canonicalisation (ordre des champs, encodage, exclusions) DOIVENT être figées et versionnées.

5.3 Construction des feuilles¶

• R6. Chaque feuille est définie comme : leaf_i = HASH(canonical_event_i).
• R7. Une même valeur de leaf PEUT être réutilisée dans plusieurs arbres distincts.

5.4 Ordonnancement¶

• R8. Les feuilles DOIVENT être triées selon un ordre canonique déterministe.
• R9. Le critère de tri DOIT être explicitement défini (ex. ordre lexicographique des hashes).

5.5 Construction de l’arbre¶

• R10. L’arbre DOIT être strictement binaire.
• R11. Chaque nœud parent est calculé comme HASH(left || right).
• R12. En cas de nombre impair de nœuds à un niveau, le dernier nœud DOIT être dupliqué.

5.6 Racine et clôture¶

• R13. La racine engage l’intégralité des événements de la fenêtre.
• R14. Une fois la racine calculée, aucun ajout n’est autorisé.

5.7 Périodicité¶

• R15. Un arbre DOIT être construit pour chaque fenêtre temporelle définie.
• R16. Chaque arbre DOIT être indépendant des arbres précédents et suivants.

5.8 Stockage logique¶

• R17. DOIVENT être persistés :
• la racine,
• les preuves d’inclusion,
• les métadonnées de batch (fenêtre, algorithme, version).

5.9 Vérifiabilité¶

• R18. Toute preuve d’inclusion DOIT être vérifiable sans dépendre du système émetteur.
• R19. La racine est l’unique entrée destinée à un usage aval (horodatage ou ancrage).

5.10 Cryptographie¶

• R20. L’algorithme de hash DOIT être nommé, versionné et appartenir à une liste autorisée.

6. Feuilles Partagées et Merkle DAG¶

• R21. Une même feuille PEUT appartenir à plusieurs arbres.
• R22. Aucun arbre NE DOIT référencer un autre arbre.
• R23. Le graphe formé par l’ensemble des arbres et feuilles DOIT être acyclique.
• R24. Le partage de feuilles NE DOIT introduire aucune dépendance temporelle, logique ou juridique.

6bis. Diagrammes¶

6bis.1 Diagramme d’état — Cycle de vie d’un batch Merkle¶

Le batch traverse trois états principaux : collecte des événements (OPEN), clôture de la fenêtre temporelle (CLOSED), puis finalisation après calcul de la racine (FINALIZED). Les invariants I3 et I4 garantissent l’immutabilité post-clôture et l’indépendance entre arbres.

stateDiagram-v2
    [*] --> OPEN : Ouverture fenêtre temporelle (R15)
    OPEN --> OPEN : Ajout événement validé (R1, R3)
    OPEN --> CLOSED : window_end atteint (R14, I3)
    CLOSED --> FINALIZED : Racine calculée (R13, R17)
    FINALIZED --> [*]

    OPEN --> REJECTED : events[] vide à clôture (R2, E1)
    REJECTED --> [*]

    state OPEN {
        [*] --> Collecting
        Collecting : Validation événements (R3)
        Collecting : Attribution fenêtre (§5.0)
    }

    state CLOSED {
        [*] --> Canonicalizing
        Canonicalizing --> Ordering : R4, R5
        Ordering --> Building : R8, R9
        Building --> RootComputed : R10, R11, R12
    }

    state FINALIZED {
        [*] --> Persisted
        Persisted : Racine + preuves + métadonnées (R17)
        Persisted : Vérifiable hors système (R18, I1)
    }

6bis.2 Diagramme de séquence — Construction d’un arbre de Merkle périodique¶

Ce diagramme illustre le flux complet depuis la collecte des événements jusqu’à la persistance de la racine et des preuves d’inclusion, en passant par la canonicalisation, le tri déterministe et la construction binaire. Les invariants I1 (déterminisme) et I2 (sensibilité) s’appliquent à chaque étape de transformation.

sequenceDiagram
    participant W as WindowScheduler
    participant V as EventValidator
    participant C as Canonicalizer
    participant S as LeafSorter
    participant B as TreeBuilder
    participant P as PersistenceLayer

    W->>V: Clôture fenêtre [window_start, window_end) (R15)
    V->>V: Vérifier events[] non vide (R2, E1)
    V->>V: Filtrer événements invalides (R3, E2)

    loop Pour chaque événement validé
        V->>C: event_i
        C->>C: Canonicalisation déterministe (R4, R5, I1)
        C-->>S: leaf_i = HASH(canonical_event_i) (R6, R20)
    end

    S->>S: Tri canonique déterministe des feuilles (R8, R9)

    S->>B: feuilles triées
    B->>B: Duplication si nombre impair (R12)

    loop Construction bottom-up
        B->>B: parent = HASH(left ∥ right) (R10, R11, I2)
    end

    B-->>P: merkle_root (R13, R14, I3)

    par Persistance (R17)
        P->>P: Stocker racine
        P->>P: Stocker preuves d’inclusion (R18, R19)
        P->>P: Stocker métadonnées (fenêtre, algo, version)
    end

    Note over P: Racine = unique entrée pour<br/>horodatage/ancrage aval (R19, I4)

6bis.3 Diagramme de séquence — Partage de feuilles entre arbres (Merkle DAG)¶

Ce diagramme montre comment un même événement partagé entre deux fenêtres temporelles produit une feuille identique dans deux arbres indépendants, sans référence croisée (R22, I4, I5).

sequenceDiagram
    participant E as Événement partagé
    participant A1 as Arbre T1 (fenêtre 1)
    participant A2 as Arbre T2 (fenêtre 2)
    participant V as Vérificateur externe

    E->>A1: Inclusion dans fenêtre 1 (R7, R21)
    E->>A2: Inclusion dans fenêtre 2 (R7, R21)

    Note over A1,A2: leaf = HASH(canonical(E))<br/>Identique dans les deux arbres (I1, I5)

    A1->>A1: Construction indépendante → root_1 (R16, I4)
    A2->>A2: Construction indépendante → root_2 (R16, I4)

    Note over A1,A2: Aucune référence croisée (R22, R23, R24)

    V->>A1: Vérifier inclusion E dans root_1 (R18)
    A1-->>V: Preuve valide ✓
    V->>A2: Vérifier inclusion E dans root_2 (R18)
    A2-->>V: Preuve valide ✓

    Note over V: Vérification indépendante<br/>du système émetteur (R18, R19)

7. Cas d’Erreur¶

• E1. events[] vide → aucun arbre produit.
• E2. Événement invalide au sens de 5.0 → exclusion obligatoire.
• E3. Canonicalisation non déterministe → non-conformité.
• E4. Algorithme de hash non conforme ou non versionné → non-conformité.

8. Critères d’Acceptation¶

Chaque règle R1 à R24 DOIT être couverte par au moins un test vérifiable.

Sont considérés comme conformes uniquement les arbres pour lesquels : - la racine est déterministe, - les preuves d’inclusion sont valides hors système, - les invariants I1 à I5 sont respectés.

9. Sécurité et Conformité¶

• Objectif de conception (non testable) : la construction vise à ne pas révéler d’information sur le contenu des événements au-delà des hashes.
• L’indépendance des arbres garantit l’absence de contamination probatoire entre batchs.

10. Contrôle de Version¶

• Version : 1.0
• Epic : PD-189 Crypto
• Référence : PD-54
• Statut : Spécification canonique contractuelle