Link contract authorization processing analysis and proposed solution

[Drummond Reed <drummond.reed@xdi.org>]

After several good discussions with Yuriy and Mike Schwartz at the OpenXDI project, who are deep in the implementation of link contracts, I composed the following analysis of why link contract processing is going to be highly burdensome on receiving XDI servers unless we add one small but important requirement to the XDI messaging protocol.

When reading this analysis it can be helpful to reference the link contract example in the last XDI Graph Patterns submission.

I'm sending this message out tonight and putting in on the agenda to discuss on tomorrow's telecon (sending that out next).

=Drummond 

******* PART ONE: ANALYSIS *******

To authorize a link contract, the receiving XDI server MUST verify that 
the following XDI statement is TRUE (i.e., it exists in the graph):

     {assignee} / $do / ({link-contract}/{operation}/{data})

Note
 that I added some spaces to the statement to make it easier to read 
that it contains a nested XDI statement (the cross-reference). So what 
you REALLY have here is two linked XDI statements:
                   (a) {assignee}/$do/{link-contract-X}
                   (b) {link-contract-X}/{operation}/{data}

...where {link-contract-X} is the same XRI in both statements, i.e., it 
is the link between the two statements. Note that both statements have 
equivalent inverse statements, i.e.:

                   (c) {link-contract-X}/$is$do/{assignee}

                   (d) {data}/$is{operation}/{link-contract-X}

In all these statements:

1. {assignee} is the XDI subject who has been assigned the link contract and is sending the request message, e.g., =!2222 in the link contract example in the last XDI Graph Patterns submission.
2. {link-contract} is the root node of the link contract identifed by a $do contextual arc, e.g., =!1111!1$do
   
3. {operation} is the requested operation that is a relational arc on the $do node, e.g., $get
4. {data} is the target subgraph of the operation, e.g., =!1111!1 or =!1111!1+photo!123
   

To
 solve this equation -- to prove that you have both linked XDI 
statements -- the receiving XDI server MUST find both linked statements 
in its graph. But if the receiving XDI server is only given 3 of the 
four variables in the request -- {assignee}, {operation}, and {data}) --
 then the receiving XDI server MUST find the fourth missing link in the 
chain -- the {link-contract} that connects the two XDI statements. We'll call this common variable 
{link-contract-X}.

This job is trivial (and extremely fast) if the receiving XDI server is given {link-contract-X} 
in the request (more about this in the recommendation below). However if the receiving XDI server is NOT given 
{link-contract-X}, then the receiving XDI server must solve both 
equations for a common variable, i.e., it must find if a valid value exists for 
{link-contract-X}.

From everything I've been able to think of, there's no shortcut way to 
do that. The server basically can take one of two approaches. In the 
first approach, the server:

1. Indexes every {assignee}/$do/{link-contract-X} statement to create index #1
   
2. Indexes every {link-contract-X}/{operation}/{data} to create index #2
   

When the server receives a request, the server searches index #1 to get 
all {link-contract-X} for {assignee}, then does a search of index #2 to 
see if any {link-contract-X}/{operation}/{data} statement is TRUE. If 
so, allow, otherwise deny (leaving out $not for right now).

In the second approach, the server:

1. Indexes every {data}/$is{operation}/{link-contract-X} to create index #1
   
2. Indexes every {link-contract-X}/$is$do/{assignee} to create index #2
   

When the server receives a request, the server searches index #1 
to get all {link-contract-X} for {data}/$is{operation}, then does a search of index #2 to 
see if any {link-contract-X}/$is$do/{assignee} statement is TRUE. If so, allow, otherwise deny.

In either case, IMHO, it's a nightmare. A huge amount of processing for 
the receiving XDI server for every inbound request that requires 
authorization.

******* PART TWO: RECOMMENDATION *********

The solution to this processing nightmare is to have the client give the
 server the magic variable -- {link-contract-X} -- in the request. The way to do this is to have the {assignee} keep its own index of the 
link contracts for which it is authorized. The the {assignee} can do this simply by updating its own link contract index 
whenever it accepts a new link contract from another XDI authority. 

Here's how it works:

1. When {assignee} accepts a link contract with the authority for XDI server X, {assignee} indexes the {data} available through the link contract by adding the following set of statements to its own XDI graph: {data}/$is{operation}/{link-contract-X}.
2. When {assignee} wants to make a request for any piece of {data} from XDI server X, {assignee} looks at this index, finds AT LEAST ONE {link-contract-X} that allows the desired {operation} on the desired {data}. Note that there may be multiple link contracts from XDI server X that provide the permission, but here must be at least one or {assignee} never had permission to {data} to begin with.
   
3. {assignee} adds the statement {data}/$is{operation}/{link-contract-X} to the request message it sends to XDI server X.

Now when XDI server X receives the request from {assignee}, it has all 
four variables above, including {link-contract-X}. It simply needs to 
verify that the following two statements exist in its graph:
                   (i) {assignee}/$do/{link-contract-X}

                   (ii) {link-contract-X}/{operation}/{data)

It can do that lightning fast and then either allow or deny the request based on the result.

The need to include the {data}/$is{operation}/{link-contract-X} statement in every request does obviously shift part of the burden for efficient link contract processing to the client. But it so dramatically increases the efficiency of link contract processing for all XDI servers that I believe this is well worth requiring in the XDI protocol. IMHO, this burden is no more than asking the client to keep track of the private key it uses to sign messages it sends to the server.

I look forward to discussing this on tomorrow's call.

=Drummond