Fine-Grained Authorization: Zanzibar, OpenFGA & Friends

A rule that keeps growing

Daniel is asked to add sharing to the company’s internal operations tool, where teams keep saved reports in folders. The first requirement sounds simple: if a folder is shared with a team, everyone on the team can see the reports in it. He writes it as a Rego rule and it works. Then folders get subfolders, and the rule needs to look one level up, then two. Then teams get sub-teams, and the rule needs to look through nested groups as well. By the fourth meeting the rule is a recursive search over every group Sara might belong to and every folder above every document, and Daniel realizes he isn’t writing a rule any more. He’s writing a graph search by hand, inside a language that wasn’t designed for it.

The previous article closed on exactly this question: can Sara view this document because she’s in a group that was shared a folder that contains it? Rego, Cedar, and Casbin can all check one hop, “is Sara in this group” or “is this document in this folder.” What they struggle with is the chain: group membership, nested to any depth, feeding into folder containment, nested to any depth, feeding into a yes or no that depends on walking a path through data whose shape you don’t know in advance. That chain isn’t a flat rule. It’s a graph, and “can Sara reach this document?” is a graph-reachability question.

This article covers the family of systems built to answer that question at production scale: Google Zanzibar, the 2019 paper and internal system that formalized the approach, and its main open-source descendants, OpenFGA, SpiceDB, and Ory Keto. The modeling technique they share is ReBAC, relationship-based access control, which you met among the decision models. Here ReBAC stops being a modeling idea and becomes an architecture you can run.

Why a flat rule doesn’t scale to relationships

Make the chain concrete. Sara is a member of the finance-team group. finance-team is a viewer of the Q3-Reports folder. Q3-Reports contains a document called board-summary. Sara should be able to view board-summary, not because any rule names Sara or that document, but because the path between them, through membership and containment, resolves to “viewer.”

Now try to express “viewer of a document” as one flat condition, the way the previous article’s engines want. You’d have to enumerate every group Sara might belong to, every folder each of those groups might reach, and every document each of those folders might contain, and the moment someone creates a subfolder inside Q3-Reports or nests one group inside another, your rule is wrong. That’s Daniel’s experience. The problem isn’t that Rego, Cedar, or Casbin are bad languages; it’s that the question isn’t “evaluate this condition” but “does a path exist,” and that’s graph traversal, not rule evaluation. A relationship-based system stores the edges, the raw facts, Sara member-of finance-team, finance-team viewer-of Q3-Reports, Q3-Reports parent-of board-summary, and answers every access question by walking them, however deep the graph is at query time.

This isn’t a new decision model. It’s the same ReBAC from the decision-model articles, unchanged in spirit. What’s new is the architecture that makes ReBAC work when the graph has millions of nodes and edges and needs an answer in a few milliseconds: a storage and query engine built for this shape of problem instead of a general policy language pressed into a job it wasn’t designed for.

Google Zanzibar

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, fast access checks across 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 nearly every ReBAC system since has followed.

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 directly a viewer of the board-summary document. Crucially, a tuple’s subject can itself be another object’s relation, a userset, which is how group membership and hierarchy come out of the same primitive instead of needing special handling: doc:board-summary#viewer@group:finance-team#member means everyone who’s a member of finance-team is a viewer, not one particular user. Chain a few of these and you get Sara’s case: membership tuples, containment tuples, and a rewrite rule connecting them into one graph.

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. A union says relation A includes everyone with relation B; an editor relation usually includes the viewer relation, so every editor is a viewer without a second tuple. Tuple-to-userset says relation A on this object is computed by following a tuple to a different object and reading a relation there; that’s how “viewer of the folder” becomes “viewer of every document in it,” by rewriting a document’s viewer relation to include its folder’s viewers 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 internal syntax, simplified from the paper’s protobuf-based format, the namespace configuration for that document rule looks roughly like this:

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

That’s the kind of configuration Google’s products write and maintain, and it’s exactly what OpenFGA’s modeling language, shown below, exists to make readable: the same union of direct and inherited viewers, the same tuple-to-userset hop through parent, in a syntax nobody would want to write by hand at scale. Understanding the raw shape once makes every friendlier notation readable straight away, because you’re never learning a new model, only new notation for the same union and tuple-to-userset primitives.

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 means walking the graph outward from the object recursively: read its rewrite rule, follow every union and tuple-to-userset branch, and recurse into each referenced object’s relations until a path to the subject turns up or every branch is exhausted. For Sara, Check(doc:board-summary, viewer, user:sara) follows the rewrite rule to the parent folder, checks the folder’s viewers (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 members)
  Engine->>Engine: expand the team members userset
  Engine->>Engine: Sara found as direct member of Finance Team
  Engine-->>Client: Allow (path found)

The new enemy problem

Walking the graph isn’t enough to be safe. Zanzibar’s other defining contribution is a consistency guarantee, motivated by an attack shape the paper calls the new enemy problem. Say Sara is removed from finance-team at time T because she’s moving to another team, a deliberate revocation. If, a moment after T, a Check for her access is served by a database replica that hasn’t caught up with the removal, it can still return Allow. The “enemy” isn’t a hacker exploiting a bug; it’s ordinary eventual consistency, applied to the one kind of read where staleness is a security hole rather than a small 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)
  DB->>DB: applied to primary, not yet replicated
  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 the globally ordered timestamps of Google Spanner and its TrueTime clocks, which a client attaches to a Check to say “answer using data at least as fresh as this point.” A write returns a zookie marking when it took effect, and the client that just made a sensitive write, such as a revocation, can pass it into its next Check and be guaranteed to see the revocation instead of racing an eventually consistent cache. Zanzibar defaults every Check to “at least as fresh as the last write this client cares about,” making the safe behavior the default rather than something every caller has to remember.

It’s tempting to see graph traversal as the interesting problem and consistency as an operational detail. It’s the other way round. Walking the graph for a Check is well understood; doing it correctly at global scale, under load, without ever letting a revoked permission stay briefly valid, is what took Google’s paper to solve and what every serious Zanzibar-family implementation has to deal with. A ReBAC engine with the right graph model and the wrong consistency model isn’t a smaller Zanzibar; it’s missing the half of the design that makes it trustworthy for security decisions.

OpenFGA: Zanzibar for everyone else

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

Where Zanzibar’s namespace configuration is an internal format, OpenFGA defines types and relations in a compact, readable modeling language:

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 as you read the Zanzibar rewrite rule. A document’s viewer relation is a union of direct grants, [user, group#member], matching individual users or group members, or the viewer relation inherited from its parent folder, exactly the tuple-to-userset rewrite that let Sara’s folder access flow down to the document. The 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 with OpenFGA’s naming:

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

Check answers whether one subject can do one thing. Real applications also need the reverse questions, which documents Sara can see, to draw a file list, and who can see this document, to draw a share dialog, and answering either by running Check against every candidate object or user doesn’t scale. OpenFGA has dedicated ListObjects and ListUsers APIs, backed by read-optimized indexes and reverse-expansion algorithms, because listing everything reachable is a different and harder query than checking whether one thing is. When you evaluate a fine-grained authorization system, ask not only how fast Check is but how it handles List.

OpenFGA runs as a standalone service over gRPC or HTTP, usually in the central-service shape from the XACML article, one authorization service called by every application that needs a decision, with SDKs for the common server languages. It’s also offered as a managed service, Auth0 FGA. Consistency is tunable per request: callers can ask for minimum latency, accepting a small staleness window, or for higher consistency, paying more latency for a Zanzibar-style freshness guarantee, depending on how sensitive that check is. It’s the same “trade-off, not a fixed answer” lesson the XACML article made about where to place the PDP, applied to consistency.

Other members of the family

OpenFGA is the most widely adopted open-source implementation, but not the only one. SpiceDB, from AuthZed, is another production-grade open-source Zanzibar implementation with its own schema language, a strong focus on pluggable, strongly consistent storage (PostgreSQL, CockroachDB, Spanner), and a testing and 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 balance between latency and freshness a visible parameter rather than a hidden default. Ory Keto is a lighter open-source permission server, also inspired by Zanzibar, that emphasizes simplicity and fits naturally with the rest of the Ory stack, Kratos for identity and Hydra for OAuth and OIDC, a good choice for teams already standardized on Ory. Permify is a newer entrant aiming for an approachable modeling experience like OpenFGA’s, with built-in support for filtering on attributes alongside relationships and a schema validator that catches modeling mistakes before production.

All four share the same DNA, tuples, a relation graph driven by rewrite rules, and a Check API for reachability, because they’re all faithful implementations of the model the paper described. Choosing among them today is mostly about storage preferences, hosting (self-run or managed), how finely you can tune consistency, and ecosystem fit, not about different authorization semantics. None of them needs Spanner or TrueTime as Google’s Zanzibar does, and that’s the engineering achievement each represents: Zanzibar’s consistency guarantees on ordinary, widely available databases.

How this compares with the rest

It’s easy to mistake ReBAC engines for “yet another policy language,” when they’re solving a structurally different problem.

The two families aren’t competitors so much as tools for different shapes of question, and production systems often run both: OPA or Cedar deciding whether an API call is allowed at all, and OpenFGA answering which specific documents the response may include.

Sara’s reports, start to finish

Back to Daniel’s operations tool, now with every piece named. Sara joins finance-team when she’s onboarded, one tuple: group:finance-team#member@user:sara. Her manager shares the Q3-Reports folder with the whole team, one tuple: folder:q3-reports#viewer@group:finance-team#member. Someone uploads board-summary into the folder, one tuple: document:board-summary#parent@folder:q3-reports. Nobody ever explicitly gives Sara access to board-summary, and yet when she opens the tool, Check(document:board-summary, viewer, user:sara) walks the path traced in the diagram and returns Allow. Daniel’s recursive Rego rule is replaced by three facts and one line of model.

Now Sara moves teams. HR’s system deletes the group:finance-team#member@user:sara tuple, one deletion and nothing else. Every document in every folder shared with finance-team, at any depth, immediately stops being reachable from Sara, because the path that made them reachable no longer exists. There’s no per-document cleanup and no forgotten grants to hunt down. That one deletion, reflected correctly and at once thanks to the consistency guarantees above, is the whole 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.

Testing and running a relationship model

A relationship graph is still policy, and the discipline of policy as code still applies; you’re just testing reachability instead of rule conditions. OpenFGA supports test files, usually .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; with the membership tuple removed, it must be false. They run in CI just as opa test runs Rego assertions. SpiceDB’s zed tool offers an equivalent workflow for testing and validating a schema and a set of relationships locally. A broken authorization graph should fail a pull request, not be discovered in production.

Running one in production adds a concern flat policy engines don’t have: graph depth. A revocation is cheap, one tuple deleted, but a Check against a deeply nested graph, groups in groups in groups, folders many levels deep, does more traversal work than a flat rule ever would. That’s why every implementation here invests heavily in caching, bounded traversal depth, and read-optimized indexes for List queries. Designing a relationship model is a schema exercise and, unavoidably, a performance exercise too.

Recap

Relationship-based authorization solves the problem these articles have been building toward, access that depends on a graph rather than a flat rule. The question changed, not just the language: “can Sara reach this document?” is reachability, which is why OPA, Cedar, and Casbin all struggle with sharing and nesting to any depth, however good their languages are. Zanzibar’s model is tuples plus rewrite rules: direct facts, object#relation@subject, combine through union and tuple-to-userset rewrites into a graph, answered by one Check operation that walks it. The new enemy problem is the hardest part: a revocation must be visible immediately, not eventually, which zookies solve by pinning a Check to a snapshot no older than a given write. OpenFGA, SpiceDB, Ory Keto, and Permify bring the model outside Google, with friendlier modeling languages over the same primitives and first-class List APIs for the reverse queries flat engines rarely handle well. And this is a different tool for a different question, not a replacement for OPA, Cedar, or Casbin; real systems often run both.

Three questions to test yourself

1. Using the Sara, finance-team, Q3-Reports, and board-summary example, explain why “can Sara view this document?” can’t be written as one flat rule the way a Cedar permit or a Casbin matcher can. What exactly makes it a reachability question?
2. Describe the new enemy problem in your own words: what has to go wrong, and in what order, for it to cause a security incident? Then explain what a zookie changes in that sequence.
3. A team is building “share this document with a group” and is choosing between a Cedar policy with a hard-coded list of allowed groups and a relationship tuple in OpenFGA. Which fits better as the feature grows to support nested folders and nested groups, and why?

Hands-on exercises

1. Model Sara’s case. Write an OpenFGA model, or the equivalent Zanzibar-style namespace configuration, with user, group, folder, and document types and the membership, viewer, and parent relations from this article. Add the three tuples from Sara’s scenario and confirm that 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 folder nested inside q3-reports and a second group nested inside finance-team, if your engine supports groups in groups. Write out step by step how a Check would cross the extra layers, and note where traversal could get expensive if the nesting were much deeper.
3. Design a test suite for a relationship model. Using OpenFGA’s .fga.yaml format or an equivalent, write at least four assertions for Sara’s case: 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 with no new direct grant.