[E-Lang] Hash Chaining & Capabilities, Proposal #2b:
Off-Line Invocation Certificates
Mark S. Miller
Wed, 18 Oct 2000 14:23:17 -0700
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 http://www.erights.org/elib/capability/ode/images/spki.gif 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
So, putting it all together, an E on-line Invocation consists of
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
http://www.erights.org/elang/kernel/index.html , 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
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