Summary
Investigate a verifiable key→value map (sparse-Merkle-backed, CONIKS / Key-Transparency style) as a complementary structure for resolving an identifier's current key state — instead of always replaying the full KEL.
Motivation
Today, resolving a device/identity's current key state means replaying its KEL from inception — O(n) in history length. For long-lived identities and high-volume "what is X's current key right now?" lookups, that cost grows with history.
A verifiable map gives O(log n) current-state lookup: the key hashes to a position, a lookup returns the value plus a logarithmic inclusion proof, verified against a single signed tree head — no full replay. It also gives absence proofs ("this identifier has no bound key" / "this key was never present"), which KEL replay handles awkwardly.
Relationship to existing infrastructure
This is not redundant with what we already ship:
- We have an RFC 6962 transparency log (
auths-transparency: inclusion/consistency proofs, checkpoints, C2SP cosignatures). That is an append-only, ordered structure — it proves "this was logged."
- A verifiable map is a different Merkle structure — key→value, current-state — it proves "this key currently maps to this value." The two are complementary.
- It ties directly into the key-state-notice (KSN) path and the planned witness network — both are about independently-verifiable current key state at scale. The map's signed tree head is a natural artifact for witnesses to co-sign.
Open questions to resolve in the spike
- Authoritative vs. verifiable index. Is the map a source of truth, or a fast provable index derived from the KELs? (Leaning: the KEL stays authoritative; the map is a verifiable index, with a consistency proof binding map value ↔ KEL-replay result so the map cannot silently lie or lag.)
- Tree-head signing/publication. Who signs the head, how often — witness-cosigned checkpoints?
- Consistency. How to prove the map's value for an identifier equals replaying that identifier's KEL.
- Revocation & non-membership representation in the map.
- Construction choice. Sparse Merkle vs. the transparency.dev "tiled" approach vs. others — compare proof size and operational complexity.
Scope
Design exploration / spike — not a committed structure yet. Produce a short design note plus a prototype demonstrating (1) a verifiable-map lookup with an inclusion proof against a signed head, and (2) a consistency check against the corresponding KEL. Compare against the status quo (KEL replay + KSN) on lookup cost, proof size, and ops complexity, then decide go/no-go.
Context
Surfaced in discussion with the KERI/CESR community, referencing transparency.dev's "strengthen discovery of encryption keys" work. Logging it so the idea isn't lost.
Summary
Investigate a verifiable key→value map (sparse-Merkle-backed, CONIKS / Key-Transparency style) as a complementary structure for resolving an identifier's current key state — instead of always replaying the full KEL.
Motivation
Today, resolving a device/identity's current key state means replaying its KEL from inception — O(n) in history length. For long-lived identities and high-volume "what is X's current key right now?" lookups, that cost grows with history.
A verifiable map gives O(log n) current-state lookup: the key hashes to a position, a lookup returns the value plus a logarithmic inclusion proof, verified against a single signed tree head — no full replay. It also gives absence proofs ("this identifier has no bound key" / "this key was never present"), which KEL replay handles awkwardly.
Relationship to existing infrastructure
This is not redundant with what we already ship:
auths-transparency: inclusion/consistency proofs, checkpoints, C2SP cosignatures). That is an append-only, ordered structure — it proves "this was logged."Open questions to resolve in the spike
Scope
Design exploration / spike — not a committed structure yet. Produce a short design note plus a prototype demonstrating (1) a verifiable-map lookup with an inclusion proof against a signed head, and (2) a consistency check against the corresponding KEL. Compare against the status quo (KEL replay + KSN) on lookup cost, proof size, and ops complexity, then decide go/no-go.
Context
Surfaced in discussion with the KERI/CESR community, referencing transparency.dev's "strengthen discovery of encryption keys" work. Logging it so the idea isn't lost.