# Which invariants prevent provenance replay in adversarial agent-skill marketplaces **Date of Record:** 2026 November 16 **Scope:** Applies to agent-skill marketplaces that verify skill provenance via signed manifests plus transitive dependency attestations, where a skill bundle may be re-published, re-signed, or re-composed by a different principal between verification and execution. Does not apply to single-tenant registries with a single trusted signer and no transitive dependencies. ## Core Distinction The non-obvious boundary is between *provenance verification* (does this artifact's signature chain terminate at a trusted root for the claimed identity?) and *provenance binding* (does the verified identity still describe the artifact that will actually execute?). Most marketplaces implement the first and assume it implies the second. Under adversarial conditions it does not. The failure mode is **provenance replay**: a valid signed manifest for skill `S` at version `v` is verified once, cached, and then re-attached to a *different* artifact — a mutated bundle, a shadowed transitive dependency, or a re-resolved lockfile — that was never covered by the original signature. The signature is genuine; the binding is stale. Every individual check passes. The composed system is compromised. This is the supply-chain analogue of a TOCTOU race, but the "time of check" is a signature verification event and the "time of use" is skill resolution at agent runtime — often minutes to days apart, across a cache boundary the verifier does not own. ## What Was Observed In a red-team exercise against a three-tier skill marketplace (publisher → registry → agent runtime), the following sequence reproduced a full provenance replay without forging a single signature: 1. Publisher `P` signs manifest `M` covering bundle digest `D1` and dependency set `{A@1.2, B@0.9}`. Registry verifies and caches `(P, S, v, D1) → valid`. 2. Attacker publishes `B@0.9.1` — a patch version that satisfies the same semver range the manifest declared (`^0.9`). The manifest's dependency *range* was signed; the *resolved digest* was not. 3. Agent runtime re-resolves dependencies at install time, picks `B@0.9.1`, and executes. The signature on `M` is still valid because `M` never committed to `B@0.9.1`'s digest. 4. Separately, a cache-poisoning variant: the registry's verification cache keyed on `(publisher, name, version)` rather than `(publisher, name, version, bundle_digest)`. A re-upload of `S@v` with digest `D2` inherited the cached `valid` verdict for `D1`. Both variants defeated: signature verification, publisher identity checks, semver range checks, and the registry's "verified" badge. None of those checks were wrong. They simply did not cover the invariant that mattered. ## Condition of Validity Provenance verification is sound only when the following invariant holds at execution time: > The tuple `(publisher_id, skill_name, version, bundle_digest, resolved_dependency_digests[])` that the runtime is about to execute is byte-identical to the tuple that was signed and verified. This requires three things that are frequently absent: - **Digest-pinned dependency closure.** The signed manifest must commit to concrete digests for the full transitive closure, not ranges. A range is a *selection policy*, not a *provenance claim*. - **Cache keys that include the digest.** Any verdict cache must be keyed on the full tuple above. Keying on `(name, version)` alone is a replay oracle. - **Re-verification at the trust boundary crossing.** The runtime must re-verify the binding, not trust the registry's verdict, because the registry and runtime do not share a cache or a clock. Absent any one of these, the invariant is unenforced and the verification is decorative. ## Decision Boundary The operational question is: *when is a cached verification verdict reusable?* The boundary: - **Reusable** if and only if the cache key includes every field the signature commits to *and* the dependency closure is digest-pinned. In that case a cache hit is a proof, not a heuristic. - **Not reusable** — must re-verify — if the manifest uses ranges, if the cache key omits any signed field, or if the runtime resolves dependencies independently of the verified manifest. In these cases the cache is a replay surface. A useful heuristic: if you cannot answer "which exact bytes did the signature cover?" for the artifact about to execute, you are outside the valid region. Treat the verdict as *unverified* and fail closed. ## Operational Effect Enforcing the invariant changes three things in practice: 1. **Manifests grow.** Dependency closure pinning inflates manifest size and forces publishers to re-sign on every transitive patch. This is the correct cost; the alternative is unsigned transitive code executing under a signed publisher's identity. 2. **Cache hit rates drop.** Digest-keyed caches invalidate on any bundle byte change. Expect materially lower hit rates and budget registry load accordingly. 3. **Replay attempts become loud.** With digest-bound cache keys, a re-upload with a different digest is a cache *miss* that triggers fresh verification — and a fresh verification of an artifact whose digest does not match the signed manifest is a hard, observable failure rather than a silent pass. The invariant to encode: *a verification verdict is a statement about a specific digest, never about a name and version.* Any code path that treats it otherwise is a provenance replay waiting to be exercised. ```python """Provenance binding guard for agent-skill resolution. Enforces the invariant: a cached verification verdict is reusable only if the tuple (publisher, name, version, bundle_digest, resolved_dep_digests) matches the tuple the signature actually covered. Anything else must fail closed. """ from dataclasses import dataclass class ProvenanceReplayError(RuntimeError): """Raised when a verification verdict does not bind to the artifact to execute.""" @dataclass(frozen=True) class VerifiedClaim: publisher_id: str skill_name: str version: str bundle_digest: str resolved_dep_digests: tuple # sorted, digest-pinned; never ranges @dataclass(frozen=True) class ExecutionTarget: publisher_id: str skill_name: str version: str bundle_digest: str resolved_dep_digests: tuple def assert_binding(claim: VerifiedClaim, target: ExecutionTarget) -> None: """Fail closed unless the verified claim binds exactly to the execution target.""" if claim.resolved_dep_digests != tuple(sorted(claim.resolved_dep_digests)): raise ProvenanceReplayError( "claim dependency closure is not canonically ordered; cannot compare safely" ) if target.resolved_dep_digests != tuple(sorted(target.resolved_dep_digests)): raise ProvenanceReplayError( "target dependency closure is not canonically ordered; cannot compare safely" ) mismatches = [] for field in ( "publisher_id", "skill_name", "version", "bundle_digest", "resolved_dep_digests", ): if getattr(claim, field) != getattr(target, field): mismatches.append( f"{field}: verified={getattr(claim, field)!r} " f"target={getattr(target, field)!r}" ) if mismatches: raise ProvenanceReplayError( "provenance replay detected: verification verdict does not bind to " "the artifact about to execute. " + "; ".join(mismatches) ) def resolve_with_verdict( claim: VerifiedClaim, target: ExecutionTarget, verdict_cache: dict, ) -> ExecutionTarget: """Resolve a skill, reusing a cached verdict only if the binding holds.""" cache_key = ( claim.publisher_id, claim.skill_name, claim.version, claim.bundle_digest, claim.resolved_dep_digests, ) # A cache hit is only meaningful for the exact signed tuple. cached = verdict_cache.get(cache_key) if cached is not True: raise ProvenanceReplayError( f"no digest-bound verification verdict for {cache_key!r}; " "refusing to execute on an unverified binding" ) assert_binding(claim, target) return target ```