Authority graph
The definition of the authority graph, the grants and revocations of a space evaluated in two passes so that every peer computes the same live access regardless of arrival order, with a worked example of delegation, revocation and recovery.

Part of Stem. This page defines the authority graph and the exact evaluation that turns grants and revocations into live access levels.

The authority graph of a space is the directed graph whose nodes are principals, groups and resource nodes, and whose edges are grants, each carrying an access level over a subject; a two-pass evaluation over the grants and revocations a peer holds yields, for every principal and subject, the live access level.

The graph is a capability system in the certificate style: authority flows along signed delegations, a holder may delegate at its own level or lower, and access along a path is capped at the lowest level on the path. It follows the Keyline design the team reviewed, with permanent admins and admin rotation by cutting supply. It is late-bound: an edge works while its issuer has enough authority, stops working when that authority disappears, and recovers if another path restores it. Peers holding the same grants and revocations compute the same result in any order.

Edges

A Grant is an edge from its signer to its audience, labelled with a subject and an access level. The owner of a space is the source of all authority in it: the owner holds admin over the space root by definition, and every chain of edges that confers access in the space begins with a grant signed by the owner or by someone the owner's chain reaches. A grant on a group at read makes the audience members of the group; at admin it lets them add members. An audience of kind group turns a group into a node of the graph that fans out to its members; an audience of kind readers fans out to the readers of a resource node.

A Revocation marks one grant as cut. It is valid if its signer is the grant's issuer, the grant's delegate (a key audience), or holds admin over the grant's subject in the positive pass described below.

Evaluation

Positive pass. Ignore every revocation. Starting from the owner with admin over the space root, walk grants outward. A grant is reachable if its signer has, through already-reachable grants, an access level over the grant's subject at least equal to the grant's level, where a subject covers another when it is the same node or group or an ancestor node with exact false. Record, for every principal, the set of subjects over which it reaches admin: its admin reach. The owner's admin reach is the whole space, forever.

Live pass. Now apply revocations. A revocation is valid if its signer is the grant's issuer or delegate, or has the grant's subject in its admin reach from the positive pass. Remove every validly revoked grant. Also remove every grant whose expires is before the evaluating peer's current time. Then repeat the reachability walk over the remaining grants. The result is the live graph: for every principal and subject, the highest access level reachable, or none.

Admins are special in one way: admin reach is computed in the positive pass, so a revocation signed by an admin stays valid even if that admin is later cut off. This is what "admins are forever" means, and it is also what makes revocations themselves immune to being revoked by the people they revoke. To remove an admin you cut the supply of authority to them and build new paths to the admins you want, which the team calls rotating the permanode; in Stem that is a Revocation of the admin's grant by the owner, plus new grants.

Readers follow from the live graph as in Readers. Write authority for a Node blob is the live level of its signer over the node (or over the parent, for a creating blob), at write or higher.

A worked example

Space A is owned by Alice. She creates a group "Workspace" and these grants:

    Alice → Workspace: admin over the space root. (Alice signs; she is owner.)

    Alice → Carol: read over the group Workspace. (Carol is a member.)

    Carol → Dave: write over node projects. Carol signs with proof naming grant 1.

    Dave → Bob: read over node projects/design, which sits under projects. Dave signs with proof naming grant 3.

Positive pass. Grant 1 is reachable: Alice is owner. Grant 2 is reachable: Alice is owner. Carol is a member of Workspace, so Carol holds admin over the root through grants 2 and 1. Grant 3 is reachable: Carol has admin ≥ write over projects. Grant 4 is reachable: Dave has write ≥ read over projects/design. Admin reach: Alice everywhere; Carol everywhere (through the group); Dave and Bob nowhere.

Live pass with no revocations: Bob reads projects/design; Dave writes under projects; Carol administers the space.

Revoking Carol. Alice signs a Revocation of grant 2. It is valid (Alice is its issuer). Grant 2 is removed. Carol no longer reaches anything. Grant 3 was signed by Carol, whose authority over projects is now none, so grant 3 is not reachable, and grant 4, signed by Dave whose authority came through grant 3, is not reachable either. Bob loses access although nobody revoked his grant. Peers that receive the revocation before grants 3 and 4, or after, compute the same result.

A second path. Alice signs grant 5: Alice → Dave, write over projects. Grant 3 stays dead, but Dave is reachable again through grant 5, so grant 4 is reachable again, and Bob reads projects/design once more. Nothing had to be re-signed by Dave or Bob. That is late binding.

Carol fights back. Before her revocation arrived at some peer, Carol signed a Revocation of grant 5. Is it valid? Carol's admin reach in the positive pass, which ignores revocations, still includes projects, so yes, it is valid. Alice answers by signing grant 6, identical to grant 5 but a new blob. Carol can revoke that too; the owner always wins eventually because Carol can no longer sign grants that are reachable, while every revocation Alice signs is valid forever. Open: whether admin reach should exclude principals whose membership was revoked by the owner specifically, to shorten this exchange. Stem keeps the Keyline rule and records the question.

Where it is used

    Authority: the full treatment with groups, delegation limits and expiry.

    Readers: the read side of the live graph.

    Access: the RPC that reports a live level and the chain behind it.

    Database structure: the materialised authority relation.

Today (HM24)

A Capability is signed only by the space owner, grants WRITER or AGENT, cannot be re-delegated except through one AGENT hop, never expires and cannot be revoked; the daemon's rule is two SQL lookups that never consult time. Read access is not expressible at all. The roadmap decided to discontinue path scopes, add groups and build revocation; the Private Document Hierarchy and Authorization design chose Keyline as the foundation. Stem's graph is that choice, with the owner's permanent admin as the root.

Do you like what you are reading? Subscribe to receive updates.

Unsubscribe anytime