The Ideas Behind Chio

Earlier research defines the mechanisms

Time-sharing systems of the 1960s had to keep one user’s computation away from another’s data. In 1972 a planning study for the US Air Force asked how one computer could serve users cleared at different levels. In 2013 Certificate Transparency proposed a public log that would let anyone audit what certificate authorities issued. The answers have names: capabilities, the reference monitor, least privilege, complete mediation, fail-safe defaults, hash trees, transparency logs, canonical encodings.

The ideas fall into three families. Ideas about authority decide what a grant contains and how it ends. Ideas about mediation decide where a call is checked and what happens when a check cannot answer. Ideas about evidence decide what a record can prove after the fact.

Err(error) => {
    let core_err = KernelCoreError::GuardError {
        guard: guard.name().to_string(),
        reason: error.deny_reason(),
    };
    return deny(core_err, Some(matched_grant_index), Some(verified));
}

Saltzer and Schroeder’s general principles apply to five Chio mechanisms. The other works each describe one mechanism or model. Chio’s receipt log uses Merkle’s tree both directly and through the Certificate Transparency construction.

A capability joins an object to the right to use it

In 1966 Jack Dennis and Earl Van Horn described the semantics of a supervisor for computations that share one machine. Each computation ran within a sphere of protection defined by a list of capabilities. A capability located an object, such as a memory segment or a file, and stated what the computation could do with it. The supervisor maintained the lists, so a computation could use a capability but could not manufacture one.

Five years later Butler Lampson stated the general model. Protection state is a matrix with a row for each domain, a column for each object, and the permitted access in each cell. An access list stores a column with its object. A capability list stores a row with the domain that holds it. The two record the same matrix and differ in who carries the authority and what a check has to look up, which Why capabilities follows cell by cell.

A Chio capability is a row made portable. An issuer signs a token naming a subject, a scope of tool grants, and a validity period. The signature of a trusted issuer stands in for the supervisor’s protected list, so a grant can cross processes and machines, and the kernel admits a token only for the subject it names. Each tool grant is a cell: a server, a tool, and the operations allowed on it. The token can also carry a delegation chain, so its holder can pass a narrower grant to another agent, and a delegated child must fit inside its parent’s grant.

pub struct CapabilityTokenBody {
    pub id: String,
    pub issuer: PublicKey,
    pub subject: PublicKey,
    pub scope: ChioScope,
    pub issued_at: u64,
    pub expires_at: u64,
    #[serde(default, skip_serializing_if = "Vec::is_empty")]
    pub delegation_chain: Vec<DelegationLink>,
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub aggregate_invocation_budget: Option<AggregateInvocationBudget>,
}

Complete mediation requires a check on every access

In October 1972 James P. Anderson’s planning study for the US Air Force described a reference monitor: a mechanism that validates every reference a running program makes against what its user is authorized to do. The study found elements of the authorization model it needed in capability systems. It then set three conditions on the mechanism that implements the monitor. It “must be tamper proof.” It “must always be invoked.” It must be “small enough to be subject to analysis and tests.”

Three years later Saltzer and Schroeder made the second condition a design principle of its own. Complete mediation reads: “Every access to every object must be checked for authority.” They added that it requires a reliable way to identify the source of every request.

Chio’s kernel is that check for governed calls. A request reaches a tool only after the kernel verifies the capability, binds it to the calling subject, matches the scope, and runs the guard pipeline, and every governed call passes that core evaluation in the same order. The mediated call traces all six stages. The decision core is a no_std Rust library with no database or network connection of its own, small enough to read whole. Selected functions are extracted into Lean and connected to protocol models by equivalence theorems, and the proof manifest names the covered semantics: capability verification, subject binding, scope matching, and the synchronous guard pipeline.

Grant only the authority the work needs

Saltzer and Schroeder’s 1975 paper set out eight design principles for protection mechanisms. Four more of them shape how Chio decides a call. Least privilege asks every program and every user to operate with the smallest set of privileges the job requires, which limits the damage an accident or an error can do. Fail-safe defaults, which they credit to E. Glaser in 1965, reads: “Base access decisions on permission rather than exclusion.”

Separation of privilege prefers a mechanism that “requires two keys to unlock it” over one that opens for a single key. Economy of mechanism asks for a design as small and simple as possible, because an error that opens an unwanted access path does not show up in normal use.

In Chio these are rules of the kernel. A grant names tools and operations, and delegation and policy can only narrow it. A call is admitted only when every check allows it, and a guard that fails with an error is a denial. The defaults hold under failure: the Tower middleware answers 502 Bad Gateway when evaluation fails, and kernel dispatch refuses a PendingApproval from an ordinary guard as unsupported.

Verdict::PendingApproval => {
    // The `Guard` trait does not carry the HITL approval flow; that runs via
    // `ApprovalGuard::evaluate`. A `Guard` returning `PendingApproval` is an
    // unsupported state, so fail closed.
    return Err(GuardRunError::new(
        KernelError::GuardDenied(format!(
            "guard \"{}\" returned an unsupported approval verdict",
            guard.name()
        )),
        evidence,
    ));
}

A grant can require a person’s approval. The kernel then needs both the capability and a signed decision bound to the exact request from an approver in the trusted set, and denies when that set is empty. Threshold approvals extend the two-key rule to several keys: a consequential call returns to admission only after a threshold of distinct eligible keys, such as two of three, have signed approvals of the same proposal. The policy can also refuse a vote from the key that submitted the request.

Authority given away has to be recoverable

Capabilities make sharing easy: a holder passes one on, and the recipient can pass it again. David Redell’s 1974 thesis at Berkeley set out the conflict between distributing access privileges freely and revoking them later, and proposed a design that supports revocation. Once a capability has been copied, taking it back means finding every copy, or arranging in advance that every copy depends on something the grantor still controls.

A Chio token expires or is revoked. Its validity period is fixed when it is signed, and a delegated child cannot outlive its parent. Revocation ends authority sooner. It is state the kernel keeps apart from the token, checked for the presented token and for every link in its delegation chain. One revocation entry closes a whole subtree of delegated work, while grants outside that subtree stay valid.

pub(crate) fn check_revocation(&self, cap: &CapabilityToken) -> Result<(), KernelError> {
    if self.with_revocation_store(|store| Ok(store.is_revoked(&cap.id)?))? {
        return Err(KernelError::CapabilityRevoked(cap.id.clone()));
    }
    for link in &cap.delegation_chain {
        if self.with_revocation_store(|store| Ok(store.is_revoked(&link.capability_id)?))? {
            return Err(KernelError::DelegationChainRevoked(
                link.capability_id.clone(),
            ));
        }
    }
    Ok(())
}

Read more in Authority has a lifetime.

A request should carry its own authority

In 1988 Norm Hardy published an account of a compiler at Tymshare. The compiler could write into a system directory, where it kept usage statistics. A user named the billing file in that directory as the destination for debugging output, and the compiler, acting on its own permission, overwrote the billing records. Capabilities retells Hardy’s account in full.

The compiler acted for two parties with one set of authority. The user supplied a name; the compiler supplied the permission. Under capabilities the name and the authority arrive together, so the compiler would have written with the user’s authority, which did not cover the billing file. The paper’s subtitle states the conclusion: “or why capabilities might have been invented.”

An agent is a deputy by construction. It reads text from parties it does not answer to, and it calls tools with authority its operator granted. In Chio the authority for a call is the capability presented with it: the scope check reads that token, and the subject check requires the caller to be the subject it names. Text in a pull request can change what the agent asks for; it cannot change what the token covers.

One root commits to every record beneath it

In 1979 Ralph Merkle filed a patent for a digital signature method built on a tree of hashes, and he presented the construction at CRYPTO ’87. Hash each record, then hash adjacent pairs of hashes, and continue until one hash remains. That root commits to every record in the tree. To show that one record belongs, it is enough to give the hashes along its path to the root, a number that grows with the logarithm of the tree’s size.

Chio commits receipts this way. The kernel batches receipts into a Merkle tree, and each checkpoint signs the tree’s root. A ReceiptInclusionProof names the checkpoint, the receipt’s position, the root, and the audit path, so a verifier holding a trusted checkpoint can check one receipt without the rest of the batch.

pub fn verify(&self, leaf_bytes: &[u8], expected_root: &Hash) -> bool {
    match self.compute_root(leaf_bytes) {
        Ok(root) => &root == expected_root,
        Err(_) => false,
    }
}

Leaves and interior nodes are hashed with different prefixes, as RFC 6962 specifies, and an odd node carries upward unchanged instead of being duplicated. The inclusion walk has a registered refinement proof up to eight leaves, under the SHA-256 assumption.

Retained commitments make conflicting histories detectable

Certificate Transparency, published as RFC 6962 in June 2013 by Ben Laurie, Adam Langley, and Emilia Kasper, applied Merkle’s tree to certificate issuance so that anyone could audit what certificate authorities issued. A log appends certificates to a Merkle tree and signs its tree heads. A consistency proof shows that a later tree extends an earlier one, and parties that compare signed heads can detect a log that presents different histories to different readers. RFC 9162 revised the protocol in December 2021.

Chio’s checkpoints apply the pattern to receipts. Each checkpoint signs its batch root and the hash of the checkpoint body before it. A checkpoint can also carry a chain root over every checkpoint so far, and consistency between two chain roots can be proved with RFC 6962 hashing instead of assumed. Conflicting checkpoints for one sequence, one tree size, or one predecessor are classified as equivocation.

A producer that re-signs its later checkpoints can make its own chain consistent again. Detection needs a commitment held outside the producer, by a recipient, a witness, or an anchor, and each anchor backend verifies something different. Retain a commitment outside the producer compares them.

A signature needs one byte string per value

A signature covers bytes, and JSON allows many byte strings for one value: keys in any order, numbers written several ways, optional whitespace. RFC 8785, the JSON Canonicalization Scheme, published in June 2020 by Anders Rundgren, Bret Jordan, and Samuel Erdtman, fixes one form. It sorts object keys by their UTF-16 code units, writes numbers as ECMAScript does, and removes whitespace between tokens, because hashing and signing need data “expressed in an invariant format.”

Chio signs canonical JSON. Its encoder follows RFC 8785 and adds one refusal: an integer whose magnitude exceeds 2⁵³ − 1, the I-JSON safe bound, is rejected before signing, because not every consumer can represent it exactly.

const I_JSON_MAX_SAFE_INTEGER: u64 = (1 << 53) - 1;
// …
fn write_canonical_object(map: &Map<String, Value>, out: &mut String) -> Result<()> {
    let mut pairs: Vec<_> = map.iter().collect();
    // RFC 8785: sort object keys by UTF-16 code unit comparison.
    pairs.sort_by(|(a, _), (b, _)| cmp_utf16_code_units(a.as_str(), b.as_str()));
    // …
}
// … strict text entry: visit_u64
        if v > I_JSON_MAX_SAFE_INTEGER {
            return Err(de::Error::custom(format!(
                "integer {v} outside I-JSON safe range [-(2^53-1), 2^53-1]"
            )));
        }

Capability tokens, receipts, and checkpoints are signed over canonical JSON, and an approval binds to a hash of the canonical arguments. A verifier that parses a record and encodes it again recovers the signed bytes.

Agents plan from the text they read

The programs these ideas were written for ran code their authors wrote. An agent decides its next call from text: a ticket, a page, the output of the last tool. Anyone who writes that text can try to steer it, so the ideas that separate a request from its authority, and a decision from its record, carry more weight than they did for a compiler. Steered by that text, an agent can rewrite a refused command in another spelling. Beyond Blocklists follows five such rewrites and the boundary that stops each one.

The agent can also chain calls that are each permitted: read an internal file, then send what it learned to a public destination. In 1976 Dorothy Denning wrote: “Most access control mechanisms are designed to control immediate access to objects without taking into account information flow paths implied by a given, outstanding collection of access rights.”

Her lattice model binds each object to a security class and gives combined information the least upper bound of its inputs’ classes. A process’s class can be determined by the history of classes it has accessed. Chio’s information labels apply that model across calls: each read joins its label into retained state, and a send needs a destination whose clearance admits that state. Information flow across calls follows one refused send.

Chio’s claims hold where the kernel mediates

These ideas give agentic operating systems a basis for assigning responsibility and retaining evidence as agents and models change. Chio makes the authority behind each call explicit, checks it before the effect, and leaves a record that others can verify later. Stated exactly, it claims four properties:

1. Each governed call is admitted against the one capability presented with it, signed by a trusted issuer, naming the caller as its subject, and fitting inside every grant it was delegated from.
2. Every governed call passes the same core evaluation in the same order, and a check that denies or fails stops the call before dispatch.
3. Revoking a token refuses it and every token delegated from it.
4. Each decision is recorded in a receipt signed over canonical bytes, and a verifier holding a trusted checkpoint can check that a receipt was committed under it.

The deployment carries the rest of the reference monitor. Anderson’s first two conditions belong to it: a tool reachable by another route is not mediated, so the host has to make the kernel the only route by withholding other credentials and handles, and a kernel whose process or keys an attacker controls is not tamper proof. Revocation is only as current as the revocation state where a call is checked, and keeping that state fresh across machines is the deployment’s responsibility. Failing closed is a default an operator can override: Tower’s with_fail_open(true) forwards a request without enforcement when evaluation fails, and counts each forward in chio_fail_open_suspected_total.

Least privilege is a property of the grant, and Chio cannot tell whether a grant is the least a task needs: a grant that includes drop_tables admits it. A tool can still be a deputy inside its own code. One that holds broad credentials and acts on a path or name from its arguments uses its own authority for that name; grant constraints and input guards limit which arguments reach it, and the kernel does not see what the tool does with its credentials after dispatch. Revocation stops later admissions and does not undo an effect a call already produced.

The record establishes how work was authorized, and it does not establish that an agent’s choices were correct. Inclusion shows that a receipt was committed under a root; it does not show that the receipt’s claim about a tool’s effect is true, or that a batch holds every receipt the kernel signed. Canonical bytes make records comparable: two allowed calls with the same arguments still produce different receipts, because the signing input includes timestamps and a nonce, so byte equality identifies the same record and not the same decision (One value, one byte string). Revocation lookups, budget mutation, and tool dispatch sit outside the proved core; every proof has an edge.

Read the mechanisms