[E-Lang] Hash Chaining & Capabilities, Proposal #1b: Simplifying Pluribus

[Mark S. Miller]

At 12:38 AM 10/15/00, Mark S. Miller wrote:
>With hash chain proposal #1, it seems we could have persistence before we have
>orthogonal persistence, and we can simplify the part of Pluribus protocol 
>that seems too messy.  With hash chain proposal #2, [...]  This note explains 
>proposal #1.  A later note will explain proposal #2.

Well, not quite.  The first note only explained the implications of proposal 
#1 for persistence.  This note explains how to use proposal #1 to simplify 
Pluribus.  The next note will discuss proposal #2.


                       Why Granovetter + Pipelining Was Awkward
                                      and how to fix it


Message pipelining has an awkward interaction with the <vatID, swissNumber> 
representation of capability tails.  When Alice sends an asynchronous 
message to Carol

    define resultC := carol <- message(...)

Alice is left holding resultC, which is the tail of a new arrow whose head 
will come to designate the outcome of delivering the message.  The tail is 
in VatA and the head will come to be (initially at least) in VatC.  Let's 
say that, before VatA hears anything back from VatC, Alice decides to pass 
this promise-for-a-result to Bob:

    bob <- foo(resultC)

This is the standard three machine Granovetter operator explained in the 
Ode, but with a crucial difference.  In the standard case, VatC assigns the 
swissNumber to Carol when a reference to Carol is first exported from VatC.  
It is this swissNumber that VatA passes to VatB, and that VatB then uses to 
establish a direct connection to Carol.

In the pipelined case explained above as well, VatA needs a swissNumber to 
pass to VatB to represent the arrowtail that designates an arrowhead on 
VatC.  Unlike the standard case, VatC is not in a position to assign this 
swissNumber, since VatA needs to know the number, in order to pass it to 
VatB, before hearing anything back from VatC.  Indeed, only VatA is in a 
position to assign the number.  However, this number will be used by VatB to 
look up an association in VatC's swissNumber table.  

Since VatA and VatC are assumed to be mutually suspicious, VatA should not 
be able to simply enter new swissNumber associations into VatC's swissNumber 
table.  Why?  Because being a client of an object is enough to know its 
swissNumber, but being a client of an object should not be enough to claim 
to be the object.  Were nothing done to repair the above description, then 
VatB, on hearing the number, could make a conflicting claim to VatC that 
this number should be used to designate the result of a different send.  
VatB's claim could well arrive before VatA's claim.

The current Pluribus protocol repairs this correctly but awkwardly.  When 
VatA sends a pipelined message to VatC it indeed provides a swissNumber.  
However, VatC's table isn't a mapping from swissNumbers to objects, but a 
mapping from a <vatID, swissNumber> pair to an object.  Unlike our previous 
discussion of such pairs, the vatID in this pair is the vatID of the Vat 
that generated this swissNumber.  In our example, VatC would enter into its 
table a mapping from <vatID(A), swissNumber(resultC)> to the result of 
delivering the message.  The bearer representation of the tail of this arrow 
that VatA would pass to VatB would then be <vatID(C), <vatID(A), 
swissNumber(resultC)>>.  While this works, it's unpleasantly complicated.

Using proposal #1, we can make the pipelined case more closely resemble the 
standard case.  VatA would still generate a new unguessable number, but this 
would not be the swissNumber for resultC.  Rather, the hash of this number 
would be the swissNumber.  Let's call this number the arcHash of the 
swissNumber of resultC.  When sending the pipelined message, VatA would send 
the arcHash to VatC, whereupon both can hash it to get resultC's 
swissNumber, and both can then forget the arcHash if they wish.  

VatC's table can once again simply map from swissNumbers to objects, 
irrespective of the origin of those numbers.  When Alice then sends resultC 
to Bob, VatA would simply send <vatID(C), swissNumber(resultC)> to VatB, 
which would then send it to VatC to look up the result.  Even though both 
VatA and VatC hashed the arcHash and threw it away, we still have VatA 
communicate the arcHash to VatC, rather than the swissNumber itself, only in 
order for VatA to establish with VatC that it has the authority to determine 
what object is designated by that number within VatC.  Since VatB is never 
informed of this number, it can't engage in the above attack.