Signing and Verifying Lineage Records

Part of: Access Control and Redaction for Lineage Records

A lineage record’s value depends on being believed, and a record stored in a database anyone with write access can edit is believed only as far as the database is trusted. Signing raises that: a signed record can be shown to be the one that was written, by the party that wrote it, unchanged since. This how-to applies signatures to lineage records without acquiring a key-management problem larger than the one it solves.

The honest scoping first: a signature proves integrity and origin, not truth. A correctly signed record asserting a false derivation is a correctly signed false record. Signing defends against later tampering and against repudiation; it does not defend against a pipeline that recorded the wrong thing, and it is often sold as though it does.

Prerequisites

  • A canonical serialisation for the records being signed, per Access Control and Redaction for Lineage Records.
  • A key store the pipeline can reach and a rotation plan.
  • A decision about signing granularity, made before the first key is issued.
  • Verification implemented somewhere other than the signer.

Canonicalisation Comes Before Cryptography

The commonest failure in record signing is not cryptographic; it is that the verifier serialises the record slightly differently from the signer, and every signature fails.

Five ways serialisation breaks a signature Key order, whitespace, numeric formatting, unicode normalisation and timestamp representation each change the bytes without changing the meaning. key order map iteration order differs by runtime sort keys whitespace pretty-printing on one side only no separators number format 1.0 vs 1 vs 1.00 vs 1e0 strings, not floats unicode form accented names in NFC vs NFD normalise to NFC timestamps offset vs Z, seconds vs milliseconds one format, UTC

Write the canonical form down as a specification rather than as an implementation. Two implementations will be needed — the signer and an independent verifier — and if the specification is “whatever the signing library produces” then the verifier is not independent.

Sign the canonical bytes and store them, not just the signature. Reconstructing the bytes years later from a database row means re-running the canonicalisation with whatever version of it exists then, and the smallest change breaks every historical signature.

Version the canonicalisation scheme in the signed envelope. When it must change — and it will — old records verify under the old rules and new ones under the new, with no ambiguity about which applies.

Choose the Granularity Deliberately

Signing every record, signing batches, and signing a periodic digest are three different systems with different costs and different guarantees.

Per-record signing gives the strongest guarantee and the highest cost: one signature operation per lineage event, and a signature stored per row. It is right where individual records are presented as evidence.

Batch signing covers a set of records with one signature over their combined digest. It is far cheaper and it degrades usefully — a tampered record is detectable, though identifying which one requires the whole batch.

Periodic digest signing publishes a signed hash of the whole store at intervals. It proves nothing about an individual record’s origin, but it proves the store has not been rewritten since the digest, which is the property most audit questions actually turn on.

Combine the last two in most cases. Batch signing at write time plus a daily published digest gives origin evidence and tamper-evidence at a cost that does not scale with event volume.

Key Management Is the Real Work

The cryptography is a library call; the key lifecycle is the part that determines whether any of it holds up.

A key's signing life is short; its verifying life is long Keys sign for a bounded period and must remain verifiable for as long as the records they signed are retained. KEY A signing — 12 months verifying — as long as the records are retained (often 7+ years) KEY B signing — 12 months verifying — continues Deleting a retired public key invalidates every record it ever signed. Publish public keys with validity dates and never remove one.

The asymmetry in the diagram is the thing to internalise. Rotation guidance is written for keys protecting live sessions, where retiring a key ends its relevance; for signed records the public key must outlive the retention period of everything it signed, which is usually far longer than anyone plans for.

Record the key identifier in the signed envelope so verification does not have to guess. A record naming its key can be verified without a search, and a key that has been compromised can be identified in every record it touched.

Keep the private key out of the pipeline process. A signing service reached over an authenticated channel means a compromised pipeline can request signatures — bad — rather than exfiltrate the key — worse and permanent.

Plan for compromise explicitly. A compromised key means every record it signed loses its origin guarantee, and the response is to re-sign under a new key with a countersignature attesting when the re-signing happened. Deciding that during the incident is too late.

Verify Somewhere the Signer Cannot Reach

A verification implemented by the signing team, running on the signing infrastructure, using the signing library, proves very little.

Implement verification independently, ideally in a different codebase, and run it on a schedule against a sample of records. It is the only check that catches a canonicalisation drift between versions of the signer.

Give the verification result a home. A verification that runs and logs to nowhere is not a control; the result should appear in the same place the coverage figures do, with the count checked and the count failing.

Publish enough for an external party to verify. If the point of signing is to support an external claim, the public keys, the canonicalisation specification and a worked example must be available outside the organisation, or the claim rests on trusting the same party the signature was meant to substitute for.

Decide What the Signature Is For Before Building It

Signing is often adopted because it sounds rigorous, and the specific claim it is meant to support is left unstated — which makes it impossible to tell whether the implementation is adequate.

Four claims, four different requirements Tamper evidence needs only a signature; origin attribution needs key custody; non-repudiation needs a bound key holder; legal timestamping needs an external authority. CLAIM ALSO REQUIRES "this record has not changed" nothing beyond the signature and a stored public key tamper evidence — the easy case, and usually enough "our pipeline wrote it" demonstrable custody of the private key origin attribution — a key in a config file will not support it "we cannot deny writing it" a key bound to a legal identity, held in hardware non-repudiation — a much heavier obligation than it sounds "it existed on this date" an external timestamping authority your own clock proves nothing about your own records

Most lineage programmes need the first row and specify the third. Tamper evidence is genuinely useful, cheap, and defensible; non-repudiation requires hardware key custody and an organisational commitment that few teams have agreed to when they write the design document.

Write the claim into the design and test against it. A verification suite testing that signatures verify is testing the library; one testing that the claim holds — that a key in a container image cannot support origin attribution, for instance — is testing the system.

Revisit the claim when the deployment changes. A key moved from a hardware module into an environment variable during a migration silently downgrades every claim the system makes, and nothing in the signature will indicate it.

Verification

Assert cross-implementation agreement: canonicalise a fixture record with the signer and with the independent verifier and compare bytes. This single test catches most real failures.

Assert tamper detection by modifying one byte of a stored record and confirming verification fails. A verifier that has never rejected anything has not been shown to work.

Assert retired-key verification by signing under a key, retiring it, and confirming the record still verifies. Key retirement that breaks verification is a common and quiet regression.

Assert the envelope carries the key identifier and the canonicalisation version, by schema check rather than by inspection.

Gotchas & edge cases

  • A signature on a record nobody can read is worthless. If the canonicalisation specification, the public keys and a working verifier are all internal, the signature supports only claims made to yourself. Publish the means of verification alongside whatever the signature is meant to prove.
  • Library defaults change between major versions. A padding scheme or hash choice that shifted under an upgrade produces signatures that verify under the new library and not the old. Pin the algorithm explicitly in the envelope rather than relying on a default.
  • Signing does not prevent deletion. A record removed entirely leaves no signature to fail. Pair signatures with an append-only log or a sequence check.
  • Verification failures need triage, not alerts. Most are canonicalisation drift rather than tampering, and an alert that cries tampering weekly will be muted before a real one arrives.
  • Timestamps in the record are not trusted time. A signer controls its own clock, so a signed timestamp proves only what the signer claimed. Use a timestamping authority where the date matters legally.
  • Redaction breaks signatures. A redacted export cannot carry the original signature. Either sign the redacted form separately or use a scheme supporting redactable signatures, and be explicit which.
  • Database round-trips mutate values. A numeric column returning a different precision, or a timestamp losing sub-second detail, changes the bytes. Sign what you store and verify what you read.
  • Signature verification cost is not trivial. Verifying a million records is minutes of compute. Sample continuously and verify in full only on demand.