Architecture & algorithms of the provenance watermark

Work through the full data path of the provenance watermark end to end — header schema, hierarchical temporal key derivation, Merkle commitment, the append-only key registry, per-format embedding, and the five-check rejection protocol — with the model written out in code and a complete signed-then-verified walkthrough.

Track

Research

Module

5 · Research case studies

Prerequisites

Digital signatures · Merkle trees · Hash chains and transparency · Provenance blindness (case study, part 1)

It helps to hold the whole pipeline in view before zooming into any one piece. An emitter produces an artifact, computes a provenance header over it, derives a signing key from the header's own timestamp and domain, signs, and embeds the header invisibly. A consumer — an agent at its ingestion boundary — extracts the header, recomputes the hash, re-derives the expected public key, verifies the signature, checks the emitter against a cached registry, and checks freshness. Only then may a belief be formed.

end-to-end path (schematic)
EMIT:    artifact -> content_hash -> header -> derive key -> sign -> embed
WIRE:    artifact-with-embedded-header  (looks normal to any consumer)
INGEST:  extract -> re-hash -> re-derive pubkey -> verify sig
         -> registry lookup -> freshness gate -> admit | reject

The header is a fixed tuple of six signed fields plus the signature over them. Nothing optional, nothing free-form — a canonical serialization so that emitter and verifier hash the exact same bytes.

header fields (transformed from the paper's Definition 1)
header = {
  version:      "1.0",                       // scheme version, for forward migration
  content_hash: SHA256(artifact_bytes),      // what the signature pins to
  sourced_at:   <unix seconds of creation>,  // the freshness + key-derivation input
  origin_id:    <emitter DID, e.g. did:web:org.example>,
  domain:       <content-domain label>,      // separates signing authority by domain
  ttl_hint:     <recommended time-to-live, seconds>,
  signature:    EdDSA_sign(k_content, canonical(fields 1..6))
}

version

Lets verifiers reject or migrate headers whose scheme they do not understand, instead of misparsing them.

content_hash

The integrity anchor. Any change to the artifact bytes changes this value and invalidates the signature. For large artifacts it is a Merkle root (below), not a flat hash.

sourced_at

Does double duty: it is the freshness value the ingestion gate reads, AND an input to key derivation, which is what makes it non-forgeable (part 2).

origin_id

A decentralized identifier for the emitter, resolved to a public key through the registry — not a network address, so it survives the emitter moving hosts.

domain

A content-domain label (e.g. "medical", "financial") that branches the key tree, so a key authorized for one domain cannot sign in another.

ttl_hint

The emitter's recommended time-to-live. The consumer's own action-class policy may be stricter — ttl_hint is advice, not a grant.

The signing key is not a fixed per-emitter key; it is derived down a path whose indices are the creation epoch, then the domain, then the content. Because BIP32 child derivation is one-way, you cannot compute a sibling or parent key without the master secret — which is exactly the property that makes the timestamp and domain tamper-evident.

derivation (transformed from the paper's Definitions 2–3)
# one-time setup per emitter:
ms  = PBKDF2-HMAC-SHA512(mnemonic, "ews-v1" || origin_id, iterations)
k_m = BIP32_root(ms)          # master key; master PUBLIC key published to registry

# per artifact with header H, created at tau, in domain d:
k_epoch   = BIP32(k_m,     floor(tau / 86400))   # index = day number
k_domain  = BIP32(k_epoch, FNV32(d))             # index = hash of domain label
k_content = BIP32(k_domain, H.content_hash[0:4]) # index = first bytes of content hash
sig       = EdDSA_sign(k_content, canonical(H))

Read the path as a narrowing of authority: the epoch key can only have come from this day, the domain key only from this domain under that day, the content key only from this artifact under that domain. A verifier reverses it: from sourced_at and domain it re-derives the expected public key and checks the signature against it. If the emitter back-dated sourced_at, the re-derived public key is the wrong one and verification fails.

A flat SHA-256 over a multi-megabyte document or image is wasteful to recompute and impossible to verify partially. For artifacts above a chunk threshold the content anchor becomes a Merkle root over fixed-size chunks, so a verifier can confirm one chunk, or stream-verify progressively, without re-hashing the whole file.

Merkle commitment for large artifacts
# split into fixed-size chunks (the paper uses 1 MB):
leaves       = [ SHA256(chunk_1), SHA256(chunk_2), ..., SHA256(chunk_n) ]
content_hash = MerkleRoot(leaves)

# partial verification of chunk i needs only:
#   chunk_i  +  the O(log n) sibling hashes on its path to the root
# => verify a 1 MB slice of a 100 MB file without touching the other 99 MB

The engineering payoff is progressive loading: an agent can begin verifying a large document as it streams in and stop early if an inconsistency appears, instead of buffering the entire artifact before the first integrity check.

Keys must rotate, and compromised keys must be revoked, but a central authority deciding trust in the request path would reintroduce exactly the single point the scheme avoids. The proposal uses an append-only, publicly auditable log — modeled on Certificate Transparency — that any party can mirror and verify. Verifiers cache a snapshot with a configurable refresh interval.

1. 1Publication: an emitter publishes its master public key to the log with a validity window [t_start, t_end]. The log is append-only, so a published key cannot be silently withdrawn or altered.
2. 2Scheduled rotation: before t_end, the emitter publishes a fresh master public key with a new window and signs new artifacts under it. Verifiers pick the key whose window contains the artifact's sourced_at.
3. 3Emergency revocation: on compromise, the emitter appends a revocation entry carrying a compromise time t_revoke. Verifiers reject artifacts with sourced_at after t_revoke; artifacts signed before it remain valid, because temporal binding ties each signature to its own epoch.
4. 4Verification: because the log is append-only and public, any party can audit it for equivocation (showing different histories to different verifiers) without trusting the log operator.

The header must ride along with the artifact without changing how normal consumers see it. The paper specifies a different embedding per format, trading off visibility against the format's structure.

JSON / CSV / Parquet

A reserved structural field (e.g. an _ews member or a file-level metadata field). Visible but inert to consumers that ignore it.

PDF

An XMP metadata stream under a custom namespace — invisible in the rendered document.

Raster images (JPEG / PNG)

XMP metadata plus least-significant-bit steganography across the blue channel, so the pixels look identical.

Medical images

A private data tag in the image container's metadata namespace.

HTTP feeds

A custom response header on the transport, rather than in the body.

LSB embedding + verification (as described by the paper)
# EMIT: base64(header) spread across LSBs of the blue channel.
#       the paper reports ~32 KB capacity in a 512x512 image -> ample.
# INGEST:
clean_image  = zero_LSBs(received_image)        # strip the carrier bits
recovered    = base64_decode(read_LSBs(received_image))
ok_integrity = (SHA256(clean_image) == recovered.content_hash)
# NOTE: verification hashes the CLEANED image, because the embedding
# itself perturbs the LSBs; the signature must be over the clean bytes.

All of the above converges on one chokepoint. Every artifact faces five checks at the ingestion boundary, in order, before any belief is derived. The order matters: cheap, decisive checks first; each failure yields a distinct, logged reason so audits can tell no-header from stale from forged.

1. 11. Header extraction — pull the header with the format-specific method. Absent -> reject (no-header).
2. 22. Integrity — recompute content_hash over the artifact (or its Merkle root) and compare. Mismatch -> reject (integrity).
3. 33. Authenticity — re-derive the expected public key from sourced_at and domain, verify the EdDSA signature. Fail -> reject (authenticity).
4. 44. Registry — resolve origin_id in the cached registry; confirm the key is known and not revoked for this sourced_at. Unknown/revoked -> reject (unknown-emitter).
5. 55. Freshness — pass sourced_at and ttl_hint to the consumer's freshness gate under the relevant action class. Stale -> reject (stale).

Every rejection is logged with the artifact hash, the reason, and the time. A transitional pragmatic mode may instead ADMIT an unsigned artifact with a time-to-live of zero for irreversible actions, flagged unverified, propagating that flag to every belief and decision derived from it. That is a deliberate, visible downgrade for the adoption period — not a silent acceptance.

One artifact, signed then verified, field by field. Synthetic values throughout.

synthetic — EMIT side
artifact      = <bytes of a 0.4 MB PDF>
content_hash  = SHA256(artifact)                 # small -> flat hash, not Merkle
sourced_at    = 1_760_000_000                    # some creation instant
origin_id     = did:web:labs.example
domain        = "clinical-note"
ttl_hint      = 86_400                            # emitter suggests 1 day

epoch_index   = floor(1_760_000_000 / 86_400)     # the creation day number
k_epoch       = BIP32(k_m, epoch_index)
k_domain      = BIP32(k_epoch, FNV32("clinical-note"))
k_content     = BIP32(k_domain, content_hash[0:4])
signature     = EdDSA_sign(k_content, canonical(header_without_sig))
embed(header + signature into the PDF's XMP stream)

synthetic — INGEST side (agent boundary)
H = extract_header(pdf)                            # (1) present? yes
assert SHA256(pdf_bytes) == H.content_hash        # (2) integrity OK

epoch_index = floor(H.sourced_at / 86_400)
pub = derive_pubkey(master_pub[H.origin_id], epoch_index,
                    FNV32(H.domain), H.content_hash[0:4])
assert EdDSA_verify(pub, canonical(H), H.signature)   # (3) authenticity OK

assert H.origin_id in registry and not revoked(H.origin_id, H.sourced_at)  # (4)
assert freshness_gate(H.sourced_at, ttl=min(H.ttl_hint, policy_ttl(action)))  # (5)
# all five pass -> belief may now be formed from this artifact

Now perturb one thing and watch a single check fail. Flip one byte of the PDF: step 2 fails (hash mismatch). Rewrite sourced_at to last week without re-signing: step 3 fails (the re-derived key is for the wrong epoch). Replay a genuine header onto different content: step 2 fails (content_hash no longer matches). Each attack is caught by exactly one named check — which is why the logged rejection reason is diagnostic, not generic.

Expected direction: (a) Check 2 integrity — recomputed content_hash no longer matches. (b) Check 3 authenticity — the re-derived key for the edited epoch differs from the signing key, so the signature fails. (c) Check 2 integrity — the header's content_hash is for last year's content, not the new bytes. (d) Check 4 registry — origin_id is revoked for a sourced_at after t_revoke. (e) Checks 1–4 pass (it is genuinely signed and unmodified); check 5 freshness rejects it because the age exceeds the action-class TTL.

Why is sourced_at used both as the freshness value and as a key-derivation input?

Using it in derivation makes it non-forgeable: a different claimed time forces a different signing key (part 2), so the freshness value the gate reads is itself cryptographically bound, not a free-form field an emitter can edit.

What does the Merkle-root content anchor buy over a flat hash for large artifacts?

Partial and progressive verification: a single chunk can be checked with O(log n) sibling hashes, so a slice of a large file is verifiable without hashing the whole thing, enabling early-abort streaming verification.

Why does a key compromise NOT invalidate everything the key ever signed?

Because revocation is time-scoped to t_revoke and each signature is temporally bound to its epoch, so only artifacts dated after the compromise are rejected while earlier, pre-compromise signatures remain valid.