Relationship-Based Access Control (ReBAC): authorization as a graph

“People with access”

Sara opens the share dialog on roadmap.md and clicks “People with access.” The panel doesn’t show a flat list of names. It says that two people were shared the document directly, that the twelve members of the Engineering group can edit it because Engineering edits the /research folder it lives in, and that everyone in Product can view it because Product can view the whole workspace above that. Then she drags the document into a different folder, and the panel changes immediately: new people, new reasons, nothing copied. Nobody edited a permission on the document itself.

Every model so far answered authorization with a property of the subject or the resource. RBAC asked what role you hold. ABAC asked what attributes you and the resource carry. PBAC asked what the policy says about those attributes. But a large share of the access decisions real software makes aren’t about roles or attributes at all; they’re about relationships. You may edit this document because you belong to the team that owns the folder it’s in. You may see this photo because the person who posted it is your friend. You may approve this expense because you’re the submitter’s manager. None of those sentences names a role or tests an attribute. Each traces a connection from the subject, through other entities, to the resource.

Relationship-based access control (ReBAC) takes that observation and makes it the whole model. Access is granted when the subject is connected to the resource through an allowed chain of relationships. Represent every relationship as an edge in a graph, Sara is a member of Engineering, Engineering is an editor of /research, /research is the parent of roadmap.md, and an authorization question becomes a question of reachability: is there an allowed path from this subject to this resource? If so, permit; if not, deny. That’s the whole conceptual core, and its elegance is why it now underpins authorization at some of the largest software companies in the world. It’s also exactly what Sara’s share dialog is showing her.

Google’s authorization problem

The idea predates its fame. Academic work on relationship-based access control goes back to the late 2000s, framed around social networks, where “friend of a friend” is literally a path in a graph. The model became an industry force in 2019, when Google published a paper describing Zanzibar, its internal global authorization system. Google had a specific problem: dozens of products, Drive, Docs, Calendar, YouTube, Photos, Cloud, each needed to answer “can this user do this to this object?”, the objects numbered in the trillions, the checks ran to millions per second, and a wrong answer meant either a broken feature or a privacy breach in the headlines. Building a separate authorization system per product was how they’d started, and it didn’t scale, organizationally or technically.

Zanzibar’s insight was to make authorization one uniform, relationship-based service that every product could share. Model every permission as a relationship tuple, store them in one planet-scale database, and expose a small API, mainly a Check call asking whether a relationship holds, that any product can call. The paper showed that ReBAC works at extreme scale and published the engineering answers to the hard problems that scale creates, consistency and performance, which we’ll come to. Within a few years it had inspired a whole generation of open-source and commercial engines bringing the same model to everyone else.

The basic unit: the relationship tuple

Everything in ReBAC is built from one tiny, uniform fact, the relationship tuple. Its shape is deliberately minimal:

⟨object⟩#⟨relation⟩@⟨subject⟩

Read it right to left as a sentence: this subject has this relation to this object. A few tuples describe Sara’s situation:

document:roadmap#editor@user:sara        // Sara is an editor of the roadmap document
folder:research#parent@document:roadmap  // roadmap lives in the research folder
folder:research#editor@user:sara         // Sara is an editor of the research folder
group:eng#member@user:daniel             // Daniel is a member of the engineering group

Each tuple is one independent edge in the authorization graph. There’s no heavy object model and no permission table per application, just a uniform stream of small facts. That uniformity is the point: because every permission in every product is the same kind of tuple, one engine can store and evaluate authorization for all of them. Granting access is writing a tuple; revoking it is deleting one. The full set of tuples is the graph the engine walks to answer any question.

Keep two things apart. Tuples are the runtime data, who’s related to what, changing constantly as people share, join teams, and move files. The authorization model, which Zanzibar called a namespace configuration and OpenFGA calls an authorization model, is the schema. It declares the object types, the relations each type has, and the rewrite rules that compute relations from other relations. The data says Sara is an editor of this document. The model says anyone who’s an editor is also a viewer, and anyone who can view the parent folder can view the document. ReBAC’s real power lives in that second part.

Usersets and rewrites: where the power lives

If tuples could only ever say object#relation@user:someone, ReBAC would be little more than a distributed access control list, expressive but flat. The leap comes from two features that let relations be computed rather than only stored.

The first is the userset: a tuple’s subject can itself be a set of users defined by another relation, not just a single user. Writing folder:research#editor@group:eng#member says the editors of the research folder include every member of the engineering group. Adding Daniel to group:eng#member then quietly makes him an editor of the folder, with no change to the folder’s tuples. It’s the group indirection RBAC gave us, generalized: any relation can point at another relation’s set of subjects, so groups, teams, and nested memberships all come from the same primitive.

The second is the rewrite rule, declared in the model rather than the data, which defines a relation in terms of other relations. Two patterns dominate. A union, “a viewer is anyone who’s directly a viewer or is an editor,” encodes permission hierarchies, since editors can obviously view, without duplicating tuples. Tuple-to-userset, the crown jewel, “the viewers of a document include the viewers of its parent folder,” encodes inheritance: define viewing once on folders and every document inside inherits it through the parent edge. That one mechanism is how ReBAC expresses the folder-tree inheritance every file-sharing product needs and that RBAC and ABAC both handle clumsily.

Together, a compact model and a handful of tuples express rules that elsewhere would need sprawling role tables or intricate ABAC policies. Sara can view roadmap.md because she’s an editor of the folder, and editors are viewers, and the document inherits its viewers from that folder. No tuple ever said “Sara can view roadmap.md”; the engine derived it by following edges. That derivation is the essence of ReBAC.

A check is a graph traversal

Because permissions are edges and derived permissions are rewrite rules, answering the core question, Check(document:roadmap, viewer, user:sara), “may Sara view the roadmap?”, is a graph search. The engine starts at the requested pair of object and relation and expands it according to the model until it either finds the subject or runs out of reachable graph:

Check(document:roadmap, viewer, sara)?
  viewer(roadmap) = direct viewers of roadmap
                  ∪ editors of roadmap            (union rewrite: editor implies viewer)
                  ∪ viewers of roadmap's parent   (tuple-to-userset: inherit from folder)
  → follow parent edge: folder:research
  → viewer(research) ⊇ editor(research) ∋ sara    (Sara is an editor of the folder)
  → PERMIT

flowchart TD
  accTitle: Resolving a ReBAC permission check as a recursive graph traversal
  accDescr: The evaluation starts at a node asking whether Sara is a viewer of the roadmap document. It expands into three branches according to the authorization model. The first branch checks direct viewers of the document and finds none. The second branch is a union rewrite that folds in editors of the document, also none directly. The third branch is a tuple-to-userset rewrite that follows the document's parent edge to the research folder and asks whether Sara is a viewer of that folder. That expands to whether Sara is an editor of the folder, which a stored tuple confirms. Because a path to Sara is found, the overall result is permit. If none of the branches had reached Sara, the result would be deny.
  Q["Check: viewer of document:roadmap = user:sara?"] --> D["Direct viewers of roadmap"]
  Q --> E["Union: editors of roadmap<br/>(editor implies viewer)"]
  Q --> P["Tuple-to-userset:<br/>follow parent edge"]
  D --> DN["none"]
  E --> EN["none directly"]
  P --> F["viewer of folder:research?"]
  F --> FE["editor of folder:research?"]
  FE --> T["tuple:<br/>folder:research<br/>#editor @user:sara ✓"]
  T --> Y["PERMIT, path to Sara found"]
  DN -.-> Y
  EN -.-> Y

This traversal is what lets ReBAC answer a question the other models find genuinely hard: who has access to this specific object? In RBAC you’d enumerate every role granting the permission and every user in those roles; in ABAC you’d evaluate the policy against every user, the reverse-query problem. In ReBAC, “who can view roadmap.md?” is the traversal run backwards: expand the object’s viewer relation and collect every subject the graph reaches. That reverse lookup, which Zanzibar calls Expand and others call a “list objects” or “list users” query, is a first-class operation, which is why ReBAC engines are the natural backend for share dialogs and “people with access” panels like Sara’s.

How ReBAC compares with the earlier models

The models complement each other, and each answers a different question best.

ReBAC’s natural fit, collaboration, hierarchy, and sharing, is exactly where RBAC and ABAC are weakest, because those scenarios are about individual objects related to individual subjects, not broad roles or intrinsic attributes. And its weak spot, conditions on time, risk, or amount, is ABAC’s home ground. That symmetry is why the frontier of authorization isn’t “pick one” but “combine the graph with conditions.”

The two hard problems Zanzibar had to solve

The ReBAC idea is simple. Making it work at Google’s scale raised two deep problems any serious relationship engine has to face, and understanding them separates a toy from a production system.

Consistency and the “new enemy” problem

Authorization data changes constantly, and it’s often replicated across regions for speed. That opens a dangerous window: if a check can read stale replicated data, it might grant access that was just revoked, or honor an old grant together with a new object. Zanzibar named the sharpest form of this the new enemy problem. Picture Sara removing Daniel, who has moved to another team, from a document, and then adding sensitive figures to it. If a later check for Daniel reads a replica where the removal hasn’t arrived yet, he sees content he was specifically cut off from before it even existed. Sara did things in the right order; the stale read reordered them and produced a real breach.

Zanzibar’s answer is the zookie, a small opaque snapshot token returned when data is written. When the application later runs a check, it can pass the zookie to say “evaluate this at least as fresh as that write,” and the engine guarantees the decision reflects a snapshot no older than the token. It’s ReBAC’s version of the tension between freshness and latency you’ve met with sessions, token revocation, attribute caching, and PBAC’s data loading, here answered with a token that lets the caller demand the freshness a particular decision needs.

The problem is subtle because nothing was misconfigured. The revocation happened before the sensitive edit, exactly as intended; the breach comes purely from a replica deciding on data older than a write that came first. Any distributed authorization system that replicates permission data has this hazard, and the fix is always some form of “decide at a snapshot no older than the write that matters.” When you evaluate a ReBAC engine, ask specifically how it handles consistency. An engine that always reads the freshest data is simple but slow, and one that reads any replica is fast but unsafe; the interesting engineering is in letting the caller choose per check.

Deep graphs, short latency budgets

The second problem is speed. One Check can in the worst case fan out across a deep, wide graph, groups within groups and folders within folders, yet it has to return in milliseconds, and the system has to sustain millions of checks per second worldwide. A naive recursive walk that re-traverses the same groups on every request can’t meet that budget. Zanzibar’s answers included aggressive caching of intermediate results, a specialized index nicknamed Leopard that precomputes flattened group memberships so a deeply nested “is X a member of Y?” becomes a fast lookup instead of a deep walk, and hedged requests to tame tail latency across replicas. You don’t need these internals to use ReBAC, but they explain why relationship engines are purpose-built databases rather than a table in your app’s Postgres: answering reachability over a huge, changing graph within a millisecond budget is genuinely hard, and it’s most of the engineering in a Zanzibar-style system.

The ecosystem Zanzibar spawned

Zanzibar itself is internal to Google, but the paper was detailed enough to seed a thriving open-source and commercial ecosystem. The shape is always the same, store tuples, declare a model with rewrite rules, expose a Check and Expand style API, but the projects differ in language, governance, and emphasis.

Two stand out. OpenFGA, born at Auth0 and donated to the Cloud Native Computing Foundation, has become something of a community standard, with an approachable modeling language and, importantly, conditions that let a relationship carry an attribute test, blending ReBAC with ABAC. SpiceDB, from AuthZed, is a close, performance-focused reimplementation of the Zanzibar design that exposes consistency controls so callers can trade freshness against latency per request.

Here’s Sara’s workspace as an OpenFGA-style model. It declares types, their relations, and the rewrites, the schema, separate from the tuple data:

model
  type user
 
  type group
    relations
      define member: [user, group#member]      // groups can nest
 
  type folder
    relations
      define editor: [user, group#member]
      define viewer: [user, group#member] or editor   // editor implies viewer
 
  type document
    relations
      define parent: [folder]
      define editor: [user, group#member] or editor from parent
      define viewer: [user, group#member] or editor or viewer from parent

editor from parent and viewer from parent are the tuple-to-userset inheritance, and or editor is the union. Ten lines of model plus a stream of tuples express folder-tree inheritance, nested groups, and permission hierarchies, a rule set that would sprawl across dozens of roles or a thick ABAC policy in the other models.

Where ReBAC shines, and where it strains

ReBAC’s sweet spot is clear once you have the model in mind. Collaborative software, documents, folders, repositories, boards, wikis, is built out of relationships: owners, editors, viewers, sharing, and containment. Hierarchies, organizations, folder trees, resource groups, multi-tenant customer structures, are exactly the parent and child edges tuple-to-userset was designed to traverse, so a permission set once at the top cascades down for free. Social and content platforms, where visibility follows friendship, following, or ownership, are relationship graphs by nature. And any product that has to show who has access to something, or what a user can reach, gets those queries as native traversals instead of expensive scans. If your authorization sentences naturally contain the word “because” followed by a chain of ownership or membership, ReBAC is very likely the right model.

It strains when access depends on things that aren’t relationships: only during working hours, only if the device is managed, only for transactions under 10,000, only if the risk score is low. Those are environmental and computed conditions, ABAC’s specialty, and a pure relationship graph has no natural place for them. The old answer was to put an ABAC check in front of the ReBAC check in application code, which works but splits authorization logic in two. The modern answer is conditional relationships: engines like OpenFGA let a tuple carry a condition, a small attribute expression that must hold for the edge to count, so “editor while the current time is within working hours” becomes one conditioned edge. That convergence, a relationship graph with attribute conditions on its edges, is where fine-grained authorization is heading.

ReBAC also moves the whole risk surface onto the tuple data. A missing tuple is a broken feature, someone can’t reach what they should. A stray tuple is a privacy breach, someone reaches what they shouldn’t. Because permissions are derived by traversal, one wrong high-level edge, a user wrongly added to a powerful group, a document filed in the wrong folder, can quietly grant access to thousands of objects downstream. The graph’s expressive power is exactly what makes its data errors travel so far. Treat tuple writes as security-sensitive events: log them, review the model’s most powerful rewrite rules, and test that “who can reach this?” returns what you expect. The reverse query is your best audit tool.

Sara’s roadmap as relationships

We’ve solved Sara’s access to /research/roadmap.md under every model in this part of the domain; ReBAC solves it as a graph. The tuples state only plain facts: Sara is a member of group:eng, group:eng#member is an editor of folder:research, and document:roadmap has folder:research as its parent. No tuple mentions Sara and the roadmap together. When the app asks Check(document:roadmap, viewer, user:sara), the engine derives the answer: the document’s viewers include its parent’s viewers, the parent is folder:research, the folder’s viewers include its editors, its editors include group:eng#member, and Sara is a member. Permit. Every hop was a stored relationship; the permission was computed.

Watch how naturally change spreads, ReBAC’s quiet superpower and the reason Sara’s share dialog updated the moment she moved the file. Move the document to another folder by writing one new parent tuple, and its entire set of permissions becomes that folder’s, because access was always inherited, never copied. Add Daniel to group:eng with one tuple and he immediately becomes an editor of the folder and every document in it, with nothing touched on those objects. Revoke by deleting the membership tuple and the derived access disappears on the next check. In RBAC, refiling a document means working out which roles should grant it now; in ABAC, you’d re-evaluate a policy per user. In ReBAC the graph is the permission model, so editing the graph is editing permissions, directly and locally, with the full inherited structure intact.

There’s a limit even here. Suppose the support rule returns: an agent may edit an account only during working hours and only if a ticket is open. “Assigned to the agent” and “belongs to the account” are relationships ReBAC expresses beautifully, but “during working hours” and “a ticket is open” are conditions, not connections. A pure graph can’t hold them; you need conditioned edges or a companion ABAC check. That gap between connection and condition is why the models rarely appear alone in production, and why the next model set out to unify them in a single, more general abstraction.

Recap

Relationship-based access control derives permissions from a graph of connections between entities. Access is granted when the subject is connected to the resource through an allowed chain of relationships, so the authorization question becomes whether an allowed path exists, a graph traversal. The tuple is the basic unit: every permission is a uniform object#relation@subject fact, usersets let a tuple point at a set of subjects, and rewrite rules, union and tuple-to-userset, compute relations, giving groups, permission hierarchies, and inheritance from one tiny primitive. Zanzibar made it real at scale and had to solve consistency, the new enemy problem answered with snapshot zookies, and performance, caching plus a precomputed membership index to walk deep graphs in milliseconds. A rich ecosystem followed, OpenFGA, SpiceDB, Permify, and Ory Keto, all storing tuples, declaring a model, and exposing Check and Expand. And ReBAC shines for collaboration, hierarchy, and sharing, answers “who can access this?” natively, and strains only on conditions such as time or risk, which is why modern engines add attribute conditions to edges, bringing ReBAC and ABAC together.

Three questions to test yourself

1. Express “you may edit this document because you’re a member of the team that owns its folder” as a set of ReBAC tuples plus the rewrite rules needed to derive the edit permission. Identify which rule does the inheritance and which does the group indirection.
2. Explain the new enemy problem in your own words, including why the two writes involved were in the right order, and describe how a snapshot token prevents the breach without forcing every check to read the freshest possible data.
3. A team wants to enforce “an editor may edit an account only during working hours.” Explain why a pure relationship graph can’t express the time condition, and describe two ways to handle it, a companion ABAC check or a conditioned edge. Which keeps authorization logic in one place?

Hands-on exercises

1. Model a folder tree in OpenFGA. In the OpenFGA playground, declare user, folder, and document types with viewer and editor relations, parent inheritance (viewer from parent), and editor implying viewer. Add tuples that make one user an editor of a top folder, then run a Check showing they can view a document three levels down. Delete one tuple and watch the access disappear.
2. Write the reverse query. For the same model, use the list-objects operation to answer “which documents can this user view?” and “who can view this document?” Notice how these queries, expensive scans in RBAC or ABAC, are native traversals here.
3. Find the seam. Take an authorization rule from a system you know and split it into its relationship part (“because they own, belong to, or manage…”) and its condition part (“but only if the time, amount, or risk…”). Decide which belongs in a relationship graph and which needs an attribute condition, and sketch how a conditioned edge would let one ReBAC engine carry both.