Provenance Graphs, Hashes, Locators, Trust, and Transformations

An evidence envelope answers what encoded artifact did this system acquire? It does not answer:

which exact pixels produced an OCR span;
which audio interval produced a transcript;
which four inputs influenced an incident summary;
which implementation and parameters performed each transformation;
whether a parent was authenticated, merely intact, licensed, or human-approved;
whether any of those judgments apply to a derivative.

Those are provenance questions. They cannot be repaired later by adding a source: String field to the final answer. A production system needs the derivation structure while it processes evidence. Otherwise it cannot construct precise citations, invalidate descendants, reproduce a transform, explain a result, apply retention, or distinguish byte integrity from human trust.

This chapter builds that structure in mosaic-evidence. Four acquired roots—a note, screenshot, voice note, and screen recording—produce OCR, a transcript, and an incident summary. Each edge names an input role and exact locator. Each transformation carries implementation and parameter identity. The graph rejects missing parents, duplicate IDs, modality-incompatible locators, malformed ranges, and noncontiguous input order. Trust assertions attach separately and do not flow through an edge.

The result is intentionally smaller than a complete provenance interchange or signing system. It is the executable core on which later decoding, observations, citations, C2PA verification, retention, and Signal Room can depend.

Learning objectives

By the end you will be able to:

distinguish artifact identity, evidence identity, derivation identity, and trust decisions;
map the implementation to provenance entities, activities, agents, usage, and generation;
build a directed acyclic derivation graph without accepting forward references;
explain why “activity used A and generated B” does not always prove B was derived from A;
make input order and semantic roles part of a reproducible transformation contract;
create typed locators for text, images, audio, and video without mixing coordinate systems;
use half-open intervals and state their boundary semantics;
explain why numeric locator validation cannot rely on unverified declared dimensions;
frame hash inputs unambiguously instead of concatenating strings or hashing incidental JSON;
identify every field included in the version-1 derivation fingerprint;
explain what the fingerprint omits and why;
separate an implementation release from a transform name;
hash parameters without exposing sensitive configuration in the graph;
treat a deterministic flag as a falsifiable claim rather than proof;
model trust as a typed, actor- and policy-versioned assertion;
preserve verified, rejected, and indeterminate as different outcomes;
explain why parent trust must not automatically propagate to OCR, transcripts, summaries, or generated media;
state what SHA-256, signatures, C2PA manifests, and human approval each can and cannot establish;
query transitive lineage in stable order;
design import, persistence, signing, invalidation, and retention extensions safely;
investigate provenance failures without silently repairing history.

Prerequisites and dependency order

Read One evidence envelope without erasing modality first. It defines immutable acquired/derived artifacts, strict modality bodies, source classes, and content-digest references. Also review:

Content-addressed artifacts for verified byte storage;
Serde contracts for strict representations;
Model release identity for the difference between a friendly alias and an executable release;
Sampling and reproducibility for bounded determinism claims.

This chapter deliberately precedes the modality decoders. The graph can validate the shape of an image locator now, but only Chapter 4 can establish verified oriented pixel dimensions. It can validate a time interval now, but the audio/video chapters establish sample clocks, stream time bases, codec delay, cuts, and variable-frame-rate behavior. Provenance records must name those later coordinate spaces rather than pretending acquisition declarations were verified.

Completion artifact

Run:

cd rust/rust-ai-engineering
cargo run -q -p mosaic-evidence --example provenance_graph

The example reads the four roots from:

fixtures/evidence/envelopes.jsonl

It then executes this derivation plan:

dashboard-shot pixels [100,50,600,200] ──OCR──────────────▶ ocr-text
operator-note time [0,3000) ms ─────────speech-to-text────▶ transcript-text

incident-note bytes [0,80) ──────────────┐
ocr-text whole ───────────────────────────┤
transcript-text whole ────────────────────┼─incident-synthesis─▶ incident-summary
screen-recording [4000,6000) ms + region ┘

The output contains seven graph nodes, three exact derivation fingerprints, six transitive ancestors for the summary, and trust counts proving that an integrity assertion on dashboard-shot did not appear on ocr-text:

{
  "node_count": 7,
  "summary_lineage": [
    "dashboard-shot",
    "incident-note",
    "ocr-text",
    "operator-note",
    "screen-recording",
    "transcript-text"
  ],
  "trust_assertion_counts": {
    "dashboard-shot": 1,
    "ocr-text": 0,
    "incident-summary": 1
  }
}

The exact fingerprints are regression evidence. They change if an input position, role, parent, locator, output digest, transform release, parameter digest, or deterministic claim changes.

First principles: four identities, not one

Systems often call every hash an “artifact ID.” That erases different questions.

Identity	Question	Example
Artifact identity	Which exact encoded bytes?	SHA-256 of the PNG
Evidence identity	Which logical record in this scope?	`dashboard-shot`
Derivation identity	Which output, inputs, locations, transform, release, and parameter set?	OCR fingerprint
Trust assertion identity/context	Who decided what, under which policy and supporting evidence?	integrity policy v1 verified the screenshot

The encoded artifact digest does not contain acquisition context. Two uploads can intentionally point to the same bytes but have different owners, consent, retention, or acquisition paths.

The evidence ID is a bounded graph key, not proof of bytes. It must be unique within the graph and scoped by tenant/collection/run in persistence.

The derivation fingerprint binds an output to one transformation recipe and ordered set of parent selections. It does not prove the transformation actually ran honestly.

A trust assertion is a policy decision about one subject. It must not be smuggled into the artifact hash or treated as an immutable fact about every descendant.

Keeping these identities separate lets the system re-evaluate policy without changing artifact history and re-run a transform without rewriting acquisition history.

Provenance is a graph of influence

The W3C PROV Data Model defines provenance around entities, activities, and agents. Activities use and generate entities; derivations connect a generated entity to an entity that influenced it. The distinction matters: merely reading a configuration file during an OCR run does not necessarily make the OCR text derived from that file in the same semantic sense as it is derived from the image.

The chapter’s compact mapping is:

W3C PROV concept	This implementation
Entity	`EvidenceEnvelope` root or derived output
Activity	`TransformReceipt` plus the derivation event
Usage	ordered `EvidenceInput`
Role	`EvidenceInput.role`
Derivation/generation	`DerivationRecord`
Agent/responsibility	future execution receipt; trust `asserted_by` is only the trust actor
Bundle/provenance of provenance	future signed/persisted graph export

Do not overclaim this mapping. TransformReceipt currently records a transform name, implementation release, parameter digest, and determinism claim. It does not yet record start/end time, worker, host, dependency closure, hardware, random stream, signature, or operator. Those belong in a future execution receipt.

The graph records declared influence. An input role should answer how the parent influenced the output:

image_source
audio_source
operator_text
dashboard_ocr
voice_transcript
screen_region

input_1 is syntactically valid but semantically weak. Roles should come from a versioned, domain-specific vocabulary once the pipeline stabilizes.

Root and derived nodes

The internal node is deliberately not publicly constructible:

enum GraphNode {
    Root(EvidenceEnvelope),
    Derived(DerivationRecord),
}

add_root validates the envelope and refuses an existing ID:

pub fn add_root(
    &mut self,
    envelope: EvidenceEnvelope,
) -> Result<(), ProvenanceError>

add_derivation validates:

the derived envelope;
source_kind == system_record;
at least one and at most 256 inputs;
contiguous input positions beginning at zero;
bounded printable transform/release/role labels;
each locator’s numeric shape;
output-ID uniqueness;
no self-reference;
every parent already exists;
locator compatibility with the parent modality.

Only after every check succeeds does it compute the fingerprint and insert the node.

Why a derived output must be a `system_record`

An OCR result was created by the pipeline, not acquired as a user upload. If a derived envelope retains user_upload, later policy cannot distinguish original evidence from a system interpretation. The explicit source class is not an authenticity claim; it is a state-machine invariant.

Why an input is mandatory

A zero-input generated artifact may be valid—for example, text-to-image from an internal task specification—but then the task specification, prompt artifact, seed/noise state, or other causal input should be represented explicitly. Version 1 rejects empty derivations because “came from nothing” prevents reproduction and invalidation. A future root-like generation event needs a separate, carefully specified constructor.

Constructing a DAG by admission order

The graph is acyclic because it only admits a derivation whose parents are already present. Every edge therefore points from a later insertion to an earlier insertion:

new node ──uses──▶ existing parent

A cycle would require some existing ancestor to point to the not-yet-inserted node, which cannot happen through the public API. The explicit self-reference check gives the most useful error for the one-node case.

This is stronger and cheaper than “insert anything, detect cycles later” for a live processing pipeline:

missing parents fail at the boundary;
traversal cannot loop;
a partial failed insert does not mutate the graph;
topological construction order is already known;
fingerprints can be computed after parent validation.

It has a trade-off: unordered graph imports and mutually referenced external manifests cannot be loaded directly. A persistent/import path should:

strictly parse all records under count/size limits;
reject duplicate IDs;
resolve external references under authorization;
topologically sort;
report missing parents separately from cycles;
insert in the sorted order;
preserve original signed/imported bytes;
compare recomputed fingerprints;
commit atomically.

Never “fix” a cycle by dropping one edge. That rewrites the provenance claim.

Ordered inputs are semantic

An input carries:

pub struct EvidenceInput {
    pub position: u16,
    pub role: String,
    pub parent_id: EvidenceId,
    pub locator: Locator,
}

Position is explicit, unique, and contiguous. The vector order alone would work inside one Rust process, but explicit positions make serialized records self-checking and expose accidental reordering.

Order can change output semantics:

system/context/user prompt pieces;
reference image versus mask;
positive versus negative example;
left/right stereo or before/after frame;
ranked retrieved passages;
primary evidence versus counterevidence.

The fingerprint includes both position and role. Two recipes using the same parents but swapping roles are different derivations.

For truly unordered inputs, canonicalize them under a declared transform contract before constructing the record—for example, sort exact content digests and use a transform version that defines set semantics. Do not silently sort an order-sensitive vector in generic provenance code.

Typed locators preserve modality

A parent ID alone can cite an entire two-hour video when the claim depended on a two-second region. The locator enum keeps each coordinate system visible:

pub enum Locator {
    Whole,
    TextBytes {
        start: u64,
        end_exclusive: u64,
    },
    ImagePixels {
        x: u32,
        y: u32,
        width: u32,
        height: u32,
        coordinate_space: String,
    },
    TimeMilliseconds {
        start: u64,
        end_exclusive: u64,
    },
    VideoRegion {
        start_ms: u64,
        end_exclusive_ms: u64,
        x: u32,
        y: u32,
        width: u32,
        height: u32,
        coordinate_space: String,
    },
}

Compatibility is closed and explicit:

Parent modality	Allowed locators
Text	whole, text bytes
Image	whole, image pixels
Audio	whole, time
Video	whole, time, spatiotemporal video region

Using an audio time locator against an image returns LocatorModalityMismatch; it does not become a generic JSON object that later code guesses how to interpret.

Why text uses byte offsets in version 1

Rust strings are UTF-8 bytes, and byte offsets can select exact source bytes without pretending Unicode scalar, grapheme, token, line/column, and rendered glyph indices are interchangeable. A consumer must still verify that start/end fall on valid boundaries for the selected operation.

Later normalized text needs a new coordinate space and mappings back to original bytes. Never apply original byte offsets directly to normalized/re-encoded text.

Why coordinates name a space

x=100 is meaningless unless the consumer knows whether it addresses:

encoded dimensions before orientation;
decoded pixels after EXIF rotation;
resized model input;
normalized [0,1] coordinates;
display/CSS pixels;
an extracted frame with its own crop.

The example names decoded-orientation-v1 and decoded-video-v1. These are bounded labels today. Production should use registered coordinate-space contracts whose release defines origin, axes, units, orientation, inclusivity, and mapping to the parent.

Half-open ranges

Text/time ranges are [start, end_exclusive). The start belongs to the selection; the end does not. The W3C Media Fragments URI recommendation uses the same half-open temporal convention, and the W3C Web Annotation Data Model defines range selectors with inclusive starts and exclusive ends.

Half-open intervals provide:

length = end - start
[0, 10) followed by [10, 20) has no gap or overlap
empty selection is exactly start == end

Version 1 rejects empty/reversed ranges and rejects zero/overflowing rectangular geometry.

Numeric validity is not semantic bounds validity

The graph checks start < end, positive width/height, and checked x + width/y + height. It does not compare the locator with declared_width_px or declared_duration_ms. Those fields came from untrusted acquisition metadata.

After decode, a coordinate-space registry must validate against verified dimensions/duration and store the mapping transform. A malicious header must not decide whether a locator is accepted or how much memory is allocated.

The current locator also does not model:

text quote context/prefix/suffix for resilient re-anchoring;
line/column, grapheme, token, DOM, PDF page, or table-cell selectors;
image polygons/masks;
audio channels/speakers;
video stream/track IDs, frame presentation timestamps, or keyframe/sample identity;
uncertainty/tolerance;
a locator across multiple artifacts.

Add variants with exact semantics; do not put them in an untyped metadata map.

A stable derivation fingerprint

The fingerprint is SHA-256 over a versioned binary transcript. Every field is encoded as:

u64 big-endian byte length || exact field bytes

The first field is a domain separator:

mosaic-derivation-fingerprint-v1

Then the implementation hashes:

output evidence ID
output artifact SHA-256
transform ID
implementation release
parameter SHA-256
deterministic-claim byte
for each input, in order:
  u16 big-endian position
  role
  parent evidence ID
  locator variant tag and exact fields

Why not concatenate strings?

Naive concatenation is ambiguous:

"ab" || "c" == "a" || "bc"

Separators are fragile when values can contain separators. A length prefix makes field boundaries unambiguous. Fixed-width integer bytes avoid locale/formatting differences.

Why not hash ordinary JSON?

Equivalent JSON may differ in object member order, whitespace, escaping, or number representation. Serde output for a particular struct/runtime can be convenient regression evidence, but it is not automatically a cross-language cryptographic canonicalization contract. One could choose a defined canonical JSON/CBOR profile; version 1 instead uses a small explicit transcript.

Why a domain separator and version?

The same bytes hashed for different protocols must not accidentally mean the same thing. The domain label identifies this protocol. If fields, encoding, or semantics change, create mosaic-derivation-fingerprint-v2; never reinterpret a v1 digest.

What the fingerprint deliberately omits

Version 1 does not hash:

trust assertions;
acquisition timestamp/source class/body declarations;
execution time, host, device, dependency closure, or operator;
raw parameter values;
signatures;
the parent artifact digest directly.

The parent IDs resolve to graph nodes, while the output artifact digest is bound directly. This works inside an immutable, validated graph. Export across stores must bind the complete referenced graph or include parent digests to avoid ambiguous ID resolution.

Trust is omitted because policy may be re-evaluated without changing the historical recipe. Runtime execution details are omitted because version 1 has no complete execution-receipt type. The limits must be documented: this is a stable derivation record fingerprint, not a bit-for-bit reproducibility proof.

Transformation receipts

pub struct TransformReceipt {
    pub transform_id: String,
    pub implementation_release: String,
    pub parameters_sha256: Sha256Digest,
    pub deterministic_claim: bool,
}

Transform ID

Names the semantic operation: ocr, speech-to-text, incident-synthesis. It should remain stable across compatible implementations only if the behavioral contract remains stable.

Implementation release

Names the executable version, such as ocr-engine@sha256:1111. A mutable latest alias is not sufficient. In production, bind a container/image digest, model artifact identity, source revision, lockfile/runtime release, and any behavior-changing processor/template.

Parameter digest

Hashes a canonical, secret-safe parameter artifact. It lets the graph distinguish two recipes without embedding sensitive prompts, credentials, or configuration.

Hashing parameters does not make them recoverable. Reproduction requires authorized storage of the exact canonical parameter artifact. Redaction policy must not destroy the only copy required for audit.

Deterministic claim

true means the producer claims the transform should reproduce under its stated boundary. It is not proof. Reproduction can still fail because of:

unpinned model/tokenizer/processor;
nondeterministic accelerator kernels;
different hardware/drivers/math libraries;
thread scheduling or unordered maps;
random state consumed in a different order;
remote provider change;
hidden service-side preprocessing;
time/network/environment inputs;
incomplete parameter capture.

A production receipt should define the determinism boundary and include repeated-run evidence. If output bytes differ legitimately, store semantic/tolerance-based reproducibility separately from exact byte identity.

Trust assertions are decisions, not inherited adjectives

The executable trust type is:

pub struct TrustAssertion {
    pub subject_id: EvidenceId,
    pub claim: TrustClaim,
    pub decision: TrustDecision,
    pub asserted_by: String,
    pub policy_release: String,
    pub supporting_evidence: Vec<EvidenceId>,
}

Claims are typed:

content_integrity
source_authenticated
capture_attested
usage_rights_verified
human_approved

Decisions are:

verified
rejected
indeterminate

These axes must not collapse:

intact bytes do not authenticate a source;
an authenticated source can state something false;
capture attestation does not grant usage rights;
usage rights do not mean a human approved publication;
human approval does not prove an OCR transcript is accurate.

indeterminate is operationally important. Missing credentials, unavailable revocation state, an unsupported manifest, or insufficient evidence is not equivalent to rejection and must not become verified by default.

Actor and policy release

asserted_by identifies the verifier/reviewer/service that made the decision. policy_release identifies the rules it applied. A later policy can produce a new assertion without altering the artifact or derivation fingerprint.

The current labels are bounded identifiers, not authenticated identities. A production design needs tenant-scoped actor IDs, authenticated audit events, timestamps, expiry/revocation behavior, and signatures where cross-boundary verification matters.

Supporting evidence

Supporting IDs must already exist and cannot repeat. For example, a reviewer’s approval of the summary cites incident-note and screen-recording.

Support is not automatically lineage. A license document can support usage rights without having influenced media content. Conversely, every derivation parent does not automatically support a trust decision.

Non-transitivity is the safe default

The example verifies content integrity for dashboard-shot; ocr-text has zero trust assertions. The OCR engine could be wrong, use the wrong crop, hallucinate characters, or have a compromised release. The derivative requires its own applicable checks, such as:

output bytes intact
approved OCR implementation/release
locator verified in decoded coordinate space
OCR confidence/calibration policy
human comparison for high-impact text

Trust propagation rules, if a domain introduces them, must be explicit policy functions that produce new assertions with provenance—not automatic graph inheritance.

Hashes, signatures, C2PA, and truth

SHA-256 supports strong detection of byte change when a trusted system recomputes and compares the digest. NIST FIPS 180-4 specifies SHA-256. A digest alone does not identify who supplied it and cannot show whether manipulation happened before hashing.

A digital signature binds signed bytes/claims to control of a private key and a certificate/trust decision. It still does not prove the content is true or the signer is benevolent.

The C2PA technical specification defines manifests containing assertions, a signed claim, content bindings, and validation procedures. It can represent ingredients and transformations and bind a credential to asset content. It is substantially richer than this chapter’s internal receipt.

Integration should:

preserve the original asset and manifest bytes;
parse/validate under strict resource limits;
validate content bindings and claim signature;
evaluate the certificate chain/trust list and revocation/time policy;
retain every validation status, not only a boolean;
map applicable assertions into typed internal observations;
store verifier release and policy release;
never convert “valid manifest” into “content is true”;
handle absent, malformed, unsupported, redacted, or externally stored credentials;
revalidate when trust policy changes.

The current TrustAssertion is not a C2PA implementation or signature container. It is the application-policy result layer that can later consume C2PA validation evidence alongside device, identity, license, and human-review evidence.

Step-by-step implementation

1. Load strict root envelopes

let roots = fixture
    .lines()
    .filter(|line| !line.trim().is_empty())
    .map(EvidenceEnvelope::parse_json_line)
    .collect::<Result<Vec<_>, _>>()?;

let mut graph = EvidenceGraph::default();
for root in roots {
    graph.add_root(root)?;
}

For public input, use the bounded streaming policy from the previous chapter rather than unbounded line reads.

2. Build an OCR derivation with a pixel locator

let ocr = DerivationRecord {
    output: derived_text_envelope("ocr-text", output_digest),
    inputs: vec![EvidenceInput {
        position: 0,
        role: "image_source".to_owned(),
        parent_id: EvidenceId::parse("dashboard-shot")?,
        locator: Locator::ImagePixels {
            x: 100,
            y: 50,
            width: 600,
            height: 200,
            coordinate_space: "decoded-orientation-v1".to_owned(),
        },
    }],
    transform: TransformReceipt {
        transform_id: "ocr".to_owned(),
        implementation_release: "ocr-engine@sha256:1111".to_owned(),
        parameters_sha256: parameter_digest,
        deterministic_claim: true,
    },
};

let ocr_fingerprint = graph.add_derivation(ocr)?;

Insertion returns the fingerprint only after validation.

3. Build a timed transcript

Locator::TimeMilliseconds {
    start: 0,
    end_exclusive: 3_000,
}

The audio chapter will replace coarse milliseconds with verified sample/timeline mappings where precision requires it.

4. Synthesize with ordered multimodal inputs

The summary uses text bytes, entire derived texts, and one video time/rectangle locator. The input roles describe the function of each item, and their positions are 0–3.

5. Add scoped trust decisions

graph.add_trust_assertion(TrustAssertion {
    subject_id: id("incident-summary")?,
    claim: TrustClaim::HumanApproved,
    decision: TrustDecision::Verified,
    asserted_by: "reviewer-17".to_owned(),
    policy_release: "incident-review-v2".to_owned(),
    supporting_evidence: vec![
        id("incident-note")?,
        id("screen-recording")?,
    ],
})?;

This says one reviewer/policy approved one summary with named support. It does not establish integrity, source authentication, rights, or approval for its descendants.

6. Query stable transitive lineage

lineage_ids walks only derived parents, deduplicates with a BTreeSet, and returns stable lexicographic ID order. That order is for deterministic display/testing, not causal/topological order.

For large persisted graphs, use indexed recursive queries/materialized ancestry with depth/node limits and tenant predicates. Never allow one citation request to traverse an unbounded hostile graph.

Validation and error taxonomy

The public API returns typed failures:

Failure	Meaning
`DuplicateEvidence`	ID immutability/uniqueness violation
`UnknownInput`	forward/missing/cross-scope parent
`SelfReference`	direct cycle attempt
`MissingInputs` / `TooManyInputs`	unbounded or causally empty record
`InvalidInputPosition`	order is ambiguous or corrupted
`DerivedOutputSource`	system output mislabeled as acquired
`InvalidLocator`	empty/reversed/zero/overflowing geometry
`LocatorModalityMismatch`	selector cannot address parent modality
`InvalidLabel`	empty, oversized, outer whitespace, or non-graphic/non-ASCII identifier
`UnknownTrustSubject`	decision targets no node in this graph
`UnknownTrustSupport`	decision cites unavailable support
`DuplicateTrustSupport`	ambiguous/redundant support list

Do not collapse these into invalid provenance. Missing parent can trigger delayed import; invalid geometry should quarantine a record; duplicate IDs indicate conflict; unknown trust support may indicate a cross-tenant leak attempt.

Failure investigations

The same OCR bytes have different derivation fingerprints

Compare, in order:

output evidence ID and artifact digest;
transform ID and exact implementation release;
canonical parameter digest;
deterministic claim;
number/order/position/role of inputs;
parent IDs;
locator variant, units, coordinate-space label, and endpoints.

Identical output bytes can legitimately have different provenance. Do not deduplicate derivation records solely by output digest.

The same recipe produced different output bytes

The fingerprint includes the output digest, so the derivations differ. Investigate model/runtime pins, hidden preprocessing, randomness, hardware/kernels, concurrency, source bytes, environment, and incomplete parameter capture. A deterministic_claim: true makes this a failed claim to debug; it does not make the mismatch impossible.

A valid image crop extends beyond the real image

Version 1 validates arithmetic but not verified decode bounds. Find the coordinate-space definition and decoded metadata child. Reject/quarantine the downstream operation, preserve the invalid record for audit, and do not clamp silently. Clamping changes the selected evidence and therefore requires a new transformation record.

Imported records form a cycle

Do not call the incremental API in arbitrary order and interpret every missing parent as a cycle. Resolve all IDs, perform bounded topological sorting, distinguish missing external parents, and reject the cyclic import as a unit.

Parent is verified but generated summary is unsafe

Expected. Verify applicable properties at the summary: output integrity, synthesis release, evidence coverage, citation entailment, safety, authorization, and human approval if required. Parent integrity alone says nothing about model reasoning.

Trust changed without a fingerprint change

Expected. Derivation history is immutable; policy decisions are re-evaluable. Compare trust actor, policy release, support, decision time, and supersession/revocation rules.

Lineage is stable but not in processing order

lineage_ids returns sorted IDs. If UI/audit needs causal order, expose a separate topological query with edge roles and depths. Do not assign causal meaning to lexicographic order.

A hash matches but the artifact is malicious

Integrity is not safety. It can be an exact copy of a malicious file. Continue content-type verification, sandboxed decode, malware/media-parser policy, prompt-injection handling, rights, and authorization.

Security implications

Validate and authorize graph scope before resolving any ID.
Never use an evidence ID or coordinate-space label as a filesystem path.
Keep IDs/labels bounded before indexing/logging.
Cap nodes, inputs per node, trust support, depth, traversal work, serialized bytes, and imports.
Reject unknown fields/versions in persisted provenance records.
Compute artifact digests from actual bounded bytes; verify again on read.
Store graph mutations atomically with artifact publication or use a recoverable consistency protocol.
Prevent ID reuse; mutation breaks every downstream reference.
Treat imported provenance and C2PA assertions as untrusted input until validated.
Verify signatures, certificate chains, time/revocation, content binding, and policy separately.
Do not equate signer identity with truth, rights, safety, or authority to publish.
Authenticate asserted_by; a string alone is not identity proof.
Keep trust decisions append-only/superseded rather than overwritten.
Make policy release, time, expiry, and revocation auditable.
Do not inherit trust, access, consent, retention, or publication rights through transformations.
Derived transcripts/embeddings can be as sensitive as their parents; authorize independently and enforce parent constraints.
Propagate deletion/retention through a deliberate graph policy without destroying required audit records illegally.
Never expose cross-tenant graph existence through digest/ID error differences.
Keep raw parameter artifacts protected; their digest can still enable correlation.
Treat locators as attacker input; reject arithmetic overflow and bound downstream decode/crop.
Preserve original invalid records for forensic audit without repeatedly executing them.

Performance and persistence

The in-memory BTreeMap/BTreeSet implementation favors deterministic behavior and a teachable contract. Its operations are adequate for bounded per-run graphs, not a global media catalog.

For production:

persist immutable nodes and edges in tenant-scoped tables;
enforce unique (scope, evidence_id) constraints;
store input position/role/locator as validated columns or strict versioned blobs;
index parent and output IDs;
publish artifact, envelope, derivation, and outbox event transactionally where possible;
precompute or cache ancestry only with invalidation/version rules;
cap recursive query depth and visited nodes;
batch existence checks on import;
verify fingerprints while streaming records;
store trust assertions in an append-only/superseding table;
index subject/claim/policy/current status;
avoid signing/hash recomputation on every read—verify on admission and periodically/auditably;
measure graph fan-in, depth, traversal latency, bytes, and invalidation cost;
include input digest/transform release/parameter digest in derivative cache keys;
retain the derivation even on cache hits and record which prior output was reused.

One subtlety: high fan-in makes a single derived node expensive to authorize, invalidate, display, and reason about. The 256-input bound is a protocol safety limit, not a recommended prompt size. Introduce hierarchical aggregation only when each intermediate node has meaningful semantics and citations; do not hide 100,000 parents behind one undocumented “batch.”

Alternatives and trade-offs

W3C PROV directly

Use PROV-O/PROV-N/PROV-JSON interoperability when data crosses organizations or general provenance tools matter. The compact Rust types are easier to validate in one application but need an explicit, tested mapping before claiming PROV conformance.

Event log instead of materialized DAG

An append-only event log preserves history and can rebuild the graph. It also requires replay versioning, snapshotting, duplicate/idempotency rules, and bounded recovery. Many systems use both: an immutable event/receipt record plus query-oriented node/edge projections.

Merkle DAG

Putting parent content IDs into node identity makes tampering evident across the whole structure and supports distributed verification. It also makes metadata/policy evolution create new node identities and requires canonical serialization. Consider it for portable bundles; do not call the current ID-keyed graph a Merkle DAG.

Whole-artifact citations only

Simpler, but often unusable for long/multimodal evidence and weak for entailment review. Precise locators cost coordinate mapping and stability work; that cost is necessary for serious evidence systems.

Generic selector JSON

Extensible, but fails closed only if every downstream consumer validates every variant. Prefer a closed enum for supported operations and retain unknown external selectors as quarantined/import records until a versioned adapter understands them.

Trust score

A single 0.87 trusted number hides which property was assessed, actor, policy, evidence, and uncertainty. Typed claims/decisions are more verbose and far safer. If a ranking model uses scores, store them as separate calibrated observations, never as replacement for policy decisions.

Exercises

Recall

How do artifact, evidence, derivation, and trust identities differ?
Why does an activity using A and generating B not always imply B was derived from A?
Which admission rule makes the live graph acyclic?
Why are input position and role included in the fingerprint?
Why are text/time ranges half-open?
Why does image locator validation not compare against declared_width_px?
What does the coordinate-space label prevent?
Why length-prefix every hashed field?
Why is ordinary JSON serialization not automatically a cryptographic canonicalization?
What does deterministic_claim: true establish?
Why is trust excluded from derivation identity?
Why must integrity, authentication, rights, and human approval remain separate claims?
What does a valid C2PA claim still not prove?
Why is sorted lineage order not causal order?

Implementation

Add strict Serde serialization for versioned derivation/trust records and reject unknown fields.
Freeze the three example fingerprints as golden tests.
Add a parameter canonicalization artifact and prove map insertion order cannot change its digest.
Add an unordered-import function with bounded topological sort and separate missing-parent/cycle errors.
Add a TextQuote locator with exact/prefix/suffix and an explicit re-anchoring result.
Add decoded-coordinate metadata and reject image regions outside verified bounds.
Add video track ID and presentation-timestamp locators without assuming constant frame rate.
Persist nodes/edges in SQLite and prove a failed derivation inserts nothing.
Add a recursive lineage query with depth/node budget and tenant isolation.
Add an append-only trust assertion with assertion ID, time, supersedes, and expiry.
Add a policy function that creates a new derivative integrity assertion only after recomputing output bytes; prove it does not copy parent assertions.
Integrate a C2PA Rust verifier against valid, tampered, absent, and unsupported fixtures.
Add a graph export signature over a defined canonical representation.
Add property tests: every accepted incremental graph is acyclic and lineage terminates.
Fuzz locator/deserialization/import boundaries and assert no panics/unbounded traversal.

Design and adversarial review

Design provenance for a transcript word aligned to source audio after resampling and codec-delay removal.
Design a citation that survives Unicode normalization without silently moving to different text.
Decide which details must enter an exact image-generation receipt: prompt, negative prompt, seed/noise, scheduler, model/VAE, dimensions, safety filter, and postprocessing.
Design rights/consent policy when an audio excerpt produces a public synthetic voice.
Threat-model an attacker who supplies a valid signature from an untrusted certificate.
Threat-model a trusted capture device whose clock is wrong.
Design deletion when a parent is removed but a regulatory audit must retain transformation receipts.
Decide how to show provenance gaps and indeterminate trust in a user interface without implying safety.
Define a cross-organization PROV/C2PA export without leaking private parameter artifacts.
Review whether parent evidence IDs alone are sufficient in a portable graph; propose a v2 fingerprint.

Solution guidance

Artifact identity names exact bytes; evidence identity names a scoped logical record; derivation identity names a recipe/result binding; trust is a policy-scoped decision about one subject.
Usage is necessary but not sufficient for semantic influence; incidental inputs may not affect the generated entity.
A new derivation may reference only already-present parents.
Position and role can change transform semantics even when parent IDs are identical.
Length is end - start, adjacent ranges compose without overlap, and empty ranges are explicit.
Declared metadata is unverified attacker-controlled acquisition data.
It disambiguates orientation, scale, crop, origin, units, and mapping.
Length prefixes make field boundaries unambiguous.
Whitespace, member order, escaping, and numeric formatting can differ without a canonical profile.
Only that the producer claims reproducibility within an unstated/stated boundary; tests and full release/environment capture are still needed.
Trust can change under new evidence/policy without rewriting historical derivations.
They answer independent questions and have different verification procedures.
Truth, benevolence, rights outside asserted scope, or safety.
BTreeSet provides deterministic display order, not topological/temporal semantics.

For the import exercise, use Kahn’s algorithm with explicit node/edge/count limits. First classify references absent from the import and authorized store. Only then report remaining in-degree as a cycle. Preserve the imported bytes and fail the transaction as a unit.

For stable parameter hashing, choose one strict schema and canonical encoding. Reject floats that are non-finite, normalize only where the contract explicitly says so, include defaults rather than letting two runtimes invent them, and version the protocol.

For image/video bounds, attach a verified decoded representation as its own derived node. The locator should address that node’s named coordinate space or carry a checked mapping to the original. Never retroactively upgrade an acquisition declaration into verified truth.

For C2PA, keep raw validation statuses and trust-policy results. Test at least: no manifest, valid content binding/signature under trusted root, valid signature under untrusted root, tampered asset, expired/revoked/unknown-time credentials, unsupported assertion, redaction, and resource exhaustion.

Check your understanding

Can identical bytes have two evidence IDs?
Can one evidence ID be reused for changed bytes?
Can identical output bytes have different derivations?
Does a fingerprint prove the implementation executed?
Does a parent ID by itself cite a specific video moment?
Is [4_000, 6_000) inclusive at 6,000 ms?
May a time locator address an image?
Does valid numeric geometry prove the crop is inside decoded pixels?
Why include the output digest in the fingerprint?
Which fields need a v2 protocol if the fingerprint changes?
Does source_authenticated imply content_integrity?
Does content_integrity imply factual truth?
Does human approval automatically apply after editing the media?
Can support evidence be outside derivation lineage?
Why can a policy update add trust assertions without mutating the graph?
What additional checks are required before treating C2PA evidence as trusted?
Why must transitive traversal have budgets even in a DAG?
Which receipt fields are still missing for exact reproduction?

Completion checklist

Authoritative references

The next chapter gives text its full ingestion contract: bounded decoding, BOM/charset policy, Unicode normalization, line/block structure, language observations, stable source coordinates, and reversible mappings. The provenance graph built here will record every normalization/segmentation step rather than replacing the original bytes.