Capability-based Active Invocation Certificates

From Erights

(Difference between revisions)
Jump to: navigation, search
(Second attempt: Edit stream start)
(Relationship to using SAML authorization assertions)
(35 intermediate revisions not shown)
Line 715: Line 715:
[[User:Zarutian|Zarutian]] my second attempt at if from that direction:
[[User:Zarutian|Zarutian]] my second attempt at if from that direction:
// E syntax 0.9
# E syntax 0.9
def makeBrandPair := <elib:sealing.makeBrand>
def makeBrandPair := <elib:sealing.makeBrand>
def makePrinicipalsSealerRegister () :any {
def makePrinicipalsSealerRegister () :any {
   // make an FlexMap, does there exists any better way to do so?
   # make an FlexMap, does there exists any better way to do so?
   var register := [].asMap().diverge()
   var register := [].asMap().diverge()
   def shared_internal(principal :any, i :int(0..1)) :any {
   def shared_internal(principal :any, i :int(0..1)) :any {
Line 732: Line 735:
def [getSealer, getUnsealer] := makePrincipalsSealerRegister()
def [getSealer, getUnsealer] := makePrincipalsSealerRegister()
def swissHash__uriGetter {
def swissHash__uriGetter {
   // to be implemented
   # to be implemented
   // used by active certs issued by this vats public key.
   # used by active certs issued by this vats public key.
   to get(str :String) :any {
   to get(str :String) :any {
     throw("Not yet implemented")
     throw("Not yet implemented")
Line 739: Line 742:
def vatId := <<get the public key of this vat>>
def vatId := <<get the public key of this vat>>
def ActiveCapCertPrincipal {
  to coerce(specimen, optEjector) :near {
    # for now nothing passes this guard
    throw.eject(optEjector, "guard not yet implimented")
def ActiveCapCert__uriGetter
def ActiveCapCert__uriGetter
def ActiveCapCertMaker {
def ActiveCapCertMaker {
   to makeFrom(cert :String) :any {
   to makeFrom(cert :String) :any {
     def issuer := null  // will be filled in by th cert parsing code
     def issuer := null  # will be filled in by th cert parsing code
     def code :EExpr := e`$code` // ditto
     def code :EExpr := e`$code` # ditto
     // check here if signed by issuer as it is pretty expensive.
     # check here if signed by issuer as it is pretty expensive.
     def unsealer(box :any) :any {
     def unsealer(box :any) :any {
       return getUnsealer(issuer).unseal(box)
       return getUnsealer(issuer).unseal(box)
Line 772: Line 781:
     return ActiveCapCert
     return ActiveCapCert
   to makeCert(code :EExpr, authorizedParties :List(ActiveCapCertPrincipal)) :String {
   to makeCert(code :EExpr) :String {
    # prepend this vats pubkey to the code
    # and sign it
Line 794: Line 804:
6. In an authenticated save style (Like in Blizzards Diablo I only that any tampering with the save file invalidates it) ( perhaps usefull in scenarious where elib.serial is used).
6. In an authenticated save style (Like in Blizzards Diablo I only that any tampering with the save file invalidates it) ( perhaps usefull in scenarious where elib.serial is used).
== Relationship to using SAML authorization assertions ==
We did similar work using [ SAML authorization assertions as capabilities].  The only major difference that I see is that the active invocation certificates include trees of authorization assertion assertions.  Our work has been adopted by the State of California Health and Human Services Privacy Board as the means to authorize consulting physicians.  Go to and search for ZBAC.  -- Alan Karp

Latest revision as of 17:33, 9 February 2011



CapCert is a cryptographic object-capability system relying on signed certificates rather than transmitted secrets. Were all these signed certs transmitted in the clear, confidentiality of the messages would of course be lost. But no integrity would be lost. The basic philosophy, imprecisely stated:

  • Use signing key pairs to represent object identity, where the (public) signature verification key designates the object and the (secret) signing key represents the permission to be the object.
  • Designation is not permission, but rather, permission is represented by a tree of signed messages, to be validated as conforming to ocap message rules.
  • Each message is signed by its sender.
  • For the receiver and each argument in the message, the message carries its designation and the prior messages received by this sender, demonstrating that this sender has been permitted to invoke that receiver and those arguments.
  • The sender is implicitly permitted to invoke itself without further demonstration.
  • Initial non-self connectivity is by distinct "initial certs" issued by the designated object to a recipient and conveyed to the recipient by out-of-band means, i.e., not by CapCert invocations.
  • The arguments of a message may instead be code expressing an attenuation of a directly permitted designator. The sender thus grants the recipient only the ability to invoke that attenuation of the sender's permission.
  • Attenuations thus compose along delegation chains. Attenuators are instantiated by the server (vat) of the resource to be attenuated.

The main difference between the idea presented above and the concrete CapCert proposal presented below is that below, the signing keys are per vat. A signing key and an SwissHash (an authority-free designator which is a cryptohash of an object's SwissNumber) together designate an object in a vat.

It is a bizarre side effect of this system that the validatability of messages (that need to be checked by receivers) implies auditability. The auditability here is similar to that provided by Horton but different in at least the following ways:

  • CapCert auditing info is non-repudiable (in a technical, not a legal sense), whereas Horton auditing info is normally repudiable. (A non-repudiable variation of Horton is possible. A repudiable variation of CapCert may not be.)
  • In CapCert, the auditing info is revealed to the target of an invocation, including the chain of prior messages. In Horton, each delegated resource receives info about "who" delegated it to "whom", but only receives the message by which it is directly invoked.

We are unaware of any theory of composable auditability, or of reconciling confidentiality with auditability, so it is not yet clear which form of auditability to prefer, or what the other salient differences might be.

Material taken from stuff linked from to the archives of the E-lang mailing list:

First message

Mark S. Miller wrote Tue, 17 Oct 2000 14:55:48 -0700 in 1:

While Alan Kay was heaping criticism on the early Macintosh, 
he also quipped that the Mac was "the first computer good enough to 
criticize".  Such reminders are important, when one singles out the 
best of a field for intense criticism, while ignoring its crappy cousins.

Similarly, SPKI is the only PKI/Certificate system I know of that's good 
enough to criticize.  As explained in the Ode:

>The enforceable subset of SPKI can be seen as an off-line, auditable, 
>heavyweight, non-confinable, semi-capability system, as opposed to E's 
>on-line, repudiatable-by-default, lightweight, confinable, full-capability 
>system. Perhaps, by comparing these, we may figure out how to build systems 
>with some of the best of both.

SPKI-like certificate technology and real capabilities clearly should be 
able to get along, but until now it wasn't clear how.  The following 
proposal is inspired by Nikita Borisov's "Active Certificates" , although 
Nikita wasn't explicitly thinking in capability terms either, he 
nevertheless provided the bridge.

Development note: I plan to complete hash chaining proposal #1, and its 
application to simplify persistence and Pluribus, for the next release of E. 
Indeed, the reconstruction of Pluribus is the gating item for this next 
release.  The proposal in this note (#2) is more long term.  Neither E nor 
E's current users currently require it, though it would add significant 
value.  So don't expect it anytime soon.  However, because it makes a second 
use of hash chaining to represent cryptographic capabilities, 
it would be good to know early whether it can co-exist with our 
other cryptographic representations of capabilities.  I want to leave the 
door open to implement this proposal later as an upward compatible extension 
of E.  If you see any possible problems on this horizon, please fire away.

Before we get to the "active" stuff, let's strip from SPKI everything that 
isn't capability logic.  It's ok if the result isn't usable at this stage, 
as long as we get back to a usable result once we put the "active" stuff in.

                                        Deconstructing SPKI

After signature checking and expansion, we see from Section 6 of that there are only two kinds of SPKI 
certificates: Authorization Certificates (or 5-tuples) and Name Certificates 
(4-tuples).  Although the SPKI perspective on names is more capability-like 
than the other PKIs, it is still not the true capability perspective on 
names, so we get rid of the Name Certificate.

We state in the Ode that a SPKI Authorization Certificate corresponds to a 
capability message, but this isn't quite right.  A capability message not 
only authorizes Bob to access Carol, but it packages this authorization 
with information that should communicate to Bob why he's being given the 
argument authorizations (the label "foo"), and in which each individual 
authorization occupies a distinct argument position, corresponding to its 
role in the "why".

So a SPKI Authorization certificate corresponds to an argument in a 
capability message.  An argument in a capability message is normally 
understood to simply be a capability, so what distinction am I drawing?  At 
the capability layer of abstraction, there are no certificates, and the 
arguments of capability messages are simply capabilities.  While at the 
crypto-implementation layer of abstraction, SPKI is a non-bearer protocol.  

An individual SPKI Authorization Certificate implements a capability as 
passed specifically from Alice to Bob.  If Bob then further authorizes Dana, 
this next authorization is the same capability but a different certificate.  
If E's current SturdyRefs are off-line bearer capabilities, we might say 
that authorization certificates are SturdyArguments -- off-line per-message 

So now let's examine the parts of a SPKI Authorization Certificate with 
regard to representing an argument in a capability message.

1) Issuer:  Fingerprint of the public key corresponding to the private 
signing key of the party sending the message.  The tuple as a whole is also 
signed with the Issuer's signing key.  Great.  We'd keep this.  For us, the 
Issuer would be the Vat, and this fingerprint is the VatID.  In the standard 
example, this is VatID(A).  It's not yet clear whether this field needs to 
be expanded to uniquely designate Alice within VatA.

2) Subject: Fingerprint of the public signature key of the party the message 
is being sent to.  In the standard example, this is VatID(B).  It's not yet 
clear whether this field needs to be expanded to uniquely designate Bob 
within VatB.

3) The infamous do-not-delegate bit.  We need to eradicate this and then 
find a strong cleanser to remove its stench.  (For those new to this list, 
see .)

5) Validity dates -- the interval during which the certificate is considered 
valid.  It's not clear whether or not this needs to be primitive.  Also, 
it's most peculiar to include an interval start time rather than just a 
deadline.  Since the deadline corresponds to the expiration time of our 
existing SturdyRefs, I'm inclined to keep the deadline for now.

4) Authorization.  An S-expression which states what rights are being 
authorized.  Intermediaries on the delegation chain can use this 
S-expression language to express subsettings of the rights being passed on.
Complex rules compose these expressed subsettings to calculate the 
intersection of allowed rights.  This item is where the action is.  

First, we remove everything extraneous from this item.  This S-expression 
language is assumed to bottom out in human readable names, and in wildcards 
over such a names.  From a capability point of view, this name space is 
misguided, and the wildcards are therefore pointless.  The rights at the 
bottom of a subsetting expression should simply be the right to invoke a 
particular object.  With this as the right to be subsetted, the SPKI 
S-expression language is clearly useless as a means to subset it.  This will 
be where Nikita's "Active" ideas become crucial, but for now let's just drop 
all the subsetting logic.  What's left?  A unique unambiguous designator of 


Till now, when we wanted a cryptographic representation for designating 
Carol, we always used the pair <VatID(C), swissNumber(Carol)>.  However, if 
we use this representation here, we lose one of the really cool properties 
of Certificates: they can communicate authority without communicating 
secrets.  Indeed, the only information they require one to keep secret is 
one's own private signing key.  Because they rely on signature chains rather 
than secrets, distributed computation stitched together with certificates 
has very strong non-repudiation and auditing properties.  OTOH, it's vastly 
more expensive than on-line secret-based protocols like Pluribus.  Which one 
to use depends on context, so it would be good to be able to switch from 
one to the other while keeping the abstract capability semantics constant.


So, instead, we need the designator of Carol in the certificate to uniquely 
and unambiguously designate Carol without itself granting the authority to 
invoke Carol.  The authority to invoke Carol comes from the signature chain 
that reflects the sequence of introductions, starting with VatC, by which 
VatB came to attempt to invoke Carol.  Yes, believe it or not, I am 
advocating a kind of separation of designation and authority, but I don't 
believe that this separation has any semantics or presents any dangers.

                                 Hash Chaining Again

So let's say that the Certificate's Authorization field contains, not 
<VatID(C), swissNumber(Carol)>, but <VatID(C), hash(swissNumber(Carol))>.  
Since we assume hashes are strongly irreversible, knowledge of 
hash(swissNumber(Carol)) provides no knowledge of swissNumber(Carol), and 
only the latter is a secret that provides authority.  This representation 
also makes it easier to see how to interface between the bearer and the 
certificate worlds:

Given a live (a bearer on-line) reference to Carol (and given another 
capability on VatC (the function sturdyRef() that grant the authority to 
burden VatC with a storage obligation), Alice may currently ask VatC for a 
corresponding SturdyRef to Carol that's good until the requested expiration 
date.  A SturdyRef is a bearer off-line reference, so Alice can pass to Bob 
in an on-line message either a live reference or a SturdyRef designating 
Carol.  When Bob wants to invoke Carol, in he hold a SturdyRef, he first 
obtains a live reference from his SturdyReference, and then invokes on it.

Similarly, given a live reference to Carol, we can enable Alice to ask VatC 
for a corresponding Authorization certificate, signed by VatC, authorizing 
VatA to invoke Carol.  Alice, being within VatA, may later use this 
certificate to obtain a live reference to Carol, which she can then invoke on 
directly.  If Alice passes to Bob a derived certificate, signed by VatA 
authorizing VatB to access Carol, and including the previous certificate, 
then Bob may likewise use this certificate chain to obtain from VatC a live 
reference to Carol, which he can then invoke.

The combination of the two hash chaining proposals together look surprising 
natural.  The three numbers correspond to a three level hierarchy of 
authority to a capability:

1) arcHash(swissNumber) provides the authority to be the object, and 
  therefore receive invocations.
2) swissNumber corresponds provides the authority to invoke the object.
3) hash(swissNumber) uniquely and unambiguously designates an invokable 
  object, but does not provide the authority to invoke it.  Curiously, it does 
  provide the ability to compare two of these for equality.

It seems fine that each authority implies the ones after it, but not the 
ones before it.

                       Why we need off-line Messages, 
                             not just off-line Arguments

More later...

Second message

Mark S. Miller wrote Wed, 18 Oct 2000 14:23:17 -0700 in [1]:

                                    Message vs Invocation:
                                  A Terminology Correction.  

In the previous note, when I referred to "Message" I usually should have 
said "Invocation".  An invocation is a pair of a Message and a reference to 
the object that will receive the Message -- the Recipient.  In the 
Granovetter diagram, the fat arrow is a Message containing a reference to 
Carol as an argument.  The fat Message arrow combined with the thin reference 
arrow on which it rides -- the reference to Bob -- together constitute an 
Invocation.  With these definitions, it is clear that an authorization 
certificate represents an Invocation Argument rather than a Message 
Argument, since it authorizes only the Recipient.

The canonical example is a certificate from Alice authorizing Bob to invoke 
Carol.  If it were a Message Argument, then it would authorize whoever the 
Message were sent to, without that having been determined yet.

           Why we need off-line Invocations, not just off-line Arguments:
                     Another Lesson from the Confused Deputy

The punch line we all know from the Confused Deputy paper is "Don't separate 
designation from authority."  But this paper has enough punch lines to last 
a conventional lifetime.  Here's another.

Let's define authorization as the granting of authority.  One may conclude 
from the same tale that, even if designation and authority are kept 
together, "one must not separate authorization from invocation".  Why?  In a 
normal message-based capability system, the deputy only receives new 
authority as arguments of messages he receives asking him to do something.  
Each new authority has a separate position in the request, which represents 
its intended role in this request.  Only this context information gives the 
Deputy enough information to know what to do and what NOT to do with the new 
authority he's just been granted.

When authorization is communicated without such context, it's like receiving 
a key in the mail with no hint about what to do with it.  Or it's like an 
object system in which objects respond to the message


After an object receives this message, she can invoke arg if she chooses, 
but why would she ever choose to do so?  Were the separation of 
authorization from invocation truly this silly, no one would have thought to 
separate them.  Instead, no one seems to question separating them.  Why?  I 
can think of two reasons, both derived from the ACL paradigm:

1) Ambient Authority.  The following chain of reasoning seems very 
plausible, especially if it's not articulated or examined closely:  If 
object A attempts to perform action X, and object A has enough authority to 
perform action X, then object A's attempt to perform action X should be be 
permitted.  The implicit assumption is that, if A attempts X, then A must 
want to perform X.  If it wants to and it's allow to, clearly it should be 
permitted to.  In such a system, a hereIsSomethingYouMayFindUseful() message 
could simply add arg to the object's ambient authority.

The flaw is the assumption that it wants its attempt to succeed.  A deputy 
only brings to bear on an action those authorities that should be applied to 
the action, because it wishes the action to fail if these authorities are 
inadequate -- even if the deputy itself has further authority.  How does a 
deputy determine which authorities to apply to an action?  In a capability 
system, only according to how the deputy came to hold these authorities -- 
by initial endowment and by receiving them as invocation arguments.

2) Labelling.  In SPKI, an authorization certificate not only authorizes, it 
names the resources that it authorizes access to.  It's like receiving a key 
in the mail that's labelled with the name of the thing it opens.  This 
presumes a namespace that's meaningful among the various parties, 
necessitating that we solve a harder problem before we can solve the easier 
problem.  Our invocation perspective is much like the labelling perspective: 
the message carries a message name (in E, the verb) used by the receiver to 
understand why he's receiving the arguments.  However, the verb labels the 
reason for interacting, not the resource being authorized.  The latter needs 
no name -- the capability is all the designation we need, and all the 
designation we can trust.

Of course, once Alice is invoking Bob rather than just authorizing Bob, now 
Bob, like Carol, is something to be invoked.  Just as Alice or Bob must be 
authorized in order to invoke Carol, so must Alice be authorized to invoke 
Bob.  If invoking is the only means of authorizing, then Alice must be 
authorized to invoke Bob in order for Alice to be able to authorize Bob.  In 
situations where this is enforceable, this both provides the reference arrow 
missing from and 
removes the asymmetry between Subject and Resource.  Both would simply be 
objects, and shown as circles.  The full Granovetter diagram would be restored.

                          The Parts of an Invocation in E

So let's examine and give names to all the parts of an inter-vat Invocation 
in E.  Inter-vat Invocations in E may only be asynchronous, so we examine 
only the eventual ("<-") send expression:

       recipient <- verb(args...)

which acts like two different expressions depending on context:

a)    define result := recipient <- verb(args...)
b)    recipient <- verb(args...); null

Both of these asks the recipient to eventually perform the verb-named action 
using the provided arguments.  The request is queued on the vat of the 
recipient to be performed to completion when that vat is done with all prior 

#a is the general case: When the send expression occurs in a static context 
where its value is needed (evaluated for value), the send expression 
immediately returns a promise for the outcome of performing the request.  
This is a tail of a reference arrow whose head is encapsulated in the 
Message.  (This head serves a role much like a lambda continuation, expect 
that it normally provides only data-flow, not control-flow.)  We call this 
arrowhead the Resolver.

#b is an important optimization: When the send expression occurs in a static 
context where the value is not needed (evaluated for effect only), then we 
can avoid creating the promise for the return result.  In both cases, these 
messages are one-way in a control flow sense.  #b is also one-way in a 
data-flow sense.

So, putting it all together, an E on-line Invocation consists of

    Recipient (arrowtail)
        Verb (usually a String.  Always passed by copy.)
        Args (List of arrowtails conceptually, but may use any passing mode)
        Resolver (optional.  arrowhead for reporting outcome)

For off-line invocation certificates, let's tentatively make four semantic

1) Let's drop the optional Resolver.  It's hard to see any motivation for 
message pipelining in the off-line case.  In the absence of pipelining, most 
of the effects of the encapsulated Resolver can instead be provided with an 
explicit Resolver argument.  This decision does make it awkward to interface 
between the on-line and off-line worlds, so we may revisit it later.

2) Drop the requirement of order-preserving fail-stop at-most-once message 
delivery.  An on-line protocol can provide such guarantees cheaply.  For an 
off-line protocol, the expense would be too great to put at the foundations. 
Instead, we leave it up to the objects interacting via off-line invocations 
to deal with the problems resulting from the absence of these guarantees.  
I'm quite queasy with this, but it corresponds to the burden placed on the 
programmer by any of the other certificate systems.  Of course, this make it 
yet more awkward to interface the off-line and on-line worlds.

3) Do not provide built-in secrecy.  As with the other PKIs, invocation 
certificates are signed but not encrypted.  If their users wish to 
separately encrypt them, fine.

4) Provide built-in non-repudiation and some measure of auditability, at the 
price of a further loss of privacy.  Indeed, I believe this to be *the* 
tradeoff that should determine whether to use a certificate system or a 
bearer system.  Clearly, both have their place.

                Proposed Contents of an E Invocation Certificate

Since we've already got a notation for describing E invocations -- E -- I'll 
use it in the certificate proposal below.  A more politically acceptable 
proposal may use the XML representation of Kernel-E parse trees , since this would be less 
readable and more verbose.  If you wish, consider all the E notation in what 
follows to be syntactic sugar for such XML.

As with any lambda language, E expressions are evaluated within a lexical 
scope.  *.emaker files are evaluated in the E "universal scope" -- a 
immutable scope containing only transitively immutable objects that provide 
no authority -- such as the binding of "true" to the appropriate boolean.  
The expression in our invocation certificate can be evaluated (for effect 
only) within this scope, but we needs more.  The authorization certificates 
provide further capabilities, but only in this context.  We need a form of 
expression available within this context that wraps the authorization 
certificate data and effectively evaluates to the corresponding object 

Let's use E's syntactic sugar for URI expressions, and introduce a binding 
for "auth__uriGetter".  The expression <auth:...>, with an authorization 
certificate in place of the "...", evaluates to a capability to the 
authorized object.  Ignoring for a moment the issue of whether it evaluates 
to an on-line or an off-line reference, our standard example would now look 

   def bob := <auth:...Alice's authorization (from somewhere) to invoke Bob...>
   def carol := <auth:...Bob's authorization from Alice to invoke Carol...>
   bob <- foo(carol)

The first authorization would be signed by whoever enabled Alice to invoke Bob.

The second authorization would be signed by Alice, and would include Alice's 
authorization to invoke Carol.

The expression as a whole would be signed by Alice.

                           An Aside: Enabling Stronger Auditing

Should Alice really sign the authorization for Bob to invoke Carol, given 
that she's signing the message as a whole?  Interestingly, we get much 
stronger auditability if the answer is no.  If the answer is yes, then this 
authorization by itself is what Bob would present when invoking Carol, or 
when authorizing someone else to invoke Carol.  If the answer is no, then 
only this invocation as a whole demonstrates Bob's authorization to Carol.

Likewise, one level back on the chain, Alice's inclusion of the 
demonstration that she is authorized to invoke Carol (necessary for her 
authorization of Bob to be valid) would not be an authorization certificate, 
but rather the entire invocation certificate showing why she came to have 
that authority.  

If the argument authorizations aren't signed, and therefore don't need to be 
standalone, then they also don't need to list the "Subject", since this must 
always be the Recipient (Bob).  They all must also have the same Issuer 
(Alice), so we could list this once rather than per-argument.  All that's 
left or SPKI's 5-tuple is the Carol designation: <vatID(C), 
hash(swissNumber(Carol))>.  The authorization data would consist of this 
plus a chain of earlier Invocation certificates.

The authorization chains are now more like stack tracebacks, whose utility 
for debugging is well known.  Auditing and debugging may be more similar 
than we think.  However, the space overhead may be unreasonable for many uses.

Next Message:  I finally get to the "Active" stuff

Third message

Mark S. Miller wrote Tue, 24 Oct 2000 13:52:34 -0700 in [2]:

Sorry for teasing, but I realized that there was one other major chunk to 
explain before I could tie this thread together into a proposal for Off-Line 
Active Invocation Certificates (as inspired by Nikita's Active 
(Authorization) Certificates).  

The previous message (#2b) proposes Off-Line Invocation Certificates as an 
off-line derivative of on-line invocation. The addition of "Active" means 
the certificate additionally carries mobile code, as a more flexible 
replacement of the SPKI subsetting language.  Following our methodology, 
support for off-line mobile code should be derived from support for on-line 
mobile code.  While E was always designed for mobile code, we're not there 
yet, so the ideas weren't in concrete form.

This has now been repaired. is my 
proposal for a remote evaluation service, and syntactic sugar to support it.
Fire away.  If this proposal survives the initial volley, the off-line 
proposal will be built on it.

Fourth message

Mark S. Miller wrote Sat, 11 Nov 2000 08:44:55 -0800 in [3]:

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 .

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 .  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 ?  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" .  
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 , 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 

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.

Complete concrete syntax

Zarutians notes:

following is in bnf like form:

invocation_cert := issuer recipient verb args signature
issuer := principal
recipient := SturdyArg | SturdyRef | initcert
verb := string
args := arg*
arg := SturdyArg | passByConstruction
signature := <crypto signature of the whole cert (issuer, recipient, verb and args)>
SturdyArg := subject [ invocation_cert ]
  cert is omitted if VatID of subject is the issuer of this invocation_cert
VatID := principal
principal := public-key | cryptohash(public-key)
swissNr := [swiss Number]
initcert := issuer subject granted initcert_signature  -- gives subject an license to use granted as recipiant in an invocation_cert
subject := VatId hash(swissNr) 
granted := hash(swissNr)  -- points to an object on issuers vat
initcert_signature := <crypto signature of the whole cert (issuer subject granted)>

Mark S. Miller: hmm... this only supports certs that invoke an object on the recipient vat directly. So if one wants to build an attenuator via the cert on must direct the invocation at an object that makes the object pointed to by an SturdyArg available to the unserialized representation of the attenuator. (Which itself is an passByConstruction arg in that invocation.

How then to make SturdyArg possible exit in serialized object graph carried in passByConstruction arg in the cert?

Zarutian: One kludge is to have an publicly aviable deserializer on the subject vat that gets invoked by the capcert. The deserialier would be of the form: deserialize(passByConstructionDepiction, exit1, exit2, ..., exitn)

But above is rather nasty kludge. The only otherway to solve this is to make capcert aviable to the deserialization surgeon or, heck, the E evaluator (as an uriGetter).

I havent gotten to the point of how to bridge the online and offline world, that is make it possible for vatConnections to invoke capcerts (which could be solved by an capcert uriGetter as above) and vice versa (other than inducing the subject vat to issue an initcert).

Zarutian later: The proplem in above paragraph can be solved by making hash(swissNr) in the subject form optional. In those cases the VatId much match the one of the vatp connection and refers to the invoking object.

The kludge that markm pointed out can be solved by adding "universal_builder" to the reciepiant form.

Zarutian: I am trying to get at the proplem from an different direction:

active_cert := issuer script signiture
issuer := prinicpal
siginiture := publickey_sign(concat(issuer script), issuer.privatekey)
script := string containing code in E

def principal_seal(thing :any, recipiant :principal) :sealed_box {}
def principal_unseal(box :sealed_box) :any {}
def rootbase_get(swissHash :string) :any {}

def do_active_cert(cert :String) :any {
  // 1. check if the signiture is valid
  // 2. make a new scope that has
  //     do_active_cert (this procedure),
  //     principal_seal,
  //     principal_unseal that only unseals sealed_boxes ment for the cert issuer
  //     all the other stuff a safeScope has
  // 3. run the script in that scope
  // 4. return any results

one issuer is special, the one who is also the VatID.
active_certs issued by that issuer can invoke (call or eventual send) rootbase_get().
why? so an tree of active_certs can get the source authority.

Second attempt

Zarutian my second attempt at if from that direction:

# E syntax 0.9

def makeBrandPair := <elib:sealing.makeBrand>
def makePrinicipalsSealerRegister () :any {
  # make an FlexMap, does there exists any better way to do so?
  var register := [].asMap().diverge()
  def shared_internal(principal :any, i :int(0..1)) :any {
    if (not(register.maps(principal))) {
      register.put(principal, makeBrandPair(principal), true)
    return register.get(principal).get(i)
  def getSealer(principal)   { return shared_internal(principal, 0) }
  def getUnsealer(principal) { return shared_internal(principal, 1) }
  return [getSealer, getUnsealer]
def [getSealer, getUnsealer] := makePrincipalsSealerRegister()
def swissHash__uriGetter {
  # to be implemented
  # used by active certs issued by this vats public key.
  to get(str :String) :any {
    throw("Not yet implemented")
def vatId := <<get the public key of this vat>>
def ActiveCapCertPrincipal {
  to coerce(specimen, optEjector) :near {
    # for now nothing passes this guard
    throw.eject(optEjector, "guard not yet implimented") 
def ActiveCapCert__uriGetter
def ActiveCapCertMaker {
  to makeFrom(cert :String) :any {
    def issuer := null   # will be filled in by th cert parsing code
    def code :EExpr := e`$code` # ditto
    # check here if signed by issuer as it is pretty expensive.
    def unsealer(box :any) :any {
      return getUnsealer(issuer).unseal(box)
    def ActiveCapCert {
      to run(parameters :any) :any {
        def env := safeScope
        env with= ("parameters", parameters)
        env with= ("my_unsealer", unsealer)
        env with= ("get_sealerFor", getSealer)
        env with= ("ActiveCapCert__uriGetter", ActiveCapCert__uriGetter)
        if (issuer == vatId) {
          env with= ("swissHash__uriGetter", swissHash__uriGetter)
        return code.eval(env)
      to getSigner() :ActiveCapCertPrincipal {
        return issuer
      to getCode() :EExpr {
        return code
      to __optUncall() :Portrayal {
        return [ActiveCapCert__uriGetter, "get", [cert]]
    return ActiveCapCert
  to makeCert(code :EExpr) :String {
    # prepend this vats pubkey to the code
    # and sign it
bind ActiveCapCert__uriGetter {
  to get(str :String) :any { return ActiveCapCertMaker(str) }

Possible usages:

1. On a CapTP connection (the messages from the sending vat are treated like they were signed by that vat).

2. A chain of simple authorization certs.

3. A tree of embedded such chains.

4. A symbolon style of authorizations. (Alice gets an authroization/active cert from Bob that can only be used if Carol gives Alice an authroization/active cert that gives the former cert authority which is given (and possibly attenuated) onward to Alice)

5. In a PostalRef scenario. (PostalRefs are offline like SturdyRefs but you can send it eventual sends which will then be written out as authroization/active cert(s))

6. In an authenticated save style (Like in Blizzards Diablo I only that any tampering with the save file invalidates it) ( perhaps usefull in scenarious where elib.serial is used).

Relationship to using SAML authorization assertions

We did similar work using SAML authorization assertions as capabilities. The only major difference that I see is that the active invocation certificates include trees of authorization assertion assertions. Our work has been adopted by the State of California Health and Human Services Privacy Board as the means to authorize consulting physicians. Go to and search for ZBAC. -- Alan Karp

Personal tools
more tools