Cryptographic Agility — Scheme-Tagged Witnesses with Ed25519 Default and ML-DSA-65 FIPS Plug-In
Accepted
Context
The protocol signs witnesses (ADR-024 acting-binding, ADR-023 G5 commitment) and, since ADR-046, substrate-view learning adjustments, with Ed25519. Ed25519 is a classical scheme whose security rests on the elliptic-curve discrete-log problem, which Shor's algorithm breaks on a cryptographically-relevant quantum computer. Unlike encryption, signatures have no harvest-now-decrypt-later exposure — but they have a worse one for an append-only record: the day Ed25519 falls, every historical witness in the oplog (ADR-036) becomes FORGEABLE, collapsing the non-repudiation of the entire record retroactively. The witness is precisely the project's long-lived integrity substrate, so it is exactly where algorithm longevity matters. NIST standardised post-quantum signatures in 2024 — FIPS 204 (ML-DSA, derived from CRYSTALS-Dilithium), FIPS 205 (SLH-DSA), FIPS 206 (FN-DSA). Some consumer deployments will additionally face a FIPS mandate independent of the quantum timeline. Hardcoding Ed25519 into the witness format would force a breaking, record-invalidating migration the moment either pressure arrives. ADR-044 already gives key succession (rotating an actor's KEY); what is missing is agility in the ALGORITHM itself. ML-DSA-65 (NIST level 3, ~AES-192) is the natural PQC target, but its artefacts are ~50x larger (public key 1952 B, signature 3309 B vs Ed25519 32/64) and signing is materially slower, so it cannot be a blanket replacement — it must be a plug-in for the deployments that need it.
Decision
Make the signature scheme a first-class, tagged dimension of every witness, via five mechanisms. (1) SCHEME TAG — every signed witness and every signed adjustment carries a `scheme` field; an unsigned digest commitment is the tier-0/1 fallback (ADR-029), a signed witness names the algorithm that produced it. (2) DISPATCH, FAIL CLOSED — verification dispatches on the declared scheme. A recognised-but-unbuilt scheme and an unknown scheme both FAIL (distinct non-zero exits); verification never silently accepts a signature whose scheme it cannot evaluate, and never coerces an unknown tag to Ed25519. (3) ED25519 DEFAULT, PQC OPT-IN — Ed25519 is the default for everyone (fast, 32/64-byte artefacts); a PQC scheme is selected per deployment or per actor, never mandated globally. (4) VARIABLE-LENGTH ENCODING — signatures and public keys are stored as variable-length hex, so a 3309-byte ML-DSA signature needs no format change; the witness record must not assume fixed artefact sizes. (5) ML-DSA-65 AS THE FIPS PLUG-IN — `ml-dsa-65` is the recognised PQC scheme slot, built behind a `pqc` Cargo feature backed by a CMVP-validated module (aws-lc-rs in FIPS mode), not an unvalidated pure-Rust implementation; a deployment may claim FIPS only when bound to the validated module. The seam ships now (scheme tag + dispatch); the ML-DSA backend is the deferred plug-in.
Constraints
- Hard Every signed witness and signed adjustment carries a `scheme` tag identifying the algorithm that produced the signature
- Hard Verification dispatches on the declared scheme and fails (non-zero exit) on a recognised-but-unbuilt or unknown scheme; it never silently accepts or downgrades to Ed25519
- Soft Ed25519 is the default scheme; a PQC scheme is selected per deployment or actor and is never mandated globally
- Hard Signatures and public keys are stored as variable-length hex; the witness record must not assume fixed artefact sizes
- Soft A deployment may claim FIPS only when the PQC scheme is bound to a CMVP-validated crypto module, not an unvalidated pure-Rust implementation
Alternatives considered
- Keep Ed25519 hardcoded with no scheme tag — rejected: Forces a breaking, record-invalidating migration the moment quantum or FIPS pressure arrives, and offers no way to keep historical witnesses verifiable across the transition. The witness format would have to change under the whole oplog at once.
- Adopt ML-DSA globally now, replacing Ed25519 — rejected: 50x larger artefacts, materially slower signing, and a validated-module dependency imposed on every adopter — including those with no quantum or FIPS requirement. Collapses the formalization-vs-adoption Spiral toward mandatory heavyweight crypto.
- Separate witness formats per scheme — rejected: N formats means N verify paths and no uniform record. A single format with a scheme tag and variable-length artefacts expresses the same agility with one code path and one stored shape.
- Treat an unknown or absent scheme as Ed25519 (lenient verify) — rejected: A forgery surface: a signature under a scheme the verifier silently downgrades would be accepted. Verification must fail closed on anything it cannot evaluate.
Anti-patterns
- Hardcoded signature scheme — Signing and verifying with a compile-time-fixed algorithm and no scheme tag on the witness, so migrating the algorithm requires rewriting every historical record.
- Silent scheme fallback — A verifier that accepts a signature whose scheme it does not recognise, or coerces an unknown/missing tag to Ed25519, creating a downgrade forgery surface.
- PQC mandated globally — Forcing a heavyweight PQC scheme on every deployment regardless of quantum or FIPS pressure, imposing 50x artefacts and slower signing where they buy nothing.
- Unvalidated FIPS claim — Claiming FIPS compliance while bound to an unvalidated implementation of ML-DSA — satisfying the algorithm name but not the mandate.