Is it possible to use the Expand API for reverse lookup?

[biwecka]

Hi, I'm very new to Keto and currently trying to implement the a simple permission model to learn the basic concepts. But I'm struggling with fetching all objects a specific subject is related to. Here's the example I've implemented.

The permission model:

/// <reference path="./lib.ts" />

class Tenant implements Namespace {
    related: {
        members: User[]
    }
    permits = {}
}


class User implements Namespace {
    related: {}
}

class File implements Namespace {
    related: {
        owners: (User | SubjectSet<Tenant, "members">)[],
    }

    permits = {
        access: (ctx: Context) =>
            this.related.owners.includes(ctx.subject)
    }
}

The relations:

// Add `u1` as member of `t1`
Relationship {
    namespace: "Tenant",
    object: "t1",
    relation: "members",
    subject_id: Some(
        "u1",
    ),
    subject_set: None,
},

// Add `u2` as member of `t2`
Relationship {
    namespace: "Tenant",
    object: "t2",
    relation: "members",
    subject_id: Some(
        "u2",
    ),
    subject_set: None,
},

// Grant all members of `t1` access to `f1`
Relationship {
    namespace: "File",
    object: "f1",
    relation: "owners",
    subject_id: None,
    subject_set: Some(
        SubjectSet {
            namespace: "Tenant",
            object: "t1",
            relation: "members",
        },
    ),
},

// Grant all members of `t2` access to `f2`
Relationship {
    namespace: "File",
    object: "f2",
    relation: "owners",
    subject_id: None,
    subject_set: Some(
        SubjectSet {
            namespace: "Tenant",
            object: "t2",
            relation: "members",
        },
    ),
},

// Explicitly grant `u2` access to `f1`.
Relationship {
    namespace: "File",
    object: "f1",
    relation: "owners",
    subject_id: Some(
        "u2",
    ),
    subject_set: None,
},

In other words: There are two tenants (t1 and t2). Each tenant has one user (t1 has u1, t2 has u2) and one file (f1 and f2 respectively). By default access to a file is granted through the members relationship of the tenant, so the tenant acts similar to a directory. But access to files can also be shared across tenants by specifying these relationships explicitly (this is done for u2 who has access to f1).

By issuing the following request to the Expand API, I first tried to query all owners of the file f1:
http://localhost:4466/relation-tuples/expand?namespace=File&object=f1&relation=owners&max-depth=100
This correctly returns u1 and u2.

Full JSON response

JSON Response of the REST API

{
  "type": "union",
  "children": [
  	{
  		"type": "leaf",
  		"tuple": {
  			"namespace": "",
  			"object": "",
  			"relation": "",
  			"subject_id": "u2"
  		}
  	},
  	{
  		"type": "union",
  		"children": [
  			{
  				"type": "leaf",
  				"tuple": {
  					"namespace": "",
  					"object": "",
  					"relation": "",
  					"subject_id": "u1"
  				}
  			}
  		],
  		"tuple": {
  			"namespace": "",
  			"object": "",
  			"relation": "",
  			"subject_set": {
  				"namespace": "Tenant",
  				"object": "t1",
  				"relation": "members"
  			}
  		}
  	}
  ],
  "tuple": {
  	"namespace": "",
  	"object": "",
  	"relation": "",
  	"subject_set": {
  		"namespace": "File",
  		"object": "f1",
  		"relation": "owners"
  	}
  }
}

Afterward I tried querying the "reverse" (meaning to get all the files u2 has access to) with the following request:
http://localhost:4466/relation-tuples?namespace=File&relation=owners&subject_id=u2&max-depth=100
But this only returned f1.

Full JSON response

JSON Response of the REST API

{
  "relation_tuples": [
  	{
  		"namespace": "File",
  		"object": "f1",
  		"relation": "owners",
  		"subject_id": "u2"
  	}
  ],
  "next_page_token": ""
}

For me this seems like Keto is only resolving the explicitly added relation between u2 and f1, but does not consider the "implicity" ownership of f2 through the members relation of u2 and t2. Is this a limitation of Keto or have I made a mistake in modeling the permissions?

PS: The second request mentioned above uses the List API. The documentation to this API states:

It's important to note that the list API does not expand subject sets. Usually the application has some context to determine what tuples to query anyway. That could be knowledge of the structure of subject sets like depth or hierarchy, or the UI context, like a "My Items" view which should probably contain other objects than a "My Organizations" or "Shared with Me" views. If there really is no way to narrow down a query, you will have to use the expand-API instead, or repeatedly call the list API. Try to avoid such cases because they require a lot of resources and can quickly degrade the service quality for all users.

Therefore I also tried using the Expand API for the "reverse" lookup, but didn't get back any useful results.

[careless6666]

I have the same question. I think possible solution for this scenario to make dfs\bfs approach.

User:Piter => Group:Admin => Resource:my-git-repo

Now i can make only expand for Resource:my-git-repo, and i receive full graph
Resource:my-git-repo
=> Group:Admin
=> User:Piter

But for reverse scenario i can make several calls like:

listRelationTuples

{
    "relation_query": {
       "subject": {
        "set": {
             "namespace": "User",
                    "object": "Piter"
        }
       }
    }
}

return

Group:Admin

listRelationTuples

{
    "relation_query": {
       "subject": {
        "set": {
             "namespace": "Group",
                    "object": "Admin"
        }
       }
    }
}

return
Resource:my-git-repo

In parallel, receiving answers, we build a reverse tree

User:Piter
=> Group:Admin
=> Resource:my-git-repo

The main issue with this decision is performance.

[biwecka]

Although making multiple calls and computing the "reverse lookup" from their results is possible, it's not a viable solution to be used in production, because it doesn't work the same for all kinds of relations and gets more tedious for larger hierarchies.

In the meantime I checked out other authorization systems like SpiceDB, OpenFGA and Permify. These all support the reverse lookup scenario. This is how it's modeled in SpiceDB for example: https://play.authzed.com/s/aha4Rc-I98yD/schema

[careless6666]

I checked OpenFGA and i see the same problem

https://openfga.dev/docs/getting-started/perform-list-objects

2. Calling list objects API

curl -X POST $FGA_API_URL/stores/$FGA_STORE_ID/list-objects \
  -H "Authorization: Bearer $FGA_API_TOKEN" \ # Not needed if service does not require authorization
  -H "content-type: application/json" \
  -d '{
        "authorization_model_id": "01HVMMBCMGZNT3SED4Z17ECXCA",
        "type": "document",
        "relation": "reader",
        "user":"user:anne"
    }'


# Response: {"objects": ["document:otherdoc", "document:planning"]}

Warning The performance characteristics of the ListObjects endpoint vary drastically depending on the model complexity, number of tuples, and the relations it needs to evaluate. Relations with 'and' or 'but not' are more expensive to evaluate than relations with 'or'.

[biwecka]

Where do you see a problem here?

This is the exact scenario I described in my question/first post. I was asking about the possibility to perform a reverse lookup (e.g. get all files a user has access to) and the list-objects endpoint of OpenFGA does exactly that.