[E-Lang] Hash Chaining & Capabilities, Proposal #2d: Deputizing Remote Vats

[Mark S. Miller]

Here is the long delayed next step in this proposal for Capability-based 
Active Invocation Certificates.  For an indefinitely postponed hypothetical 
piece of engineering, this thread is taking up a distressing amount of 
paper.  *If* off-line certificates are indeed useful in an increasingly 
on-line world (a questionable assumption), then I believe this thread will 
prove important.  Thanks for your indulgence.

(Alan and Bill, you guys are the most qualified to address this 
questionable assumption, as you've both been heavily involved in engineering 
efforts with similar goals on both sides of this coin.  (E-Speak 2.2 vs 
E-Speak 3.0/SPKI; Indra & Pluribus vs SPKI).  Is there a compelling 
need for off-line certificates?  Do they address a real problem?)

Previous messages in this thread have already established a strong 
correspondence between Invocation Certificates and E/Pluribus messages -- 
they are simply the off-line and on-line embodiments, respectively, of a 
Granovetter/capability message.  The semantic differences are only due to 
the differences between our notions off-line and on-line (significantly 
clarified in answer to Bill's question), plus that we only define off-line 
certificates to be the equivalent of sendOnly messages -- messages without a 
continuation 
http://www.erights.org/elib/concurrency/msg-passing.html#sendOnly .

The remaining element, and the element that motivated this whole thread in 
the first place, is the not-yet-explained "Active" feature of our 
certificate proposal.  Rather than explain Active certificates directly, 
this message will show the on-line equivalent of this feature: 
Deputizing Remote Vats with Mobile Code.  That's why we introduced the 
Evaluator earlier.

Let's construct the standard deputy scenario 
http://www.erights.org/elib/capability/deputy.html .  Let's say that Alice 
had a prior reference to Mallet and the power, P, and that Alice constructs 
Bob in order to provide Mallet with reduced authority over the power.  For 
example, let's say P is a mutable slot with getValue() and 
setValue(newValue) messages, and that Alice wishes to provide Mallet only 
the authority to see the current value, but not to set it.  As a contrived 
embellishment whose purpose will be clear later, let's say Alice constructs 
Bob to accept but ignore the setValue message.  Alice might define Bob thus:

    define BobMaker new(P) :any {
        define Bob {
            to getValue :any { P getValue }
            to setValue(newValue) {}
        }
    }

Alice would then give Mallet

    Mallet foo(BobMaker new(P))

However, now let's say Alice, P, and Mallet are all in three separate vats:
VatA, VatP, and VatM.  The code would then read

    define BobMaker new(P) :any {
        define Bob {
            # returns a promise for the value
            to getValue :any { P <- getValue }
            to setValue(newValue) {}
        }
    }

    Mallet <- foo(BobMaker new(P))

>From a security point of view, this is ideal.  Bob is Alice's deputy, and 
Bob runs on VatA, and therefore Alice's TCB.  Alice necessarily 
"trusts" her own TCB, not because she necessarily has higher confidence in 
its trustworthiness, but because she can't help but be fully vulnerable to 
it, so she may as well stop worrying.  Since she already has this 
vulnerability, she does not acquire any new vulnerability by trusting the 
same TCB to run Bob.

Unfortunately, depending on the particulars of the situation, this choice 
may not be ideal from a distributed systems point of view.  Any time Mallet 
wishes to exercise his reduced power, the request has to go through Bob 
(necessary) and therefore through VatA (unfortunate).  Besides the obvious 
performance cost, Alice may be expecting VatA to go off-line soon, or become 
otherwise inaccessible to VatM and VatP.  Let's say Alice also expects VatM 
and VatP to remain accessible to each other.  If Alice were introducing 
Mallet to all of P, our standard Granovetter introduction protocol would put 
VatM and VatP in direct contact, and Alice could drop out of the picture 
without disrupting their further communication.  How can Alice introduce 
Mallet to the "some of P" represented by Bob, and still be able to drop out?

I'm sure you can all see what's coming: there are only two other Vats in the 
picture.  Alice's only two sensible choices are to instantiate Bob on VatM 
or on VatP.  Both subject Alice to greater security risk that Bob on VatA.

Bob on VatM:

If Alice trusts VatM more than Mallet, this can be a sensible choice 
(depending on the nature of trust in VatM).  Alice cannot rationally trust 
VatM less than Mallet.  If she trusts them the same, then this is a bad 
choice, since VatM is being given direct access to P.

Bob on VatP:

P is necessarily vulnerable to VatP, so any dishonest execution of Bob 
that's equivalent to corruption of P creates no loss of security.  What 
greater damage can a corrupt VatP cause?  Alice's intended Bob behavior 
prevents Mallet from sending capabilities to P as argument of setValue 
message.  Is this a form of distributed capability confinement 
http://www.erights.org/elib/capability/dist-confine.html ?  With Bob on 
VatA, it might seem that Mallet and P cannot arrange for Mallet to send 
capabilities to P.  Unfortunately, the getValue message, as currently 
defined, allows P to "send" (reveal, as the outcome of a prior send) an 
arbitrary capability, which is enough to work around the restriction.  
However, Bob might be more constraining.  A Bob that only allowed integers 
to be gotten from P would prevent Mallet from sending a capability to P.

If we run Bob on VatP and VatP is corrupt (and in cahoots with Mallet and 
P), then it can give to P capabilities from Mallet that Alice coded Bob to 
prevent.  But wait a second, if VatP is corrupt, can't it separately 
establish a channel between Mallet and P?  Only with VatM's cooperation.  So 
we're back to relying on trust in VatM.

When the location question comes up, I suspect capability confinement will 
rarely be a concern (though it's good to check!).  Therefore, when 
non-security issues argue against putting Bob on VatA, security issues will 
typically argue for putting it on VatP.  Note that the non-security issues 
are almost perfectly indifferent between VatP and VatM.

Ok, so how does Alice instantiate Bob on VatP, and give Mallet access to 
that Bob.  An economist turned programmer might say "Assume an Evaluator" 
http://www.erights.org/javadoc/org/erights/e/elang/evm/Evaluator.html .  
Specifically, an Evaluator on VatP (exported by VatP's TCB), let's say 
called evalP in Alice's scope.  Alice only needs to change her code to:

    meta <- eval(evalP, define BobMaker new(P) :any {
        define Bob {
            # returns a promise for the value
            to getValue :any { P <- getValue }
            to setValue(newValue) {}
        }
    })

    Mallet <- foo(BobMaker <- new(P))

This asks the Evaluator on VatP to evaluate the expression defining 
"BobMaker".  It also defines "BobMaker" in this (Alice's) scope to be a 
promise for that remote BobMaker.  We then send a remote request on this 
BobMaker-promise to create a new Bob (BobMaker <- new(P)).  The value of 
this expression is a promise for Bob, which is then sent to Mallet.

(Just to show off message pipelining 
http://www.erights.org/elib/concurrency/pipeline.html , all three of these 
messages go out immediately, without VatA waiting to hear anything back.)

The analogy with the SPKI subsetting language should be clear: Bob expresses 
a subsetting of the authority of P.  Alice, who has authority P, is giving 
Mallet only that subset, but is handing over the interpretation of her 
subsetting intentions to VatP.  When Mallet goes to exercise his authority, 
the subsetting is enforced by VatP, hopefully according to Alice's 
instructions.

The main difference, due to Nikita, is that we're expressing the subsetting 
in a general purpose programming language.  This allows abstraction as well 
as subsetting-by-thinning.  For example, a covered call option is a deputy 
subsetting-by-abstraction the underlying instrument, such as stock.  One could 
never express this kind of subsetting in a data-language such as SPKI provides.