[cap-talk] Petnames versus E-order with ocaps

[David-Sarah Hopwood]

Bill Frantz wrote:
> erights at gmail.com (Mark Miller) on Friday, January 30, 2009 wrote:
>>
>> Please reread the explanation of WormholeOp
>> <http://www.erights.org/elib/distrib/captp/WormholeOp.html>. With WormholeOp,
>> if Alice sends a resolved reference to Bob, it arrives resolved, so it can
>> immediately be assigned a petname on arrival. But VatA also sends to VatB
>> all of VatA's remaining traffic for VatC that was unacked at the time it is
>> sending this message to VatB, all encrypted so only VatC can decrypt. This
>> includes all of Alice's prior messages for Carol. VatB will present this
>> encrypted traffic to VatC prior to redeeming the serialized ref to Carol.
>> Therefore, with WormholeOp, Bob can immediately assign a petname without
>> losing pipelining.
> 
> It sounds to me like this algorithm gives Bob a way to deny Carol's service
> to Alice by just throwing the redirected communication on the floor.

I think there is a fifth plausible solution to the conflict described on
the WormholeOp page. It is a variation on solution 2, which I'll quote here
for context:

# 2. Wait for drainage. Block all further communications from VatB to VatC
#    until all communications from VatA to VatC prior to the introduction
#    have drained out, or until the VatA/VatC timeout period expires,
#    killing the connection. This could repeatedly impose a huge cost on
#    VatB for the sake of only a few objects in VatB. While E avoids making
#    any claims about resistance to denial of service attack, this would be
#    too egregious a vulnerability to such an attack.

As Bill Frantz points out, WormholeOp creates a different DoS vulnerability.
It is possible to avoid both of these vulnerabilities (and maximize
pipelining subject to the E-order constraint) by only delaying the
reception by Carol of messages sent on Bob's reference to Carol, rather
than all messages sent between VatB and VatC.

I'd better make sure that I have a correct idea of precisely what the
E-order constraint is, though, since I've got it wrong before. I think
that E-order can be modelled as follows (ignoring some additional
complexities of E such as broken promises):

 - each sent message has a unique MessageID.

 - a vat has a collection of mutable objects. Each object is associated
   with a unique ObjectID, and a set of MessageIDs of messages that it
   has already acted on. A vat also has a collection of received
   (promise, message) pairs.

 - a promise, in a given vat, is a mutable data structure that includes
   the fields
     referentCell:
         a pointer to a mutable cell that, when the promise is
         settled, will contain the ObjectID of the referenced object.
     lastMessage:
         the MessageID of the last message that *must* have been acted
         on by the referenced object before it can receive any messages
         sent on this promise.

   (If a promise is shallow-copied, the referentCell will be aliased
   between the copy and the original.)

 - when a message M is sent to a promise P,
    - P and each promise contained in M are shallow-copied, giving
      (P', M').
    - P.lastMessage is then updated to be the MessageID of M.
    - if and when P (or equivalently, P') is settled, (P', M') is
      forwarded to the vat of the promise's referent.

 - for each turn in a given vat V, the vat implementation
    - selects an arbitrary received (P'', M''), where P'' is a
      settled reference to object O in V, and P''.lastMessage
      indicates a message that has already been acted on by O.
    - causes O to act on M''.

   (The constraint on P''.lastMessage is sufficient by itself to
   enforce E-order; there are no explicit FIFO queues in the model.)

Pipelining can be maximized by implementing this model fairly literally.
Messages are held by the receiving vat until they can be acted on in an
order that is consistent with E-order. (To avoid resource exhaustion, a
vat could have a memory quota for held messages received from each other
vat.) An implementation does not actually need to record *all* of the
MessageIDs of messages already acted on by a given object, only those
that might still be in some promise's lastMessage field (which is a
distributed garbage collection problem with some potential optimizations
specific to this context).

The consequence of this approach for the petname system is similar to
the WormholeOp approach: if Alice sends a settled promise to Bob, it will
arrive settled, so it can immediately be assigned a petname on arrival.

-- 
David-Sarah Hopwood ⚥