Watermarking and provenance: Exercises — AI-ML deep dive

This page is a self-test ladder for Watermarking and provenance. Every problem states its level — from L1 Recognition (do you know the words?) up to L5 Mastery (can you build something new?). Work each one on paper first, then open the collapsible solution.

Before we start, one symbol we lean on everywhere:

The white bell is what unwatermarked text does (centred at $N /2$ ). The amber bell is watermarked text (shifted right). The $z$ -score measures, in bell-widths, how far a sample sits from the white centre.

Level 1 — Recognition

Problem 1.1

Match each term to its one-line job: (a) watermark, (b) provenance, (c) green list, (d) $δ$ (watermark strength).

Recall Solution

(a) watermark — a hidden, detectable signal woven into the content itself (survives copy/paste; unlike metadata it isn't a separate tag).
(b) provenance — the full history/chain-of-custody: who made it, when, with what tool, what edits.
(c) green list — the subset of the vocabulary the model is nudged toward at a given position.
(d) $δ$ — the number added to the logit (pre-softmax score) of every green token; larger $δ$ = stronger, more detectable, but lower-quality text.

Problem 1.2

True or false: "A watermark and a C2PA metadata tag are the same thing because both prove where content came from."

Recall Solution

False. Both target provenance, but a watermark is embedded in the content (words chosen, pixels perturbed) so it survives when the file is copied or re-saved. C2PA metadata is an attached signed manifest that can be stripped by re-uploading. See Cryptographic signatures for how the C2PA signature itself is made.

Problem 1.3

Under the "no watermark" assumption, what fraction of tokens do we expect to be green, and why exactly that number?

Recall Solution

Exactly $1/2$ . The hash splits the vocabulary into two sets of (roughly) equal size, and without any bias the model picks tokens independently of that split — so each token is green with probability $\frac{1}{2}$ , like a fair coin. That is why $μ = N /2$ sits at the centre of the white bell.

Level 2 — Application

Problem 2.1

A model emits $N = 200$ tokens; $n_{green} = 130$ . Compute $z$ .

Recall Solution

$z = \frac{2 ( 130 ) - 200}{200} = \frac{60}{14.142} \approx 4.243$ $z \approx 4.24$ . Above the usual threshold $z_{th} = 4$ , so watermark detected (false-positive rate $< 0.003$ ).

Problem 2.2

Same $N = 200$ , but this is a human essay with $n_{green} = 104$ . Compute $z$ and decide.

Recall Solution

$z = \frac{2 ( 104 ) - 200}{200} = \frac{8}{14.142} \approx 0.566$ $z \approx 0.57$ . Tiny — well inside normal random wobble. No watermark detected. Getting 104 green out of 200 by pure chance is completely ordinary.

Problem 2.3

Adding $δ = 2$ to a green token's logit. By roughly what factor does its softmax weight $e^{logit}$ grow before renormalisation?

Recall Solution

Softmax weight is $e^{logit}$ . Adding $δ$ multiplies it by $e^{δ}$ : $e^{logit + δ} = e^{logit} \cdot e^{δ} .$ For $δ = 2$ : $e^{2} \approx 7.389$ . So each green token's raw weight is boosted about 7.4× before the denominator $Z$ renormalises everything back to a probability distribution.

Problem 2.4

How many green tokens $n_{green}$ (out of $N = 200$ ) are needed to just hit $z = 4$ ?

Recall Solution

Solve $z = \frac{2 n _{green} - 200}{200} = 4$ : $2 n_{green} - 200 = 4200 = 56.569 ⟹ n_{green} = \frac{256.569}{2} = 128.28.$ So you need 129 green tokens (round up, since $128$ gives $z < 4$ ).

Level 3 — Analysis

Problem 3.1

A watermarked 300-token text has $z = 6$ . A paraphraser rewrites it, leaving $N^{'} = 240$ tokens. Suppose the green fraction among surviving tokens stays the same as the original. Find the original green count, the surviving green count, and the new $z^{'}$ .

Recall Solution

Original green count from $z = 6$ , $N = 300$ : $6 = \frac{2 n - 300}{300} ⟹ 2 n - 300 = 6300 = 103.92 ⟹ n = 201.96 \approx 202.$ Green fraction $= 202/300 = 0.6733$ . Surviving green (same fraction over 240 tokens): $0.6733 \times 240 = 161.6 \approx 162$ . New $z^{'}$ : $z^{'} = \frac{2 ( 162 ) - 240}{240} = \frac{84}{15.492} \approx 5.42.$ Watermark still strongly detected ( $z^{'} \approx 5.4$ ). Fewer tokens shrinks $z$ (the $N$ in the denominator gets smaller slower than the numerator would if fraction held), but here the signal is strong enough to survive.

Problem 3.2

Explain, using the green-list construction, why paraphrasing actually hurts more than the simplified Problem 3.1 assumes.

Recall Solution

The green list at position $t$ is seeded by the previous token(s): $h_{t} = HASH (w_{t - 1}, key)$ . When a paraphraser changes $w_{t - 1}$ , the green list at position $t$ changes too — so even a token you kept is now scored against a different list and is green only by chance (50%). One edit therefore corrupts not just that token but its neighbour's classification. Real paraphrase attacks push the surviving green fraction back toward 0.5, not "unchanged," making Problem 3.1's assumption optimistic. This coupling is the same fragility exploited by Adversarial examples.

Problem 3.3

Two texts both give $z = 4$ . Text A has $N = 100$ , Text B has $N = 400$ . Which has the higher green fraction, and what does that say about needed watermark strength?

Recall Solution

Solve $n$ for each:

A: $2 n - 100 = 4100 = 40 \Rightarrow n = 70$ , fraction $= 0.70$ .
B: $2 n - 400 = 4400 = 80 \Rightarrow n = 240$ , fraction $= 0.60$ . Text A has the higher fraction (0.70 vs 0.60). Interpretation: short texts need a much stronger per-token bias to reach the same confidence, because $z \propto N$ — long texts accumulate weak evidence for free, short texts must lean hard on $δ$ .

Level 4 — Synthesis

Problem 4.1

Design choice: you must watermark tweets (avg 40 tokens). What green fraction $p$ does your $δ$ need to guarantee, so that a typical tweet reaches $z \geq 4$ ? Assume $n_{green} = pN$ exactly.

Recall Solution

$z = \frac{2 pN - N}{N} = (2 p - 1) N .$ Set $= 4$ with $N = 40$ : $(2 p - 1) 40 = 4 ⟹ 2 p - 1 = \frac{4}{6.325} = 0.6325 ⟹ p = 0.816.$ You need about 82% of tokens green per tweet — an aggressive bias, meaning a large $δ$ and noticeable quality loss. Synthesis insight: watermarking very short content forces a brutal quality/detectability tradeoff; often it's better to aggregate across many tweets from one account (raising effective $N$ ) than to hammer $δ$ on one tweet.

Problem 4.2

A C2PA manifest signs $h = SHA256 (content)$ . An attacker changes one pixel. Walk through what breaks and why verification returns FALSE, tying it to why watermarking and signing are complementary.

Recall Solution

Verifier recomputes $h^{'} = SHA256 (new content)$ . A single-pixel change makes $h^{'} \neq = h$ (SHA256 is avalanche-sensitive: one bit flips ~half the output).
The stored signature $s = Sign_{private} (h)$ only validates against the original $h$ . So $Verify_{public} (h^{'}, s) = FALSE$ .
Complementarity: the signature detects any tampering but is trivially stripped (delete the manifest). The watermark stays inside the pixels and survives stripping, but only proves "an AI made this," not "exactly this file, unedited." Together: signature = integrity + identity when present; watermark = survivable origin signal. See Cryptographic signatures and Content moderation for how platforms stack both.

Level 5 — Mastery

Problem 5.1

Adaptive attacker. An attacker knows the green list is seeded by the previous token but not the secret key. They randomly replace a fraction $r$ of tokens with synonyms. Model surviving green fraction as $p_{eff} = (1 - r) p_{0} + r \cdot \frac{1}{2}$ , where $p_{0} = 0.68$ is the original green fraction. For $N = 250$ original tokens (kept count $= (1 - r) N$ , ignoring length change), find the largest $r$ for which detection ( $z \geq 4$ ) still holds.

Recall Solution

Surviving tokens: $N_{s} = (1 - r) \cdot 250$ . Green fraction $p_{eff} = (1 - r) (0.68) + 0.5 r = 0.68 - 0.18 r$ . $z = (2 p_{eff} - 1) N_{s} = (2 (0.68 - 0.18 r) - 1) 250 (1 - r) = (0.36 - 0.36 r) 250 (1 - r) .$ Factor: $z = 0.36 (1 - r) 250 1 - r = 0.36 250 (1 - r)^{3/2}$ . With $0.36 250 = 5.692$ : $z = 5.692 (1 - r)^{3/2} \geq 4 ⟹ (1 - r)^{3/2} \geq 0.7027 ⟹ 1 - r \geq 0.702 7^{2/3} = 0.7898.$ $r \leq 0.2102.$ The attacker can rewrite up to ≈21% of tokens before detection fails. The steep $(1 - r)^{3/2}$ decay (not linear!) is the key mastery point: each edit hurts both the fraction and the sample size, so robustness collapses faster than intuition suggests. This is exactly the arms-race framing in AI regulation.

Problem 5.2

Full synthesis. In two sentences, argue why watermarking alone cannot guarantee provenance, referencing at least the strength/quality tradeoff and the strippability of signatures.

Recall Solution

Watermarks decay under paraphrase/compression and, for short or creative text, demand a $δ$ so high that quality suffers before detection is reliable (Problems 4.1, 5.1), so any determined attacker can drive $z$ below threshold. Cryptographic signatures (Problem 4.2) prove integrity but are removable, and open-source models simply skip watermarking — so real provenance needs a layered system: embedded watermark + signed manifest + platform policy + Content moderation, never any single mechanism.

Recall Self-test recap

The whole detection story is one line ::: $z = (2 p - 1) N$ — effect size $(2 p - 1)$ times evidence volume $N$ . Why signatures and watermarks are complementary ::: signatures prove integrity but strip off; watermarks survive stripping but only prove AI-origin, not exact-file integrity. Why short content is hard to watermark ::: $z \propto N$ , so tiny $N$ forces a large $δ$ and wrecks text quality.