Check it out #2: How intersections and exclusions are computed in SpiceDB and Authzed

In my previous post, I discussed how SpiceDB walks a graph formed by relationships and schema to determine whether a subject (typically a user) has a specific permission on a resource.

Following the publication of that blog post, we’ve had a question come up frequently:

Okay, I get how that works for simple permissions… but how are intersections and exclusions computed?

Why intersection and exclusion?

Permissions used and defined by applications are typically additive: For example, a user may gain permission to view a document if they have a reader role or a writer role or are the administrator of the document’s organization. This process is also known as the user being on an allowlist, typically defined by one or more roles.

In our experience, while most permissions are defined by the requirement of a single resolution path for a given user, some require more complex calculations.

In fact, in some cases, whether a user has a permission can be defined not just by what they are allowed to do but also by what they are not.

To support both of these cases, SpiceDB supports not only the standard union operator (+) but also the intersection and exclusion operators. These operators allow schemas to define that a subject has a permission if either the user is found on both paths (intersection: &) or only on one path, but not the other (exclusion: -)

Example: Intersection

Intersection is often used when a permission is based on multiple other permissions or roles.

For example, imagine a permission on a document that says a comment can be deleted only if a user is both an editor and a commenter.

For this use case, the intersection operator (&) can be used, to create an allowlist that only applies if the user has both roles:

definition user {}

definition document {
  relation commenter: user
  relation editor: user

  permission edit = editor
  permission comment = commenter
  permission delete_comment = comment & edit
}

Example: Exclusion

As another example, imagine an application that allows any user to comment on a post. Such an application might want the ability to ban problematic users from posting while still not requiring the need to grant a comment posting role to every user.

For this use case, the exclusion operator (-) can be used, to create a denylist of only those problematic users, while still allowing for general access:

definition user {}

definition post {
  relation commenter: user:*
  relation banned: user

  permission comment = commenter
  permission post_comment = comment - banned
}

In this schema, only users found in the banned relation will be expressly prohibited from having the post_comment permission; any other user (via the wildcard user:*) will have permission.

Breaking into subproblems

As we saw in the Check it out blog post, permissions in SpiceDB are answered by walking the directed graph formed by both the relationships and the schema, from the permission to the associated subject (user): if at least one such path exists, then the subject has the permission on the resource, and SpiceDB can return saying so.

Recall the example used in that blog post:

To check whether a user (such as jill) had permission to view the document, a walk was started at the view permission for the document, until jill was encountered:

One item elided from the previous blog post is how SpiceDB computes these walks in a performant manner: each "step" in the walk is considered a problem to be solved.

By treating each step as its own problem, SpiceDB is able to both cache problems for reuse and execute these subproblems in parallel, ensuring good performance:

This makes perfect sense for computing permissions that are just additive (i.e. only include "unions"), but how does this work for intersection and exclusion?

Intersection and Exclusion Subproblems

Intersections and exclusions in SpiceDB are handled similarly to standard additive permissions with one caveat: they are not always able to short-circuit.

In a simple addition permission, as soon as SpiceDB finds any subproblem that returns "has permission", we’re done: the subject has been determined to have permission, and the answers to the other subproblems, if any, do not matter. SpiceDB can successfully answer the permission query with the information found and cancel any other pending requests.

For intersection and exclusion, on the other hand, SpiceDB can only partially short-circuit the subproblems; if a subproblem returns "no permission" (for intersection) or "has permission" (for exclusion), SpiceDB must wait for the other subproblem answers before it can continue.

Intersection

Let’s take the intersection example from earlier and compute whether a particular user (fred) can delete a comment on a document.

To start, we have our schema:

definition user {}

definition document {
  relation commenter: user
  relation editor: user

  permission edit = editor
  permission comment = commenter
  permission delete_comment = comment & edit
}

And some test relationships:

document:somedocument#commenter@user:fred
document:somedocument#commenter@user:jill
document:somedocument#editor@user:jill

This schema and relationships can be formed into the following graph:

To compute whether fred can delete a comment on the document, we start at the delete_comment permission and walk outward:

As we see above, the path for permission comment for fred returns "has permission"! However, in order to delete a comment on the document, fred needs both comment and edit permissions This means that SpiceDB had to check both subproblems and wait for all to return "has permission" (which it did not).

Fortunately, here SpiceDB was able to be partially short-circuit: as soon as it saw a "no permission" response for edit, SpiceDB was able to cancel the other check immediately, because an intersection requires all branches to be "has permission".

Let’s try for user jill:

As we can see for jill, every subproblem found shows jill has permission; thus, she has permission to delete comments on the document!

We can therefore see how SpiceDB resolves intersections:

1. API call to check for delete_comment on document:somedocument for subject user:fred
2. Dispatch two subproblems:

• Check permission edit on document:somedocument for user:fred
• Check permission comment on document:somedocument for user:fred

3. If any check is "no permission", return "no permission" (we’re done!)
4. Otherwise, return "has permission" once all checks have completed

Exclusion

Exclusion in SpiceDB is handled as the rough inverse of intersection: Rather than waiting for every branch to return "has permission" and returning immediately if at least one does not, exclusion check all branches (except the first), and if any return "has permission", the entire permission returns "no permission".

Let’s take the example from earlier and compute whether a particular user (jill) can post a comment on a document.

To start, we have our schema:

definition user {}

definition post {
  relation commenter: user:*
  relation banned: user

  permission comment = commenter
  permission post_comment = comment - banned
}

And some test relationships:

document:somedocument#commenter@user:* # Any user can comment
document:somedocument#banned@user:tom  # Tom is banned

This schema and relationships can be formed into the following graph:

To compute whether jill can post a comment on the document, we start at the post_comment permission and walk outward:

Since jill has permission to comment (because of the wildcard) and she is not found in the banned relation, she can comment on the document!

Let’s try for tom, who is supposed to be banned:

In the case of tom, as soon as SpiceDB sees that he is in the banned relation, it does not matter if he otherwise has permission, and SpiceDB can return "no permission"

We can therefore see how SpiceDB resolves exclusions:

1. API call to check for post_comment on document:somedocument for subject user:tom
2. Dispatch two subproblems:

• Check permission comment on document:somedocument for user:tom
• Check permission banned on document:somedocument for user:tom

3. If comment is "no permission", return "no permission"
4. If any other branch is "has permission", return "no permission"
5. Otherwise, return "has permission" once all checks have been completed

Final thoughts

Intersection and exclusion are powerful tools in a schema author’s toolkit, providing the ability to create more complex permissions systems expressing ideas such as feature flags. They are, however, less parallelizable than simple unions, so they should be used wisely.

In the next post in this series, we'll detail about how SpiceDB uses caching to ensure the scalability and performance of checks.

Have another question or want to discuss with the community? Check out our Discord!

Additional Reading

If you’re interested in learning more about Authorization and Google Zanzibar, we recommend reading the following posts:

• Understanding Google Zanzibar: A Comprehensive Overview
• A Primer on Modern Enterprise Authorization (AuthZ) Systems
• Fine-Grained Access Control: Can You Go Too Fine?
• Relationship Based Access Control (ReBAC): Using Graphs to Power your Authorization System
• Pitfalls of JWT Authorization