[RFC] ReBAC

[uatuko]

👉 Should we support full ReBAC?

1. Problem

Currently, very limited ReBAC capabilities can be achieved by creating authorisation grants with relation attributes. But this doesn't allow inherited permissions.

Let's consider the following scenario.

1. User user:jane is a member of group group:editors.
2. All members of group:editors can edit document document:notes.txt.
3. Since user:jane is a member of group:editors, they can edit document:notes.txt.

With current capabilities we will need to explicitly grant each member of group:editors access to document:notes.txt (e.g. document:notes.txt#editor@user:jane¹).

However, this approach can create inconsistencies. e.g. if access rights from group:editors to document:notes.txt changes, we will need to keep track of which authorisation grants have been created by the document:notes.txt#editor@group:editors#member relationship and update them accordingly. Similarly, when group:editors members change we will need to update authorisation grants accordingly.

Since Sentium doesn't have knowledge of document:notes.txt#editor@group:editors#member relationship or group:editor#member@user:* relationships, a system outside of Sentium will need to keep track of these relationships and update authorisation grants accordingly.

2. Proposed solution(s)

2.1 Solution A - Relation Tuples

In order to store relations between entities, we can use relation tuples. A relation tuple can be expressed using '['⟨strand⟩']'⟨entity⟩'/'⟨relation⟩'/'⟨entity⟩ text notation, where;

• ⟨strand⟩ is a relation that connects two tuples together which can be empty
• ⟨entity⟩ is a principal or an outside entity with a type and an id
• ⟨relation⟩ is a string describing the relation between the two entities

To be able to connect two tuples and consider them as a single relation chain,

1. First tuple's right entity must match the second tuple's left entity
2. And, first tuple's relation must match second tuple's strand

For example, []user:alice/member/team:writers can be chained with [member]team:writers/edit/doc:notes.txt but not with [owner]team:writers/edit/doc:notes.txt (since first tuple's relation, member, doesn't match second tuple's strand, owner).

Table 2.1/a - Example relation tuples

Text notation	Semantics
[]user:alice/member/team:writers	User user:alice is a member of team:writers
[member]team:writers/edit/doc:notes.txt	Members of team:writers can edit doc:notes.txt
[owner]folder:F/owner/doc:notes.txt	Owners of folder:F are also owners of doc:notes.txt
[]folder:F/parent/doc:notes.txt	Entity folder:F has a parent relation to doc:notes.txt

Database schema for storing relation tuples

create table if not exists tuples (
  space_id  text not null,  -- used for creating data silos to support multi-tenancy

  strand text,  -- a relation that connects two tuples together

  -- Left entity
  --
  l_entity_type  text not null,
  l_entity_id    text not null,

  relation  text not null,

  -- Right entity
  --
  r_entity_type  text not null,
  r_entity_id    text not null,

  -- Duplicate columns for foreign key constraints if either left/right entity refer to a principal
  --
  l_principal_id  text,
  r_principal_id  text,

  attrs  jsonb,

  _id   text    not null,
  _rid  text,  -- self reference for computed tuples
  _rev  integer not null,

  constraint "tuples.pkey" primary key (_id),
  constraint "tuples.unique" unique (
    space_id,
    strand, l_entity_type, l_entity_id,
    relation,
    r_entity_type, r_entity_id),

  constraint "tuples.fkey-_rid" foreign key (_rid)
    references tuples(_id)
    on delete cascade,

  constraint "tuples.fkey-space_id+l_principal_id" foreign key (space_id, l_principal_id)
    references principals(space_id, id)
    on delete cascade,

  constraint "tuples.fkey-space_id+r_principal_id" foreign key (space_id, r_principal_id)
    references principals(space_id, id)
    on delete cascade,

  constraint "tuples.check-attrs" check (jsonb_typeof(attrs) = 'object')
);

2.1.1 Computed relations

Given the following tuples,

1. []user:jane/member/group:editors - User user:jane is a member of group group:editors
2. [member]group:editors/member/group:viewers - group:editors is a member of group group:viewers and all members of group:editors are also members of group:viewers
3. [member]group:viewers/view/doc:notes.txt - Members of group:viewers can view document doc:notes.txt

 strand |  l_entity_id  | relation |  r_entity_id  |   _id
--------+---------------+----------+---------------+---------
        | user:jane     | member   | group:editors | tuple:1
 member | group:editors | member   | group:viewers | tuple:2
 member | group:viewers | view     | doc:notes.txt | tuple:3

We can compute that user:jane has view relation to doc:notes.txt ([]user:jane/view/doc:notes.txt) using the following logic.

1. Retrieve all tuples where r_entity_id = 'doc:notes.txt', which results in tuple:3
2. Find other tuples where r_entity_id = 'group:viewers' and relation = 'member', which results in tuple:2
3. Find other tuples where r_entity_id = 'group:editors' and relation = 'member', which results in tuple:1
4. Chaining tuple:1, tuple:2 and tuple:3 we can infer []user:jane/view/doc:notes.txt

2.1.2 Optimisations

Computing indirect relations can be expensive when there are deeply nested relations (which essentially results in graph traversal algorithms).

To counter for such scenarios and to keep lookup costs low, we can compute inferred relations between the user and deeply nested groups during inserts and store them as computed tuples.

For example if tuple:1 and tuple:2 existed when inserting tuple:3, we can compute an additional relation as []user:jane/member/group:viewer and store that as a computed tuple entry.

 strand |  l_entity_id  | relation |  r_entity_id  |   _id   |  _rid
--------+---------------+----------+---------------+---------+---------
        | user:jane     | member   | group:editors | tuple:1 |
 member | group:editors | member   | group:viewers | tuple:2 |
 member | group:viewers | view     | doc:notes.txt | tuple:3 |
        | user:jane     | member   | group:viewers | tuple:4 | tuple:2

Note the _rid value in tuple:4. Computed tuples are stored with a reference to the entry that produced the computed tuple so they can be removed if the relation chain changes.

Having the computed tuple simplifies the logic to check if user:jane has a view relation to doc:notes.txt as following.

1. Check a direct relation ([]user:jane/view/doc:notes.txt) - no results
2. List all tuples for groups with view relations to doc:notes.txt - results in tuple:3
3. For each resulting tuple, check if user:jane has a relation to the group that matches the strand - results in tuple:4

Steps (2) and (3) can be further optimised by retrieving the relevant groups with view relation to doc:notes.txt and matching those with relavant groups user:jane is related to.

2.1.3 Constraints

Computing indirect relations and storing them as additional computed tuples during inserts can be expensive, specially when there are deeply nested hierarchies or large number of entities linked.

To limit the number of rows inserted as computed tuples we can first compute additional relations and assign a cost. This cost can then be used to reject modifications if it's above a set threshold.

Footnotes

1. Represented using Zanzibar's text notation for relationship tuples (i.e. ⟨object⟩‘#’⟨relation⟩‘@’⟨user⟩) ↩

[td0m]

For reference, if it helps, here is a summary of my ReBAC implementation.

---

The core of zima is an ACL with the ability to "inherit" access.

zima API consists of only 5 endpoints:

• addSubset(set, subset)
• removeSubset(set, subset)
• label(set, label)
• unlabel(set, label)
• check(set, label) => boolean

Zima is not designed as a primary source of data. It's limited API does not allow complex operations like listing or search. This is on purpose - otherwise zima turns into an ugly NoSQL graph store. Store your records in a primary database such that zima ACLs can be built asynchronously. For this reason all zima endpoints are idempotent.

Example

Bob and alice are employed at "the paper company" and are using an online file storage application.

The file structure looks like this:

/
  internal-docs/
    onboarding.md
  public/
    logo.png
  salaries.pdf

Flat ACLs, RBAC

Alice wants to make herself the owner of "salaries.pdf":

addSubset("file_owners:/salaries.pdf", "alice")

Checking if alice is an owner looks like this:

check("file_owners:/salaries.pdf", "alice")
=> true

If you are in need of a role+permission model, this has to be done at the application layer:

function canViewFile(file, user) {
    return check(`file_owners:${file}`, user) 
        || check(`file_viewers:${file}`, user)
}

Given a single person is not granted by lots of different roles and check being O(1), this should not be a problem to evaluate. The zima library supplies a helper function that allows doing these checks concurrently.

Nested ACLs

Suppose we want users who own a folder to also own its children. We can do this by asynchronously listening to when a file is created and adding the set of folder owners as a subset of the file owners.

function onCreateFile(folderId, fileId, ownerId) {
    z.addSubset(
      `file_owners:${fileId}`,
      `folder_owners:${folderId}`
    )
	
    z.label(`file_owners:${fileId}`, ownerId)
}

This means that now any folder_owner is indirectly contained in the file_owner set.

Groups (also nested ACLs)

Zima would work very similarly if we had "groups" of users with access to a given resource. In such a case you might create the following sql tables:

• groups(id, name)
• users(id, email)
• files(id, data)
• group_members(group_id, user_id)
• `group_files(group, file_id, role)

You'd then listen to when:

• a new group_members row is inserted and add the user U to group_members:G set in Zima via addLabel.
• a new group_files row is inserted and add the group_members set as a subset of the file_owners

Resulting in:

file_owners:F -> group_members:G -> U

Meaning the following is true:

check("file_owners:F", "U")
=> true

[uatuko]

Zima's reference implementation can be found at https://github.com/td0m/zima.

[kw510]

From my understanding, the problem is that subsets are not computed, which is the solution that you have proposed in

2.1.3 Computed relationships

The optimal solution to strive for is a data structure that can support subsets.

This way when querying e.g., is jane a viewer of a object, it would be able to return yes,

• because jane is a user that is within the set of viewers as the set owner is a subset of viewers.

i.e. a function is needed s.t.

IsSuperSet(UserRelationSet, user)

=> IsSuperSet("viewer", "jane") => true

[uatuko]

I've updated the RFC and the numbering has changed. New reference is 2.1.1 Computed relations.

[uatuko]

ReBAC implementation is tracked in #73.