Evaluating the watermark: evidence, estimates and counterfactuals

Read the paper's evaluation like a reviewer: separate what is proven by reduction, what holds by construction, what is only an engineering estimate on one machine, and what is an illustrative counterfactual — and understand why conflating these four is the most common way a security claim is overstated.

Track

Research

Module

5 · Research case studies

Prerequisites

Binding keys to time (case study, part 2) · Hash functions

The single most useful skill when reading a systems-security paper is refusing to let four very different kinds of claim blur into one word, "works". This scheme makes claims in all four classes, and its honesty — or a reader's — depends on keeping them apart.

Proven by reduction

A theorem: property X holds unless a named, standard hardness assumption is false. Strongest, but scoped exactly to what the reduction covers.

Guaranteed by construction

If the specified enforcement actually runs as written, the property follows from the design. Contingent on correct, complete implementation — not a theorem about adversaries.

Estimated (engineering)

A measured or back-of-envelope number on specific hardware. Indicative of feasibility, not a benchmark, and not a security property at all.

Illustrative (counterfactual)

A described scenario where the scheme "would have" prevented a failure. Motivates the design; establishes no effectiveness rate.

Exactly one property in the scheme is backed by a stated reduction: temporal binding. The claim is that a signature made under the key for one day-epoch cannot verify under the key for a different day-epoch.

the reduction, in words
Assume an adversary who does NOT hold the master secret k_m can
present an artifact as created on day T2 when it was signed for day T1.

Step 1 (key independence): computing k_epoch(T2) from k_epoch(T1)
        requires k_m, because BIP32 child derivation is one-way.
Step 2 (key-specific verification): an EdDSA signature under
        k_epoch(T1) verifies only against the public key of
        k_epoch(T1), which differs from that of k_epoch(T2).

=> To make the forgery verify, the adversary needs k_m (contradiction)
   OR must break EdDSA unforgeability (contradiction).
Therefore back-dating fails for anyone without the master secret.

Integrity and authenticity are not given separate novel proofs; they inherit the standard guarantees of SHA-256 collision resistance and EdDSA unforgeability. The paper reuses audited primitives precisely so it does not have to re-prove them — a strength, not an omission, as long as the reuse is faithful.

A second class of claim is architectural: if every ingested artifact must pass the five-check protocol, then certain defect classes cannot be introduced through ingestion. This is weaker than a reduction — it depends on the enforcement actually being mandatory and correctly implemented — but it is a real guarantee about the system's structure.

• ▸A belief cannot be stale-without-detection if freshness is checked against a cryptographically bound timestamp on every artifact.
• ▸A post-hoc edit to the pipeline cannot hide, because each transformation step is hash-chained (an append-only chain over input hash, operation id, output hash).
• ▸Single-source laundering cannot pass as independent corroboration if independence is checked from signed origin_id values at ingestion.

The paper reports an end-to-end verification cost and explicitly frames it as an estimate on commodity hardware (a single CPU thread), not a benchmark. The honest way to read the number is to decompose it and see what dominates.

the paper's reported estimates (one commodity CPU thread)
SHA-256, 1 KB artifact (header only)   : < 0.1 ms
SHA-256, 1 MB artifact (document)      : ~ 3   ms   <- dominant term
SHA-256, 10 MB artifact (large image)  : ~ 30  ms
BIP32 key derivation (4 levels)        : ~ 2   ms   (fixed cost)
EdDSA verification                     : ~ 0.1 ms   (fixed cost)
registry lookup (cached, in-memory)    : < 0.1 ms
-----------------------------------------------------------------
end-to-end, 1 MB artifact              : < 6   ms   (the paper's figure)

Two structural facts fall out of the decomposition. First, the cost is dominated by hashing the artifact bytes, which scales with artifact size; the cryptographic ceremony (derivation + verification) is a near-constant few milliseconds regardless of size. Second, that means the per-artifact overhead is essentially "the cost of reading the bytes once", which any integrity scheme pays — the signature machinery adds little on top.

What the estimate deliberately omits is also worth naming: the amortized cost of registry refresh, the memory footprint of a large cached registry, the tail latency under contention, and the emitter-side signing cost. Feasibility on the verify path is argued; a full performance characterization is not claimed.

To ground the standard the paper describes one anonymized instance: a deployed decision-support system produced a high-confidence, irreversible, incorrect output after forming a belief from data that was roughly a decade stale, carried no verified timestamp, and whose apparently independent sources shared a single origin.

The argument is counterfactual: under mandatory data provenance the stale artifact would have failed the freshness check (its effective TTL for an irreversible action being zero), so no belief would have formed and the incorrect output could not have been produced; and under action accountability the chain would have named who was responsible for a decade-old artifact sitting in production without a freshness marker.

A careful reader also notes what the counterfactual quietly assumes: that the TTL policy was configured strictly for irreversible actions, that the registry correctly listed the emitter, and that the stale source would have been required to carry a header at all. Those are the exact deployment conditions part 6 flags as non-automatic. The counterfactual is only as strong as those assumptions hold.

Putting the four columns side by side gives a fair scorecard of the evaluation — strong where it claims strength, honest about where it is only indicative.

Temporal binding

Proven by reduction (scoped to adversaries without the master secret). The strongest claim in the paper.

Integrity / authenticity

Inherited from standard primitives (SHA-256, EdDSA). Not re-proven, and reasonably so.

Defect-class elimination

By construction, contingent on mandatory enforcement and correct implementation.

Verification overhead

Estimated on one machine; supports feasibility, not a precise latency claim.

Real-world benefit

Illustrative counterfactual only; no measured effectiveness rate.

Expected direction: (a) Proven by reduction; does not establish anything against an emitter holding the master secret, nor any latency. (b) Estimated on one CPU thread; does not establish security, variance, behavior under load, or performance on other hardware/sizes. (c) By construction, contingent on enforcement being mandatory and correctly implemented; does not hold if any ingestion path bypasses the protocol. (d) Illustrative counterfactual; does not establish a prevention rate or generalization beyond the single described case, and quietly assumes a strict TTL policy and correct registry.

Which single property is backed by a reduction, and to what assumptions?

Temporal binding — reduced to one-wayness of BIP32 derivation and EdDSA unforgeability, scoped to adversaries who do not hold the master secret.

Why does the paper call its ~6 ms figure an estimate rather than a benchmark?

It is from one commodity CPU thread, with no reported variance, concurrency, comparison baseline, or independent reproduction; it argues feasibility, not a precise latency claim.

What does the prevented-failure counterfactual establish, and what does it not?

It establishes that the targeted failure mode is real and that the design would have caught that one case; it does not establish an effectiveness rate, generalization, or independence from the authors' framing, and it assumes strict TTL and a correct registry.