Why Capabilities

Access lists and capability lists store the same matrix

In 1971 Butler Lampson gave protection an abstract model that fit most mechanisms of the time. It has a set of objects, a set of domains, and an access matrix A. Rows are labeled by domains and columns by objects, and each entry holds the access attributes one domain has to one object, such as read or write. Later work, including the paper by Miller, Yee, and Shapiro used below, calls the rows subjects and the columns resources.

A matrix with a row for every subject and a column for every resource is mostly empty, and Lampson judged a single table of its entries usually impractical. He described two ways to cut it instead. Attach each subject’s row to the subject, as pairs of a resource and the rights on it: each pair is a capability, and the subject’s set of them is its capability list, or C-list. Or attach each resource’s column to the resource, as a list of who may do what: an access control list.

The subjects and files in this matrix come from Hardy’s account of the confused deputy.

pub struct EvaluateInput<'a> {
    /// Tool call request being evaluated.
    pub request: &'a PortableToolCallRequest,
    /// The capability token authorising this call.
    pub capability: &'a CapabilityToken,
    // …
}

Both layouts contain the same permissions. This has led to the belief that access lists and capabilities are equivalent. Miller, Yee, and Shapiro named the belief the Equivalence Myth. A static matrix does not say how a subject names the resource it wants, or how rights move from one subject to another, and the two designs differ in both.

Naming is the first difference. Under access lists, a subject names a resource through a shared namespace, such as file names, and the system then consults the resource’s list. The name and the permission arrive by separate routes. A capability points from the subject to the resource, so each capability can serve both to “designate which resource to access, and to provide the authority to perform that access.”

The compiler mixed two parties’ authority

Norm Hardy published the account in 1988, from his time at Tymshare, a commercial timesharing company. A compiler was installed in a directory called SYSX, and a user ran it with RUN (SYSX)FORT, optionally naming a file to receive debugging output. The compiler also recorded language usage statistics in (SYSX)STAT. To let it write that file, Tymshare gave the compiler a home files license, which allowed it to write files in its home directory, SYSX.

The billing information was stored in the same directory, in (SYSX)BILL. A user who learned that name supplied it as the file for debugging output. The compiler asked the operating system to open the file, the system saw the home files license and allowed the write, and the billing information was lost.

The compiler’s code had been correct when it was written. Hardy traced the fault to authority “stemming from two sources”: the user’s, handed over by running the compiler, and the license, granted for the statistics. “The compiler serves two masters,” he wrote, and it had no way to express which authority a given write was meant to use.

Access lists make the compiler’s authority ambient

Under access lists, a request for (SYSX)BILL carries only the file’s name. The check consults that file’s column against everything the compiler holds, the user’s row and its own, and the license supplies the right. Name (SYSX)STAT and the statistics are overwritten the same way; Hardy noted that file also needed protecting.

The first repair added a system call that let the compiler choose between its two authorities, which Hardy called switching hats. Some applications soon needed more than two. The rules for opening a file kept growing until, the last time Hardy wrote them down, they needed fourteen boolean operators. The trouble was structural: one mechanism told the compiler which file to write, and a separate one decided whether it could.

Miller, Yee, and Shapiro call this kind of authority ambient: authority “exercised, but not selected, by its user.” Their example is Unix file permissions. A caller of open() chooses no credential to present; the request succeeds or fails. Their Property D, No Ambient Authority, requires a subject to select the authority it exercises. An agent with its operator’s API keys in its environment holds ambient authority of the same kind. The text it reads is in the position of the user who supplied (SYSX)BILL: it needs only to name a resource, and the agent’s own authority does the rest.

A capability names and authorizes at once

Capabilities are older than the deputy. In 1966 Jack Dennis and Earl Van Horn described a computation as proceeding within a sphere of protection specified by a list of capabilities, a C-list. Each capability locates an object and indicates the actions the computation may perform on it. A process could create an inferior sphere and grant it some of its own capabilities, and a segment capability could be “passed down with restricted access authority.”

Hardy’s capability solution used that shape. The compiler would hold a capability to the statistics file and use it when writing statistics. For debugging output it would use a capability supplied by the user. “The capability both identifies the file and authorizes the compiler to write there.” No file name has to be resolved, and nothing has to decide which of the compiler’s authorities applies. Under capability lists, a request for (SYSX)BILL must carry a capability from the user’s row. The user holds none for the billing file, so it cannot supply one. The compiler’s license is still in the matrix, and no request from the user can reach it.

Miller, Yee, and Shapiro call this Property A, No Designation Without Authority. No access list system can have it, because an access list system names resources through a namespace kept apart from authority. A system with Property A also has Property D: a request that must carry its authority has selected that authority. The paper also states the limit. Removing ambient authority helps make it possible to avoid confused deputies; it does not guarantee that a deputy never errs.

A Chio grant is a signed capability

Chio grants authority to agents as capability tokens. Each token names the issuer that granted it, the subject that may exercise it, a scope of permitted calls, and a validity period, and the issuer signs all of it. A tool grant in the scope names a tool on a server, the operations allowed, and constraints on its parameters. Read against Lampson’s model, a grant is a row entry, and the tokens an agent holds make up its capability list.

A call presents one token with the request. The kernel’s evaluation input contains both the request and the capability token authorizing it. The kernel checks that this token covers this request for this caller and consults nothing else the agent holds. A token’s identifier alone carries none of its authority; the complete signed token arrives with the call.

In the Quickstart, you grant the fixer agent part of a fork of your project.

const project = await Computer.open("quickstart");
const fixer = await project.agent("fixer");
const fork = await project.fork();
const authority = fork.grant({
  to: fixer,
  resources: { "/workspace": ["read", "write"], "/models/default": ["invoke"] },
  budget: USD(2),
  expiresIn: "20m",
});
console.log(authority.describe());

grant      cap-01a8…31f2, signed by your kernel
to         fixer, did:chio:z6MkrT2…8wd
on         quickstart, fork 51c07ae
allows     /workspace         read, write
           /models/default    invoke
budget     USD 2.00, charged at your door
expires    in 20 minutes

project = Computer.open("quickstart")
fixer = project.agent("fixer")
fork = project.fork()
authority = fork.grant(
    to=fixer,
    resources={"/workspace": ["read", "write"], "/models/default": ["invoke"]},
    budget=USD(2),
    expires_in="20m",
)
print(authority.describe())

grant      cap-01a8…31f2, signed by your kernel
to         fixer, did:chio:z6MkrT2…8wd
on         quickstart, fork 51c07ae
allows     /workspace         read, write
           /models/default    invoke
budget     USD 2.00, charged at your door
expires    in 20 minutes

let project = Computer::open("quickstart").await?;
let fixer = project.agent("fixer").await?;
let fork = project.fork().await?;
let authority = fork.grant(
    Grant::to(&fixer)
        .resource("/workspace", ["read", "write"])
        .resource("/models/default", ["invoke"])
        .budget(USD(2))
        .expires_in("20m"),
)?;
println!("{}", authority.describe());

grant      cap-01a8…31f2, signed by your kernel
to         fixer, did:chio:z6MkrT2…8wd
on         quickstart, fork 51c07ae
allows     /workspace         read, write
           /models/default    invoke
budget     USD 2.00, charged at your door
expires    in 20 minutes

The output reads as one row of the matrix. Your kernel is the issuer that signed it, fixer is the subject, allows lists the scope, and expires ends the validity period. When the fixer later tried to read /secrets/.env, its request carried this token, and the kernel refused the read because the scope does not cover that path.

A signed token is closer to a certificate than to Lampson’s protected pair, and Miller, Yee, and Shapiro consider that case too. A certificate names its resource in cleartext, so a name can be separated from the authority. They give two conditions under which deputies that cannot be confused remain feasible: certificates arrive in the context of a request, and subjects keep local identifiers for the certificates they hold. A Chio call meets the first by construction, since the token travels with the request it authorizes.

Lampson’s capabilities could not be forged because only the supervisor could create them. A Chio token is data that agents hold and present, so its issuer’s signature takes that role, and the kernel accepts only issuers it trusts. A signature prevents forgery but not copying. The token’s subject binds it to one caller: the kernel admits the token only for the caller it names, and a grant can also require a fresh proof of possession signed with that caller’s key.

Delegation narrows authority; revocation follows it

Delegation lets an application assign work to specialists with only the authority each assignment needs. Delegation follows Dennis and Van Horn’s grant with restricted access. When a grant permits delegation, its holder can pass part of that authority to another agent, and the kernel admits the child only if each of its grants is covered by a grant of the parent. Each step is recorded as a signed link in the child’s delegation chain, naming the delegator, the delegatee, and how the scope was narrowed.

The Irrevocability Myth holds that a capability, once handed out, cannot be taken back. The paper answers it with a forwarder the grantor can later disable, a method it traces to Redell in 1974. Chio keeps revocation as kernel state. Each admission checks the presented token and every link of its delegation chain against the revocation records, so once a parent is revoked, every token delegated from it is refused. Expiry needs no revocation: a token’s validity period is fixed when it is signed, and a delegated child cannot outlive its parent.

In the figure, grant p delegates to c, which passes part of its authority to d; s is a second child of p. Revoking c sets the hour from which c and d are refused, while p and s keep their windows. Each child’s window sits inside its parent’s, so none outlives the grant it came from.

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(())
}

In Chio, each of these ideas has a concrete counterpart.

A capability list per subjectDennis and Van Horn, 1966; Lampson, 1971

The tokens an agent holds; each grant names a tool, its operations, and constraints on its parameters.

Capabilities cannot be forgedLampson, 1971

The issuer’s signature over the token, checked against the kernel’s trusted issuer keys.

Designation travels with authorityHardy, 1988; Property A

The request and the token it exercises are evaluated together.

Authority is selected by its userProperty D

Each call presents one token; the kernel checks that token alone.

Delegation with restricted accessDennis and Van Horn, 1966

Each child grant is covered by a parent grant, and each step is a signed link.

Access can be revokedRedell, 1974

Revocation records in the kernel, checked for the token and its whole chain.

Read more in Delegation and attenuation, which gives the full rules for narrowing and chain validation.

A grant still needs a boundary

A capability decides which authority a request exercises. It authorizes a call; it does not make the call correct, the tool’s answer true, or the task finished. Within that authority, names still designate. A grant that permits writes under repository/ admits a write to any file there, and text the agent reads can still steer it toward one of them. The kernel refuses what a grant excludes; what a grant includes is a design decision, and the principle of least privilege applies to every grant.

Three mechanisms narrow what that steering can reach. With task-scoped authority, the application mints a grant per subtask, sized to its paths, call count, and lifetime, so injected text reaches only what the current task holds. With information flow across calls, the kernel joins the label of each read into retained state and refuses a send to a destination whose clearance does not admit that state, however many permitted calls come between. Guards inspect the contents of a request, such as a path, a destination, or a command, and can refuse a call the token covers. They narrow the calls a grant permits and cannot widen the token.

Kernel admission protects a resource only when the agent has no other way to reach it. The host has to prevent access through other credentials or handles, such as an API key left in the agent’s environment. Authority the kernel never sees stays ambient.

Continue with the mechanism