Relationship Graphs and How ReBAC Checks Resolve Access

Roles answer “what is this user’s job”. Attributes answer “what is true about this request”. Neither answers the question that most collaborative software actually asks: is this user related to this document in a way that grants access, through a chain of intermediate objects? Relationship-based access control treats authorization as a graph problem, and the design constraints that follow are the constraints of storing, indexing, and traversing a graph under latency budgets.

Tuples as the unit of policy

A relationship tuple is a triple: an object, a relation, and a subject. The subject may itself be an object, which is what makes chains possible. A document’s viewer relation may include a group object; that group’s member relation may include a user. The user is then a viewer of the document by one hop of indirection.

The tuple set is the entire policy. There are no rules in a separate language that reference tuples; the schema defines which relations exist, what types they accept, and how they compose, while the tuples are the data. This separation matters operationally because tuples are written by application code as objects are created and shared, so authorization state changes as a side effect of normal product operations rather than as an administrative act.

A schema declares relations and their allowed subject types. A document type might declare that viewer accepts users directly, accepts groups as members, and accepts the parent folder’s viewer relation. The last form is the rewrite rule that creates inheritance: being a viewer of the folder implies being a viewer of everything inside it, expressed as a relation rather than as a policy statement.

Traversal, and the shape of the search

Answering “can user U view document D” means searching for a path from D to U through the relation graph, following only the edges the schema permits. The search is bounded by the schema’s rewrite rules, which act as a grammar over paths rather than an arbitrary graph walk.

The naive implementation expands breadth-first from the object, fetching tuples for each relation at each level. With branching factor b and depth d, the frontier grows as b^d, so a document inside a deeply nested folder tree inside a large group produces a search whose cost is dominated by the group’s membership count. That count is the number that decides whether the query is fast: a group with a hundred thousand members makes a membership check a scan unless the storage layer indexes by subject as well as by object.

Real systems invert the direction for exactly this reason. Instead of asking “who is in this group”, the check asks “which groups contain this user”, which is a lookup by subject. The tuple store therefore needs indexes on both orientations, and the storage cost is roughly double the tuple count. The published Zanzibar design keeps tuples in a sparse, sharded store with indexes keyed by object-and-relation, by subject, and by a subject-relation pair, precisely so that traversal can proceed in whichever direction the query shape requires.

Depth bounds are the other lever. An unbounded traversal over a user-editable graph is an availability hazard, because a user who can create objects and share them can create a chain of arbitrary length. Implementations impose a maximum depth, and a check that exceeds it fails closed. The bound is a policy constant, and it must be at least as deep as the deepest legitimate structure the product creates.

type folder
  relations
    define parent: folder
    define viewer: user | group#member | viewer from parent

type document
  relations
    define parent: folder
    define viewer: user | group#member | viewer from parent

The viewer from parent clause is the inheritance edge. Reading it as a rewrite: to check whether someone is a viewer of this document, also check whether they are a viewer of its parent, recursively, until the depth bound or a root with no parent.

Consistency, and why the check cannot always be linearizable

Zanzibar’s central engineering claim is that authorization checks must be fast and available, and that new-enemy problems, where a permission change takes time to propagate, are acceptable if bounded. The system therefore serves checks from a snapshot of tuples that may lag recent writes by a bounded interval, with a mechanism that lets a caller request a check against the newest state for cases where staleness is unacceptable, at the cost of latency.

This is a deliberate trade, and its direction is worth stating: freshness costs latency, and the latency is on the path of the operation being authorized. A system that requires a linearizable check for every read pays a strongly consistent lookup per request; a system that tolerates bounded staleness serves most checks from cached or replicated state.

The failure mode when the trade is made silently is a revocation that does not take effect. A user removed from a group may retain access for the propagation window. If the product’s semantics require immediate revocation, the removal must be paired with something else, such as a version check in the token or a cache invalidation, and that something else is a second authorization mechanism with its own failure modes.

Caching compounds the problem because the check result is cached per subject-object pair, so the effective staleness is the propagation delay plus the cache lifetime. Both are configuration, and both belong in the documented revocation bound rather than being discovered during an incident.

Cycles, aliasing, and the problems the schema cannot prevent

The schema is a grammar, so the set of permitted paths is finite in form but not in length. A cycle arises when the data creates one: folder A’s parent is B, B’s parent is A. Implementations must either reject such tuples at write time or detect the cycle during traversal by tracking visited objects. Tracking visited objects costs memory proportional to the path length and is the usual answer, since rejecting cycles at write time requires a check that is itself a traversal.

Aliasing is subtler. If a group can be a member of another group, and a document grants access to a group’s members, then adding a user to an inner group grants access to the document. The tuple that changed is nowhere near the document, and no audit of the document’s tuples will reveal it. Auditing a relationship system means asking reachability questions in the reverse direction: for this object, which subjects can reach it. That query is a traversal of the whole reverse graph and is generally more expensive than the forward check, which is why the reverse indexes exist and why they are maintained synchronously with writes.

There is also the question of what a relation means when a subject type is admitted that the schema author did not consider. If viewer accepts any object of type group, and a group’s member relation accepts another group, then the nesting depth is unbounded and every check depends on the depth bound rather than on the schema. Schema review is therefore a security review, and the interesting question about any schema is which relations admit object subjects and whether the admission is transitive.

Where this model is the right one

The model fits products whose sharing is inherently relational: file trees, project workspaces, issue trackers, and anything where the natural operation is “give this person access to this container”. It handles delegation and nesting without role explosion, because a new folder does not require a new role, only a parent edge.

It fits poorly where access depends on properties rather than relationships. “Anyone in the EU can view this record during business hours” is an attribute condition, and expressing it as tuples means materializing a group per region and per time window, which defeats the model’s economy. The practical architecture combines the two, with the graph resolving the relationship portion and a policy layer evaluating the attribute portion, as described in the attribute-based evaluation article.

The last constraint is write amplification. Every object creation writes tuples for its relations, and every share writes or deletes one. The tuple store is on the write path of the product’s core operations, so its availability is the product’s availability. Systems that treat authorization data as a derived store rebuilt from the product database accept a recovery window in which the graph is incomplete, and an incomplete graph denies access rather than granting it, which is the correct direction for the error to point.