Capability ledger substrate
← All revisions
editorial(substrate): move capability-ledger + merkle-proofs to substrate/ — correct category, slug, and _index MOC entries
@@ -0,0 +1,381 @@ --- schema: foundry-doc-v1 title: "The Capability Ledger Substrate" slug: capability-ledger-substrate category: substrate type: topic quality: complete short_description: "The Capability Ledger Substrate is the mechanism by which every access-control decision in a Foundry deployment becomes a cryptographically auditable event anchored to a log the customer controls." status: active bcsc_class: no-disclosure-implication last_edited: 2026-05-22 editor: pointsav-engineering cites: [] references: - id: 1 text: "C2SP signed-note specification" url: "https://github.com/C2SP/C2SP/blob/main/signed-note.md" - id: 2 text: "RFC 9162 — Certificate Transparency Version 2.0" url: "https://datatracker.ietf.org/doc/html/rfc9162" paired_with: capability-ledger-substrate.es.md --- > The Capability Ledger Substrate is the mechanism by which every access-control decision in a Foundry deployment becomes a cryptographically auditable event anchored to a log the customer controls. The Capability Ledger Substrate extends the seL4 microkernel's native capability model — which is correct by formal proof — with a transparency layer that makes the audit record portable, customer-rooted, and verifiable by third parties without any trust relationship with the operator. ## 1. What the Capability Ledger Substrate is An operating system kernel mediates access to hardware resources. When a process wants to write to a memory region, open a file, or send a network packet, the kernel decides whether the process is permitted. This decision is what "access control" means at the system layer. The seL4 microkernel makes access-control decisions using *capabilities* — unforgeable tokens that encode exactly what resource a process holds and what operations it may perform on that resource. A process that does not hold a valid capability for a resource cannot access it; there is no override, no ambient authority, no root user that bypasses the check. The seL4 capability model has been formally verified: the kernel's C implementation is proven correct against a mathematical specification. This is the foundation. The Capability Ledger Substrate does not replace this foundation. It adds one new property: every capability invocation decision can be linked, via a Merkle inclusion proof, to a checkpoint in a signed transparency log. The customer holds the signing keys for that log. The customer can audit the full history. Third parties can verify individual entries against published checkpoints without access to the full log. The result is a security substrate with two independently verifiable layers: the kernel layer (seL4 formal proof — the kernel cannot be misled into honoring a capability it should refuse) and the ledger layer (Merkle audit trail — the history of capability state changes cannot be rewritten without the customer's apex keys). The combination is what the Capability Ledger Substrate names as the leapfrog: neither layer alone provides both properties. ## 2. The `Capability` type — fields, kernel binding, and the ledger anchor In `system-core`, the `Capability` struct is the ledger-bound authorisation token: ```rust pub struct Capability { pub cap_type: CapabilityType, // Endpoint, Memory, Irq, Notification, CNode pub rights: Vec<Right>, // Read, Write, Invoke, Grant, Revoke pub expiry_t: Option<u64>, // Unix seconds; None = no built-in expiry pub witness_pubkey: Option<String>, // SSH public key for expiry extension pub ledger_anchor: LedgerAnchor, // Points into the customer Merkle log } ``` The `cap_type` and `rights` fields map directly to seL4 CDT (Capability Derivation Tree) semantics: an `Endpoint` capability with `[Invoke]` rights is the seL4 object that lets one protection domain send a message to another. A `Memory` capability with `[Read, Write]` is an IPC-shared memory region. These are the kernel's native vocabulary; the Capability Ledger Substrate adopts them without modification. The `ledger_anchor` field is the new binding. It identifies the C2SP signed-note checkpoint in the customer transparency log at which this capability was committed: ```rust pub struct LedgerAnchor { pub origin: String, // e.g. "foundry.<module-id>.capability-ledger" pub tree_size: u64, // Log size at commitment time pub root_hash: Hash256, // Merkle root at that size } ``` A capability that carries a `ledger_anchor` pointing to tree position 1,247 in a log with a known root can be verified: produce an inclusion proof that the capability's SHA-256 hash is at leaf 1,247 in the tree, and verify that proof against the signed checkpoint at tree_size = 1,247. If the proof verifies, the capability's existence in the log is established. If the log has a published checkpoint history, the anchor ties the capability to a specific point in that auditable history. The `Capability::hash()` method computes the SHA-256 of the JSON-serialized struct. This is the value used as the leaf in the Merkle tree and as the key in the revocation set. Determinism is tested: the same struct always produces the same hash; changing any field — including `expiry_t` or the anchor's `tree_size` — produces a different hash. ## 3. Time-Bound Capabilities (Mechanism A) A capability with a non-None `expiry_t` field may not be invoked after the Unix timestamp `t` without an extension. This is Mechanism A, Time-Bound Capabilities, per the substrate operational specification §5. The extension mechanism requires two parties: the capability itself names a `witness_pubkey` (an SSH ed25519 public key), and the holder of that key signs a `WitnessRecord`: ```rust pub struct WitnessRecord { pub capability_hash: Hash256, // identifies which capability is extended pub new_expiry_t: u64, // must be greater than the previous expiry_t pub signature: Vec<u8>, // ssh-keygen -Y sign, namespace "capability-witness-v1" } ``` The namespace tag `capability-witness-v1` prevents cross-namespace replay. An ed25519 signature produced by `ssh-keygen -Y sign` over a commit message or an apprenticeship verdict cannot be replayed as a capability witness extension, because the namespace tags differ. The `system-ledger` `witness.rs` module verifies signatures by shelling out to `ssh-keygen -Y verify` with the correct namespace. The kernel decision flow for a time-bound capability is: 1. If `now < expiry_t`: honor the invocation (no witness needed) 2. If `now >= expiry_t` and no witness is supplied: `Refuse(Expired)` 3. If `now >= expiry_t` and a witness is supplied: - Verify the witness signature against the capability's `witness_pubkey` - Verify a Merkle inclusion proof that the witness record's hash is in the current log - If both pass: `ExtendThenAllow { new_expiry_t }` — honor the invocation and update the ledger - If either fails: `Refuse(WitnessSignatureInvalid)` or `Refuse(WitnessNotInLedger)` The inclusion-proof requirement on the witness record is the key property: a witness extension cannot be honored until it has been committed to the customer's transparency log and an apex-signed checkpoint covers it. The customer's apex sign-off is a prerequisite for capability lifetime extension. This cannot be forged without the customer's ed25519 apex keys. ## 4. The apex-ownership ceremony (N+3+ handover) The customer's apex keys are the root of trust for the entire capability ledger. A transparency log is only as trustworthy as the process for establishing and rotating those keys. The Capability Ledger Substrate specifies a formal ownership-transfer ceremony that produces an auditable handover record in the same log it secures. The ceremony proceeds at checkpoints N, N+1, N+2, N+3+: | Height | Action | Required signatures | |---|---|---| | N | Final checkpoint under P-old authority | P-old only | | N+1 | Revocation entry: P-old is revoked | P-old (signing its own revocation) | | N+2 | Handover checkpoint — co-signed by both apexes | P-old AND P-new (both required) | | N+3+ | Post-handover checkpoints | P-new only; P-old refused with `StaleApex` | The C2SP signed-note format directly supports multi-signature: the same checkpoint body (origin + tree_size + root_hash) can carry multiple signature lines, each from a different named key. The `SignedCheckpoint::verify_apex_handover` composed primitive checks both signatures on a handover checkpoint. The N+3+ invariant is: any capability invocation presenting a checkpoint signed only by P-old at height N+3 or later is refused with `Refuse(StaleApex)`. The `ApexHistory` module in `system-ledger` tracks the effective lifetime of each apex (`effective_from` and `effective_until` heights) and enforces this invariant at consult time. The ceremony has three properties that matter to a customer: 1. **Atomicity**: the handover is a single, self-contained event in the log. There is no out-of-band state migration. The log records the full ceremony. 2. **Auditability**: any third party examining the log can identify the exact checkpoint where P-old's authority ended and P-new's authority began. 3. **Finality**: once the N+2 handover checkpoint is published, P-old cannot produce a valid checkpoint for N+3+ that the kernel will accept. The key rotation is permanent absent a further ceremony. An end-to-end test in `system-ledger` (`full_handover_ceremony_end_to_end`) verifies all four stages: pre-handover P-old allows; revocation applies; handover with both signatures accepts; post-handover P-old-only is refused with `StaleApex`. ## 5. The `LedgerConsumer` state machine — consult flow and Verdict types The `LedgerConsumer` trait in `system-ledger` is the kernel-facing interface: ```rust pub trait LedgerConsumer { fn consult_capability( &self, cap: &Capability, current_root: &SignedCheckpoint, now: u64, witness: Option<&WitnessRecord> ) -> Result<Verdict, ConsultError>; fn apply_revocation(&mut self, event: RevocationEvent) -> Result<(), LedgerError>; fn apply_apex_handover(&mut self, ...) -> Result<(), LedgerError>; fn apply_witness_record(&mut self, record: WitnessRecord, proof: InclusionProof) -> Result<(), LedgerError>; } ``` `consult_capability` is the read-side hot path. It returns one of three verdicts: | Verdict | Meaning | Kernel action | |---|---|---| | `Allow` | Capability is current and unexpired | Honor the invocation | | `Refuse(reason)` | Capability invalid; reason provided | Deny the invocation | | `ExtendThenAllow { new_expiry_t }` | Witness extension accepted | Extend + honor | The consultation decision flow: 1. **Apex validity check**: is the current_root signed by the recognized apex? If the checkpoint is not apex-signed, all bets are off — `Refuse(ApexInvalid)`. 2. **Post-handover invariant check**: if an apex handover has occurred, is this checkpoint from a refused (stale) apex? If so, `Refuse(StaleApex)`. 3. **Revocation check**: is the capability's hash in the revocation set? If so, `Refuse(Revoked)`. 4. **Expiry check**: is `now < expiry_t` (or is `expiry_t` None)? If so, `Allow`. 5. **Witness path**: if expired, attempt the witness extension flow (§3 above). The three write-side methods (`apply_revocation`, `apply_apex_handover`, `apply_witness_record`) update ledger state that subsequent consultations read. They are separated from the read-side precisely because the kernel's read/write access patterns differ: `consult_capability` is called on every invocation; the write methods are called much less frequently (revocation events and apex handovers are rare; witness extensions happen at capability expiry boundaries, which may be hours or days apart). ## 6. Cache discipline — why the 358,000× speedup is architecturally critical The `consult_capability` decision flow requires verifying that the current checkpoint is apex-signed. An ed25519 signature verification takes approximately 4 milliseconds on the Intel Xeon 2.20 GHz hardware where the substrate is developed. Any workload calling `consult_capability` hundreds of times per second would spend most of its time doing signature verification — an unacceptable overhead for kernel-mediated access control. The `CheckpointCache` in `system-ledger` resolves this. It holds the most recent N (default 64) verified checkpoints, keyed by tree_size. A cache hit — looking up a checkpoint the ledger has already verified — costs 11.2 nanoseconds. The cache stores the verified `SignedCheckpoint` objects; a lookup confirms the checkpoint is present and returns it without re-running ed25519. | Operation | Time | Ratio | |---|---|---| | Cache hit (most-recent lookup) | 11.2 ns | 1× (baseline) | | Cache miss (full 64-entry scan) | 362 ns | ~32× | | `verify_signer` (ed25519, 1 apex) | 4.01 ms | ~358,000× | | `consult_capability` (full path, cache miss) | 3.74 ms | ~334,000× | In steady-state operation, the kernel publishes checkpoints infrequently (each checkpoint commits a batch of capability state changes). Between checkpoint publications, every capability invocation hits the cache. The cache hit rate approaches 100% for any sustained workload. The ed25519 verifier runs only when a new checkpoint is published — which happens on the write path, not the read path. The 64-entry bound covers: the apex-handover window (during which P-old and P-new checkpoints coexist at heights N+1 and N+2), the overlap period when multiple system components hold references to slightly different recent checkpoints, and reasonable checkpoint publishing rates without exceeding kernel working-set constraints. The bound is a configuration choice, not a protocol requirement. The architectural lesson is that the cache and the Merkle inclusion proofs are not alternatives — they answer different questions on different access paths. The cache makes the read path fast. The inclusion proofs make the write path trustworthy. Both are required for a production substrate. ## 7. Revocation and post-handover invariants **Revocation** is the mechanism for permanently revoking a capability's authority. A `RevocationEvent` carries the capability's SHA-256 hash and a revocation record. After `apply_revocation` is called, `consult_capability` returns `Refuse(Revoked)` for that capability hash regardless of expiry or witness state. The revocation set is a `HashSet<Hash256>` in the in-memory implementation — O(1) membership check. Revocation events are themselves log entries, anchored to the same customer-signed transparency log as capability commitments. An auditor examining the log sees the full sequence: capability committed at height N₁, revoked at height N₂, and no subsequent witness extension is valid after N₂ because any such extension would need to reference a checkpoint at N₂ or later, where the revocation entry is visible. The **post-handover invariant** is a different property: it governs which apex signing key is authoritative on a given checkpoint, independent of individual capability revocation. Once the apex handover ceremony completes at height N+2, any invocation presenting a checkpoint signed only by P-old at height N+3 or later is refused. This prevents P-old from re-asserting authority after transferring it — the log records the transfer, and the kernel enforces the cutoff height. The two properties operate at different levels of the substrate: - Revocation is per-capability (a specific token is invalid) - Post-handover is per-epoch (the old apex key is invalid for an entire period of time) Both are enforced by the `InMemoryLedger` in `system-ledger`. Both are tested in the `full_handover_ceremony_end_to_end` integration test. ## 8. Relationship to the WORM ledger The WORM (Write-Once Read-Many) ledger substrate is the foundational record-storage layer of the Foundry architecture. It implements a C2SP tlog-tiles compatible transparency log: append-only, content-addressed, cryptographically signed by an apex. Service-level consumers (notably `service-fs`, the Ring 1 WORM backend) interact with it at the application tier. The Capability Ledger Substrate is the substrate-tier consumer of the same log format. The data-primitive types (`Capability`, `WitnessRecord`, `LedgerAnchor`, `SignedCheckpoint`, `InclusionProof`, `ConsistencyProof`) defined in `system-core` are the L0 schema layer. The state machine in `system-ledger` is the L1+L2 consumer. The parallel with `service-fs` is structural and deliberate: - `service-fs` is the application-tier WORM consumer: Ring 1, userspace, network-accessible, human-scale record throughput - `system-ledger` is the substrate-tier WORM consumer: kernel-adjacent, single-threaded, microsecond-scale read latency required Both use the same C2SP signed-note format for checkpoints. Both verify apex ed25519 signatures. Both accept capability-state changes (revocations, witness records) that need Merkle inclusion proofs to be trusted. The difference is the access pattern and the consequence of failure: in `service-fs`, a slow verification delays a file operation; in `system-ledger`, a slow verification delays a kernel-mediated capability invocation, which is a system-level performance constraint. This layer separation — same cryptographic primitives, different deployment tiers, different performance envelopes — is the architectural pattern the Capability Ledger Substrate formalizes. A future system that replaces `service-fs` or adds a second WORM consumer does not need to reimplement the proof mechanics; it shares `system-core` and composes the same primitives at its own tier. ## 9. Cross-references - **The Capability Ledger Substrate** — the constitutional anchor for customer-rooted Merkle-log binding in Foundry deployments. Every capability authorization is anchored to a customer-held transparency log. - **The Two-Bottoms Sovereign Substrate** — the Two-Bottoms composition (seL4 native-bottom + NetBSD compat-bottom) shares the same capability ledger substrate. The audit trail travels with the capability regardless of which bottom it runs on. - **Substrate operational specification** The 12-section specification covering: §3.1 (Capability type schema), §4 (N+3+ apex handover ceremony), §5.1 (WitnessRecord schema and Mechanism A), §6.1 (reproducible-verification artefact format), §8 (scoresheet). - **WORM ledger design** The foundational record-storage layer. §3 D1 (C2SP tlog-tiles wire format), §3 D3 (SHA-256 baseline). The Capability Ledger is a substrate-tier consumer of the same design. - **`topic-merkle-proofs-as-substrate-primitive.md`** Companion technical article covering RFC 9162 inclusion and consistency proofs, the `InclusionProof` and `ConsistencyProof` structs, verification algorithms, and performance benchmarks. Read alongside this article for the cryptographic grounding. - **Implementation state (Phase 1A)** - `system-core` v0.2.0: `Capability`, `WitnessRecord`, `LedgerAnchor`, `Checkpoint`, `NoteSignature`, `SignedCheckpoint`, `InclusionProof`, `ConsistencyProof`. 51 tests. - `system-ledger` v0.2.1: `LedgerConsumer` trait, `InMemoryLedger`, `CheckpointCache`, `RevocationSet`, `ApexHistory`, `verify_witness_signature`. 44 tests + 10 criterion benchmarks.