Skip to content

Design analysis: KERI-AID-owned MPFS leaves (claude)

What ships, and the accepted design

Historical vetting of an archived specification. Nothing here ships. The current machine is the Lean checkpoint and the simulations on the home page.

Read-only analysis. Repos inspected: cardano-mpfs-onchain (validators/cage.ak, types.ak, lib.ak, docs/architecture/proofs.md), cardano-mpfs-offchain (cardano-mpfs-cage-tx, cardano-mpfs-client, cardano-mpfs-verify), cardano-mpfs-offchain-issue-258, cardano-mpfs-cage. The brief names state.ak / request.ak / shared.ak; the live on-chain repo has consolidated these into cage.ak (spend+mint), types.ak (datums/redeemers), lib.ak (token helpers). The older split survives only in a dist-newstyle cache. Citations below use the live files.

Executive summary (5 lines)

  1. Today the oracle has unilateral write authority over every leaf: Modify only checks an MPF proof + the oracle's signature; the requestOwner field is never bound to leaf content at fold time (cage.ak:517-605), and request UTxOs are permissionlessly creatable, so the oracle fabricates any (key,value).
  2. The hard constraint holds: PlutusV3/Aiken can do one Ed25519 verify + blake2b per touched leaf, but cannot replay a KEL — so on-chain ownership must reduce to one sig against an on-chain-anchored current key-state, KEL replay staying off-chain in the pure verifier.
  3. Recommendation: Design B, in its strongest form — a second MPF (identityRoot) mapping AID → keyStateAnchor, with value-keys namespaced under their owner AID (key = H(AID ‖ subkey)) so ownership is implicit in the key and a single identity entry covers all of an AID's leaves. This gives O(1) rotation; the naive B1 (key → keyState) and Design A (owner embedded in each leaf) both degrade to O(leaves-owned) rotation and are rejected.
  4. Refinement: put identityRoot in its own UTxO/thread token, referenced read-only by data Modify and mutated by permissionless, self-authorizing rotation — otherwise the single oracle-signed State UTxO lets the oracle censor rotations and thereby keep a stolen key alive (the one residual that quietly breaks KERI recovery).
  5. Biggest risk is not on-chain cost — it is a wasm/js-portable Ed25519 + CESR in cardano-mpfs-verify (its crypto today is cardano-crypto-class, whose Ed25519 is libsodium-FFI and a known wasm blocker). Prototype that build first.

0. What the code actually does today (basis for everything below)

Datum (types.ak:205-222): a single State per cage — 

State { owner: VerificationKeyHash, root: ByteArray /*32B value-MPF root*/,
        tip: Int, process_time: Int, retract_time: Int }
One root, one owner (a Cardano payment-key hash).

Modify (cage.ak:250-277, 639-687): expect StateDatum(state), validateOwnership (= oracle VKH in extra_signatories, cage.ak:366-371), then foldl over tx.inputs with mkAction (cage.ak:517-605). For each input that is a RequestDatum whose requestToken == tokenId, it pops one RequestAction and applies mpf.insert/delete/update(root, requestKey, …, proof). Final root must equal the output datum's root (cage.ak:675).

The forgery vector, precisely. In mkAction, requestOwner is read only to build the lovelace-refund list (cage.ak:589-595); it is never used to authorize the (requestKey, requestValue) transition. Request UTxOs are created permissionlessly (Contribute is signature-free, cage.ak:243-249, 416-437). Therefore the oracle can: mint a request UTxO with requestOwner = anyone, requestKey = K, requestValue = Insert/Update/Delete(V), supply a valid MPF proof, sign as state.owner, and write any leaf to any value. requestOwner is a refund address + retract authorizer, not an integrity binding. This is the trust the brief wants the contract to remove.

Leaf bytes (confirmed both sides): MPF hashes key and value with blake2b-256; off-chain mkMPFHash = blake2b256 matches blake2b_256(key)/blake2b_256(value) in the Aiken MPF lib. Conceptually leaf = (blake2b(key), blake2b(value)). Off-chain Fact{key, value} are raw bytes; root is Root ByteString (32B).

Verifier (cardano-mpfs-verify, pure, cross-target): replays CSMT (UTxO) and MPF (facts) inclusion/exclusion proofs against a trusted snapshot root; no Ed25519 anywhere (deps: cardano-crypto-class for blake2b, cborg, mts:{csmt-verify,mpf-write}). No KERI/AID/owner/per-leaf-signature/second-trie concept exists anywhere in either repo.

Constraint check (done myself). Aiken/PlutusV3 exposes verify_ed25519_signature + blake2b_256 and the secp256k1/BLS verifies — all single-shot, cheap enough for a handful per tx. There is no primitive to parse CESR, iterate an unbounded event list, or walk a pre-rotation hash-chain within budget. So the constraint in the brief is real: on-chain = one sig vs anchored key-state; KEL replay = off-chain. Accepted as a hard boundary.

1. On-chain enforcement at Update, per design

Design A — owner embedded in the leaf

Self-contained leaf: value = encode(payload, curKeyDigest, nextKeyDigest, seq). At Update of key K: 1. mpf inclusion proof of old leaf K → oldValue (gives the validator curKeyDigest, nextKeyDigest, seq for free — they are inside the proven value). 2. Redeemer carries ownerKey (pre-image); check blake2b(ownerKey) == curKeyDigest. 3. verify_ed25519(ownerKey, msg, sig), msg = H(tokenId ‖ K ‖ oldPayload ‖ newPayload ‖ seq). 4. mpf.update(root, K, proof, oldValue, newValue) writes the new leaf (with seq+1, possibly a rotated curKeyDigest/nextKeyDigest).

No second root is referenced — ownership rides in-band. Redeemer per leaf: { proof, ownerKey, sig }. Cheap to reference (nothing external), but see §2/§5 for why this in-band coupling is fatal for rotation.

Datum gains a root; redeemer gains an identity proof + sig per touched leaf.

State { owner, valueRoot, identityRoot, tip, process_time, retract_time }
//                         ^ NEW: MPF root of  AID -> keyStateAnchor

RequestAction =
  | UpdateAction { valueProof: Proof          // K: oldV->V in valueRoot (existing)
                 , identityProof: Proof        // AID -> keyState in identityRoot
                 , ownerKey: ByteArray          // ed25519 pubkey pre-image (32B)
                 , ownerSig: ByteArray }        // 64B over the transition
  | Rejected                                    // unchanged (oracle GC)
On-chain check per touched value-leaf K owned by AID: 1. Derive/locate owner. Namespaced variant (preferred): recompute AID as the declared prefix of K and require K == H(AID ‖ subkey) (or K's leading 32B == AID); the oracle cannot place a leaf under a prefix it can't sign for. General variant: read ownersRoot[K] = AID via an extra inclusion proof (a third root — see §2). 2. Resolve key-state: mpf inclusion of AID → keyState=(curDigest,nextDigest,seq) against identityRoot (the datum's trusted root). 3. blake2b(ownerKey) == curDigest. 4. verify_ed25519(ownerKey, msg, ownerSig) with msg binding tokenId, K, op, oldV, newV and an anti-replay term (see §0/§3 binding discussion). 5. Existing mpf.insert/delete/update against valueRoot. 6. Oracle sig still required (liveness/fee/ordering) but is necessary-not-sufficient.

Cost per leaf: +1 blake2b, +1 MPF inclusion verify (identity), +1 ed25519, on top of the existing value-MPF op. For a batch of m leaves: m sigs + ≈2m MPF verifies. PV3 budget makes m ≈ 10–20 realistic; large batches must shard across txs (they are already proof-bounded). The identity proof is O(log |AIDs|); value proof unchanged.

Why B references the owner the way it does. The chain trusts exactly one thing it can read locally: a root in its own input datum. So the anchor (identityRoot) lives in the datum; the proof that AID's key-state is what the KEL says is off-chain. The validator verifies the local step (sig by the key whose digest the anchored state commits); it does not verify the global KEL.

2. Data structures, proof composition, claiming a new key

Roots. - A: one root (valueRoot), identity in-band → datum unchanged, redeemer grows. Zero new roots but O(n) rotation (§5). - B-namespaced: two roots — valueRoot, identityRoot (AID→keyState). Ownership is implicit in the key, so no key→AID map is needed. - B-general (arbitrary keys): three roots — add ownersRoot (K→AID). Each value write composes three inclusion proofs (valueRoot op, ownersRoot[K]=AID, identityRoot[AID]).

identityRoot leaf: key = AID (32B self-certifying prefix), value = serialize(curDigest ‖ nextDigest ‖ seq ‖ threshold-meta). MPF hashes both as usual.

Proof composition (B-namespaced Update): snapshot → datum(valueRoot, identityRoot) ⟹ verify identityRoot[AID] (inclusion) ⟹ blake2b(ownerKey)=curDigest ⟹ ed25519(ownerKey, msg, sig) ⟹ valueRoot op. All four are independent single-shot checks; none requires iteration.

Establishing ownership of a NEW key — the genuinely hard sub-problem. Insert proves absence, and absence binds no one. Options, with honest trust assessment: - Self-namespacing (best). Require K under AID's prefix and a sig by AID's current key. Then "owner of K is necessarily AID" is cryptographic, not assigned: the oracle cannot squat AID's namespace, and there is no land-grab for known AIDs. Unowned space outside any prefix can be oracle-assigned or forbidden. - First-claim (race-prone). First request to insert K sets K→AID. The oracle orders txs, so it always wins the race and can squat. Weak. - Oracle-assigned. Oracle writes ownersRoot[K]=AID once; thereafter cannot alter content (needs AID sig). Trust shrinks from "forge forever" to "assign correctly once" — a real reduction, acceptable as a transitional/hybrid policy, but still trust. - Bonded. Claim requires a deposit; slashable on dispute. Adds an oracle/court. Heavy.

AID inception must itself be bound: require the AID to be self-certifying (AID == H(inception event embedding curKeys + nextDigest), i.e. KERI's own derivation), so InceptIdentity can be permissionless (absence proof on identityRoot + self-cert check) yet unforgeable — the oracle can mint its own AIDs freely (fine) but cannot fabricate an AID prefix matching an externally-known identity.

3. Operation model

Op Today Under B-namespaced
Boot/Mint empty valueRoot, owner=oracle also empty identityRoot
InceptIdentity — permissionless insert AID→keyState; absence proof + self-cert
Insert (claim K) oracle-only sig by AID (identity inclusion) + K under AID prefix
Update/Delete oracle-only identity inclusion + owner sig over transition; oracle sig still needed for liveness
Rotate — reveal pre-rotated key (blake2b==nextDigest), new nextDigest, sig by revealed key; mpf.update identityRoot[AID], seq+1
Retract requestOwner VKH (cage.ak:214-242) unchanged; request now also carries owner sig so it is foldable
Reject/GC oracle, Phase-3 (cage.ak:578-587) unchanged — oracle can decline, cannot forge
End oracle sig + burn (cage.ak:269-271, 336-341) unchanged

Who authorizes a leaf mutation: both — the leaf owner's Ed25519 sig authorizes the content; the oracle's sig authorizes inclusion/ordering/fee. Clean separation: forgery needs the owner key; liveness/GC stays with the oracle.

How the request carries the sig: extend the off-chain Request/RequestAction to carry ownerKey + ownerSig (the Modify builder in cardano-mpfs-cage-tx/.../Cage/Update.hs and the Request builder in .../Cage/Request.hs already thread proofs/datums; this is an additive field + hand-written ToData in .../Cage/Serialize.hs to keep byte-parity with Aiken).

Anti-replay binding (subtle, prototype this). msg must pin the transition to this cage and this state so a captured sig can't be reapplied. Three candidates: - per-leaf seq in the value/owner-meta — O(1), but turns every write into a counter bump and pollutes the value; - bind to pre-state valueRoot — no counter, sig valid only against the exact snapshot the owner saw (oracle reorder invalidates it — a feature), but multi-owner batches fold the root between steps, so all owners must sign vs the initial batch root and the validator must check sigs against the pre-fold root; - bind to (AID, seq) from identityRoot — robust but serializes all of an AID's writes on its identity entry (contention). Recommendation: pre-state-root binding + batch atomicity, fall back to per-leaf nonce if concurrency demands it. Same-batch rotate-then-write of one AID must be ordered or forbidden (sign against old or new key?).

4. Forgery resistance (adversarial enumeration)

Design B-namespaced. Oracle CAN: order/batch, set fee/timing, Reject/GC expired requests, censor (refuse any write), create its own AIDs and own leaves under them, End the cage. Oracle CANNOT: write/alter/delete a leaf under an AID whose key it does not hold; rotate an AID it does not control; forge an AID prefix matching a known external AID (collision-resistance); replay an owner sig onto a different transition/state (if §3 binding holds). Residual trust: (a) censorship/liveness — mediated, not forgeable; (b) inception/claim self-cert rests on hash collision-resistance; (c) anchor-freshness gap, see §5.

Design A. Same content forgery-resistance for existing leaves (sig vs leaf-embedded key). But: worse first-claim (no namespacing structure to lean on), O(n) rotation, and the data plane is polluted with identity material (every reader must parse keys out of values). A buys the same headline guarantee at structurally worse cost.

The residual that quietly matters (both designs, sharpened for B): every datum mutation spends the single State UTxO, which validateOwnership ties to the oracle's signature (cage.ak:260, 366-371). If rotations also flow through that UTxO, the oracle can censor a rotation and thereby keep a stolen current key usable for data writes. KERI's "rotate to lock out the thief" then depends on oracle liveness — a real weakening. Fix in §5/§8 (separate identity UTxO, permissionless rotation).

5. Key rotation / compromise

Rotation step (O(1) in B, the decisive advantage): identityRoot[AID]: (curDigest, nextDigest, seq) → (blake2b(revealedNextKey), newNextDigest, seq+1) where the redeemer supplies revealedNextKey with blake2b(revealedNextKey) == nextDigest (proves pre-rotation), newNextDigest, and rotSig = ed25519(revealedNextKey, H(AID ‖ newCurDigest ‖ newNextDigest ‖ seq+1 ‖ binding)). Validator: identity inclusion (old) → pre-image check → sig by revealed key → mpf.update identityRoot. One Ed25519, one mpf.update, regardless of how many leaves the AID owns. In A the same rotation must rewrite every leaf carrying the key-state → O(leaves-owned); this is the single most important reason to prefer B.

Pre-rotation preserved. Because rotation requires the pre-committed next key (not the current one), theft of the current signing key does not enable rotation — the standard KERI guarantee, reproduced on-chain with one hash + one verify.

Recursion (off-chain KEL ↔ on-chain anchor). The on-chain (curDigest, nextDigest, seq) is a checkpoint. The full KEL — every interaction/rotation event, witness receipts, pre-rotation chain, duplicity checks — is replayed off-chain to prove the checkpoint is AID's legitimate current projection. The chain enforces only the local monotonic step (each on-chain rotation signed by the revealed pre-rotated key, seq strictly +1); the off-chain verifier proves global legitimacy and that the anchored digest equals the replayed key-state. This is exactly the on-chain-anchor / off-chain-replay split the brief asks for.

Compromise race + the censorship caveat. With the current key stolen but un-rotated, the thief can solicit data writes (current key still valid) until the holder lands a rotation. If rotations are oracle-mediated, the oracle can stall the holder's rotation and extend the thief's window. Therefore make rotation permissionless and self-authorizing, on a UTxO the oracle does not gate (§8). Then the holder can always self-rotate; the worst the oracle does is censor data (freeze), never forge and never block recovery.

6. Off-chain pure verifier (wasm/js)

Chain enforces: local step — one sig vs anchored key-state, one membership proof, root transition. Reader verifies (off-chain, pure): snapshot anchor → value-MPF inclusion (data) → identity-MPF inclusion (AID→keyState) → full KEL replay proving that key-state is AID's true current state → (for write-receipts) the owner sig over the transition. The verifier is the only place the global KERI guarantee is checked.

Purity is preserved — KEL replay is deterministic (parse CESR, verify per-event Ed25519, check pre-rotation digests, detect duplicity). But the new primitives are the portability risk: a CESR parser and Ed25519 verify must compile to wasm32-wasi and GHC-JS. Today cardano-mpfs-verify carries no Ed25519, and its cardano-crypto-class Ed25519 is libsodium-FFI — a known wasm blocker (consistent with this repo's documented Haskell-wasm dep pain). A pure/wasm-friendly Ed25519 (and a minimal CESR reader) must be admitted before the design is, per the constitution's verifier-portability rule. The write path (off-chain tx builder, native) may keep using libsodium; only the verifier must be portable.

7. Migration / compat

  • Datum is breaking: identityRoot (and, for B-general, ownersRoot) added to State. The existing Migrating path (cage.ak:792-818, carries root over) extends to initialise the new root(s) to empty. New script hash → new policy id → tokens migrate via atomic burn+mint.
  • Legacy leaves: pre-migration leaves have no owner. Policy needed: grandfather them as oracle-owned (oracle retains trust over legacy data only) or require owners to re-claim via inception+claim. A hybrid (oracle-trusted legacy + KERI-owned new) shrinks trust incrementally without a flag-day.
  • Redeemer is breaking: RequestAction grows ownerKey/ownerSig; new Rotate/Incept actions; clients must upgrade. Hand-written ToData in …/Cage/Serialize.hs keeps Aiken parity.
  • Budget/size: +1 MPF verify +1 Ed25519 per touched leaf → batch sizes ~halve; script size grows modestly (Ed25519 + extra MPF calls are stdlib). Proof-bearing responses grow by one identity proof per leaf (+ owners proof in B-general).

8. Recommendation

Adopt Design B, namespaced, with identity in its own UTxO. Reject A and reject B1.

  • B over A: identical content-forgery resistance, but B gives O(1) rotation, a single source of truth per identity, and a clean data plane. A's in-band key-state forces O(leaves-owned) rotation and pollutes values — disqualifying at scale.
  • Namespaced (key = H(AID ‖ subkey)) over key→keyState (B1): B1 duplicates an AID's key-state per key and re-incurs O(n) rotation; namespacing makes ownership cryptographic, needs only one identity entry per AID, and kills squatting of known AIDs.
  • Identity in its own UTxO/thread token, referenced read-only by data Modify, rotated by permissionless self-authorizing txs: decouples KERI recovery from oracle liveness (§4/§5), at the cost of one extra UTxO and serialization on the identity UTxO (shard by AID later if contended). If a single-UTxO design is kept for v1, document the censorship-of-rotation residual explicitly.

Decisive trade-offs: O(1) vs O(n) rotation (the swing factor); data-plane hygiene; one extra UTxO + cross-UTxO reference (the cost of censorship-resistant rotation).

Biggest risk: wasm/js-portable Ed25519 + CESR in the pure verifier — a toolchain/portability problem, not a contract one. It can sink the whole approach if it can't be built; everything else is incremental.

Prototype first, in this order: 1. wasm32-wasi + GHC-JS build of Ed25519 verify (and a stub CESR reader) inside cardano-mpfs-verify. If this can't be made portable, stop — re-scope to a trusted-verifier model. (highest-risk, cheapest to falsify) 2. On-chain Modify with identity-inclusion + per-leaf Ed25519, measure PV3 exec units to fix the real max batch size. 3. Rotation redeemer with pre-rotation reveal on a standalone identity UTxO; prove O(1)-rotation + permissionless recovery. 4. Pin the anti-replay binding (pre-state-root vs per-leaf nonce vs identity-seq) under a concurrent multi-owner batch — the subtlest correctness question.

Hybrid worth keeping: oracle-assigned/legacy leaves coexisting with KERI-namespaced leaves during migration — narrows trust monotonically without a flag-day, and lets steps 1–4 ship behind real usage rather than all at once.