Merkle-tree artifact identity for cross-pipeline deduplication and non-determinism detection

[sjawhar]

Context

During the compositional pipeline API work, we explored using Merkle-tree-based artifact identity as the foundation for the engine. We decided to defer this in favor of the simpler path-extraction refactor, but the ideas are worth capturing.

The Idea

Artifact identity as a Merkle hash:

artifact_identity = hash(
    stage_code_fingerprint +
    input_artifact_identities +    # recursive — forms a Merkle tree
    params_hash
)

• External inputs (leaves): identity = content hash of the file
• Produced artifacts: identity = hash(code + params + input identities)
• Computed bottom-up through the DAG, before execution
• Two invocations with identical (code, inputs, params) → same identity → automatic deduplication

This is the same model used by Nix (derivation hashes), Bazel (action keys), and Buck2 (action digests).

What It Would Enable

1. Cross-pipeline deduplication: If pipeline A and pipeline B both call the same stage function with the same inputs and params, they produce the same Merkle ID → cache hit → only computed once.

2. Non-determinism detection: After execution, compare the Merkle ID (what the inputs predicted) against the content hash (what was actually produced). If two runs with the same Merkle ID produce different content hashes, the stage is non-deterministic → warn the user.

3. Hermeticity declarations: @pivot.stage(extra_inputs=[lambda: date.today()]) to make non-hermetic inputs (time, API versions, env vars) explicit in the identity hash. Plus @pivot.stage(impure=True) for truly non-deterministic stages.

Why We Deferred

• Skip detection already works well with code fingerprint + params + input file hashes. Merkle trees don't add much for the common case.
• Cross-pipeline dedup is rare in practice — how often do two pipelines call the same function with identical inputs?
• The real problem we need to solve is extracting paths from the engine/registry layer — simpler than full Merkle identity.
• Hash brittleness: Any change to the fingerprinting algorithm invalidates the entire cache.
• Over-invalidation: Adding a comment to a stage function changes its fingerprint → cache miss, even though behavior is identical.
• Hermeticity can't be enforced: Pivot stages aren't sandboxed — they can do network calls, use datetime, etc. The Merkle identity is only as good as the inputs you declare.

Storage Design (if we do implement)

• StateDB drv: prefix: drv:{merkle_id} → {output_content_hashes} for O(1) lookup
• Lock files: Keep stage-named files (user-friendly), add merkle_id field inside
• Nix hybrid model: Input-hash (Merkle) for build planning ("should I rebuild?"), content-hash for storage ("where is the result?")

Related

• Compositional pipeline API (compose.py)
• Content-addressed storage (.pivot/cache/files/) — already exists
• Path extraction from engine/registry — the prerequisite refactor