Every authorization system answers the same kind of question: may this user do this to this object? The paper puts it as checking “that a user has permission to carry out an operation on a digital object” (§1). The four common models differ in what they store and what they compute when the question arrives.
In 1971 Butler Lampson described protection as a matrix: rows are domains (in today’s terms, subjects), columns are objects, and each cell lists the access a domain has to an object (Lampson, “Protection”). No real system stores the whole matrix. An ACL stores its columns, roles and attribute rules compute its cells, and a relationship graph derives them by following edges.
This page models one cell four ways. The running example: Anne, Beto and Chen (user:anne, user:beto, user:chen); the document doc:readme in folder:A; the group group:eng. Anne owns the readme, Beto is in eng, eng members view the readme, and Chen views folder A. The decision is:
Can user:chen view doc:readme?
The expected answer is yes, and only because of the folder. Chen has no direct grant on the readme.
ACL: a list on the object
An access control list attaches to each object a list of entries, each a principal and a set of rights. Multics had ACLs “on segments and directories”, with entries made of “a principal identifier and a set of permissions bits” (§5, citing Saltzer’s SOSP ’73 paper, revised as Saltzer 1974). Later systems let an entry name a group, as POSIX ACLs do (§5).
What does the readme’s own list say about Chen?
The check itself is a lookup: scan the readme’s list for Chen. Notice where the folder went. Inheritance is not part of the ACL model, so the entry has to be copied onto the readme, either when the document is created (VMS “supports ACL inheritance for files created within a directory tree”, §5) or by the application. Once copied, the entry no longer remembers where it came from.
RBAC: users, roles, permissions
Role-based access control puts a layer between users and permissions. In the NIST wording, “RBAC controls all access through roles assigned to users. Each role assigns a collection of permissions to users” (Kuhn, Coyne and Weil 2010). Ferraiolo and Kuhn proposed it in 1992, and a unified NIST model became ANSI INCITS 359-2004 in 2004 (NIST RBAC project).
Roles are global, so a grant on one document needs a role that names that document. The running example becomes three roles:
| User | Role | Permissions the role grants |
|---|---|---|
user:anne |
readme_owner |
edit doc:readme, view doc:readme |
user:beto |
eng |
view doc:readme |
user:chen |
folderA_viewer |
view folder:A, view doc:readme (and every other document in folder A) |
Which role gives Chen the view permission?
Notice that the folder survives only as a name. folderA_viewer is not connected to folder:A in any way the system understands; someone has to keep its permission set equal to “everything in folder A”. Per-object roles like readme_owner are the pattern that leads to role explosion, discussed in the table below.
ABAC: a predicate over attributes
Attribute-based access control stores no grants at all. NIST SP 800-162 defines it as a methodology where authorization “is determined by evaluating attributes associated with the subject, object, requested operations, and, in some cases, environment against policy, rules, or relationships” (NIST SP 800-162). The decision is a function of attributes, evaluated at request time.
Here are the running example’s three grants as rules, in the syntax of Cedar, a policy language AWS open-sourced in 2023:
// Anne: the owner may view
permit (principal, action == Action::"view", resource)
when { resource.owner == principal };
// Beto: anyone whose team is listed on the document
permit (principal, action == Action::"view", resource)
when { resource.viewerTeams.contains(principal.team) };
// Chen: anyone listed as a viewer of the document's folder
permit (principal, action == Action::"view", resource)
when { resource.folder.viewers.contains(principal) };
Which attributes does the engine read to decide Chen’s request?
Notice the two highlighted attributes. doc:readme.folder and folder:A.viewers are relationships stored as attribute values, and the rule follows one to reach the other. The rules stay short, but the data has moved into attributes, and nothing outside the rules says which attributes matter for which decision.
ReBAC: a graph of relationships
Relationship-based access control decides from the relationships between the requester and the resource. Fong credits Carrie Gates with coining the term (her 2007 workshop paper was not checked for this page), and Philip Fong’s 2011 model bases decisions “on the relationship between the resource owner and the resource accessor” (Fong 2011). Fong stresses that binary relations compose, as in friends of friends, while a role is a unary predicate that offers little beyond boolean combinations.
Zanzibar stores each relationship as a relation tuple, object#relation@user (§2.1), and a namespace config says how relations combine. The paper’s Figure 1 encodes exactly this example: owners are editors, editors are viewers, and “viewers of the parent folder are also viewers of the document”. The paper does not use the word ReBAC.
How does a graph of stored tuples reach Chen?
Notice that the folder is still a folder here. The readme points at folder:A with a parent tuple, and the rule turns “viewer of the parent” into “viewer of the readme” at check time. The step-by-step walk is on the relation tuples page.
The same example, cell by cell
| ACL | RBAC | ABAC | ReBAC (Zanzibar) | |
|---|---|---|---|---|
| What is stored | The readme’s list: Anne (owner), group:eng (view), Chen (view, copied from folder A) |
Three role assignments and three roles’ permission sets | Three rules, plus attributes on users, the readme and folder A | Five tuples (owner, eng member, eng viewer, parent, folder viewer) and one namespace config |
| Who can view the readme | Read the list and expand group:eng: Anne, Beto, Chen |
Everyone holding a role that grants “view doc:readme”: Anne, Beto, Chen |
Not stored anywhere: evaluate the rules for every user. Anne, Beto, Chen | Expand doc:readme#viewer (§2.4.5): Anne, Beto, Chen |
| Beto leaves eng | Remove Beto from the group; the readme’s list is untouched | Remove Beto’s assignment to eng |
Change user:beto.team |
Delete one tuple, group:eng#member@user:beto |
| The readme moves from folder A to folder B | Remove the entries copied from A and copy in B’s, on the readme and on everything else that moved | Take “view doc:readme” out of folderA_viewer and add it to a folderB_viewer role |
Change doc:readme.folder; the rules stay the same |
Replace one parent tuple: doc:readme#parent@folder:A#... becomes @folder:B#... |
| What is hard | Inheritance and groups are add-ons; “what can Chen see?” means scanning every object’s list | Role explosion: “thousands of separate roles”, and n Boolean conditions can need 2ⁿ roles (Kuhn et al.); per-object roles like readme_owner make it worse |
Auditing: ABAC “is easy to set up, but analyzing or changing user permissions can be problematic” (Kuhn et al.). “Attribute sprawl” is industry shorthand for the same problem, not a NIST term | Graph traversal: “Recursive pointer chasing … has difficulty maintaining low latency with groups that are deeply nested or have a large number of child groups” (§3.2.4). SpiceDB caps depth at 50 hops by default, OpenFGA’s resolveNodeLimit at 25 |
Notice the two middle rows. Beto leaving eng is one change in every model, because every model here has some form of group. The folder move is where they part: ACL and RBAC copied the folder’s meaning into the readme’s grants, so they have to rewrite those grants; ABAC and ReBAC kept the folder as data, so one value changes. ReBAC also keeps “who can view?” answerable from stored data, which the rules-only ABAC version cannot.
Where Zanzibar sits
Zanzibar is a ReBAC system: relation tuples are the edges, and userset rewrite rules (§2.3.1) say how edges combine. Its data model supports “permissions, users, groups, and inheritance” as found in Multics, UNIX, POSIX ACLs and VMS (§5), and it treats a group as just another object, which “allows us to unify the concepts of ACLs and groups” (§2.1).
RBAC fits on top. The paper says roles “are similar to Zanzibar relations” and that “A number of Zanzibar clients have implemented RBAC policies on top of Zanzibar’s namespace configuration language” (§5). It does not say how; one way is to make a role an object whose member relation is a userset.
What does Chen’s role look like in tuples?
Notice that the role is the same shape as group:eng: a userset. In Zanzibar the second viewer edge is unnecessary, because the parent rule already gives folder viewers the readme; the role only needs to be a viewer of the folder.
ABAC is the part the paper does not cover. Conditions on the request, such as time of day or network, are not relations between stored objects. Several Zanzibar-style systems add them: SpiceDB has caveats, conditions written in CEL (SpiceDB schema docs), OpenFGA has conditions, and Permify’s schema has attribute and rule (Permify docs). Cedar goes the other way: an attribute language with in for hierarchy membership (Cedar syntax).
Sources
- Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang
- B. W. Lampson, “Protection”, 1971; reprinted in ACM SIGOPS OSR 8(1), 1974, PDF
- J. H. Saltzer, “Protection and the Control of Information Sharing in Multics”, CACM 17(7), 1974, dl.acm.org/doi/10.1145/361011.361067
- D. R. Kuhn, E. J. Coyne, T. R. Weil, “Adding Attributes to Role-Based Access Control”, IEEE Computer 43(6), 2010, PDF
- NIST, Role Based Access Control project, csrc.nist.gov/projects/role-based-access-control
- NIST SP 800-162, Guide to Attribute Based Access Control, csrc.nist.gov/pubs/sp/800/162/upd2/final
- Philip W. L. Fong, “Relationship-Based Access Control: Protection Model and Policy Language”, CODASPY ’11, PDF
- Cedar policy syntax, docs.cedarpolicy.com/policies/syntax-policy.html
- SpiceDB recursion and max depth, authzed.com/docs/spicedb/modeling/recursion-and-max-depth
- SpiceDB schema language (vendor docs), authzed.com/docs/spicedb/concepts/schema
- OpenFGA configuration, openfga.dev/docs/getting-started/setup-openfga/configuration
- OpenFGA conditions, openfga.dev/docs/modeling/conditions
- Permify modeling, fusionauth.io/permify-docs/getting-started/modeling