PD-54 — Plan d'implementation¶

1. Objectif¶

Ce document decrit comment implementer le mecanisme de construction d'arbres de Merkle periodiques a feuilles partagees tel que specifie dans PD-54-specification.md. L'implementation produit, pour chaque fenetre temporelle close, une racine de Merkle deterministe engageant l'integralite des evenements valides, utilisable comme unique entree d'horodatage et/ou d'ancrage externe.

2. Choix techniques retenus¶

3. Identifiants normatifs versions et registre¶

3.1 Identifiants¶

Ces identifiants DOIVENT etre presents dans les metadonnees de chaque arbre et preuve.

3.2 Registre normatif public (R18, TC-NOM-12)¶

Conformement a §5.0 de la specification, les definitions normatives associees aux identifiants DOIVENT etre : - soit publiques et accessibles independamment, - soit fournies avec la preuve elle-meme.

Registre normatif : Un document JSON public (normative-registry.json) contient les definitions completes :

{
  "registry_version": "1.0",
  "definitions": {
    "JCS-RFC8785-V1": {
      "type": "canonicalization",
      "reference": "RFC 8785 - JSON Canonicalization Scheme",
      "url": "https://datatracker.ietf.org/doc/html/rfc8785",
      "rules": [
        "Cles triees lexicographiquement (Unicode code point)",
        "Pas d'espaces superflus",
        "Nombres sans exposant si possible",
        "Encodage UTF-8 strict"
      ]
    },
    "LEX-HEX-ASC-V1": {
      "type": "leaf_ordering",
      "description": "Tri lexicographique ascendant sur representation hexadecimale lowercase des hashes",
      "algorithm": "leaves.sort((a, b) => a.hash.localeCompare(b.hash))"
    },
    "SHA256-V1": {
      "type": "hash_algorithm",
      "reference": "FIPS 180-4",
      "name": "SHA-256",
      "output_size_bytes": 32,
      "output_encoding": "hexadecimal lowercase"
    },
    "MERKLE-PROOF-V1": {
      "type": "proof_format",
      "concatenation": "binary (bytes decoded from hex)",
      "hash_input": "left_bytes || right_bytes",
      "path_position": "L = sibling a gauche, R = sibling a droite"
    }
  }
}

Inclusion dans les preuves : Chaque preuve DOIT inclure soit : - une URL vers le registre normatif public, soit - les definitions normatives inline dans le champ normative_definitions

Ceci permet a un auditeur externe de verifier la preuve sans acces au systeme emetteur (R18).

4. Architecture ciblee¶

┌─────────────────────────────────────────────────────────────────────────┐
│                        MERKLE TREE ENGINE                                │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│  ┌────────────────┐    ┌────────────────┐    ┌────────────────┐        │
│  │ EventValidator │───►│ Canonicalizer  │───►│ LeafBuilder    │        │
│  │ (R1-R3, 5.0)   │    │ (R4-R5)        │    │ (R6-R7)        │        │
│  └────────────────┘    └────────────────┘    └────────────────┘        │
│                                                      │                   │
│                                                      ▼                   │
│  ┌────────────────┐    ┌────────────────┐    ┌────────────────┐        │
│  │ WindowManager  │───►│ LeafSorter     │───►│ TreeBuilder    │        │
│  │ (R15-R16)      │    │ (R8-R9)        │    │ (R10-R12)      │        │
│  └────────────────┘    └────────────────┘    └────────────────┘        │
│                                                      │                   │
│                                                      ▼                   │
│  ┌────────────────┐    ┌────────────────┐    ┌────────────────┐        │
│  │ HashProvider   │    │ ProofGenerator │◄───│ RootFinalizer  │        │
│  │ (R20)          │    │ (R17-R19)      │    │ (R13-R14)      │        │
│  └────────────────┘    └────────────────┘    └────────────────┘        │
│                                                      │                   │
│                                                      ▼                   │
│                              ┌────────────────────────────┐             │
│                              │ MerkleDAGManager (R21-R24) │             │
│                              │ Gestion feuilles partagees │             │
│                              └────────────────────────────┘             │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘
                                      │
                                      ▼
┌─────────────────────────────────────────────────────────────────────────┐
│                           STORAGE LAYER                                  │
├─────────────────────────────────────────────────────────────────────────┤
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐    │
│  │ Trees       │  │ Leaves      │  │ Proofs      │  │ Metadata    │    │
│  │ (roots)     │  │ (shared)    │  │ (inclusion) │  │ (windows)   │    │
│  └─────────────┘  └─────────────┘  └─────────────┘  └─────────────┘    │
└─────────────────────────────────────────────────────────────────────────┘

5. Decoupage technique¶

5.1 Module EventValidator¶

Responsabilite : Valider les evenements selon les criteres de la section 5.0 de la spec.

Interface :

interface EventValidator {
  validate(event: Event, window: TimeWindow): ValidationResult;
  filterValid(events: Event[], window: TimeWindow): Event[];
}

interface Event {
  id: string;
  event_time: unknown;     // Format non contraint par la spec ; doit permettre attribution univoque a une fenetre
  payload: unknown;
}

interface TimeWindow {
  window_start: unknown;   // Format non contraint par la spec ; interprete dans window_timezone
  window_end: unknown;     // Format non contraint par la spec ; interprete dans window_timezone
  window_timezone: string; // IANA TZ (ex. "Europe/Paris")
}

type ValidationResult =
  | { valid: true }
  | { valid: false; reason: 'NO_ID' | 'NO_TIME' | 'OUT_OF_WINDOW' | 'CANONICALIZATION_FAILED' };

Regles de validation (§5.0) : 1. Identifiant present et non vide → sinon invalide 2. event_time present et parsable → sinon invalide 3. window_start <= event_time < window_end (intervalle semi-ouvert) → sinon hors fenetre 4. Canonicalisation possible → sinon invalide

Observable : Evenements invalides exclus, traces avec raison

5.2 Module Canonicalizer¶

Responsabilite : Transformer un evenement en representation canonique deterministe.

Interface :

interface Canonicalizer {
  canonicalize(event: Event): Result<Uint8Array, CanonicalizationError>;
}

type CanonicalizationError = { code: 'E3'; message: string };

Algorithme (JCS-RFC8785-V1) : 1. Serialiser l'evenement en JSON 2. Appliquer RFC 8785 : - Cles triees lexicographiquement (Unicode code point) - Pas d'espaces superflus - Nombres sans exposant si possible - Encodage UTF-8 strict 3. Retourner les octets UTF-8 du JSON canonique

Contrainte : Deux executions avec le meme evenement DOIVENT produire des octets identiques.

Observable : Representation canonique identique pour evenements identiques (TC-NOM-02)

5.3 Module LeafBuilder¶

Responsabilite : Construire une feuille a partir d'un evenement canonique.

Interface :

interface LeafBuilder {
  buildLeaf(canonicalEvent: Uint8Array): Leaf;
}

interface Leaf {
  hash: string;           // Hex lowercase, 64 chars
  eventId: string;
  treeId?: string;        // Optionnel, pour tracer l'appartenance
}

Algorithme :

leaf = SHA256(canonical_event)
return lowercase_hex(leaf)

Contrainte R7 : Une meme valeur de leaf.hash PEUT etre reutilisee dans plusieurs arbres.

Observable : leaf = HASH(canonical_event) deterministe (TC-NOM-03)

5.4 Module LeafSorter¶

Responsabilite : Trier les feuilles selon un ordre canonique deterministe.

Interface :

interface LeafSorter {
  sort(leaves: Leaf[]): Leaf[];
}

Algorithme (LEX-HEX-ASC-V1) :

return leaves.sort((a, b) => a.hash.localeCompare(b.hash))

Contrainte : L'ordre est strictement identique a chaque execution pour le meme ensemble.

Observable : Ordre final identique sur executions repetees (TC-NOM-04)

5.5 Module TreeBuilder¶

Responsabilite : Construire l'arbre de Merkle binaire a partir des feuilles triees.

Interface :

interface TreeBuilder {
  build(sortedLeaves: Leaf[]): MerkleTree;
}

interface MerkleTree {
  root: string;                    // Hash racine
  levels: string[][];              // Niveaux de l'arbre (0 = feuilles)
  leafCount: number;
}

Algorithme :

function build(leaves):
  if leaves.length == 0:
    return null  // E1: pas d'arbre

  currentLevel = leaves.map(l => l.hash)  // hashes en hex lowercase
  levels = [currentLevel]

  while currentLevel.length > 1:
    nextLevel = []
    for i = 0; i < currentLevel.length; i += 2:
      leftHex = currentLevel[i]
      rightHex = currentLevel[i + 1] ?? currentLevel[i]  // R12: duplication si impair

      // IMPORTANT (R11): Concatenation sur les BYTES, pas sur les chaines hex
      leftBytes = bytes.fromhex(leftHex)    // 32 bytes
      rightBytes = bytes.fromhex(rightHex)  // 32 bytes
      parentBytes = SHA256(leftBytes || rightBytes)  // 64 bytes en entree
      parentHex = lowercase_hex(parentBytes)

      nextLevel.push(parentHex)
    currentLevel = nextLevel
    levels.push(currentLevel)

  return {
    root: currentLevel[0],
    levels: levels,
    leafCount: leaves.length
  }

Contraintes : - R10 : Arbre strictement binaire - R11 : parent = HASH(left_bytes || right_bytes) — concatenation sur les bytes bruts (32+32=64 octets), PAS sur les chaines hex (64+64=128 caracteres) - R12 : Duplication du dernier noeud si nombre impair

IMPORTANT : L'encodage de la concatenation est explicitement defini comme binaire (bytes decodes de hex). Cette regle est documentee dans le registre normatif sous MERKLE-PROOF-V1.concatenation.

Observable : Structure binaire valide, duplication correcte (TC-NOM-05)

5.6 Module WindowManager¶

Responsabilite : Gerer les fenetres temporelles et l'attribution des evenements.

Interface :

interface WindowManager {
  createWindow(start: string, end: string, timezone: string): TimeWindow;
  getWindowForEvent(event: Event, windows: TimeWindow[]): TimeWindow | null;
  isWindowClosed(window: TimeWindow): boolean;
}

Regles : - Intervalle semi-ouvert : [window_start, window_end) - window_timezone DOIT etre un identifiant IANA TZ valide - Un evenement appartient a une unique fenetre

Mecanismes d'enforcement (R1, R15-R16, H-01, H-03) :

interface WindowManager {
  // ... existant ...

  // Enforcement de la cloture (R1, H-01)
  closeWindow(window: TimeWindow): ClosedWindow;
  isWindowClosed(window: TimeWindow): boolean;

  // Enforcement du non-chevauchement (R15-R16, H-03)
  validateNoOverlap(windows: TimeWindow[]): ValidationResult;
  registerWindow(window: TimeWindow): Result<void, OverlapError>;
}

interface ClosedWindow extends TimeWindow {
  closedAt: unknown;
  eventCount: number;
  readonly: true;  // Immutable apres cloture
}

type OverlapError = { code: 'WINDOW_OVERLAP'; windows: [TimeWindow, TimeWindow] };

Algorithme de validation non-chevauchement :

function validateNoOverlap(windows):
  sorted = windows.sortBy(w => w.window_start)
  for i = 0; i < sorted.length - 1; i++:
    if sorted[i].window_end > sorted[i+1].window_start:
      return { valid: false, overlap: [sorted[i], sorted[i+1]] }
  return { valid: true }

Algorithme de cloture :

function closeWindow(window):
  if isWindowClosed(window):
    throw "Window already closed"

  // Marquer comme close - aucun evenement supplementaire accepte
  window.readonly = true
  window.closedAt = now()

  // Persister l'etat de cloture
  persist(window)

  return window as ClosedWindow

Observable : Attribution correcte des evenements (TC-NOM-13), rejet si fenetre close ou chevauchement

5.7 Module RootFinalizer¶

Responsabilite : Finaliser et verrouiller la racine apres construction.

Interface :

interface RootFinalizer {
  finalize(tree: MerkleTree, window: TimeWindow): FinalizedTree;
  isFinalized(treeId: string): boolean;
}

interface FinalizedTree {
  treeId: string;
  root: string;
  window: TimeWindow;
  finalizedAt: unknown;   // Format non contraint ; horodatage de finalisation
  metadata: TreeMetadata;
  locked: true;
}

interface TreeMetadata {
  canonicalization_id: string;
  leaf_ordering_id: string;
  hash_algorithm_id: string;
  proof_format_id: string;
  leaf_count: number;
}

Contraintes : - R13 : La racine engage l'integralite des evenements - R14 : Aucun ajout apres finalisation

Observable : Ajout rejete apres cloture (TC-NOM-06)

5.8 Module ProofGenerator¶

Responsabilite : Generer et verifier les preuves d'inclusion.

Interface :

interface ProofGenerator {
  generateProof(tree: MerkleTree, leafHash: string): InclusionProof;
  verifyProof(proof: InclusionProof, root: string): boolean;
}

interface InclusionProof {
  leaf: string;
  root: string;
  path: ProofStep[];
  metadata: ProofMetadata;
}

interface ProofStep {
  hash: string;
  position: 'L' | 'R';  // Position du sibling
}

interface ProofMetadata {
  tree_id: string;
  window_start: unknown;   // Format non contraint
  window_end: unknown;     // Format non contraint
  window_timezone: string;
  canonicalization_id: string;
  leaf_ordering_id: string;
  hash_algorithm_id: string;
  proof_format_id: string;

  // TC-NOM-12, R18: Au moins une des deux options DOIT etre presente
  normative_registry_url?: string;       // URL vers le registre normatif public
  normative_definitions?: NormativeDefinitions;  // Definitions inline
}

interface NormativeDefinitions {
  [id: string]: {
    type?: string;
    reference?: string;
    description?: string;
    [key: string]: unknown;
  };
}

Algorithme de generation :

function generateProof(tree, leafHash):
  leafIndex = tree.levels[0].indexOf(leafHash)
  if leafIndex == -1:
    throw "Leaf not found"

  path = []
  index = leafIndex

  for level = 0; level < tree.levels.length - 1; level++:
    siblingIndex = index % 2 == 0 ? index + 1 : index - 1
    sibling = tree.levels[level][siblingIndex] ?? tree.levels[level][index]
    position = index % 2 == 0 ? 'R' : 'L'
    path.push({ hash: sibling, position: position })
    index = Math.floor(index / 2)

  return { leaf: leafHash, root: tree.root, path: path, metadata: ... }

Algorithme de verification :

function verifyProof(proof, expectedRoot):
  currentHex = proof.leaf

  for step in proof.path:
    // Decoder les hashes hex en bytes avant concatenation
    currentBytes = bytes.fromhex(currentHex)
    siblingBytes = bytes.fromhex(step.hash)

    if step.position == 'L':
      // Sibling a gauche : sibling || current
      parentBytes = SHA256(siblingBytes || currentBytes)
    else:
      // Sibling a droite : current || sibling
      parentBytes = SHA256(currentBytes || siblingBytes)

    currentHex = lowercase_hex(parentBytes)

  return currentHex == expectedRoot

IMPORTANT : La concatenation || opere sur les bytes bruts (32 octets chacun), conformement a R11 et au registre normatif MERKLE-PROOF-V1.concatenation.

Contraintes : - R18 : Verification possible hors systeme emetteur - R19 : La racine est l'unique entree pour usage aval

Observable : Preuve verifiable independamment (TC-NOM-09)

5.9 Module HashProvider¶

Responsabilite : Fournir l'algorithme de hash versionne.

Interface :

interface HashProvider {
  getAlgorithm(): HashAlgorithm;
  hash(data: Uint8Array): string;
}

interface HashAlgorithm {
  id: string;           // "SHA256-V1"
  name: string;         // "SHA-256"
  outputSize: number;   // 32 bytes
}

Contrainte R20 : L'algorithme DOIT etre nomme, versionne et appartenir a une liste autorisee.

Algorithme utilise dans cette implementation : - SHA256-V1 : SHA-256 (FIPS 180-4), sortie 32 octets

Note sur la liste autorisee : La specification (R20) exige que l'algorithme appartienne a "une liste autorisee" sans definir cette liste. Cette implementation utilise exclusivement SHA256-V1. L'extension a d'autres algorithmes (SHA-384, SHA-512) est hors perimetre de cette implementation et necessite une evolution du registre normatif.

Observable : hash_algorithm_id = "SHA256-V1" dans les metadonnees (TC-NOM-10)

5.10 Module MerkleDAGManager¶

Responsabilite : Gerer le partage de feuilles entre arbres sans reference croisee.

Interface :

interface MerkleDAGManager {
  registerLeaf(leaf: Leaf, treeId: string): void;
  getTreesForLeaf(leafHash: string): string[];
  validateNoCircularReference(trees: FinalizedTree[]): boolean;
}

Contraintes : - R21 : Une feuille PEUT appartenir a plusieurs arbres - R22 : Aucun arbre NE DOIT referencer un autre arbre - R23 : Le graphe DOIT etre acyclique (DAG) - R24 : Pas de dependance temporelle, logique ou juridique

Observable : Racines independantes, pas de reference croisee (TC-NOM-11)

6. Schema de stockage¶

-- Arbres finalises
CREATE TABLE merkle_trees (
  tree_id UUID PRIMARY KEY,
  root VARCHAR(64) NOT NULL,
  window_start TIMESTAMP WITH TIME ZONE NOT NULL,
  window_end TIMESTAMP WITH TIME ZONE NOT NULL,
  window_timezone VARCHAR(50) NOT NULL,
  leaf_count INTEGER NOT NULL,
  finalized_at TIMESTAMP WITH TIME ZONE NOT NULL,
  canonicalization_id VARCHAR(30) NOT NULL,
  leaf_ordering_id VARCHAR(30) NOT NULL,
  hash_algorithm_id VARCHAR(30) NOT NULL,
  proof_format_id VARCHAR(30) NOT NULL,
  locked BOOLEAN NOT NULL DEFAULT TRUE,

  CONSTRAINT chk_root_format CHECK (root ~ '^[a-f0-9]{64}$'),
  CONSTRAINT chk_window_order CHECK (window_start < window_end),
  CONSTRAINT chk_locked CHECK (locked = TRUE)
);

-- Feuilles (partagees potentiellement)
CREATE TABLE merkle_leaves (
  leaf_hash VARCHAR(64) NOT NULL,
  event_id UUID NOT NULL,
  tree_id UUID NOT NULL REFERENCES merkle_trees(tree_id),
  leaf_index INTEGER NOT NULL,
  created_at TIMESTAMP WITH TIME ZONE NOT NULL,

  PRIMARY KEY (tree_id, leaf_hash),
  CONSTRAINT chk_leaf_format CHECK (leaf_hash ~ '^[a-f0-9]{64}$')
);

-- Index pour partage de feuilles
CREATE INDEX idx_leaves_by_hash ON merkle_leaves(leaf_hash);

-- Preuves d'inclusion
CREATE TABLE inclusion_proofs (
  proof_id UUID PRIMARY KEY,
  tree_id UUID NOT NULL REFERENCES merkle_trees(tree_id),
  leaf_hash VARCHAR(64) NOT NULL,
  proof_path JSONB NOT NULL,
  created_at TIMESTAMP WITH TIME ZONE NOT NULL,

  CONSTRAINT fk_leaf FOREIGN KEY (tree_id, leaf_hash)
    REFERENCES merkle_leaves(tree_id, leaf_hash)
);

-- Niveaux de l'arbre (optionnel, pour reconstruction)
CREATE TABLE tree_levels (
  tree_id UUID NOT NULL REFERENCES merkle_trees(tree_id),
  level_index INTEGER NOT NULL,
  node_index INTEGER NOT NULL,
  node_hash VARCHAR(64) NOT NULL,

  PRIMARY KEY (tree_id, level_index, node_index)
);

7. Flux detailles¶

7.1 Flux de construction d'arbre¶

                              events[]
                                 │
                                 ▼
┌─────────────────────────────────────────────────────────────┐
│ 1. VALIDATION (EventValidator)                               │
│    - Filtrer events[] pour la fenetre [start, end)          │
│    - Exclure evenements invalides (E2)                       │
│    - Si vide → E1, pas d'arbre                              │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
┌─────────────────────────────────────────────────────────────┐
│ 2. CANONICALISATION (Canonicalizer)                          │
│    - Pour chaque event: canonical = JCS(event)              │
│    - Si echec → E3, exclure                                 │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
┌─────────────────────────────────────────────────────────────┐
│ 3. CONSTRUCTION FEUILLES (LeafBuilder)                       │
│    - Pour chaque canonical: leaf = SHA256(canonical)        │
│    - Encoder en hex lowercase                               │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
┌─────────────────────────────────────────────────────────────┐
│ 4. TRI (LeafSorter)                                          │
│    - Trier feuilles par ordre lexicographique ascendant     │
│    - Ordre deterministe garanti                             │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
┌─────────────────────────────────────────────────────────────┐
│ 5. CONSTRUCTION ARBRE (TreeBuilder)                          │
│    - Niveau 0 = feuilles triees                             │
│    - Pour chaque niveau:                                    │
│      - Grouper par paires                                   │
│      - Si impair: dupliquer dernier                         │
│      - parent = SHA256(left || right)                       │
│    - Repeter jusqu'a racine unique                          │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
┌─────────────────────────────────────────────────────────────┐
│ 6. FINALISATION (RootFinalizer)                              │
│    - Associer metadonnees (window, algorithms)              │
│    - Verrouiller l'arbre (locked = true)                    │
│    - Persister racine et structure                          │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
┌─────────────────────────────────────────────────────────────┐
│ 7. GENERATION PREUVES (ProofGenerator)                       │
│    - Pour chaque feuille: generer chemin d'inclusion        │
│    - Persister preuves avec metadonnees                     │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
                          FinalizedTree
                     (root, proofs, metadata)

7.2 Flux de verification independante¶

┌─────────────────────────────────────────────────────────────┐
│                    VERIFICATEUR EXTERNE                      │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 │ Recoit: InclusionProof
                                 │
                                 ▼
┌─────────────────────────────────────────────────────────────┐
│ 1. EXTRAIRE METADONNEES                                      │
│    - hash_algorithm_id → determiner fonction hash           │
│    - leaf, root, path                                       │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
┌─────────────────────────────────────────────────────────────┐
│ 2. RECALCULER LA RACINE                                      │
│    current = leaf                                           │
│    for step in path:                                        │
│      if step.position == 'L':                               │
│        current = HASH(step.hash || current)                 │
│      else:                                                  │
│        current = HASH(current || step.hash)                 │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
┌─────────────────────────────────────────────────────────────┐
│ 3. COMPARER                                                  │
│    return current == proof.root                             │
└─────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
                          VALIDE / INVALIDE

7.3 Diagrammes Mermaid¶

7.3.1 Graphe de dependances des modules¶

graph TD
    EV[EventValidator<br/><i>R1-R3, 5.0</i>] --> CA[Canonicalizer<br/><i>R4-R5</i>]
    CA --> LB[LeafBuilder<br/><i>R6-R7</i>]
    LB --> LS[LeafSorter<br/><i>R8-R9</i>]
    LS --> TB[TreeBuilder<br/><i>R10-R12</i>]
    TB --> RF[RootFinalizer<br/><i>R13-R14</i>]
    RF --> PG[ProofGenerator<br/><i>R17-R19</i>]
    PG --> DAG[MerkleDAGManager<br/><i>R21-R24</i>]

    HP[HashProvider<br/><i>R20</i>] -.->|SHA-256| LB
    HP -.->|SHA-256| TB
    HP -.->|SHA-256| PG

    WM[WindowManager<br/><i>R15-R16</i>] -->|fenetre close| EV

    DAG --> SL[(Storage Layer)]
    RF --> SL

    classDef engine fill:#e8f4fd,stroke:#2196f3
    classDef infra fill:#fff3e0,stroke:#ff9800
    classDef storage fill:#e8f5e9,stroke:#4caf50

    class EV,CA,LB,LS,TB,RF,PG,DAG engine
    class HP,WM infra
    class SL storage

7.3.2 Sequence de construction d'arbre (flux principal)¶

sequenceDiagram
    participant WM as WindowManager
    participant EV as EventValidator
    participant CA as Canonicalizer
    participant LB as LeafBuilder
    participant HP as HashProvider
    participant LS as LeafSorter
    participant TB as TreeBuilder
    participant RF as RootFinalizer
    participant PG as ProofGenerator
    participant DAG as MerkleDAGManager
    participant DB as Storage Layer

    WM->>EV: fenetre close [start, end)
    EV->>EV: filtrer events valides (R1-R3)
    alt aucun event valide
        EV-->>WM: E1 — pas d'arbre
    end
    EV->>CA: events[] valides
    CA->>CA: JCS(event) pour chaque event (R4-R5)
    alt echec canonicalisation
        CA-->>EV: E3 — event exclu
    end
    CA->>LB: canonical[]
    LB->>HP: demande SHA-256
    HP-->>LB: hash hex lowercase
    LB->>LS: leaves[]
    LS->>LS: tri lexicographique ascendant (R8-R9)
    LS->>TB: sorted_leaves[]
    loop chaque niveau
        TB->>HP: SHA-256(left || right)
        HP-->>TB: parent hash
        Note over TB: si impair, dupliquer dernier noeud
    end
    TB->>RF: arbre complet
    RF->>RF: associer metadonnees + locked=true (R13-R14)
    RF->>DB: persister racine + structure
    RF->>PG: arbre finalise
    loop chaque feuille
        PG->>PG: calculer chemin d'inclusion (R17-R19)
    end
    PG->>DAG: preuves generees
    DAG->>DAG: resoudre feuilles partagees (R21-R24)
    DAG->>DB: persister preuves + metadonnees DAG

7.3.3 Sequence de verification independante¶

sequenceDiagram
    participant V as Verificateur externe
    participant P as InclusionProof
    participant H as Fonction hash

    V->>P: extraire leaf, root, path, hash_algorithm_id
    V->>V: current = leaf
    loop chaque step in path
        alt step.position == 'L'
            V->>H: SHA-256(step.hash || current)
        else step.position == 'R'
            V->>H: SHA-256(current || step.hash)
        end
        H-->>V: nouveau current
    end
    V->>V: comparer current == proof.root
    alt match
        V-->>V: VALIDE
    else mismatch
        V-->>V: INVALIDE
    end

8. Mapping Invariants → Mecanismes techniques¶

9. Mapping Regles normatives → Tests¶

10. Gestion des erreurs¶

Observabilite : - Chaque erreur genere une trace structuree - Les erreurs E2 n'empechent pas la construction (exclusion) - Les erreurs E1, E3, E4 empechent la construction

11. Structure des preuves d'inclusion (MERKLE-PROOF-V1)¶

11.1 Format JSON¶

{
  "version": "MERKLE-PROOF-V1",
  "leaf": "a1b2c3d4...",
  "root": "e5f6g7h8...",
  "path": [
    { "hash": "1234abcd...", "position": "R" },
    { "hash": "5678efgh...", "position": "L" },
    { "hash": "9012ijkl...", "position": "R" }
  ],
  "metadata": {
    "tree_id": "uuid-xxx",
    "window_start": "...",
    "window_end": "...",
    "window_timezone": "Europe/Paris",
    "canonicalization_id": "JCS-RFC8785-V1",
    "leaf_ordering_id": "LEX-HEX-ASC-V1",
    "hash_algorithm_id": "SHA256-V1",
    "proof_format_id": "MERKLE-PROOF-V1",

    // Option 1: URL vers le registre normatif public (TC-NOM-12, R18)
    "normative_registry_url": "https://example.com/normative-registry.json",

    // Option 2: Definitions normatives inline (alternative si URL non disponible)
    "normative_definitions": {
      "SHA256-V1": { "reference": "FIPS 180-4", "output_size_bytes": 32 },
      "MERKLE-PROOF-V1": { "concatenation": "binary", "hash_input": "left_bytes || right_bytes" }
      // ... autres definitions
    }
  }
}

Note TC-NOM-12 : Au moins une des deux options (normative_registry_url ou normative_definitions) DOIT etre presente pour permettre la verification independante (R18).

11.2 Algorithme de verification¶

def verify_proof(proof, expected_root):
    """
    Verification independante - aucune dependance au systeme emetteur.

    IMPORTANT: La concatenation s'effectue sur les BYTES bruts (32 octets chacun),
    conformement a R11 et au registre normatif MERKLE-PROOF-V1.concatenation.
    """

    # 1. Charger les definitions normatives (depuis URL ou inline)
    definitions = load_normative_definitions(proof)

    # 2. Determiner l'algorithme de hash
    algo = proof['metadata']['hash_algorithm_id']
    if algo not in definitions:
        raise UnsupportedAlgorithm(algo)

    hash_fn = get_hash_function(definitions[algo])  # ex: sha256

    # 3. Partir de la feuille (decoder hex -> bytes)
    current = bytes.fromhex(proof['leaf'])  # 32 bytes

    # 4. Remonter le chemin
    for step in proof['path']:
        sibling = bytes.fromhex(step['hash'])  # 32 bytes

        # Concatenation sur les BYTES (32 + 32 = 64 octets)
        if step['position'] == 'L':
            # Sibling a gauche : sibling || current
            current = hash_fn(sibling + current)
        else:
            # Sibling a droite : current || sibling
            current = hash_fn(current + sibling)

    # 5. Comparer avec la racine attendue
    computed_root = current.hex()  # Reencode en hex lowercase
    return computed_root == expected_root


def load_normative_definitions(proof):
    """Charge les definitions normatives depuis l'URL ou inline."""
    if 'normative_registry_url' in proof['metadata']:
        return fetch_json(proof['metadata']['normative_registry_url'])
    elif 'normative_definitions' in proof['metadata']:
        return proof['metadata']['normative_definitions']
    else:
        raise MissingNormativeDefinitions()

12. Securite et contraintes¶

12.1 Independance des arbres¶

• Chaque arbre est auto-suffisant (racine + preuves + metadonnees)
• Pas de FK entre tables merkle_trees
• Validation DAG : parcours du graphe pour detecter cycles

12.2 Confidentialite (objectif de conception, non testable - Spec §9)¶

Note : Conformement a §9 de la specification, la confidentialite est un objectif de conception et non une exigence testable. Les points ci-dessous sont des proprietes visees, pas des contraintes contractuelles :

• Seuls les hashes sont exposes (pas les evenements en clair)
• La racine ne revele pas le contenu des evenements
• Les preuves minimisent l'information divulguee

Ces proprietes ne font pas l'objet de tests d'acceptation.

12.3 Integrite¶

• Verrouillage post-finalisation (locked=true)
• Contraintes DB pour empecher modification
• Hash cryptographique pour detecter alteration

12.4 Retrocompatibilite¶

• Toute evolution de version des identifiants DOIT etre retrocompatible
• Meme ensemble d'evenements → meme racine (invariant contractuel)

13. Hypotheses techniques¶

13.1 Hypotheses heritees de la spec¶

13.2 Hypotheses d'implementation¶

14. Points de vigilance¶

14.1 Risques¶

14.2 Tests de non-regression¶

• TC-NR-01 : Meme entree + nouvelle version → racine inchangee
• TC-NR-02 : Ajout d'un arbre → arbres existants inchanges

14.3 Tests adversariaux¶

• TC-NEG-01 : Injection evenement post-cloture → rejet
• TC-NEG-02 : Collision volontaire entree → racine differente

14.4 Cas limites¶

• 1 evenement : arbre a 1 feuille, racine = feuille
• 2 evenements : arbre minimal
• Nombre impair : verification duplication correcte
• Feuilles identiques dans le meme arbre : tri stable requis

15. Hors perimetre (rappel)¶

Explicitement exclus de cette implementation :

• Horodatage eIDAS (RFC 3161)
• Ancrage blockchain
• Signature cryptographique des racines
• Transport, stockage physique ou replication
• Validation metier ou semantique des evenements

16. Vecteurs de test de reference¶

VEC-01 : Arbre minimal (2 feuilles)¶

Events:
  - { id: "evt-1", event_time: "2024-01-01T10:00:00+01:00", payload: { type: "A" } }
  - { id: "evt-2", event_time: "2024-01-01T11:00:00+01:00", payload: { type: "B" } }

Window: [2024-01-01T00:00:00+01:00, 2024-01-02T00:00:00+01:00), Europe/Paris

Canonicals (JCS):
  - evt-1: {"event_time":"2024-01-01T10:00:00+01:00","id":"evt-1","payload":{"type":"A"}}
  - evt-2: {"event_time":"2024-01-01T11:00:00+01:00","id":"evt-2","payload":{"type":"B"}}

Leaves (SHA256, hex):
  - leaf_1 = SHA256(canonical_1) = <hash_1>
  - leaf_2 = SHA256(canonical_2) = <hash_2>

Sorted (lexicographic):
  - [min(hash_1, hash_2), max(hash_1, hash_2)]

Root:
  - root = SHA256(sorted[0] || sorted[1])

VEC-02 : Arbre impair (3 feuilles)¶

Leaves: [L1, L2, L3] (sorted)

Level 0: [L1, L2, L3]
Level 1: [H(L1||L2), H(L3||L3)]  // L3 duplique
Level 2: [H(Level1[0]||Level1[1])] = Root

VEC-03 : Feuille partagee¶

Tree A: events [E1, E2]
Tree B: events [E2, E3]

E2 produit la meme feuille dans les deux arbres.
Root_A != Root_B (car ensembles differents)
Proof pour E2 dans A valide contre Root_A
Proof pour E2 dans B valide contre Root_B

17. Checklist de livraison¶

• Module EventValidator implemente et teste (TC-NOM-01, TC-ERR-02)
• Module Canonicalizer implemente (JCS-RFC8785-V1) et teste (TC-NOM-02, TC-ERR-03)
• Module LeafBuilder implemente et teste (TC-NOM-03)
• Module LeafSorter implemente et teste (TC-NOM-04)
• Module TreeBuilder implemente et teste (TC-NOM-05)
• Module WindowManager implemente et teste (TC-NOM-07, TC-NOM-13)
• Module RootFinalizer implemente et teste (TC-NOM-06)
• Module ProofGenerator implemente et teste (TC-NOM-09)
• Module HashProvider implemente et teste (TC-NOM-10, TC-ERR-04)
• Module MerkleDAGManager implemente et teste (TC-NOM-11)
• Schema de stockage deploye (TC-NOM-08)
• Metadonnees normatives completes (TC-NOM-12)
• Tests d'invariants passes (TC-INV-01 a TC-INV-05)
• Tests de non-regression passes (TC-NR-01, TC-NR-02)
• Tests adversariaux passes (TC-NEG-01, TC-NEG-02)
• Verificateur independant fonctionnel
• Documentation API

References¶

• Specification : PD-54-specification.md
• Tests : PD-54-tests.md
• Epic : PD-189 Crypto
• JIRA : PD-54
• Standards : RFC 8785 (JCS), RFC 6962 (Certificate Transparency), FIPS 180-4 (SHA-256)