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

The question the previous models kept dodging

Every model so far answered authorization with a property of the subject or the resource. RBAC asked “what role do you hold?” ABAC asked “what attributes do you and the resource carry?” PBAC asked “what does the policy say about those attributes?” But a huge fraction of the access decisions real software makes are not really about roles or attributes at all — they are about relationships. You may edit this document because you belong to the team that owns the folder it lives in. You may view this photo because the person who posted it is your friend. You may approve this expense because you are the submitter’s manager. Notice that none of those sentences names a role or tests an attribute; each one 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 reachability question: does a permitted path exist from this subject to this resource? If yes, permit; if no, deny. That is the entire conceptual core, and its elegance is why it now underpins the authorization systems of some of the largest software companies on earth.

This article is the last in the model-by-model tour. It closes a progression that has been quietly building: from owner-decides (DAC), to label-decides (MAC), to role-decides (RBAC), to attribute-decides (ABAC), to policy-decides (PBAC), and now to relationship-decides. Each model answered “what should access be based on?” with a different noun. ReBAC’s answer — the connections between things — turns out to be the one that fits collaborative, hierarchical, sharing-centric software the way none of the others quite could.

A short history: Google’s authorization problem

ReBAC as an 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 graph path. But the model became an industry force in 2019, when Google published a paper describing Zanzibar, its internal global authorization system. Google had a very 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 into the millions per second, and a wrong answer meant either a broken feature or a privacy breach making headlines. Building a separate authorization system per product was how they had started, and it did not scale organizationally or technically.

Zanzibar’s insight was to make authorization a single, uniform, relationship-based service that every product could share. Model all permissions as relationship tuples, store them in one planet-scale database, and expose a small API — chiefly a Check call (“does this relationship hold?”) — that any product could call. The paper did two things that reshaped the industry: it proved ReBAC works at extreme scale, and it published the engineering answers to the hard problems that scale creates — consistency and performance — which we will come to. Within a few years, Zanzibar had inspired a whole generation of open-source and commercial engines built to bring the same model to everyone else. When people say “Zanzibar-style authorization” today, ReBAC is what they mean.

The atomic unit: the relationship tuple

Everything in ReBAC is built from one tiny, uniform fact called a relationship tuple (or “relation 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 concrete tuples describe our running scenario:

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 a single, independent edge in the authorization graph. There is no schema-heavy object model here, no per-application permission table — just a uniform stream of these small facts. That uniformity is the point: because every permission in every product is expressed as 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 complete set of tuples, taken together, is the graph the engine walks to answer any question.

Usersets and rewrites: where the power lives

If tuples were only ever 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 a single user. Writing folder:research#editor@group:eng#member says “the editors of the research folder include every member of the engineering group.” Now adding Daniel to group:eng#member silently makes him an editor of the folder, with no change to the folder’s tuples. This is exactly the group indirection RBAC gave us, but generalized: any relation can point at any other relation’s set of subjects, so groups, teams, and nested memberships all fall out of the same primitive.

The second is the rewrite rule (or “userset rewrite”), declared in the model rather than the data. A rewrite defines a relation in terms of other relations. Two patterns dominate. Union / implication — “a viewer is anyone who is directly a viewer or is an editor” — encodes permission hierarchies (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 within inherits it through the parent edge. That single mechanism is how ReBAC expresses the folder-tree permission inheritance that every file-sharing product needs and that RBAC and ABAC both handle clumsily.

Put the two together and a compact model plus a handful of tuples expresses rules that would take sprawling role tables or intricate ABAC policies elsewhere: Sara can view roadmap.md because she is an editor of the folder (editor implies viewer), and roadmap.md inherits its viewers from that folder (tuple-to-userset). No tuple ever said “Sara can view roadmap.md” — the engine derived it by following edges. That derivation is the essence of ReBAC.

Answering 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 (object, relation) pair and expands it according to the model until it either finds the subject or exhausts the reachable graph. Conceptually:

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

The diagram below shows that resolution as the engine actually performs it — a recursive expansion of the target relation through union and inheritance edges until the subject is reached or the search is exhausted.

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: folder:research#editor@user:sara ✓"]
  T --> Y["PERMIT — path to Sara found"]
  DN -.-> Y
  EN -.-> Y

This traversal model is what makes ReBAC answer a question the other models find genuinely hard: “who has access to this specific object?” In RBAC you would have to enumerate every role that grants the permission and every user in those roles; in ABAC you would have to evaluate the policy against every user. In ReBAC, “who can view roadmap.md?” is just the traversal run in reverse — expand the object’s viewer relation and collect every subject the graph reaches. That reverse-lookup power (Zanzibar calls it Expand; others call it 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.

How ReBAC compares to the models before it

The models are complements, not competitors, and each answers a different question best. It helps to line them up:

The row that matters most for ReBAC is the last one. Its natural fit — collaboration, hierarchy, sharing — is precisely the case RBAC and ABAC handle worst, because those scenarios are about individual objects related to individual subjects, not about broad roles or intrinsic attributes. And its weak spot — conditions on time, risk, or amount — is exactly ABAC’s home turf. That symmetry is why the frontier of authorization is not “pick one” but “combine the graph with conditions,” a hybrid we return to below.

The two hard problems Zanzibar had to solve

The ReBAC idea is simple; making it work at Google’s scale surfaced two deep problems that any serious relationship engine must confront. Understanding them separates a toy from a production system.

Consistency and the “new enemy” problem

Authorization data changes constantly, and it is often replicated across regions for speed. That creates a dangerous window: if a permission check can read stale replicated data, it might grant access that was just revoked — or, worse, honor an old grant in combination with a new object. Zanzibar named the sharpest form of this the “new enemy” problem. Picture it: Sara removes her ex-colleague from a document, then adds sensitive content to it. If a later check for that colleague reads a replica where the removal has not yet landed, the “new enemy” sees content they were specifically cut off from before it existed. The two writes were correctly ordered by the application, but stale reads reordered them, producing a real breach.

Zanzibar’s answer is the “zookie” — a small, opaque snapshot token returned when data is written. When the application later performs a check, it can pass the zookie to say “evaluate this at least as fresh as that write.” The engine then guarantees the decision reflects a snapshot no older than the token, closing the window. This is the ReBAC-specific incarnation of the freshness-versus-latency tension you have now met in sessions, token revocation, ABAC attribute caching, and PBAC data loading — the recurring identity question “how current is the data I decide on?” — here answered with a token that lets the caller demand the freshness a given decision requires.

Performance: deep graphs, shallow latency budgets

The second problem is speed. A single Check can, in the worst case, fan out across a deep, wide graph — nested groups within groups, folders within folders — yet it must return in milliseconds, and the system must sustain millions of checks per second globally. A naïve recursive traversal that re-walks the same groups on every request cannot meet that budget. Zanzibar’s answers included aggressive caching of intermediate results, a specialized index (nicknamed “Leopard”) that precomputes flattened, transitively-closed group memberships so a deeply nested “is X a member of Y?” is a fast lookup rather than a deep walk, and request hedging to tame tail latency across replicas. You do not 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, churning graph within a millisecond budget is genuinely hard, and it is most of the engineering in a Zanzibar-style system.

The ecosystem Zanzibar spawned

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

Two are worth singling out. OpenFGA, born at Auth0 and donated to the Cloud Native Computing Foundation, has become something of a community standard, with an approachable modeling DSL and — importantly — conditions that let a relationship carry an attribute test, blending ReBAC with ABAC (more on that next). SpiceDB, from AuthZed, is a close, performance-focused reimplementation of the Zanzibar design, exposing consistency controls (its “zedtokens” are zookies by another name) so callers can trade freshness against latency per request. What all of them share is the essential ReBAC bargain: model your domain as relationships once, and every authorization question becomes a query against one graph.

What the model looks like in practice

To make it concrete, here is the running scenario as an OpenFGA-style authorization model. Notice it declares types, their relations, and the rewrites — this is the schema, distinct 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

The phrases editor from parent and viewer from parent are the tuple-to-userset inheritance; or editor is the union implication. Ten lines of model plus a stream of tuples now 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 unmistakable once you have the model in mind. Collaborative software — documents, folders, repositories, boards, wikis — is built from relationships: owners, editors, viewers, sharing, and containment. Hierarchies — organizations, folder trees, resource groups, multi-tenant customer structures — are exactly the parent/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 their very nature. And any product that must render “who has access to this?” or “what can this user reach?” gets those queries as first-class traversals rather than 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.

The strain shows up when access depends on things that are not relationships. “Only during business hours.” “Only if the device is managed.” “Only for transactions under 10,000.” “Only if the risk score is low.” These are environmental and computed conditions — ABAC’s core competency — and a pure relationship graph has no natural place to put them. The historical answer was to bolt an ABAC check in front of the ReBAC check in application code, which works but splits the authorization logic in two. The modern answer is conditional relationships: engines like OpenFGA now 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 business hours” becomes a single conditioned edge. That convergence — a relationship graph with attribute conditions on its edges — is where fine-grained authorization is heading, and it is the practical shape of the RBAC-plus-ABAC-plus-ReBAC hybrids you will design in the capstone article.

A worked example: Sara’s roadmap, re-solved as relationships

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

Now watch how naturally change propagates, which is ReBAC’s quiet superpower. Move the document to a different folder — write one new parent tuple — and its entire permission set changes instantly to that folder’s, because access was always inherited, never copied. Add Daniel to group:eng — 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 vanishes on the next check. Compare this to RBAC, where re-parenting a document means re-deriving which roles should grant it, or ABAC, where you would re-evaluate a policy per user. In ReBAC the graph is the permission model, so editing the graph is editing permissions — directly, locally, and with the full inherited structure preserved. That is the payoff the whole model was built to deliver.

There is a limit even here, and it is the seam to the rest of the module. Suppose the fintech rule from earlier returns: a support agent may edit an account only during business hours and only if a ticket is open. “Assigned to the agent” and “belongs to the account” are relationships ReBAC expresses beautifully — but “during business hours” and “ticket is open” are conditions, not connections. A pure graph cannot hold them; you need conditioned edges or a companion ABAC check. That gap between connection and condition is exactly why the authorization models rarely appear alone in production, and why the next model set out to unify them under a single, more general abstraction.

Recap

Relationship-Based Access Control derives permissions from a graph of connections between entities:

1. Relationships, not roles or attributes. Access is granted when the subject is connected to the resource through an allowed chain of relationships; the authorization question becomes “does a permitted path exist?” — a graph traversal.
2. The tuple is the atom. Every permission is a uniform object#relation@subject fact; a userset lets 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 a tiny primitive.
3. Zanzibar made it real at scale and had to solve two hard problems: consistency (the “new enemy” problem, answered with snapshot “zookies”) and performance (caching plus a transitive-closure index to walk deep graphs in milliseconds).
4. A rich ecosystem followed — OpenFGA, SpiceDB, Permify, Ory Keto — all storing tuples, declaring a model, and exposing Check/Expand.
5. It shines for collaboration, hierarchy, and sharing, answers “who can access this?” natively, and strains only on conditions like time or risk — which is why modern engines add attribute conditions to edges, converging ReBAC with ABAC.

Three questions to test yourself

1. Express the sentence “you may edit this document because you are a member of the team that owns its folder” as a set of ReBAC relationship tuples plus the rewrite rules needed to derive the edit permission. Identify which rule is doing inheritance and which is doing group indirection.
2. Explain the “new enemy” problem in your own words, including why the two writes involved were correctly ordered by the application, and describe how a snapshot token (“zookie”) 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 business hours.” Explain why a pure relationship graph cannot express the time condition, and describe two ways to handle it (a companion ABAC check, or a conditioned edge). Which keeps the authorization logic in one place?

Hands-on exercises

1. Model a folder tree in OpenFGA. Using the OpenFGA playground, declare user, folder, and document types with viewer/editor relations, parent inheritance (viewer from parent), and editor implies viewer. Add tuples that make one user an editor of a top folder, then run a Check proving 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” (Expand) operation to answer “which documents can this user view?” and “who can view this document?” Note how these queries — expensive scans in RBAC or ABAC — are native traversals here.
3. Find the seam. Take one authorization rule from a system you know and split it into its relationship part (“…because they own/belong to/manage…”) and its condition part (“…but only if time/amount/risk…”). Decide which belongs in a relationship graph and which needs an attribute condition, and sketch how a conditioned edge would let a single ReBAC engine carry both.