Fine-Grained Authorization: Zanzibar, OpenFGA & Friends

From flat rules to a relationship graph

The previous article closed on a question the languages we covered were never built to answer well: can Sara view this document because she is in a group that was shared a folder that contains it? Rego, Cedar, and Casbin can all check “is Sara in this group” or “is this document in this folder” as a single hop. What they struggle with is the chain — group membership, nested arbitrarily, feeding into folder containment, nested arbitrarily, feeding into a final yes/no that depends on walking a path through data whose shape you don’t know ahead of time. That chain is not a flat rule. It is a graph, and the question “can Sara reach this document” is a graph-reachability problem.

This article covers the family of systems built specifically to answer that kind of question at production scale: Google Zanzibar, the 2019 paper and internal system that first formalized the approach, and its most important open-source descendants — OpenFGA, SpiceDB, and Ory Keto. The modeling technique they all share has a name: ReBAC, relationship-based access control, which you first met as one of six decision models back in the ABAC/PBAC/ReBAC article. This article is where ReBAC stops being a modeling idea and becomes an architecture you can actually run.

Why a flat rule doesn’t scale to relationships

Picture the access chain concretely. Sara is a member of the finance-team group. The finance-team group is a viewer of the Q3-Reports folder. The Q3-Reports folder contains a document called board-summary. Sara should be able to view board-summary — not because any rule mentions Sara or that document by name, but because the path between them, traced through membership and containment, resolves to “viewer.”

Now try to express “viewer of a document” as a single flat condition the way the previous article’s engines want you to. You would need to enumerate every group Sara might belong to, every folder each of those groups might have access to, and every document each of those folders might contain — and the moment someone creates a sub-folder inside Q3-Reports, or nests one group inside another, your flat rule is already wrong. The problem is not that Rego, Cedar, or Casbin are bad languages; it is that the question itself is not “evaluate this condition,” it is “does a path exist,” and path-existence is graph traversal, not rule evaluation. A relationship-based system solves this by storing the edges — the raw facts, Sara member-of finance-team, finance-team viewer-of Q3-Reports, Q3-Reports parent-of board-summary — and answering every access question by walking them, however deep the graph happens to be at query time.

Google Zanzibar: the paper that started it

Google needed one authorization system to serve Drive, Calendar, YouTube, Photos, Cloud, and dozens of other products — each with its own sharing model, all needing correct, low-latency access checks at a scale of trillions of stored relationships and millions of queries per second. The 2019 paper Zanzibar: Google’s Consistent, Global Authorization System describes how they built it, and its data model became the template essentially every ReBAC system since has followed.

Relationship tuples: the only fact Zanzibar stores

Everything in Zanzibar is a relationship tuple, written object#relation@subject — “this object has this relation to this subject.” doc:board-summary#viewer@user:sara means Sara is a viewer of the board-summary document, directly. Critically, the subject of a tuple can itself be another object’s relation — a userset — which is how group membership and hierarchy fall out of the same primitive instead of needing special-case handling: doc:board-summary#viewer@group:finance-team#member means “everyone who is a member of the finance-team group” is a viewer, not one specific user. Chain a few of these and you get exactly the Sara example: membership tuples, containment tuples, and a userset rewrite rule (covered next) connecting them into one graph.

Userset rewrites: how relations compute from other relations

A raw tuple only states a direct fact. The interesting behavior — “editors are automatically viewers too,” “viewing a folder means viewing everything inside it” — comes from a namespace configuration that defines, for each object type, how each relation can be computed from others. Two rewrite operations matter most: union (relation A includes everyone with relation B — an editor relation typically unions in the viewer relation, so every editor is automatically a viewer without a second tuple) and tuple-to-userset (relation A on this object is computed by following a tuple to a different object and reading a relation there — this is exactly how “viewer of the folder” becomes “viewer of every document inside it,” by rewriting a document’s viewer relation to include the folder’s viewer relation, followed through the containment tuple).

flowchart LR
  accTitle: How direct tuples and a userset rewrite combine into a traversable relationship graph
  accDescr: The diagram shows three direct relationship tuples as nodes connected by labeled edges. Sara connects to Finance Team group by a member edge. Finance Team group connects to Q3 Reports folder by a viewer edge. Q3 Reports folder connects to Board Summary document by a parent edge. A separate note explains the userset rewrite rule: the viewer relation on a document is computed as the union of any direct viewer tuple plus the viewer relation of its parent folder, followed through the parent edge. This rewrite rule is what allows Sara's membership and the folder's viewer grant to resolve, through the parent edge, into Sara being a viewer of the document.
  Sara((Sara)) -- member --> Team[Finance Team<br/>group]
  Team -- viewer --> Folder[Q3 Reports<br/>folder]
  Folder -- parent --> Doc[Board Summary<br/>document]
  Rule["Rewrite rule on document.viewer:<br/>direct viewer OR<br/>parent folder's viewer"]
  Rule -.-> Doc

In Zanzibar’s own internal syntax, the namespace configuration expressing that document rewrite rule looks roughly like this (simplified from the paper’s protobuf-based format):

name: "document"
relation { name: "parent" }
relation {
  name: "viewer"
  userset_rewrite {
    union {
      child { _this {} }
      child { tuple_to_userset {
        tupleset { relation: "parent" }
        computed_userset { relation: "viewer" }
      } }
    }
  }
}

This is precisely the config Google’s own products author and maintain, and it is exactly what OpenFGA’s DSL (shown below) exists to make readable: the same union-of-direct-and-inherited-viewer logic, the same tuple-to-userset indirection through the parent relation, expressed in a syntax nobody would want to hand-write at scale. Understanding the raw shape once is what makes every friendlier DSL after it instantly legible — you are never learning a new model, only a new notation for the same union and tuple-to-userset primitives.

The Check API: answering one question by walking the graph

Every Zanzibar-family system exposes the same core operation: Check(object, relation, subject) — is this subject related to this object by this relation, directly or through any chain of tuples and rewrite rules? Answering it means recursively walking the graph outward from the object: read its rewrite rule, follow every union and tuple-to-userset branch, and recurse into each referenced object’s own relations, until a path to the subject is found or every branch is exhausted. For the Sara example, Check(doc:board-summary, viewer, user:sara) follows the rewrite rule to the parent folder, checks Folder#viewer@user:sara (no direct match), expands finance-team#member, and finds Sara — a path exists, so the answer is true.

sequenceDiagram
  accTitle: A Check call recursively traversing the relationship graph
  accDescr: The diagram shows a sequence of steps for evaluating Check on Board Summary document, viewer relation, for user Sara. The client calls Check. The engine reads the document's rewrite rule and follows it to the parent folder's viewer relation. The engine reads the folder's viewer tuple, which names a userset, the Finance Team group's member relation, rather than a direct user. The engine expands that userset by reading Finance Team's member tuples and finds Sara listed as a direct member. Because a path was found, the engine returns Allow to the client.
  Client->>Engine: Check(doc:board-summary, viewer, user:sara)
  Engine->>Engine: apply rewrite rule (direct OR parent's viewer)
  Engine->>Engine: read Folder#viewer tuple (points to Team#member userset)
  Engine->>Engine: expand Team#member userset
  Engine->>Engine: Sara found as direct member of Finance Team
  Engine-->>Client: Allow (path found)

The new enemy problem: consistency at Google’s scale

Graph traversal alone is not enough to be safe — Zanzibar’s other defining contribution is a specific consistency guarantee, motivated by a specific attack shape the paper names the new enemy problem. Imagine Sara is removed from finance-team at time T because she is leaving the company — a deliberate revocation. If, a moment after T, a Check call for her access happens to be served by a database replica that has not yet caught up with the removal, it can still return Allow. The “enemy” is not a hacker exploiting a bug; it is ordinary eventual consistency, applied to the one kind of read where staleness is a security hole rather than a minor inconvenience.

sequenceDiagram
  accTitle: The new enemy problem and how a consistency token fixes it
  accDescr: The diagram contrasts two timelines. In the first, Admin removes Sara from Finance Team at time T, writing to a primary database. Shortly after, a Check call for Sara's access to Board Summary is served by a stale replica that has not yet received the removal, and incorrectly returns Allow, illustrating the new enemy problem. In the second timeline, the same Check call instead carries a zookie consistency token pinned to a snapshot at or after time T. The engine is forced to read data at least as fresh as that snapshot, sees the removal, and correctly returns Deny.
  Admin->>DB: remove Sara from Finance Team (time T)
  Note over DB: write applied to primary,<br/>not yet replicated everywhere
  Client->>Engine: Check(sara, viewer, doc) — no zookie
  Engine->>DB: read from a stale replica
  DB-->>Engine: Sara still a member (stale)
  Engine-->>Client: Allow (WRONG — the new enemy)
  Client->>Engine: Check(sara, viewer, doc) — zookie pinned to T
  Engine->>DB: read at snapshot >= T
  DB-->>Engine: Sara removed (fresh)
  Engine-->>Client: Deny (correct)

Zanzibar’s fix is the zookie — an opaque consistency token, derived from Google Spanner’s globally-ordered timestamps (via TrueTime), that a client attaches to a Check call to say “answer this using data at least as fresh as this point.” A write returns a zookie marking the moment it took effect; the client that just performed a sensitive write (like a revocation) can pass that zookie into its next Check and be guaranteed the revoke is visible, instead of racing an eventually-consistent cache. Zanzibar defaults every Check to “at least as fresh as the last write this client is known to care about,” making the safe behavior the default rather than something every caller has to remember to ask for.

OpenFGA: Zanzibar for the rest of us

OpenFGA is an open-source authorization engine, originally built at Auth0 and now a CNCF project, that implements Zanzibar’s relationship-tuple-and-Check model without requiring Google-scale infrastructure underneath. It is the most widely adopted way to get Zanzibar-style ReBAC into a production system today.

The authorization model: a readable DSL over the same primitives

Where Zanzibar’s namespace configuration is an internal Google format, OpenFGA defines types and relations in a compact, human-readable DSL:

type user
 
type group
  relations
    define member: [user]
 
type folder
  relations
    define viewer: [user, group#member]
 
type document
  relations
    define parent: [folder]
    define viewer: [user, group#member] or viewer from parent

Read the last line the way you read the Zanzibar rewrite rule earlier: a document’s viewer relation is a union of direct viewer grants ([user, group#member], matching either individual users or group members directly) or the viewer relation inherited from its parent folder — exactly the tuple-to-userset rewrite that let Sara’s folder-level access flow down to the document. The relationship facts themselves are stored as tuples, structurally identical to Zanzibar’s:

{"user": "user:sara", "relation": "member", "object": "group:finance-team"}
{"user": "group:finance-team#member", "relation": "viewer", "object": "folder:q3-reports"}
{"user": "folder:q3-reports", "relation": "parent", "object": "document:board-summary"}

And the query is the same Check operation, now with OpenFGA’s naming:

POST /stores/{store_id}/check
{
  "tuple_key": {
    "user": "user:sara",
    "relation": "viewer",
    "object": "document:board-summary"
  }
}

The other half of the problem: listing, not just checking

Check answers “can this one subject do this one thing.” Real applications also need the reverse questions — “which documents can Sara see” (to render a file list) and “who can see this document” (to render a share dialog) — and naively answering either by running Check against every candidate object or every candidate user does not scale. OpenFGA exposes dedicated ListObjects and ListUsers APIs, backed by read-optimized indexes and reverse-expansion algorithms, specifically because “list everything reachable” is a fundamentally different (and harder) query shape than “is this one thing reachable” — a distinction worth remembering any time you evaluate a fine-grained authorization system: ask not just “how fast is Check” but “how does it handle List.”

Deployment and tuning

OpenFGA runs as a standalone service (gRPC or HTTP), typically the centralized-service deployment shape from the XACML article — one authorization service, called by every application that needs a permission decision, with SDKs in the common server languages. It is also available as a managed offering (Auth0 FGA). Consistency is tunable per request rather than fixed: callers can request minimal latency (accepting a small staleness window) or higher consistency (paying more latency for a Zanzibar-style freshness guarantee) depending on how security-sensitive that particular check is — the same “trade-off, not a fixed answer” lesson the XACML article’s deployment section made about PDP placement, now applied to consistency instead of network topology.

Other members of the family

OpenFGA is the most widely adopted open-source Zanzibar implementation, but it is not the only one, and the differences between them are worth knowing:

• SpiceDB (from Authzed) is another open-source, production-grade Zanzibar implementation, with its own schema language and a strong focus on pluggable, strongly consistent storage backends (PostgreSQL, CockroachDB, Spanner) and a dedicated testing/tooling CLI (zed). Its consistency API is unusually explicit — callers choose minimize_latency, at_least_as_fresh (the zookie-style guarantee), or fully_consistent per request, making the latency-versus-freshness trade-off this article keeps returning to a first-class, visible parameter rather than a hidden default.
• Ory Keto is a lighter-weight open-source permission server, also Zanzibar-inspired, that emphasizes simplicity and integrates naturally with the rest of the Ory identity stack (Kratos for identity, Hydra for OAuth/OIDC) — a good fit for teams already standardized on Ory who want relationship-based checks without adopting a separate ecosystem.
• Permify is a newer open-source entrant in the same family, aiming for an approachable modeling experience similar to OpenFGA’s, with built-in support for data filtering (attribute-based fields alongside relationships) and a schema validator for catching modeling mistakes before they reach production.

All four share the same DNA — relationship tuples, a rewrite-rule-driven relation graph, a Check API answering reachability — because they are all faithful implementations of the model the Zanzibar paper described. Choosing between them today is mostly a question of storage backend preferences, hosting model (self-run versus managed), consistency-tuning granularity, and ecosystem fit, not fundamentally different authorization semantics. None of them require Spanner or TrueTime the way Google’s own Zanzibar does — that is precisely the engineering achievement each project represents: delivering Zanzibar’s consistency guarantees on ordinary, widely available databases instead of Google’s globally-distributed infrastructure.

How this compares to everything else in the module

It is worth being precise about what actually changed, because it is easy to mistake ReBAC engines for “yet another policy language” when they are solving a structurally different problem.

The two families are not competitors so much as tools for different question shapes, and production systems commonly use both — OPA or Cedar deciding “is this API call allowed at all” while OpenFGA answers “which specific documents does this response get to include,” each doing the part it is actually good at.

Worked example: Sara’s shared reports, traced in full

Return one last time to the scenario that opened this article, now with every piece named. The cashback company’s internal operations tool lets teams organize saved reports into shared folders. Sara joins the finance-team group when she’s onboarded — one tuple: group:finance-team#member@user:sara. Her manager shares the Q3-Reports folder with the whole finance team — one tuple: folder:q3-reports#viewer@group:finance-team#member. Someone on the team uploads a board-summary document into that folder — one tuple: document:board-summary#parent@folder:q3-reports. No one ever explicitly grants Sara access to board-summary — and yet the moment she opens the operations tool, Check(document:board-summary, viewer, user:sara) walks exactly the path traced in the earlier diagram and returns Allow.

Now watch what happens when Sara moves teams. HR’s system removes the group:finance-team#member@user:sara tuple — one deletion, nothing else touched. Every document in every folder shared with finance-team, at any depth, instantly stops being reachable from Sara, because the path that made them reachable no longer exists — no per-document cleanup, no orphaned grants to hunt down. That single deletion, correctly and immediately reflected thanks to the consistency guarantees this article covered, is the entire payoff of modeling access as a graph instead of a pile of individual permissions: the graph’s shape is the access model, so changing one relationship changes everything that depended on it, all at once, correctly.

Testing and operating a relationship model

A relationship graph is still policy, and the “policy as code” discipline from the previous article still applies — the mechanics just look a little different because you are testing reachability, not rule conditions. OpenFGA supports authorization-model test files (commonly .fga.yaml) that pair a model and a set of tuples with explicit assertions — “given these tuples, Check(document:board-summary, viewer, user:sara) must be true; given these tuples with the membership tuple removed, it must be false” — runnable in CI the same way opa test runs Rego assertions. SpiceDB’s zed CLI offers an equivalent local testing and validation workflow against a schema and a set of relationships. In both cases, the discipline is identical to what the previous article argued for: a broken authorization graph should fail a pull request, not get discovered in production.

Operating one in production adds a concern flat policy engines don’t have: write amplification and graph depth. A single revocation is cheap (one tuple deleted), but a Check against a deeply nested graph — groups inside groups inside groups, folders nested many levels deep — does more traversal work than a flat rule ever would, which is exactly why every implementation in this article invests so heavily in caching, bounded traversal depth, and read-optimized indexes for the List queries. Modeling a relationship graph is not just a schema design exercise; it is also, unavoidably, a performance design exercise.

Recap

Relationship-based authorization solves the problem this whole module has been building toward — access that depends on a graph, not a flat rule:

1. The question changed, not just the language. “Can Sara reach this document” is graph reachability, not rule evaluation — the reason OPA, Cedar, and Casbin all struggle with arbitrarily deep sharing and nesting, however good their languages are.
2. Zanzibar’s model is relationship tuples plus rewrite rules. Direct facts (object#relation@subject) combine through union and tuple-to-userset rewrites into a traversable graph, answered by a single Check operation that walks it.
3. The new enemy problem is the model’s hardest part. A revoke must be visible immediately, not eventually — solved by zookies, consistency tokens that pin a Check to a snapshot no older than a given write.
4. OpenFGA (and SpiceDB, Ory Keto, Permify) bring the model outside Google, with an approachable DSL over the same tuples-and-Check primitives, plus first-class ListObjects/ListUsers APIs for the reverse queries flat engines rarely handle well.
5. This is a different tool for a different question shape, not a replacement for OPA/Cedar/Casbin — real systems commonly run both, each answering the kind of question it is actually built for.

Three questions to test yourself

1. Explain, using the Sara/finance-team/Q3-Reports/board-summary example, why “can Sara view this document” cannot be expressed as a single flat rule the way a Cedar permit policy or a Casbin matcher can — what specifically makes it a graph-reachability question instead?
2. Describe the new enemy problem in your own words: what has to go wrong, in what order, for it to actually cause a security incident? Then explain what a zookie changes about that sequence.
3. A team wants to build a “share this document with a group” feature and is deciding between modeling it as a Cedar policy with a hard-coded set of allowed groups, versus a relationship tuple in OpenFGA. Which fits better as the sharing feature grows to support nested folders and nested groups, and why?

Hands-on exercises

1. Model the Sara example yourself. Write an OpenFGA authorization model (or the equivalent Zanzibar-style namespace config) for user, group, folder, and document types with the membership, viewer, and parent relations from this article. Add the three tuples for Sara’s scenario and confirm a Check for (document:board-summary, viewer, user:sara) returns true; then remove the membership tuple and confirm it returns false.
2. Trace a deeper graph on paper. Extend the example with a second, nested folder inside q3-reports, and a second group nested inside finance-team (if your chosen engine supports group-in-group). Write out, step by step, how a Check call would traverse the extra layer, and identify where the traversal could become expensive if the nesting were much deeper.
3. Design a test suite for a relationship model. Using OpenFGA’s .fga.yaml test format (or an equivalent), write at least four assertions for the Sara scenario: access granted through the group, access denied after the membership tuple is removed, access denied for an unrelated user, and access granted for a second document added to the same folder without any new direct grant.