A signature that knows where it lives.
Most signed-record designs choose what to sign by asking what is convenient. The better method is to enumerate the replay attacks a signature must survive and let each one add exactly one field to the signed bytes. Done that way the preimage is short, every component is justified, and the omissions become visible — including the omission that let a complete, correctly-signed history be presented as a different organisation's.
§1Derivation, not decoration
A record has been given an identity by Paper 002: a Merkle root over its salted fields, stable under redaction. Signing that root proves an author. The question is what else the signature should cover, and the honest way to answer it is adversarially: start with the minimum, find the attack, add the field that closes it, repeat.
What follows is that derivation in order. Each step is an attack that works against the previous step's construction.
§2Step 0 — sign the record hash
signed = recordHashAttack. A signature is a portable object. Lift it, together with its record, into an entirely different set of records. Nothing in the signed bytes says which collection this record belonged to, so it verifies wherever it is placed. A record of a routine decision can be inserted into a history that never contained it.
§3Step 1 — bind each record to the one before it
Give each record a link to its predecessor — link = SHA-256(prevLink ‖ recordHash) — and
sign that. Now records form a chain, and an edit anywhere breaks every link after it.
signed = SHA-256(prevLink ‖ recordHash)Attack. Chains repair. An adversary who edits record 4 recomputes record 4's hash, then recomputes every downstream link, and produces a chain that is internally flawless. If they also hold the signing key the chain is indistinguishable from an honest one. Even without the key, the structure gives no reason a signature valid at one position should not be valid at another where the surrounding hashes happen to line up.
Hash-linking makes tampering expensive and downstream-visible. It does not make it detectable on its own. Every additional field below exists because the chain alone is not enough, and a design that stops here — many do — is weaker than its diagram suggests.
§4Step 2 — bind the position
Include the sequence number in the signed bytes. A signature now attests this record, at this position, and cannot be moved even if the surrounding hashes are arranged to accommodate it.
One design note that matters more than it looks. Sequence numbers must be required to strictly increase, and must not be required to be consecutive. A verifier that demands contiguity will report intact chains as tampered the moment the counter behind the sequence is shared across tenants — two parties appending concurrently legitimately hold 1, 3, 5 and 2, 4, 6. This is not hypothetical: it was shipped, and it produced false alarms on correct data, which is the failure mode most corrosive to trust in a verification tool. Nothing is lost by relaxing it: a dropped record is caught by the link, and a reordered one by its own signature.
§5Step 3 — bind the domain
Attack. Two different systems adopt this same construction — likely, since it is built from public standards. A record signed by one now replays as a record of the other, because the signed bytes describe a position in a chain and say nothing about which system's chain. Worse if the two share any key material or any verifier.
The fix is a domain-separation tag: a constant string identifying the construction and the system, included in the signed bytes. The important design rule is that it must have no default. A tag that falls back to a shared value when unset defeats the separation exactly when someone forgets to set it — which is the only circumstance in which it matters.
§6Step 4 — bind the owner (the one that was missed)
Everything above binds a record to a content, a position and a construction. None of it binds a record to a party. In a multi-tenant system that omission is severe, and it is the one that shipped.
A complete, correctly-signed history can be relabelled as another party's
The conditions are ordinary rather than exotic. One signing key per deployment, rather than per
tenant — a normal choice. A sequence counter shared across tenants — also normal. A preimage of
domain ‖ seq ‖ prevHash ‖ recordHash, containing no tenant identifier.
Under those conditions, relabelling every row of one organisation's chain to another organisation leaves an intact, fully-signed, fully-verifying chain attributed to the wrong party. No forgery is required. No key is compromised. Every hash recomputes, every link holds, every signature checks — and the verifier reports success, because the question "whose is this?" was never asked of the signature.
For a system whose entire claim is this party did this, attribution is the one property the signature must carry. It was the one property it did not.
The closed form adds the chain identifier — the identity of the party the chain belongs to:
preimage = domain │ chainId │ seq │ prevHash │ recordHash
example, as UTF-8 bytes
example.evidence.1.link│did:example:org:northwind│2│c06cbe0d…│a0a252e4…Two rules attach to that layout, and both are the kind that get dropped in a rewrite:
- Neither the domain nor the chain identifier may be empty, and neither may default. A verifier asked to check signatures without being told which chain it is checking should refuse, not guess. Refusing is the correct answer: the alternative is a tool that reports a lifted chain as valid.
- Neither may contain the separator. Otherwise a value can be smuggled across a
field boundary — a chain identifier ending in
│9produces the same preimage as a different identifier with sequence 9. This is the same injectivity requirement as Paper 002 §4, arriving in a different costume. Field-separated encodings need the separator excluded from the fields; length-prefixed encodings do not, and are the safer default when the fields are not under your control.
§7Migrating a signature format without re-signing anything
The defect in §6 raises an awkward question: how do you change what a signature covers when records are, by construction, append-only? You cannot re-sign old records — rewriting them is precisely the operation the system exists to detect, and a migration that touches historical rows destroys the property it was meant to protect.
The answer is to make the envelope a per-record field rather than a system-wide setting:
- Every record carries the version of the format it was written under.
- The writer emits only the current version.
- The reader understands every version, dispatching on the record's own field, and chooses the correct preimage layout per record.
- The verdict reports which properties actually hold. A chain containing pre-migration records is reported as verified and not tenant-bound — two separate facts, neither hidden.
- Older versions are accepted only behind an explicit flag, so that reading legacy records is a deliberate act rather than a silent default.
No record is ever rewritten. The chain migrates at a boundary, and the boundary is visible to anyone examining it. The cost is that the old format is now permanent — a reader must understand it forever — which is a strong argument for getting the preimage right before the first record is written, and the reason this paper exists.
§8Why Ed25519
The signature scheme is chosen for boring reasons, which are the correct reasons.
- Deterministic. Ed25519 derives its per-signature nonce from the key and the message.[1] There is no random nonce, and therefore no nonce-reuse failure mode — the class of defect that has repeatedly leaked ECDSA private keys, including in widely-deployed production systems. Removing a failure mode entirely is worth more than mitigating it.
- Independently implemented and verifiable with stock tooling. A sceptic can check a signature with common command-line tools and no software of ours. That is requirement 2 of Paper 001, and it eliminates schemes whose only implementation is the vendor's.
- Small and fast enough to be checked in a browser, which matters because the cheapest way to make verification credible is to let someone do it in front of you without installing anything.
The hash is SHA-256[2] for the same reason: an examining party's expert can recompute it with a standard utility and move on. Novel primitives are a liability in a context where the goal is for the other side to stop arguing.
§9Two failures that verifiers routinely treat as non-failures
The construction is only as good as the code that checks it, and two specific mistakes appear repeatedly. Both were found in working systems; both are one operator in a boolean expression.
A missing signature treated as nothing to check
the defective guard
if (publicKey && entry.signature && !verify(publicKey, data, entry.signature)) {
fail()
}
Read it as an adversary. If entry.signature is absent the condition is false, the check
is skipped, and verification succeeds. So the attack is not to forge a signature — it is to
delete it. Rewrite the payloads, recompute the hashes and links, remove the
signatures entirely, and the verifier reports an intact chain.
The rule: when a public key has been supplied, a missing signature is a failure, never a skip. The presence of a key is the caller stating that signatures are required.
A key that will not load, treated as a key that was not supplied
The same defect, one layer up, and considerably harder to see. A key-import function returns
null on failure — a malformed key, the wrong algorithm, or a runtime that lacks the
signature scheme. Callers then write the natural thing:
verifyChain(records, { publicKey: key || undefined, … })
null is falsy, so the verifier concludes that no key was supplied, skips signature
checking entirely, and returns success. Every signature-dependent property silently evaporates —
including, in the case where this was found, the cross-tenant check from §6, which is the only
protection a signature provides against relabelling.
The repair is to make the failure representable. Return a distinct sentinel that is truthy — so no caller can accidentally demote it to "absent" — and that verifies nothing, so the outcome is an invalid-signature verdict rather than a silent pass. "I was given no key" and "I was given a key and could not load it" are different questions and must not share an answer.
Each defect converts a required check into an optional one by way of a falsy value, and in both cases the resulting behaviour is indistinguishable from correct operation on honest data. Tests written from the happy path pass. The general rule worth extracting: in verification code, every branch that skips a check should be justified by an explicit statement of intent from the caller, never inferred from the absence of data — because absence is exactly what an adversary controls.
§10The result
Five fields, each traceable to an attack that works without it: the construction and system (domain), the party (chain identifier), the position (sequence), the history (previous hash) and the content (record hash). Determinstic signatures over an injective encoding, an envelope version per record so the format can move without rewriting history, and a verifier that fails closed on every absence.
What none of it does is detect the records that were never handed to the verifier at all. A chain with its final entries removed is a chain that verifies perfectly — every hash, every link, every signature — because verification can only examine what it was given. That is the subject of the next paper, and it is the limit that most systems, including careful ones, describe least honestly.
References
- S. Josefsson, I. Liusvaara, Edwards-Curve Digital Signature Algorithm (EdDSA), RFC 8032, January 2017. §5.1 (Ed25519), including deterministic nonce derivation.
- NIST, Secure Hash Standard (SHS), FIPS PUB 180-4, August 2015.
- B. Laurie, A. Langley, E. Kasper, Certificate Transparency, RFC 6962, June 2013 — the tree construction the record identity in Paper 002 is built on.