Intersection Arrow Proposal

[josephschorr]

Background

SpiceDB’s schema contains the arrow operation (known as TupleToUserset in Zanzibar), which performs a “walk” of relationships found on a relation (forming the tupleset), and for each object found, walks to the referenced relation or permission of a given name on the object (via the computed_userset).

If any results are found by this walk, then the overall arrow operation resolves to HAS_PERMISSION for a Check:

definition user {}

definition folder {
  relation viewer: user
}

definition document {
  relation parent: folder
  permission view = parent->viewer
}

Example Resolution Steps

1. Start a parent, and find all subjects for the current document object
2. For each folder found, walk to the viewer relation and perform a check for the user on that relation, with the folder as the new object
3. If any of the folders have the user as a viewer, then the user is considered to be able to view the document

Problem

There are scenarios in which a permission might be defined not based on whether the user has permission on any of the parent object(s)'s relations, but rather all of the parent objects's relations.

As a concrete example, imagine a schema with permission roles, each of which is important when taken together:

definition user {}

definition role {
  relation viewer: user
}

definition document {
  relation requirement: role
  permission view = requirement->viewer // Works with just one requirement
}

If the writer of the schema wishes to define view such that users can only view a document if they are a viewer on all roles found in requirement, they currently cannot do so easily.

Proposal

Introduce a new operator into the SpiceDB schema known as the “intersection arrow” or “and arrow”.

The arrow would act the same as the existing arrow operator, but for every subject found, would require that all checks succeed for the operator to return HAS_PERMISSION

Example:

definition user {}

definition role {
  relation viewer: user
}

definition document {
  relation requirement: role
  permission view = requirement-&->viewer // Needs all requirements
}

In the above example, if there are multiple roles within requirement on the document, then the user would be required to have viewer on all found roles for them to have view permission

Changes

• [ ] Add either a new operation or a new field onto TupleToUserset in the core namespace API protos
  1. Likely a new field indicating the operation to be performed for each computed userset value, and a default to “union”
  2. If a new flag: add switches, on the flag, everywhere a TTU is currently used and ensure that a panic is raised in the default branch
• [ ] Add the new syntax to the lexer
• [ ] Add the new syntax to the parser, with a new node in the syntax tree
• [ ] Have the schemadsl compiler and formatter support the new new node type
• [ ] Have Check, Expand and Lookup be adapted to support the new construct/new flag on TTUs
  1. Lookup will need to consider it an intersection and use the slow path for now
• [ ] Update the playground to support the new syntax
• [ ] Write many consistency tests
• [ ] Update schema documentation with the new operator and examples
• [ ] Write a blog post, with good examples

[jzelinskie]

I'm here for the syntax bike-shedding:

• requirement~>viewer
• requirement=>viewer
• requirement.viewer
• requirement->>viewer

[bryanhuhta]

I'm here for the syntax bike-shedding

Additionally: &> or &-> but I like ~> best.

[josephschorr]

~> is certainly simpler to implement, but not sure if there is a strong connection between ~ and the intersection operation here

[josephschorr]

Another idea: requirement->&viewer, since it is the intersection of all the viewer's

[phdowling]

We would be highly interested in this feature as we have a scenario like this in our business requirements for authorization to specific kinds of resources that have dependencies. What would be the current workaround for this problem? For the concrete example you gave, can such a check be achieved in spicedb at all, or would the client have to make sure to run all necessary checks as separate calls and evaluate the "intersection" constraint itself?

[josephschorr]

@phdowling Right now you'd need to issue the checks yourself and compute it client side. Intersection currently only operates over distinct relations, not within one.

[josephschorr]

Suggestions are welcome for the operator to use, as it is the main blocker for adoption

[phdowling]

Thanks for the quick response @josephschorr. Since you ask: to me, => makes intuitive sense as it looks very similar to -> but has multiple lines, so you can read it as "follow all paths, not just any path". I also like &> and ->& (and other & variants) since it makes the logical operator clearly visible.

[alebo]

I would be happy to test any draft implementation even if the syntax is still subject to change.

[josephschorr]

Another possible syntax:

definition user {}

definition folder {
  relation viewer: user
}

definition document {
  relation parent: folder
  permission view = parent.any(viewer) + parent.all(viewer)
}

The parent.any(viewer) would be equivalent to today's parent->viewer (they'd be aliases) and parent.all(viewer) would represent the user being in viewer for all parents.

[phdowling]

@josephschorr is this on your development roadmap now by any chance? We're still quite eager to push down more of our authz logic into SpiceDB, our current approach of issuing multiple calls to SpiceDB and computing the intersection ourselves feels like an anti-pattern. Coupled with caveated relationships (great stuff by the way) this would get us to a point of handling basically all authz business logic declaratively and efficiently through SpiceDB!

My 2 cents on notation: .any() and .all() are great options IMO, since they are very readable and self-explanatory. From all of the arrow-like options, I probably like => the best (see above, "one link vs. many links" mental model).

[arashpayan]

We have a similar use case to what is described in the issue with one exception. Here's a simplified version of our schema:

definition user {}

definition worker {
    relation manager: user
    permission manage = manager
}

definition job {
    relation viewer: user
    relation worker: worker
    permission edit = viewer & worker->manage
}

Not only would we want to make sure that a user has permission to manage all the workers of a job in order to edit it, we want a user to be able to edit a job if there are no worker relationships on it (so they can start/resume the job with their own workers). Though I'm not familiar with the spicedb internals, I think this would make sense when it comes time to implement.

• Assume the worker->manage check is true
• Start a goroutine for each worker relationship
  • Wait for them all to resolve to a user
  • If anyone of them do not resolve to true, the overall check can terminate early as false.

I'll also add on to the bike shedding over the operator. My first choice would be for .all() because it's the clearest and probably the easiest to google. I imagine a beginner looking over a spicedb schema they've been told to modify for work will Google something like this: all function spicedb schema

which I bet will have better results than ->& spicedb schema because google seems to ignore symbols these days.

But if an arrow of some sort is necessary, I prefer ->&.

[tafli]

We are evaluating SpiceDB as a centralized system for storing our old permission data for a decentralized world. For us, this intersection proposal would be crucial as our use case needs this 'can see all documents in a folder to access the folder' permission.

Are there any news (e.g. a roadmap) for this feature? Are there any ways we can support the implementation of this feature?

[corkrean]

Hey @tafli

It is possible to enforce that a user has a given permission on all of an object's parents with SpiceDB today. You'll need to use an "and tree" to do this.

In this example that continues the original example, a user can be required to have view permissions on all roles to view the document.

[tafli]

Thank you, @corkrean I took a look at this and the problem I see is to build up (and manage) this "and tree". Imaging having hundreds of different files in a folder.

We also had a similar idea using a linked list, which also did work. But the same problem here with building and managing the relations.